Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) in Boolean Algebra

Learn about Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF) in Boolean algebra. This guide explains how to represent Boolean expressions in DNF (Sum of Products) and CNF (Product of Sums), including maxterms and minterms.

Disjunctive Normal Form (DNF) and Conjunctive Normal Form (CNF)

Disjunctive Normal Form (DNF)

A Boolean expression is in Disjunctive Normal Form (DNF), also known as Sum of Products (SOP), if it's an OR of AND terms. Each AND term (product term) contains each variable or its complement exactly once. A DNF expression is essentially a series of AND statements connected by ORs.

Example: DNF

(The example (x₁' ∧ x₂' ∧ x₃') ∨ (x₁' ∧ x₂ ∧ x₃') ∨ (x₁ ∧ x₂ ∧ x₃) from the original text should be included here.)

Maxterms

A maxterm is an OR of literals where each variable appears exactly once (either complemented or not). Each maxterm is false for exactly one combination of input values.

Conjunctive Normal Form (CNF)

A Boolean expression is in Conjunctive Normal Form (CNF), also known as Product of Sums (POS), if it's an AND of OR terms. Each OR term (sum term) contains each variable or its complement exactly once. A CNF expression is essentially a series of OR statements connected by ANDs.

Example: CNF

(The example (x₁ ∨ x₂ ∨ x₃) ∧ (x₁ ∨ x₂ ∨ x₃) ∧ (x₁ ∨ x₂ ∨ x₃) ∧ (x₁' ∨ x₂ ∨ x₃') ∧ (x₁' ∧ x₂' ∧ x₃) from the original text should be included here.)

Constructing DNF and CNF

Given a Boolean function (a truth table), we can construct its DNF and CNF representations:

• DNF: Include a minterm for each row in the truth table where the function's output is 1.
• CNF: Include a maxterm for each row in the truth table where the function's output is 0.

Example: Constructing DNF and CNF from a Truth Table

(The example from the original text, showing the construction of DNF and CNF from a given truth table, should be included here. The truth table, the resulting DNF expression, and the resulting CNF expression should all be clearly presented.)

Principle of Duality

In Boolean algebra, the dual of an expression is obtained by switching AND (∧) and OR (∨) and switching 0 and 1. If an expression is true, its dual is also true.

Examples: Finding the Dual

(Three examples demonstrating how to find the dual of Boolean expressions are given in the original text and should be included here.)

Conclusion

DNF and CNF are standard forms for representing Boolean expressions, simplifying analysis and manipulation. The principle of duality provides a powerful tool for deriving new theorems and equivalences.