인공지능(AI) #3_ 명제 논리와 모형 점검 방식

안녕하세요. 문범우입니다.

이번포스팅에서는 명제 논리와 모형 점검 방식에 대해서 알아보도록 하겠습니다.

---

1. 명제 논리(Propositional logic)

1-1. 구문(Syntax)

명제 논리의 구문(syntax)은 허용되는 문장들을 정의합니다. 즉, 어떻게 문장을 구성해야 하는지를 이야기합니다.

하나의 문장, 원자적 문장(atomic sentence)은 하나의 명제 기호(proposition symbol)로 구성됩니다. 그리고 그러한 기호는 참(true)이거나 거짓(false)인 하나의 명제를 나타 냅니다. 예를 들어 P, Q, R, North 등이 명제 기호입니다.

이때, 항상 고정적 의미를 가진 명제가 있는데 자주 보셨듯이 True와 False 입니다. True는 항상 참인 명제이며 False는 항상 거짓인 명제입니다.

또한 우리는 간단한 문장들을 괄호와 논리 접속사(logical connective)로 연결해서 복합 문장을 만들 수 있습니다.

일반적인 접속사(연산자)는 아래와 같습니다.

(부정)	부정(negation)이라고 부른다.  리터럴(literal)은 원자적 문장 또는 원자적 문장의 부정인데, 전자를 긍정 리터럴(positive literal), 후자를 부정 리터럴(negative literal)이라고 부른다.
(논리곱)	논리곱 성분(conjunction) 이라고 부른다. 또는 연언문이라고 부른다.
(논리합)	논리합 성분(disjunction) 이라고 부른다. 또는 선언문이라고 부른다. 역사적으로는 '또는'을 뜻하는 라틴어 'vel'에서 비롯되었다.
(함의)	함의(implication) 또는 조건부 문장이라고 부른다. 또한 함의 문장을 규칙(rule)이나 if-then 문장이라고 부르기도 한다.
(동치)	동치, 상호조건(biconditional)이라고 부른다.

문장들을 이러한 접속사(연산자)를 이용하여 복합 문장을 만들어 내면 그 또한 문장입니다.

1-2. 의미론(Semantics)

명제 논리의 구문을 살펴보았으니, 이제 명제 논리의 의미론을 살펴보도록 하겠습니다.

의미론(semantics)이란 특정 모형에 대한 문장의 진리를 결정하는 규칙들을 정의합니다. 명제 논리에서 모형은 모든 명제 기호의 진릿값(truth value), 즉 참(true) 또는 거짓(false)을 고정하는 역할만 합니다.

명제 논리의 의미론은 주어진 모형에 대해 임의의 문장의 진릿값을 계산하는 방법을 명시해야 합니다. 모든 문장은 원자적 문장과 위에서 본 다섯가지 접속사로 구성됩니다. 따라서 원자적 문장의 진릿값을 계산하는 방법과 각 접속사로 만들어지는 문장의 진릿값을 계산하는 방법을 명시해야 합니다.

원자적 문장에 대한 의미론은 다음과 같습니다.

- True는 모든 모형에서 참이고 False는 모든 모형에서 거짓이다.

- 다른 모든 명제 기호의 진릿값은 반드시 모형 자체에 명시되어 있어야 한다.

복합 문장에 대해서는 다섯 가지 규칙이 존재합니다.

이러한 규칙들은 임의의 모형 m 안의 임의의 문장 P와 Q에 대해 성립합니다.

- P는 오직 m에서 P가 거짓일 때에만 참이다.

- P Q는 오직 m에서 P와 Q가 모두 참일 때에만 참이다.

- P Q는 오직 m에서 P 또는 Q가 참일 때에만 참이다.

- P Q는 m에서 P가 참이고 Q가 거짓이 아닌 한 참이다.

- P Q는 오직 m에서 P와 Q가 둘 다 참이거나 둘 다 거짓일 때에만 참이다.

이러한 규칙들은 복합 성분의 진릿값을 나열한 진리표(truth table)로 표현할 수 있습니다.

