긴 식의 양화사를 앞에 모아도 되나요?

네. 모든 양화사가 식의 맨 앞에 차례로 놓이고, 그 뒤에는 양화사가 없는 부분만 남게 정리해 보겠습니다. 이 모양을 전두형, 또는 전두 정규형이라고 부릅니다. “전두”는 앞머리를 가리키는 이름이라고 생각하면 됩니다.

올바른 동치 변환이라면 참과 거짓이 달라지지 않습니다. 정리한 식이 참인지도 따로 살펴야 합니다. 또 앞에 양화사를 모았다고 해서 그 순서를 마음대로 바꿀 수 있는 것은 아닙니다. 왜 첫 예제가 가능한지 차근차근 확인하겠습니다.

먼저 각 x가 어느 양화사의 범위 안에 있는지 확인해 보세요. (∀xP(x))∨R(x,a)를 보겠습니다. 첫 x는 ∀x가 맡지만, R 안의 x는 그 양화사의 괄호 밖에 있습니다. a는 이름입니다.

그렇습니다. 원래 자유로웠던 출현까지 새로 묶입니다. 이런 일을 변수 포획이라고 불렀지요. 원래 식의 x는 값을 정해 놓고 읽었는데, 바꾼 식에서는 그 자리까지 “모든 x”가 움직입니다. 먼저 왼쪽 양화사의 변수 이름을 다르게 바꾸어야 합니다.

양화사 표시와 그 양화사가 맡는 출현을 함께 바꿉니다. 새 변수는 이미 다른 역할로 쓰이는 자리와 겹치지 않게 고르겠습니다. 첫 예제에서는 (∀uP(u))∨R(x,a)로 바꿉니다. 자유로운 x와 이름 a는 그대로 둡니다.

그 y는 자유롭게 남아 있던 자리입니다. u로 바꾸면 바깥 ∀u가 잡아 버립니다. 표의 마지막 식에서도 y는 그대로 두어야 합니다. 새 이름을 고를 때에는 “지금 이 글자가 식의 다른 곳에서 쓰이나요?”부터 확인하세요.

→가 있으면 A→B를 ¬A∨B로 먼저 바꾸어 보세요. 여기서 A와 B는 짧거나 긴 식 전체를 대신하는 표시입니다. 조건문의 앞부분이 부정으로 바뀌는 모습을 보면, 그 안의 양화사가 왜 뒤집히는지도 이해하기 쉽습니다.

맞습니다. 그래서 ↔를 풀어 쓴 다음, 서로 다른 범위를 맡는 양화사에는 서로 다른 변수 글자를 다시 배정하는 것이 안전합니다. 전체의 자유변수는 그대로 유지하면서, 속박변수만 새 글자로 정리합니다.

네. ¬∀xA는 ∃x¬A로, ¬∃xA는 ∀x¬A로 바꿉니다. A가 길면 A 전체를 부정한 뒤 다시 안쪽을 살핍니다.

이 예제에서는 영역을 가상 모임 사람들로 두고, P(x)는 “x가 발표자다”, R(x,y)는 “x가 y에게 인사했다”로 정합니다. 마지막 식은 어느 발표자가 누구에게도 인사하지 않았다는 말입니다. 처음의 “모든 발표자가 누군가에게 인사했다”를 부정한 뜻과 맞는지 말로도 확인해 보세요.

∀y가 지나갈 P(x)에는 y가 자유롭게 나타나지 않습니다. 따라서 우리처럼 비어 있지 않은 영역을 사용하는 고전 논리에서는 ∃x∀y(P(x)∧¬R(x,y))로 바꿀 수 있습니다. 바깥 ∃x의 범위는 유지합니다.

네. B∧(∀xA)처럼 오른쪽에 있어도 B에 x의 자유 출현이 없다는 조건을 확인합니다. ∧와 ∨의 순서를 바꾸어 표를 적용한 뒤 되돌려도 되고, 같은 원리로 바로 옮겨도 됩니다. 한 번에 한 양화사씩 옮기면 조건을 확인하기 좋습니다.

영역을 아라와 보라 두 사람으로 정하겠습니다. P는 아라에게만 참이고, Q는 보라에게만 참입니다. 자유변수 x에는 보라를 배정합니다. 다음 두 식을 같은 조건에서 읽어 보세요.

