Syntactical Transformations

Week 2

what is a literal?

a propositional symbol or the negation of a propositional symbol

What is the main rule of DNF?

disjunction may NOT appear in the scope of a conjunction

How to write a contradiction in both DNF and CNF?

P AND NOT P

How to write a tautology in both DNF and CNF

P OR NOT P

how to form DNF from a truth table?

1) complete the truth table

2) find the models of the formula

3) use conjunction to join the inputs which causes the formula to evaluate to true, for each model of the formula

4) use disjunction to join the conjunction formulas obtained from the previous step

what is the main rule of CNF?

a conjunction may NOT appear in the scope of a disjunction

how to form a CNF from a truth table?

1) complete the truth table

2) find the interpretations which makes formula evaluate to FALSE, using conjunction to join the inputs of each interpretation

3) use disjunction to join the conjunction formulas obtained from the previous step

4) negate the WHOLE of the formula obtained above and apply de Morgan’s law to simplify