명제 논리 예제

이 글에서는 몇 가지 논리식과 그 진릿값 할당을 진리표를 이용한 방법으로 살펴본다.

첫 번째 예제

다음 논리식이 언제 참인지 알아보자: ϕ = (p ∧ q) ∨ ¬q. 먼저 표에 명제 변수 p와 q를 적는다.

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

다음으로 논리식의 첫 부분 (p ∧ q), 부정 ¬q, 그리고 논리식 전체를 표에 덧붙인다.

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

이제 세 번째 열의 값을 구한다. 세 번째 열은 단순한 논리곱이다. 부정의 값도 함께 구하는데, 두 번째 열의 값을 뒤집어 적기만 하면 된다.

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 0& 0\\ 0& 0& 0& 1\end{array}$$

마지막으로 맨 끝 열의 값을 구한다. 이 열이 논리식 전체이다. 이 표에서는 “세 번째 열과 네 번째 열의” 논리합을 계산하는 셈이다. 결과는 다음과 같다.

$$\begin{array}{ccccc}p& q& p\wedge q& \mathrm{\neg }q& \varphi \\ 1& 1& 1& 0& 1\\ 1& 0& 0& 1& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 1& 1\end{array}$$

두 번째 예제

같은 문제를 다른 논리식으로 풀어 보자: ϕ = (p ∧ ¬q) ⇔ (¬p ⇒ q). 이 논리식에는 명제 변수 p, q와 그 부정이 있다. 그래서 먼저 두 변수와 그 부정으로 표를 만든다.

