14 ~ Theory of Computer Science
subset of {OO, 01, 10, 11}. As the number of subsets is 2
4 , the number of
distinct formulas is 16. (Refer to the remarks made at the beginning of this
section.)
The truth table and the principal disjunctive normal form of a are closely
related. Each minterm corresponds to a particular assignment of truth values
to the variables yielding the truth value T to a. For example, P 1\ Q 1\ --, R
corresponds to the assignment of T, T, F to P, Q and R, respectively. So, if
the truth table of a is given. then the minterms are those which correspond
to the assignments yielding the truth value T to ex.
EXAMPLE 1.1 5
For a given formula a, the truth values are given in Table 1.12. Find the
principal disjunctive normal form.
TABLE 1.12 Truth Table of Example 1.15
P
Q
R
a
T
T
T
T
T
T
F
F
T
F
T
F
T
F
F
T
F
T
T
T
F
T
F
F
F
F
T
F
F
F
F
T
Solution
We have T in the a-column corresponding to the rows 1, 4, 5 and 8. The
minterm corresponding to the first row is P 1\ Q 1\ R.
Similarly, the mintem1S corresponding to rows 4, 5 and 8 are respectively
P 1\ --, Q 1\ ---, R, --, P 1\ Q 1\ Rand --, P 1\ ---, Q 1\ --, R. Therefore, the principal
disjunctive normal form of ex is
ifI\Ql\mvifl\--,QI\--,mvbPI\Ql\mvbPI\--,QI\--,m
We can form the 'dual' of the disjunctive normal form which is termed the
conjunctive normal form.
DefInition 1.10 A formula is in conjunctive normal form if it is a product
of elementary sums.
If a is in disjunctive normal form, then --, a is in conjunctive normal
form. (This can be seen by applying the DeMorgan's laws.) So to obtain the
conjunctive normal form of a, we construct the disjunctive normal form of
--, a and use negation.
Deimition 1.11 A maxterm in n propositional variables PI, P 2 , ••. , P n is
Ql V Q2 V ... V QII' where each Qi is either Pi or --, Pi'
http://engineeringbooks.net