술어와 양화사

"모든 사용자에게 추천할 상품이 있다"와 "모든 사용자가 좋아하는 상품이 있다"는 비슷해 보이지만 전혀 다른 요구 사항입니다. 앞의 것은 사용자마다 각자 맞는 상품이 하나씩 있으면 되지만, 뒤의 것은 한 상품을 모든 사용자가 좋아해야 합니다. 이런 차이는 "모든"과 "어떤"이 어떤 순서로 나오느냐에서 생깁니다. 이 글에서는 명제와 논리 연산에 변수를 더해, 변수의 범위와 "모든", "어떤"을 정확하게 적는 방법을 익힙니다.

술어와 정의역

"x는 짝수다"처럼 변수가 들어 있어서 변수에 값을 넣어야 참과 거짓이 정해지는 문장을 술어(predicate)라 하고 $P(x)$처럼 적습니다. x에 4를 넣은 $P(4)$는 참인 명제이고, 5를 넣은 $P(5)$는 거짓인 명제입니다. 변수에 넣을 수 있는 값들의 집합을 정의역(domain)이라고 합니다. 같은 술어라도 정의역이 정수인지, 자연수인지, 어떤 사용자 목록인지에 따라 뒤에서 볼 "모든 x"가 가리키는 대상이 달라지므로, 술어를 쓸 때는 정의역부터 정해야 합니다.

모든 것과 어떤 것

정의역의 모든 원소에 대해 $P(x)$가 참이라는 명제를 $\forall x\,P(x)$로 쓰고 "모든 x에 대해 P(x)"라고 읽습니다. ∀를 전칭 양화사(universal quantifier)라고 합니다. 정의역에 $P(x)$가 참인 원소가 적어도 하나 있다는 명제는 $\exists x\,P(x)$로 쓰고 "어떤 x에 대해 P(x)" 또는 "P(x)인 x가 존재한다"라고 읽으며, ∃를 존재 양화사(existential quantifier)라고 합니다. 술어에 양화사가 붙으면 x에 값을 넣지 않아도 참과 거짓이 정해지는 명제가 됩니다.

존재 양화사는 "적어도 하나"라는 뜻이지 "정확히 하나"라는 뜻이 아닙니다. 정확히 하나라고 말하려면, 그런 원소가 존재하고 그 성질을 가진 원소는 모두 그 하나와 같다는 것을 따로 말해야 합니다.

정의역이 유한하다면 양화사는 Python의 all과 any로 그대로 계산할 수 있습니다. all은 모든 값이 참일 때, any는 하나라도 참일 때 참을 돌려주기 때문입니다.

domain = range(-3, 4)
print(all(x * x >= 0 for x in domain))
print(any(x * x == 2 for x in domain), any(x * x == 4 for x in domain))
print(all(x > 10 for x in []), any(x > 10 for x in []))

True
False True
True False

-3부터 3까지의 정수에서 제곱은 모두 0 이상이고, 제곱이 2인 정수는 없지만 제곱이 4인 정수는 있습니다. 마지막 줄은 정의역이 비어 있는 경우입니다. 원소가 하나도 없으면 "모든 원소가 10보다 크다"는 반례가 없으므로 참이고, "10보다 큰 원소가 있다"는 그런 원소가 없으므로 거짓입니다. 앞 장에서 빈 곱을 1로, 빈 합을 0으로 정한 것처럼, 빈 정의역에서 전칭 명제는 참, 존재 명제는 거짓으로 정해집니다.

양화사의 순서가 뜻을 바꾼다

양화사가 여러 개 있으면 순서가 중요합니다. 처음의 추천 예를 술어로 적어 보겠습니다. $L(u,p)$를 "사용자 u가 상품 p를 좋아한다"라고 하면, "모든 사용자에게 좋아하는 상품이 있다"는 $\forall u\,\exists p\,L(u,p)$이고, "모든 사용자가 좋아하는 상품이 있다"는 $\exists p\,\forall u\,L(u,p)$입니다. 앞의 것은 u를 먼저 정한 뒤 그 u에 맞는 p를 고르면 되므로 사용자마다 다른 상품이어도 되지만, 뒤의 것은 p 하나를 먼저 정하고 그 p가 모든 u에 대해 성립해야 합니다.

likes = {"민수": {"책", "펜"}, "지수": {"펜", "컵"}, "하늘": {"컵"}}
products = ["책", "펜", "컵"]
print(all(any(p in likes[u] for p in products) for u in likes))
print(any(all(p in likes[u] for u in likes) for p in products))

True
False

바깥의 all과 안쪽의 any가 $\forall u\,\exists p$를, 바깥의 any와 안쪽의 all이 $\exists p\,\forall u$를 그대로 옮긴 것입니다. 세 사람 모두 좋아하는 상품이 하나씩은 있지만, 세 사람이 함께 좋아하는 상품은 없습니다.

