• 이산수학 논리 단원에서 무엇을 배우는가
• 명제란 무엇인가
• 논리연산과 조건명제 이해하기
• 역·이·대우와 논리적 동치
• 술어논리와 한정자
• 추론과 시험 포인트
• 정리
• FAQ

이산수학 논리 단원에서 무엇을 배우는가

이 단원은 문장을 참과 거짓의 구조로 바꾸어 판단하는 방법을 배우는 단원입니다. 일상에서는 대충 맞는 말처럼 느껴지는 표현도 많지만, 이산수학에서는 참인지 거짓인지가 명확해야 합니다. 그래서 먼저 어떤 문장이 명제인지 구분하고, 그다음에는 여러 명제를 연결했을 때 전체가 언제 참이 되는지를 진리표로 계산합니다. 이후에는 조건명제, 논리적 동치, 술어와 한정자, 추론 규칙까지 이어지면서 문장을 더 정확하게 다루는 방법을 익히게 됩니다.

이 장의 핵심 흐름

명제 구분
→ 논리연산과 진리표
→ 조건명제와 쌍조건명제
→ 역, 이, 대우
→ 항진명제와 모순명제
→ 논리적 동치
→ 술어논리와 한정자
→ 추론의 타당성 판단

처음부터 전부 한꺼번에 외우려고 하면 오히려 더 헷갈립니다. 이 단원은 앞부분이 뒷부분의 기초가 되기 때문에, 명제와 진리표를 먼저 이해하고 그 위에 조건명제와 한정자, 추론을 쌓는 방식으로 공부하는 것이 가장 효율적입니다.

특히 시험에서는 계산 자체보다도 해석에서 실수가 많이 납니다. 조건명제에서 왜 어떤 경우만 거짓인지, 대우가 왜 원래 명제와 같은 뜻인지, 한정자의 부정이 왜 반대로 바뀌는지를 이해하면 이후 문제 풀이가 훨씬 안정됩니다.

명제란 무엇인가

명제는 참 또는 거짓이 분명하게 결정되는 문장이나 수학적 식입니다. 여기서 가장 중요한 기준은 문장이 예쁘거나 자연스러운지가 아니라, 참과 거짓을 판별할 수 있느냐입니다. 평서문처럼 보여도 참과 거짓이 확정되지 않으면 명제가 아니고, 간단한 수학식이라도 진리값이 정해지면 명제가 됩니다.

명제와 명제가 아닌 것 구분

명제인 것
- 해는 동쪽에서 떠서 서쪽으로 진다.
- 2 + 3 = 5

명제가 아닌 것
- 이번 시험 잘 보자.
- 지금 기분이 어때?
- 야 이것 참 아름답다.
- x + 2 = 5

첫 번째와 두 번째는 참과 거짓을 바로 판단할 수 있으므로 명제입니다. 반면 바람, 질문, 감탄은 진리값을 정할 수 없기 때문에 명제가 아닙니다. 또 x + 2 = 5 같은 식은 x 값이 정해지지 않았으므로 아직 참인지 거짓인지 확정할 수 없어 명제가 아닙니다.

시험에서는 이 구분이 가장 자주 나옵니다. 따라서 문장을 보자마자 평서문인지보다 먼저, 참과 거짓이 지금 바로 정해지는지 확인하는 습관을 들이는 것이 중요합니다.

빠르게 판단하는 기준

명제
- 참/거짓 판별 가능

명제가 아님
- 질문문
- 명령문
- 감탄문
- 주관적 표현
- 변수가 있어 진리값이 아직 확정되지 않은 문장

이 기준만 정확히 잡아도 명제 파트의 첫 문제는 대부분 정리됩니다. 이후 술어논리에서 변수가 있는 문장을 다시 다루게 되지만, 그때는 한정자를 붙여서 참과 거짓이 확정된 형태로 바꾸게 됩니다.

논리연산과 조건명제 이해하기

논리연산은 명제 하나를 뒤집거나, 두 개 이상의 명제를 연결해서 새로운 명제를 만드는 방식입니다. 이산수학에서는 부정, 논리곱, 논리합, 배타적 논리합, 조건, 쌍조건을 핵심으로 다룹니다. 중요한 것은 말로만 외우는 것이 아니라, 진리표에서 각 연산이 어떤 규칙으로 움직이는지를 익히는 것입니다.

