Recognizing Normal Forms — Select the expressions that are in CNF or DNF!

(p ∧ q) ∨ (¬p ∧ r) → DNF. (p ∨ q) ∧ (¬p ∨ r) → CNF. (¬p ∨ q) → both CNF and DNF. The last one is not a pure normal form.

Normal Forms

Equivalence Deduction

Logical expressions can be rewritten into standard forms. These are called normal forms. The two most important types: conjunctive normal form (CNF) and disjunctive normal form (DNF).

Disjunctive Normal Form (DNF)

DNF is a form where the expression is a disjunction of conjunctions. In other words: conjunctions within each part, and the parts are connected by disjunction.

This is DNF: first part (p ∧ q), second part (¬p ∧ r), connected by ∨.

Conjunctive Normal Form (CNF)

CNF is a form where the expression is a conjunction of disjunctions. In other words: disjunctions within each part, and the parts are connected by conjunction.

This is CNF: first part (p ∨ q), second part (¬p ∨ r), connected by ∧.

Why Are They Useful?

They help simplify logical expressions.
Basic forms in automated proof systems.
Computer algorithms can work with them more easily.

Example of Transformation

Take the expression: (p → q). This can be transformed to: (¬p ∨ q). This is already both CNF and DNF, since there's only one ∨.

Summary

DNF: disjunction of conjunctions. CNF: conjunction of disjunctions. Every logical expression can be rewritten into one of these normal forms.

Practice Exercise

We have reviewed and checked the materials, but errors may still occur. The content is provided for educational purposes only, so use it at your own responsibility and verify with other sources if needed.