이러한 표를 이용하면 임의의 모형 m에 대한 임의의 문장 s의 진릿값을 간단한 재귀적 평가를 통해서 구할 수 있습니다.

즉, 아래와 같은 예시를 쉽게 참 또는 거짓을 구분할 수 있습니다.

논리곱, 논리합 등과 같은 논리 접속사에서는 일상적인 자연어로 이야기 할 때 다소 혼동되는 부분들이 있을 수 있습니다.

하나씩 살펴보도록 하겠습니다.

논리곱과 논리합, 부정의 진리표는 영어 문장에서의 해당 영어 단어 and, or, not의 의미를 잘 반영합니다. 그러나 헷갈리는 부분이 역시나 존재합니다.  라는 것은 P 또는 Q가 참일 때는 물론이고 둘 다 참일 때에도 참입니다. 하지만 단순히 or이라는 의미는 P 또는 Q가 참일 때 참이라는 의미만 가지고 있어서 헷갈릴 수 있습니다.

또한 이와는 다른 접속사인 '배타적 논리합(exclusive or, 줄여서 "xor")'은 두 논리합 성분이 모두 참일 때에는 거짓을 산출 합니다.

논리곱, 논리합, 부정은 크게 혼동되지는 않을 터이나 이제 설명드릴 함의와 같은 논리접속사에 대해서는 의미적으로 많은 혼동이 있을 수 있으니 천천히 이해하시길 바랍니다.

논리 접속사 (함의)에 대한 지리표는 언뜻 보면 "P가 Q를 함의한다" 또는 "만일 P이면 Q이다"라는 문장에 대한 우리의 직관적 이해와 잘 맞지 않는 것처럼 보입니다. 한 예시를 들어보도록 하겠습니다. 명제 논리에서는 P와 Q사이에 어떤 인과관계가 있어야 한다고 요구하지 않습니다. 즉, P와 Q사이에는 전혀 무관할 수 있습니다. "만일 5이 홀수이면 서울은 한국의 수도이다."는 일상 언어의 감각으로는 상당이 엉뚱합니다. 하지만 명제논리에서는 해당 복합 문장을 참이라고 말합니다.(통상적인 해석하에서) 복합 문장을 만들어 내는 각각의 문장에 대한 서로의 인과관계는 필요 없기 때문입니다.

또 다른 혼란스러운 점은, 전제가 거짓인 명제 논리 문장은 결론과는 무관하게 무조건 참입니다. 예를 들어, "만일 3이 짝수라면 범우는 똑똑하다."는 범우가 똑똑한지 똑똑하지 않은지와 상관없이 무조건 참인 문장입니다. 이상하게 느껴질지 모르겠지만, '만일 3이 짝수라면' 이라는 전제가 거짓이기 때문에 결론을 신경쓸 필요없이 해당 복합문장은 참이기 때문입니다.

이를 보다 의미적으로 쉽게 다가가기 위해서, PQ 라는 문장을 "만일 P가 참이면 나는 Q가 참이라고 주장한다. 참이 아니면 나는 어떠한 주장도 하지 않는다."라는 문장으로 생각하면 이해가 될 것 입니다. 이런 문장은 오직 P가 참이고 Q가 거짓일 때에만 거짓이기 때문입니다. 

1-3. 웜푸스 세계에서의 간단한 지식 기지

명제 논리의 구문과 의미론에 대해서 알아보았으니 이제 그것들을 기초로 하여 지난 포스트에서 살펴본, 웜푸스 세계의 지식 기지를 구축해 보도록 하겠습니다. 현재는 웜푸스 세계가 변하지 않는, 불변이(immutable) 측면들에 초점을 맞출 것이며 가변(mutable)적인 측면들은 나중에 살펴보겠습니다. 우선, 아래와 같은 명제 기호에 대한 정의를 가지고 시작하겠습니다.

- 는 만일 [x, y]에 구덩이가 있으면 참이다.

- 는 만일 [x, y]에 웜푸스가 있으면(죽음과 상관없이) 참이다.

- 는 만일 에이전트가 [x, y]에서 미풍을 지각하면 참이다.

