이산수학 2강 - 명제부터 술어논리와 추론까지
논리는 명제의 참과 거짓을 판별하고, 여러 명제를 결합하며, 올바른 결론을 이끌어 내는 규칙을 다루는 분야이다. 이 글에서는 명제와 논리연산의 기초부터 논리적 동치, 술어논리, 추론규칙까지 2강의 핵심 내용을 단계적으로 정리한다.
1. 학습 내용과 핵심 흐름
이번 강의는 명제, 논리연산, 술어논리, 추론의 네 부분으로 구성된다. 먼저 참과 거짓을 명확히 구분할 수 있는 문장을 명제로 정의하고, 논리합·논리곱·부정·배타적 논리합을 이용하여 합성명제를 만든다. 이어 조건명제와 쌍조건명제의 진리표를 살펴보고, 두 명제가 모든 경우에 같은 진리값을 갖는 논리적 동치를 학습한다.
명제논리만으로 표현하기 어려운 변수 포함 문장은 명제함수와 한정자를 이용하는 술어논리로 확장한다. 마지막으로 참인 전제에서 결론을 도출하는 추론의 뜻과 대표적인 추론규칙을 익혀 추론의 유효성을 판별한다.
학습 목표
- 명제와 명제가 아닌 문장을 구분하고 진리값을 판단한다.
- 논리연산자를 이용하여 합성명제의 진리표를 작성한다.
- 조건명제의 역·이·대우와 여러 논리적 동치법칙을 구분한다.
- 전체한정자와 존재한정자가 포함된 명제함수를 해석한다.
- 추론규칙을 적용하여 유효한 추론인지 판별한다.
2. 명제와 진리값
2.1 명제의 정의
명제(proposition)란 참과 거짓을 분명하게 구별할 수 있는 문장이나 수학적 식이다. 명제가 타당하면 진리값을 참(True, T), 타당하지 않으면 거짓(False, F)으로 나타낸다. 중요한 것은 문장이 실제로 참인지 여부뿐 아니라, 객관적인 기준에 따라 참 또는 거짓 중 하나로 확정할 수 있는지이다.
| 문장 또는 식 | 명제 여부 | 이유 |
|---|---|---|
| 6은 2의 배수이다. | 명제, T | 참임을 객관적으로 판별할 수 있다. |
| 2 + 3 = 7 | 명제, F | 거짓임을 객관적으로 판별할 수 있다. |
| 철수는 공부를 잘한다. | 명제가 아님 | ‘잘한다’의 기준이 명확하지 않다. |
| x + 2 = 0 | 명제가 아님 | x의 값에 따라 진리값이 달라지는 명제함수이다. |
강의의 예에서 “2, 3, 6은 소수이다”는 6이 소수가 아니므로 거짓이고, “소수의 개수는 무한하다”와 “지구에서 가장 높은 산은 에베레스트이다”는 참이다. 여러 내용을 ‘그리고’로 연결한 명제는 구성 요소가 모두 참이어야 전체가 참이라는 점도 함께 기억해야 한다.
2.2 명제의 종류
하나 이상의 명제와 논리연산자, 괄호로 이루어진 명제를 합성명제라고 한다. 조건과 결론의 관계를 표현하는 조건명제, 양쪽 방향을 모두 요구하는 쌍조건명제도 합성명제의 중요한 형태이다. 구성 명제의 진리값과 관계없이 항상 참인 명제는 항진명제, 항상 거짓인 명제는 모순명제라고 한다.
3. 논리연산과 진리표
3.1 합성명제와 논리연산자
실수에 덧셈·뺄셈·곱셈·나눗셈을 적용하여 새로운 수식을 만드는 것처럼, 논리값 T와 F에는 논리합, 논리곱, 부정, 배타적 논리합 등의 연산을 적용하여 합성명제를 만든다. 진리표는 구성 명제들이 가질 수 있는 모든 진리값의 조합에 대해 합성명제의 결과를 정리한 표이다.
| p | q | p ∨ q | p ∧ q | p ⊕ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| T | T | T | T | F | T | T |
| T | F | T | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | F | F | F | T | T |
3.2 논리합, 논리곱, 부정
- 논리합(disjunction, p ∨ q): p와 q 가운데 하나 이상이 참이면 참이다. 두 명제가 모두 거짓일 때만 거짓이다.
- 논리곱(conjunction, p ∧ q): p와 q가 모두 참일 때만 참이다. 하나라도 거짓이면 거짓이다.
- 부정(negation, ¬p 또는 ∼p): p의 진리값을 반대로 바꾼다. p가 참이면 ¬p는 거짓이고, p가 거짓이면 ¬p는 참이다.
3.3 배타적 논리합
배타적 논리합(exclusive or, p ⊕ q)은 p와 q의 진리값이 서로 다를 때만 참이다. 따라서 두 명제가 모두 참이거나 모두 거짓이면 거짓이며, 다음과 같이 기본 연산으로 나타낼 수 있다.
예를 들어 (p ∧ q) ∨ (p ⊕ q)는 p와 q 중 적어도 하나가 참일 때 참이므로 p ∨ q와 같은 진리표를 갖는다. 복잡한 합성명제는 괄호 안쪽의 연산부터 열을 하나씩 추가해 계산하면 실수를 줄일 수 있다.
4. 조건명제와 쌍조건명제
4.1 조건명제
조건명제 p → q는 “p이면 q이다”라고 읽는다. p는 조건, q는 결론의 역할을 하며, p는 q의 충분조건이고 q는 p의 필요조건이다. 조건명제는 p가 참인데 q가 거짓인 경우에만 거짓이다. p가 거짓이면 q의 진리값과 관계없이 조건명제는 참으로 정한다.
4.2 쌍조건명제
쌍조건명제 p ↔ q는 “p일 필요충분조건이 q이다” 또는 “p이면 그리고 그때에만 q이다”라고 읽는다. p와 q가 조건과 결론의 역할을 동시에 수행하므로 두 방향의 조건명제가 모두 참이어야 한다.
따라서 p와 q의 진리값이 같으면 참, 다르면 거짓이다.
4.3 역, 이, 대우
| 구분 | 논리식 | 원래 명제와의 관계 |
|---|---|---|
| 조건명제 | p → q | 기준 명제 |
| 역(converse) | q → p | 원래 명제와 반드시 동치가 아님 |
| 이(inverse) | ¬p → ¬q | 역과 서로 동치 |
| 대우(contrapositive) | ¬q → ¬p | 원래 명제와 항상 동치 |
그림으로 연결 관계를 기억하면 조건명제와 대우가 서로 동치이고, 역과 이가 서로 동치임을 쉽게 확인할 수 있다. 반면 원래 명제가 참이라고 해서 그 역도 자동으로 참이 되는 것은 아니다.
5. 논리적 동치와 주요 법칙
5.1 논리적 동치
두 명제가 가능한 모든 진리값 조합에서 항상 같은 진리값을 가지면 논리적 동치(logical equivalence)라고 하며 p ≡ q로 나타낸다. 두 식의 동치 여부는 진리표의 최종 열을 비교하여 증명할 수 있다. 예를 들어 p ∨ (q ∧ r)와 (p ∨ q) ∧ (p ∨ r)는 분배법칙에 의해 동치이다.
5.2 기본 동치법칙
| 법칙 | 논리합 형태 | 논리곱 형태 또는 관련 식 |
|---|---|---|
| 교환법칙 | p ∨ q ≡ q ∨ p | p ∧ q ≡ q ∧ p |
| 결합법칙 | (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) |
| 분배법칙 | p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) |
| 항등법칙 | p ∨ F ≡ p | p ∧ T ≡ p |
| 지배법칙 | p ∨ T ≡ T | p ∧ F ≡ F |
| 멱등법칙 | p ∨ p ≡ p | p ∧ p ≡ p |
| 흡수법칙 | p ∨ (p ∧ q) ≡ p | p ∧ (p ∨ q) ≡ p |
5.3 부정과 함축에 관한 법칙
- 부정법칙: ¬T ≡ F, ¬F ≡ T, p ∨ ¬p ≡ T, p ∧ ¬p ≡ F
- 이중부정법칙: ¬(¬p) ≡ p
- 드 모르간 법칙: ¬(p ∨ q) ≡ ¬p ∧ ¬q, ¬(p ∧ q) ≡ ¬p ∨ ¬q
- 함축법칙: p → q ≡ ¬p ∨ q
- 대우법칙: p → q ≡ ¬q → ¬p
드 모르간 법칙은 연속된 범위의 부정을 구할 때 유용하다. 예를 들어 −2 < x < 3은 (−2 < x) ∧ (x < 3)이므로 그 부정은 (x ≤ −2) ∨ (x ≥ 3)이다. 즉 범위 밖의 두 구간 가운데 하나에 속한다는 뜻이다.
5.4 항진명제와 모순명제
합성명제를 구성하는 개별 명제의 진리값과 관계없이 항상 참인 명제를 항진명제(tautology), 항상 거짓인 명제를 모순명제(contradiction)라고 한다. p ∨ ¬p는 항진명제이고 p ∧ ¬p는 모순명제이다. 논리적 동치와 추론규칙은 관련 조건식이 항진명제가 되는지를 이용해 확인할 수 있다.
6. 술어논리와 명제함수
6.1 명제함수
명제함수(propositional function)는 변수의 값에 따라 진리값이 결정되는 문장이나 식이다. 예를 들어 P(x, y)가 x² + y² = 4라면 변수에 구체적인 값을 대입하거나 변수의 범위를 한정해야 참과 거짓을 판별할 수 있다. 명제만을 대상으로 하는 명제논리와 달리 술어논리는 변수, 술어, 정의역, 한정자를 함께 다룬다.
6.2 전체한정자와 존재한정자
| 한정자 | 표현 | 의미 | 판정 방법 |
|---|---|---|---|
| 전체한정자 | ∀xP(x) | 정의역의 모든 임의의 x에 대해 P(x)가 참 | 반례가 하나라도 있으면 거짓 |
| 존재한정자 | ∃xP(x) | 정의역의 어떤 x에 대해 P(x)가 참 | 참이 되는 사례가 하나만 있어도 참 |
정의역은 한정명제의 진리값을 결정하는 핵심 조건이다. P(x)가 “x는 실수이다”이고 정의역이 양수라면 ∀xP(x)는 참이다. 반면 P(x)가 x² + x − 2 > 0이고 정의역이 실수라면 x = 0에서 거짓이므로 ∀xP(x)는 거짓이다. 또한 P(x)가 “x는 무리수이다”이고 정의역이 유리수라면 ∃xP(x)는 거짓이다.
“모든 x가 P이다”의 부정은 “P가 아닌 x가 적어도 하나 존재한다”이고, “P인 x가 존재한다”의 부정은 “모든 x가 P가 아니다”이다. 즉 ¬∀xP(x) ≡ ∃x¬P(x), ¬∃xP(x) ≡ ∀x¬P(x)이다.
6.3 타당성의 직관적 검사
한정자가 포함된 명제함수의 타당성은 벤 다이어그램으로 직관적으로 검사할 수 있다. “모든 평행사변형은 사각형이다”는 평행사변형 집합이 사각형 집합 안에 포함된 그림으로 나타난다. 또한 “영희는 서울에 있다”, “서울은 한국에 있다”라는 포함 관계가 모두 참이면 영희가 한국에 있다는 결론을 도출할 수 있다.
7. 추론과 추론규칙
7.1 추론과 유효추론
추론(inference)은 참으로 알려진 명제를 바탕으로 다른 명제를 유도하는 과정이다. 결론의 근거로 주어진 명제를 전제(premise), 새로 유도된 명제를 결론(conclusion)이라고 한다. 전제를 모두 참이라고 가정했을 때 결론이 항상 참이 되는 추론을 유효추론이라고 한다.
추론의 유효성은 실제 세계에서 각 명제가 우연히 참인지가 아니라 논리적 형식으로 판정한다. 모든 전제가 참인데 결론이 거짓인 행이 진리표에 하나라도 있으면 그 추론은 유효하지 않다.
7.2 대표적인 추론규칙
| 법칙 | 전제 | 결론 | 핵심 구조 |
|---|---|---|---|
| 선언적 부가 | p | p ∨ q | 참인 명제에 논리합을 덧붙인다. |
| 단순화 | p ∧ q | p | 참인 논리곱에서 한 성분을 얻는다. |
| 긍정논법 | p, p → q | q | 전건을 긍정해 후건을 얻는다. |
| 부정논법 | ¬q, p → q | ¬p | 후건을 부정해 전건을 부정한다. |
| 선언적 삼단논법 | p ∨ q, ¬p | q | 한 선택지를 제거해 다른 것을 얻는다. |
| 가설적 삼단논법 | p → q, q → r | p → r | 조건 관계를 연쇄적으로 연결한다. |
7.3 잘못된 추론을 판별하는 방법
p → q와 q를 전제로 p를 결론 내리는 형식은 후건 긍정의 오류로, 유효한 추론이 아니다. 진리표에서 p = F, q = T인 경우 두 전제 p → q와 q는 모두 참이지만 결론 p는 거짓이기 때문이다. 조건명제의 역을 원래 명제와 같은 것으로 착각하지 않도록 주의해야 한다.
8. 핵심 개념 정리
- 명제는 참과 거짓을 분명하게 구별할 수 있는 문장이나 수학적 식이다.
- 논리합은 하나 이상이 참일 때, 논리곱은 모두 참일 때, 배타적 논리합은 두 진리값이 다를 때 참이다.
- 조건명제 p → q는 p가 참이고 q가 거짓일 때만 거짓이며, 쌍조건명제는 두 진리값이 같을 때 참이다.
- p → q는 대우 ¬q → ¬p와 동치이고, 역 q → p는 이 ¬p → ¬q와 동치이다.
- 논리적 동치는 가능한 모든 경우에 두 명제의 진리값이 같다는 뜻이다.
- 명제함수는 변수의 값에 따라 진리값이 결정되며 ∀는 모든 원소, ∃는 적어도 하나의 원소를 대상으로 한다.
- 전제가 모두 참일 때 결론이 항상 참이면 유효추론이다.
시험 직전 최종 점검
진리표에서는 p → q가 거짓인 단 하나의 경우(T, F)를 먼저 기억하고, p ↔ q와 p ⊕ q가 서로 반대되는 열이라는 점을 활용한다. 동치법칙은 드 모르간·함축·대우법칙을 중심으로 식을 변형해 보고, 추론에서는 긍정논법과 부정논법을 후건 긍정·전건 부정의 오류와 구별하는 연습이 중요하다.
9. 예상문제 20선
1. 다음 중 명제인 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
“7은 홀수이다”는 객관적으로 참임을 판별할 수 있으므로 명제이다. 나머지는 질문, 명령 또는 주관적인 평가이다.
2. p = T, q = T일 때 p ⊕ q의 진리값은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
배타적 논리합은 두 진리값이 서로 다를 때만 참이다. 둘 다 참이므로 결과는 거짓이다.
3. p = F, q = F일 때 p ∨ q의 진리값은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
논리합은 두 명제 중 하나 이상이 참일 때 참이다. 두 명제가 모두 거짓인 경우에는 거짓이다.
4. 조건명제 p → q가 거짓이 되는 경우는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
조건이 성립했는데 결론이 성립하지 않는 경우, 즉 전건이 참이고 후건이 거짓일 때만 p → q는 거짓이다.
5. 쌍조건명제 p ↔ q에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
p ↔ q는 (p → q) ∧ (q → p)와 동치이다. 따라서 두 명제의 진리값이 모두 참이거나 모두 거짓일 때 참이다.
6. 조건명제 p → q의 대우는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
대우는 후건과 전건의 순서를 바꾸고 각각을 부정한 ¬q → ¬p이다. 원래 조건명제와 대우는 항상 동치이다.
7. 조건명제 p → q의 이(inverse)는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
이는 전건과 후건의 위치는 그대로 두고 둘을 각각 부정한 명제이다. q → p는 역, ¬q → ¬p는 대우이다.
8. 드 모르간 법칙으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
논리곱 전체를 부정하면 각 명제를 부정한 뒤 논리합으로 연결한다. 마찬가지로 논리합의 부정은 부정들의 논리곱이다.
9. 함축법칙에 따라 p → q와 동치인 식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
조건명제 p → q는 전건의 부정과 후건을 논리합으로 연결한 ¬p ∨ q와 같은 진리표를 가진다.
10. 다음 중 항진명제는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
p와 ¬p 가운데 하나는 반드시 참이므로 p ∨ ¬p는 p의 진리값과 관계없이 언제나 참이다.
11. 흡수법칙을 바르게 나타낸 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
p가 이미 논리합의 한 항이면 p ∧ q가 더해져도 결과는 p이다. 이것이 논리합 형태의 흡수법칙이다.
12. 명제함수에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
명제함수는 변수에 값을 대입하거나 정의역을 한정하면 진리값을 판정할 수 있는 문장이나 식이다.
13. ∀xP(x)의 의미로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
전체한정자 ∀는 “모든” 또는 “임의의”를 뜻한다. 정의역 안의 반례가 하나라도 발견되면 전체명제는 거짓이다.
14. ∃xP(x)가 참임을 보이는 방법은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
존재한정자는 조건을 만족하는 원소가 하나 이상 존재한다는 뜻이다. 참이 되는 구체적인 사례 하나면 충분하다.
15. ¬∀xP(x)와 논리적으로 동치인 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
모든 x가 P를 만족한다는 주장의 부정은 P를 만족하지 않는 x가 적어도 하나 존재한다는 뜻이다.
16. 추론에서 결론의 근거로 주어지는 알려진 명제는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
추론에서 결론의 근거를 제공하는 명제를 전제라고 하고, 그 전제로부터 새로 유도된 명제를 결론이라고 한다.
17. 전제 p와 p → q로부터 q를 얻는 추론규칙은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
전건 p가 참이고 p이면 q라는 조건명제가 참일 때 후건 q를 결론으로 얻는 규칙이 긍정논법이다.
18. 전제 ¬q와 p → q로부터 얻을 수 있는 결론은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
후건 q가 거짓이라는 사실과 p → q로부터 전건 p가 거짓임을 얻는 부정논법의 구조이다.
19. p → q, q → r을 전제로 p → r을 도출하는 규칙은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
두 조건명제를 중간 명제 q로 연결하여 p → r을 얻는 규칙을 가설적 삼단논법 또는 추이법칙이라고 한다.
20. 전제 p → q와 q로부터 p를 결론 내리는 추론이 유효하지 않은 이유는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
유효추론은 전제가 모두 참일 때 결론이 항상 참이어야 한다. p = F, q = T는 두 전제를 참으로 만들면서 결론을 거짓으로 만드는 반례이다.
댓글
댓글 쓰기