왜 진리표부터 시작해야 하는가

01편에서 $\neg$, $\land$, $\lor$, $\rightarrow$, $\leftrightarrow$ 다섯 기호를 소개했다. 그런데 이 기호들이 정확히 “어떤 상황에서 참, 어떤 상황에서 거짓”인지는 아직 다루지 않았다. 이산수학의 논리 파트에서 첫 번째로 익혀야 할 것은, 이 다섯 연산자가 만드는 결과를 표로 정확히 외우는 것이다. 이 표를 정확히 알아야 04편의 정량자, 05편의 증명 기법에서 “이 명제가 참인지 거짓인지”를 스스로 판정할 수 있다.

쉽게 말하면: 진리표는 논리연산자의 “곱셈구구단”이다. 외워서 바로 쓸 수 있어야 이후 모든 증명·추론이 매끄러워진다.

명제의 정의와 진리값

명제(proposition)는 참(true, T) 또는 거짓(false, F) 중 정확히 하나로 판정되는 문장이다. 이때 참·거짓을 통틀어 진리값(truth value)이라 부른다. “5는 3보다 크다”는 참인 명제이고, “5는 3보다 작다”는 거짓인 명제다. 반면 “5는 큰 수다”는 “크다”의 기준이 사람마다 달라 참·거짓을 하나로 정할 수 없으므로 명제가 아니다.

명제를 매번 문장으로 쓰지 않고 $p$, $q$, $r$ 같은 문자(명제변수, propositional variable)로 표기하는 이유는, 문장의 실제 내용과 무관하게 논리 구조만으로 참·거짓을 분석하기 위해서다.

부정 — 하나뿐인 단항 연산

부정(negation) $\neg p$는 유일하게 명제 하나만 받는 단항연산자(unary operator)다. $p$가 참이면 $\neg p$는 거짓, $p$가 거짓이면 $\neg p$는 참이 된다.

예를 들어 $p$가 “오늘은 월요일이다”이면, $\neg p$는 “오늘은 월요일이 아니다”가 된다. 부정은 문장 앞에 “~이 아니다”를 붙이는 것과 같은 조작이라고 생각하면 직관적이다.

논리곱과 논리합 — 두 명제를 묶는 이항연산

논리곱(conjunction) $p \land q$와 논리합(disjunction) $p \lor q$는 명제 두 개를 받는 이항연산자(binary operator)다. 이 둘의 진리표는 다음과 같다.

$p \land q$는 “$p$이고 $q$이다”라고 읽으며, 표에서 보듯 두 명제가 모두 참일 때만 참이 된다. 예를 들어 $p$가 “3은 홀수다”(참), $q$가 “3은 소수다”(참)이면 $p \land q$는 참이지만, $q$를 “3은 짝수다”(거짓)로 바꾸면 $p \land q$는 거짓이 된다.

$p \lor q$는 “$p$이거나 $q$이다”라고 읽으며, 표에서 보듯 둘 중 하나라도 참이면 참이 된다. 특히 $p$, $q$가 모두 참일 때도 $p \lor q$가 참이라는 점에 주의해야 한다. 이는 일상어에서 흔히 쓰는 “둘 중 하나만”이라는 배타적 의미와는 다르다. 이런 이산수학의 논리합을 포괄적 논리합(inclusive or)이라 부르며, “둘 중 정확히 하나만” 참일 때 참이 되는 연산은 따로 배타적 논리합(exclusive or, XOR)이라 부르고 $p \oplus q$로 표기한다.

쉽게 말하면: 논리곱은 “둘 다 만족해야 통과”, 논리합은 “하나만 만족해도 통과”인 문(gate)이라고 생각하면 된다.

조건명제 — 시험에서 가장 많이 헷갈리는 연산

조건명제(conditional statement) $p \rightarrow q$는 “$p$이면 $q$이다”라고 읽으며, $p$를 가정(hypothesis, 전제), $q$를 결론(conclusion)이라 부른다. 진리표는 다음과 같다.

이 표에서 유일하게 거짓이 되는 경우는 $p$가 참인데 $q$가 거짓인 경우뿐이다. 이 부분이 독학사 시험에서 가장 자주 함정으로 나오는 지점이다. 특히 $p$가 거짓일 때는 $q$가 무엇이든 $p \rightarrow q$ 전체가 참이 된다는 사실이 직관과 어긋나 보이지만, 이는 논리학에서 정한 정의이므로 그대로 받아들여야 한다.

