Conjunctive and Disjunctive Normal Form (PDNF & CDNF)

Conjunctive and Disjunctive Normal Form: Product of elementary sums are called conjunctive normal form (CNF) whereas sum of elementary products are called disjunctive normal form (DNF).

Elementary product:

Product of the variables and their negations. For example, p∧q, p∧~q, ~p∧~q, p, q etc.

Elementary sum:

Sum of the variables and their negations. For example, p∨q, p∨~q, ~p∨~q, p, q etc.

Normal Form

There are two types of normal forms:

1. Conjunctive Normal Form (CNF): This is the product of elementary sums. For example, (p∨q)∧(~p∨~q).
2. Disjunctive Normal Form (DNF): This is the sum of elementary products. For example, (p∧~q)∨(p∧~q).

Method

1	Remove → and ↔ by using the following logical equivalences: p→q ≡ ~p∨q p↔q ≡ (p→q)∧(q→p)
2	Eliminate ~ before sums and products by De Morgan’s laws: ~(p∧q) ≡ ~p∨~q and ~(p∨q) ≡ ~p∧~q.
3	Apply distributive laws.

Lets understand the above procedure with examples.

Solved Problems

$\boxed{\color{blue}\textbf{Q}1:}$ Convert p∧(p→q) into CNF and DNF.

Answer:

For CNF:

p∧(p→q) ≡ p∧(~p∨q)

For DNF:

p∧(p→q)

≡ p∧(~p∨q)

≡ (p∧~p)∨(p∧q)

$\boxed{\color{blue}\textbf{Q}2:}$ Convert (p→q)∧~q into CNF and DNF.

Answer:

For CNF:

(p→q)∧~q ≡ (~p∨q)∧~q

For DNF:

(p→q)∧~q

≡ (~p∨q)∧~q

≡ (~p∧~q)∨(q∧~q)

$\boxed{\color{blue}\textbf{Q}3:}$ Convert ~(p∧q)↔(p∨q) into CNF and DNF.

Answer:

For CNF:

~(p∧q)↔(p∨q)

≡ [~(p∧q)→(p∨q)] ∧ [(p∨q)→~(p∧q)]

≡ [(p∧q)∨(p∨q)] ∧ [~(p∨q)∨~(p∧q)]

≡ (p∨p∨q)∧(q∨p∨q) ∧ [(~p∧~q)∨(~p∨~q)]

≡ (p∨p∨q)∧(q∨p∨q) ∧ (~p∨(~p∨~q)) ∧ (~q∨(~p∨~q))

≡ (p∨p∨q) ∧ (q∨p∨q) ∧ (~p∨~p∨~q) ∧ (~q∨~p∨~q)

For DNF:

~(p∧q)↔(p∨q)

≡ [~(p∧q)∧(p∨q)] ∨ [~(~(p∧q))∧~(p∨q)]

≡ [(~p∨~q)∧(p∨q)] ∨ [(p∧q)∧(~p∧~q)]

≡ (~p∧p)∨(~p∧~q)∨(~q∧p)∨(~q∧q)∨(p∧q∧~p∧~q)

Min Terms and Max terms

For propositional variables p and q, minterms and maxterms are given as follows:

Minterms: p∧q, p∧~q, ~p∧q, ~p∧~q

Maxterms: p∨q, p∨~q, ~p∨q, ~p∨~q

NOTE: For n propositional variables, there will be 2ⁿ minterms (or maxterms).

Principal Disjunctive Normal Form (PDNF)

Principal disjunctive normal form i.e PDNF is defined as the sum of minterms.

For example,

Principal Conjunctive Normal Form (PCNF)

Principal conjunctive normal form i.e PCNF is defined as the product of maxterms.

For example,

Method to get PDNF/PCNF

1. At first, obtain DNF or CNF.
2. Introduce the missing factors
3. Avoid duplications.

$\boxed{\color{blue}\textbf{Q}1:}$ Obtain the principal disjunctive normal form of p∨~q.

Answer:

p∨~q

≡ [p∧(q∨~q)]∨[~q∧(p∨~p)]

≡ (p∧q)∨(p∧~q)∨(~q∧p)∨(~q∧~p)

$\boxed{\color{blue}\textbf{Q}2:}$ Obtain the principal disjunctive normal form of p→q.

Answer:

p→q

≡ ~p∨q

≡ [~p∧(q∨~q)]∨[q∧(p∨~p)]

≡ (~p∧q)∨(~p∧~q)∨(q∧p)∨(q∧~p)

≡ (~p∧q)∨(~p∧~q)∨(p∧q)

Related Articles:

1. Mathematical Logic
2. Tautology, Contradiction, and Contingency
3. Logical Equivalence
4. Determine whether the following argument is valid