괄호와 변수는 어디까지 이어지나요?

오늘은 글자가 나타난 자리를 하나씩 짚어 보겠습니다. 식의 맨 앞에 ∃x가 있다고 해서 뒤에 나오는 모든 x를 한꺼번에 다루지는 않습니다. 먼저 우리가 볼 장면과 글자의 뜻을 정하겠습니다.

맞습니다. P(x)는 배정한 아이의 모자를, Q(x)는 그 아이의 공책을 확인합니다. 이번 편에서 배정을 바꿀 때에는 아이들의 상태나 a·b·c가 가리키는 사람을 바꾸지 않습니다.

작은 부분부터 살펴보면 됩니다. P(x)의 괄호에는 P를 적용할 대상의 자리가 있습니다. Q(x)도 마찬가지입니다. 두 식 바깥의 큰 괄호는 P(x) ∧ Q(x)를 하나의 내용으로 묶습니다.

그렇습니다. 여기서는 한 아이를 골라 두 조건을 함께 확인합니다. 처음 장면의 아라가 두 조건을 충족하므로 이 존재 주장은 참입니다. 찬우의 모자와 보라의 공책을 가져와 합치는 방식으로 읽지 않습니다.

같은 묶음을 눈에 잘 보이게 적은 것입니다. 이 수업에서는 바깥의 둥근 괄호를 대괄호로 바꾸어 써도 같은 묶음을 뜻합니다. 괄호의 모양을 바꾸는 일과, 닫는 괄호의 위치를 옮기는 일은 구별해야 합니다.

이번에는 두 식을 나란히 놓겠습니다. ∃x(P(x) ∧ Q(x))와 (∃xP(x)) ∧ Q(x)입니다. 두 번째 식에서는 ∃x에 딸린 부분이 P(x)에서 끝납니다.

맞습니다. 두 번째 식은 “모자를 쓴 아이가 적어도 한 명 있다”와 “지금 따로 x에 배정한 아이가 공책을 들고 있다”를 ∧로 묶었습니다. 왼쪽에서 존재를 확인할 때 골랐던 아이를 오른쪽까지 자동으로 데려오지 않습니다.

양화사가 붙은 부분식 전체를 그 양화사의 범위라고 부르겠습니다. 범위 안에서 실제로 대상을 바꾸며 확인할 내용은 양화사 뒤에 붙은 식입니다. 괄호는 그 내용의 끝을 보여 줍니다.

처음 장면에서 바깥의 x에 찬우를 배정해 보세요. 첫 식은 아라 덕분에 참입니다. 두 번째 식의 왼쪽도 참이지만, 오른쪽 Q(x)는 찬우에 대해 거짓입니다. 따라서 두 번째 식 전체는 거짓입니다.

x가 나타난 각각의 자리를 나누어 말하면 됩니다. (∃xP(x)) ∧ Q(x)에서 P(x)의 x는 왼쪽 ∃x에 묶여 있습니다. Q(x)의 x는 자신을 묶는 양화사의 범위에 들어 있지 않습니다.

양화사에 묶인 자리를 속박된 출현, 묶이지 않은 자리를 자유로운 출현이라고 합니다. 출현은 글자가 식의 어느 자리에 나타났다는 뜻입니다. “자유변수 x가 있다”는 말은 x가 자유롭게 나타난 자리가 있다는 뜻으로 읽으면 됩니다.

그 x는 어느 변수의 자리를 묶을지 알려 주는 표지로 읽겠습니다. 이 편에서 자유·속박을 찾아보라고 할 때에는 P(x), Q(x), R(x,y)처럼 대상 자리에 나타난 변수를 하나씩 확인합니다. 양화사의 표지와 대상 자리를 구별해서 짚으세요.

그렇습니다. 각 자리에서 괄호를 따라 바깥쪽으로 살펴보세요. 그 자리를 포함하면서 같은 글자를 사용하는 양화사가 있는지 확인합니다. 왼쪽 멀리에 같은 글자가 보인다는 사실만으로는 연결할 수 없습니다.

이번 식은 ∃x(P(x) ∧ Q(y))입니다. P의 대상 자리에는 x, Q의 대상 자리에는 y가 있습니다. 무엇이 묶이는지 먼저 예상해 볼까요?

∃x는 x라는 글자가 쓰인 자리를 다룹니다. y를 묶는 양화사는 이 식에 없습니다. 그래서 P(x)의 x는 속박되고, Q(y)의 y는 자유롭게 남습니다. 큰 괄호 안에 들어 있다는 것만으로는 충분하지 않습니다.