내용 시작 전, 먼저 보고 가는 기호 읽는 법

¬p   : not p, p가 아니다, p의 부정
p ∧ q : p and q, p 그리고 q, 논리곱
p ∨ q : p or q, p 또는 q, 논리합
p ⊕ q : p xor q, 둘 중 하나만 참, 배타적 논리합
p → q : p이면 q이다, 조건명제
p ↔ q : p일 때 그리고 그럴 때에만 q이다, 쌍조건명제
p ≡ q : p와 q는 논리적으로 동치이다
∀x   : 모든 x에 대하여, 전체한정자
∃x   : 어떤 x가 존재하여, 존재한정자
∴    : 따라서, 그러므로

처음에는 기호 자체가 가장 낯설 수 있습니다. 그래서 문제를 풀기 전에 기호를 한국어 문장으로 바로 읽을 수 있어야 합니다. 예를 들어 p → q를 보면 p가 q를 만든다고 보기보다, p이면 q이다라는 조건문으로 읽는 습관을 들이는 것이 중요합니다.

가장 먼저 익혀야 할 기본 연산

p: 오늘은 비가 온다.
q: 나는 우산을 가져간다.

¬p  : 오늘은 비가 오지 않는다.
p ∧ q : 오늘은 비가 오고, 나는 우산을 가져간다.
p ∨ q : 오늘은 비가 오거나, 나는 우산을 가져간다.
p ⊕ q : 둘 중 정확히 하나만 참이다.

부정은 참과 거짓을 뒤집는 가장 단순한 연산입니다. 논리곱은 둘 다 참일 때만 참이고, 논리합은 둘 중 하나라도 참이면 참입니다. 배타적 논리합은 이름 그대로 배타적이기 때문에 정확히 하나만 참일 때 참이 됩니다. 둘 다 참이면 오히려 거짓이라는 점에서 일반 논리합과 다릅니다.

조건명제가 가장 헷갈리는 이유

p → q 는 p가 참이고 q가 거짓일 때만 거짓

T → T = T
T → F = F
F → T = T
F → F = T

조건명제는 보통 처음 배울 때 가장 낯섭니다. 이유는 일상 언어의 감각과 수학적 약속이 완전히 같지 않기 때문입니다. p이면 q이다라는 말은, p가 성립했을 때 q도 반드시 따라와야 한다는 약속으로 읽습니다. 따라서 p가 참인데 q가 거짓이면 약속을 어긴 것이므로 전체가 거짓이 됩니다.

반대로 p가 애초에 거짓이면, 약속을 어겼다고 판단할 근거가 없습니다. 그래서 나머지 경우는 모두 참으로 처리합니다. 이 규칙을 이해하지 않고 외우기만 하면 조건명제 문제에서 계속 흔들리게 됩니다.

조건명제를 이해할 때는 결과가 맞았는지만 보는 것이 아니라, 앞의 조건이 실제로 발생했는지를 먼저 확인해야 합니다. 즉 조건명제는 원인과 결과를 느슨하게 이어 붙인 문장이 아니라, 앞부분이 참일 때 뒷부분도 보장되는지를 검사하는 문장이라고 보는 편이 훨씬 정확합니다.

쌍조건명제는 양방향 약속이다

p ↔ q
≡ (p → q) ∧ (q → p)

쌍조건명제는 p이면 q이고, 동시에 q이면 p인 경우를 함께 요구합니다. 그래서 두 명제의 진리값이 같을 때 참이 됩니다. 한쪽만 맞으면 되는 조건명제보다 더 강한 관계라고 보면 이해하기 쉽습니다.

역·이·대우와 논리적 동치

조건명제를 배운 다음 가장 많이 헷갈리는 부분이 역, 이, 대우입니다. 이름이 비슷해서 섞이기 쉬운데, 시험에서는 거의 반드시 구분을 요구합니다. 이 부분은 정의를 따로 외우기보다 한 문장을 기준으로 어떤 부분이 바뀌는지 비교하면서 정리하는 것이 좋습니다.

역, 이, 대우 한 번에 정리하기

원래 명제      : p → q
역 (converse) : q → p
이 (inverse)  : ¬p → ¬q
대우 (contrapositive) : ¬q → ¬p

