[계산논리] 명제논리의 문법 3. 명제식의 의미와 모델

 

 

모델 장윤주

 

 

 

명제식의 의미

 

이전 글에서 명제식을 정의했다. https://hellworld.tistory.com/20

명제식은 참/거짓, 참과 거짓이 될 수 있는 명제변수, 연결사로 명제변수를 묶은것으로 정의된다. 

그리고 진리표를 그려서 명제식의 값을 판단해보았다.

 

이번 글에서는 명제식을 이해할 수 있는 다른 방법을 소개할 예정이다. 

 

우선, 이전 글에서 소개했던 명제식과 그에 해당하는 진리표를 그려보자.

 

 

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

 

 

이 진리표의 의미를 좀 더 자세히 분석해보도록 하겠다.

 

 

왼쪽 두 줄은 명제변수 $A$와 $B$가 가질 수 있는 값의 모든 경우의 수를 나타낸 것이다. 

 

명제변수는 참/거짓 $($또는 true/false 또는 1/0$)$ 둘 중 하나의 값만 가질 수 있다.

따라서 명제변수가 두개라면 가능한 경우의 수는 4가지이다. 

$($자명하게도 명제변수가 $n$개라면 가능한 경우의 수는 $2^n$개일 것이다.$)$

 

오른쪽 한 줄은 각각의 경우의 수에 대해 명제식이 갖는 값을 나타낸다.

예를 들어, $A$의 값이 0이고 $B$의 값이 0일 때 $((A \rightarrow B) \wedge \neg A)$의 값은 1이 된다.

 

 

이때, 명제변수가 가질 수 있는 각 경우의 수에 대하여 명제식은 하나의 값에 대응됨을 알 수 있다. 

우리는 여기에서 명제식 하나가 0 또는 1에 대응되도록 하는 하나의 함수를 정의할 수 있다. 

 

 

 

모델과 Valuation

 

 

위의 진리표를 다시 한번 살펴보자. 

 

Valuation	$A$	$B$	$((A \rightarrow B) \wedge \neg A)$
$v_0$	0	0	1
$v_1$	0	1	1
$v_2$	1	0	0
$v_3$	1	1	0

 

왼쪽에 한 줄이 추가되었다.

의미를 간단하게 설명하자면, 단순하게 각 명제변수의 값에 대한 경우의 수에 이름을 붙인 것이다.

$($참고로, valuation은 단순히 이름을 붙인 것이기 때문에 $v_0$과 같은 형식에는 크게 신경쓸 필요 없다. $)$

 

예를 들어 valuation $v_0$은 $A = 0, B = 0$인 경우를 말하는 것이다.

 

 

그리고, 각각의 valuation은 함수라고 생각할 수 있다. 

$v:WFF \rightarrow \left\{0,1\right\}$, 즉, 각 명제식을 명제변수의 값에 따라 0 또는 1에 대응하는 함수인 것이다. 

 

 

위의 명제식을 다시 생각해보자.

$P = ((A \rightarrow B) \wedge \neg A)$에 대하여, 4개의 valuation은 다음과 같이 나타낼 수 있다.

$v_0(P) = 1$

$v_1(P) = 1$

$v_2(P) = 0$

$v_3(P) = 0$

 

이때, 명제식의 값을 1로 만드는 valuation을 우리는 그 명제식의 모델이라고 한다.

명제식 $P$의 모델은 $v_0$과 $v_1$인 것이다. 

 

 

Valuation에 대한 이해

명제식 $P$와 $Q$를 $P = A \vee B$, $Q = A \wedge B$로 정의하자. 

두 명제에 대한 진리표를 그려보자. 

 

Valuation	$A$	$B$	$P$	$Q$
$v_0$	0	0	0	0
$v_1$	0	1	1	0
$v_2$	1	0	1	0
$v_3$	1	1	1	1

 

이때, 각 valuation에 대하여 명제식의 함숫값은 다음과 같다.

$v_0(P) = 0, v_0(Q) = 0$

$v_1(P) = 1, v_1(Q) = 0$

$v_2(P) = 1, v_2(Q) = 0$

$v_3(P) = 1, v_3(Q) = 1$

 

명제식 $P$의 모델은 $v_1$, $v_2$, $v_3$이며 명제식 $Q$의 모델은 $v_3$이다. 

 

 

이번에는 명제변수를 3개 이용하여 명제식 $R$을 $R = A \vee (B \wedge C)$로 정의하자. 

 

Valuation	$A$	$B$	$C$	$P$	$Q$	$R$
$v_0$	0	0	0	0	0	0
$v_1$	0	0	1	0	0	0
$v_2$	0	1	0	1	0	0
$v_3$	0	1	1	1	0	1
$v_4$	1	0	0	1	0	1
$v_5$	1	0	1	1	0	1
$v_6$	1	1	0	1	1	1
$v_7$	1	1	1	1	1	1

 

연습문제

 

위의 진리표에서 각 valuation에 대해 명제식 $P, Q, R$의 값을 알아보고, $P, Q, R$의 모델을 각각 구하여라. 

 

 

 

몇가지 정의

명제식 $P$에 대하여 다음 개념을 정의할 수 있다.

다음 조건들은 모두 필요충분조건이다. 

 

1. 항진명제

명제식 $P$가 항진명제라면 모든 valuation이 $P$의 모델이다.

즉, 명제식 $P$를 0으로 만드는 valuation이 존재하지 않는다.

예를 들면, $A \vee \neg A$와 같은 명제식이 있다.

 

2. 모순

명제식 $P$가 모순이라면 모든 valuation이 $P$의 모델이 아니다.

즉, 명제식 $P$를 1으로 만드는 valuation이 존재하지 않는다.

예를 들면, $B \wedge \neg B$와 같은 명제식이 있다.

 

3. 만족 가능

명제식 $P$의 모델이 존재하면 명제식  $P$는 만족 가능한 명제이다.