Artificial Intelligence - 서술 논리(Predicate logic)에 대하여

서술 논리라 함은 1차 서술 논리(first-order Predicate Logic)라고도 하는데 아주 강력한 심볼릭 언어이다. 명제논리보다 훨씬 더 표현력이 강해서 복잡할 수 있지만 전반적인 흐름은 비슷하다.

가령 명제논리에서 로봇-7이 로봇-12보다 오른쪽에 있다는 객체들의 관계를 표현하기에 어렵다. (로봇과 좌표가 많은 경우 따져야하는 경우의 수가 너무 많아지기 때문이다.)
ex) 로봇 7이 (x,y)좌표 (35,79)에 존재한다. 로봇 12가 (x,y)좌표 (10,93)에 있다....


서술 논리(First-order Predicate Logic)의 정의

서술 논리의 문법을 정의하기 위하여 먼저 Term을 정의한다. Term은 세상이 객체(Object)들로 구성되었다고 가정하면 이 객체를 가리키는 혹은 표현하는 언어의 일부이다. 이를 이용하여 추후에 문장(Formula)를 구성하게 된다.

Term은 3가지의 방법으로 사용된다.

첫째는 constant term으로, 예를 들어 John, Mary 등과 같이 세상의 객체인 John이라는 남자, Mary이라는 여자를 가리키는 의미로 사용할 수 있다. John과 Mary 앞의 정의 K 라는 집합에 원소가 될 수 있다.

두번째 방법으로 변수(variable) term으로, 예를 들어 x, y, z 등을 변수 심볼이라 하면, 이 변수들은 앞의 정의에서 사용한 집합 V의 원소들이 된다. 변수 term 들도 세상의 객체를 가리켜야 한다. 예를 들어 변수 x를 John이라는 남자를 가리키게 할 수도 있고 Mary라는 여자를 가리키는 변수로 사용할 수도 있다.

세번째로 함수(function) term이 있다. 물론 함수 term도 세상의 객체를 가리켜야 한다. 예를 들어 John의 아버지를 표현할 때 함수 term, father-of(John)로 표현할 수 있겠다. 물론 father-of(John)도 john의 아버지 객체를 가리킨다. 이때 father-of는 function symbol로 argument 1개를 갖는 함수 심볼로 앞의 정의 F 집합의 한 원소가 되며, 함수 f(x)의 뜻은 x의 아버지를 나타낸다. 이러한 함수를 1-place function이라고 한다. 

함수의 argument도 반드시 term이어야만 한다. Term은 상수, 변수, 함수 term이 되므로 재귀적(recursive)으로도 사용할 수 있다. 예를 들어 John의 아버지의 아버지는 father-of(father-of(John))으로 표현할 수 있으며 이 함수 term은 John의 할아버지인 객체를 나타낸다.

서술논리의 집합 P는 다음과 같이 정의된다.

서술 논리의 문장(Formula)는 객체와 객체의 관계를 표현하는데 사용되며, 이러한 관계를 나타내는 심볼을 Predicate symbol이라고 한다. 예를 들어 John이 Mary를 사랑(loves)한다면 loves(John, Mary)로 표현 할 수 있는데 John과 Mary는 상수 term이고, loves는 2개의 argument(term)를 갖는 2-place predicate symbol이다. 이 때 loves는 앞에서 정의 한 집합 P 의 원소가 된다.

또한 function term과 혼동하지 말아야 할 것은 predicate는 서술 논리의 문장인 formula를 만들며 John과 Mary의 관계, 즉 John이 Mary를 사랑하는 관계를 나타내며, 이 문장은 참일 수도 거짓일 수도 있다. 반편 함수 term, 예를 들어 father-of(John)은 객체를 나타내어 predicate의 argument 혹은 function의 argument로 사용되므로 관계를 나타내는데 사용될 수 없다. 만약 어떤 사람이 Smith가 John의 아버지라는 관계를 말하고 싶다면 관계를 나타내는 predicate, 예를 들어 2-place predicate symbol is-a-father-of를 사용하여 is-a-father-of(Smith, John) 표현할 수 있다.


그렇다면 서술 논리로 명제를 표현해보자.
명제 : 똘똘이는 개이다. 개는 달릴 수 있다.

똘똘이는 개이다.
constant symbol : 똘똘이
1-place predicate symbol : Dog(x) ; x is dog
Formula : Dog(똘똘이)

개는 달릴 수 있다.
1-place predicate symbol : Runable(x) ; x can run
Formula : ∀x Dog(x) ⇒ Runable(x)

명제에서 개를 constant라고 한다면 세상에는 개가 한마리 밖에 존재하지 않으므로 개는 1-place predicate symbol로 정의하여 Dog(x), 즉 개들의 집합으로 본다. 반면에 똘똘이(term)는 하나의 객체를 의미한다.
만약에 개를 constant로 사용하여 Runable(개)라고 표현하면 세상에 개는 한마리만 있는 세상에서나 가능한 이야기다.

