사람마다 한 명과 모두에게 한 명은 어떻게 다른가요?

네. 한 사람의 성질을 나타내던 P(x)에는 대상을 넣는 자리가 하나 있었습니다. R(x,y)에는 두 자리가 있습니다. 이런 술어로 두 대상 사이의 관계를 나타낼 수 있습니다.

그렇습니다. 첫 자리에 a가 있으니 기억하는 사람은 아라입니다. 둘째 자리에 b가 있으니 기억하는 이름은 보라의 이름입니다. 따라서 “아라는 보라의 이름을 기억한다”라고 읽습니다. R이라는 글자 자체에 이 뜻이 들어 있지는 않으므로, 처음 약속을 먼저 확인해야 합니다.

이제 실제 값을 넣겠습니다. 다음 표는 이 수업을 위해 정한 가상 현황입니다. 각 칸을 모두 확인했다고 가정합니다. 왼쪽에서 가로줄을 고르고, 위쪽에서 세로줄을 고르면 두 사람이 만나는 한 칸이 나옵니다.

맞습니다. 이번에는 보라 가로줄에서 아라 세로줄을 찾으면 거짓입니다. R(b,a)는 거짓이지요. 아라가 보라의 이름을 기억한다는 정보만으로 보라도 아라의 이름을 기억한다고 말할 수는 없습니다.

그 칸들은 자기 자신의 이름을 기억하는지를 나타냅니다. 이 표에서는 세 칸 모두 참입니다. 두 자리에 같은 사람을 넣는 경우도 관계표의 일부라는 점을 눈여겨보세요.

“아라는 y의 이름을 기억한다”입니다. y에 아라·보라·찬우를 각각 넣으면 처음 표의 아라 가로줄을 왼쪽부터 읽게 됩니다. 그 값은 참·참·거짓입니다.

네. x에 아라·보라·찬우를 넣으면 보라의 이름을 누가 기억하는지 확인합니다. 아라와 보라는 기억하고 찬우는 기억하지 못합니다. 그래서 ∃x R(x,b)는 참이고 ∀x R(x,b)는 거짓입니다.

그렇습니다. 양화사의 글자와 관계의 자리를 함께 보세요. ∃y는 y가 있는 둘째 자리의 대상을 찾고, ∀x는 x가 있는 첫째 자리를 영역 전체에 걸쳐 확인합니다.

그때 ∀x (∃y R(x,y))라고 적습니다. 바깥의 ∀x는 각 사람을 살펴보겠다는 뜻입니다. 그 사람을 하나 정한 다음, 안쪽의 ∃y에 따라 그 사람이 이름을 기억하는 대상을 찾습니다. 괄호를 줄여 ∀x∃y R(x,y)라고 적기도 합니다.

참인 칸이면 됩니다. 처음 표에서 아라에게는 보라, 보라에게는 찬우, 찬우에게는 아라를 골라도 됩니다. ∃y는 특정 이름을 미리 고정하지 않습니다. 각 x에 맞는 대상을 찾을 수 있으면 됩니다.

이번에는 이름의 주인 y를 하나 정했을 때 모든 사람 x가 그 이름을 기억해야 합니다. 그래서 ∃y (∀x R(x,y))라고 적습니다. 바깥에서 y를 찾고, 그 같은 y를 둔 채 안쪽에서 모든 x를 살펴봅니다.

그 차이를 양화사의 순서가 드러냅니다. ∀x∃y에서는 x마다 알맞은 y를 찾습니다. ∃y∀x에서는 모든 x에게 통하는 y를 찾습니다. 여기서 “먼저 고른다”는 말은 식을 평가하는 순서를 설명한 것입니다. 실제 사람들이 어떤 시간 순서로 이름을 외웠는지까지 말하지는 않습니다.

더 작은 예로 다시 확인하겠습니다. 이 절의 별도 영역에는 아라와 보라 두 사람만 있고, 각자 자기 이름만 기억한다고 약속합니다. 찬우는 이 절의 영역에 들어 있지 않습니다.

맞습니다. 아라에게는 아라, 보라에게는 보라를 고르면 됩니다. 그런데 아라 세로줄에는 보라의 거짓이 있고, 보라 세로줄에는 아라의 거짓이 있습니다. 모든 칸이 참인 세로줄이 없으므로 ∃y∀x R(x,y)는 거짓입니다.

네. 전제인 ∀x∃y R(x,y)는 참인데 결론인 ∃y∀x R(x,y)는 거짓인 해석을 만들었습니다. 이런 해석을 반모형이라고 부릅니다. 명제논리에서 반례 배정을 찾았던 것처럼, 술어논리에서는 대상들과 성질·관계까지 정해 검토합니다.

네. 그리고 ∀x∃y R(x,y)도 참입니다. x가 아라일 때 y를 보라로, x가 보라일 때에도 y를 보라로, x가 찬우일 때에도 y를 보라로 고르면 됩니다.

그렇습니다. ∃y는 각 x에서 조건을 만족하는 대상을 찾으라고 할 뿐, x가 바뀔 때마다 y도 바꾸라고 요구하지 않습니다. 같은 y가 여러 x에서 통하면 그대로 사용할 수 있습니다. 반대로 한 x에서 가능한 y가 여러 명 있어도 됩니다.