이걸 직관적으로 납득하는 방법은 “지키지 못할 상황이 아니면 거짓말이 아니다”라는 비유다. “비가 오면 우산을 쓴다”($p \rightarrow q$)라는 약속을 예로 들면, 실제로 비가 왔는데($p$ 참) 우산을 안 썼다면($q$ 거짓) 약속을 어긴 것이므로 거짓이다. 하지만 비가 안 왔다면($p$ 거짓), 우산을 쓰든 안 쓰든 애초에 약속을 어길 상황 자체가 발생하지 않으므로, 이 약속은 참으로 취급한다.

조건명제와 관련해 세 가지 변형 명제를 함께 알아 두어야 한다.

이 중 원래 명제와 대우는 항상 같은 진리값을 가진다(등가). 이 성질은 05편(증명 기법)에서 “대우 증명법”의 이론적 근거가 되므로 반드시 기억해 두어야 한다. 반면 역과 이는 원래 명제와 진리값이 같다는 보장이 없다.

쌍조건명제 — 서로 같은 값일 때만 참

쌍조건명제(biconditional statement) $p \leftrightarrow q$는 “$p$일 필요충분조건은 $q$이다” 또는 “$p$이면 그리고 오직 그럴 때만 $q$이다”라고 읽는다.

표를 보면 $p$와 $q$의 진리값이 서로 같을 때만 참이 된다는 것을 알 수 있다. $p \leftrightarrow q$는 사실 $(p \rightarrow q) \land (q \rightarrow p)$와 같은 값을 가지는데, 이는 “$p$이면 $q$“와 “$q$이면 $p$“가 동시에 성립해야 필요충분조건이 된다는 의미와 정확히 일치한다.

복합 명제의 진리표 만들기 — 실제 예제로 검산

지금까지 배운 연산자를 조합한 복합 명제 $(p \lor q) \rightarrow \neg r$의 진리표를 처음부터 끝까지 만들어 보자. 명제변수가 3개($p$, $q$, $r$)이므로 가능한 조합은 $2^3 = 8$가지다.

이 표를 만드는 절차는 다음과 같다.

이렇게 작은 단위부터 차례로 채워 나가면, 아무리 복잡한 복합 명제라도 실수 없이 진리표를 완성할 수 있다.

논리적 등가 — 두 명제식이 “같다”는 것의 의미

두 논리식 $P$와 $Q$가 모든 명제변수 조합에서 항상 같은 진리값을 가지면, 이 둘을 논리적으로 등가(logically equivalent)라고 하고 $P \equiv Q$로 표기한다. 등가인지 확인하는 가장 확실한 방법은 두 식의 진리표를 각각 만들어서 모든 행에서 값이 일치하는지 대조하는 것이다.

예를 들어 $p \rightarrow q$와 $\neg p \lor q$가 등가인지 확인해 보자.

네 행 모두에서 $p \rightarrow q$ 열과 $\neg p \lor q$ 열의 값이 일치한다. 따라서 $p \rightarrow q \equiv \neg p \lor q$가 성립한다. 이 등가식은 조건명제를 논리곱·논리합·부정만으로 바꿔 쓸 수 있게 해 주는 중요한 도구로, 16~17편(부울대수·논리회로)에서 회로를 단순화할 때도 그대로 활용된다.

기본 논리 법칙 — 이름과 함께 외운다

논리식을 변형할 때마다 매번 진리표를 새로 그리는 것은 비효율적이다. 그래서 자주 쓰이는 등가 관계를 법칙으로 정리해 두고, 증명이나 간소화 과정에서 “어느 줄에 어느 법칙을 썼는지” 이름을 붙여 서술한다. 이 서술 방식은 05편(증명 기법)과 16편(부울대수)에서도 그대로 이어진다.

이 중 드모르간 법칙(De Morgan’s law, 영국 수학자 오거스터스 드모르간의 이름에서 따왔다)은 시험에서 가장 자주 등장한다. “$p$이고 $q$이다”의 부정은 “$p$가 아니거나 $q$가 아니다”라는 것인데, 처음 배우면 “$p$가 아니고 $q$가 아니다”로 착각하기 쉽다. 즉 부정을 씌우면서 논리곱과 논리합이 서로 바뀐다는 점이 핵심이다.

