[계산논리] 명제논리의 문법 2. 명제식의 정의와 진리표

WFF : World Fitness Federation

 

 

 

이전 글에서 명제 변수의 의미와 몇 가지 연결사에 대해 알아보았다.

연결사 부분만 한 눈에 보기 좋게 다시 정리해보자면 아래와 같다.

 

연결사 $($복습$)$

 

1. $\neg$, NOT

명제의 참, 거짓을 뒤집는다.

$\neg$$($참인 명제$)$ = 거짓

$\neg$$($거짓인 명제$)$ = 참

 

2. $\vee$, OR

두 명제를 '또는'의 의미로 연결한다. 둘 중 하나만 참이면 참이다. 

$($참인 명제$)$ $\vee$ $($참인 명제$)$ = 참

$($참인 명제$)$ $\vee$ $($거짓인 명제$)$ = 참

$($거짓인 명제$)$ $\vee$ $($참인 명제$)$ = 참

$($거짓인 명제$)$ $\vee$ $($거짓인 명제$)$ = 거짓

 

3. $\wedge$, AND

두 명제를 '그리고'의 의미로 연결한다. 두 명제 모두 참일 때만 참이다.

$($참인 명제$)$ $\wedge$ $($참인 명제$)$ = 참

$($참인 명제$)$ $\wedge$ $($거짓인 명제$)$ = 거짓

$($거짓인 명제$)$ $\wedge$ $($참인 명제$)$ = 거짓

$($거짓인 명제$)$ $\wedge$ $($거짓인 명제$)$ = 거짓

 

4. $\rightarrow$, Implication

두 명제를 '만약'의 의미로 연결한다. 앞의 명제가 참인 동시에 뒤의 명제가 거짓일 때만 거짓이다.

$($참인 명제$)$ $\rightarrow$ $($참인 명제$)$ = 참

$($참인 명제$)$ $\rightarrow$ $($거짓인 명제$)$ = 거짓

$($거짓인 명제$)$ $\rightarrow$ $($참인 명제$)$ = 참

$($거짓인 명제$)$ $\rightarrow$ $($거짓인 명제$)$ = 참

 

5. $\leftrightarrow$, Equivanlence

두 명제를 '동치'의 의미로 연결한다. 두 명제의 진리값이 같을 때만 참이다.

$($참인 명제$)$ $\leftrightarrow$ $($참인 명제$)$ = 참

$($참인 명제$)$ $\leftrightarrow$ $($거짓인 명제$)$ = 거짓

$($거짓인 명제$)$ $\leftrightarrow$ $($참인 명제$)$ = 거짓

$($거짓인 명제$)$ $\leftrightarrow$ $($거짓인 명제$)$ = 참

 

 

 

더 자세한 글은 이전 글을 참조.

https://hellworld.tistory.com/19

 

이제 명제 변수와 연결사를 이용해서 명제식을 수학적으로 정의해보려고 한다.

 

 

 

 

명제식의 정의

 

명제식은 집합을 이용해서 정의한다.

명제식의 집합을 우선 정의한 후, 해당 집합의 원소를 명제식이라고 정의하는 것이다. 

 

그 전에 먼저 명제 변수의 집합을 정의해야 한다.

집합 $V$를 모든 명제 변수의 집합이라고 정의하자. 

즉, 집합 $V$에는 $P$, $Q$와 같은 명제 변수가 들어가있다. 

$($명제 변수는 T, F와 같은 진리값을 대입할 수 있는 '변수'를 말한다. $)$

 

이제 명제식의 집합 $WFF$를 정의하자.

$WFF$는 Well Formed Formula for Propositional Logic에서 앞 세 단어를 따 이름을 붙인 것이다. 

 

$WFF$는 모든 명제식의 집합이다. 이 집합의 정의는 아래와 같다. 

 

1. 명제 상수 $T, F \in WFF$

2. 명제 변수의 집합 $V$의 모든 원소는 $WFF$의 원소이다. 즉, $V \subseteq WFF$

3. $WFF$의 모든 원소 $P$에 대해 $\neg P \in WFF$

4. $WFF$의 모든 원소 $P, Q$에 대해 $(P \wedge Q), (P \vee Q), (P \rightarrow Q), (P \leftrightarrow Q) \in WFF$

5. 위에서 언급한 문자열을 제외한 그 어떤 문자열도 $WFF$의 원소가 아니다. 

 

 

 

이렇게 $WFF$의 정의를 알아보았다. 

재귀적으로 정의되어 직관적으로 이해가 잘 되지 않을 수도 있다. 

말로 풀어서 설명하자면 명제 상수, 명제 변수 그리고 이들을 연결사로 묶은 것만이 $WFF$의 원소라는 것이다. 

 

그리고 명제식은 바로 $WFF$의 원소가 명제식인 것이다. 

예시를 통해 명제식으로 어떤 것이 있는지 알아보자. 

 

명제 변수 $A$는 명제식이다. 

명제 변수 $B$는 명제식이다. 

$(A \vee B)$는 명제식이다. 

$((A \vee B) \wedge B)$는 명제식이다.

$(((A \vee B) \wedge B) \rightarrow (A \leftrightarrow B))$는 명제식이다. 

등등등...

 

 

 

 

 

명제식의 진리값

 

명제식의 진리값을 구해보자.

즉, 명제식이 언제 참이 되고 언제 거짓이 되는지 알아보자는 것이다.

 

명제식의 진리값을 구하는 방법은 여러가지가 있다.

그중에서 진리표를 그리는 것이 가장 이해하기 쉽고 간단한 방법이다.

명제식의 진리값을 구하는 다른 방법들은 나중에 다룰 예정이다. 

 

 

우선 가장 간단한 $\neg$에 대하여 진리표를 그려보자.

$A$	$\neg A$
0	1
1	0

 

즉, 명제 변수 $A$의 값이 0일 때는 명제식 $\neg A$이 1,  $A$의 값이 1일 때는 $\neg A$이 0이 된다는 의미이다. 

 

 

이번에는 $\vee$에 대해 진리표를 그려보자.

$A$	$B$	$A \vee B$
0	0	0
0	1	1
1	0	1
1	1	1

 

명제 변수 $A$가 0이고 $B$가 0일 때는 명제식 $A \vee B$이 0이 되고.... 라는 의미이다.

 

 

진리표를 그리는 것은 명제 변수의 값이 0, 1이 되는 모든 경우의 수에 대해 전체 명제식의 값을 구하는 과정이다. 

명제 변수가 1개면 2개의 경우의 수, 2개면 4개의 경우의 수, ... $n$개일 때는 $2^{n}$개의 경우의 수가 있다. 

 

 

 

조금 더 복잡한 명제식의 진리표도 그려볼 수 있겠다. 

$((A \rightarrow B) \wedge \neg A)$의 진리표를 그려보자. 

$A$	$B$	$(A \rightarrow B)$	$\neg A$	$((A \rightarrow B) \wedge \neg A)$
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	1	0	0

 

 

연습문제

명제변수가 3개인 명제식도 진리표를 그릴 수 있을까?

$(A \rightarrow B)  \vee (A \wedge \neg C)$의 진리표를 그려보자.