논리식의 참, 거짓

원자 명제 몇 개를 이어 논리식을 만들었다면, 그 논리식 전체가 참인지 거짓인지를 판단해 볼 수 있다.

명제의 참, 거짓

먼저 명제의 진릿값이 무엇인지 분명히 해 두자. 명제 p가 있으면 그것이 참인지 거짓인지를 판단할 수 있어야 한다. 참인 명제의 진릿값은 1, 거짓인 명제의 진릿값은 0으로 정한다.

진릿값 할당은 주어진 명제에 0 또는 1을 대응시키는 규칙 e이다. e(p)라고 쓰면 명제 p의 진릿값을 알아보겠다는 뜻이다. p가 “2 곱하기 2는 4이다”라는 명제이면 참인 명제이므로 e(p) = 1이다. q가 “철수는 여자이다”라는 명제이면 철수는 여자가 아니므로 e(q) = 0이다. 즉 e는 명제가 참인지 아닌지를 알려 주는 함수이다.

여기서 주의할 점이 있다. e는 세상 모든 것을 아는 마법의 함수가 아니라, 정해 준 대로 움직이는 함수이다. 철수가 남자인지 여자인지 이 함수는 알지 못한다. 그래서 계산을 시작할 때 진릿값 할당이 어떻게 작동할지를 먼저 정해 두어야 한다. 철수가 여자라고 정해 주면 e(q) = 1을 돌려준다.

논리 연결사의 참, 거짓

논리식의 참, 거짓을 정하려면 논리 연결사의 참, 거짓을 판단하는 방법을 알아야 한다. 즉 e(p)와 e(q)를 알 때 p ∧ q, p ⇒ q 같은 논리식의 진릿값이 어떻게 되는지를 알아야 한다.

논리 연결사는 저마다 작동 방식과 쓰임이 다르므로 하나씩 살펴보자.

논리곱의 참, 거짓

논리곱은 p ∧ q로 나타내고 “p 그리고 q”라고 읽는다. 예를 들어 “대한민국은 동아시아에 있고, 그리고 수도는 서울이다”라는 논리식을 생각해 보자. 이 문장 전체는 언제 참일까?

참, 거짓을 정하는 데에는 연결사 “그리고”가 그대로 도움이 된다. 이 연결사는 왼쪽과 오른쪽의 두 명제가 모두 참이기를 요구한다. 따라서 두 명제 p와 q가 모두 참이면, 즉 e(p) = 1이고 e(q) = 1이면 논리곱 전체도 참이다. 그 밖의 경우, 즉 두 명제 가운데 하나가 거짓이거나 둘 다 거짓이면 논리식 전체가 거짓이다.

참이 아닌 논리곱의 예로 “한강은 강이고, 그리고 한강은 러시아를 흐른다”를 들 수 있다. 한강이 강인 것은 맞지만 러시아를 흐르지는 않으므로 논리곱 전체는 참이 아니다.

이를 한눈에 정리하면 다음 표와 같다.

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

앞의 두 열에는 명제 p와 q의 진릿값이 있고, 세 번째 열에는 논리식 p ∧ q의 진릿값이 있다.

논리합의 참, 거짓

논리합은 p ∨ q로 나타내고 “p 또는 q”라고 읽는다. 예: “러시아는 유럽에 있거나 또는 아시아에 있다.” 이 문장 전체는 언제 참일까?

논리합은 두 경우 가운데 적어도 하나만 참이면 된다. 연결사 “또는”은 선택지를 주는 것이므로 왼쪽이나 오른쪽 가운데 한쪽만 참이어도 충분하다. 일상 언어와 조금 다른 점은 두 명제가 모두 참일 때에도 논리적인 “또는”은 참이라는 것이다. 일상에서는 이런 경우가 드물다. 흔히 “또는”을 “…이거나 …이거나 둘 중 하나”라는 배타적인 뜻으로 쓰기 때문이다.

이와 관련된 유명한 농담이 있다. 한 가족이 중고차 매장에서 새 차를 고르고 있었다. 아빠가 판매원에게 “파란 차나 빨간 차를 사기로 했어요”라고 말했다. 판매원은 두 차를 모두 팔았다. 논리적인 “또는”과 일상의 “또는”의 차이를 잘 보여 주는 이야기이다. 아빠는 아마 두 차 가운데 하나만 고르겠다는 뜻이었겠지만, 판매원은 두 대를 다 파는 것도 올바른 선택지라고 여긴 것이다.

