1.17 양화 논리(Quantificational Logic)와 명제 함수의 형식화

1. 명제 논리의 한계와 양화 논리의 필요성

명제 논리(Propositional Logic)는 명제를 분해 불가능한 원자 단위로 취급하며, 명제의 내부 구조를 분석하지 않는다. 이 한계로 인해 명제 논리는 다음과 같은 유형의 추론을 형식화할 수 없다.

“모든 인간은 필멸적이다. 소크라테스는 인간이다. 따라서 소크라테스는 필멸적이다.”

이 삼단논법에서 전제와 결론 사이의 논리적 연관은 “인간”, “필멸적”, “소크라테스“라는 명제의 내부 구성 요소에 의존한다. 명제 논리에서 이 세 문장은 단순히 세 개의 독립적인 명제 변수 $p$ , $q$ , $r$ 로 표현되며, 이들 사이의 논리적 연관은 포착되지 않는다.

양화 논리(Quantificational Logic), 즉 술어 논리(Predicate Logic)는 명제의 내부 구조를 술어, 개체 항, 양화사로 분해하여 분석함으로써 이 한계를 극복한다.

2. 명제 함수(Propositional Function)의 개념

명제 함수는 하나 이상의 변수를 포함하는 표현으로서, 변수에 특정 값이 대입되면 하나의 명제(참 또는 거짓인 진술)가 되는 함수이다. 현대적 용어로는 술어(Predicate) 또는 열린 문장(Open Sentence)이라 한다.

2.1 형식적 정의

$n$ -항 명제 함수(또는 $n$ -항 술어)는 논의 영역(Domain of Discourse) $D$ 에서 진리값의 집합 $\{T, F\}$ 로의 함수이다:

$P: D^n \rightarrow \{T, F\}$

1-항 명제 함수 $P(x)$ 는 변수 $x$ 에 $D$ 의 원소를 대입하면 참 또는 거짓의 명제를 산출한다. 예를 들어, 논의 영역이 자연수이고 $P(x)$ 가 “ $x$ 는 소수이다“일 때:

$P(2)$ = 참
$P(4)$ = 거짓
$P(7)$ = 참

2-항 명제 함수 $R(x, y)$ 는 두 변수에 값을 대입하면 명제가 된다. “ $x$ 는 $y$ 보다 크다“를 $G(x, y)$ 로 표기하면:

$G(5, 3)$ = 참
$G(2, 7)$ = 거짓

자유 변수와 속박 변수

명제 함수에서 양화사에 의해 지배되지 않는 변수를 자유 변수(Free Variable)라 하고, 양화사에 의해 지배되는 변수를 속박 변수(Bound Variable)라 한다.

$P(x)$ 에서 $x$ 는 자유 변수이다. 이 표현은 명제가 아니라 명제 함수이다.

$\forall x \, P(x)$ 에서 $x$ 는 속박 변수이다. 이 표현은 완전한 명제이며, 참 또는 거짓의 진리값을 갖는다.

$\forall x \, R(x, y)$ 에서 $x$ 는 속박 변수이고 $y$ 는 자유 변수이다. 이 표현은 $y$ 에 대한 명제 함수이다.

모든 변수가 속박된 논리식을 폐쇄식(Closed Formula) 또는 문장(Sentence)이라 하며, 자유 변수가 존재하는 논리식을 개방식(Open Formula)이라 한다.

전칭 양화(Universal Quantification)

정의

전칭 양화사 $\forall$ (“모든 $x$ 에 대하여”)는 명제 함수 $P(x)$ 가 논의 영역 $D$ 의 모든 원소에 대해 참임을 주장한다:

$\forall x \, P(x) \equiv P(d_1) \wedge P(d_2) \wedge P(d_3) \wedge \cdots$

논의 영역이 유한한 경우 $D = \{d_1, d_2, \ldots, d_n\}$ , 전칭 양화는 논리곱의 유한 전개와 동치이다:

$\forall x \, P(x) \equiv \bigwedge_{i=1}^{n} P(d_i)$

논의 영역이 무한한 경우, 전칭 양화는 무한 논리곱의 논리적 의미를 갖되, 유한하게 표현 가능하다. 이 점이 양화사의 결정적 표현력 이점이다.

