Friday, January 14, 2005

Propositional Logic Review

Topics Covered (Sebastiani CADE 04 Slides pp. 8-24)
Boolean Propositional Logic
Connectives, Valuations, Truth Tables
Trees and DAGs
Best-case exponential saving in space and time.
Normal Forms
Negative Normal Form
expand implications; push negations down using de Morgan and double negation
Conjunctive Normal Form
Distribute \/ over /\, top-down. Worst-case exponential.