12 ~ Theory of Computer Science
== P v P v Q v -, Q v -, R
by using 1 3
== P v Q v -, Q v -, R
by using Ii
Thus, P v Q v -, Q v -, R is a disjunctive normal form of the given formula.
EXAMPLE 1.12
Obtain the disjunctive normal form of
(P ;\ -, (Q ;\ R)) v (P =} Q)
Solution
(P ;\ -, (Q ;\ R)) v (P =} Q)
== (P ;\ -, (Q ;\ R) v (---, P v Q)
(step 1 using 1d
== (P ;\ (-, Q v -, R)) v (---, P v Q)
(step 2 using 1 7 )
== (P ;\ -, Q) v (P ;\ -, R) v -, P v Q
(step 3 using 1 4 and 1 3 )
Therefore, (P ;\ -, Q) v (P ;\ -, R) v -, P v Q is a disjunctive normal form
of the given formula.
For the same formula, we may get different disjunctive normal forms. For
example, (P ;\ Q ;\ R) v (P ;\ Q ;\ -, R) and P ;\ Q are disjunctive normal
forms of P ;\ Q. SO. we introduce one more normal form, called the principal
disjunctive nomwl form or the sum-of-products canonical form in the next
definition. The advantages of constructing the principal disjunctive normal
form are:
(i) For a given formula, its principal disjunctive normal form is unique.
(ii) Two formulas are equivalent if and only if their principal disjunctive
normal forms coincide.
Definition 1.8 A minterm in n propositional variables p], .,', P/1 is
QI ;\ Q2 ' " ;\ Q/l' where each Qi is either Pi or -, Pi'
For example. the minterms in PI and P 2 are Pi ;\ P 2 , -, p] ;\ P 2 ,
p] ;\ -, P'J -, PI ;\ -, P 2 , The number of minterms in n variables is 2/1.
Definition 1.9 A formula ex is in principal disjunctive normal form if ex is
a sum of minterms.
1.2.2 CONSTRUCTION TO OBTAIN THE PRINCIPAL
DISJUNCTIVE NORMAL FORM OF A GIVEN FORMULA
Step 1 Obtain a disjunctive normal form.
Step 2 Drop the elementary products which are contradictions (such as
P ;\ -, P),
Step 3 If Pi and -, Pi are missing in an elementary product ex, replace ex by
(ex;\ P) v (ex;\ -,PJ
http://engineeringbooks.net
== P v P v Q v -, Q v -, R
by using 1 3
== P v Q v -, Q v -, R
by using Ii
Thus, P v Q v -, Q v -, R is a disjunctive normal form of the given formula.
EXAMPLE 1.12
Obtain the disjunctive normal form of
(P ;\ -, (Q ;\ R)) v (P =} Q)
Solution
(P ;\ -, (Q ;\ R)) v (P =} Q)
== (P ;\ -, (Q ;\ R) v (---, P v Q)
(step 1 using 1d
== (P ;\ (-, Q v -, R)) v (---, P v Q)
(step 2 using 1 7 )
== (P ;\ -, Q) v (P ;\ -, R) v -, P v Q
(step 3 using 1 4 and 1 3 )
Therefore, (P ;\ -, Q) v (P ;\ -, R) v -, P v Q is a disjunctive normal form
of the given formula.
For the same formula, we may get different disjunctive normal forms. For
example, (P ;\ Q ;\ R) v (P ;\ Q ;\ -, R) and P ;\ Q are disjunctive normal
forms of P ;\ Q. SO. we introduce one more normal form, called the principal
disjunctive nomwl form or the sum-of-products canonical form in the next
definition. The advantages of constructing the principal disjunctive normal
form are:
(i) For a given formula, its principal disjunctive normal form is unique.
(ii) Two formulas are equivalent if and only if their principal disjunctive
normal forms coincide.
Definition 1.8 A minterm in n propositional variables p], .,', P/1 is
QI ;\ Q2 ' " ;\ Q/l' where each Qi is either Pi or -, Pi'
For example. the minterms in PI and P 2 are Pi ;\ P 2 , -, p] ;\ P 2 ,
p] ;\ -, P'J -, PI ;\ -, P 2 , The number of minterms in n variables is 2/1.
Definition 1.9 A formula ex is in principal disjunctive normal form if ex is
a sum of minterms.
1.2.2 CONSTRUCTION TO OBTAIN THE PRINCIPAL
DISJUNCTIVE NORMAL FORM OF A GIVEN FORMULA
Step 1 Obtain a disjunctive normal form.
Step 2 Drop the elementary products which are contradictions (such as
P ;\ -, P),
Step 3 If Pi and -, Pi are missing in an elementary product ex, replace ex by
(ex;\ P) v (ex;\ -,PJ
http://engineeringbooks.net