명제 논리(propositional logic)

명제(proposition)

 

참 또는 거짓 중 하나를 나타내는 선언적 문장이다.

 

명제인 예:

1. 미국의 수도는 워싱턴 D.C이다.

2. 캐나다의 수도는 토론토이다.

명제가 아닌 예:

1. 몇 시입니까?

2. 이것을 주의 깊게 읽어라.

 

명제를 표현하는 변수를 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판