Lesson 2 of 20

진리표 — 모든 경우를 빠짐없이 적는 표

그리고 · 또는 · 아니다

명제 하나로는 할 수 있는 일이 별로 없습니다. 재미는 명제를 붙일 때 시작돼요.

이름	기호	파이썬	참이 되는 때
부정	¬p	`not p`	p 가 거짓일 때
논리곱 (그리고)	p ∧ q	`p and q`	둘 다 참일 때
논리합 (또는)	p ∨ q	`p or q`	하나라도 참일 때
배타적 논리합	p ⊕ q	`p != q`	둘이 서로 다를 때

여기서 꼭 짚고 갈 것 하나. 수학의 또는(∨)은 일상어와 다릅니다. "커피 또는 홍차"라고 하면 보통 둘 중 하나만 고르라는 뜻이지만, 논리의 ∨는 둘 다여도 참입니다. 둘 중 하나만 참일 때만 참인 것은 따로 이름이 있어요 — 배타적 논리합 ⊕입니다.

High school모든 경우를 빠짐없이 적는 표

진리표는 가장 단순하고 가장 확실한 도구입니다.

경우를 전부 적으면 — 틀릴 수가 없다

세 가지 연산

기호	이름	참일 때
∧	그리고 (AND)	둘 다 참
∨	또는 (OR)	하나라도 참
¬	아니다 (NOT)	반대

일상어 세 마디가 논리의 전부다

경우의 수

변수 수	줄 수
1	2
2	4
3	8
n	2ⁿ

변수 하나가 늘 때마다 두 배 — 금세 감당이 안 된다

변수 20개면 백만 줄입니다. 그래서 4강의 부울대수로 계산해서 줄이는 거예요.

비유 — 자물쇠 다 열어 보기

자리 수	경우
3자리	1,000 — 해 볼 만하다
10자리	100억 — 불가능

"전부 해 보기" 는 작을 때만 통한다 — 이 강의 전체의 주제다

경우가 4개뿐이니 전부 적어 볼 수 있습니다 — 이것이 진리표입니다.

Python Runs in your browser

# and · or · not · != (XOR) 를 모든 경우에 대해 찍어 봅니다
print(" p      q     | and    or     xor")
print("-" * 42)
for p in (True, False):
    for q in (True, False):
        print(f"{p!s:<7}{q!s:<7}| {p and q!s:<7}{p or q!s:<7}{p != q}")

진리표란

진리표(truth table)는 명제들이 가질 수 있는 모든 참·거짓 조합과 그 결과를 적은 표입니다. 명제가 n개면 줄 수는 2ⁿ개예요. 1개면 2줄, 2개면 4줄, 3개면 8줄, 10개면 1024줄.

이 "2의 거듭제곱"은 이 강의 내내 따라다닙니다. 컴퓨터가 비트 n개로 2ⁿ가지를 표현하는 것과 정확히 같은 이유예요.

High school진리표는 '완전 탐색' 입니다

note 의 이 표현이 알고리즘과 이어집니다.

전부 해 보는 방법 — 확실하지만 비싸다

두 방법의 성격

방법	확실성	비용
진리표	100% ✔	2ⁿ ⚠
부울대수	100% ✔	대개 훨씬 적다

같은 답을 싸게 얻는 것이 4강의 목적이다

그런데 진리표에도 값어치가 있습니다

쓰임	설명
확인용	계산한 결과가 맞는지
이해용	왜 그런지 눈으로 본다
작은 문제	변수 3~4개면 가장 빠르다

작은 문제에서는 단순한 방법이 이긴다 — 자주 나오는 교훈

비유 — 계산기와 손계산

문제	빠른 방법
2 + 3	암산
3847 × 2913	계산기

규모가 방법을 정한다 — 늘 그렇다

SAT 문제로 이어집니다

"이 논리식을 참으로 만드는 값이 있나?" 를 SAT 라고 합니다.

사실	—
진리표로 풀면	2ⁿ
더 빠른 일반 방법	아직 모른다 ⭐

이게 그 유명한 P vs NP 문제의 중심에 있다

같은 뜻인 두 식 — 동치

겉모습이 달라도 진리표가 완전히 같으면 두 식은 같은 명제입니다. 이것을 논리적 동치(logically equivalent)라 하고 ≡로 씁니다.

