Truth Tables

Overview

In classical logic, every proposition can be written in disjunctive normal form (DNF) and conjunctive normal form (CNF). This is evident with the use of truth tables. To write a proposition in DNF, write its corresponding truth table and $\vee$ each row that evaluates to $T$. To write the same proposition in CNF, apply $\vee$ to each row that evaluates to $F$ and negate it.

$\neg (a\Rightarrow b)\iff c$

It’s truth table looks like

\neg & (a & \Rightarrow & b) & \Leftrightarrow & c \\ \hline F & T & T & T & F & T \\ F & T & T & T & T & F \\ T & T & F & F & T & T \\ T & T & F & F & F & F \\ F & F & T & T & F & T \\ F & F & T & T & T & F \\ F & F & T & F & F & T \\ F & F & T & F & T & F \end{array}$$ and it's DNF looks like

(a \land b \land \neg c) \lor (a \land \neg b \land c) \lor (\neg a \land b \land \neg c) \lor (\neg a \land \neg b \land \neg c)

$$I{t}^{\prime }sCNFresultsfromapplyingDeMorga{n}^{\prime }sLawtothetruthtabl{e}^{\prime }s"complement":$$

\neg( (a \land b \land c) \lor (a \land \neg b \land \neg c) \lor (\neg a \land b \land c) \lor (\neg a \land \neg b \land c) )

## Bibliography * Gries, David. *The Science of Programming*. Texts and Monographs in Computer Science. New York: Springer-Verlag, 1981. * Herbert B. Enderton, *Elements of Set Theory* (New York: Academic Press, 1977).