C463 / B551 Artificial Intelligence

Logic and Reasonning

Outline

Formal Logic

Propositional Logic

Truth Table
 A   B   A & B 
TTT
TFF
FTF
FFF
       
 A   B   A => B 
TTT
TFF
FTT
FFT

-
 A   B   C   (A x B) => C 
TTTT
TTFT
TFTT
TFF F
FTTT
FTF F
FFTT
FFFT

Proposition Evaluation

Problem Reduction

Problem Reduction - HC

HC Proposition Example
(and
    (xor AE AC AB)
    (xor EA CA BA)
    (xor BA BE BD)
    (xor AB EB DB)
    (xor CA CE CD)
    (xor AC EC DC)
    (xor DC DB)
    (xor CD BD)
    (xor EA EB EC)
    (xor AE BE CE)
)

Graph Coloring

Reasoning

Inference Rules

Conjunctive Normal Form

Examples

Resolution Algorithm for SAT

Automatic Proofs

Davis-Putnam Algorithm

Davis-Putnam Examples

Predicate (First Order) Logic

Model

Formal Definition

Quantifiers

Validity

Example: Graph Coloring (same graph as above)

A Problem

Representation

Additional Facts

Horn Clauses

Prolog Example

Reasoning in Predicate Logic

Unification

Chaining