명제논리
명제, 논리 연산, 진리표, 동치
개요 — 동기·문제의식
수학의 모든 증명은 문장들을 규칙에 따라 이어붙인 것이다. 그런데 일상 언어는 이 목적에 쓰기에 너무 모호하다 — "밥 또는 빵을 먹겠다"의 "또는"은 둘 다를 허용하는가, "성적이 오르면 선물을 주겠다"는 성적이 오르지 않았을 때 무엇을 약속하는가. 명제논리(propositional logic)는 문장을 참·거짓만 갖는 단위로 추상화하고, 문장을 결합하는 연결사들의 의미를 진리값의 함수로 완전히 고정함으로써 이 모호함을 제거한다. 그 대가로 얻는 것이 크다: 어떤 추론이 옳은지가 취향이 아니라 계산의 문제가 된다.
이 장은 명제를 더 쪼개지 않는 원자로 취급한다. "$x+1=2$"처럼 변수를 품은 문장의 내부 구조와 "모든", "어떤" 같은 한정사는 술어와 한정기호에서 다루고, 여기서 확립한 동치 법칙과 타당한 논증 형식이 실제 증명 전략으로 번역되는 과정은 증명 기법에서 다룬다.
직관
명제변수가 $n$개면 가능한 진리값 배정은 $2^n$가지뿐이다. 그러므로 합성명제의 의미는 유한한 표 하나 — 진리표 — 로 완전히 결정되고, 두 명제가 "논리적으로 같다"는 주장도 표의 두 열을 비교하는 유한한 검산으로 판정된다. 명제논리의 모든 정리가 원리적으로 기계적 확인만으로 증명되는 이유가 이것이다.
연결사는 스위치 회로로 그려볼 수 있다. $\land$는 직렬연결(둘 다 켜져야 통전), $\lor$는 병렬연결(하나만 켜져도 통전), $\neg$는 반전 스위치다. 함의 $p\to q$는 회로보다 계약으로 읽는 편이 낫다: "p가 성립하면 q를 보장한다"는 계약은 p가 성립했는데 q가 깨졌을 때에만 위반이다. p가 애초에 성립하지 않았다면 계약은 위반되지 않았고, 따라서 참이다.
정의
명제
정의. 참($\mathrm{T}$) 또는 거짓($\mathrm{F}$) 중 정확히 하나의 진리값(truth value)을 갖는 평서문을 명제(proposition)라 한다. 명제를 나타내는 문자 $p,q,r,\dots$를 명제변수라 하고, 연결사로 결합해 만든 명제를 합성명제(compound proposition)라 한다.
논리 연산 (연결사)
정의. 여섯 연결사의 진리값은 다음 표로 정의된다. 부정 $\neg p$, 논리곱 $p\land q$, 논리합 $p\lor q$(포함적), 배타적 논리합 $p\oplus q$(정확히 하나가 참), 함의 $p\to q$, 상호함의 $p\leftrightarrow q$.
| $p$ | $q$ | $\neg p$ | $p\land q$ | $p\lor q$ | $p\oplus q$ | $p\to q$ | $p\leftrightarrow q$ |
|---|---|---|---|---|---|---|---|
| T | T | F | T | T | F | T | T |
| T | F | F | F | T | T | F | F |
| F | T | T | F | T | T | T | F |
| F | F | T | F | F | F | T | T |
$p\to q$에서 $p$를 전건(hypothesis), $q$를 후건(conclusion)이라 한다. $p\to q$는 전건이 참인데 후건이 거짓인 단 한 경우에만 거짓이다. $q\to p$를 역(converse), $\neg p\to\neg q$를 이(inverse), $\neg q\to\neg p$를 대우(contrapositive)라 한다.
항진명제와 모순명제
정의. 모든 진리값 배정에서 참인 합성명제를 항진명제(tautology), 모든 배정에서 거짓인 것을 모순명제(contradiction), 둘 다 아닌 것을 불확정명제(contingency)라 한다. 예: $p\lor\neg p$는 항진, $p\land\neg p$는 모순.
논리적 동치
정의. $p\leftrightarrow q$가 항진명제일 때 $p$와 $q$는 논리적으로 동치(logically equivalent)라 하고 $p\equiv q$로 쓴다. 이는 두 명제의 진리표 열이 완전히 일치한다는 것과 같다. $\equiv$는 연결사가 아니라 두 명제 사이의 관계(메타언어의 기호)임에 주의한다.
논증과 타당성
정의. 전제 $p_1,\dots,p_n$과 결론 $q$로 이루어진 논증(argument)이 타당(valid) $\iff$ $(p_1\land\cdots\land p_n)\to q$가 항진명제, 즉 전제가 모두 참인 모든 배정에서 결론도 참이다. 타당성은 논증의 형식의 성질이며, 전제가 실제로 참인지와는 무관하다.
주요 정리
정리 1 (이중부정·드모르간 법칙). $\neg\neg p\equiv p$, $\neg(p\land q)\equiv\neg p\lor\neg q$, $\neg(p\lor q)\equiv\neg p\land\neg q$.
증명 보기
증명. 이중부정은 두 행 확인으로 끝난다. 둘째 동치는 아래 표에서 마지막 두 열이 일치하므로 성립하고, 셋째도 같은 방식이다.
| $p$ | $q$ | $\neg(p\land q)$ | $\neg p\lor\neg q$ |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | T | T |
| F | F | T | T |
$\blacksquare$
정리 2 (분배법칙). $p\land(q\lor r)\equiv(p\land q)\lor(p\land r)$, $p\lor(q\land r)\equiv(p\lor q)\land(p\lor r)$.
증명 보기
증명 스케치. 8행 진리표 대신 $p$의 값으로 경우를 나눈다. 첫째 법칙: $p=\mathrm{F}$이면 양변 모두 $\mathrm{F}$; $p=\mathrm{T}$이면 좌변은 $q\lor r$, 우변도 $q\lor r$로 일치. 둘째 법칙: $p=\mathrm{T}$이면 양변 모두 $\mathrm{T}$; $p=\mathrm{F}$이면 양변 모두 $q\land r$. 모든 배정에서 일치하므로 동치이다. $\blacksquare$
정리 3 (함의의 동치). $p\to q\equiv\neg p\lor q$.
증명 보기
증명. 두 명제가 거짓이 되는 배정을 비교한다. $p\to q$가 거짓 $\iff$ $p=\mathrm{T}$이고 $q=\mathrm{F}$. $\neg p\lor q$가 거짓 $\iff$ $\neg p=\mathrm{F}$이고 $q=\mathrm{F}$ $\iff$ $p=\mathrm{T}$이고 $q=\mathrm{F}$. 거짓이 되는 배정이 정확히 같으므로 참이 되는 배정도 같고, 따라서 동치이다. $\blacksquare$
정리 4 (대우 법칙). $p\to q\equiv\neg q\to\neg p$. 반면 역 $q\to p$와 이 $\neg p\to\neg q$는 $p\to q$와 동치가 아니다.
증명 보기
증명. 정리 3을 두 번 쓰면 $\neg q\to\neg p\equiv\neg\neg q\lor\neg p\equiv q\lor\neg p\equiv\neg p\lor q\equiv p\to q$ (이중부정과 $\lor$의 교환법칙). 비동치는 반례 배정 하나로 충분하다: $p=\mathrm{F},q=\mathrm{T}$에서 $p\to q=\mathrm{T}$이지만 $q\to p=\mathrm{F}$이고 $\neg p\to\neg q=\mathrm{F}$. $\blacksquare$
정리 5 (modus ponens·modus tollens). $((p\to q)\land p)\to q$와 $((p\to q)\land\neg q)\to\neg p$는 항진명제이다.
증명 보기
증명. Modus ponens: 어떤 배정에서 거짓이라 가정하면 $(p\to q)\land p=\mathrm{T}$이고 $q=\mathrm{F}$. 그런데 $p=\mathrm{T}$이고 $q=\mathrm{F}$이면 $p\to q=\mathrm{F}$가 되어 모순. 그러므로 거짓이 되는 배정이 없다. Modus tollens: 정리 4에 의해 $p\to q\equiv\neg q\to\neg p$이므로, 전제 $\neg q$에 modus ponens를 적용한 것과 같다. $\blacksquare$
정리 6 (가언 삼단논법). $((p\to q)\land(q\to r))\to(p\to r)$는 항진명제이다.
증명 보기
증명. 어떤 배정에서 거짓이라 가정하면 $p\to q=\mathrm{T}$, $q\to r=\mathrm{T}$, $p\to r=\mathrm{F}$이다. 마지막에서 $p=\mathrm{T}$, $r=\mathrm{F}$. $p=\mathrm{T}$와 $p\to q=\mathrm{T}$에서 $q=\mathrm{T}$; $q=\mathrm{T}$와 $q\to r=\mathrm{T}$에서 $r=\mathrm{T}$, 이는 $r=\mathrm{F}$와 모순. $\blacksquare$
예제
예제 1 (명제 판별). "17은 소수이다"는 참인 명제, "서울은 일본의 수도이다"는 거짓인 명제다. "$x+1=2$"는 $x$의 값에 따라 진리값이 달라지므로 명제가 아니라 술어이고(술어와 한정기호), "문을 닫아라"는 평서문이 아니므로 명제가 아니다. "이 문장은 거짓이다"는 어느 진리값을 배정해도 모순이 생기므로 명제가 아니다.
예제 2 (진리표 작성). $(p\lor\neg q)\to(p\land q)$의 진리표를 만들면 배정 $(\mathrm{T},\mathrm{T})$에서만 참이고 나머지 세 배정에서 거짓이다. 예컨대 $(\mathrm{F},\mathrm{F})$에서는 전건 $p\lor\neg q=\mathrm{T}$, 후건 $p\land q=\mathrm{F}$이므로 전체는 $\mathrm{F}$. 변수 $n$개짜리 합성명제의 진리표는 항상 $2^n$행이다.
예제 3 (공허한 참). "$2+2=5$이면 $2$는 홀수이다"는 참이다 — 전건이 거짓이므로 계약이 위반될 길이 없다(vacuous truth). 이 규약은 임의로 정한 것이 아니라, "모든 원소에 대해 $\dots$이면 $\dots$" 꼴의 수학적 진술이 빈 경우에도 무너지지 않게 하려면 강제되는 선택이다.
예제 4 (함의의 부정). $\neg(p\to q)\equiv\neg(\neg p\lor q)\equiv p\land\neg q$ (정리 3, 드모르간, 이중부정). 따라서 "합격하면 한턱낸다"의 부정은 "합격했는데 한턱내지 않는다"이지, "합격하면 한턱내지 않는다"라는 또 다른 함의가 아니다.
예제 5 (배타적 논리합의 표현). $p\oplus q\equiv(p\lor q)\land\neg(p\land q)\equiv\neg(p\leftrightarrow q)$. 진리표에서 $p\oplus q$ 열은 두 변수의 값이 다를 때에만 T인데, 이는 $p\leftrightarrow q$ 열을 정확히 반전한 것이다.
예제 6 (오류 논증). "비가 오면 경기가 취소된다. 경기가 취소되었다. 그러므로 비가 왔다"는 타당하지 않다. 형식은 $((p\to q)\land q)\to p$인데 배정 $p=\mathrm{F}, q=\mathrm{T}$(정전으로 취소)에서 전제는 모두 참이지만 결론이 거짓이다 — 후건 긍정의 오류.
흔한 오해와 함정
- "$p\to q$는 $p$가 $q$의 원인이라는 뜻이다" — 함의는 인과·시간 관계가 아니라 진리값만의 함수다. "$1+1=2$이면 파리는 프랑스에 있다"는 두 문장이 무관해도 참이다.
- "전건이 거짓이면 조건문의 진리값을 정할 수 없다" — 정의상 참이다(예제 3). 미정으로 두면 함의가 진리함수가 되지 못한다.
- "일상어의 '또는'은 항상 $\lor$이다" — 식당의 "밥 또는 빵"은 대개 배타적($\oplus$)이다. 수학의 $\lor$는 언제나 포함적이며, 배타를 원하면 $\oplus$를 명시해야 한다.
- "역은 대우처럼 원 명제와 동치이다" — 거짓. $q\to p$는 $p\to q$와 독립이다(정리 4의 반례). 역과 이는 서로 대우이므로 그 둘끼리만 동치다.
- "결론이 참이면 좋은 논증이고, 타당한 논증의 결론은 늘 참이다" — 타당성은 형식의 성질이다. 전제가 거짓이면 타당한 논증도 거짓 결론을 낼 수 있고, 엉터리 형식이 우연히 참인 결론에 도달할 수도 있다.
- "$p\equiv q$도 하나의 합성명제다" — $\equiv$는 "$p\leftrightarrow q$가 항진"이라는 명제들 사이의 관계다. 합성명제 안에 연결사로 등장하는 것은 $\leftrightarrow$이다.
큰 그림 / 연결
명제논리는 이 코스 전체의 문법이다. 술어와 한정기호는 명제를 술어와 한정기호로 쪼개 표현력을 확장하되 이 장의 동치 법칙(특히 드모르간)을 그대로 물려받고, 증명 기법는 정리 4의 대우 법칙을 대우 증명으로, modus ponens를 직접 증명의 한 걸음으로, $\neg(p\to q)\equiv p\land\neg q$를 귀류법의 출발점으로 번역한다. 집합과 함수의 집합 연산은 이 장의 거울이다 — $\cap,\cup,{}^c$는 $\land,\lor,\neg$에 대응하고 집합의 드모르간 법칙은 정리 1의 직역이다. 진리표의 행 수 $2^n$은 셈의 기본 원리의 곱의 법칙이 처음 등장하는 자리이기도 하다. 응용 쪽으로는 논리 회로 설계와 SAT 문제(명제논리 충족가능성 판정, 최초의 NP-완전 문제)가 모두 이 장의 언어로 서술된다.
연습문제
- 다음이 명제인지 판별하라: (a) "$\pi>3$" (b) "$x^2\ge0$" (c) "내일 비가 올까?" (d) "모든 짝수는 $2$로 나누어진다" (e) "이 문장은 참이다".
- $(p\to q)\land(q\to p)$의 진리표를 작성하고 $p\leftrightarrow q$와 동치임을 확인하라. 명제변수가 $5$개인 합성명제의 진리표는 몇 행인가.
- $\neg(p\to q)\equiv p\land\neg q$를 진리표 없이 동치 법칙만으로 유도하고, "이 함수가 연속이면 미분가능하다"의 부정을 서술하라.
- 둘째 분배법칙 $p\lor(q\land r)\equiv(p\lor q)\land(p\lor r)$를 $8$행 진리표로 직접 검증하라.
- $(p\lor q)\to r\equiv(p\to r)\land(q\to r)$를 동치 법칙(정리 1–3)만으로 증명하라.
- 선언 삼단논법 $((p\lor q)\land\neg p)\to q$가 항진명제임을 증명하라.
- 다음 논증의 타당성을 판정하라: "합격하면 여행을 간다. 여행을 가지 않았다. 그러므로 합격하지 못했다." 또한 "합격하지 못하면 여행을 가지 않는다"를 전제로 같은 결론을 내는 논증은 타당한가.
- $n$개의 명제변수 위의 진리함수(진리표의 가능한 출력 열)는 정확히 $2^{2^n}$개임을 보이고, 모든 진리함수가 $\neg,\land,\lor$만으로 표현됨(함수적 완전성)을 증명하라.
힌트 / 정답
- (a) 참인 명제. (b) 변수가 있으나 모든 실수에서 참인 사실을 서술한 것으로 볼 수 있으나 한정사가 명시되지 않았으므로 이 장의 틀에서는 술어 — 명제 아님. (c) 의문문 — 명제 아님. (d) 참인 명제. (e) 참을 배정해도 모순이 없지만 진리값이 유일하게 결정되지 않는다는 점에서 문제적 — 보통 명제로 취급하지 않는다.
- 두 열이 네 배정 모두에서 일치한다(둘 다 $p,q$의 값이 같을 때만 T). 행 수는 $2^5=32$.
- $\neg(p\to q)\equiv\neg(\neg p\lor q)\equiv\neg\neg p\land\neg q\equiv p\land\neg q$. 부정: "이 함수는 연속인데 미분가능하지 않다."
- $p$ 값으로 경우를 나누면 빠르다: $p=\mathrm{T}$이면 양변 T, $p=\mathrm{F}$이면 양변 모두 $q\land r$.
- 좌변 $\equiv\neg(p\lor q)\lor r\equiv(\neg p\land\neg q)\lor r\equiv(\neg p\lor r)\land(\neg q\lor r)\equiv(p\to r)\land(q\to r)$ — 정리 3, 드모르간, 분배법칙 순.
- 거짓이라 가정: $p\lor q=\mathrm{T}$, $\neg p=\mathrm{T}$, $q=\mathrm{F}$. 그러면 $p=\mathrm{F}$이고 $q=\mathrm{F}$이므로 $p\lor q=\mathrm{F}$, 모순.
- 첫 논증은 modus tollens(정리 5) 형식 $((p\to q)\land\neg q)\to\neg p$이므로 타당. 둘째는 $((\neg p\to\neg q)\land\neg q)\to\neg p$ 꼴 — 전제가 이(inverse)이므로 후건 긍정과 같은 구조다. 배정 $p=\mathrm{T},q=\mathrm{F}$에서 전제 참, 결론 거짓이므로 타당하지 않다.
- 개수: 진리표의 각 행($2^n$개)에 독립적으로 T/F를 배정하므로 $2^{2^n}$. 완전성: 출력이 T인 각 행에 대해, 그 행에서 T인 변수는 그대로, F인 변수는 부정을 취한 리터럴들의 논리곱(최소항)을 만들면 정확히 그 행에서만 참이다. 이런 최소항들의 논리합(선언 표준형, DNF)이 주어진 진리함수와 같은 표를 갖는다. T인 행이 하나도 없으면 $p\land\neg p$를 쓴다.