네. ∃y∀x R(x,y)가 참이라고 합시다. 그러면 모든 x에게 통하는 y가 적어도 하나 있습니다. x를 누구로 고르든 그 같은 y를 사용하면 R(x,y)가 참입니다. 따라서 각 x에서 ∃y R(x,y)가 참이고, ∀x∃y R(x,y)도 참입니다.

맞습니다. 이때 공통 대상이 어떤 익숙한 사람이라고 미리 정할 필요는 없습니다. 누구든 모두에게 통하는 대상이 있다는 사실을 사용합니다. 아까 보라가 공통 대상인 표는 그 추론을 보여 주는 구체적인 예였고요.

두 변수에 같은 사람을 배정할 수 있습니다. 6절의 두 사람 표에서는 x에 아라, y에도 아라를 넣어 R(a,a)를 확인했지요. x와 y가 다르게 적혀 있다는 사실만으로 사람도 다르다는 조건이 생기지는 않습니다.

대상이 서로 다르다는 조건을 함께 적어야 합니다. x ≠ y는 x와 y에 배정한 두 대상이 서로 다르다는 뜻입니다. 이제 ∃y (x ≠ y ∧ R(x,y))라고 쓰면, x와 다른 사람이면서 x가 그 이름을 기억하는 y를 찾습니다.

그 표현에서는 기억하는 사람 x를 하나 정합니다. 그 x가 모든 사람 y의 이름을 기억해야 하므로 ∃x∀y R(x,y)입니다. 관계표에서는 아홉 칸 전체를 볼 필요 없이, 모든 칸이 참인 가로줄 하나를 찾으면 됩니다.

다른 관계에도 같은 방식으로 적용할 수 있습니다. 예를 들어 H(x,y)를 “x가 y를 도왔다”로 정하면, ∃x∀y H(x,y)는 모두를 도운 사람이 있다는 뜻이고, ∃y∀x H(x,y)는 모두에게 도움을 받은 사람이 있다는 뜻입니다. 첫 자리의 역할과 둘째 자리의 역할을 바꾸지 않고 읽는 연습입니다.

그렇게 외우면 같은 종류의 양화사를 연이어 쓰는 경우를 놓칩니다. ∀x∀y R(x,y)와 ∀y∀x R(x,y)는 모두 영역의 모든 대상 쌍에서 R이 참이라고 말합니다. 가로줄부터 전부 살펴보아도, 세로줄부터 전부 살펴보아도 결국 같은 모든 칸을 확인합니다.

∃x∃y R(x,y)와 ∃y∃x R(x,y)도 동치입니다. 관계표 어딘가에 참인 칸이 적어도 하나 있으면 두 식이 모두 참입니다. x와 y를 찾는 순서를 바꾸어도 그 참인 한 쌍을 사용할 수 있습니다.

네. 식을 옮길 때에는 지금 적용하는 동치가 어느 형태인지 확인하면 됩니다. 여기서 양화사의 순서를 바꿀 수 있다는 말은 개별 관계 R(a,b)를 R(b,a)로 바꾸어도 된다는 뜻과 구별합니다. 둘의 값은 실제 관계에 달려 있습니다.

같은 역할의 자리를 빠짐없이 함께 바꾸면 뜻을 유지할 수 있습니다. ∀x∃y R(x,y)에서 x를 모두 u로, y를 모두 v로 바꾸면 ∀u∃v R(u,v)입니다. 바깥에서 모든 사람을 살펴보고 그 사람에게 맞는 이름의 주인을 찾는 구조는 같습니다.

네. 그 식에서는 y가 첫 자리의 사람을, x가 둘째 자리의 사람을 맡습니다. “모든 첫 자리 사람에 대해 둘째 자리의 대상을 찾는다”는 관계가 그대로입니다. 이처럼 변수 이름을 함께 바꾸는 것과, ∃y∀x R(x,y)처럼 두 양화사의 범위를 바꾸는 일은 다릅니다.

맞습니다. 지금처럼 두 변수가 분명히 나뉜 식부터 연습하면 됩니다. 긴 식에서 기존에 쓰던 변수와 이름이 겹치는 문제, 양화사의 범위 밖에 남은 변수는 다음 회차에서 자세히 살펴보겠습니다.

바깥 양화사부터 한 번에 하나씩 적용하면 됩니다. 먼저 “모두”를 부정하므로, 안쪽의 “누군가의 이름을 기억한다”가 거짓인 사람이 적어도 한 명 있다고 읽습니다. 그다음 안쪽 존재문을 부정합니다.

네. ∃y∀x 전체를 부정하면 ∀y∃x가 되고, 관계를 부정합니다. 어떤 이름의 주인 y를 골라도 그 이름을 기억하지 못하는 x가 적어도 한 명 있다는 뜻입니다. y마다 그런 x가 달라도 됩니다.

좋습니다. 두 자리의 뜻을 적어 두고, 바깥 양화사에서 정한 대상을 안쪽 식에서도 유지해 보세요. 그림을 그리거나 표를 만들 때에도 같은 약속을 지키면 됩니다. 이어지는 과정에서는 괄호와 변수의 범위를 자세히 살펴보며, 긴 식에서 어떤 자리가 아직 정해지지 않았는지 읽어 보겠습니다.