[수리논리] 4. 술어 논리(Predicate Logic)

술어 논리는 원자 명제에 대해 술어(Predicate)와 술어를 제외한 나머지 항목에 대하여 나눈다. 술어는 인자로 술어를 제외한 나머지 항목인 술어 변수(Predicate Variables)를 받는다. 이는 기존 논리와 가장 큰 차별점이다. 술어 변수는 주어부나 목적부가 될 수 있으며, 임의의 대상에 대하여 기술할 수 있다. 술어 변수는 작은 음소문자로 술어는 큰 음소문자로 기입하여 \(P(x)\)와 같이 진리-함수(Truth-Function)로 나타낸다. 

 

술어 논리에서 원자 명제의 술어는 함수와 같이 표기한다. 이는 주어부가 변동되더라도 술어부 특징은 유지됨을 나타낸다. 예시로 "모든 사람은 필멸이고, 아리스토텔레스는 사람이기 때문에 아리스토텔레스는 필멸이다."라는 명제를 술어 명제로 표현하면 다음과 같다. 

 

\(M(x) := All \; x \; is \; Mortal\)

\(H(x) := Some\;  x\;  is \;Human\)

\( (M(Human) \wedge  H(Aristotelis)) \rightarrow M(Aristotelise)\)

 

예시에서 \(M(x)\)를 정의하였다. x라는 자유 변수는 어떠한 것이더라도 치환이 된다. 따라서 \(M(Human)\)은 \( All \; Human \; is \; Mortal \)과 동치가 된다. 위와 같은 명제에 사용된 함수를 한 자리 술어(One-Place Predicate )라고 한다. 한자리 술어는 표현이 한정적이라 불편하다. 이를 확장한 것이 N 자리 술어(n-Place Predicate)이다. \(P_0^n, P_1^n, P_2^n,...,\)와 같이 총인수의 개수를 윗 첨자로 사용하며 아래 첨자는 함수 또는 인수 구분이다. 위 명제를 2자리 술어를 사용하면 다음과 같다.

 

\( A(x, y) := All \; x \; is \; y \)

\( B(x, y) :=Some \;x\; is\; y \)

\(h:=Human\)

\(a:=Aristotelis\)

\(m:=mortal\)

\( (A(h, m) \wedge B(a, h)) \rightarrow B(a, m) \)

 

2자리 술어를 사용했음에도 불구하고, 예제에서는 같은 내용에 대한 함수가 중복으로 생긴다. 이는 양에 대한 표현을 함수 밖에서 할 수 없기 때문이다. 따라서 한정자를 사용하는데, 한정자는 기존 논리에서 량에 대한 표기법이다.

• "For All"을 뜻하는 기호로 "\( \forall \) " 가 있으며 보편적 한정(Universal Quantification)
• "There Exist"을 뜻하는 기호로 "\( \exists \)"가 있으며 실존적 한정(Existential Quantification)
• "There Exist Exactly One"을 뜻하는 기호로 "\( \exists! \)"가 있으며 고유적 한정(Uniqueness Quantification)

 한정자는 함수에 들어가는 인수를 한정을 할 수 있다. 표기 방법은 함수 앞에 기입하고 아래 첨자로 인수를 표기하면 된다. 예시는 다음과 같다.

$$C(x, y) := x \;is \;y$$

$$h:=Human$$

$$a:=Aristotelis$$

$$m:=mortal$$

$$  ( \forall_h C(h, m) \wedge C(a, h)) \rightarrow C(a, m) $$

 

예제에서 모든 변수 \(h\)는 \(C(h,m)\)을 만족한다는 표현으로 \( \forall_h C(h, m) \) 항이 만들어 졌다. 변수 \(h\)는 함수 \(C\)안에서 모두 포함되기 때문에 변수 \(h\)는 함수 \(C\)에 대해 묶여(Bound) 있고 변수 \(m\)은 한정자로 묶여 있지 않기 때문에 함수 \(C\)에 대해 자유(Free)롭다고 표현된다. 일반적인 표현에서 변수는 함수에 대해 자유롭지만, 한정자나 조건에 의해서 특정 변수는 함수에 대해 묶여 있을 수 있다. 묶여 있는 변수는 보다 자세히 기술하려 표현하는 방법중의 하나이지 이해를 방해하는 요소는 아니다. 

 

아직까지 함수 C에 대한 정의는 자연어로 표현되고 있다. 이제 진리를 객관적으로 표현하고자 등호를 사용하여 두 변수 간의 평등한(Equality) 관계를 기술한다. 등호를 사용하기 때문에 원자 명제는 원자 식(Atomoic Formula)라고 한다.

 

$$C(x, y) := (x = y)$$

$$h:=Human$$

$$a:=Aristotelis$$

$$m:=mortal$$

$$  ( \forall_h C(h, m) \wedge C(a, h)) \rightarrow C(a, m) $$

$$  ( \forall_h (h=m) \wedge (a=h)) \rightarrow (a=m) $$

 

이로써 명제를 자연어보다 구체적인 정형 언어로 표현할 수 있게 된다. 이를 이용한 술어 논리에는 몇 가지 속성이 있다. 논리적 등가(Logical equivalence) 속성이 대표적인데 여기서는 하기 표로 간단하게 정리하고 넘어간다. 하기 표의 \( p\)와\(q\), \(r\)은 임의의 술어 변수이고 \( \Phi \)는 임의의 함수이다. 이 계념은 술어 변수 뿐만 아니라 원자 식에도 해당 된다. (\( \neg\)는\( \overline{ }\)으로 표현된다.)  

