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.