$$\begin{array}{cccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q\\ 1& 1& 0& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 0\\ 0& 0& 1& 1\end{array}$$

다음으로 논리식 p ∧ ¬q와 ¬p ⇒ q를 덧붙인다. 표에 각 명제와 그 부정의 진릿값이 모두 있으므로 값을 쉽게 구할 수 있다. 표는 다음과 같다.

$$\begin{array}{cccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)\\ 1& 1& 0& 0& 0& 1\\ 1& 0& 0& 1& 1& 1\\ 0& 1& 1& 0& 0& 1\\ 0& 0& 1& 1& 0& 0\end{array}$$

마지막으로 논리식 전체의 값을 구한다. 논리식 전체는 마지막 두 열의 동치이다.

$$\begin{array}{ccccccc}p& q& \mathrm{\neg }p& \mathrm{\neg }q& (p\wedge \mathrm{\neg }q)& (\mathrm{\neg }p\Rightarrow q)& \varphi \\ 1& 1& 0& 0& 0& 1& 0\\ 1& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 0& 0& 1& 0\\ 0& 0& 1& 1& 0& 0& 1\end{array}$$

세 번째 예제

세 번째 예제는 조금 더 복잡하다. 명제 변수가 세 개라서 표를 계산하기가 더 번거롭다. 논리식은 다음과 같다: ϕ = (¬(p ⇒ q)) ∧ (r ⇔ (¬p ∨ q)).

명제 변수가 세 개이므로 가능한 진릿값 할당은 모두 8가지이다.

$$\begin{array}{ccc}p& q& r\\ 1& 1& 1\\ 1& 1& 0\\ 1& 0& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\\ 0& 0& 0\end{array}$$

그다음은 앞의 예제와 같은 방법으로, 각 열의 값을 8개의 행 모두에서 구한다. 완성된 표는 다음과 같다.

$$\begin{array}{ccccccccc}p& q& r& \mathrm{\neg }p& (p\Rightarrow q)& (\mathrm{\neg }p\vee q)& \mathrm{\neg }(p\Rightarrow q)& (r\iff (\mathrm{\neg }p\vee q))& \varphi \\ 1& 1& 1& 0& 1& 1& 0& 1& 0\\ 1& 1& 0& 0& 1& 1& 0& 0& 0\\ 1& 0& 1& 0& 0& 0& 1& 0& 0\\ 1& 0& 0& 0& 0& 0& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 0& 1& 0\\ 0& 1& 0& 1& 1& 1& 0& 0& 0\\ 0& 0& 1& 1& 1& 1& 0& 1& 0\\ 0& 0& 0& 1& 1& 1& 0& 0& 0\end{array}$$

네 번째 예제

이번에는 논리식을 그냥 주지 않고 문장제로 낸다. 세 친구가 신나는 파티에 가려고 한다. 그런데 셋은 서로 그다지 사이가 좋지 않아서, 파티에 갈 조건을 서로 내걸었다. 세 사람의 이름은 민준, 지호, 푸름이다. 규칙은 다음과 같다.

1. 민준이가 가면 지호도 간다.
2. 푸름이가 파티에 오거나, 또는 민준이가 오면 지호는 오지 않는다.
3. 푸름이는 민준이가 오지 않거나 지호가 오지 않을 때 그리고 그때에만 온다.

세 사람이 모두 파티에 올 수 있을까? 올 수 없다면, 어떤 규칙도 어기지 않고 파티에 갈 수 있는 사람은 누구일까?

먼저 위의 문장을 명제 변수와 논리식으로 바꿔 써야 한다. 명제 변수를 M, J, P(민준, 지호, 푸름의 로마자 머리글자)라고 하자. 각 기호는 “민준이가 파티에 간다” 같은 명제를 나타낸다. 첫 번째 규칙은 M ⇒ J, 즉 “M이면 J”, 다시 말해 “민준이가 파티에 가면 지호도 파티에 간다”로 쓸 수 있다.

두 번째 규칙은 다음과 같이 바꿔 쓴다. 규칙은 “푸름이가 파티에 오거나…”로 시작하므로 논리합이 필요하다는 것을 알 수 있다. 우선 P ∨ …라고 적어 두자. 문장의 나머지 부분은 “민준이가 오면 지호는 오지 않는다”이다. 이 부분은 조건문이고, 오른쪽에는 부정을 써야 한다. “지호는 오지 않는다”는 ¬J이다. 조건문 전체는 M ⇒ ¬J가 된다. 이것을 앞의 논리합에 이으면 P ∨ (M ⇒ ¬J)이다.

세 번째 규칙은 다음과 같이 바꿔 쓴다. “푸름이는 … 때 그리고 그때에만 온다”는 동치를 뜻한다: P ⇔ … 그다음은 “민준이가 오지 않거나 지호가 오지 않는다”이고, 이는 ¬M ∨ ¬J로 쓴다. 합치면 (P ⇔ (¬M ∨ ¬J))이다.

이제 모든 논리식을 표에 넣고 값을 구한다.

$$\begin{array}{cccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))\\ 1& 1& 1& 1& 1& 0\\ 1& 1& 0& 1& 0& 1\\ 1& 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 1& 0\\ 0& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0\end{array}$$

물음은 세 친구가 모두 신나는 파티에 갈 수 있느냐였다. 답은 첫 번째 행에 있다. 첫 번째 행은 세 사람이 모두 가는 경우로, 앞의 세 열이 모두 1이다. 조건은 모두 만족될까? 첫 번째 조건은 만족되고(네 번째 열), 두 번째 조건도 만족되지만(다섯 번째 열), 마지막 조건은 만족되지 않는다(마지막 열이 0이다). 즉 세 사람이 모두 가면 세 번째 조건이 만족되지 않는다.

따라서 조건을 나타내는 자리(마지막 세 열)가 모두 1인 행을 찾으면 된다. 1은 조건이 만족된다는 뜻이다. 그런 행은 두 개이다. 지호와 푸름이는 가고 민준이는 가지 않는 경우, 그리고 푸름이만 가는 경우이다.

표에 세 조건의 논리곱인 논리식 ϕ를 덧붙여 구할 수도 있다. 이 논리식은 ϕ = ((M ⇒ J) ∧ (P ∨ (M ⇒ ¬J)) ∧ (P ⇔ (¬M ∨ ¬J)))이다. 이 식은 모든 논리식(모든 조건)이 만족되어야 한다는 요구를 그대로 나타낸다. 표는 다음과 같다.

