MATH 3265 Class Notes 02-10-2025

notelogic

Reviewed Conjunctive Normal Form and Disjunctive Normal Form

Theorem

Every formula is equivalent to one in CNF and one in DNF. In fact, for any truth table, there is a formula in CNF, and one in DNF that has that truth table.

Formulated an Algorithm to Find DNF for a Formula, and Algorithm to Find CNF for a Formula

Defined Adequate (for Propositional Logic)

We have shown by the CNF/DNF theorem, that $\{\vee ,\wedge ,\neg \}$ is adequate. Furthermore, $\{\neg ,\wedge \}$ is adequate, as is $\{\neg ,\vee \}$.