예를 들어 비가 오면 길이 젖는다는 문장에서, 역은 길이 젖으면 비가 온다이고, 이는 비가 오지 않으면 길이 젖지 않는다이며, 대우는 길이 젖지 않으면 비가 오지 않았다가 됩니다. 여기서 중요한 사실은 원래 명제와 대우는 항상 논리적으로 동치이고, 역과 이는 서로 동치라는 점입니다.

반면 원래 명제와 역은 일반적으로 같지 않습니다. 길이 젖은 이유가 꼭 비 때문이라고는 할 수 없기 때문입니다. 이런 식으로 현실 예시를 붙여보면 왜 대우만 특별한지 훨씬 잘 이해됩니다.

항진명제, 모순명제, 동치 법칙

항진명제: p ∨ ¬p
모순명제: p ∧ ¬p
조건명제 변환: p → q ≡ ¬p ∨ q
드모르간 법칙: ¬(p ∧ q) ≡ ¬p ∨ ¬q

항진명제는 항상 참인 명제이고, 모순명제는 항상 거짓인 명제입니다. 그리고 논리적 동치는 표현은 달라도 모든 경우에서 진리값이 같다는 뜻입니다. 문제를 풀 때는 진리표로 직접 확인할 수도 있고, 자주 쓰는 동치 법칙을 이용해 식을 더 쉬운 형태로 바꿀 수도 있습니다.

특히 p → q를 ¬p ∨ q로 바꾸는 공식과 드모르간 법칙은 매우 자주 쓰입니다. 식 변형 문제뿐 아니라 증명이나 추론 문제에서도 반복적으로 등장하므로, 단순 암기보다 여러 번 적용해 보는 것이 중요합니다.

두 식이 동치인지 헷갈릴 때는 각 식의 진리표를 만든 뒤 마지막 열이 완전히 같은지 비교하면 됩니다. 이 방법은 시간이 조금 들더라도 가장 안전한 확인 방식이라서, 시험장에서 형태 변형이 잘 보이지 않을 때 특히 유용합니다.

술어논리와 한정자

지금까지의 명제논리는 문장 전체를 하나의 단위로 보는 방식이었습니다. 하지만 수학에서는 x > 3, x + y = 10처럼 변수가 들어간 문장을 자주 다룹니다. 이런 문장은 값이 정해지기 전에는 참과 거짓을 확정할 수 없으므로, 그대로는 명제가 아니라 명제함수 또는 술어로 봅니다.

명제함수와 술어의 의미

P(x) : x > 5

x = 7 이면 참
x = 2 이면 거짓

이처럼 변수에 어떤 값을 넣느냐에 따라 진리값이 달라지는 문장을 명제함수라고 합니다. 즉, 아직은 참과 거짓이 확정되지 않은 상태이고, 값이 들어가야 비로소 명제가 됩니다. 술어논리는 이런 문장을 다루기 위한 논리라고 보면 됩니다.

전체한정자와 존재한정자

∀x P(x) : 모든 x에 대하여 P(x)
∃x P(x) : 어떤 x가 존재하여 P(x)

전체한정자는 대상 전체가 조건을 만족해야 참입니다. 반대로 존재한정자는 하나라도 만족하면 참입니다. 이 둘은 말이 비슷해 보여도 의미 차이가 매우 크기 때문에, 문장을 볼 때 전부를 말하는지 일부를 말하는지 먼저 확인해야 합니다.

예를 들어 모든 학생이 170cm 이상이라고 하면 한 명만 아니어도 거짓입니다. 하지만 어떤 학생은 170cm 이상이라고 하면 한 명만 있어도 참입니다. 이 차이가 한정자 문제의 핵심입니다.

한정자의 부정은 방향이 바뀐다

¬(∀x P(x)) ≡ ∃x ¬P(x)
¬(∃x P(x)) ≡ ∀x ¬P(x)

전체의 부정은 존재로, 존재의 부정은 전체로 바뀝니다. 그리고 안의 명제도 함께 부정됩니다. 이 부분은 시험에서 매우 자주 나오므로 문장으로도 풀어 읽는 연습이 중요합니다. 모든 x가 P라는 말의 부정은, P가 아닌 x가 적어도 하나 존재한다는 뜻입니다.

예를 들어 모든 학생이 과제를 제출했다의 부정은 모든 학생이 제출하지 않았다가 아니라, 제출하지 않은 학생이 적어도 한 명 있다입니다. 한정자 부정에서 가장 흔한 실수는 전체와 존재를 그대로 둔 채 안쪽만 부정하는 경우이므로, 바깥 기호부터 바뀐다고 기억하는 것이 좋습니다.

