양화식을 같은 뜻으로 어떻게 바꾸나요?

‘같은 뜻’의 기준부터 정하겠습니다. 이 편에서 두 식이 논리적으로 동치라는 말은, 허용하는 모든 해석에서 두 식의 참·거짓이 같다는 뜻입니다. 자유변수가 남은 식이라면 같은 대상 배정 아래에서도 늘 값이 같아야 합니다. 표에서는 이 관계를 ≡로 표시하겠습니다. ≡는 두 식을 비교하는 표시이며, 식 안에 넣는 ↔와 역할을 구별합니다.

맞습니다. 그러나 아라는 첫 글을 읽고 보라는 읽지 않은 등록부에서는 첫 식이 참이고 둘째 식이 거짓입니다. 한 곳에서 값이 같은 것만으로 두 식을 언제나 교환할 수는 없습니다.

네. 모든 사람이 첫 글을 읽었다는 말이 거짓이면, 첫 글을 읽지 않은 사람이 적어도 한 명 있습니다. 반대로 읽지 않은 한 사람이 있으면 모두 읽었다는 말은 거짓입니다. 이 두 방향이 ¬∀xP(x) ≡ ∃x¬P(x)를 뒷받침합니다.

부정의 위치와 양화사의 종류를 함께 바꿔야 합니다. 안쪽 식이 길어도 그 식 전체를 부정합니다. ¬∀x(P(x)∧Q(x))는 먼저 ∃x¬(P(x)∧Q(x))가 됩니다. 다음에 명제논리의 드모르간 법칙을 적용하면 ∃x(¬P(x)∨¬Q(x))가 됩니다.

전칭 부정이 찾는 대상은 조건문을 거짓으로 만드는 대상입니다. M(x)→P(x)가 거짓이 되려면 M(x)는 참이고 P(x)는 거짓이어야 합니다. 정회원이면서 첫 글을 읽지 않은 사람이 반례입니다.

정회원이 없으면 원래 전칭 조건문은 공허하게 참입니다. 따라서 그 부정은 거짓입니다. 마지막 존재문도 M과 ¬P를 동시에 만족할 정회원이 없어서 거짓입니다. 전체 영역에 사람이 있다는 약속과 정회원이 있다는 주장을 섞지 마세요.

가능합니다. 첫 식이 참이면 어느 사람이든 첫 글과 둘째 글을 모두 읽었습니다. 따라서 모두 첫 글을 읽었다는 말도 참이고, 모두 둘째 글을 읽었다는 말도 참입니다. 이번에는 거꾸로 생각해 보세요. 모두 첫 글을 읽고 모두 둘째 글을 읽었다면, 임의의 같은 사람에게 두 사실을 적용할 수 있습니다.

맞습니다. 방금 이유는 두 명이나 세 명이라는 수에 의존하지 않았습니다. 임의의 대상에 적용되는 양쪽 조건을 비교했으므로 모든 허용 해석에 통합니다.

이 경우에도 가능합니다. 식은 첫 글 또는 둘째 글을 읽은 사람이 있다는 뜻입니다. 그런 사람이 있으면 첫 글을 읽은 사람이 있거나 둘째 글을 읽은 사람이 있습니다. 거꾸로 첫 글을 읽은 사람이 있다면 그 사람은 P∨Q의 증거가 되고, 둘째 글을 읽은 사람이 있어도 마찬가지입니다.

이 편의 ∨는 포괄적인 ‘또는’입니다. P와 Q가 둘 다 참인 대상도 P∨Q를 만족합니다. 두 글을 다 읽은 아라 한 명만 있어도 왼쪽 존재문은 참이고, 오른쪽의 두 존재문도 모두 참이므로 전체 선언은 참입니다.

왼쪽은 두 글을 같은 사람이 읽어야 합니다. 오른쪽은 첫 글의 증거와 둘째 글의 증거가 서로 다른 사람이어도 됩니다. 그 차이가 드러나는 등록부를 만들어 보겠습니다. 영역은 아래 두 사람뿐입니다.

맞습니다. ∃x(P(x)∧Q(x))에서 (∃xP(x))∧(∃xQ(x))로 가는 한 방향 추론은 타당합니다. 오른쪽에서 왼쪽으로 돌아오는 방향은 방금 반모형 때문에 성립하지 않습니다.

네. 앞 절의 두 사람을 그대로 쓰겠습니다. 아라는 첫 글을, 보라는 둘째 글을 읽었으므로 각 사람은 적어도 한 글을 읽었습니다. 하지만 모두가 첫 글을 읽은 것도 아니고 모두가 둘째 글을 읽은 것도 아닙니다.

그렇습니다. 모두 첫 글을 읽었다면 누구나 P∨Q를 만족하고, 모두 둘째 글을 읽었어도 누구나 P∨Q를 만족합니다. 따라서 (∀xP(x))∨(∀xQ(x))에서 ∀x(P(x)∨Q(x))로 가는 방향은 타당합니다.

다음 표의 화살표 문구는 타당한 추론 방향을 뜻합니다. 식 안에 들어 있는 →와 섞지 않도록 ‘왼쪽에서 오른쪽’이라고 풀어 쓰겠습니다. 같은 영역과 같은 술어 해석을 유지한 비교입니다.

달라질 수 있습니다. A를 x가 자유롭게 나타나지 않는 식의 약칭이라고 합시다. 예를 들어 A를 Q(a), 곧 ‘아라가 둘째 글을 읽었다’로 둘 수 있습니다. 같은 등록부에서 x를 아라로 보든 보라로 보든 Q(a)의 값은 그대로입니다. 여기서 ‘무관하다’는 것은 확률적 독립이 아니라 이 자유변수 조건을 뜻합니다.