즉 ∀x Dog(x) ⇒ Runable(x)로 정의할 수 있다.(모든 x에 대해서 x가 개라면 달릴 수 있다.)

그렇다면 ∀x Dog(x) ∧ Runable(x)는 왜 안될까?
모든 x에 대해서 x는 개이고 개는 달릴 수 있다. 이 말은 세상에 개만 존재하는 세상이라면 어울릴 수 있겠지만 그게 아니기 때문에 ∧(conjunction)로 표현하면 어색한 표현이 될 수 있다.
정리하면 ∀x Dog(x) ⇒ Runable(x)는 개는 달릴 수 있다는 의미에 가깝지만 ∀x Dog(x) ∧ Runable(x)는 세상에 모든 것은 개이고 개는 달릴 수 있다 라는 의미에 가깝다.

다음은 다양한 예이다.

이외에도 앞서 포스팅했던 명제논리 편에서 설명했던 Formula에 적용되는 용어인 valid, satisfiable, unsatisfiable, model, entailment 등 또한 모두 똑같이 통용된다.



한가지 예를 들어서 상기시켜보자.
John loves Mary
John's brother loves Mary's sister.

온톨로지를 정의하면
Constant symbols : John, Mary
1-place function symbol: brother-of(x) ; brother of x / sister-of(x) ; syster of x
2-place predicate symbol: love(x,y) ; x loves y.

love(John,Mary)
love(brother-of(John),sister-of(Mary))

객체로는 John, Mary, John's brother, Mary's sister 등이 존재할 것이고 매핑함수 현실세계 W와 논리세계를 매핑해주는 함수 I는 저 객체들을 가리킬 것이다.

한번 더 해보자
다음은 소크라테스 문제이다.
KB = {∀x man(x) ⇒ mortal(x), man(Socrates)}
KB |= mortal(Socrates) ? 답은 yes.

man(Socrates) ⇒ mortal(Socrates)
≡ ┐man(Socrates) ∨ mortal(Socrates)
따라서 ┐man(Socrates) 가 false이기 때문에 mortal(Socrates) is true가 된다.

위에서 설명된 내용은 모두 집합이라고 보고 이를 집합에 의한 의미론이다 하여 Set theoretic Semantics 혹은 객체를 가리킨다 하여 Denotation Semantics 이라고 불리기도 한다.




가족 관계 트리를 보자.

사람들의 이름이 상수 term이 되고 2개의 predicate symbol을 정의했다.
1-place predicate female(x): x is a female
3-place predicate child(x, y, z): x is a child of y and z

Karen은 여자이고 Oscar A는 karen과 franz의 자식이다 라는 표현을 서술 논리 formula로 female(karen), child(oscar A. karen, franz) 로 정의했다. 소문자 karen은 서술 논리에서 사용하는 상수 symbol이고 대문자 Karen은 World에 존재하는 객체 Karen을 나타내기 위해 구분하였다.

Kind는 child를 말한다. (책이 독일어가 가끔씩 나온다.)

child(eve, anne, oscar)는 그림에서 보듯 참이다. 그럼 child(eve, oscar, anne)가 참이 되려면 무슨 지식이 더 필요할까? 위에 가족관계 트리 아래쪽에 Relation에 없는 것을 보니 바로 True로 하면 안될 것 같다.

명제 논리에서 설명한 A ⇔ B : A if and only if B (equivalence) A가 참이면 B도 참, B가 참이면 A도 참 이라는 지식이 더 필요하다.

그리고 descendant라는 함수를 통해 x는 y의 후손이다 라는 것을 정의할 수 있다.

x는 y, z는 아이인데 그런 z가 존재하거나 또는 x가 u, v의 자식이고 u는 y의 후손이다라고 reculsive하게 정의할 수 있다.

마침내 아래처럼 Knowledge Base를 정이하여 child(eve, oscar, anne)도 참이라는 결론을 Derivation 할 수 있다.

서술 논리에서도 명제 논리처럼 entail하는지 계산할 수 있는 derivation 프로그램인 theorem prover가 필요하다. 이를 위하여 궁극적으로 resolution-refutation 방법을 사용하기 위하여는 먼저 CNF(Conjunctive Normal Form)으로 변환하여야한다. 이를 위해 서술 논리에서는 명제 논리에 없는 한정사를 제거하는 과정이 필요하다. 먼저 prenex normal form으로  만들고, existential quantifier를 skolemization을 이용하여 제거하고 최종적으로 universal quantifier 제거하게 된다. 또한 unification process도 필요하다.



