술어논리(4) ㅡ 문장규칙

 술어논리는 명제논리와 다르게, 문장만 있는 것이 아니라 식(formula)이 있고 식 중에 일부를 문장이라고 부릅니다. 이를 위해선 항, 원자식, (일반)식, 문장의 단계를 거쳐가야 합니다.

1. 항(term)

 '_는 소수이다'를 P_로 나타낸다고 할 때, 결국 언젠가 _에 들어가서 개체로서 의미를 지닐 수 있게 될 수 있는 가능성을 지닌 대상들을 항(term)이라고 부릅니다. 여기엔 개체상항, 변항, 그리고 두 개에 함수기호를 적용해서 만들어지는 (일반)항이 옵니다. 가령 a는 자연수 2를 가리킨다고 생각하면, Pa는 참인 문장이 되겠죠. Px에서 비록 x는 자리만 채워주는 역할만 하짐나 x에 어떤 수를 대입시켜 Pa 같이 만든다고 생각한다면 대입의 관점에서 x는 그 자체로는 아무 의미도 없지만 간접적으로 개체의 기능을 만든다고 볼 수도 있겠습니다. 그리고 만약 b가 3이라고 하고 fxy를 x+y로 생각한다면, Pfab는 5가 소수라는 의미를 지니게 될 것입니다. 또한 gxy를 x곱하기 y로 생각한다면, $Pg_{faafbb}$는  4x9=36이 소수라는 의미가 될겁니다. 함수는 여러번 적용하는 게 가능합니다.

 일반적으로 정의하면

(i)변항은 항이다
(ii)개체상항(individual constant = a, b, c, ...)은 항이다
(iii)f가 n항 함수기호이고, $t_1, t_2, ..., t_n$이 항이면, $f_{t_1 t_2 ... t_n}$도 항이다.

 입니다. 이 외의 규칙에 의해 만들어진 건 항이 아닙니다. 식이 복잡해 보이지만 결국 변항과 개체상항에 함수기호를 0번, 1번, 2번, ... 적용한 것들이 모두 항이라는 의미입니다. 위의 식에서 g(f(a,a),f(b,b))같이 왜 좀더 보기쉽게 쓰지 않느냐고 물으신다면 몇 가지 여기서 밝히기 어려운 수학적 이유가 있습니다만 크게 중요한 건 아니고, 관례적으로 이렇게 굳어졌기 때문에 이렇게 쓴다고 보시면 됩니다.

2. 원자식(atomic formula)

 원자식은 양화사나 논리적 연결사가 없이 항이 달려있는 술어기호의 형태를 뜻합니다. 위에서 Pa Pb, Pfab ... 등이 모두 원자식입니다. 엄밀하게는, $P$가 n항 술어기호이고, $t_1, ..., t_n$이 항이면 $P_{t_1 t_2 ... t_n}$은 원자식입니다. 보시는 책에 따라 다르긴 하지만 일반적으로 동일성기호(등호)=도 술어기호로 인정하기 때문에, t1 t2가 항일 때 t1=t2는 언제나 

원자식이 됩니다.

3. 식(formula)

 식은 원자식에 적합한 괄호삽입에 의한 논리적 연결사, 양화사의 작용으로 만들어지는 표현을 뜻합니다. 쉽게 말해, 원자식들에다가 not, and, or, ... 등과 for all, exists 등을 넣어서 만들어지는 식들을 의미합니다. 엄밀히 말하면,

(i)원자식은 식이다
(ii)A,B가 식이면, 명제논리의 문장생성규칙에 의해 만들어지는 식들은 모두 식이다.
즉, (~A), (A→B), (A∧B), (A∨B), (A↔B)는 모두 식이다.

(iii) x가 변항이고 A가 식일 때, ∀xA, ∃xA는 식이다.

 마지막으로 이 규칙을 따르지 않은 표현은 식이 아닙니다. 식은 Px나 Px→∃yFxy같이 변항이 아무런 제한 없이 남아있어서 참/거짓을 판별할 수 없는 식들이 있는가하면, ∀xPx와 ∀x(Px→∃yFxy)같이 변항을 양화하여 특정 해석 하에서 참/거짓을 가릴 수 있는 식들이 있습니다. 좀더 엄밀히 말하면, 전자는 '변항 x가 자유롭게 나타나는 식'이고 후자는 '변항 x가 자유롭게 나타나지 않는 식입니다. 자유롭게 나타난다는 것은 양화사에 의해 제한되지 않아서 아무 의미를 지니지 않은 채로 남아있다는 것입니다. 우리는 어떤 변항도 자유롭게 나타나지 않을 때, 즉 모든 변항이 양화사에 의해 속박되어 있을 때를 문장이라고 부릅니다. 식 중에 문장만은 참/거짓을 논할 수 있는 대상이 됩니다. 직관적으로는 각 술어에 의미를 대입해서 일상적인 의미를 파악한다고 할 때 미지수가 남아있어서 해석의 빈공간이 생기느냐 아니냐로 판단하시면 됩니다.

 좀더 엄밀하게는, 이렇게 정의합니다.

(i)원자식의 변항은 모두 자유롭게 나타난다

(ii)A가 식일 때, (~A)의 자유로운 변항의 집합은 A의 자유로운 변항의 집합과 같다
(iii)A,B가 식일 때, (A→B), (A∧B), (A∨B), (A↔B)의 자유로운 변항은 A의 자유로운 변항들의 집합과 B의 자유로운 변항들의 집합을 합집합한 것이다

(iv)A가 식일 때 ∀xA, ∃xA의 자유로운 변항들의 집합은 A의 자유로운 변항들의 집합에서 x를 뺀 것이다.

(v)A가 식일 때, A에 자유로운 변항이 없으면, 즉 자유로운 변항의 집합이 공집합일 때 A를 문장이라고 정의한다.

 의미는 위에서 말한 것과 같습니다. Pt1...tn 형태에서는 양화사가 없기 때문에 변항이 있어도 양화사에 의해 속박되지 않으므로 모든 변항이 자유롭습니다. 그러나 변항이 없는 경우는 자유로운 변항도 없게 되니까 문장이 됩니다. 즉, Pa Pb는 문장이고 Fay에서 y가 자유롭기 때문에 Fay는 문장이 아닌 식입니다.

 논리적 연결사는 양화사를 더하는 것이 아니기 때문에 연결사에 의해 자유로운 변항이 변동되는 경우가 없고 따라서 연결되는 식들의 자유변항들을 그저 다 더하면 됩니다. 특정 변항에 대해 양화사가 비로소 추가되면 자유로웠던 변항이 속박되게 되겠죠. 

 다음 시간엔 해석에 대해서 살펴봅시다.