구분	등가 식
교환 (Communitative)	$$ \begin{align}p \vee q \equiv q \vee p \\p \wedge q \equiv q \wedge p \end{align}$$
연관 (Associative)	$$ \begin{align}(p \vee q) \vee r \equiv p \vee (q \vee r) \\ (p \wedge q) \wedge r \equiv p \wedge (q \wedge r) \end{align}$$
분배 (Distributive)	$$ \begin{align}p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r) \\ p \wedge (q \vee r) \equiv (p \wedge r) \vee (p \wedge r) \end{align}$$
멱등 (Idempotent)	$$ \begin{align}p \vee p \equiv p \\ p \wedge p \equiv p \end{align}$$
드모르간 (De Morgan)	$$ \begin{align} \overline{p \vee q} \equiv \overline{p} \wedge \overline{q} \\ \overline{p \wedge q} \equiv \overline{p} \vee \overline{q} \end{align}$$
역 (Inverse)	$$ \begin{align} p \vee \overline{p} \equiv T \\ p \wedge \overline{p} \equiv T \end{align}$$
항등 (Identity)	$$ \begin{align} p \vee F \equiv p \\ p \wedge T \equiv p \end{align}$$
지배 (Domination)	$$ \begin{align} p \vee T \equiv T \\ p \wedge F \equiv F \end{align}$$
귀결 (Implication)	$$ \begin{align} p \rightarrow q \equiv \overline{q} \rightarrow \overline{p} \end{align}$$
분리로서 귀결 (Implication as a Disjunction)	$$ \begin{align} p \rightarrow q \equiv \overline{p} \vee q \end{align}$$
귀결의 부정 (Negation of an Implication)	$$ \begin{align} \overline{p \rightarrow q} \equiv p \wedge \overline{q} \end{align}$$
한정자 (Quantification)	$$ \begin{align} \exists_p \Phi(p) \equiv \overline{\forall_p (\overline{ \Phi(p)})} \end{align}$$

해석 및 평가 순서는 다음을 따른다.

1. \( \neg\) 먼저 평가
2. \( \wedge, \; \vee \) 평가
3. \( \forall \)과 같은 수량자 평가
4. \( \rightarrow \)와 같은 관계 평가

예시는 다음과 같다.

 

$$ \forall_x(\neg P(x)) \rightarrow \exists_x(F(x) \vee G(x))$$

$$ \forall_x(P(x)는\;아니다.) \rightarrow \exists_x(F(x) \vee G(x)) $$

$$ \forall_x (P(x)는\;아니다.) \rightarrow \exists_x (F(x)이고\;G(x)이다.) $$

$$ 모든 \;x는\; P(x)가\; 아니다. \rightarrow F(x)이고\; G(x)인\; x가\; 존재한다. $$

$$ (모든 x는\; P(x)가\; 아니다.)이면 (F(x)이고\; G(x)인\; x가\; 존재한다.)이다. $$

 

이처럼 술어 논리는 기존 논리와 다르게 거의 대부분을 객관적으로 묘사할 수는 있다. 하지만 한계는 존재한다. 다음 명제로 예시를 설명하자.

 

$$ c \; := \; Crowd$$

$$ m \; := \; a \; Man$$

$$ (\exists_{c})(c \rightarrow m) $$

 

라는 명제는 술어 논리에서 참과 거짓을 논하기 힘들다. 왜냐하면 "군중이 존재하면 한 사람이 있다."라는 명제의 참과 거짓을 파악하기 위해서, 군중과 한 사람의 관계를 알아야 한다. 우리는 군중(Crowd) 속성과 한 사람(a Man) 속성에 대한 관계를 관념적으로는 알 수 있지만, 명제 자체적으로는 알 수 없기 때문이다.  

따라서 2차 논리(2nd-Order Logic)는 1차 논리를 확장하여, 이러한 문제를 해결하였다. 2차 논리에 들어가기 앞서, 2차 논리에 포함된 집합론(Set Theory)의 개념을 알아 가보자 한다. 집합론은 1차 논리를 확장하여 객체 간의 관계를 탐구하는 학문이다.

 

참고 문헌

1. MOSLEY, Albert; BALTAZAR, Eulalio. An Introduction to Logic: From Everyday Life to Formal Systems. 2019.
2. WEISS, William AR. An introduction to set theory. University of Toronto, 2008, 119.

참고 사이트

1. Wikipedia contributors. First-order logic [Internet]. Wikipedia, The Free Encyclopedia; 2022 Aug 17, 03:40 UTC [cited 2022 Aug 28]. Available from: https://en.wikipedia.org/w/index.php?title=First-order_logic&oldid=1104829708.
2. Wikipedia contributors. List of logic symbols [Internet]. Wikipedia, The Free Encyclopedia; 2022 May 24, 23:21 UTC [cited 2022 Aug 17]. Available from: https://en.wikipedia.org/w/index.php?title=List_of_logic_symbols&oldid=1089645787.
   
3. Agnishom Chattopadhyay and Eric Bullingtoncontributed, contributed, Predicate Logic [Internet], BRILLIANT; 2022 Jul 18, 19:12 UTC [cited 2022 Aug 15]. Available from:https://brilliant.org/wiki/predicate-logic/
4. Harris Kwong contributed, Logical Equivalences [Internet] , Methematics LibreTexts; 2022 Jul 18, 19:12 UTC [cited 2022 Aug 15]. Available from:https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/2%3A_Logic/2.5%3A_Logical_Equivalences