Problem reduction

Problem reduction :

We have considered search strategies for OR graph through which we want to find a single path to a goal .such structure represent the fact that we will know how to get from anode to a goal state if we can discover how to get from that nod e to a goal sate along any one of the branches leaving it

AND – OR Graph.

Example
To London






Go by car Go by train Go by plane






Get to the Catch train Get from
station London station


AND- OR Graph


- All AND successors must be expanded.
- Only expand OR successor until one yield true.


• Heuristic may be applied to choosing which OR successor to expand.










T






T T



T T T




Knowledge Representation

1. Proposional logical and resolution in proposional logical (Algorithm) logic and theory proving.

If P than Q.

If the animal has feathers then it is a bird.
P Q
Antecendent consequent
implies
Feathers (X) bird (X).
Feathers (Albatross) bird (Albatross).

If A B

If A & B C Conjunction.

If A V B C Disjunction.

- When expressions are joined by (&) they from a conjunction and each part is called conjunct.
- When expression are joined by (V) they from a disjunction and each part is called disjunct.
& , V , ~ , are called logical connectives.
E1 E2

E1 E2 E1 E2
E1 V E2 E1 8 E2 ~ E1 ~ E1 V E2
T T T T T F T
T F F T F F F
F T T T F T T
F F T F F T T




E1 E2 ~ E1 V E2



~ (~ A) = A
E1 & E2 E2 & E1 commutative law.
E1 V E2 E2 V E1


E1 & ( E2 V E3) ( E1 & E2 ) V (E1 & E3) distribution law
E1 V ( E2 & E3) (E1 V E2) & (E1 V E3)



E1 & (E2 & E3) (E1 & E2) & E3 associative law
E1 V (E2 V E3) (E1 V E2) V E3

~ ( E1 & E2) (~ E1) V (~ E2)
~ ( E1 V E2) (~ E1) & (~ E2) demorgans law

~ X P (x) ? X p (x)

~ X p (x) ? X p (x)

for all

There exist for all :quantifiers