A가 참이면 P가 어떤 값이든 모든 대상에게 P∨A가 참이므로 양쪽이 참입니다. A가 거짓이면 각 대상의 P∨A 값은 P의 값과 같으므로 양쪽 모두 ∀xP(x)의 값으로 결정됩니다. 이 두 경우가 모든 가능성을 덮습니다. 앞 절의 Q(x)는 사람마다 달라질 수 있었지만, 지금의 A는 x에 따라 달라지지 않습니다.

충분히 안전한 방법은 없는 식을 고르는 것이지만, 정확한 조건은 자유로운 x가 없어야 한다는 것입니다. A가 ∀xQ(x)라면 그 x는 안쪽 양화사가 맡습니다. 혼동을 줄이려고 A를 ∀zQ(z)로 안전하게 이름 바꿔 쓸 수 있습니다. 반면 A가 Q(x) 또는 ∀yR(x,y)라면 x가 자유롭게 남습니다. 여기서 R은 ‘x가 y를 독서 짝으로 추천했다’는 관계로 두겠습니다.

영역은 {아라, 보라}, P인 사람은 없고 Q인 사람은 아라뿐이라고 합시다. 자유변수 x에는 아라를 배정합니다. 그러면 (∀zP(z))∨Q(x)는 거짓∨참이어서 참입니다. 이것을 ∀x(P(x)∨Q(x))로 고치면 보라에게 두 항이 모두 거짓이어서 전체가 거짓이 됩니다. 원래 자유로웠던 Q(x)를 새 ∀x가 잡아 버린 결과입니다.

A에 x가 자유롭게 나타나지 않을 때 올바른 동치는 (∃xP(x))→A입니다. 조건문의 앞부분은 부정과 연결되기 때문에 양화사의 종류가 바뀝니다. A가 Q(a)라면 첫 식은 ‘누구든 첫 글을 읽었다면 아라가 둘째 글을 읽었다’이고, 바뀐 식은 ‘첫 글을 읽은 사람이 있다면 아라가 둘째 글을 읽었다’입니다.

영역은 {아라, 보라}, P인 사람은 아라뿐, Q인 사람은 없다고 합시다. A=Q(a)는 거짓입니다. ∀x(P(x)→A)는 아라에게 참→거짓이어서 거짓입니다. 그런데 (∀xP(x))→A는 앞부분이 보라 때문에 거짓이어서 참입니다. 두 값이 달라지므로 그 변환은 동치가 아닙니다.

두 전칭끼리, 두 존재끼리는 같은 본문을 유지하며 순서를 바꿀 수 있습니다. 서로 다른 두 변수를 쓰고, 어떤 출현을 묶는지도 유지해야 합니다. 관계 R(x,y)의 첫 자리는 추천한 사람, 둘째 자리는 추천받은 사람입니다.

맞습니다. 영역 {아라, 보라}에서 서로를 추천하고 자신은 추천하지 않는 경우, 각 사람에게 추천한 상대가 있으므로 ∀x∃yR(x,y)는 참입니다. 모든 사람이 추천한 한 사람은 없으므로 ∃y∀xR(x,y)는 거짓입니다. 반대로 공통으로 추천받는 한 사람이 있으면 그 사람을 각 x의 증거로 사용할 수 있어, ∃y∀x에서 ∀x∃y로 가는 방향은 성립합니다.

임의의 위치에서 자유롭게 교체하려면 동치가 필요합니다. 한 방향으로만 강도가 다른 두 식은 부정 속에서 특히 조심해야 합니다. U를 ∃x(P(x)∧Q(x)), V를 (∃xP(x))∧(∃xQ(x))의 약칭이라고 하겠습니다. U에서 V로 갈 수 있지만, ¬U에서 ¬V로 같은 방향으로 갈 수는 없습니다.

그렇습니다. 반면 ¬∀xP(x)와 ∃x¬P(x)처럼 동치인 식은 참 조건이 완전히 일치합니다. 자유변수의 배정과 속박을 보존하면서 동치인 부분식으로 바꾸면 더 큰 식에서도 값이 유지됩니다. 다음 편의 전두형 변환도 이 원리를 사용합니다.

‘첫 글이나 둘째 글 중 어느 하나라도 읽지 않은 정회원은 없다’를 정리해 보겠습니다. ¬P(x)∨¬Q(x)는 적어도 한 글을 읽지 않았다는 말입니다. 여기에 M(x)를 연언으로 묶고, 그런 사람이 있다는 존재문을 부정하여 시작합니다.

네. ‘빠뜨린 정회원이 없다’는 표현을 두 전칭 조건으로 풀어 쓴 것입니다. 5번에서 쓰는 명제논리 분배와 6번에서 쓰는 양화 분배를 구별해 두면, 긴 변형도 한 걸음씩 검토할 수 있습니다.

자주 쓰는 두 출발점부터 익히면 좋습니다. 부정을 양화사 안으로 넣을 때에는 ∀와 ∃를 바꾸고 안쪽 식 전체를 부정합니다. 분배에서는 모든 대상에게 두 성질이 있는지, 한 증거가 어느 쪽을 만족하면 되는지 묻습니다. 익숙하지 않은 변환은 양쪽의 참 조건을 말로 풀어 보세요.

다음 18편에서는 오늘 확인한 동치를 이용하여 양화사들을 식의 앞쪽으로 모읍니다. 먼저 변수 이름을 정리하고, 한 번 옮길 때마다 자유변수 조건을 확인하겠습니다. 식의 모양이 달라져도 참 조건이 그대로 이어지는지가 기준입니다.