명제와 논리 연산

게시판의 접근 조건을 "로그인했고 관리자이거나 작성자이면 글을 고칠 수 있다"라고 적었다고 해 봅시다. 이 문장은 "로그인했고, 관리자이거나 작성자이면"으로도, "로그인한 관리자이거나, 작성자이면"으로도 읽을 수 있습니다. 두 해석은 로그인하지 않은 작성자를 통과시키느냐에서 갈립니다. 일상 언어로 적은 조건은 이렇게 여러 뜻으로 읽힐 수 있으므로, 프로그램으로 옮기기 전에 정확한 모양으로 적어야 합니다. 이 글에서는 참과 거짓을 따지는 문장을 기호로 적고, 그 문장들을 연결하는 논리 연산과 진리표를 익힙니다.

참이나 거짓을 정할 수 있는 문장

참인지 거짓인지를 분명하게 정할 수 있는 문장을 명제(proposition)라고 합니다. "7은 소수다"는 참인 명제이고, "7은 짝수다"는 거짓인 명제입니다. 거짓인 문장도 참과 거짓을 정할 수 있으므로 명제입니다. 반면 "문을 닫아라" 같은 명령이나 "이 프로그램은 멋지다"처럼 기준이 정해지지 않은 평가는 참과 거짓을 정할 수 없으므로 명제로 다루지 않습니다.

"x는 짝수다"처럼 변수가 들어 있는 문장은 x에 무엇을 넣느냐에 따라 참이 되기도 하고 거짓이 되기도 합니다. 이런 문장은 x의 값을 정하기 전까지는 명제가 아니며, 다음 글에서 술어로 따로 다룹니다. 이 글에서는 P, Q처럼 이미 참이나 거짓이 정해진 명제들을 연결하는 방법을 봅니다.

명제를 잇는 논리 연산

명제 P의 부정 $\neg P$는 P의 참과 거짓을 뒤집은 명제입니다. 두 명제를 잇는 연산으로는 논리곱(and) $P\land Q$와 논리합(or) $P\lor Q$가 있습니다. 논리곱은 두 명제가 모두 참일 때만 참이고, 논리합은 적어도 하나가 참이면 참입니다. 논리합은 둘 다 참인 경우도 참이라는 점에서 일상 언어의 "또는"과 다를 수 있습니다. "커피 또는 차를 드립니다"는 보통 둘 중 하나만이라는 뜻인데, 이렇게 둘 중 정확히 하나만 참일 때 참인 연산은 배타적 논리합(exclusive or) $P\oplus Q$라 하여 따로 구분합니다.

명제의 참과 거짓을 진릿값이라 하고, 가능한 모든 진릿값의 조합에 대해 식의 진릿값을 적은 표를 진리표(truth table)라고 합니다. 명제가 두 개이면 조합은 참·참, 참·거짓, 거짓·참, 거짓·거짓의 네 가지입니다. Python의 and, or, not은 논리곱, 논리합, 부정과 같고, 두 진릿값이 다른지를 묻는 !=는 배타적 논리합과 같습니다. 아래 코드는 이 연산들과 뒤에서 설명할 조건명제의 진리표를 만듭니다. 표에서 1은 참, 0은 거짓입니다.

from itertools import product


def implies(p, q):
    return (not p) or q


print("P Q  P∧Q P∨Q P⊕Q P→Q P↔Q")
for p, q in product([True, False], repeat=2):
    row = [p and q, p or q, p != q, implies(p, q), p == q]
    print(int(p), int(q), " ", "   ".join(str(int(v)) for v in row))

P Q  P∧Q P∨Q P⊕Q P→Q P↔Q
1 1   1   1   0   1   1
1 0   0   1   1   0   0
0 1   0   1   1   1   0
0 0   0   0   0   1   1

product([True, False], repeat=2)는 참과 거짓으로 만들 수 있는 두 값의 조합 네 가지를 차례로 내놓습니다. int(True)는 1, int(False)는 0입니다.

