4.2 Normal Forms: Conjunctive and Disjunctive

Propositional logic normal forms standardize complex statements into simpler structures. Conjunctive Normal Form (CNF) uses conjunctions of clauses, while Disjunctive Normal Form (DNF) uses disjunctions. These formats make it easier to analyze and compare logical expressions.

Converting to normal forms involves eliminating certain operators, pushing negations inward, and distributing operations. While these forms offer benefits like standardization and algorithmic analysis, they can also lead to longer, less intuitive statements. Understanding normal forms helps in problem-solving and checking logical equivalence.

Propositional Logic Normal Forms

Conversion to CNF

• Conjunctive Normal Form (CNF) represents propositional logic statements in a standardized format
  • CNF statements consist of a conjunction of clauses ($clause_1 \land clause_2 \land ... \land clause_n$)
  • Each clause is a disjunction of literals ($literal_1 \lor literal_2 \lor ... \lor literal_m$)
  • Literals are atomic propositions or their negations ($p$, $\lnot q$)
• Convert statements to CNF by applying logical equivalences and rules
  • Eliminate biconditionals ($\leftrightarrow$) and conditionals ($\rightarrow$)
    • $p \leftrightarrow q \equiv (p \rightarrow q) \land (q \rightarrow p)$
    • $p \rightarrow q \equiv \lnot p \lor q$
  • Push negations inward using De Morgan's laws
    • $\lnot (p \land q) \equiv \lnot p \lor \lnot q$
    • $\lnot (p \lor q) \equiv \lnot p \land \lnot q$
  • Distribute disjunctions over conjunctions
    • $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$

Conversion to DNF

• Disjunctive Normal Form (DNF) represents propositional logic statements in another standardized format
  • DNF statements consist of a disjunction of clauses ($clause_1 \lor clause_2 \lor ... \lor clause_n$)
  • Each clause is a conjunction of literals ($literal_1 \land literal_2 \land ... \land literal_m$)
• Convert statements to DNF using similar steps as CNF conversion
  • Eliminate biconditionals and conditionals using the same equivalences
  • Push negations inward with De Morgan's laws
  • Distribute conjunctions over disjunctions
    • $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

Advantages vs disadvantages of normal forms

• Normal forms (CNF and DNF) offer benefits for analyzing propositional logic statements
  • Standardization simplifies comparisons and enables the use of specialized algorithms (resolution)
  • Logical equivalence can be checked by converting statements to the same normal form
• However, normal forms also have drawbacks
  • Conversion may cause an exponential increase in statement size (CNF or DNF explosion)
  • Resulting statements can be less intuitive and harder to comprehend
  • Some logical properties (satisfiability) may be more challenging to determine in normal forms

Problem-solving with normal forms

• Check logical equivalence by converting statements to the same normal form
  1. Convert both statements to CNF (or DNF)
  2. Compare the resulting clauses; if identical (ignoring order), the original statements are logically equivalent
• Determine satisfiability based on the normal form
  • CNF: Satisfiable if every clause has at least one literal
  • DNF: Satisfiable if at least one clause contains no contradictory literals
• Simplify statements in normal forms
  1. Remove clauses subsumed by other clauses
  2. Eliminate duplicate literals within clauses
  3. Remove clauses containing a literal and its negation (tautologies)