맞습니다. 잘못 옮긴 식은 한 사람이 두 성질을 함께 가져야 한다고 바꾸었습니다. 안전하게 하려면 왼쪽의 속박 x를 y로 바꾸어 (∃yP(y))∧Q(x)로 쓴 뒤 ∃y(P(y)∧Q(x))로 옮깁니다. 자유로운 x는 계속 보라를 가리키는 배정을 유지합니다.

우리 과정은 처음부터 전체 영역에 적어도 한 대상이 있는 표준 고전 논리를 사용합니다. 어떤 이동은 이 약속을 사용합니다. 차이를 보기 위해 이번 표에서만 빈 영역을 허용한다고 가정해 보겠습니다. S는 x가 없는 하나의 문장을 대신합니다.

그 경우에는 전체 영역이 비어 있지 않습니다. “참가자는 있지만 표를 받은 사람은 없다”를 생각하면 됩니다. 6절의 이동은 P의 외연이 비었을 때도 조건을 지켜 적용할 수 있습니다. 전체 영역이 비는 것과 P인 대상이 없는 것을 나누어 보세요.

이번 예제의 영역은 가상 모임의 사람들입니다. P는 발표자, Q는 자료를 받은 사람, R(x,a)는 “x가 아라에게 인사했다”입니다. a는 아라의 이름입니다. 모든 발표자가 자료를 받았고 누군가 아라에게 인사했다는 말을 정리해 보겠습니다.

그럴 수 있습니다. 이 예제에서는 y에게 요구하는 조건 R(y,a)가 x에 의존하지 않으므로, 아라에게 인사한 한 사람을 모든 x에 대해 공통으로 골라도 됩니다. 마지막 식이 참이면 영역의 어느 x 하나에서 얻은 y가 R(y,a)의 증거가 됩니다. 동시에 모든 x에 대해 P(x)→Q(x)가 성립하므로 원래 두 부분이 모두 참입니다.

조건문의 앞부분에서 바깥으로 나올 때는 바뀝니다. (∀xP(x))→S를 먼저 ¬∀xP(x)∨S로 써 보세요. 양화 부정 때문에 ∃가 나타납니다. S에는 x가 자유롭게 나타나지 않는다고 정합니다.

처음에는 그렇게 해 보세요. 특히 “양화사가 조건문을 지나면 언제나 바뀐다”고 외우면 후건에서도 잘못 뒤집게 됩니다. 전건인지 후건인지와 자유변수 조건을 함께 봅니다.

바깥 연결사부터 보겠습니다. 아래 식의 전건 전체는 “모든 P인 대상에게 R로 관계 맺는 상대가 있다”이고, 후건은 “Q인 대상이 있다”입니다. 이번에는 특정 생활 해석을 덧붙이지 않고, P·Q·R에 어떤 뜻을 주어도 성립하는 변형의 구조를 살펴보겠습니다.

맞습니다. 이제 부정 정리가 끝났습니다. 각 양화사가 지나갈 부분에 자기 변수의 자유 출현이 없는지 보면서 꺼내겠습니다.

그렇게 하기 전에 별도의 동치 근거가 필요합니다. 이미 앞에 놓인 ∀x∃yR(x,y)는 전두형입니다. 여기서 두 양화사를 바꾼 ∃y∀xR(x,y)는 보통 더 강한 요구를 합니다.

가능한 경우가 있습니다. (∀xP(x))∧∃yQ(y)에서는 두 부분이 서로의 변수에 의존하지 않아, 이동 조건을 지켜 ∀x∃y로 모을 수도 있고 ∃y∀x로 모을 수도 있습니다. 그 식에 적용한 정당한 이동 과정이 근거입니다. 여기의 R(x,y)는 두 변수를 함께 연결하므로 같은 설명을 그대로 가져올 수 없습니다.

먼저 한 줄을 바꾼 이유를 적어 보세요. 그다음 지나가는 식에 자유변수가 남아 있는지 표시합니다. 아래 문제는 모두 비어 있지 않은 영역의 고전 논리에서 풉니다.

앞에 모였는지는 모양 점검입니다. 뜻을 지켰는지는 각 줄의 근거를 보아야 합니다. 식이 길어질수록 처음의 자유변수, 이름, 괄호를 적어 두면 도움이 됩니다.

이번에는 긴 식을 다루는 손순서를 익혔습니다. 다음 편에서는 실제처럼 보이는 가상 안내문을 읽겠습니다. 문장의 대상과 시점을 정하고, 무엇이 주어졌으며 어떤 결론까지 따라오는지 끝까지 확인해 보겠습니다.