Intelligent Systems Lecture Notes

28 September 2011 • Advanced Representations

---

Outline

• Horn clauses and contradictions.
  • Assumptions.
• Complete knowledge.

Horn Clause

• A Horn clause a definite clause of the form

  h \(\leftarrow\) b

  or of the form (called an integrity constraint)

  false \(\leftarrow\) b

  where false is a special atom which is never true.
• A Horn clause knowledge base contains Horn clauses.

false \(\leftarrow\) b

• From the when truth table, false \(\leftarrow\) b is true when b is false.
• b could be the conjunct \(b_1\) \(\wedge\) \(\ldots\) \(\wedge\) \(b_n\).
• If \(b_1\) \(\wedge\) \(\ldots\) \(\wedge\) \(b_n\) is false, at least one of \(b_i\) is false.
• false \(\leftarrow\) b asserts an atom is false (is contradicted).

  false \(\leftarrow\) dogissmelly
  false \(\leftarrow\)
    bulb1isout \(\wedge\) bulb2isout \(\wedge\) bulb3isout
  

Unsatisfiability

• A knowledge base is unsatisfiable if it has no models.
• A propositional knowledge base always has a model.
• A Horn-clause knowledge base may be unsatisfiable.

  a
  false \(\leftarrow\) a

Inconsistency

• A clause set S is inconsistent if it can prove false: S \(\vdash\) false.

  Given knowledge base S: { a, false \(\leftarrow\) a }
  a is true
  false \(\leftarrow\) a is true
  false is true by modus ponens.

• Propositional knowledge bases can never be inconsistent.
  • They don't admit integrity constraints.

Propositional Negations

¬ a f t t f

Propositional negations are a logical consequence of Horn clauses.

• For example, given

  KB: {		false \(\leftarrow\) a \(\wedge\) b
  		a \(\leftarrow\) c
  		b \(\leftarrow\) c	}

  then KB \(\models \neg\)c.

Proof by Contradiction

• If knowledge base KB is satisfiable, then KB \(\not\models\) false.
• Suppose KB \(\cup\) { a } \(\models\) false.
  • Then a can't be true, because KB is satisfiable.
  • If a’s not true, then it's false, or KB \(\models\) ¬a.
• This is known as proof by contradiction:

  Assume a’s true,
  Show a proves false (a contradiction),
  Conclude a’s not true.

Conflicts

• An assumption set is a conflict if it makes a Horn-clause knowledge base inconsistent.
  • \(KB \cup \{ a_1, \ldots, a_k \} \models \) false
• If \(\{ a_1, \ldots, a_k \}\) is a conflict with KB, then

  \(KB \models\) \(\neg a_1\)  \(\vee\) \(\cdots\) \(\vee\)  \(\neg a_k\)

  At least one of the assumptions are wrong.

• A minimal conflict is the smallest assumption set producing a contradiction.

Consistency-Based Diagnosis

• Add integrity constraints about correct operation

  false \(\leftarrow\) bulblit \(\wedge\) bulbdark

  and assumptions about lack of faults to rules.

  lit \(\leftarrow\) light \(\wedge\) live \(\wedge\) poweredlight

• Determine the conflicts under a given interpretation.
• The individual negated assumptions are potential failure points.

Bottom-Up Conflict

• A bottom-up proof determines what can be proved by starting with atoms and working up.

  BUConflicts(KB, Assumptions)
  

    proved = {\((a, \{ a \}) : a \in \) Assumptions}

    repeat
      select h \(\leftarrow\) \(b_1\) \(\wedge\) \(\cdots\) \(\wedge\) \(b_m\) \(\in\) KB
        where \((b_i, A_i)\in C\) for all \(i\)
        and \((h, A = A_1\cup\cdots\cup A_m) \not\in C\)
      \(C = C \cup \{(h, A)\}\)
    until nothing more to select

    return { \(A : (false, A) \in C\) }

Top-Down Conflict

TDConflicts(KB, Assumptions)


  G = { false }

  repeat
    select a_i \(\not\in\) Assumptions from G
    choose a_i \(\leftarrow\) b from KB
    G = G \(\cup\) atomsIn(b)
  until G \(\subseteq\) Assumptions

  return G

• This is a non-deterministic algorithm.

Known Unknowns

• Given the knowledge base KB { a \(\leftarrow\) b } and the empty interpretation,

  ask a	⇒ unknown
  ask b	⇒ unknown
  ask a \(\wedge\) b	⇒ unknown

• Because neither a nor b can be proved in KB, nothing can be assumed about them.
  • This is the open-world assumption.

No Unknowns

• In the closed-world assumption, rule heads that can't be proved true are assumed to be false.

  KB: { a \(\leftarrow\) b }, I: { }

  ask a	⇒ false
  ask b	⇒ false
  ask a \(\wedge\) b	⇒ false

  • Also known as the complete-knowledge assumption.

Clark’s Completion

• Under the closed-world assumption, the rule sets

  a \(\leftarrow\) b1 \(\vdots\) a \(\leftarrow\) bk

  and

  a \(\rightarrow\) b1 \(\vee\) \(\cdots\) \(\vee\) bk a \(\leftarrow\) b1 \(\vee\) \(\cdots\) \(\vee\) bk

  are equivalent, and so

  a \(\leftrightarrow\) b₁ \(\vee\) \(\cdots\) \(\vee\) b_k

  This is known as Clark’s completion.

Observations

a \(\leftrightarrow\) b t t t t f f f f t f t f

Equivalence (if and only if, iff), \(\leftrightarrow\), \(\equiv\)

• A listed atom a completes to a \(\leftrightarrow\) true.
• An unlisted atom a completes to a \(\leftrightarrow\) false.
• Completion can derive negations, represented as \(\sim\)a.
  • \(\sim\) requires the closed-world assumption.

Monotinicity

• Monotonic reasoning never forgets.
  • Adding facts doesn't change existing facts.
• Non-monotonic reasoning does forget.
  • Adding facts can change existing facts.
• Negated atoms provide non-monotonic reasoning.

  bulblit \(\leftarrow\) powered \(\wedge \sim\)blown

References

• The Language of First-Order Logic (Chapter 2) and Expressing Knowledge (Chapter 3) of Knowledge Representation and Reasoning by Ronald Brachman and Hector Levesque from Morgan Kaufmann, 2004.
• From Logic-Based Chaining to Production Systems (Chapter 6) in Intelligent Systems by Robert Schalkoff from Jones and Bartlett, 2011.

---

This page last modified on 2011 September 28.