앞의 러시아 문장은 두 명제가 모두 참이므로 참이다. “7은 3으로 나누어떨어지거나 또는 7은 소수이다”라는 문장은 7이 소수이므로 참이다. 7이 3으로 나누어떨어지지 않는다는 것은 상관이 없다. 진리표는 다음과 같다.

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

조건문의 참, 거짓

조건문은 p ⇒ q로 나타내고 “p이면 q이다”라고 읽는다. 예를 들어 “술을 많이 마시면 토한다”라는 문장은 조건문이다. 이 문장은 언제 참일까?

논리적인 조건문은 모든 연결사 가운데 가장 헷갈리기 쉽다. 일상 언어에서도 잘못 이해되어 동치와 혼동되는 일이 많다. 역 q ⇒ p도 함께 성립하는지 생각해 보자.

술을 많이 마시면 토한다는 것은 알고 있다. 그러면 토했을 때에는 반드시 술을 많이 마신 것일까? 결코 그렇지 않다. 상한 음식을 먹었을 수도 있고, 전혀 다른 이유로 속이 안 좋을 수도 있다. 따라서 역이 저절로 성립하지는 않는다. p ⇒ q와 q ⇒ p가 모두 성립하면 동치가 되는데, 이는 뒤에서 다룬다.

다른 예를 보자. “내일 비가 오면 민준이는 우산을 챙긴다.” 그런데 민준이가 우산을 챙겼다고 하자. 그날 비가 왔을까? 많은 사람이 당연히 왔다고 답하고 싶어 한다. 비가 오면 민준이가 우산을 챙긴다고 했으니까. 그러나 원래 문장은 그런 뜻이 아니다!

민준이는 알 수 없는 전혀 다른 이유로 우산을 챙겼을 수도 있다. 할머니 댁에 갈 때는 늘 우산을 챙기는 습관이 있을지도 모른다. 새 우산을 사기로 하고 낡은 우산을 버리러 가는 길이었을 수도 있다. 이런 것은 모두 비가 오지 않았는데도 민준이가 우산을 챙길 수 있는 정당한 이유이다.

이제 조건문이 언제 참인지 답할 수 있다. 두 명제가 모두 참이면 조건문은 당연히 참이다. “42가 자연수이면 양수이다”에서는 두 명제가 모두 참이므로 조건문 전체가 참이다. 한편 “42가 자연수이면 음수이다”라는 조건문은 참이 아니다. 참인 것에서 참이 아닌 것을 이끌어 내려고 했기 때문이다.

마지막으로 첫 번째 명제가 거짓인 경우가 남는다. 이때는 두 번째 명제의 참, 거짓은 더 이상 상관이 없다. 거짓에서 출발하면 그 뒤에는 무슨 말을 해도 된다. “1이 음수이면 나는 웃음의 신이다”나 “펭귄이 하늘을 난다면 태양은 파랗다” 같은 문장이 그렇다. 이런 경우 조건문은 거짓에서 출발하므로 자동으로 참이다. 진리표는 다음과 같다.

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

동치의 참, 거짓

동치는 p ⇔ q로 쓰고 “p일 때 그리고 그때에만 q”라고 읽는다. 예를 들어 “수 x는 짝수일 때 그리고 그때에만 2로 나누어떨어진다”는 동치이다. 이 문장 전체는 언제 참일까?

동치에서는 두 명제가 한 몸처럼 움직여서 둘 다 성립하거나 둘 다 성립하지 않기를 기대한다. 따라서 수 x는 짝수이면서 2로 나누어떨어지거나, 둘 중 어느 것도 아니어야 한다. x가 짝수인데 2로 나누어떨어지지 않는 경우는 있을 수 없다.

예: “도윤이는 화장실에 앉아 있을 때 그리고 그때에만 책을 읽는다.” 이 동치가 성립하려면 도윤이는 화장실에 앉아 있을 때마다 반드시 책을 읽어야 한다. 또 책을 읽을 때마다 반드시 화장실에 앉아 있어야 한다. 예를 들어 침대에서 책을 읽는 일은 있을 수 없다.

동치는 두 조건문으로 나타낼 수 있다. 즉 p ⇔ q는 “p ⇒ q 그리고 q ⇒ p”로 바꿔 쓸 수 있다. 진리표는 다음과 같다.

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