조건명제는 약속처럼 읽는다

"P이면 Q이다"를 조건명제(conditional) $P\to Q$라 하고, P를 가정, Q를 결론이라고 부릅니다. 진리표의 $P\to Q$ 열에서 거짓인 칸은 P가 참이고 Q가 거짓인 한 칸뿐입니다. 처음 보면 P가 거짓일 때 늘 참인 것이 이상해 보이는데, 조건명제를 약속으로 읽으면 이해하기 쉽습니다. "비가 오면 우산을 가져오겠다"는 약속은 비가 왔는데 우산을 안 가져왔을 때만 깨집니다. 비가 오지 않은 날에는 우산을 가져오든 안 가져오든 약속을 어긴 것이 아니므로, 조건명제는 참으로 둡니다.

조건명제는 P가 Q의 원인이라는 뜻이 아니라는 점도 알아 두어야 합니다. "2 + 2 = 4이면 서울은 한국의 수도다"는 두 부분 사이에 아무 관계가 없지만, P와 Q가 모두 참이므로 조건명제로서는 참입니다. 논리에서 조건명제는 오직 진리표로만 뜻이 정해집니다.

$P\to Q$가 참이면, P가 성립하는 것만으로 Q가 성립하기에 충분하므로 P를 Q의 충분조건이라 하고, Q가 성립하지 않으면 P도 성립할 수 없으므로 Q를 P의 필요조건이라고 합니다. "4의 배수이면 짝수다"에서 4의 배수라는 것은 짝수이기에 충분하지만, 짝수라고 해서 4의 배수인 것은 아닙니다. 6이 그 예입니다.

조건명제 $P\to Q$에서 가정과 결론의 자리를 바꾸거나 부정해 만든 명제들에도 이름이 있습니다. $Q\to P$를 역(converse), $\neg P\to\neg Q$를 이(inverse), $\neg Q\to\neg P$를 대우(contrapositive)라고 합니다. 원래 명제와 대우는 진릿값이 늘 같지만, 역과 이는 원래 명제와 진릿값이 다를 수 있습니다. "4의 배수이면 짝수다"는 참이고, 대우인 "짝수가 아니면 4의 배수가 아니다"도 참이지만, 역인 "짝수이면 4의 배수다"는 6에서 거짓입니다. 두 방향의 조건명제가 모두 참일 때는 $P\leftrightarrow Q$로 쓰고 "P일 때 그리고 그때에만 Q"라고 읽습니다.

동치는 모든 줄에서 같아야 한다

두 식이 가능한 모든 진릿값의 조합에서 같은 진릿값을 가지면 두 식은 논리적으로 동치(logically equivalent)라 하고 ≡로 씁니다. 진리표를 보면 $P\to Q$는 $\neg P\lor Q$와 네 줄 모두에서 같으므로 동치이고, 앞의 implies 함수가 그렇게 정의된 것도 이 때문입니다. 부정이 논리곱과 논리합을 바꾸는 드모르간 법칙 $\neg(P\land Q)\equiv\neg P\lor\neg Q$와 $\neg(P\lor Q)\equiv\neg P\land\neg Q$도 자주 씁니다. "둘 다 참"이 아니라는 것은 "적어도 하나가 거짓"이라는 뜻이기 때문입니다.

동치인지는 모든 조합을 계산해 비교하면 확인할 수 있습니다. 아래의 equivalent는 명제의 개수만큼 모든 조합을 만들어 두 식의 값을 비교합니다. 처음의 게시판 조건도 확인해 보겠습니다. L을 로그인, A를 관리자, W를 작성자라고 하면, 첫 해석은 $L\land(A\lor W)$, 둘째 해석은 $(L\land A)\lor W$입니다.

from itertools import product


def implies(p, q):
    return (not p) or q


def equivalent(f, g, count):
    return all(f(*values) == g(*values) for values in product([True, False], repeat=count))


