# Normal forms

• Remember that we also called “or” “disjunction” and “and” “conjunction”.
• A clause that contains only  is called a disjunctive clause and only  is called a conjunctive clause.
• Negation is allowed, but only directly on variables.
• p¬qr: a disjunctive clause
• ¬pq¬r: a conjunctive clause
• ¬p¬qr: neither
• If we put a bunch of disjunctive clauses together with , it is called conjunctive normal form.
• For example: (pr)(¬q¬r)q is in conjunctive normal form.
• Similarly, putting conjunctive clauses together with , it is called disjunctive normal form.
• For example: (p¬qr)(¬q¬r) is in disjunctive normal form.
• More examples:
• (pq¬rs)(¬qs)(ps) is in disjunctive normal form.
• (pq¬rs)(¬qs)¬s is in conjunctive normal form.
• (pr)(q(p¬q)) is not in a normal form.
• ¬pqr and ¬pqr are in both normal forms.
• It turns out we can turn any proposition into either normal form.
• We can use the definitions to get rid of , and .
• Use DeMorgan’s laws to move any ¬ in past parens, so they sit on the variables.
• Use double negation to get rid of any ¬¬ that showed up.
• Use the distributive rules to move things in/out of parens as we need to.
• For example, converting to conjunctive normal form:
¬((¬p¬q)¬r)¬((¬¬p¬q)¬r)¬((p¬q)¬r)¬(p¬q)¬¬r¬(p¬q)r(¬p¬¬q)r(¬pq)r(¬pr)(qr)[definition][double negation][DeMorgan’s][double negation][DeMorgan’s][double negation][distributive]
• It was actually in disjunctive normal form in the second-last step.
• Why would we want to convert to a normal form?
• May be easier to prove equivalence: to show AB, convert both to normal form, and then re-write one proof backwards.
• Maybe we simplify a lot: if we end up with (p¬p) terms, we know they are true.
• Proving theorems about all propositions: only have to handle boolean expressions in a normal form and that covers every proposition.
• Shows that we can use circuitry to calculate any boolean expression with two layers of logic gates.
• Another example:
(pq)(¬rq)¬(pq)(¬rq)¬(¬pq)(¬rq)(¬¬p¬q)(¬rq)(p¬q)(¬rq)[definition][definition][DeMorgan’s][double negation]
• At this point, it’s in DNF. Continuing…
(pq)(¬rq)(p¬q)(¬rq)(p(¬rq))(¬q(¬rq))(p(¬rq))(¬q¬r)(¬qq)(p(¬rq))(¬q¬r)T(p(¬rq))(¬q¬r)(p¬r)(pq)(¬q¬r)[as above][distributive][distributive][negation][identity][distributive]