[인공지능] 7. Propositional logic - 1

1. Propositional Logic (명제 논리학)

  1) Example

이번 단원 내내 지겹도록 보게 될 Wumpus World game이다. 이 게임은 (1,1)에서 용사가 출발해 괴물과 함정을 피해 gold를 무사히 찾는 것이 목표이다.  함정이 있으면 함정의 사방으로 breeze 바람이 불고, 괴물이 있으면 괴물의 사방으로 악취 strench가 풍긴다. 이 힌트를 이용해 최소한으로 움직여 무사히 gold를 찾으면 된다. 용사가 어떤 Action을 취할 때마다 cost가 든다. 

이건 알아도 되고 몰라도 되는데 용사는 화살을 쏠 수 있다. 화살을 쏘면 직선 방향으로 쭉 날아가는데, 괴물이 맞으면 소리를 지르면서 죽는다. 이 소리를 듣고 괴물의 위치를 예측할 수 있다. 

 

용사는 자기가 있는 칸에서 정보를 수집한다. 이 칸에 바람이 부는지, 악취가 나는지, 금이 있는지, 괴물이 죽는 소리를 들었는지, 어디로 움직일 수 있는지. 즉 Partialy observable한 상황이다.

 

1,1 에서 용사는 악취와 바람이 불지 않음을 확인했다. 따라서 1,2 와 2,1 은 안전하다. 

2,1로 움직였더니 바람이 분다. 따라서 2,2 또는 3,1에 함정이 있다. 1,1과 1,2는 안전하다는게 확인 되었으니 1,2로 움직인다. 

1,2 로 움직였더니 악취가 난다. 일단 바람은 안불었으니 2,2는 안전하다. 그러므로 3,1엔 함정이, 1,3엔 괴물이 있다. 2,2로 이동한다.

2,2에는 아무것도 없으므로 2,3이 안전하다. 움직였더니 금이 있었다. 이제 방문했던 곳을 따라 다시 1,1로 돌아오면 된다. 이제 이걸 PL을 이용해 CSP문제처럼 풀어내보자.

 

 

 2) Syntax

 

  - atomic sentences : single proposition symbol. 하나의 명제 기호. P, Q, R과 같은 변수나 True, False 등.

  - Complex sentences : atomic sentence들이 논리기호로 연결된 문장. 

    (￢ : not(nagative), ∧ : and(conjunction), ∨ : or(disconjunction), ⇒ : implies, ⇔: if and only if)

 - literal : atomic sentence(=positive literal) 과 nagated atomic sentence( = nagative literal)로 이루어짐. 

             즉, 명제 기호 딸랑 하나 있거나, 명제 기호에 not 기호 하나 붙어 있는 애들이 literal

 

 

  3) Semantics

 

   - 표준적인 logic에서 모든 문장은 true 또는 false라는 값을 가지게 된다. 우리는 가능한 세계를 model이라는 개념으로 나타낸다. 각 literal이 어떤 값을 가지냐에 따라서 문장 전체의 진리값이 달라지기 때문에 literal에 할당하는 진리값 하나하나에 따라 가능한 possible world가 달라지는데, 각각의 경우들을 model이라고 부른다. 

 

  - semantics (의미론) 은 어떤 모델에서 문장의 진위 여부를 결정하기 위한 규칙을 정의한다.

PL에서의 semantic은 어떤 model이 주어졌을 때 그 sentence의 참 거짓 값을 계산하는 방법, 일종의 규칙을 모아둔 것을 말한다.

위 표에서 각각 한 행이 하나의 model이다. 

 

  ① sentence 는 knowledge representation language라고 불리는 언어로 표현된다.

  ② axiom : 공리 는 다른 문장으로 부터 증명되지 않아도, 그 문장 자체로 true라고 간주한다.

  ③ 문장들은 representation language의 syntax(문법)에 맞게 표현된다. 그리고 이것은 well-formed sentence를 특정한다.

  ④ logic은 반드시 semantic 또는 문장의 의미가 정의되어야 한다. semantic은 문장이 각 가능세계에 대해서 true인지 false인지를 정의한다.

  ⑤ knowledge base(KB: 지식체계)는 문장들의 집합이다. 이 KB는 처음에는 background knowledge로 시작해서 추론을 통해 문장을 추가해나간다. 

 

 

 4) Example 

 

앞서 살펴봤던 Wumpus World를 떠올려보자. 여기서 함정에 대해 KB를 만들어보자.

먼저 기본적인 규칙(공리)를 설정해주자

 

- 시작지점에는 함정이 있으면 안된다 (R1) : ￢P(1,1)

- (1,1)에서 바람이 불면 (2,1) 또는 (1,2)에 함정이 있다 (R2) : B(1,1) ⇔ (P(1,2) ∧ P(2,1))

.

.

.

그리고 관측 결과

- (1,1)에서는 바람이 불지 않는다 (R4) : ￢B(1,1)

- (2,1)에서는 바람이 분다 (R5) : B(2,1)

 

이러한 알려진 사실을 바탕으로 truth table을 만들어보자. 

 