print(equivalent(lambda p, q: implies(p, q), lambda p, q: implies(not q, not p), 2))
print(equivalent(lambda p, q: implies(p, q), lambda p, q: implies(q, p), 2))
print(equivalent(lambda p, q: not (p and q), lambda p, q: (not p) or (not q), 2))
print(equivalent(lambda l, a, w: l and (a or w), lambda l, a, w: (l and a) or w, 3))
L, A, W = False, False, True
print(L and A or W, L and (A or W))

True
False
True
False
True False

lambda p, q: ...는 이름 없는 짧은 함수이고, f(*values)는 튜플 values의 값들을 각각의 인자로 넘깁니다. 원래 명제와 대우는 동치이고 역은 동치가 아니며, 드모르간 법칙도 성립합니다. 게시판 조건의 두 해석은 동치가 아닙니다. 로그인하지 않은 작성자, 곧 L이 거짓, A가 거짓, W가 참인 경우에 첫 해석은 거짓이지만 둘째 해석은 참이기 때문입니다.

마지막 줄은 Python의 연산자 우선순위와 관련이 있습니다. Python에서 and는 or보다 먼저 계산되므로, 괄호 없이 쓴 L and A or W는 (L and A) or W, 곧 둘째 해석으로 계산되어 로그인하지 않은 작성자에게도 참이 나옵니다. 첫 해석을 뜻했다면 L and (A or W)처럼 괄호를 써야 합니다. 조건을 코드로 옮길 때 괄호를 빠뜨리면 오류 없이 다른 뜻의 조건이 만들어지므로, 우선순위를 외워 두기보다 뜻이 갈릴 수 있는 곳에는 괄호를 쓰는 편이 안전합니다.

항진명제와 모순명제

모든 줄에서 참인 식을 항진명제(tautology), 모든 줄에서 거짓인 식을 모순명제(contradiction)라고 합니다. $P\lor\neg P$는 P가 무엇이든 참이므로 항진명제이고, $P\land\neg P$는 늘 거짓이므로 모순명제입니다. 두 식이 동치라는 것은 $P\leftrightarrow Q$ 형태로 이은 식이 항진명제라는 것과 같은 말입니다.

정리

• 명제는 참과 거짓을 분명하게 정할 수 있는 문장입니다. 변수가 들어 있어 값에 따라 진릿값이 바뀌는 문장은 술어로 따로 다룹니다.
• 부정은 진릿값을 뒤집고, 논리곱은 둘 다 참일 때, 논리합은 적어도 하나가 참일 때 참입니다. 둘 중 정확히 하나만 참일 때는 배타적 논리합입니다.
• 조건명제 $P\to Q$는 P가 참이고 Q가 거짓일 때만 거짓이며, 원인과 결과의 관계를 뜻하지 않습니다. 원래 명제와 대우는 동치이지만 역과 이는 그렇지 않습니다.
• 두 식이 모든 진릿값의 조합에서 같으면 논리적으로 동치이고, 모든 조합을 계산해 확인할 수 있습니다. 동치가 아님은 값이 다른 조합 하나로 보일 수 있습니다.
• 모든 줄에서 참인 식은 항진명제, 모든 줄에서 거짓인 식은 모순명제입니다.

연습 문제

1. 드모르간 법칙 적용하기

$\neg(P\lor Q)$를 부정과 논리곱만으로 나타내고, P가 참, Q가 거짓일 때 두 식의 값을 계산하세요.

2. 대우와 역

"n이 6의 배수이면 3의 배수다"의 대우와 역을 쓰고, 각각 참인지 거짓인지 판단하세요.

3. 두 해석이 갈리는 경우

본문의 게시판 조건에서 $L\land(A\lor W)$와 $(L\land A)\lor W$가 서로 다른 값을 내는 L, A, W의 조합을 모두 찾으세요.

괄호가 헷갈리면 작은 진리표부터 만들어 보세요. 변수가 들어 있는 문장과 "모든", "어떤"을 다루는 방법은 술어와 양화사에서 이어집니다.