식은 어떤 규칙으로 만들어지나요?

네. 기호를 아무렇게나 늘어놓으면 참·거짓을 평가할 식이 되는 것은 아닙니다. 이번에는 어떤 재료를 어떤 순서로 결합할 수 있는지 정하겠습니다. 이 모양에 관한 규칙을 구문이라고 부르고, 그 식에 뜻을 주는 해석은 의미론에서 다룹니다.

f(a)는 이 예에서 한 사람을 가리킵니다. 그 사람이 서류를 냈는지 묻는 P(f(a))가 참·거짓을 평가할 식입니다. 대상을 가리키는 표현과 그 대상에 대해 말하는 식을 나누는 것이 첫걸음입니다.

그렇습니다. 이번 편에서는 아래 기호들로 이루어진 작은 언어를 사용하겠습니다. 이름을 나타내는 기호는 상수기호라고도 부릅니다. f는 입력 자리 하나를 가진 함수기호, P와 Q는 대상 자리 하나를 가진 술어기호, R은 대상 자리 두 개를 가진 관계의 술어기호입니다.

이번 언어에서는 f가 한 자리 함수이므로 그 모양으로 항을 만들 수 없습니다. 두 자리 함수기호를 별도로 도입한 언어라면 두 항을 받는 규칙을 사용할 수 있지만, 지금의 f에 정한 자리 수를 중간에 바꾸지는 않습니다.

만드는 규칙을 먼저 정하면 됩니다. 이 언어에서는 모든 변수와 a·b·k가 항입니다. 이미 만든 항 t가 있으면 f(t)도 항입니다. 이 규칙을 유한 번 적용하여 얻은 것만 항으로 인정합니다. 여기의 t는 특정 변수 글자가 아니라 항 하나 전체를 대신하는 설명용 약칭입니다.

이처럼 작은 구성에 적용한 규칙을 더 큰 구성에도 다시 쓰는 정의를 재귀적 정의라고 부릅니다. 끝없이 이어지는 표현 하나를 허용한다는 뜻은 아닙니다. 각각의 항은 유한한 길이로 완성되어야 합니다. 다만 그 길이에 하나의 공통 최대치를 미리 정하지는 않습니다.

통상적인 일차논리에서 함수기호에 주는 해석은 전체 영역의 모든 입력에 값이 정확히 하나 있는 함수입니다. 이번 가상 등록부에서는 연락인을 빠짐없이 한 명씩 지정했다고 정하겠습니다. 실제 기록에 미지정자가 있다면, 이런 함수 약속을 그대로 만족하는지부터 확인해야 합니다.

함수라는 조건은 입력 하나에 값이 하나라는 뜻입니다. 서로 다른 두 입력에 같은 연락인을 지정해도 함수가 될 수 있습니다. 위 표는 순환하는 예 하나일 뿐이며, 모든 함수가 순환하거나 입력마다 다른 값을 가져야 하는 것은 아닙니다. 자기 자신을 연락인으로 정하는 경우도 함수 조건만으로 배제되지 않습니다.

안쪽 f(a)부터 읽으면 됩니다. a는 아라이고, 표에서 아라의 연락인은 보라입니다. 그러면 바깥 f는 보라를 입력으로 받습니다. 보라의 연락인은 찬우이므로 f(f(a))가 가리키는 대상은 찬우입니다.

그렇습니다. 이 해석에서는 f(a)=b라는 동일성 식이 참입니다. 항 두 개의 글자열이 같아야 동일성 식이 참인 것은 아닙니다. 실제로 가리키는 대상이 같은지 봅니다. 우리 과정의 =는 각 해석에서 대상의 실제 동일성으로 해석합니다.

P와 Q에는 항 하나, R에는 항 두 개를 넣습니다. 두 항 사이에 =를 놓을 수도 있습니다. 이렇게 만든 것을 원자식이라고 부릅니다. 원자식은 연결사나 양화사로 더 작은 식을 묶어서 만든 것이 아니라, 항을 바탕으로 만든 기본 식입니다. ⊥도 기본 식으로 둡니다.