부정

부정은 단항 연산으로, 프라임을 붙여 p'으로 쓰거나 기호 ¬p로 쓴다. 부정은 원래 주장을 부정한다. “영희는 가수이다”라는 명제를 부정하면 “영희가 가수인 것은 아니다”, 줄여서 “영희는 가수가 아니다”라는 명제를 얻는다. 거의 모든 경우 명제 앞에 “…인 것은 아니다”를 붙이면 부정을 만들 수 있다.

부정은 진릿값을 뒤집는다. 즉 0을 1로, 1을 0으로 바꾼다. 따라서 ¬0 = 1, ¬1 = 0이라고 쓸 수 있다.

헷갈리기 쉬운 경우를 조심해야 한다. “석회는 하얗다”라는 주장이 있다고 하자. 부정은 무엇일까? “석회는 까맣다”라고 생각할 수도 있지만 그렇지 않다! 앞의 방법을 쓰면 부정은 “석회가 하얀 것은 아니다”이다. 그렇다고 해서 반드시 까매야 할까? 그렇지 않다. 예를 들어 분홍색일 수도 있다.

모든 연결사의 진리표

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

논리식 전체의 참, 거짓

이제 논리 연결사로 이어진 두 명제의 참, 거짓을 판단할 수 있다. 논리식 전체도 같은 방식으로 판단한다. 예를 들어 논리식 (p ⇒ q) ∧ r에서 (p ⇒ q)의 진릿값이 1로 나왔다면, 이미 풀 줄 아는 보통의 논리곱 1 ∧ r을 얻는다.

가장 단순한 논리 연결사를 차례로 적용하면 논리식 전체의 진릿값에 이른다. 이때 흔히 진리표를 이용한 방법을 쓰는데, 아래에서 설명한다.

진리표를 이용한 방법

진리표를 이용한 방법은 복잡한 논리식의 참, 거짓을 판단할 때 쓴다. 처음 n개의 열에는 논리식에 쓰인 n개의 명제 변수를 적고, 그다음 열에는 논리식을 이루는 부분 논리식을 차례로 적는다. 예를 보면 쉽게 이해할 수 있다.

논리식 (p ∨ q) ∧ (q ⇒ p)를 생각하자. 먼저 표에 모든 명제 변수, 즉 p와 q를 적고 진릿값의 모든 조합을 적는다.

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

다음으로 부분 논리식 p ∨ q와 q ⇒ p의 열을 덧붙인다.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

이제 이 논리식의 값을 구해 열에 0이나 1을 채운다. 필요한 정보는 모두 표에 있다. 첫 번째 행에서 p ∨ q의 값을 구할 때는 p에 1, q에도 1을 대입한다. 그러면 1 ∨ 1을 얻는다. 이 값은 1이므로 표에 1을 적는다.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

이런 식으로 표 전체를 채운다.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

이제 논리식 전체의 값을 구하는 일이 남았다. 이 논리식을 φ = (p ∨ q) ∧ (q ⇒ p)라고 하자. 표에 φ의 열을 덧붙이고 값을 구하는데, 이때는 앞의 두 열을 이용한다.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

이제 표가 완성되었고, 가능한 모든 진릿값 할당에서 논리식의 진릿값을 알 수 있다. 예를 들어 e(p) = 1이고 e(q) = 1이면 논리식은 참이다. e(p) = 0이고 e(q) = 1이면 논리식은 참이 아니다.

“논리식은 참이다”라고만 말할 수는 없다는 점에 주의하자. 논리식이 참이라고 말하려면 어떤 진릿값 할당에서 참인지를 밝혀야 하므로, 이 문장만으로는 뜻이 통하지 않는다. 따라서 “논리식 φ는 할당 e₁에서 참이고 할당 e₂에서는 참이 아니다”처럼 말해야 한다.

논리식이 참이라고 말할 수 있는 경우는 가능한 모든 할당에서 참일 때뿐이다. 예를 들어 논리식 p ∨ ¬p는 모든 할당에서 참이므로 이 논리식은 참이라고 말할 수 있다. 모든 할당에서 거짓인 논리식도 마찬가지이다.

이런 논리식에는 따로 이름이 있다. 모든 할당에서 참인 논리식을 항진명제(토톨로지)라고 한다. 어떤 할당에서도 참이 되지 않는 논리식을 모순명제라고 한다.