[이산 수학] 합성 명제

합성 명제

논리 연산자의 우선 순위

• 합성 명제는 하나 이상의 단순 명제를 논리 연산자로 결합한 명제를 말한다.
• 합성 명제의 진릿값은 각 단순 명제의 진릿값에 따라 달라지지만, 논리 연산자의 연산 순서 또한 진릿값을 결정하는 데 영향을 미친다.

우선순위	논리 연산자
1	$\neg$
2	$\land$
3	$\lor$
4	$→$
5	$↔$

 

• 합성 명제에서 괄호로 묶은 연산은 먼저 해야 한다.
  • 예) $(\neg p \lor q) \land r$
    • $\lor$ 가 $\land$ 보다 우선 순위가 낮지만, $\lor$ 는 괄호 안의 연산이므로 $\neg p$ 와 `q` 를 $\lor$ 연산한 후 `r` 과 $\land$ 연산한다.
    • 그러므로 합성 명제  $(\neg p \lor q) \land r$ 과  $\neg p \lor q \land r$ 의 진릿값은 전혀 다르다.

 

$(\neg p \lor q) \land r$ 의 진리표

`p`	`q`	`r`	$\neg p$	$(\neg p \lor q)$	$(\neg p \lor q) \land r$
T	T	T	F	T	T
T	T	F	F	T	F
T	F	T	F	F	F
T	F	F	F	F	F
F	T	T	T	T	T
F	T	F	T	T	F
F	F	T	T	T	T
F	F	F	T	T	F

 

$\neg p \lor q \land r$ 의 진리표

`p`	`q`	`r`	$\neg p$	$q \land r$	$\neg p \lor q \land r$
T	T	T	F	T	T
T	T	F	F	F	F
T	F	T	F	F	F
T	F	F	F	F	F
F	T	T	T	T	T
F	T	F	T	F	T
F	F	T	T	F	T
F	F	F	T	F	T

 

합성 명제의 종류

• 합성 명제는 진릿값에 따라 세 가지 종류로 구분할 수 있다.

 

항진 명제(Tautology : T  )

합성 명제를 구성하는 단순 명제의 진릿값에 상관 없이 합성 명제의 진릿값이 항상 참(T)인 명제

• 합성 명제 $p \lor \neg p$ 의 진리표를 보면, 단순 명제 `p` 의 진릿값이 참(T)이든 거짓(F)이든 상관 없이 $p \lor \neg p$ 의 진릿값은 참(T)이다. 그러므로 합성 명제 $p \lor \neg p$ 는 항진 명제이다.

`p`	$\neg p$	$p \lor \neg p$
T	F	T
F	T	T

 

 

모순 명제(Contradiction : F )

합성 명제를 구성하는 단순 명제의 진릿값에 상관 없이 합성 명제의 진릿값이 항상 거짓(F)인 명제

• 합성 명제 $p \land \neg p$ 의 진리표를 보면, 단순 명제 `p` 의 진릿값이 참(T)이든 거짓(F)이든 상관 없이 $p \land \neg p$ 의 진릿값은 거짓(F)이다. 그러므로 합성 명제 $p \lor \neg p$ 는 모순 명제이다.

`p`	$\neg p$	$p \land \neg p$
T	F	F
F	T	F

 

사건 명제(Contingency)

항진 명제도 모순 명제도 아닌 합성 명제