[Artificial Intelligence] Inference

Inference

• $\Delta$, 지식베이스
  • SWITCH_ON
  • ~ALARM
  • SWITCH_ON∧DOOR_OPEN  ALARM === ~A ∨ B
  • ~SWITH_ON ∨ ~DOOR_OPEN ∨ ALARM

• $\omega$ : ~ DOOR_OPEN

• How to Prove?

Theorem : example

Definition of Proof

• Proof of $\omega_n$ from a set of wffs $\Delta$
  • sequence $[\omega_1, \omega_2, \dots, \omega_n]$
• $\omega_n$
  • 1) in $\Delta$
  • 2) or can be inferred from a wffs earlier in the sequence
• $\omega_n$ is a theorem of set $\Delta$
  • If there is a proof of $\omega_n$ from $\Delta$

Resolution in Propositional Logic

• Literal
• Positive literal(atom), negative literal(negated atom)
• Clause(절): a set of literals, disjunction of all the literals in the set.
• ex. {P, Q, ~R} : $P \vee Q \vee ~R$
• { } : nil

Resolution on Clauses

Converting wffs to CNF

• (Conjunctive Normal Form): conjunction of clauses, 절들의 논리곱

Resolution Refutation 논리융합반박

• Convert wffs in $\Delta$ to clauuse form
• Convert negation of wff $\omega$ to clause form -> ~$\omega$모순의 의한 증명
• Combine clauses resulting from steps 1 and 2 into a set $S$
• Iteratively apply resolution to clauses in $S$ and add results to $S$ either
  • until there are no more new resolvents
  • or until empty clause is produced -> { } : nil

Theorem Proof : resolution

Exercise 1

• $\Delta$
  • SWITCH_ON

  • ~ALARM

  • SWITCH_ON ∧ DOOR_OPEN -> ALARM === ~A ∨ B
  • ~SWITH_ON ∨ ~DOOR_OPEN ∨ ALARM

• $\omega$ : ~ DOOR_OPEN

• How to Prove? Resolution Refutation

Exercise 2

Resolution in Predicate Logic

• literal:

  • Predicate Constant,~ Predicate Constant

    clause

    literal that might contain variables clause: ( , ,…, )( … ) 1 2 n 1 2 k x x x e e  e 1 2 k e  e  … e i e { , ,…, }

Unification

…

Prove Theorem

Package Delivery Problem

(a) All of the packages in room 27 are smaller than any of the ones in room 28

$(\forall x, y) [P(x) \wedge P(y) \wedge I(x, 27) \wedge I(y, 28) \rightarrow S(x, y)]$

clause form $~P(x) \vee ~P(y) \vee ~I(x,27) \vee ~I(y,28) \vee S(x,y)$

(b) $P(A)$ (c) $P(B)$ (d) $I(A,27) \vee I(A,28)$ (e) $I(B,27)$ (f) Package B is not smaller than package A, $~S(B,A)$

---

• Prove that package A is in room 27

~$I(A,27)$

총 6개의 절 집합으로 증명해야함
I(A,27)



1. 먼저 ~$\omega$ 로 부정을 취해야한다.
2. ~$\omega$ 이 nil이 된다면 **증명**
3. 

Resolution Refutation

$~I(A,27),I(A,27) \vee I(A,28) \Rightarrow I(A,28)$