LOGIC Course

Conjunctive normal form (FNC)

  • A literal is a propositional variable or its negation
    • $p, \neg q$ are literals
    • $\neg \neg p, p \vee p$ are not literals
  • A clause is a disjunction of literals
    • $p, \neg p, p \vee \neg q$ are clauses
    • $\neg(p \vee q), p \wedge q, (\neg \neg p) \vee q$ are not clauses
  • A conjunctive normal form is a conjunction of clauses
    • $p, \neg p, p \vee \neg q, \neg p \wedge q, (p \vee q) \wedge r \wedge (p \vee r)$ are FNC
    • $\neg (p \wedge q), (\neg \neg p) \wedge q$ are not FNC

You can write any formula in FNC.

But be careful. You have, in order, to:

  • remove all $\bot$ using for example the equivalent $p \wedge \neg p$
  • replace all implications with its equivalent.
  • place directly all negations in variables using the equivalents:
    • $\neg \neg F \equiv F$
    • $\neg (F\wedge G) \equiv \neg F \vee \neg G$
    • $\neg (F\vee G) \equiv \neg F \wedge \neg G$
  • place all conjunction in first using the equivalent $F \vee (G \wedge H) \equiv (F \vee G) \wedge (F \vee H)$

There is also DNF which stands for disjunctive normal form: instead of putting the conjunction in first, you place the disjunctions. So a DNF is a disjunction of conjunction of literals. Yet, DNF is not much employed.