드모르간 법칙 검산 — 실제 진리표로 확인

$\neg(p \land q) \equiv \neg p \lor \neg q$가 실제로 성립하는지 진리표로 검산해 보자.

$\neg(p \land q)$ 열과 $\neg p \lor \neg q$ 열이 네 행 모두에서 일치하므로, 이 법칙이 성립함을 확인했다. 같은 방식으로 $\neg(p \lor q) \equiv \neg p \land \neg q$도 검산할 수 있다.

법칙을 적용해 논리식 간소화하기

법칙을 적용해 $\neg(p \land \neg q) \lor (\neg p \land q)$를 더 간단한 형태로 바꿔 보자. 각 줄마다 적용한 법칙 이름을 명시한다.

• 1단계: 드모르간 법칙을 적용해 $\neg(p \land \neg q)$를 $\neg p \lor \neg(\neg q)$로 바꾸었다.

• 2단계: 이중부정법칙을 적용해 $\neg(\neg q)$를 $q$로 바꾸었다.

• 3단계: 결합법칙을 적용해 괄호 묶음을 바꾸었다.

• 4단계: $q \lor (\neg p \land q)$는 흡수법칙(absorption law, $q \lor (\neg p \land q) \equiv q$)에 의해 $q$로 정리된다. 흡수법칙은 “$q$가 이미 참이면 뒤의 논리곱 항이 무엇이든 전체 논리합은 $q$ 하나로 결정된다”는 성질에서 나온다.

결국 $\neg(p \land \neg q) \lor (\neg p \land q) \equiv \neg p \lor q$까지 간소화된다. 이렇게 각 줄에 적용한 법칙 이름을 명시하는 서술 방식은 독학사 서술형·객관식 모두에서 채점자(또는 스스로 검산하는 사람)가 논리 흐름을 검증할 수 있게 해 주므로 매우 중요하다.

자주 틀리는 점

• 조건명제 $p \rightarrow q$에서 $p$가 거짓이면 전체가 거짓이라고 착각하는 실수: 실제로는 $p$가 거짓이면 $q$와 무관하게 전체가 참이 된다. 거짓이 되는 경우는 오직 $p$가 참, $q$가 거짓일 때뿐이다.
• 드모르간 법칙을 적용하며 논리곱·논리합을 바꾸지 않는 실수: $\neg(p \land q)$를 $\neg p \land \neg q$로 잘못 바꾸는 경우가 많다. 부정을 씌우면 반드시 연산자도 함께 바뀐다.
• 역·이·대우를 원래 명제와 같은 값으로 착각하는 실수: 원래 명제와 같은 진리값을 갖는 것은 대우뿐이며, 역과 이는 원래 명제와 다를 수 있다.
• 포괄적 논리합과 배타적 논리합을 혼동하는 실수: $p \lor q$는 둘 다 참이어도 참이지만, $p \oplus q$(XOR)는 둘 다 참이면 거짓이 된다.

핵심 정리

• 진리표는 명제변수 $n$개에 대해 $2^n$가지 조합을 모두 나열해 만들며, 복합 명제는 작은 단위 연산부터 순서대로 채운다.
• $p \rightarrow q$가 거짓이 되는 경우는 $p$가 참, $q$가 거짓인 경우 하나뿐이다. 원래 명제와 진리값이 항상 같은 것은 대우 $\neg q \rightarrow \neg p$뿐이다.
• 두 논리식이 모든 조합에서 같은 진리값을 가지면 논리적으로 등가($\equiv$)라 하며, 진리표로 직접 대조해 판정할 수 있다.
• 드모르간 법칙은 부정을 씌우면서 논리곱과 논리합이 서로 바뀐다는 것이 핵심이며, 논리식 간소화의 뼈대가 되는 법칙이다.
• 논리식 간소화는 한 줄씩 적용한 법칙의 이름을 명시하며 진행해야 검산과 서술이 가능하다.

마무리 복습

참고 자료

• 국가평생교육진흥원 독학학위제 - 이산수학 출제기준  — 명제·논리연산 항목이 출제기준에서 차지하는 위치를 확인할 수 있는 공식 자료.