추론과 시험 포인트

추론은 참이라고 알려진 전제에서 새로운 결론을 끌어내는 과정입니다. 여기서 중요한 것은 결론이 사실인지가 아니라, 전제가 모두 참일 때 그 결론이 반드시 따라오느냐입니다. 즉, 추론의 타당성을 묻는 문제라고 이해해야 합니다.

대표적인 타당한 추론 규칙

긍정논법      : p, p → q ∴ q
부정논법      : p → q, ¬q ∴ ¬p
가언삼단논법  : p → q, q → r ∴ p → r

긍정논법은 조건과 그 조건의 앞부분이 모두 주어졌을 때 뒷부분을 결론으로 내리는 방식입니다. 부정논법은 결론 부분이 거짓이라는 사실을 이용해 원인 부분도 거짓임을 끌어내는 방식입니다. 가언삼단논법은 조건명제를 연쇄적으로 연결하는 형태입니다.

자주 나오는 잘못된 추론

역을 긍정하는 오류 : p → q, q ∴ p
이를 부정하는 오류 : p → q, ¬p ∴ ¬q

비가 오면 길이 젖는다고 해서, 길이 젖었다는 사실만으로 비가 왔다고 단정할 수는 없습니다. 또 비가 오지 않았다고 해서 길이 젖지 않았다고도 할 수 없습니다. 이처럼 조건명제는 한 방향의 약속이라는 점을 놓치면 잘못된 추론에 쉽게 빠집니다.

시험에서는 타당한 추론 규칙을 묻는 문제와 잘못된 추론을 구별하는 문제가 함께 나오는 경우가 많습니다. 따라서 규칙 이름만 외우지 말고, 왜 타당하거나 왜 틀린지 예시 문장으로 설명할 수 있어야 합니다.

또한 추론은 벤 다이어그램처럼 집합 포함 관계로 해석해도 이해가 쉬워집니다. 모든 A가 B에 포함되고 어떤 x가 A에 속한다면 x는 B에도 속한다는 식으로 보면, 문장형 추론과 집합형 추론이 사실 같은 구조라는 점을 자연스럽게 연결할 수 있습니다.

정리

이산수학의 논리 단원은 결국 문장을 참과 거짓의 구조로 바꾸고, 그 관계를 계산하고, 전제로부터 타당한 결론을 이끌어내는 방법을 배우는 과정입니다. 공부 순서는 명제 구분, 기본 진리표, 조건명제 해석, 역·이·대우, 논리적 동치, 한정자, 추론 순서로 잡는 것이 가장 자연스럽습니다.

특히 시험 직전에는 명제인지 아닌지, p → q의 진리값, 대우의 형태, 드모르간 법칙, 한정자의 부정, 긍정논법과 부정논법을 먼저 다시 확인하는 것이 좋습니다. 이 단원은 암기도 필요하지만, 결국 문장을 논리식으로 바꾸는 연습이 핵심입니다.

많이 받는 질문

Q. 조건명제에서 p가 거짓이면 왜 참으로 보나요?
조건명제 p → q는 p가 성립했을 때 q도 따라와야 한다는 약속입니다. 따라서 약속이 깨지는 경우는 p가 참인데 q가 거짓인 경우뿐입니다. p가 거짓이면 약속을 위반했다고 판단할 상황 자체가 없기 때문에 참으로 처리합니다.

Q. 역과 대우는 어떻게 가장 쉽게 구분하나요?
역은 앞뒤를 단순히 바꾸는 것이고, 대우는 앞뒤를 바꾼 뒤 둘 다 부정하는 것입니다. 원래 명제가 p → q라면 역은 q → p, 대우는 ¬q → ¬p입니다. 시험에서는 원래 명제와 대우가 동치라는 점을 함께 기억하는 것이 중요합니다.

Q. 한정자의 부정이 자꾸 헷갈리는데 어떻게 외우면 좋나요?
전체의 부정은 예외 하나를 찾는 것이고, 존재의 부정은 전부 아니라고 말하는 것이라고 기억하면 편합니다. 그래서 ¬(∀x P(x))는 ∃x ¬P(x)가 되고, ¬(∃x P(x))는 ∀x ¬P(x)가 됩니다.