1강. 명제논리

수학의 문장은 참이나 거짓이 분명해야 합니다. 이 강에서는 '그리고', '또는', '아니다', '이면' 같은 말을 기호로 정확히 정하고, 진리표로 문장의 참거짓을 기계적으로 계산하는 법을 익힙니다. 고등학교에서 배운 명제와 조건문을 조금 더 정확히 다시 보는 강이고, 컴퓨터의 논리 회로와 프로그래밍의 조건문이 바로 이 규칙으로 움직입니다.

명제

참인지 거짓인지가 정해지는 문장을 명제(proposition)라 합니다. 참과 거짓을 진릿값(truth value)이라 하고 각각 $T$ , $F$ 로 씁니다.

“ $2 + 3 = 5$ ”는 참인 명제입니다.
“ $7$ 은 짝수입니다”는 거짓인 명제입니다.
“ $x + 1 = 3$ ”은 $x$ 의 값에 따라 참과 거짓이 달라지므로 명제가 아닙니다. $x$ 의 값을 정하면 명제가 됩니다.
“문을 닫아라”는 참이나 거짓을 말할 수 없으므로 명제가 아닙니다.

명제를 가리키는 문자로 $p$ , $q$ , $r$ 을 씁니다. 이런 문자를 명제 변수라 합니다.

연결사

명제를 이어 붙여 새 명제를 만드는 기호를 연결사(connective)라 합니다. 다섯 개를 씁니다.

기호	이름	읽는 법	참이 되는 때
$\neg p$	부정	$p$ 가 아니다	$p$ 가 거짓일 때
$p \land q$	논리곱	$p$ 그리고 $q$	둘 다 참일 때
$p \lor q$	논리합	$p$ 또는 $q$	적어도 하나가 참일 때
$p \to q$	조건문	$p$ 이면 $q$ 입니다	$p$ 가 참이고 $q$ 가 거짓인 경우만 빼고 모두
$p \leftrightarrow q$	쌍조건문	$p$ 일 때, 그리고 그때만 $q$ 입니다	두 진릿값이 같을 때

논리합 $p \lor q$ 는 둘 다 참일 때도 참입니다. 일상의 “또는”이 둘 중 하나만을 뜻할 때가 있는 것과 다릅니다.

진리표

변수가 가질 수 있는 진릿값의 모든 조합에 대해 식의 값을 적은 표를 진리표(truth table)라 합니다. 변수가 $n$ 개면 조합은 $2^n$ 개입니다. 한 변수마다 $T$ , $F$ 두 가지가 있기 때문입니다.

$p$	$q$	$\neg p$	$p \land q$	$p \lor q$	$p \to q$	$p \leftrightarrow q$
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

조건문이 낯선 이유

$p \to q$ 에서 $p$ 를 가정, $q$ 를 결론이라 합니다. 가정이 거짓이면 결론이 무엇이든 조건문은 참입니다. “시험에서 만점을 받으면 선물을 줍니다”는 약속을 생각합니다. 만점을 받았는데 선물을 주지 않았을 때만 약속을 어긴 것입니다. 만점을 받지 못했다면 선물을 주든 주지 않든 약속을 어기지 않았습니다. 그러므로 조건문이 거짓이 되는 행은 $p$ 가 참이고 $q$ 가 거짓인 행 하나뿐입니다.

연산 순서

괄호가 없으면 $\neg$ 을 가장 먼저, 그다음 $\land$ , $\lor$ , $\to$ , $\leftrightarrow$ 의 순서로 묶습니다. 예를 들어 $\neg p \lor q \to r$ 은 $((\neg p) \lor q) \to r$ 입니다. 헷갈릴 때는 괄호를 씁니다.

역, 이, 대우

조건문 $p \to q$ 에서 세 가지 조건문을 더 만듭니다.

이름	꼴
역	$q \to p$
이	$\neg p \to \neg q$
대우	$\neg q \to \neg p$

조건문과 그 대우(contrapositive)는 진릿값이 항상 같습니다. $\neg q \to \neg p$ 가 거짓인 때는 $\neg q$ 가 참이고 $\neg p$ 가 거짓인 때, 곧 $q$ 가 거짓이고 $p$ 가 참인 때입니다. 이는 $p \to q$ 가 거짓인 때와 같습니다. 그러므로 어떤 조건문을 증명하기 어려우면 대우를 증명해도 됩니다.