R들은 이미 알려진 사실로, 얘네는 true여야만 한다. 즉, 관측 결과를 바탕으로 추론한 애들이 R, 즉 knowledge base를 참으로 만드는 문장이 새로운 참인 문장이다. 

 

지금 우리는 (1,1)~(3,1)에 대한 정보를 알고 있다. 이 정보가 R1~R5 안에 담겨 있다. 이 아이들이 KB이다.

그리고 우리는 (1,1)~(3,1)에서 가능한 모든 경우의 수를 적어보았다. 2의 7제곱, 총 128개의 경우의 수가 있다. 이 수많은 경우의 수에서 KB를 true로 만드는 경우, 그 model을 바탕으로 새로운 KB를 만들어 낼 수 있다.

 

 

 5) Entailment and Inference

 

 ① 만약 sentence α가 model m에서 true일 때, m satisfie α 또는 m is a model of α라고 말한다. α의 model들의 집합, 즉 α의 모든 모델들, α가 true인 테이블의 모든 행들을 M(α)라고 표현한다.

 

 ② 만약 sentence α 가 sentence β 를 entail할 때, α ⊨ β 라고표현한다.

    모든 model에서 α가 true라면 β 역시도 true이다. 

  ③ Inference(추론)은 어떤 old sentence로부터 new sentence가 도출되었을 때를 말한다. 만약 inference algorithm i가 KB로부터 α를 도출해냈다면, KB ⊢i α라고 쓸 수 있으며 , "α는 i에 의해 KB로부터 derive되었다" 또는 "i derives α from KB" 라고 말할 수 있다.

 

  ④ inference algorithm이 true인 문장만 derive하여 entail될 수 있는 문장만 entail시키면, sound하다고 말하고, 나올 수 있는 모든 true인 sentence를 도출해내 entail할 수 있는 모든 문장을 찾을 수 있으면 complete하다고 말한다. 

즉 sound할 경우 모든 entail하는 sentence를 다 찾는 건 아니지만 찾은 sentence는 다 entail 할 수 있는 것이고, complete할 경우 모든 entail 할 수 있는 sentence를 다 찾은 거지만, 안되는 sentence도 섞여있을 수 있다. 

 

(a)  (1, 2)에는 함정이 없다는 새로운 α1 을 도출해냈다고 치자. KB가 true인 모든 model에서 α1 역시 true이므로 KB는 a를 entail 한다고 볼 수 있다.

 

(b) (2, 2)에는 함정이 없다는 α2를 도출해 냈다고 치자. 이는 KB가 true인 모든 model에서 만족하는 것이 아니기 때문에 무조건 함정이 없다고 할 수는 없는 것이다. 즉, Entail하지 않다.

 

 

2. Model Cheking Approach

 - KB가 α를 entail 하는지 안하는지를 결정하기 위해서는 model checking을 해서 α가 KB가 TRUE인 모든 model에서 true인지 확인해야 한다. 

P,Q,R이라는 세개의 symbol이 있을 때 2^3개의 truth table이 만들어질 수 있다. 이 truth table에서 KB가 true가 되는 model이 있을 때, 그 model 모두에서 α가 true여야지만 KB가 α를 entail한다고 할수있다.

알고리즘은 다음과 같다.

ㅏ

KB가 α를 entail하는지를 알아보는 함수 TT-ENTAILS?함수를 보자.

 

KB와 α에 존재하는 모든 Proposition symbol들, 모든 literal들을 symbols라는 리스트에 담고, TT-CHECK-ALL함수를 호출한다.

 

TT-CHECK-ALL 함수는 symbol 하나하나에 진리값을 넣어서 model을 만들고 탐색을 진행한다.

 

우선 symbols이 비어있다면, model이 KB를 만족하는지, 즉 model이 KB가 true인지를 판별해본다. 만약 해당 model에서 KB가 true라면, α 또한 그 model에서 true여야 한다. 그래서 true면 true를, false면 false를 return한다.

만약 model에서 KB가 애초에 false라면 볼 필요가 없으므로 그냥 true를 반환해준다. 

 

만약 symbols이 비어있지 않다면, P에 첫번째 symbol을, rest에 나머지 symbol을 넣어준다. 

그리고 먼저 TT-CHECK-ALL함수를 P=true일때와 P=false일 때 각각 호출해서 and 연산을 시켜준다. 

이 과정은 쉽게 말해서 model을 만들어주는 과정이라고 생각하면 된다. model에서 False가 하나라도 반환되는 순간, KB는 true이지만 α는 false인 model이 있었다는 것이기 때문에 entail할 수 없다. 

 

 

 

* Analysis of Model Checking Approach

 - 이 알고리즘은 entailment의 정의를 직접적으로 활용한 것이기 때문에 당연히도 sound하다. 

 - 또한 모든 KB와 α에 대해 수행되고, 항상 끝까지 찾기 때문에(=DFS) Complete 하기도 하다. 

 - Time Complexity : O(2^n)  // 모든 model을 찾는 경우의 수 = 2x2x...x2 (n개) , n은 symbol 개수

   Space Complexity : O(n) // 한 번에 모델 하나씩 검사하니까 한 번에 최대 n