CSCE 420 Lecture 21

« previous | Thursday, April 4, 2013 | next »

Defaults and Exceptions: Nonmonotonic Logic

FOL doesn't support exceptions to universally quantified rules

monotonicity: if you add sentences to KB, everything that was previously entailed is still entailed.

Default Logic

$P_{1},\ldots ,P_{m}/J_{1},\ldots ,J_{m}\rightarrow C$

J's represent:

• "It is consistent to believe"
• "If not provably false"
• "If $J_{i}$ is false, then rule is blocked"
• "Unless there is evidence to the contrary"

Bird(x) / Flies(x) → Flies(x)
Bird(tweety)
Bird(opus)
¬Flies(opus)

"Fixed-point semantics"

1. Start with a minimal model
2. elaborate and add consequences

KB with exceptions and contradictions is still allowed to be consistent

Circumscription

Usually, we write

∀x bird(x) → flies(x)
∀y dog(y) → barks(x)

But we add "abnormal predicates" that allows for exceptions:

∀x bird(x) ∧ ¬abnormal1(x) → flies(x)
∀y dog(y) ∧ ¬abnormal2(y) → barks(x)

"preferred" models are those that minimize abnormal assumptions:

bird(tweety)
bird(opus)
¬flies(opus)
dog(fido)
dog(snoopy)
¬barks(snoopy)

m1:
    abnormal1(tweety)
    abnormal1(opus)
    abnormal2(fido)
    abnormal2(snoopy)

m2:
    abnormal1(opus)
    abnormal2(snoopy)
    flies(tweety)
    barks(fido)

m2 has the fewest abnormal assumptions

Truth-Maintenance Systems

• Assert and retract information (facts, observations, perceptions)
• Keep track of dependencies
• Graph structure: map facts to derived inferences (similar to a proof tree)
• When a fact changes, consequences are propagated (belief updating, theory revision)

Semantic Networks

Visual (graph) representation of knowledge:

Figure 1. Semantic Network representing John and Mary

Mary is John's sister (Figure 1)

Nodes:

• a
• b
• Mary
• John
• female persons
• male persons
• person

Edges

• (a, Mary, name)
• (b, John, name)
• (a, b, sister)
• (a, female persons, member)
• (b, male persons, member)
• (female persons, person, subset)
• (male persons, person, subset)

Figure 2. 3-way gives event node.

How to represent three-argument predicates (Figure 2)?

gives(John, Mary, present):

• added nodes: c, presents
• added edges: (c, presents, member)
• event node: giving event
  • receiver: a
  • giver: b
  • object: c

Figure 3. Procedural lookup for How many legs does Mary have?

Semantic Networks handle defaults by inheritance, and handle exceptions by a "procedural lookup mechanism"

How many legs does Mary have? (Figure 3)

• find Mary
• follow (a, Mary, name)
• follow (a, female persons, member)
• follow (female persons, person, subset)
• identify (person, 2, num_legs)

Figure 4. Procedural short-circuit lookup for How many legs does John have?

Procedural lookup: suppose John only has one leg; short-circuit the default lookup operation by defining (b, 1, num_legs) (Figure 4)

Problem: semantic networks don't scale well to real-world applications

Back to Prolog

Cannot directly assert negated facts

Closed-world assumption: everything not explicitly asserted is assumed to be false

took(joe, csce311). took(julie, csce315). lower_level(X) :- \+ took(X, 315).

This is enough to prove that Joe did not take CSCE 315

Intervally, Prolog handles Negation as Failure:

• If top goal on stack is a negative literal $\neg \phi$, then
• Invoke side-call backchaining on $\phi$, trying to prove it.
• If $\phi$ fails, then original proof can proceed
• Otherwise if $\phi$ succeeds, then original proof must back-track

Example program:

bird(tweety). penguin(opus).

bird(X) :- penguin(X).

flies(X) :- bird(X), \+ penguin(X).