정의. 참인지 거짓인지가 분명하게 정해지는 문장을 명제라고 합니다. 참과 거짓 중 하나를 그 명제의 진리값이라고 합니다.
핵심은 "참·거짓이 정해진다"입니다. 지금 당장 어느 쪽인지 몰라도, 원리적으로 참 또는 거짓 중 하나로 정해지기만 하면 명제입니다.
명제인 예:
"2는 짝수이다." (참)
"7은 3의 배수이다." (거짓)
"100번째 소수는 541이다." (실제로 참이며, 계산으로 정해집니다.)
명제가 아닌 예:
"이 그림은 아름답다." (기준에 따라 달라져 참·거짓이 정해지지 않습니다.)
"x는 짝수이다." (x가 정해지기 전에는 참·거짓이 없습니다. 이런 문장은 뒤에서 다룰 명제함수입니다.)
"지금 몇 시입니까?" (물음은 참·거짓을 따질 수 없습니다.)
직관은 이렇습니다. 명제는 "참"이라는 도장과 "거짓"이라는 도장 중 정확히 하나가 찍히는 문장입니다.
문제 1. (기초) 다음 중 명제인 것을 모두 고르십시오. (가) "3+4=8" (나) "창문을 닫아라." (다) "5는 소수이다." (라) "x+1>0" 답. (가), (다) 풀이. (가)는 거짓인 명제, (다)는 참인 명제로 진리값이 정해집니다. (나)는 명령문이라 참·거짓을 따질 수 없습니다. (라)는 x가 정해지지 않아 진리값이 없으므로 명제가 아니라 명제함수입니다.
문제 2. (기초) 명제 "12는 5의 배수이다"의 진리값을 말하십시오. 답. 거짓(F) 풀이.12=5×2+2로 나머지가 2이므로 12는 5의 배수가 아닙니다. 따라서 이 명제는 거짓입니다.
문제 3. (표준) "이 문장은 거짓이다"가 명제가 될 수 없는 이유를 설명하십시오. 답. 참이라 하면 거짓이 되고, 거짓이라 하면 참이 되어 진리값을 하나로 정할 수 없기 때문입니다. 풀이. 이 문장이 참이라고 가정하면, 문장의 내용대로 "이 문장은 거짓"이 되어 모순입니다. 거짓이라고 가정하면, 문장의 내용이 틀린 것이므로 "이 문장은 참"이 되어 또 모순입니다. 어느 쪽으로도 진리값이 확정되지 않으므로 명제가 아닙니다(거짓말쟁이 역설).
문제 2. (표준) "x≥3"의 부정을 쓰십시오. 답. "x<3" 풀이.x≥3은 x=3을 포함해 그 이상 전부를 뜻합니다. 이것이 성립하지 않는 경우는 x가 3보다 작을 때뿐이므로 부정은 x<3입니다. "x≤3"이나 "x>3"으로 쓰면 경계값 처리가 틀립니다.
문제 3. (표준) ¬(¬P)≡P임을 진리표로 확인하십시오. 답. 아래 진리표에서 ¬(¬P) 열과 P 열이 같습니다. 풀이.P=T이면 ¬P=F, ¬(¬P)=T입니다. P=F이면 ¬P=T, ¬(¬P)=F입니다. 모든 경우에 ¬(¬P)의 값이 P와 같으므로 두 명제는 동치입니다.
정의.논리곱P∧Q는 P와 Q가 모두 참일 때만 참입니다. 논리합P∨Q는 P와 Q 중 적어도 하나가 참이면 참입니다.
P
Q
P∧Q
P∨Q
T
T
T
T
T
F
F
T
F
T
F
T
F
F
F
F
주의할 점은 논리합의 "또는"이 일상어와 다르다는 것입니다. 수학의 ∨는 둘 다 참인 경우도 포함하는 포괄적 "또는"입니다. "커피 또는 홍차"처럼 하나만 고르는 배타적 뜻이 아닙니다.
문제 1. (기초) P: "2>1", Q: "3<0"일 때 P∧Q와 P∨Q의 진리값을 말하십시오. 답.P∧Q는 거짓, P∨Q는 참. 풀이.P는 참, Q는 거짓입니다. 논리곱은 둘 다 참이어야 하므로 거짓입니다. 논리합은 적어도 하나가 참이면 참인데 P가 참이므로 참입니다.
문제 2. (표준) "x는 2 이상 5 이하이다"를 논리곱으로 나타내십시오. 답.(x≥2)∧(x≤5) 풀이. "2 이상"은 x≥2, "5 이하"는 x≤5이고, 두 조건이 동시에 성립해야 하므로 논리곱으로 잇습니다.
문제 3. (심화) P∨(P∧Q)≡P임을 진리표로 보이십시오(흡수법칙). 답. 네 경우 모두 P∨(P∧Q)의 값이 P와 같습니다. 풀이.P=T이면 P∨(⋯)는 첫 항이 참이라 항상 참이고 P도 참입니다. P=F이면 P∧Q=F이므로 P∨(P∧Q)=F∨F=F이고 P도 거짓입니다. 모든 경우 일치하므로 동치입니다.
정의.조건명제P→Q는 "P이면 Q"라는 문장입니다. 이 명제는 P가 참인데 Q가 거짓일 때만 거짓이고, 나머지는 모두 참입니다. P를 가정, Q를 결론이라 합니다.
P
Q
P→Q
T
T
T
T
F
F
F
T
T
F
F
T
가장 헷갈리는 부분은 아래 두 줄, 즉 가정 P가 거짓이면 P→Q가 무조건 참이라는 점입니다. 이것을 공허하게 참이라고 합니다.
직관은 이렇습니다. P→Q는 "P가 참이라면 Q도 참이라고 약속한다"는 약속입니다. 약속을 어기는 경우는 오직 "P가 실제로 참인데 Q가 거짓인" 경우뿐입니다. P가 애초에 참이 아니면 약속을 어길 상황 자체가 오지 않으므로 약속은 깨지지 않았고, 그래서 참으로 봅니다.
예를 들어 "비가 오면 우산을 쓴다"는 약속은, 비가 오지 않은 날에는 우산을 쓰든 안 쓰든 깨지지 않습니다. 약속이 깨지는 것은 "비가 왔는데 우산을 안 쓴" 경우 하나뿐입니다.
또한 P→Q는 논리합으로 다시 쓸 수 있습니다.
(P→Q)≡(¬P∨Q)
이 식은 진리표로 확인됩니다. P가 거짓이면 ¬P가 참이라 전체가 참이고, P가 참이면 Q의 값이 그대로 전체 값이 됩니다.
문제 1. (기초) P: "1=2", Q: "3은 짝수이다"일 때 P→Q의 진리값을 말하십시오. 답. 참 풀이.P는 거짓입니다. 조건명제는 가정이 거짓이면 결론에 상관없이 참(공허하게 참)이므로 P→Q는 참입니다.
문제 2. (표준) 조건명제 "n이 4의 배수이면 n은 짝수이다"의 진리값을 말하고 이유를 설명하십시오. 답. 참 풀이.n이 4의 배수이면 n=4k로 쓸 수 있고 n=2(2k)이므로 짝수입니다. 가정이 참인 모든 경우에 결론도 참이고, 가정이 거짓인 경우는 공허하게 참이므로 이 조건명제는 항상 참입니다.
문제 3. (심화) (P→Q)≡(¬P∨Q)를 진리표로 증명하십시오. 답. 네 경우 모두 두 식의 진리값이 같습니다. 풀이.(P,Q)=(T,T): P→Q=T, ¬P∨Q=F∨T=T. (T,F): P→Q=F, ¬P∨Q=F∨F=F. (F,T): T, T∨T=T. (F,F): T, T∨F=T. 모든 행에서 값이 같으므로 동치입니다.
즉 원명제와 대우는 항상 동치입니다. 반면 역과 이는 원명제와 동치가 아닙니다(역과 이끼리는 서로 대우 관계라 동치입니다).
진리표로 확인해 봅니다.
P
Q
P→Q
¬Q→¬P
T
T
T
T
T
F
F
F
F
T
T
T
F
F
T
T
세 번째와 네 번째 열이 완전히 같으므로 원명제와 대우는 동치입니다. 이 사실은 4강의 대우증명법에서 직접 쓰입니다. 어떤 명제를 곧바로 증명하기 어려우면 그 대우를 증명해도 된다는 근거가 바로 이 동치입니다.
문제 1. (기초) "x=2이면 x2=4이다"의 대우를 쓰십시오. 답. "x2=4이면 x=2이다." 풀이. 대우는 결론을 부정한 것을 가정으로, 가정을 부정한 것을 결론으로 놓습니다. 결론 "x2=4"의 부정은 "x2=4", 가정 "x=2"의 부정은 "x=2"입니다.
문제 2. (표준) "x=2이면 x2=4"의 역을 쓰고, 원명제와 역의 진리값이 다를 수 있음을 예로 보이십시오. 답. 역은 "x2=4이면 x=2"이며, x=−2가 반례라서 역은 거짓입니다(원명제는 참). 풀이. 원명제는 참입니다. 역 "x2=4이면 x=2"에서 x=−2를 넣으면 가정 x2=4는 참이지만 결론 x=2는 거짓이므로 역은 거짓입니다. 따라서 원명제가 참이어도 역은 거짓일 수 있습니다.
문제 3. (심화) 원명제의 이가 역의 대우임을 이용해, 이와 역이 동치임을 설명하십시오. 답. 역 Q→P의 대우는 ¬P→¬Q인데 이것이 곧 이이므로, 이는 역의 대우이고 대우는 원명제와 동치이므로 이와 역은 동치입니다. 풀이. 역은 Q→P입니다. 임의의 조건명제는 그 대우와 동치이므로, Q→P는 대우 ¬P→¬Q와 동치입니다. 그런데 ¬P→¬Q가 바로 원명제의 이입니다. 따라서 이와 역은 동치입니다.
두 명제 P와 Q가 모든 경우에 같은 진리값을 가지면 P≡Q, 즉 동치라고 합니다. 이것은 P↔Q가 항상 참(항진명제)이라는 것과 같습니다.
자주 쓰는 동치는 드모르간 법칙입니다.
¬(P∧Q)≡¬P∨¬Q,¬(P∨Q)≡¬P∧¬Q
말로 풀면 "그리고의 부정은 부정의 또는", "또는의 부정은 부정의 그리고"입니다. 부정이 괄호 안으로 들어가면서 ∧와 ∨가 서로 바뀝니다.
문제 1. (기초) P↔Q가 참이 되는 경우를 모두 쓰십시오. 답.P와 Q가 모두 참이거나, 모두 거짓인 경우. 풀이. 쌍조건은 두 명제의 진리값이 같을 때만 참입니다. 같은 경우는 (참, 참)과 (거짓, 거짓) 두 가지입니다.
문제 2. (표준) 드모르간 법칙 ¬(P∧Q)≡¬P∨¬Q를 진리표로 증명하십시오. 답. 네 경우 모두 두 식의 값이 같습니다. 풀이.(T,T): ¬(T)=F, ¬P∨¬Q=F∨F=F. (T,F): ¬(F)=T, F∨T=T. (F,T): T, T∨F=T. (F,F): T, T∨T=T. 모든 행이 일치하므로 동치입니다.
문제 3. (심화) "x>0 그리고 y>0"의 부정을 드모르간 법칙으로 쓰십시오. 답. "x≤0 또는 y≤0" 풀이.P: x>0, Q: y>0로 두면 부정할 것은 ¬(P∧Q)입니다. 드모르간 법칙으로 ¬P∨¬Q가 되고, ¬P는 x≤0, ¬Q는 y≤0이므로 "x≤0 또는 y≤0"입니다.
말로 풀면 "모든 것이 성립한다의 부정은, 성립하지 않는 것이 하나 있다"이고, "성립하는 것이 있다의 부정은, 모든 것이 성립하지 않는다"입니다. 부정이 한정기호를 지나가면 ∀과 ∃가 서로 바뀌고 안쪽 명제가 부정됩니다.
여러 한정기호가 겹치면 순서가 뜻을 바꿉니다. 실수 전체에서
∀x∃y(y>x)
는 "어떤 x를 주더라도 그보다 큰 y가 있다"로 참입니다(y=x+1로 잡으면 됩니다). 그러나 순서를 바꾼
∃y∀x(y>x)
는 "모든 x보다 큰 하나의 y가 존재한다"로, 그런 최대 실수는 없으므로 거짓입니다. ∀과 ∃의 순서는 함부로 바꾸면 안 됩니다.
문제 1. (기초) "∀x∈R,x2≥0"을 말로 옮기고 진리값을 말하십시오. 답. "모든 실수 x에 대해 x2은 0 이상이다", 참. 풀이. 임의의 실수의 제곱은 음수가 될 수 없으므로(x2≥0) 모든 x에서 성립합니다. 따라서 참입니다.
문제 2. (표준) "∀x(x>0→x2>0)"의 부정을 한정기호로 쓰십시오. 답.∃x(x>0∧x2≤0) 풀이.¬∀xP(x)≡∃x¬P(x)이고, 안쪽 P(x)는 조건명제 x>0→x2>0입니다. 조건명제의 부정은 (P→Q)≡(¬P∨Q)의 부정, 즉 P∧¬Q이므로 x>0∧x2≤0입니다.
문제 3. (심화) ∀x∃y(x+y=0)과 ∃y∀x(x+y=0)의 진리값을 실수 범위에서 각각 판정하십시오. 답. 앞은 참, 뒤는 거짓. 풀이. 앞 문장은 각 x마다 y=−x로 잡으면 x+y=0이 성립하므로 참입니다. 뒤 문장은 하나의 y가 모든 x에 대해 x+y=0을 만족해야 하는데, y를 고정하면 x=−y일 때만 성립하고 다른 x에서는 깨지므로 그런 y는 없어 거짓입니다.
문제 3. (기초) "x≤5"의 부정을 쓰십시오. 답. "x>5" 풀이.x≤5가 성립하지 않는 경우는 x가 5보다 클 때뿐이므로 부정은 x>5입니다.
문제 4. (표준) P→Q가 거짓이 되는 (P,Q)의 진리값 조합을 쓰십시오. 답.(P,Q)=(T,F) 풀이. 조건명제는 가정이 참이고 결론이 거짓인 경우에만 거짓입니다. 나머지 세 조합에서는 모두 참입니다.
문제 5. (표준) "n2이 짝수이면 n은 짝수이다"의 대우를 쓰십시오. 답. "n이 홀수이면 n2은 홀수이다." 풀이. 결론 "n은 짝수"의 부정은 "n은 홀수", 가정 "n2이 짝수"의 부정은 "n2은 홀수"입니다. 대우는 부정한 결론을 가정으로, 부정한 가정을 결론으로 놓습니다.
문제 6. (표준) "x>0 또는 x<−1"의 부정을 드모르간 법칙으로 쓰십시오. 답. "x≤0 그리고 x≥−1", 즉 −1≤x≤0. 풀이.¬(P∨Q)≡¬P∧¬Q입니다. ¬(x>0)은 x≤0, ¬(x<−1)은 x≥−1이므로 두 조건을 동시에 만족하는 −1≤x≤0입니다.
문제 7. (표준) (P→Q)∧(Q→P)와 동치인 기호를 쓰십시오. 답.P↔Q 풀이. 쌍조건은 두 방향의 조건명제가 모두 성립함을 뜻하므로 정의상 (P→Q)∧(Q→P)와 동치입니다.
문제 8. (표준) "∃x∈R,x2=2"의 진리값을 말하십시오. 답. 참 풀이.x=2가 x2=2를 만족하므로 그런 실수가 존재합니다. 따라서 참입니다.
문제 9. (표준) "모든 학생은 수학을 좋아한다"의 부정을 자연스러운 문장으로 쓰십시오. 답. "수학을 좋아하지 않는 학생이 (적어도 한 명) 있다." 풀이.¬∀xP(x)≡∃x¬P(x)입니다. "모든"의 부정은 "어떤 하나가 아니다"이므로, 수학을 좋아하지 않는 학생이 존재한다가 됩니다.
문제 10. (심화) P→Q가 참이고 Q→R이 참이면 P→R이 참임을 진리표 없이 설명하십시오(삼단논법). 답.P가 참이면 첫 조건에서 Q가 참, 둘째 조건에서 R이 참이 되고, P가 거짓이면 공허하게 참이므로 P→R은 항상 참입니다. 풀이.P가 참인 경우, P→Q가 참이므로 Q도 참이고, Q→R이 참이므로 R도 참입니다. 따라서 결론 R이 참이라 P→R이 참입니다. P가 거짓인 경우, 가정이 거짓이므로 P→R은 공허하게 참입니다. 두 경우 모두 참이므로 항상 참입니다.
문제 11. (심화) ¬(P→Q)를 ∧를 써서 나타내십시오. 답.P∧¬Q 풀이.(P→Q)≡(¬P∨Q)이므로 부정하면 드모르간 법칙으로 ¬(¬P∨Q)≡¬(¬P)∧¬Q≡P∧¬Q입니다.
문제 12. (심화) "∀x∃y(y=x2)"의 진리값을 실수 범위에서 판정하십시오. 답. 참 풀이. 임의의 실수 x에 대해 y=x2로 두면 항상 y가 하나 정해지므로 각 x마다 조건을 만족하는 y가 존재합니다. 따라서 참입니다.
문제 13. (심화) "∃x∀y(x≤y)"를 자연수 N={1,2,3,…}에서 판정하십시오. 답. 참 풀이.x=1로 잡으면 모든 자연수 y에 대해 1≤y가 성립합니다. 즉 모든 y보다 작거나 같은 x(최솟값 1)가 존재하므로 참입니다. (같은 문장을 실수에서 보면 최소 실수가 없어 거짓이 되어, 논의 범위가 진리값을 바꿈에 주의합니다.)