명제(proposition)는 참인지 거짓인지를 명확하게 판별할 수 있는 문장이나 식이다. 참/거짓을 명제의 진리값이라 한다.
수학이 다루는 문장은 "옳다/그르다"가 객관적으로 정해지는 것뿐이다. "$3$은 소수다"는 명제(참)이고, "$1+1=3$"도 명제(거짓)다. 그러나 "수학은 아름답다"는 사람마다 판단이 달라 명제가 아니다. 집합의 원소 판별 기준이 애매하면 안 되는 것과 같은 정신이다 — 실제로 조건 $p(x)$를 만족하는 $x$의 모임이 집합(진리집합)이 된다.
조건문 $p \rightarrow q$에 대해:
| 이름 | 형태 | 원명제와의 관계 |
|---|---|---|
| 역 | $q \rightarrow p$ | 진리값이 다를 수 있음 |
| 이 | $\sim p \rightarrow \sim q$ | 진리값이 다를 수 있음 |
| 대우 | $\sim q \rightarrow \sim p$ | 항상 진리값이 같음 |
대우의 동치성은 증명 기법의 뿌리다: $p \rightarrow q$를 직접 보이기 어려우면 $\sim q \rightarrow \sim p$를 보이면 된다(대우 증명법). 결론을 부정해 모순을 끌어내는 귀류법도 여기서 나온다.
위 표에서 대우만 "항상 진리값이 같음"인 이유는 외울 것이 아니라 한 가지 관찰에서 곧바로 따라온다. 출발점은 조건문이 거짓이 되는 경우는 딱 하나라는 사실이다.
① 조건문은 언제 거짓인가. "비가 오면 땅이 젖는다"는 약속을 어긴 상황은 하나뿐이다 — 비가 왔는데(가정 참) 땅이 젖지 않은(결론 거짓) 경우. 비가 오지 않은 날에는 땅이 젖었든 말랐든 이 약속을 어긴 것이 아니다. 그래서
$$p \rightarrow q \text{ 가 거짓} \iff p \text{ 는 참},\ q \text{ 는 거짓}$$
② 대우가 거짓이 되는 경우를 같은 방법으로 적는다. $\sim q \rightarrow \sim p$의 가정은 $\sim q$, 결론은 $\sim p$이므로 ①을 그대로 적용하면 "$\sim q$가 참이고 $\sim p$가 거짓"일 때 거짓이다. 부정을 풀면 "$q$가 거짓이고 $p$가 참" — ①과 글자만 다른 같은 조건이다.
③ 그래서 동치다. 두 문장이 거짓이 되는 상황이 완전히 같으므로, 어떤 경우에도 진리값이 갈라질 수 없다. 이것이 대우 증명법의 근거다 — 증명하고 싶은 것과 증명하는 것이 같은 문장이기 때문에 허용된다.
④ 역은 왜 다른가. $q \rightarrow p$가 거짓인 경우는 ①을 적용하면 "$q$가 참, $p$가 거짓"이다. ①과 가정·결론의 자리가 서로 바뀌어 있으므로 조건이 다르고, 따라서 원명제가 참이어도 역은 참일 수도 거짓일 수도 있다. 이($\sim p \rightarrow \sim q$)는 역의 대우이므로 역과 진리값이 같고, 역시 원명제와는 무관하다.
⑤ 집합으로 옮기면 그림이 된다. 조건 $p$, $q$의 진리집합을 $P$, $Q$라 하면 ①은 "$P$에 들면서 $Q$에 들지 않는 원소가 없다"는 말이므로
$$p \Rightarrow q \iff P \subset Q$$
가 된다. 이 그림에서 필요·충분이라는 이름도 그대로 읽힌다 — $P$에 들기만 하면 $Q$에 드는 것이 보장되니 $p$는 충분하고, $Q$ 밖으로 나가면 $P$에도 있을 수 없으니 $q$는 필요하다. 대우 $\sim q \Rightarrow \sim p$는 $Q^c \subset P^c$인데, 벤 다이어그램에서 이것은 $P \subset Q$와 같은 그림이다.
⑥ 귀류법도 여기서 나온다. ①에 따르면 $p \rightarrow q$의 반례는 "$p$이고 $\sim q$"인 상황 하나뿐이다. 그러므로 그 상황을 가정해 모순을 끌어내면 반례가 존재할 수 없다는 뜻이 되어 증명이 끝난다.
명제 단원에서 학생들이 특히 자주 걸리는 두 지점이 있다. 첫째는 필요조건과 충분조건의 방향이다. $p \Rightarrow q$에서 화살표가 나가는 $p$가 충분조건, 들어오는 $q$가 필요조건이다. "비가 왔다 $\Rightarrow$ 땅이 젖었다"로 보자. 비가 왔다는 사실 하나만 있으면 땅이 젖었다고 결론짓기에 충분하다(그래서 $p$가 충분조건). 한편 비가 왔다면 땅은 반드시 젖어 있으니, $p$가 참이기 위해 $q$는 꼭 갖춰져야 하는 조건이다(그래서 $q$가 필요조건). 방향을 억지로 외우기보다 "이것만으로 충분한가? 이게 없으면 안 되나?"라고 말로 풀어 보면 헷갈림이 줄어든다.
둘째는 왜 대우만 원명제와 진리값이 항상 같은가다. "비가 오면 땅이 젖는다"가 참이어도, 뒤집은 역 "땅이 젖으면 비가 왔다"는 거짓일 수 있다 — 누가 물을 뿌렸을 수도 있으니까. 그런데 대우 "땅이 안 젖었으면 비가 안 왔다"는 원래 문장과 완전히 같은 말이다: 비가 왔는데 땅이 안 젖는 일은 없으니, 땅이 말라 있다면 비는 오지 않은 게 확실하다. 그래서 원명제를 직접 보이기 어려울 때 대우를 대신 증명해도 되는 것이다. "거꾸로 뒤집기(역)"와 "부정해서 뒤집기(대우)"는 전혀 다르다는 점만 확실히 잡아두자.
"$n^2$이 짝수이면 $n$은 짝수다"를 직접 증명하기는 번거롭지만, 대우 "$n$이 홀수이면 $n^2$은 홀수다"는 $n = 2k+1$을 대입해 바로 확인된다:
$$(2k+1)^2 = 4k^2 + 4k + 1 = 2(2k^2 + 2k) + 1$$
추론의 형식을 내용과 떼어 내 다룬 첫 시도는 아리스토텔레스의 삼단논법이다(기원전 4세기). "모든 사람은 죽는다, 소크라테스는 사람이다, 그러므로 소크라테스는 죽는다"에서 중요한 것은 사람이나 소크라테스가 아니라 틀이라는 발견이었고, 이 틀은 이후 2천 년 동안 논리학의 표준으로 남았다. 다만 그때의 논리는 어디까지나 자연어 문장의 형식이었다.
논리를 계산으로 바꾸자는 생각은 라이프니츠의 구상으로 남아 있었고, 실제로 해낸 사람은 조지 불이다. 그는 1847년과 1854년의 저작에서 참을 $1$, 거짓을 $0$으로 놓고 '그리고·또는·아니다'를 곱셈·덧셈처럼 다루는 대수를 세웠다(오늘의 부울 대수). 같은 시기 오거스터스 드모르간이 부정이 분배되는 법칙을 정리했고, 이것이 이 문서의 부정·합성 규칙으로 이어진다. 이어 고틀로프 프레게가 1879년 '모든'과 '어떤'을 다루는 기호(양화사)를 도입해 수학의 명제를 온전히 형식화했다.
이 흐름의 예상치 못한 결말은 기계였다. 1937년 클로드 섀넌이 석사논문에서 불의 대수가 전기 스위치의 켜짐·꺼짐과 정확히 대응한다는 것을 보였고, 그래서 오늘의 컴퓨터는 명제 논리를 회로로 구현한 장치다. 학교에서 배우는 $\sim p$, "$p$이고 $q$"가 프로그래밍 언어의 !, &&와 같은 것인 이유가 여기에 있다.