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]

Author: Team

1 thought on “Normal forms

Leave a Reply

Your email address will not be published. Required fields are marked *