- 는 만일 에이전트가 [x, y]에서 악취를 지각하면 참이다.

지난 포스트에서 우리는 (1,2)에 구덩이가 없음을 비공식적으로 유도하였습니다. 따라서 그에 해당 하는 문장인 을 공식적으로 유도하기 위해 명제 논리 문장들을 작성해 보도록 하겠습니다. Ri는 이후 편하게 문장을 사용할 수 있도록 문장에 각각의 문장을 나타냅니다.

- [1,1]에 구덩이가 없다.

   R1 : 

- 에이전트가 하나의 칸에 존재함 그 이웃칸에 구덩이가 있으면, 그리고 오직 그럴때에만 미풍을 지각할 수 있다.

   R2 : 

   R3 : 

- 앞의 문장들은 모든 웜푸스 세계에서 참이다. 이제 에이전트가 있는 특정한 세계에서 처음 방문한 두 칸에 대한 미풍 지각을 위한 문장들을 명시한다.

   R4 : 

   R5 : 

이렇게 하여 기본적인 지식 기지를 구축해 보았습니다.

1-4. 웜푸스 세계에서의 간단한 추리 절차(모형 점검 방식)

우리의 목표는 지식기지(KB)에서 KB|=a 인 문장 a가 존재하는지를 알아내는 것 입니다.

즉, 위에서 구축한 KB가 를 함축하는지 알아내야 합니다.

이를 알아내기 위해서 진행할 첫 번째 추리 알고리즘은 함축의 정의를 직접 구현하는, 모형 점검 접근방식의 알고리즘입니다.

다시말해 이번에 살펴볼 추리 절차는 모든 모형들을 나열하면서 이에 대해 지식 기지(KB)가 참인지 거짓인지 확인합니다. 그리고 지식 기지가 참인 모든 모형들에서 문장 a가 참인지 점검합니다. 

웜푸스 세계로 돌아 간다면 유관한 명제 기호는  입니다. 명제 기호가 총 7개 이므로 가능한 모형은 총 128개(2의 7승)입니다. 이를 전부 나열했을때 지식 기지가 참인 것을 확인하면 총 3가지의 모형을 볼 수 있습니다.

지식기지가 참이 되는 세가지 모형을 보면 우리가 알아내려한 가 참인 것을 알 수 있습니다. 따라서 (1,2)에는 구덩이가 없습니다. 반면 는 세가지 모형 중 둘에서는 참이고 하나에서는 거짓이므로 (2,2)에 구덩이가 있는지 없는지 알 수 없습니다.

이러한 추리 방법은 이전에 비공식적으로 (1,2)에 구덩이가 없다는 것을 추리한 것보다 보다 엄밀한 추리 방법입니다. 알고리즘에서 함축의 정의를 직접적으로 구현 하기때문에 건전합니다.(sound) 그리고 KB와 a에 대해 작동하고 반드시 종료되므로 완결적(complete) 입니다. 알고리즘이 반드시 종료된다는 것은, 확인할 모형의 개수가 유한하기 때문입니다.

하지만 확인할 모형의 개수가 유한하다는 것은 '적다'라는 의미와는 다릅니다. KB와 a의 기호가 총 n개 일떄 확인해야 할 모형은 총 2^n개 입니다. 따라서 알고리즘의 시간 복잡도는 O(2^n)입니다. 그렇다면 보다 많은 경우에서 우리가 확인한 것보다 더 많은 모형을 확인해야 할 것입니다. 따라서 우리는 훨씬 효율적인 알고리즘들을 뒤에서 살펴보겠습니다.

아래는 표준적인 논리 동치 관계들을 나타내는 것으로써 각각의 문장들로 인한 복합문장들의 참 또는 거짓을 구별할 때 사용됩니다.

---

이렇게 하여 명제 논리와 모형 점검 방식에 대해 알아보았습니다.

다음 포스팅에서는 정리 증명(theorem proving)을 이용해서 함축 관계를 확인하는 방법을 살펴보도록 하겠습니다.

궁금한 점이나 내용에 대한 피드백은 댓글을 이용해주세요 :)