정의역이 무한해도 같은 차이가 있습니다. 정수에서 $R(x,y)$를 $y=x+1$이라 하면, $\forall x\,\exists y\,R(x,y)$는 참입니다. x가 무엇이든 그보다 1 큰 정수 y를 고르면 되기 때문입니다. 반면 $\exists y\,\forall x\,R(x,y)$는 거짓입니다. 그런 y가 있다면 x = 0일 때 y = 1이어야 하고, x = 1일 때 y = 2여야 해서 하나의 y로는 불가능하기 때문입니다. 같은 종류의 양화사끼리는 순서를 바꾸어도 뜻이 같지만, ∀와 ∃가 섞여 있으면 순서를 함부로 바꾸면 안 됩니다. 데이터베이스에서 "조건마다 그 조건을 만족하는 결과가 있는가"와 "모든 조건을 한꺼번에 만족하는 결과가 있는가"를 구분해야 하는 것도 같은 문제입니다.

양화사의 부정

"모든 요청이 성공했다"가 거짓이라는 것은 "실패한 요청이 적어도 하나 있다"는 뜻입니다. "모든 요청이 실패했다"가 아닙니다. 마찬가지로 "성공한 요청이 있다"가 거짓이라는 것은 "모든 요청이 실패했다"는 뜻입니다. 기호로 적으면 다음과 같습니다.

부정이 양화사를 지나가면 ∀는 ∃로, ∃는 ∀로 바뀌고 부정은 안쪽으로 들어갑니다. 유한한 정의역에서는 not all(...)과 any(not ...)이 같은 값을 냅니다.

requests = [200, 200, 500, 200]
succeeded = [code == 200 for code in requests]
print(all(succeeded), not all(succeeded), any(not s for s in succeeded))
print(not any(code == 404 for code in requests), all(code != 404 for code in requests))

False True True
True True

양화사가 여러 개 있어도 바깥에서부터 하나씩 바꾸면 됩니다. $\neg\forall x\,\exists y\,R(x,y)$는 $\exists x\,\neg\exists y\,R(x,y)$이고, 다시 $\exists x\,\forall y\,\neg R(x,y)$입니다. 정수의 $y=x+1$ 예에서는 "어떤 정수 x에 대해서는 x 다음 수가 되는 정수가 하나도 없다"가 되는데, 원래 명제가 참이므로 이 부정은 거짓입니다.

조건이 붙은 전칭 명제 $\forall x\,(P(x)\to Q(x))$를 부정하면 $\exists x\,(P(x)\land\neg Q(x))$가 됩니다. 조건명제는 가정이 참이고 결론이 거짓일 때만 거짓이므로, 반례는 P가 참이면서 Q가 거짓인 원소여야 합니다. "6의 배수이면 3의 배수다"의 반례를 찾으려고 6의 배수가 아닌 수를 고르면 반례가 되지 않습니다. 가정을 만족하지 않는 원소는 조건명제를 거짓으로 만들 수 없기 때문입니다.

정리

• 술어는 변수에 값을 넣어야 참과 거짓이 정해지는 문장이고, 변수에 넣을 수 있는 값의 집합인 정의역을 먼저 정해야 합니다.
• $\forall x\,P(x)$는 정의역의 모든 원소에서, $\exists x\,P(x)$는 적어도 하나의 원소에서 P가 참이라는 뜻이며, 유한한 정의역에서는 all과 any로 계산할 수 있습니다.
• 빈 정의역에서 전칭 명제는 참, 존재 명제는 거짓입니다.
• ∀와 ∃가 섞여 있으면 순서에 따라 뜻이 달라집니다. $\forall x\,\exists y$는 x마다 다른 y여도 되지만, $\exists y\,\forall x$는 하나의 y가 모든 x에 대해 성립해야 합니다.
• 부정은 ∀를 ∃로, ∃를 ∀로 바꾸며 안쪽으로 들어가고, $\forall x\,(P(x)\to Q(x))$의 반례는 P가 참이고 Q가 거짓인 원소입니다.

연습 문제

1. 파일과 사용자

"모든 파일에 대해, 그 파일을 읽을 수 있는 사용자가 있다"를 기호로 적고 그 부정을 문장으로 쓰세요.

2. 정의역을 바꾸면

정의역이 정수일 때 $\exists x\,(x^2=2)$와 $\forall x\,(x^2\ge0)$의 진릿값을 판단하고, 정의역을 실수로 바꾸면 무엇이 달라지는지 설명하세요.

3. 조건명제의 반례 찾기

1부터 20까지의 정수에서 "6의 배수이면 3의 배수다"와 "3의 배수이면 6의 배수다"의 반례를 각각 모두 찾으세요.

"모든"과 "어떤"이 헷갈리면 정의역의 원소 두세 개로 문장을 풀어 써 보세요. 존재 명제와 전칭 명제를 증명하는 방법은 존재증명과 반례에서, 앞의 명제들로 결론을 이끄는 규칙은 다음 글 추론 규칙과 논증의 타당성에서 다룹니다.