수학은 엄밀한 논리적 추론을 바탕으로 한다. 이 장에서는 수학적 추론의 기초가 되는 명제와 논리를 다룬다. 명제의 기본 개념과 연산을 살펴보고, 이를 통해 수학적 진술을 정확하게 표현하고 분석하는 방법을 익힌다.
1. 명제의 개념
명제(proposition)란 참이나 거짓을 명확하게 판별할 수 있는 문장이다. 예를 들어, "\(2 + 3 = 5\)"는 참인 명제이고, "\(\pi < 3\)"은 거짓인 명제이다. 반면 "\(x > 5\)"는 \(x\)의 값이 정해지지 않았으므로 명제가 아니다.
[변수를 포함한 문장은 명제가 아니지만, 변수에 특정 값을 대입하면 참 또는 거짓이 결정되는 문장은 명제와 유사한 성질을 가진다. 따라서 이런 문장도 명제 연산자(논리합, 논리곱, 부정, 조건부 등)를 사용하여 변형하거나 결합할 수 있다.]
명제를 나타낼 때는 보통 \(p\), \(q\), \(r\) 등의 소문자를 사용한다. 명제 \(p\)가 참일 때는 "\(p\)의 진릿값이 참(True, T)이다" 또는 간단히 "\(p\)가 참이다"라고 말하고, \(p\)가 거짓일 때는 "\(p\)의 진릿값이 거짓(False, F)이다" 또는 간단히 "\(p\)가 거짓이다"라고 말한다.
2. 명제의 연산
하나의 명제를 변형하거나 둘 이상의 명제를 결합하여 새로운 명제를 만들 수 있다. 이러한 연산을 명제 연산 또는 논리 연산이라고 부른다.
- 부정(negation): 명제 \(p\)의 부정 \(\neg p\)는 \(p\)가 참일 때 거짓이고, \(p\)가 거짓일 때 참이다. "\(p\)가 아니다"라고 읽는다.
- 논리곱(conjunction): 명제 \(p\)와 \(q\)의 논리곱 \(p \wedge q\)는 \(p\)와 \(q\)가 모두 참일 때만 참이다. "\(p\) 그리고 \(q\)"라고 읽는다.
- 논리합(disjunction): 명제 \(p\)와 \(q\)의 논리합 \(p \vee q\)는 \(p\)와 \(q\) 중 적어도 하나가 참일 때 참이다. "\(p\) 또는 \(q\)"라고 읽는다.
- 조건부(conditional): 명제 \(p\)와 \(q\)의 조건부 또는 함의 \(p \to q\)는 \(p\)가 참이고 \(q\)가 거짓일 때만 거짓이고, 나머지 경우는 모두 참이다. "\(p\)이면 \(q\)이다"라고 읽는다. 여기서 \(p\)를 가정 또는 전제라 하고, \(q\)를 결론이라 한다.
- 쌍조건부(biconditional): 명제 \(p\)와 \(q\)의 쌍조건부 \(p \leftrightarrow q\)는 \(p\)와 \(q\)의 진릿값이 같을 때 참이다. "\(p\)일 필요충분조건은 \(q\)이다"라고 읽는다.
명제 연산의 진릿값을 나타내는 표를 진리표(truth table)라고 부른다. 기본적인 명제 연산자의 진리표는 다음 표와 같다.
두 명제 \(p\)와 \(q\)에 대하여, \(p \leftrightarrow q\)가 항상 참일 때 \(p\)와 \(q\)가 논리적으로 동치(logically equivalent)라고 하고 \(p \equiv q\)로 나타낸다. 예를 들어, \(p \to q \equiv \neg p \vee q\)이다.
\(p \to q\)가 참일 때 \(p\)가 \(q\)를 논리적으로 함의한다고 하고 \(p \Rightarrow q\)로 나타낸다. \(p\Rightarrow q\)이면서 \(q \Rightarrow p\)인 것을 \(p \Leftrightarrow q\)와 같이 나타낸다.
[단순명제 \(p\), \(q\)와 마찬가지로 명제함수 \(p(x)\), \(q(x)\)에 대해서도 \(\forall x (p(x)\rightarrow q(x))\)가 참일 때 \(p(x)\Rightarrow q(x)\)로 나타내기도 한다. 이는 교육적 편의를 위한 표기법이며, 엄밀하게는 \(p\models q\)로 표기해야 한다. 더 엄밀한 표기법은 명제논리의 의미론과 일계논리의 의미론을 보기 바란다.]
3. 조건부 명제와 관련된 개념
조건부 명제 \(p \to q\)가 참일 때, 즉 \(p\Rightarrow q\)일 때 다음과 같이 정의한다.
- \(p\)는 \(q\)의 충분조건(sufficient condition)이다.
- \(q\)는 \(p\)의 필요조건(necessary condition)이다.
특히 \(p\Leftrightarrow q\)일 때, \(p\)와 \(q\)는 서로의 필요충분조건이다.
조건부 명제 \(p \to q\)와 관련하여 다음과 같은 명제들을 정의한다.
- 명제 \(q \to p\)를 \(p \rightarrow q\)의 역(converse)이라고 부른다.
- 명제 \(\neg p \to \neg q\)를 \(p \rightarrow q\)의 이(inverse)라고 부른다.
- 명제 \(\neg q \to \neg p\)를 \(p \rightarrow q\)의 대우(contrapositive)라고 부른다.
조건부 명제와 그 대우는 항상 논리적으로 동치이다. 즉, \((p \to q) \equiv (\neg q \to \neg p)\)이다. 이것을 대우법칙이라고 부른다.
문제 1.1. 다음 각각에 대하여, 주어진 두 명제가 논리적으로 동치임을 진리표를 사용하여 확인하시오.
- \(p \to q\)와 \(\neg q \to \neg p\)
- \(\neg (p \wedge q)\)와 \(\neg p \vee \neg q\)
- \(\neg (p \vee q)\)와 \(\neg p \wedge \neg q\)
- \(p \to (q \to r)\)와 \((p \wedge q) \to r\)
4. 명제 연산의 성질
명제 연산에는 다음과 같은 중요한 성질들이 있다.
- 교환법칙: \[\begin{aligned} p \wedge q &\equiv q \wedge p\\[6pt] p \vee q &\equiv q \vee p \end{aligned}\]
- 결합법칙: \[\begin{aligned} (p \wedge q) \wedge r &\equiv p \wedge (q \wedge r)\\[6pt] (p \vee q) \vee r &\equiv p \vee (q \vee r) \end{aligned}\]
- 분배법칙: \[\begin{aligned} p \wedge (q \vee r) &\equiv (p \wedge q) \vee (p \wedge r)\\[6pt] p \vee (q \wedge r) &\equiv (p \vee q) \wedge (p \vee r) \end{aligned}\]
- 드 모르간의 법칙: \[\begin{aligned} \neg (p \wedge q) &\equiv \neg p \vee \neg q\\[6pt] \neg (p \vee q) &\equiv \neg p \wedge \neg q \end{aligned}\]
- 이중부정법칙: \[\neg(\neg p) \equiv p\]
- 항등법칙: \[\begin{aligned} p \wedge \text{T} &\equiv p\\[6pt] p \vee \text{F} &\equiv p \end{aligned}\]
- 지배법칙: \[\begin{aligned} p \wedge \text{F} &\equiv \text{F}\\[6pt] p \vee \text{T} &\equiv \text{T} \end{aligned}\]
- 멱등법칙: \[\begin{aligned} p \wedge p &\equiv p\\[6pt] p \vee p &\equiv p \end{aligned}\]
문제 1.2. 진리표를 사용하여 위 성질을 증명하시오.
5. 추론 규칙
수학적 증명에서는 참인 명제들로부터 새로운 참인 명제를 이끌어내는 추론 규칙을 사용한다. 대표적인 추론 규칙은 다음과 같다.
- 전건 긍정(Modus Ponens): \(p \to q\)와 \(p\)가 참이면 \(q\)도 참이다. \[((p \to q) \wedge p) \Rightarrow q\]
- 후건 부정(Modus Tollens): \(p \to q\)와 \(\neg q\)가 참이면 \(\neg p\)도 참이다. \[((p \to q) \wedge \neg q) \Rightarrow (\neg p)\]
- 가언적 삼단논법(Hypothetical Syllogism): \(p \to q\)와 \(q \to r\)이 참이면 \(p \to r\)도 참이다. \[((p \to q) \wedge (q \to r)) \Rightarrow (p \to r)\] 이것을 추이법칙이라고도 한다.
- 선언적 삼단논법(Disjunctive Syllogism): \(p \vee q\)와 \(\neg p\)가 참이면 \(q\)도 참이다. \[((p \vee q) \wedge \neg p) \Rightarrow q\]
문제 1.3. 다음 추론이 타당한지 판별하시오.
- 만약 비가 내리면 땅이 젖는다. 땅이 젖어 있다. 따라서 비가 내린 것이다.
- 만약 \(n\)이 짝수이면 \(n^2\)도 짝수이다. \(n^2\)이 홀수이다. 따라서 \(n\)은 홀수이다.
- \(x > 2\)이면 \(x^2 > 4\)이다. \(x^2 > 4\)이면 \(x > 2\) 또는 \(x < -2\)이다. 따라서 \(x > 2\)이면 \(x > 2\) 또는 \(x < -2\)이다.
6. 항진명제와 모순명제
어떤 경우에도 항상 참인 명제를 항진명제(tautology)라고 하고, 어떤 경우에도 항상 거짓인 명제를 모순명제(contradiction)라고 한다. 예를 들어 다음과 같은 것들이 있다.
- \(p \vee \neg p\)는 항진명제이다. (배중률)
- \(p \wedge \neg p\)는 모순명제이다.
- \((p \to q) \leftrightarrow (\neg q \to \neg p)\)는 항진명제이다.
문제 1.4. 다음 명제가 항진명제인지, 모순명제인지, 아니면 둘 다 아닌지 판별하시오.
- \((p \to q) \to ((\neg p) \vee q)\)
- \((p \wedge q) \wedge \neg(p \vee q)\)
- \(((p \to q) \wedge (q \to r)) \to (p \to r)\)
- \((p \leftrightarrow q) \wedge (p \leftrightarrow \neg q)\)
7. 명제 함수
변수를 포함한 문장으로, 변수에 특정 값을 대입하면 명제가 되는 것을 명제 함수(propositional function) 또는 술어(predicate)라고 부른다. [더 엄밀하게는, 일계논리에서 자유변수를 가진 논리식이라고 부른다. 실제로 우리가 지금 '명제'라고 부르는 대상은 형식논리에서 '문장'(sentence, 자유변수가 없는 논리식)에 해당하며, 현재는 직관적 이해를 위해 '명제'와 '명제함수'라는 용어를 사용하고 있다.] 예를 들어, \(p(x): x > 5\)는 변수가 \(x\)인 명제 함수이다. \(x = 7\)일 때 \(p(x)\)는 참인 명제가 되고, \(x = 3\)일 때 \(p(x)\)는 거짓인 명제가 된다.
명제 함수는 다음 장에서 다룰 한정명제를 정의하는 데 중요한 역할을 한다. 특히 집합론에서 집합의 원소를 기술할 때 명제 함수를 사용하여 조건을 명확히 표현할 수 있다.