조건문과 그 역(converse)은 진릿값이 같지 않을 수 있습니다. “ $n$ 이 4의 배수이면 $n$ 은 짝수입니다”는 참이지만, 역인 “ $n$ 이 짝수이면 $n$ 은 4의 배수입니다”는 $n = 2$ 에서 거짓입니다.

항진명제와 모순명제

변수에 어떤 값을 넣어도 참인 식을 항진명제(tautology), 어떤 값을 넣어도 거짓인 식을 모순명제(contradiction)라 합니다. 진리표의 마지막 열이 모두 $T$ 이면 항진명제이고, 모두 $F$ 이면 모순명제입니다.

$p \lor \neg p$ 는 항진명제입니다. $p$ 가 참이면 앞쪽이, 거짓이면 뒤쪽이 참입니다.
$p \land \neg p$ 는 모순명제입니다. $p$ 와 $\neg p$ 가 함께 참일 수 없습니다.

논리적 동치

두 식 $A$ , $B$ 의 진릿값이 변수의 모든 조합에서 같을 때 두 식은 논리적으로 동치(logically equivalent)라 하고 $A \equiv B$ 로 씁니다. 이는 $A \leftrightarrow B$ 가 항진명제라는 말과 같습니다. 동치인 식은 서로 바꿔 쓸 수 있습니다.

자주 쓰는 동치는 다음과 같습니다.

이름	동치
이중 부정	$\neg(\neg p) \equiv p$
교환법칙	$p \land q \equiv q \land p$ , $\quad p \lor q \equiv q \lor p$
결합법칙	$(p \land q) \land r \equiv p \land (q \land r)$ , $\quad (p \lor q) \lor r \equiv p \lor (q \lor r)$
분배법칙	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ , $\quad p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
드모르간 법칙	$\neg(p \land q) \equiv \neg p \lor \neg q$ , $\quad \neg(p \lor q) \equiv \neg p \land \neg q$
조건문	$p \to q \equiv \neg p \lor q$
대우	$p \to q \equiv \neg q \to \neg p$
쌍조건문	$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$

진리표로 확인하기

드모르간 법칙의 첫 식을 확인합니다. 두 식의 열이 네 행 모두에서 같습니다. 그러므로 두 식은 동치입니다.

$p$	$q$	$p \land q$	$\neg(p \land q)$	$\neg p$	$\neg q$	$\neg p \lor \neg q$
T	T	T	F	F	F	F
T	F	F	T	F	T	T
F	T	F	T	T	F	T
F	F	F	T	T	T	T

아래 위젯의 식은 두 식을 $\leftrightarrow$ 로 이은 것입니다. 두 식이 동치이면 모든 행이 $T$ 가 됩니다. 식을 고쳐 다른 동치도 확인할 수 있습니다.

동치로 식 바꾸기

진리표를 그리지 않고 알려진 동치를 차례로 적용해 식을 바꿀 수도 있습니다. $\neg(p \to q)$ 를 간단히 합니다.

\neg(p \to q) \equiv \neg(\neg p \lor q) \equiv \neg(\neg p) \land \neg q \equiv p \land \neg q

첫 단계는 조건문의 동치, 둘째 단계는 드모르간 법칙, 셋째 단계는 이중 부정입니다. 그러므로 “ $p$ 이면 $q$ 다”의 부정은 “ $p$ 인데 $q$ 가 아닙니다”가 됩니다. “ $p$ 이면 $q$ 가 아닙니다”가 아니라는 점에 주의합니다.

쓰이는 곳. 프로그래밍의 조건문과 디지털 회로의 논리 게이트(AND, OR, NOT)가 이 강의 연결사이고, SAT 문제와 프로그램 검증, 데이터베이스 질의도 명제논리 위에 있습니다.

문제

문제 1 · 확인 문제

$p \to q$ 가 거짓이 되는 $(p, q)$ 의 조합은 몇 개일까요?

힌트 1

진리표에서 조건문이 거짓인 행을 셉니다.

힌트 2

$p$ 가 참이고 $q$ 가 거짓인 경우를 찾습니다.