반면에 서술 논리에서 term을 사용하여 객체를 나타내게 되는데 우리 종종 같은 객체를 다른 이름으로 사용하는 경우가 많다. 예를 들어 John's father를 function term으로 father-of(john)이라고 표현할 수도 있지만, John's father가 Smith라고 한다면, 우리는 쉽게 father-of(john) = smith라는 관계를 표현 할 수 있다.  이 때 = symbol을 어떻게 처리할 것인가 하는 문제가 생긴다. 한 가지 방법은 = symbol을 predicate symbol로 간주하는 경우이다 (물론 이 때 문법은 일반 predicate와 다르게 양쪽에 term이 오는 형식으로 2-place predicate symbol이다).
이럴 경우 = symbol은 다음 처럼 axiom이 필요하게 된다.

다른 한가지 방법은 = symbol을 특수 연산자로 정의하여 사용할 수 있지만 이는 구현(control)의 방법으로 해결하는 것으로 순수한 논리 언어라고 볼 수 없다. 어쨌든 논리 equality 심볼은 많은 문제점을 내포하고 있어서 지식 표현 시스템에서도 equality 사용을 허용하지 않는 경우도 존재한다고 한다.

equality axioms를 적용하여 표현해보자.
( = symbol에 이렇게 복잡한(?) 의미가 있다니...)

John’s father loves Mary.
John’s father is Smith.
Ontology:
Constant symbols: John , Mary , Smith
2-place predicate symbol: loves(x, y)  ; x loves y.
1-place function symbol: father-of(x)  ; x’s a fther.
KB , a set of formulas:
loves(father - of(John), Mary)
father - of(John) = Smith
KB╞ loves(Smith, Mary) 
by the equality axioms



prenex normal form은 quantifier를 모두 앞으로 빼는 것이다.

예를 들어보자.

Ontology:
Constant symbol: 0, b, N
Function symbols:  abs(x) ; x
a(n) ; 𝑎𝑛
minus(x, y)  ; x- y
Predicate symbols: el(x, y)  ; x ∈ y , gr(x, y)  ; x > y

결국 아래처럼 Quantifier를 앞으로 보낸다.

이걸 step을 따라가보면 다음과 같다.
보기엔 어렵지만 한번 이해를 해두기 위해 손으로 적으면서 step을 따라가야 한다.

언어는 훈련이 되어야 사용이 가능한 것이다.

모든 Predicate logic formula는 prenex normal form으로 바꿀 수 있다.
분명한 것은 쉽지 않다.
온톨로지를 정의하는 것 조차 상당한 훈련이 필요하다.


이후 Skolemization를 하고 똑같이 Resolution을 하는 것은 명제 논리와 같다.
(Skolemization은 existential quntifier를 제거하는 것을 뜻한다.)


지금까지 서술논리에 대해서 어느 정도 설명했는데 서술논리는 변수와 universal quantifier가 사용되기 때문에 명제 논리보다 표현력이 뛰어나다고 볼 수 있다.

Deduction theroem은 다음과 같다.

지금까지 계속 이야기했던 내용과 비슷하다. 결국 어떤 formula가 true인지를 증명하려면 부정을 해서 KB에 넣어서 이게 모순이 되는지를 확인하는 것이다.

Deduction theorem에 의하여 KB |= A이 참이면 KB ⇒ A 가 valid(tautology)가 된다. 그런데 KB⇒ A ≡ ┐KB ∨ A가 된다. Tautology를 부정하면, 즉 ┐(┐KB ∨ A) ≡ KB ∧ ┐A는 unsatisfiable (즉 contradiction)이 된다.
따라서 KB |= A 는 true이다.


다음을 보자.

모두가 그(Henry)의 어머니를 안다. Henry는 어떤 사람을 아는가?
Q를 Henry가 y를 안다를 부정하자.
그리고 KB에 넣으면 이는 모순이 되기 때문에 Henry는 어떤 사람을 알게 된다.

다음은 다른 이야기이다.
Resolution Rule은 sound하다. 하지만 complete하지 않다.

유명한 러셀(Russell)의 역설(paradox)이다.

어떤 마을에 이발사가 존재한다. 그 사람은 스스로 면도를 하지 못하는 모든 사람들의 면도를 해준다.
이 문제는 아무리 Resolution을 해도 contradiction을 만들 수가 없다. 즉 sound는 해도 complte하지않는다.

따라서 Factorization이 필요하다.

위키를 참조하면 다음과 같다. (일명 이발사의 역설이다.)
마을에서 단 한 명의 이발사(남성)는 스스로 수염을 깎지 않는 모든 사람의 수염을 면도하고 그 이외의 사람의 수염은 깎지 않는다고 가정한다.
여기서 문제는 "이발사는 자신의 수염을 면도하는가?"이다.