같은 아이여도 됩니다. 서로 다른 변수 글자는 서로 다른 자리를 표시합니다. 두 자리에 서로 다른 대상을 반드시 넣으라는 조건은 포함하지 않습니다. 이 경우에는 x의 조건을 충족할 아이로 아라나 찬우를 고를 수 있습니다.

식 전체를 읽을 때는 자유롭게 남은 y의 배정을 먼저 유지하고, ∃x가 지시하는 방식대로 x를 살펴보세요. y의 배정까지 함께 바꾸어 존재를 찾으면 다른 질문에 답하게 됩니다.

쓸 수 있는 식입니다. 다만 P(x)처럼 자유롭게 남은 자리가 있으면, 그 자리에 어떤 대상을 배정했는지와 함께 평가합니다. 처음 장면에서 x에 아라를 배정하면 참이고, 보라를 배정하면 거짓입니다.

자유변수가 하나도 없는 식을 닫힌 식, 또는 술어논리의 문장이라고 합니다. 자유변수가 있는 식은 열린 식이라고 부릅니다. 먼저 식 안의 연결을 보고 구별한 다음, 그 식을 어떻게 평가할지 살펴봅니다.

꼭 바뀌지는 않습니다. P(x) ∨ ¬P(x)를 보세요. x는 자유롭게 남아 있지만, 어느 아이를 배정해도 “모자를 썼거나 쓰지 않았다”는 식은 참입니다. 자유로운지 여부는 양화사에 묶였는지로 판단합니다. 배정 두 개에서 우연히 같은 값을 얻었다고 해서 속박된 자리가 되지는 않습니다.

조금 낯선 식을 하나 보겠습니다. ∀x(P(x) → ∃xQ(x))입니다. x를 사용하는 양화사가 두 개 있습니다. 이런 식도 허용되지만, 읽을 때 두 양화사의 역할을 나누어야 합니다.

맞습니다. 한 자리를 포함하는 같은 글자의 양화사가 겹치면, 그 자리와 가장 안쪽에서 연결되는 양화사가 묶습니다. Q(x)에 도달했을 때에는 안쪽 ∃x가 자기 일을 시작합니다. 바깥에서 살펴보던 아이와 같은 아이로 고정하지 않습니다.

그 식은 ∀x(P(x) → Q(x))로 적습니다. 지금 식은 “어느 아이든, 그 아이가 모자를 썼다면 공책을 든 아이가 적어도 한 명 있다”입니다. 공책을 든 아이는 그 모자 쓴 아이와 같아도 되고 달라도 됩니다.

혼동을 줄이려면 안쪽 ∃x와 그 ∃x가 묶는 자리를 함께 바꾸어 ∀x(P(x) → ∃yQ(y))라고 쓰면 됩니다. 바깥 x의 역할은 유지됩니다.

그렇습니다. 이제 세 아이가 오전 9시 59분에 주고받은 가상 쪽지 기록을 추가하겠습니다. 영역과 이름은 그대로이며, 앞의 모자·공책은 오전 10시 모습으로 유지합니다. R(x,y)는 “그 쪽지 활동에서 x가 y에게 쪽지를 보냈다”를 뜻합니다.

자기 자신에게 쪽지를 보낸 기록은 없습니다. 아라에게 보낸 기록도 없습니다. 이 표에서는 첫째 자리가 보낸 사람, 둘째 자리가 받은 사람입니다.

맞습니다. 그래서 ∃xR(x,y)에서 R의 첫째 자리 x는 속박되고 둘째 자리 y는 자유롭습니다. R(x,y) 안에 나란히 적혀 있다고 해서 두 자리의 역할이 같아지지 않습니다.

z가 이 식에 쓰이지 않았으므로, ∃zR(z,y)로 함께 바꿀 수 있습니다. ∃x를 ∃z로 바꾸고, 그 양화사가 묶는 R의 첫째 자리도 z로 바꿉니다. 자유롭게 남은 y는 그대로 둡니다.

두 식 모두, 주어진 y의 대상에게 쪽지를 보낸 아이가 있는지 찾습니다. y에 보라를 배정하면 둘 다 참이고, 아라를 배정하면 둘 다 거짓입니다. 찾는 자리의 글자만 바뀌었습니다.

∃zR(x,y)에서는 z가 R의 어느 자리에도 없습니다. x는 자유롭게 남습니다. 예를 들어 x에 보라, y에 보라를 배정하면 R(x,y)는 거짓이고, z에 어떤 아이를 넣어도 그 사실이 바뀌지 않습니다. 원래 ∃xR(x,y)는 y가 보라일 때 참이었지요.