정답

풀이

$p \to q$ 는 $p$ 가 참이고 $q$ 가 거짓일 때만 거짓입니다. 그러므로 조합은 $(T, F)$ 하나뿐입니다.

문제 2 · 확인 문제

$(p \lor q) \land \neg p$ 의 진리표를 완성합니다. 빈칸에는 T나 F를 적습니다.

$p$	$q$	$(p \lor q) \land \neg p$
T	T	[?]
T	F	[?]
F	T	[?]
F	F	[?]

힌트 1

$p \lor q$ 의 열과 $\neg p$ 의 열을 따로 구한 뒤, 두 열이 모두 T인 행을 찾습니다.

정답

F
F
T
F

풀이

$\neg p$ 는 $p$ 가 거짓인 아래 두 행에서만 참입니다. 그 두 행 가운데 $p \lor q$ 가 참인 행은 $q$ 가 참인 셋째 행뿐입니다. 그러므로 열은 위에서부터 F, F, T, F다. 이 식은 $\neg p \land q$ 와 동치입니다.

문제 3 · 확인 문제

$p \to q$ 와 논리적으로 동치인 것은?

$q \to p$
$\neg q \to \neg p$
$\neg p \to \neg q$
$p \land \neg q$

힌트 1

역, 이, 대우 가운데 원래 조건문과 진릿값이 항상 같은 것은 하나입니다.

정답

풀이

2번은 대우이므로 $p \to q$ 와 동치입니다. 1번은 역, 3번은 이여서 $p$ 가 거짓이고 $q$ 가 참일 때 값이 달라집니다. 4번은 $p \to q$ 의 부정입니다.

문제 4 · 확인 문제

항진명제를 모두 고릅니다.

$p \lor \neg p$
$(p \land q) \to p$
$p \to (p \land q)$
$p \land \neg p$

힌트 1

조건문은 가정이 참이고 결론이 거짓인 경우가 있는지만 살핍니다.

정답

1,2

풀이

1번은 항상 참입니다. 2번은 가정 $p \land q$ 가 참이면 $p$ 도 참이므로 거짓이 될 수 없습니다. 3번은 $p$ 가 참이고 $q$ 가 거짓일 때 거짓입니다. 4번은 모순명제입니다. 그러므로 답은 1번과 2번입니다.

문제 5 · 확인 문제

변수가 $p$ , $q$ , $r$ 셋일 때, $(p \to q) \land (q \to r)$ 이 참이 되는 진릿값 조합은 8개 가운데 몇 개일까요?

힌트 1

$p \to q$ 가 참이려면 “ $p$ 가 참이면 $q$ 도 참”이어야 합니다. $q \to r$ 도 마찬가지입니다.

정답

풀이

두 조건문이 모두 참이려면, 참인 변수 뒤의 변수도 참이어야 합니다. 곧 $(p, q, r)$ 이 F에서 T로 한 번만 바뀌거나 바뀌지 않는 꼴이어야 합니다. 그런 조합은 $(F,F,F)$ , $(F,F,T)$ , $(F,T,T)$ , $(T,T,T)$ 의 4개입니다.

문제 6

$p \to q \equiv \neg p \lor q$ 임을 진리표로 보입니다. 그리고 이 동치와 드모르간 법칙을 써서 $\neg(p \to q) \equiv p \land \neg q$ 임을 보입니다.

힌트 1

두 식의 열을 나란히 적고 네 행을 비교합니다.

풀이

$p$	$q$	$p \to q$	$\neg p$	$\neg p \lor q$
T	T	T	F	T
T	F	F	F	F
F	T	T	T	T
F	F	T	T	T

셋째 열과 다섯째 열이 네 행 모두에서 같습니다. 그러므로 $p \to q \equiv \neg p \lor q$ 입니다.

이 동치를 쓰면 $\neg(p \to q) \equiv \neg(\neg p \lor q)$ 입니다. 드모르간 법칙으로 $\neg(\neg p \lor q) \equiv \neg(\neg p) \land \neg q$ 이고, 이중 부정으로 $\neg(\neg p) \equiv p$ 입니다. 그러므로 $\neg(p \to q) \equiv p \land \neg q$ 가 됩니다.