지식 표현과 논리 (Lecture Note #5) Modified from the slides by SciTech Media 지식 표현과 논리 (Lecture Note #5) 인공지능 이복주 단국대학교 컴퓨터공학과

Outline 지식 표현 논리 비교흡수 부정 의미망 프레임 객체지향 개념 Slide made by Bogju Lee

지식표현 (Knowledge Representation) 지식 표현 지식은 인공지능에서 가장 핵심 지식표현 연구는 지식을 체계적으로 조직, 저장하고 이를 효율적으로 이용하도록 하는 방법의 연구 문제 영역이나 문제해결의 효율성을 위해 적절한 지식표현 방법을 선택하는 것이 매우 중요하다 지식표현의 종류 논리 (Logic) 의미망 (Semantic Net) 프레임 (Frame) 규칙 (Rule) 객체지향 표현기법 (Object-Oriented Representation) Slide made by Bogju Lee

논리 (Logic) 논리 명제 논리 (propositional logic) 서술 논리 (predicate logic) 명제: 참, 거짓 판명 가능한 문장 복합문 (compound statement): 연결자 (and, or, not, implies, equivalent)에 의해 연결된 문장 서술 논리 (predicate logic) 논리의 단위가 명제가 아닌 객체 (object)와 술어 (predicate) Canary is a bird = (is-a canary bird) Canary, bird: 인자 (argument) 변수, 한정기호 (quantifier: forall, exist) 사용 가능 If x is a bird, then x has wings (x) {Is-a(x, Bird)  has(x, Wings)} Slide made by Bogju Lee

논리 (Logic) 논리의 장점 논리의 단점 수학적인 근거를 바탕으로 논리개념을 자연스럽게 표현 지식의 정형화 영역에 적합 (정리 증명: theorem proving) 지식의 첨가와 삭제가 용이하고 단순 가정 (assertion) 들이 독립적 (modular) 논리의 단점 절차적, 결정적 지식표현이 어렵다 사실의 구성법칙이 부족하므로 실세계의 복잡한 구조를 표현하기 어렵다. Slide made by Bogju Lee

논리 (Logic) 정형 공식 (well-formed formula: wff) 항 (Term) 1) 상수, 변수는 항 2) 함수 f가 항 x를 인자로 가지면 f(x)는 항 3) 1), 2)에 의해 구성되는 것은 모두 항 예: MARY, BOX, x, y, z, father(MARY) 기초공식 (atomic formula) 항을 인자로 가지는 서술어(predicate)는 모두 기초공식이다 Ex) Woman(MARY), Married(father(JOHN), mother(JOHN)) 정형공식(wff : well formed formula) 1) 기초공식 f는 wff 2) F, G가 wff면, (F∨G), (F∧G), ∼F, (F→G), (F↔G)도 wff 3) F가 wff면, (∀x)F, (∃x)F도 wff 4) 1), 2), 3)의 과정에 의해서만 구성되는 것은 모두 wff Slide made by Bogju Lee

비교흡수 부정 비교흡수 부정 (Resolution Refutation) 두개의 기초절(부모절(parent clause)이라 함)에서 P1 ∨P2 ∨ … ∨PN 과 ~P1 ∨Q2 ∨ … ∨ QM 이 두개의 부모절 (parent clause)을 논리합을 취해서 새로운 비교흡수절 (resolvent)을 생성(비교흡수) (P1∨ ~P1)∨(P2 ∨ … ∨PN ∨Q2 ∨ … ∨ QM) 비교흡수 부정에서의 모든 절은 논리합으로만 된 정형공식 정형공식 집합 S에 특정 정형공식 X가 논리적으로 따름(logically follow)을 증명하기 위한 것 P=S∪{~X}  P에 대해 비교흡수 수행  비교흡수절 Ri 생성  P∪Ri에 대해 비교흡수 반복  모순(NIL)이 생성되면 종결 Slide made by Bogju Lee

비교흡수 부정 비교흡수부정의 이론 가정: S에 X가 논리적으로 따른다고 가정  S를 만족하는 모든 해석은 X를 만족(satisfy)함  S를 만족하는 모든 해석은 S∪{X}를 만족함(satisfiable)  S를 만족하는 모든 해석은 ~X를 만족하지 않음  S를 만족하는 모든 해석은 S∪{~X}를 불만족(unsatisfiable) 즉, 불만족인 집합내에는 어떤 절 Ci에 대해, Ci와 ~Ci가 공존하는 상황(모순)으로 볼 수 있다.  어떤 해석이 주어져도 Ci와 ~Ci를 동시에 만족할 수 없다  이러한 절들에 대한 비교흡수는 결국 NIL(모순) 생성  이는 S에 논리적으로 따르는 X를 부정(~X)한 결과는 모순을 초래하므로 결국 X는 S를 논리적으로 따른다 Slide made by Bogju Lee

비교흡수를 위한 정형공식의 절 변환 1. Implication() 제거 Ex) A→B ≡ ~A∨B 2. Negation(~) 영역 축소 Ex) ~(A∨B) ≡ ~A∧~B 3. 각 한정기호에 고유한 변수를 가지도록 변수 표준화 Ex) (∀x)[P(x) →(∃x)Q(x)] ≡ (∀x)[P(x) →(∃y)Q(y)] 4. 존재 한정 기호(∃) 제거 Skolem 상수 {∀ y Person(y) → ∃x Heart(x) ∧ Has(x,y) } {∀ y Person(y) → Heart(H) ∧ Has(y,H) } {x/H}  문제임 (∀y)[(∃x)P(x, y)] : x는 y에 종속되어 결정 x를 y에 대한 어떤 함수로 표현: g(y) : Skolem 함수 (∀y)[P(g(y), y)]로 변환 5. Prenix 형으로 변환: 모든 전체한정기호(∀)를 정형공식 앞으로 내어 영역을 전체공식에 미치도록 함 6. 정형공식을 논리곱 정규형(conjunctive normal form)으로 변환 Ex) X1 v (X2 ^ X3) ≡ (X1 v X2) ^ (X1 v X3) 7. 전체한정기호를 모두 생략 8. 논리곱을 생략. Ex) X1 ^ X2 ≡ {X1, X2} 9. 각 절에서 같은 변수명이 없도록 조정 Slide made by Bogju Lee

비교흡수를 위한 정형공식의 절 변환 예제 3.1: 정형 공식을 절들의 집합으로 변환 2003.09.08 Slide made by Bogju Lee

Summary 지식 표현 논리 비교 흡수 부정 정형공식의 절 변환 Slide made by Bogju Lee