#3 지식 표현과 추론

규칙

조건부의 지식을 표현하는 IF-THEN형태의 문장이다.

ex)

▷IF 연료통이 빈다 THEN 차가 멈춘다.    // 인과관계

▷IF 여름철이다 AND 날이 흐리다 THEN 우산을 가지고 가라    // 추천

▷IF 차가 멈췄다 AND 연료통이 비었다 THEN 주유를 한다    // 지시

▷IF 차가 멈췄다 THEN 연료통을 확인한다 AND 단계1을 끝낸다    // 전략

   IF 단계1이 끝났다 AND 연료통은 충분히 찼다

   THEN 배터리를 확인한다 AND 단계2를 끝낸다

▷IF 시료가 액체이다 AND 시료의 PH가 6미만이다 AND 냄새가 시큼하다    // 휴리스틱

   THEN 시료는 아세트산이다

 

Logic(로직)

Logic은 결론이 도출될 수 있도록 정보를 표현할 수 있는 형식적 언어이다.

Syntax는 문장의 문법이다.

Semantic은 문장의 의미이다. (True/False)

 

Entailment(함의)

Entailment 관계란 α가 β를 함의할 경우 β는 α의 결과를 따른다는 것입니다.

즉, α가 "true"이면 β도 "true"라는 것입니다. 이때 이때 α는 β의 subset 관계입니다.

 

α |= β ( "α entails β" or "β follows from α")

α가 β를 함의한다 = β는 α의 결과를 따른다

즉, 만약 α가 "true"이면 β도 "true"이다.

이때 α는 β의 subset 관계이다.

ex) α : 왕은 독살당했다 / β : 왕은 죽었다.

 

추론

KB ⊢i α 는 문장 α는 추론 절차 i에 의해 KB로부터 결과를 유도할 수 있다는 것입니다.

Soundness(건전성)

: 추론 절차 i가 sound하다는 것은, 만약 추론 절차 i를 통해 도출된 KB ⊢i α 가 True이면

  α |= β 의 결과는 항상 True이다를 보장할 수 있는 것입니다.

Complementness(완전성)

: 추론 절차 i가 complet하다는 것은, 만약 α |= β가 True일 때 추론 절차 i를 통해

  KB ⊢i α 의 모든 결과도 항상 True임을 보장할 수 있는 것이다.

 

논리적 동치 관계

두 가지 풀이 : 동치 관계 풀이, Truth Table

p → q ⇔ ¬p∨q

p → q ⇔ ¬q → ¬p
p∨q ⇔ ¬p → q

p∧q ⇔ ¬(p → ¬q)

(p → q) ∧ (p → r) ⇔ p → (q∧r)

(p → r) ∧ (q → r) ⇔ (p∨q) → r

(p → q) ∨ (q → r) ⇔ p → (q∨r)

(p → r) ∨ (q → r) ⇔ (p∧q) → r

 

유효, 만족 가능성

풀이 : Truth Table

 

 

 

명제논리 -

추론 규칙

: 추론 규칙은 우리가 가지고 있는 지식(KB)과 이미 알고 있는 사실로부터

  새로운 사실을 유추해내는 것이다.

1) 전건긍정

: A가 True인 것으로 정의하면, B도 True라는 결론을 얻는 논리 규칙

규칙 | A → B

사실 | A

-----------------

결론 B

2) 부정논법

: 규칙의 결론이 False인 경우 해당 조건 또한 False로 추론하는 것

규칙 | A → B

사실 | NOT B

-----------------

결론 NOT A

3) AND조건의 삭제

: A가 True이며 A^B의 결론이 True인 경우, B 또한 True로 추론하는 것

규칙 | A ∧ B

사실 | A

-----------------

결론 B

4) 삼단논법

: 두 개의 규칙을 연쇄적으로 작용시켜 새로운 규칙을 도출해내는 추론 방법

규칙 | A → B

사실 | B → C

-----------------

결론 A → C

 

추론 규칙 이용한 증명

 

 

명제 논리 -

증명 방법

1) Forward Chaining (전방 연쇄/순방향 추론)

: 알려진 사실로부터 출발하여 결론을 이끌어내는 방법이다.

2) Backward Chaining (후방 연쇄/역방향 추론)

: 목표를 설정하고, 이를 증명하는 증거를 찾는 방법이다.

 

Forward Chaining (전방 연쇄/순방향 추론)

KB rules(지식베이스 규칙)

P ⇒ Q

L ∧ M ⇒ P

B ∧ L ⇒ M

A ∧ P ⇒ L

A ∧ B ⇒ L

사실(Fact(True))

A

B

 

 

 

Forward Chaining vs. Backward Chaining

 

Forward Chaining은 Data-Driven 방법이다. 사실을 모은 후 이를 바탕으로 추론한다는 것이다.

Forward Chaining의 경우 목표와 관련없는 규칙들에 대해서도 살펴봐야한다. (BFS 방법과 유사)

Backward Chaining은 Goal-Driven 방법이다. 목표에서 시작하여 데이터들이 목표를 지원하는지 확인한다.

Backward Chaining의 경우 일반적으로 Forward Chaining보다 빠르지만(효과적),

완전성과 최적성을 보장하지 못한다. (DFS 방법과 유사)

 

 

명제 논리 -

CNF (논리곱 표준형)

명제 P와 명제 부정의 ¬P를 리터럴이라고 한다.

리터럴들이 논리합(∨)으로만 연결되거나, 논리곱(∧)으로 연결되면 절이라고 한다.

ex)    P ∨ Q ∨ ¬R (논리합 절) , P ∧ Q ∧ ¬R (논리곱 절)

논리합 절들이 논리곱으로 연결되어 있으면 CNF라고 한다.

ex)    (P ∨ Q ∨ ¬R) ∧ (¬Q ∨ R ∨ S) ∧ (P ∨ R ∨ S)

 

CNF 변환

연습문제 :

P ∧ (q → r) → p ∧ q

 

 

명제논리의 장단점

장점(Pros) :

명제논리는 문맥이 독립적이고 모호하지 않은 선언적 의미론을 기반으로 한다.

명제논리는 부분, 분리, 부정 정보를 허용한다.

명제논리는 구성적이다.

단점(Cons) :

명제논리는 표현력이 매우 제한적이다.