전칭 양화의 논리적 성질

전칭 예화(Universal Instantiation): $\forall x \, P(x)$ 로부터, 임의의 특정 값 $a \in D$ 에 대해 $P(a)$ 를 도출할 수 있다.
전칭 일반화(Universal Generalization): $P(a)$ 가 $a$ 에 대한 어떤 특수한 가정도 없이(임의의 $a$ 에 대해) 증명되었으면, $\forall x \, P(x)$ 를 도출할 수 있다.

존재 양화(Existential Quantification)

정의

존재 양화사 $\exists$ (“어떤 $x$ 가 존재하여”)는 명제 함수 $P(x)$ 가 논의 영역 $D$ 의 적어도 하나의 원소에 대해 참임을 주장한다:

$\exists x \, P(x) \equiv P(d_1) \vee P(d_2) \vee P(d_3) \vee \cdots$

유한 논의 영역에서:

$\exists x \, P(x) \equiv \bigvee_{i=1}^{n} P(d_i)$

존재 양화의 논리적 성질

존재 예화(Existential Instantiation): $\exists x \, P(x)$ 로부터, $P(c)$ 를 만족하는 특정 원소 $c$ (스콜렘 상수, Skolem Constant)의 존재를 가정할 수 있다.
존재 일반화(Existential Generalization): 특정 값 $a$ 에 대해 $P(a)$ 가 참이면, $\exists x \, P(x)$ 를 도출할 수 있다.

양화사 사이의 논리적 관계

전칭 양화사와 존재 양화사는 부정을 통해 상호 정의 가능하다:

$\neg \forall x \, P(x) \equiv \exists x \, \neg P(x)$
$\neg \exists x \, P(x) \equiv \forall x \, \neg P(x)$
$\forall x \, P(x) \equiv \neg \exists x \, \neg P(x)$
$\exists x \, P(x) \equiv \neg \forall x \, \neg P(x)$

이 관계들은 양화사에 대한 드모르간 법칙(De Morgan’s Laws for Quantifiers)으로 불린다. 전칭 양화와 논리곱, 존재 양화와 논리합 사이의 구조적 유사성을 반영한다.

다중 양화(Multiple Quantification)

복수의 양화사가 중첩된 논리식의 의미론은 양화사의 순서에 결정적으로 의존한다.

동종 양화사의 교환

동일한 종류의 양화사는 교환 가능하다:

$\forall x \, \forall y \, P(x, y) \equiv \forall y \, \forall x \, P(x, y)$
$\exists x \, \exists y \, P(x, y) \equiv \exists y \, \exists x \, P(x, y)$

이종 양화사의 비교환성

상이한 종류의 양화사는 일반적으로 교환 불가능하다:

$\forall x \, \exists y \, P(x, y) \not\equiv \exists y \, \forall x \, P(x, y)$

$\forall x \, \exists y \, P(x, y)$ 는 “모든 $x$ 에 대해, (그 $x$ 에 의존하는) 어떤 $y$ 가 존재하여 $P(x, y)$ 가 성립한다“를 의미한다. $\exists y \, \forall x \, P(x, y)$ 는 “모든 $x$ 에 대해 동시에 $P(x, y)$ 를 만족하는 단일한 $y$ 가 존재한다“를 의미한다. 후자가 전자를 함의하나( $\exists y \, \forall x \, P(x,y) \Rightarrow \forall x \, \exists y \, P(x,y)$ ), 역은 일반적으로 성립하지 않는다.

예를 들어, “모든 사람에게는 어머니가 있다”( $\forall x \, \exists y \, \text{Mother}(y, x)$ )는 참이나, “모든 사람의 어머니인 한 사람이 존재한다”( $\exists y \, \forall x \, \text{Mother}(y, x)$ )는 거짓이다.

3. 일차 술어 논리(First-Order Predicate Logic)

양화 논리의 표준 체계인 일차 술어 논리(First-Order Predicate Logic, FOL)에서 양화사는 개체 변수(Individual Variable)에만 적용된다. 술어 자체나 함수에 대한 양화는 허용되지 않는다.

3.1 일차 술어 논리의 형식적 언어

일차 술어 논리의 형식 언어는 다음의 기호로 구성된다:

