Logical conditionals

Logical methods for AI

Logical conditionals

Lecture 6

What you’ll be able to do

Read chapter 6 first; exercise sheet 6 comes after the lecture.

Conditionals

Rules, applied to facts, tell us what our knowledge entails.
An expert system: a KB of rules and facts, an inference engine.
Rain and a low sun: a rainbow.

The material conditional

$RAIN$	$WIND$	$RAIN \to WIND$
$1$	$1$	$1$
$1$	$0$	$0$
$0$	$1$	$1$
$0$	$0$	$1$

False iff (glossary, opens in a new tab) the antecedent (glossary, opens in a new tab) is true and the consequent (glossary, opens in a new tab) is false.

Default-true

python

1
2


if day == "monday":
    number = 1

On Tuesday, the rule says nothing: assigning 1 or 2 both satisfy it.

The default truth-value is $1$ ; only a counterexample changes it to $0$ .

With two truth-values, there is no third option.

Conditional rewriting

(A \to B) ⟹ (\negA \lor B)

Ex.

The interactive example is loading.

Modus ponens

By refutation:

RAIN \land (\negRAIN \lor WIND) \land \negWIND

resolves to $WIND$ , then to $⊥$ .

Not every if is material: “if you’d throw the ball at the window, then it would break.”

Knowledge bases

MORNING \to DAY EVENING \to DAY (CLEAR \land DAY) \to SUN (MORNING \land SUN) \to LOW_SUN (EVENING \land SUN) \to LOW_SUN (RAIN \land LOW_SUN) \to RAINBOW

TELL: $MORNING, CLEAR, RAIN$

ASK: $RAINBOW$ ?

Every part of the antecedent first, then the consequent.

Forward chaining

Forward chaining, step by step

Try “Rainbow”, then “Missing fact”: the same KB without $CLEAR$ .

The example is loading.

Derivations found

Backward chaining

Rule used backward	Remaining queries
Start	$RAINBOW$
$(RAIN \land LOW_SUN) \to RAINBOW$	$LOW_SUN$ ; $RAIN$ is known
$(MORNING \land SUN) \to LOW_SUN$	$SUN$ ; $MORNING$ is known
$(CLEAR \land DAY) \to SUN$	$DAY$ ; $CLEAR$ is known
$MORNING \to DAY$	None; $MORNING$ is known

Backward chaining, step by step

Try the same query without $CLEAR$ . Where does the search get stuck?

The example is loading.

Derivations found

Search order

Forward and backward describe the direction of reasoning; depth first and breadth first, the order of search.

Depth first

A
- B
  - D
  - E
- C
  - F
  - G

Breadth first

A
- B
  - D
  - E
- C
  - F
  - G

Horn clauses

Disjunctive form	Conditional form	Use
$\negCLEAR \lor \negDAY \lor SUN$	$(CLEAR \land DAY) \to SUN$	Derive a fact
$SUN$	$⊤ \to SUN$	Initial fact
$\negSUN \lor \negRAIN$	$(SUN \land RAIN) \to ⊥$	Forbid a combination

Horn SAT

Chain from the facts. A constraint reached: $⊥$ , unsatisfiable. Otherwise the derived atoms are the least model (glossary, opens in a new tab) .

Truth-tables: $2ⁿ$ rows. Will our planning formulas be Horn?

Counters and an agenda

A counter of unmet premises for each rule; an agenda (glossary, opens in a new tab) of facts to process.

The example is loading.

Derivations found

Planning problem

Green on red $⟶$ red on green. Two action steps.

Formalization and SATPLAN

States

\negOn(X, X, t) On(X, Y, t) \to \negOn(Y, X, t)

Initial and goal:

I = On(G, R, 0) \land \negOn(R, G, 0) G = On(R, G, 2)

Preconditions and effects

Stack(X, Y, t) \to \negOn(X, Y, t) Stack(X, Y, t) \to \negOn(Y, X, t) Unstack(X, Y, t) \to On(X, Y, t) Stack(X, Y, t) \to On(X, Y, t+1) Unstack(X, Y, t) \to \negOn(X, Y, t+1)

Frame conditions and miracles

The example is loading.

Derivations found

Frame problem

How do we represent what stays unchanged?

\negOn(X, Y, t) \lor Unstack(X, Y, t) \lor On(X, Y, t+1)

Two positive literals: this frame clause is non-Horn. The $O(m+1)$ guarantee no longer applies.

The example is loading.

Derivations found