가장 유명한 동치가 드모르간 법칙(De Morgan's laws)입니다.

¬(p ∧ q) ≡ ¬p ∨ ¬q — "둘 다는 아니다" = "하나는 아니거나 다른 하나가 아니다"
¬(p ∨ q) ≡ ¬p ∧ ¬q — "둘 다 아니다" = "이것도 아니고 저것도 아니다"

말로 들으면 헷갈리지만 진리표로 확인하면 1초입니다.

네 줄이 모두 같으면 증명 끝입니다. 이것이 '진리표에 의한 증명'이에요.

Python Runs in your browser

# 드모르간 법칙을 네 경우 모두에서 확인합니다
print("p      q      | ¬(p∧q)  ¬p∨¬q  | 같은가")
print("-" * 48)
모두_같음 = True
for p in (True, False):
    for q in (True, False):
        왼쪽 = not (p and q)
        오른쪽 = (not p) or (not q)
        모두_같음 = 모두_같음 and (왼쪽 == 오른쪽)
        print(f"{p!s:<7}{q!s:<7}| {왼쪽!s:<8}{오른쪽!s:<7}| {왼쪽 == 오른쪽}")
print()
print("네 경우 모두 같은가? →", 모두_같음, "→ 동치입니다 (≡)")

High school코드에서 자주 나는 실수

note 의 경고를 실전 코드로 봅시다.

가장 흔한 것 — 드모르간 법칙을 잘못 쓰는 것

법칙부터

식	같은 식
¬(A ∧ B)	¬A ∨ ¬B
¬(A ∨ B)	¬A ∧ ¬B

부정이 안으로 들어가면 ∧ 와 ∨ 가 뒤바뀐다

틀리는 예

# 의도: "A 이고 B" 가 아닐 때
if not A and not B:      # ⚠ 틀렸다
if not (A and B):        # ✔ 맞다

A	B	not(A and B)	not A and not B
T	F	참	거짓 ⚠

한 줄이 다른 조건이 된다 — 진리표로 확인하면 바로 보인다

일상어로 확인해 보면

말	뜻
"둘 다 오지는 않았다"	한 명은 왔을 수 있다
"둘 다 안 왔다"	아무도 안 왔다

일상어에서도 부정의 위치가 뜻을 바꾼다

또 하나 — 단축 평가

if x is not None and x.value > 0:   # ✔ 순서가 중요

파이썬은 왼쪽이 거짓이면 오른쪽을 안 봅니다. 순서를 바꾸면 오류가 나요.

논리적으로는 같은데 실행은 다르다 — 코드의 특수 사정

항상 참, 항상 거짓

항진명제(tautology) — 어떤 경우에도 참. 예: p ∨ ¬p ("비가 오거나 안 오거나")
모순명제(contradiction) — 어떤 경우에도 거짓. 예: p ∧ ¬p

프로그램에서 조건이 항진명제가 되면 그 if는 있으나 마나이고, 모순명제가 되면 그 안의 코드는 영원히 실행되지 않습니다. 컴파일러가 "이 코드는 도달할 수 없습니다"라고 경고하는 것이 바로 이 계산의 결과예요.

식을 하나 더 만들어 넣어 보세요.

Python Runs in your browser

def 항진인가(식, 이름):
    결과 = [식(p, q) for p in (True, False) for q in (True, False)]
    if all(결과):   판정 = "항진명제 — 언제나 참"
    elif not any(결과): 판정 = "모순명제 — 언제나 거짓"
    else:           판정 = "그때그때 다름"
    print(f"{이름:<22} {결과}  →  {판정}")

항진인가(lambda p, q: p or not p,          "p ∨ ¬p")
항진인가(lambda p, q: p and not p,         "p ∧ ¬p")
항진인가(lambda p, q: (p and q) or not q,  "(p ∧ q) ∨ ¬q")
항진인가(lambda p, q: p and q,             "p ∧ q")

High school꼭 기억하세요

2강의 정리를 다른 과목과 이어 봅시다.

AND · OR · NOT 셋이면 모든 논리를 만든다

이 사실이 얼마나 큰가

분야	어떻게 쓰이나
회로	게이트 셋으로 CPU (`/ca` 4강)
검색	AND · OR 검색
SQL	WHERE 절
조건문	모든 프로그램

1854년 불(Boole)의 발상이 현대 컴퓨터의 토대가 되었다

그런데 셋도 필요 없습니다

NAND 하나로 셋을 전부 만들 수 있어요.

만들 것	NAND 몇 개
NOT	1개
AND	2개
OR	3개

부품 한 종류로 세상의 모든 계산을 한다 — /ca 4강

드모르간을 기억하는 법

부정이 괄호를 넘어가면 ∧↔∨ 가 뒤집힌다

말로	—
"둘 다는 아니다" = "하나는 아니거나 다른 하나가 아니다"	—

일상어로 읽어 보면 자연스럽습니다. 외우지 말고 말로 확인하세요.

🤔 Check yourself

p가 참, q가 거짓일 때 p ∨ q 와 p ⊕ q 의 값은?

🤔 Check yourself

명제 3개로 만든 진리표의 줄 수는?

Answer 각 명제가 참·거짓 두 가지이므로 2 × 2 × 2 = 8줄입니다. 일반적으로 명제 n개면 2ⁿ줄이에요 — 비트 n개가 2ⁿ가지를 나타내는 것과 같은 계산입니다.

🤔 Check yourself

not (재고있음 and 결제완료) 와 같은 뜻인 것은?