LEARNING OBJECTIVES:
By the end of this class, the student will be able to:

1. Recall the definition of literal and of conjunctive and disjunctive normal forms.
2. Identify the structures of an expression in CNF and DNF.
3. Use CNF or DNF to simplify propositional logic expressions.

INDEX
DEFINITION OF LITERAL
DEFINITION OF NORMAL FORMS
NORMAL FORMS THEOREM

An interesting and useful result of propositional logic is related to normal forms. To delve into these topics, we first need to review some concepts.

Definition of Literal

A literal is any atomic expression or the negation of an atomic expression. Based on this, we talk about negative or positive literals depending on whether the atomic expressions are preceded by a negation or not. For example: A would be a positive literal and \neg A would be a negative literal.

Definition of Normal Forms

An expression F is in normal form when it can be written as a conjunction of disjunctions of literals, that is:

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

Similarly, there will be a disjunctive normal form (DNF) if it is written as the disjunction of conjunctions of literals:

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

Normal Forms Theorem

All propositional logic expressions are equivalent to an expression in DNF and another in CNF.

PROOF:

This can be demonstrated by induction on the complexity of formulas F.

• Base case: If F is an atomic expression, it can be written in CNF and DNF simultaneously because: F\equiv F_D \equiv F_C, where F_C:=((F\vee F)\wedge (F\vee F)) and F_D:=((F\wedge F)\vee (F\wedge F))
• Inductive step: Let G and H be any two expressions for which the theorem holds; that is, there exist H_C and G_C in CNF, and H_D and G_D in DNF such that:

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  So we can write:

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  Without loss of generality, if F:= \neg G, then using the substitution theorem on the generalized De Morgan’s laws, we have that:

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  On the other hand, if F:=G\wedge H, then by the substitution theorem:

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  which is a conjunctive normal form. And in the same way, if F:=H\vee G, then:

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  that is, a disjunctive normal form.

  Therefore, the induction is complete and all propositional logic expressions can be written in DNF and CNF.

The study of conjunctive normal form (CNF) and disjunctive normal form (DNF) in propositional logic is essential for simplifying and solving complex problems in mathematics and computer science. The theorem that states that any logical expression can be written in both DNF and CNF is highly relevant, as it allows for structuring propositions in a more manageable and standardized way, thus facilitating their analysis and manipulation. The importance of this result lies in providing a solid foundation for algorithm design, logical expression optimization, and efficient problem-solving in various fields of knowledge, such as artificial intelligence and software verification. Additionally, the proof technique by induction used to prove this theorem strengthens the understanding of the fundamental properties of logical expressions and their applicability in other mathematical contexts.