가상 모임의 예에서는 “앞 사람이 뒤 사람에게 오후 6시까지 인사했다”로 읽겠습니다. Q는 1편처럼 “오후 6시까지 확인 도장을 받았다”입니다. 연락인이라는 함수 f를 정했다고 해서 인사 관계 R까지 저절로 정해지는 것은 아닙니다. 어떤 쌍에 R이 참인지도 해석에서 따로 지정합니다.

A와 B가 이미 만들어진 식이라고 합시다. ¬A를 만들거나, 두 식을 (A∧B), (A∨B), (A→B), (A↔B)로 묶을 수 있습니다. 변수 x와 식 A가 있으면 ∀xA와 ∃xA도 만듭니다. 원자식에서 시작해 이 규칙으로 유한 번 만든 것만 식으로 인정하겠습니다.

이번 문법의 양화사는 변수를 받습니다. a는 상수기호이므로 ∀aP(a)는 규칙에 맞지 않습니다. ∀xP(x)처럼 변수를 사용해야 합니다. 반면 ∀xP(a)는 허용합니다. 몸통 P(a)에 자유로운 x가 없어서 실제로 묶는 자리가 없더라도 문법상 식을 만들 수 있습니다.

만들 수 있습니다. 먼저 항들을 확인한 뒤 원자식을 만듭니다. 그다음 R(x,y)에 ∃y를 붙이고, P(f(x))와 그 존재식을 조건문으로 묶습니다. 마지막에 ∀x를 붙이면 전체 식이 됩니다.

필요한 항이 이미 준비되었다면 가능합니다. 그러나 마지막 식을 어떤 두 부분으로 조건 결합했는지, 어느 식 전체에 ∀x를 붙였는지는 고정되어 있습니다. 구성 작업의 시간 순서가 여러 개일 수 있다는 사실과, 완성된 식의 구조가 애매하다는 말은 다릅니다.

항상 그렇지는 않습니다. 전체 식을 마지막으로 만든 구성 단계에서 더한 연결사나 양화사가 주연산자입니다. 예를 들어 (∀xP(x)→Q(a))는 두 식을 →로 묶어 만든 조건문입니다. 처음 보이는 ∀x는 왼쪽 부분식 안에 있습니다.

읽기에 혼동이 없을 때에는 최외곽 괄호를 생략하는 관례를 쓰기도 합니다. 이 편에서 구성 규칙을 확인하거나 괄호 수를 세는 연습을 할 때에는 두 식을 결합한 부분을 (A∧B)처럼 괄호까지 갖춘 모양으로 되돌려 봅니다. 양화사의 몸통과 연결 범위가 분명해야 합니다.

먼저 각 출현을 따로 봅니다. 아래 식 ∀x(R(x,y)∧∃xP(f(x)))에서는 바깥 ∀x와 안쪽 ∃x가 서로 다른 범위를 맡습니다. R 안의 x는 바깥 ∀x에 묶이고, f(x) 안의 x는 더 안쪽 ∃x에 묶입니다. y를 맡는 양화사는 없습니다.

그 x는 어느 변수를 묶겠다는 표시입니다. 자유변수를 찾을 때에는 몸통의 항 자리에 있는 출현이 어느 양화사에 묶이는지 봅니다. 양화사 자체의 변수 표시를 별도의 자유로운 대상 자리로 세지 않습니다.

자유롭게 나타나는 변수들의 집합을 FV라고 적겠습니다. 영어 free variables를 줄인 표시이며, 식의 의미를 분석하는 설명용 도구입니다. 예를 들어 FV(R(x,y))={x,y}입니다. 같은 변수가 여러 번 나와도 목록에는 한 번만 적고, 하나도 없으면 ∅를 씁니다.

