∀I

Logical methods for AI

Lecture 6

Logical conditionals

This work is licensed under CC BY 4.0

https://forms.gle/JiXXM9eysAZaJMja9

Logical conditionals

Question

$$\nu(A\to B)=???$$

Clear cases

If $\nu(A)=1$ and $\nu(B)=0$, then $\nu(A\to B)=0$
If $\nu(A)=1$ and $\nu(B)=1$, then $\nu(A\to B)=1$

Tautologies

Definition. $\vDash A$ iff for all $\nu$, $\nu(A)=1$
Deduction theorem: $$P_1,P_2,\dots\vDash C\Leftrightarrow\ \vDash (P_1\land P_2\land \dots)\to C$$

Example

$$(\mathsf{RAIN}\lor \mathsf{BIKE}),\mathsf{SUN}\vDash\mathsf{BIKE}$$

Forward chaining

Ideas

Modus Ponens (MP): $$A,A\to B\vDash B$$

Forward chaining

Inference method for automated reasoning
Repeated MPs

Example

Knowledge base:
1. $\mathsf{SUN}\to \mathsf{BIKE}$
2. $\mathsf{RAIN}\to \mathsf{CAR}$
3. $\mathsf{WARM}\to \mathsf{SHIRT}$
4. $\mathsf{COLD}\to \mathsf{COAT}$
5. $\mathsf{BIKE}\to \mathsf{HELMET}$
6. $\mathsf{CAR}\to \mathsf{KEYS}$

Example

Known facts:
1. $\mathsf{RAIN}$
2. $\mathsf{COLD}$

Example

Derivations:
1. $\mathsf{RAIN},\mathsf{RAIN}\to\mathsf{CAR}\vDash \mathsf{CAR}$
2. $\mathsf{COLD},\mathsf{COLD}\to\mathsf{COAT}\vDash \mathsf{COAT}$
3. $\mathsf{CAR},\mathsf{CAR}\to\mathsf{KEYS}\vDash \mathsf{KEYS}$

Example

Outcome:
1. $\mathsf{RAIN}$
2. $\mathsf{CAR}$
3. $\mathsf{COLD}$
4. $\mathsf{COLD}$
5. $\mathsf{KEYS}$

Method

Check known facts agains KB.
If fact is in antecedent, apply MP.
Add conclusion to known facts.
Lather, rinse, repeat until done.
Data driven!

Backward chaining

Ideas

Backwards MP:
- Want to know whether $B$.
- Recursively check if we have $A$ and $A\to B$.
- If so, then $B$.
- If not, then $\neg B$.

Example

Knowledge base:
1. $\mathsf{SUN}\to \mathsf{BIKE}$
2. $\mathsf{RAIN}\to \mathsf{CAR}$
3. $\mathsf{WARM}\to \mathsf{SHIRT}$
4. $\mathsf{COLD}\to \mathsf{COAT}$
5. $\mathsf{BIKE}\to \mathsf{HELMET}$
6. $\mathsf{CAR}\to \mathsf{KEYS}$
Known facts:
1. $\mathsf{RAIN}$
2. $\mathsf{COLD}$

Example

Question: $$?\mathsf{HELMET}$$

Example

Reasoning:
- Have: $\mathsf{BIKE}\to\mathsf{HELMET}$
- Need: $\mathsf{BIKE}$
- Have: $\mathsf{SUN}\to\mathsf{BIKE}$
- Need: $\mathsf{SUN}$
- Don't!
- So: $\neg\mathsf{HELMET}$

Closed world assumption

If $A$ according to KB, then we can infer $A$ from KB.
If we can't infer $A$ from KB, then $\neg A$ according to KB.

Method

Check goal agains KB.
If goal is in conclusion, add antecedent to goals.
Lather, rinse, repeat until done.
If known fact in goals, success (via MP).
If no known fact in goals, failure.
Goal directed!

Programming conditionals

$$1,2,Fizz,3,4,Buzz,Fizz,7,8,Fizz,Fizz,Buzz,\dots$$

FizzBuzz


      for n in range(1,101):
        if n is divisible by 3 and n is divisible by 5:
          print("FizzBuzz")
        elif n is divisible by 3:
          print("Fizz")
        elif n is divisble by 5:
         print("Buzz")
        else:
         print(n)

Analysis

Knowledge base:

$\mathsf{DIV\_3}\land \mathsf{DIV\_5}\to \mathsf{PRINT\_FIZZBUZZ}$
$\mathsf{DIV\_3}\land \neg\mathsf{DIV\_5}\to \mathsf{PRINT\_FIZZ}$
$\neg\mathsf{DIV\_3}\land \mathsf{DIV\_5}\to \mathsf{PRINT\_BUZZ}$
$\neg\mathsf{DIV\_3}\land \neg\mathsf{DIV\_5}\to \mathsf{PRINT\_NUMBER}$

(Changing) facts:
1. $\neg\mathsf{DIV\_3}\land\neg\mathsf{DIV\_5}\leadsto \mathsf{PRINT\_NUMBER}$
2. $\neg\mathsf{DIV\_3}\land\neg\mathsf{DIV\_5}\leadsto \mathsf{PRINT\_NUMBER}$
3. $\mathsf{DIV\_3}\land\neg\mathsf{DIV\_5}\leadsto \mathsf{PRINT\_FIZZ}$
4. ...