| 명제(proposition) |
참 또는 거짓 중 하나를 나타내는 선언적 문장이다.
명제인 예:
-
미국의 수도는 워싱턴 D.C이다.
-
캐나다의 수도는 토론토이다.
명제가 아닌 예:
-
몇 시입니까?
-
이것을 주의 깊게 읽어라.
명제를 표현하는 변수를 p, q, r, s 등 문자로 나타낸다.
명제의 진리값(truth value)이 참일 때는 T, 거짓일 때는 F로 나타낸다.
더 나누어질 수 없는 명제는 단순명제이다.
부정(negation)
$p$가 명제라 하면 $p$의 부정은 $\neg p$ or $\bar{p}$로 나타내고, "It is not the case that p."의 문장이 된다.
<진리표>
| $p$ | $\neg p$ |
| $T$ | $F$ |
| $F$ | $T$ |
논리곱(conjunction)
$p$와 $q$가 명제라 하면 $p \land q$ 로 나타내는 $p$와 $q$의 논리곱은 명제 "p and q"이다.
$p$, $q$가 모두 참일 때만 참이다.
<진리표>
| $p$ | $q$ | $p \land q$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $F$ |
논리합(disjunctiuon)
$p$와 $q$가 명제라 하면 $p \lor q$로 나타내는 $p$와 $q$의 논리합은 명제 "p or q"이다.
$p$, $q$ 중 하나만 참이면 참이다.
<진리표>
| $p$ | $q$ | $p \lor q$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
배타적 논리합(exclusive disjunction)
$p$와 $q$가 명제라 하면 $p \oplus q$로 나타내는 $p$와 $q$의 논리합은 명제 "p exclusive-or q"이다.
$p$, $q$ 중 어느 하나만 참이면 참이다.
<진리표>
| $p$ | $q$ | $p \oplus q$ |
| $T$ | $T$ | $F$ |
| $T$ | $F$ | $T$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $F$ |
| 조건문(함축, implication) |
$p$와 $q$가 명제라 하면 조건문 $p \rightarrow q$는 명제 "if p, then q"이다. $p$를 가정(전제, 전항)이라 하고 $q$를 결론(결과)라고 한다.
다음처럼 여러 형태로 표현된다.
if $p$, then $q$. ($p$이면 $q$이다)
$p$ implies $q$. ($p$는 $q$를 함축한다)
$p$ only if $q$. ($q$일 경우에만 $p$이다)
a sufficient condition for $q$ is $p$. ($q$의 충분조건은 $p$이다)
a necessary condition for $p$ is $q$. ($p$의 필요조건은 $q$이다)
<진리표>
| $p$ | $q$ | $p \rightarrow q$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $T$ |
| $F$ | $F$ | $T$ |
| 역(converse), 대우(contrapositive, 이(inverse) |
조건문 $p \rightarrow q$로부터
$q \rightarrow p$를 $p \rightarrow q$의 역,
$\neg q \rightarrow \neg p$를 $p \rightarrow q$의 대우,
$\neg p \rightarrow \neg q$를 $p \rightarrow q$의 이라고 한다.
| 동치(equivalent) |
두 개의 복합명제가 항상 같은 진리값을 가질 경우 이들을 동치라 한다.
명제 $p \rightarrow q$와 명제 $p \rightarrow q$의 대우 $\neg q \rightarrow \neg p$는 서로 동치다.
명제 $p \rightarrow q$의 역 $q \rightarrow p$과 이$\neg p \rightarrow \neg q$는 서로 동치다.
| 상호 조건문(biconditional) |
$p$와 $q$가 명제라 하면 조건문 $p \iff q$는 명제 "p if and only if q"이다. $p$와 $q$가 동일한 진리값을 가질 때 참이다.
<진리표>
| $p$ | $q$ | $p \iff q$ |
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $T$ |
참고자료
Rosen의 이산수학 8판