이 질문에 답변할 경우 모순이 발생한다. 이발사는 스스로 면도를 하지 않는 사람에게만 면도를 수행하므로 스스로 면도를 할 수 없다. 이처럼 스스로 면도를 한다면 그는 이발사 일을 그만두게 된다. 이와 반대로, 이발사가 스스로 면도를 하지 않는다면 그는 이발사에게 면도를 받는 사람의 그룹에 속하게 되므로 이발사로서 그는 스스로 면도를 해야 한다.


이번에는 CNF로 바꾸는 예를 들어보자.

Everyone who loves all animals is loved by someone.
모든 동물을 좋아하는 사람이 있다면 그 사람을 좋아하는 사람이 있다.

CNF for first-order logic: similar to the propositional case.
Ex) ∀x [∀y Animal(y )⇒ Loves(x,y)]⇒[∃y Loves(y,x)]


1. Eliminate implications: (임플리케이션을 지운다.)
∀x ┐ [∀y ┐Animal(y)∨Loves(x,y)]∨[∃y Loves(y,x)]

2. Move ┐ inwards:
┐∀x P becomes ∃x ┐P (좌측이 우측으로 바뀜.)
┐∃x P becomes ∀x ┐P (좌측이 우측으로 바뀜.)
∀x [∃y ┐(┐Animal(y) ∨ Loves(x,y))] ∨ [∃y Loves(y,x)]
∀x [∃y ┐┐Animal(y) ∧ ┐Loves(x,y)] ∨ [∃y Loves(y,x)]
∀x [∃y Animal(y) ∧┐Loves(x,y)] ∨ [∃y Loves(y,x)]

3. Standardize(Rename) variables: (변수 이름을 바꿀 필요가 있으면 바꿔준다.)
∀x [∃y Animal(y) ∧  ┐Loves(x,y)] ∨ [∃z Loves(z,x)]

4. Skolemize: (Skolemize을 한다.)
∀x [Animal(F(x)) ∧  ┐Loves(x,F(x))] ∨ Loves(G(x),x)

5. Drop universal quantifiers: (universal quantifiers을 지운다.)
[Animal(F(x)) ∧  ┐Loves(x,F(x))] ∨ Loves(G(x),x)

6. Distribute ∨ over ∧: (분배법칙 적용)
[Animal(F(x)) ∨ Loves(G(x),x) ]
∧[ ┐Loves(x,F(x))∨Loves(G(x),x)]

그렇다면 다음을 보자.

Everyone who loves all animals is loved by someone.

Anyone who kills an animal is loved by no one.

Jack loves all animals.

Either Jack or Curiosity killed the cat, who is named Tuna.

Did Curiosity kill the cat?

온톨로지

Constants: Jack, Tuna, Curiosity

1-place Predicates: Animal(x) ; x is an animal.

Cat(x) ; x is a cat.

2-place Predicates: Loves(x,y) ; x loves y.

Kills(x,y) ; x kills y.

Example for resolution

1. ∀x [∀y Animal(y) ⇒ Loves(x,y)] ⇒ [∃y Loves(y,x)]

2. ∀x [∃y Animal(y) ∧ Kills(x,y)] ⇒ [∀z ┐Loves(z,x)]

3. ∀x Animal(x) ⇒ Loves(Jack,x)

4. Kills(Jack,Tuna) ∨ Kills(Curiosity,Tuna)

잭이 튜나를 죽였거나 Curiosity가 튜나를 죽였거나 둘 중에 하나다.

5. Cat(Tuna)

6. ∀x Cat(x) ⇒ Animal(x) ; Additional knowledge

┐G. ┐Kills(Curiosity,Tuna) : Refute the query

Curiosity가 튜나를 죽였나?

Transform to CNF
1. Animal(F(x)) ∨ Loves(G(x),x)

2. ┐Loves(x, F(x)) ∨ Loves(G(x),x)

3. ┐Animal(y) ∨ ┐Kills(x1,y) ∨ ┐Loves(z,x1)

4. ┐Animal(x2) ∨ Loves(Jack,x2)

5. Kills(Jack, Tuna) ∨ Kills(Curiosity, Tuna)

6. Cat(Tuna)

7. ┐Cat(x3) ∨ Animal(x3)

┐G. ┐Kills(Curiosity, Tuna)

결론 : Curiosity가 튜나를 죽였다.

포스팅 내용이 뒤죽박죽이고 설명을 잘 못했는데 부족한 점은 나중에 기회가 되면 다시 보완해야겠다. (사실 쓰면서도 한번에 집중하지 않으면 헷갈리고 내용이 어렵다.)



- 참고
아주대학교 정보통신대학원 인공지능(Artificial Intelligence(김민구 교수님))의 강의를 수강하며 배운 내용을 바탕으로 정리하였습니다. 그리고 강의 내용은 ertel's slide가 참고 되었습니다. 학습 목적으로 포스팅 합니다.