[계산논리] 명제논리의 문법 4. Satisfy

2019학년도 수능 국어 기출

 

 

명제식의 모델

 

이전 글에서, 우리는 모델과 valuation에 대해 알아보았다.

 

간단하게 정리하자면, valuation은 명제 변수에 특정한 논리값을 대입하는 것을 말한다.

그리고 모델은 명제식을 참으로 만드는 valuation을 말한다. 

 

 

이제, 어떤 명제식의 모델을 기호로 나타내는 방법을 알아보자.

 

명제식 $P \in WFF$와 어떤 valuation $v$에 대해 $v(P) = 1$이면, $v$는 $P$의 모델이며, 다음과 같이 나타낸다.

 

$$v \vDash P$$

 

여러의 valuation이 명제식 $P$의 모델인 경우, 집합을 이용하여 $\left\{v_1, ..., v_n\right\} \vDash P$와 같이 나타낼 수 있다.

즉, valuation의 집합 $\Gamma$에 대해 $\Gamma \vDash P$라면, $\forall v \in \Gamma . v \vDash P$인 것이다. 

 

 

두 명제식 $P, Q \in WFF$ 사이에서도 $\vDash$ 기호를 이용하여 관계를 나타낼 수 있다.

$Q \vDash P$라면, $v \vDash Q$인 모든 valuation $v$에 대해서 $v \vDash P$라는 의미이다. 

 

 

명제식의 집합 $W \in WFF$에 대해서도 $\vDash$ 기호가 정의된다.

$W \vDash P$라면, 집합 $W$의 모든 명제식 $Q \in W$에 대해 $Q \vDash P$라는 의미이다. 

 

 

마지막으로, $\vDash P$라면, 모든 valuation $v$에 대해 $v(P)=1$, 즉, $P$가 항진명제라는 것이다.

그리고 $\emptyset \vDash P$라면, $P$를 참으로 만드는 valuation이 존재하지 않는다, 즉 모순이라는 것이다. 

 

 

 

---

 

 

만족의 이해

 

실제 명제식과 진리표를 이용해서, valuation이 명제식을 만족시킨다는 것을 이해해보자.

간단하게 명제식 $P = A \vee B$라고 정의하자. 

 

이 명제식의 진리표를 그려보면 아래와 같다. 

 

Valuation	$A$	$B$	$P = A \vee B$
$v_0$	0	0	0
$v_1$	0	1	1
$v_2$	1	0	1
$v_3$	1	1	1

 

진리표를 이용해서 간단하게 명제식 $P$의 모델은 $v_1, v_2, v_3$임을 확인할 수 있다. 

이를 기호 $\vDash$를 이용하여 나타내면 아래와 같다. 

 

$$v_1 \vDash P, v_2 \vDash P, v_3 \vDash P$$

 

집합 $\Gamma$를 $\Gamma = \left\{v_1, v_2\right\}$라고 정의하자. 

그러면 아래와 같이 나타낼 수 있다.

 

$$\Gamma \vDash P$$

 

새로운 명제식 $Q = A \wedge B$라고 정의하자.

$Q$의 진리표는 아래와 같다. 

 

Valuation	$A$	$B$	$Q = A \wedge B$
$v_0$	0	0	0
$v_1$	0	1	0
$v_2$	1	0	0
$v_3$	1	1	1

 

이때, $Q$의 모델은 $v_3$밖에 없으므로, $Q$를 참으로 만드는 모든 valuation은 $P$를 참으로 만든다.

따라서 아래가 성립한다.

 

$$Q \vDash P$$

 

 

 

---

 

몇가지 정리

 

몇가지 정리를 증명해보자. 

 

1) $P \vDash P$

 

$Q \vDash P$의 정의는, $Q$을 참으로 만드는 모든 valuation이 $P$를 참으로 만든다는 것이다.

따라서, $P \vDash P$라면, $P$를 참으로 만드는 모든 valuation이 $P$를 참으로 만든다는 의미이다.

이는 자명하게 참임을 확인할 수 있다. $\blacksquare$

 

 

 

2) $\mathrm{If} \, P \vDash Q \, \mathrm{and} \, Q \vDash R \, \mathrm{then} \, P \vDash R$

 

$P \vDash Q$라면, $P$를 참으로 만드는 모든 valuation이 $Q$를 참으로 만든다는 것이다.

그리고, $Q \vDash R$라면, $Q$를 참으로 만드는 모든 valuation이 $R$을 참으로 만든다는 것이다. 

 

따라서 $P \vDash Q \, \mathrm{and} \, Q \vDash R$라면, $P$를 참으로 만드는 모든 valuation이 $Q$를 참으로 만드는데,

이때 $Q$를 참으로 만드는 모든 valuation이 $R$을 참으로 만든다.

즉, $P$를 참으로 만드는 모든 valuation은 $R$을 참으로 만든다. 

따라서 $P \vDash R$임을 알 수 있다. $\blacksquare$

 

 

 

3) $\mathrm{If} \vDash (P \rightarrow Q) \, \mathrm{then} \, P \vDash Q$

 

$\vDash (P \rightarrow Q)$라는 것은, $P \rightarrow Q$가 항진명제라는 것이다. 

따라서, 모든 valuation에 대하여 $P \rightarrow Q$가 참이라는 의미이다. 

 

이때, 명제에서 $\rightarrow$의 의미를 살펴보면 다음과 같다 :

명제식 $(P \rightarrow Q)$은 $P$가 참인 동시에 $Q$가 거짓일 때만 전체 명제가 거짓이 된다. 

 

따라서, $P \rightarrow Q$가 항진명제라면, $P$가 참인 동시에 $Q$가 거짓인 경우가 존재하지 않는다는 것이다. 

즉, 모든 valuation $v$에 대해 다음 세 가지 경우의 수 밖에 존재하지 않게 된다. 

$$v(P)=0 \,\mathrm{and}\, v(Q)=0$$

$$v(P)=1 \,\mathrm{and}\, v(Q)=1$$

$$v(P)=0 \,\mathrm{and}\, v(Q)=1$$

따라서, 어떤 valuation이 명제 $P$를 참으로 만든다면, $Q$도 참으로 만들게 됨을 확인할 수 있다.

즉, $P \vDash Q$가 된다. $\blacksquare$