In this note, we study some standard ways (normal forms) of representing formulas. The rules are:

1. Only $\wedge$, $\vee$, and $\neg$ are used.
2. Any negations are attached to propositional variables, not to larger expressions.
3. The $\vee$’s and the $\wedge$’s are organized in the manner described below: A literal is either a propositional variable (such as $p$) or the negation of a single variable (such as $\neg q$). If a formula is an $\wedge$ of $\vee$’s of literals we say it is in CNF (Conjunctive Normal Form). For example, \begin{align*}(p\vee q)\wedge(\neg p\vee q)\wedge(p\vee\neg q)\wedge(\neg p\vee \neg q)\\p\wedge\neg p\\(p\vee\neg q\vee r)\wedge(\neg s\vee t)\end{align*} are all in CNF. One may wonder why $p\wedge\neg p$ is in CNF. That’s because it is logically equivalent to $(p\vee p)\wedge(\neg p\vee\neg p)$. A formula is in DNF (Disjunctive Normal Form), on the other hand, is an $\vee$ of $\wedge$’s of literals. For example, $$(p\wedge\neg q\wedge r)\vee(\neg r\wedge t)$$ is in DNF. $p\wedge\neg p$ is also in DNF because it is logically equivalent to $(p\wedge\neg p)\vee (p\wedge\neg p)$. Similarly, $p\vee q$ is in both CNF and DNF.

Example. $(p\vee\neg q\vee r)\wedge(\neg q\vee t)$ is in CNF. Formulae $p\vee\neg q\vee r$ and $\neg q\vee t$ are clauses of the formula. The clauses of a CNF formula are disjuncts of literals while the clauses of a DNF formula are conjuncts of literals. That is to say, a CNF formula is a conjunction of disjuncts of literals and a DNF formula is a disjunction of conjuncts of literals.

A CNF formula is true if at least one literal from each clause is true. Similarly, a DNF formula is true if and only of there is at least one disjunct (clause) in which all the literals are true. For example, the DNF formula $$(\neg p\wedge q)\vee(p\wedge r)$$ is true when $p$ is false and $q$ is true.

Theorem. (De Morgan’s Law) \begin{align*}\neg(p\wedge q)&\equiv\neg p\vee\neg q\\\neg(p\vee q)&\equiv\neg p\wedge\neg q\end{align*}

Proof. It can be easily proved by truth table. We prove only the first one here. The proof of the second one is left for exercise. $$\begin{array}{|c|c|c|c|c|c|c|}\hline p & q & p\wedge q &\neg(p\wedge q) & \neg p & \neg q & \neg p\vee\neg q\\\hline T & T & T & F & F & F &F\\\hline T & F & F & T &F & T & T\\\hline F & T & F & T & T & F & T\\\hline F & F & F & T & T & T & T\\\hline\end{array}$$

Example. Using commutative laws, associative laws, distributive laws we learned here along with De Morgan’s law, we can write a given formula into its equivalent formula in a normal form. To see this let us consider the formula $$p\vee(q\wedge(r\vee(s\wedge t)))$$ It can be written into an equivalent formula in conjunctive normal form. \begin{align*}p\vee(q\wedge(r\vee(s\wedge t)))&\equiv (p\vee q)\wedge(p\vee(r\vee(s\wedge t))\\&\equiv(p\vee q)\wedge(p\vee((r\vee s)\wedge(r\vee t))\\&\equiv(p\vee q)\wedge(p\vee(r\vee s))\wedge(p\vee(r\vee t))\\&\equiv(p\vee q)\wedge(p\vee r\vee s)\wedge(p\vee r\vee t)\end{align*} But then it can also be written into an equivalent formula in disjunctive normal form. \begin{align*}p\vee(q\wedge(r\vee(s\wedge t)))&\equiv p\vee((q\wedge r)\vee(q\wedge(s\wedge t)))\\&\equiv p\vee(q\wedge r)\vee(q\wedge s\wedge t)\end{align*} In general, the following theorem holds.

Theorem. Every formula is equivalent to one in conjunctive normal form, and also to one in disjunctive normal form.

We are not going to prove the theorem here but interesting readers can find a proof in the reference [1] below.

Example. Write $(\neg p\vee q)\Longrightarrow\neg p$ in disjunctive normal form.

Solution. \begin{align*}(\neg p\vee q)\Longrightarrow\neg p&\equiv\neg(\neg p\vee q)\vee\neg q\\&\equiv(\neg\neg p\wedge\neg q)\vee\neg q\\&\equiv p\vee\neg q\vee\neg q\\&\equiv p\vee\neg p\vee\neg q\end{align*} Since $p\vee\neg p$ is a tautology, $(\neg p\vee q)\Longrightarrow\neg p$ is a tautology.

As shown in the above example, any expression that can be simplified to become a tautology must be a tautology itself. Determining whether a formula is a tautology is a fundamental problem of computer science. Using truth table is in deed not an effective method to tackle the problem because the truth table of a formula with a large number of variables would become too big to handle for us. For instance, the truth table for a formula with 30 variables would have $2^{30}=1,073,741,824$ rows, more than a billion rows! It is yet unknown if there is an effective algorithm to determine satisfiability, in particular whether a formula is a tautology.

References.

[1] Essential Discrete Mathematics for Computer Science, Harry Lewis and Rachel Zax, Princeton University Press, 2019