네. f(x) 안의 x는 함수기호 때문에 숨거나 묶이지 않습니다. P(f(x))에서는 자유롭고, ∀xP(f(x)) 전체에서는 ∀x가 그 출현을 묶습니다. 무엇의 FV를 구하는지, 식 전체인지 몸통만인지 적어 두면 좋습니다.

그렇습니다. 자유변수가 없는 식을 문장, 또는 닫힌 식이라고 부릅니다. 닫혀 있다는 것은 변수의 열린 자리가 없다는 말이며, 참이라고 보증하는 말은 아닙니다. ∃xP(x)는 닫힌 문장이지만 제출자가 없는 해석에서는 거짓입니다.

문장인지 여부는 자유변수의 출현으로 정합니다. x=x에는 두 x를 묶는 양화사가 없으므로 FV가 {x}입니다. 열린 식도 모든 배정에서 같은 값을 가질 수 있습니다. 따라서 “값이 실제로 달라지는가”를 문장의 정의로 삼지는 않습니다.

A와 B는 우리가 만든 식 하나 전체를 대신하는 메타언어의 약칭입니다. 분석 대상인 언어를 대상 언어라고 하고, 그 언어를 설명하는 한국어와 약칭들을 메타언어라고 부릅니다. 예를 들어 “A가 식이면 ¬A도 식”이라는 설명에서 A에 P(a)를 넣으면 실제 대상 언어의 식 ¬P(a)를 얻습니다.

“A는 P(a)의 약칭”이라고 정하는 것은 표현을 가리키는 설명입니다. 대상 언어의 a=b는 두 이름이 같은 대상을 가리킨다는 식입니다. 혼동을 피하려고 이번 편에서는 약칭을 정할 때 말로 풀어 쓰겠습니다. 기호를 설명하는 문장 자체를 다시 그 대상 언어의 식이라고 생각하지 않아도 됩니다.

쓰입니다. 모든 원자식에 어떤 성질이 있고, 그 성질을 가진 작은 식들을 허용된 방식으로 결합할 때마다 성질이 유지된다면, 구성 규칙으로 만든 모든 식에도 그 성질이 있습니다. 이것을 식의 구조에 대한 귀납, 구조적 귀납이라고 부릅니다.

그래서 먼저 항에 대한 작은 증명을 합니다. 변수와 상수에는 괄호가 없으므로 두 수가 0으로 같습니다. t의 괄호 수가 같다면 f(t)는 여는 괄호와 닫는 괄호를 하나씩 더하므로 여전히 같습니다. 항을 만드는 모든 경우를 확인했으므로 모든 항의 괄호 수가 같습니다.

이제 작은 식 A와 B에 대해 두 수가 같다고 가정하고, 각각의 결합 규칙을 확인합니다. 이 가정은 이미 작은 구성들에 대해 확보한 성질을 다음 구성으로 이어 가기 위한 귀납 가정입니다. 처음부터 모든 식의 결론을 가정하는 것은 아닙니다.

네. 모든 식은 원자식에서 유한 번 구성된 것으로 정의했습니다. 출발점과 모든 구성 규칙에서 성질이 유지되므로 어느 완성된 식까지 가도 성질을 잃지 않습니다. 이것으로 이번 주장의 구조적 귀납 증명이 끝납니다.

문제를 풀 때에는 작은 질문부터 나누어 보세요. f의 입력이 항인지, P와 R의 자리에 알맞은 항이 들어갔는지, 두 식을 어떤 연결사로 묶었는지, 양화사가 어떤 출현을 맡는지 순서대로 확인하면 됩니다. 방금 만든 긴 식으로 다시 연습하겠습니다.

다음 3편에서는 이 구성 순서를 그대로 이용하여 항의 값과 식의 만족을 계산합니다. 이름과 함수의 해석을 정하고, 변수에 대상을 배정한 다음, 작은 항과 식에서 큰 식으로 올라갑니다. 오늘 익힌 구조가 의미를 계산하는 순서도 안내해 줄 것입니다.