$$\begin{array}{ccccccc}M& J& P& (M\Rightarrow J)& (P\vee (M\Rightarrow \mathrm{\neg }J))& (P\iff (\mathrm{\neg }M\vee \mathrm{\neg }J))& \varphi \\ 1& 1& 1& 1& 1& 0& 0\\ 1& 1& 0& 1& 0& 1& 0\\ 1& 0& 1& 0& 1& 1& 0\\ 1& 0& 0& 0& 1& 0& 0\\ 0& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 1& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$

진리표를 이용한 방법의 예제 몇 가지

주어진 논리식에서 진리표 전체를 자동으로 만들어 주는 프로그램을 작성해 두었으니, 이를 활용해 풀어 본 논리식 몇 개를 더 소개한다.

논리식: ((a ∧ ¬b) ∨ (b ∧ (b ⇒ a))). 진리표:

$$\begin{array}{ccccc}a& b& (a\wedge \mathrm{\neg }b)& (b\wedge (b\Rightarrow a))& ((a\wedge \mathrm{\neg }b)\vee (b\wedge (b\Rightarrow a)))\\ 1& 1& 0& 1& 1\\ 1& 0& 1& 0& 1\\ 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0\end{array}$$

논리식: (a ∨ ¬a) ⇔ (b ∧ ¬b). 진리표:

$$\begin{array}{ccccc}a& b& (a\vee \mathrm{\neg }a)& (b\wedge \mathrm{\neg }b)& ((a\vee \mathrm{\neg }a)\iff (b\wedge \mathrm{\neg }b))\\ 1& 1& 1& 0& 0\\ 1& 0& 1& 0& 0\\ 0& 1& 1& 0& 0\\ 0& 0& 1& 0& 0\end{array}$$

논리식: ¬(a ∨ b) ⇔ (¬b ∧ ¬a). 진리표:

$$\begin{array}{ccccc}a& b& \mathrm{\neg }(a\vee b)& (\mathrm{\neg }b\wedge \mathrm{\neg }a)& (\mathrm{\neg }(a\vee b)\iff (\mathrm{\neg }b\wedge \mathrm{\neg }a))\\ 1& 1& 0& 0& 1\\ 1& 0& 0& 0& 1\\ 0& 1& 0& 0& 1\\ 0& 0& 1& 1& 1\end{array}$$

논리식: ϕ = (¬p ⇔ (q ∧ r)) ⇒ (p ∨ ¬(p ∧ q)). 진리표:

$$\begin{array}{cccccccc}p& q& r& (q\wedge r)& \mathrm{\neg }(p\wedge q)& (\mathrm{\neg }p\iff (q\wedge r))& (p\vee \mathrm{\neg }(p\wedge q))& \varphi \\ 1& 1& 1& 1& 0& 0& 1& 1\\ 1& 1& 0& 0& 0& 1& 1& 1\\ 1& 0& 1& 0& 1& 1& 1& 1\\ 1& 0& 0& 0& 1& 1& 1& 1\\ 0& 1& 1& 1& 1& 1& 1& 1\\ 0& 1& 0& 0& 1& 0& 1& 1\\ 0& 0& 1& 0& 1& 0& 1& 1\\ 0& 0& 0& 0& 1& 0& 1& 1\end{array}$$

논리식: ϕ = ¬(p ⇔ ¬q) ∧ (r ⇒ ¬p) ∧ (p ∨ r). 진리표:

$$\begin{array}{ccccccc}p& q& r& \mathrm{\neg }(p\iff \mathrm{\neg }q)& (r\Rightarrow \mathrm{\neg }p)& (p\vee r)& \varphi \\ 1& 1& 1& 1& 0& 1& 0\\ 1& 1& 0& 1& 1& 1& 1\\ 1& 0& 1& 0& 0& 1& 0\\ 1& 0& 0& 0& 1& 1& 0\\ 0& 1& 1& 0& 1& 1& 0\\ 0& 1& 0& 0& 1& 0& 0\\ 0& 0& 1& 1& 1& 1& 1\\ 0& 0& 0& 1& 1& 0& 0\end{array}$$