이번에는 ∃xR(x,y)에서 묶인 x를 y로 바꾸었다고 하며 ∃yR(y,y)를 써 보겠습니다. 아까처럼 안전한 변경일까요?

바로 그 변화가 생깁니다. 원래 둘째 자리 y는 주어진 배정을 따랐습니다. 변경한 식에서는 두 y가 같은 ∃y에 묶이므로, 자기 자신에게 쪽지를 보낸 아이가 있는지 묻습니다.

이렇게 변경 과정에서 자유롭게 남아 있던 변수의 자리가 양화사에 묶여 버리는 일을 변수 포획이라고 합니다. 글자 모양을 정리하려다가 원래 따로 두었던 대상 자리를 붙잡은 것입니다.

맞습니다. 또 안쪽에 이미 있는 양화사와 충돌하는지도 살펴야 합니다. ∀x∃yR(x,y)의 바깥 x를 y로 바꾸어 ∀y∃yR(y,y)라고 쓰면, R의 첫째 자리까지 안쪽 ∃y가 묶습니다. 바깥에서 살펴보던 보내는 사람의 자리가 사라집니다.

먼저 어느 식의 자유로운 x 자리에 넣는지 확인합니다. (∃xP(x)) ∧ Q(x)의 자유로운 x에 a를 넣으면 (∃xP(x)) ∧ Q(a)가 됩니다. 왼쪽 P(x)의 x는 이미 ∃x에 묶여 있으므로 그대로 둡니다.

두 작업의 목적이 다릅니다. 묶인 변수의 이름 바꾸기는 같은 물음을 다른 글자로 적습니다. 자유로운 자리에 a를 넣는 일은 그 자리를 아라에 관한 물음으로 정하는 것입니다. 두 작업을 모두 “글자 바꾸기”라고만 생각하면 대상과 범위를 놓치기 쉽습니다.

여기서 대입은 뜻을 무조건 보존하는 변형이 아닙니다. 어떤 대상을 물을지 정하는 작업이므로, 새로 넣은 자리가 의도하지 않은 양화사에 묶이지 않도록 해야 합니다. 뒤의 증명 규칙에서도 이 점을 다시 사용하겠습니다.

이제 ∀x(P(x) → ∃y(R(x,y) ∧ Q(y)))를 함께 읽겠습니다. P와 Q는 오전 10시의 상태, R은 앞에서 정한 오전 9시 59분의 쪽지 기록입니다. 세 아이와 세 기록을 그대로 사용합니다.

바깥 ∀x를 보고 아이를 한 명 살펴본다고 생각하세요. 그 아이가 모자를 썼는지 P(x)를 확인합니다. 썼다면, 그 아이가 쪽지를 보낸 사람 가운데 오전 10시에 공책을 든 아이가 적어도 한 명 있는지 찾습니다.

됩니다. ∃y는 각 아이에 대해 조건을 충족하는 받는 사람이 있는지를 묻습니다. 받는 사람이 같아도 되고 달라도 됩니다. 이 기록에서는 보라가 두 경우의 근거입니다. 각 x에 대한 조건문이 모두 참이므로 전체 식도 참입니다.

이제 연결도 짚어 보세요. P(x)의 x와 R(x,y)의 첫째 자리 x는 바깥 ∀x에 묶입니다. R(x,y)의 둘째 자리 y와 Q(y)의 y는 안쪽 ∃y에 묶입니다. 자유롭게 남은 자리가 없으므로 닫힌 식입니다.

좋습니다. 아래 문제에서도 먼저 양화사가 붙은 부분을 찾으세요. 그다음 같은 글자가 있는 대상 자리를 연결하고, 자유롭게 남은 자리는 따로 표시해 보세요. 값이 필요한 문제는 앞에서 정한 장면과 쪽지 기록을 사용합니다.

다른 식을 만나도 같은 순서로 읽을 수 있습니다. 양화사가 붙은 부분을 찾고, 각 변수 자리의 연결을 확인한 뒤, 아이들에 관한 말로 다시 풀어 보세요. 글자를 바꿀 때에는 그 연결과 자유롭게 남은 자리가 유지되는지 확인합니다.

다음 편에서는 ‘학생만 입장했다’와 ‘학생이면 입장했다’를 함께 읽겠습니다. 어떤 사람이 나오면 그 말이 거짓이 되는지 살펴보면, 조건문의 화살표가 향하는 방향을 찾을 수 있습니다.