개체 변수(Individual Variables): $x, y, z, \ldots$
개체 상수(Individual Constants): $a, b, c, \ldots$
술어 기호(Predicate Symbols): $P, Q, R, \ldots$ (각각 정해진 항수를 가짐)
함수 기호(Function Symbols): $f, g, h, \ldots$ (선택적)
논리 연결사: $\neg, \wedge, \vee, \rightarrow, \leftrightarrow$
양화사: $\forall, \exists$
등호: $=$ (선택적)

3.2 항(Term)의 정의

개체 변수와 개체 상수는 항이다.
$f$ 가 $n$ -항 함수 기호이고 $t_1, \ldots, t_n$ 이 항이면, $f(t_1, \ldots, t_n)$ 은 항이다.

3.3 적격식(Well-Formed Formula, WFF)의 정의

$P$ 가 $n$ -항 술어 기호이고 $t_1, \ldots, t_n$ 이 항이면, $P(t_1, \ldots, t_n)$ 은 원자식(Atomic Formula)이다.
$\phi$ 가 적격식이면, $\neg \phi$ 도 적격식이다.
$\phi$ 와 $\psi$ 가 적격식이면, $(\phi \wedge \psi)$ , $(\phi \vee \psi)$ , $(\phi \rightarrow \psi)$ , $(\phi \leftrightarrow \psi)$ 도 적격식이다.
$\phi$ 가 적격식이고 $x$ 가 변수이면, $\forall x \, \phi$ 와 $\exists x \, \phi$ 도 적격식이다.

4. 양화 논리의 의미론

4.1 해석(Interpretation)과 모형(Model)

일차 술어 논리의 의미론은 해석 구조(Interpretation Structure) $\mathcal{I} = (D, I)$ 에 의해 정의된다. 여기서 $D$ 는 비어 있지 않은 논의 영역이고, $I$ 는 해석 함수로서:

각 개체 상수 $c$ 에 $D$ 의 원소 $I(c) \in D$ 를 대응시킨다.
각 $n$ -항 술어 기호 $P$ 에 $D^n$ 의 부분집합 $I(P) \subseteq D^n$ 을 대응시킨다.
각 $n$ -항 함수 기호 $f$ 에 함수 $I(f): D^n \rightarrow D$ 를 대응시킨다.

4.2 만족 관계(Satisfaction Relation)

해석 $\mathcal{I}$ 와 변수 할당(Variable Assignment) $\sigma$ 에 대해, 논리식 $\phi$ 의 진리값은 재귀적으로 정의된다:

$\mathcal{I}, \sigma \models P(t_1, \ldots, t_n)$ iff $(\sigma(t_1), \ldots, \sigma(t_n)) \in I(P)$
$\mathcal{I}, \sigma \models \neg \phi$ iff $\mathcal{I}, \sigma \not\models \phi$
$\mathcal{I}, \sigma \models \forall x \, \phi$ iff 모든 $d \in D$ 에 대해 $\mathcal{I}, \sigma[x \mapsto d] \models \phi$
$\mathcal{I}, \sigma \models \exists x \, \phi$ iff 어떤 $d \in D$ 에 대해 $\mathcal{I}, \sigma[x \mapsto d] \models \phi$

5. 양화 논리의 표현력과 인공지능에의 응용

일차 술어 논리는 기호주의 인공지능(Symbolic AI)의 핵심적 지식 표현 언어이다. 세계에 대한 지식을 술어, 개체, 양화사로 표현하고, 논리적 추론 규칙에 의해 새로운 지식을 도출하는 것은 기호주의 인공지능의 근본 방법론이다.

프롤로그(Prolog) 프로그래밍 언어는 일차 술어 논리의 호른 절(Horn Clause) 부분집합에 기반한 논리 프로그래밍 언어이며, 전문가 시스템의 지식 표현과 추론에 직접적으로 활용되었다. 데이터베이스 질의 언어인 SQL의 WHERE 절 또한 일차 술어 논리의 양화 구조에 기반한다.

양화 논리는 명제 함수의 형식화를 통해 세계에 대한 구조화된 지식의 표현과 기계적 추론을 가능하게 한 이론적 체계이며, 현대 인공지능의 논리적 기반을 구성하는 핵심적 형식 도구이다.