Let A(P_{1}, P_{2}, P_{3}, …, P_{n}) be a statement formula where P_{1}, P_{2}, P_{3}, …, P_{n} are the atomic variables. If A has truth value T for all possible assignments of the truth values to the variables P_{1}, P_{2}, P_{3}, …, P_{n} , then A is said to be a tautology. If A has truth value F, then A is said to be identically false or a contradiction.
1.2.1 Disjunctive
A product of the variables and their negations in a formula is called an elementary product. A sum of the variables and their negations is called an elementary sum. That is, a sum of elementary products is called a disjunctive normal form of the given formula.
Example:
- PÙ (P® Q) Û PÙ (ù PÚ Q) Û (PÙ ù P)Ú (PÙ Q).
- ù (P Ú Q) (PÙ Q) Û (ù (PÚ Q)Ù (PÙ Q))Ú ((PÚ Q)Ù ù (PÙ Q))
Û (ù P Ù ù Q Ù P Ù Q) Ú (P Ù ù P) Ú (Q Ù ù P) Ú (P Ù ù Q) Ú (Q Ù ù Q).
1.2.2 Conjunctive
A formula which is equivalent to a given formula and which consists of a product of elementary sums is called a conjunctive normal form of a given formula.
Example 1:
(b) ù (P Ú Q) Û ù P Ù ù Q.
(c) ù (P Q) Û ù ((P® Q) Ù (Q® P))
Û ù ((ù P Ú Q) Ù (ù Q Ú P))
Û ù (ù P Ú Q) Ú ù (ù Q Ú P)
Û (P Ù ù Q) Ú (Q Ù ù P)
Û (P Ú Q) Ù (Q Ú ù Q) Ù (P Ú ù P) Ù (ù P Ú ù Q).
(d) ù (P Ú Q) (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) Ù (ù P Ú ù Q Ú ù Q).
Example 2:
ù B Ú (ù A Ù B) Ú (A Ù B) Û ù B Ú ((ù A Ú A) Ù B)
Û (ù B Ú ù A Ú A) Ù (ù B Ú B)
Û T Ù T
Û T.
Therefore, it is a tautology.
(b) Show that the formula (ù B Ù A) Ù B is a contradiction.
(ù B Ù A) Ù B Û A Ù (B Ù ù B)
Û A Ù F
Û F.
Therefore, it is a contradiction.
(c) Show that (Q® P) Ù ( ù P Ù Q) is a contradiction.
(Q® P) Ù ( ù P Ù Q) Û (ù Q Ú P) Ù (ù P Ù Q)
Û (ù P Ù Q Ù ù Q) Ú (P Ù ù P Ù Q)
Û F Ú F
Û F.
Therefore, it is a contradiction.
1.2.3 Principal Disjunctive Normal Form (PDNF)
Let us assume A and B be two statement variables. All possible formulas by using conjunction are given as follows. The total number of formulas for two variables A and B are 2^{2} formulas. They are A Ù B, A Ù ùB,
ùA Ù B and ù A Ù ù B.
These are called minterms or Boolean conjunctions of A and B. The minterms (2^{n} terms) are denoted by M_{0}, M_{1}, … ,M_{2}^{n}_{-1}.
A formula equivalent to a given formula consisting of the disjunction of minterms only is called PDNF of the given formula.
Example 1:
P | Q | ù PÚ ù Q | P ù Q | (ù PÚ ù Q) ® (P ù Q) |
T | T | F | F | T |
T | F | T | T | T |
F | T | T | T | T |
F | F | T | F | F |
(ù PÚ ù Q)® (P ù Q) Û (PÙ Q) Ú (PÙ ù Q) Ú (ù PÙ Q)
Û (ù PÙ Q) Ú (PÙ ù Q) Ú (PÙ Q)
Û
Example 2:
Obtain the PDNF of
P | Q | P ® Q |
T | T | T |
T | F | F |
F | T | T |
F | F | T |
P® Q Û (PÙ Q) Ú (ù PÙ Q) Ú (ù PÙ ù Q)
Û (ù PÙ ù Q) Ú (ù PÙ Q) Ú (PÙ Q)
Û
Procedure for obtaining PDNF
Step2 : Use De Morgan’s law.
Step3 : Use distributive law.
Step4 : Introduce missing factor in the disjunction.
Step5 : If there is elementary product of the form.
(PÙ ù P) Ú ( ) Ú …… , delete P Ù ù P.
For every truth value T in the truth table of the given formula, select minterm which also has the value T for the same combination of the truth values of P and Q. The disjunction of these minterms will be equivalent to the given formula.
To find a particular minterm M_{i}, the subscript i is expressed in the binary representation and suitable number of 0’s are added to the left.
Example 3:
Obtain PDNF for .
Assign 1 for P and 0 for ù P.
Example 4:
Obtain PDNF for .
Solution:
Example 5:
Û P® ((P® P Ù Q))
Û P® (ù P Ú (P Ù Q))
Û ù P Ú (ù P Ú (P Ù Q))
Û ù P Ú (P Ù Q)
Û (ù P Ù (Q Ú ù Q)) Ú (P Ù Q)
Û (ù P Ù Q) Ú (ù P Ù ù Q) Ú (P Ù Q)
Û (ù P Ù ù Q) Ú (ù P Ù Q) Ú (P Ù Q)
Û .
1.2.4 Principal Conjunctive Normal Forms (PCNF)
The duals of minterms are called maxterms. For a given number of variables the maxterm consists of disjunctions in which each variable or its negation, but not both, appears only once.
For a given formula, an equivalent formula consisting of conjunctions of maxterms only is known as its principal conjunctive normal form. This is also called the product of sums canonical form.
Example 1:
Solution:
(ù P® R) Ù (Q P) Û (P Ú R) Ù ((Q® P) Ù (P® Q))
Û (P Ú R) Ù ((ù Q Ú P) Ù (ù P Ú Q))
Û (P Ú R Ú (Q Ù ù Q)) Ù ((P Ú ù Q Ú (R Ù ù R)) Ù (ù P Ú Q Ú (R Ù ù R))
Û (P Ú Q Ú R) Ù (P Ú ù Q Ú R) Ù (P Ú ù Q Ú ù R) Ù (ù P Ú Q Ú R) Ù (ù P Ú Q Ú ù R)
S Û p (0,2,3,4,5).
ù S Û consisting of missing maxterms
Û M_{1} Ù M_{6} Ù M_{7}
Û (P Ú Q Ú ù R) Ù (ù P Ú ù Q Ú R) Ù (ù P Ú ù Q Ú ù R).
Example2:
Obtain PCNF for A : (ù P® R) Ù ((Q® P) Ù (P® Q)).
Solution:
A Û (PÚ R)Ù ((ù QÚ P)Ù (ù PÚ Q))
Û (PÚ RÚ (QÙ ù Q)) Ù (PÚ ù QÚ (RÙ ù R)) Ù (ù PÚ QÚ (RÙ ù R))
Û (PÚ QÚ R)Ù (PÚ ù QÚ R)Ù (PÚ ù QÚ R)Ù (PÚ ù QÚ ù R)Ù (ù PÚ QÚ R)Ù (ù PÚ QÚ ù R)
Û (PÚ QÚ R) Ù (PÚ ù QÚ R) Ù (PÚ ù QÚ ù R) Ù (ù PÚ QÚ R) Ù (ù PÚ QÚ ù R)
Û p (0,2,3,4,5).
Example 3:
From the given truth table formula S, determine its PDNF and PCNF
Table 1.2.4
A | B | C | S |
T | T | T | T |
T | T | F | F |
T | F | T | F |
T | F | F | F |
F | T | T | F |
F | T | F | F |
F | F | T | F |
F | F | F | T |
the PDNF of S .
By choosing the maxterms corresponding to each F value of S,
the PCNF of S Û (ù A Ú ù B Ú C) Ù (ù A Ú B Ú ù C) Ù (ù A Ú B Ú C) Ù (A Ú ù B Ú ù C) Ù (A Ú ù B Ú C)
Ù (A Ú B Ú ù C) .
Example 4:
Form the given truth table formula S, determine its PDNF and PCNF
A | B | C | S |
T | T | T | F |
T | T | F | F |
T | F | T | T |
T | F | F | F |
F | T | T | T |
F | T | F | T |
F | F | T | F |
F | F | F | T |
the PDNF of S Û (A Ù ù B Ù C) Ú (ù A Ù B Ù C) Ú (ù A Ù B Ù ù C) Ú (ù A Ù ù B Ù ù C)
Û .
By choosing maxterms corresponding to each F value of S,
the PCNF of S Û (ù A Ú ù B Ú ù C) Ù (ù A Ú ù B Ú C) Ù (ù A Ú B Ú C) Ù (A Ú B Ú ù C)
Û p(1,4,6,7).
Example 5:
Obtain the product of sums canonical form of the formula A which is given by
(P Ù Q Ù R) Ú (ù P Ù Q Ù R) Ú (ù P Ù ù Q Ù ù R)
Solution:
ù A Û (ù P Ú ù Q Ú ù R) Ù (P Ú ù Q Ú ù R) Ù (P Ú Q Ú R)
Û p(0,3,7).
ù (ù A) Û consisting of missing maxterms
Û p(1,2,4,5,6)
Û (P Ú Q Ú ù R) Ù (P Ú ù Q Ú R) Ù (ù P Ú Q Ú R) Ù (ù P Ú Q Ú ù R) Ù (ù P Ú ù Q Ú R) .
Example 6:
Obtain the product-of-sums canonical form of the formula A, which is given by
(ù P Ù Q Ù R Ù ù S) Ú (P Ù ù Q Ù ù R Ù S) Ú (P Ù ù Q Ù R Ù ù S) Ú (ù P Ù Q Ù ù R Ù S) Ú (P Ù Q Ù ù R Ù ù S).
Solution:
ù A Û (P Ú ù Q Ú ù R Ú S) Ù (ù P Ú Q Ú R Ú ù S) Ù (ù P Ú Q Ú ù R Ú S) Ù (P Ú ù Q Ú R Ú ù S) Ù
(ù P Ú ù Q Ú R Ú S)
Û (P Ú ù Q Ú R Ú ù S) Ù (P Ú ù Q Ú ù R Ú S) Ù (ù P Ú Q Ú R Ú ù S) Ù (ù P Ú Q Ú ù R Ú S) Ù
(ù P Ú ù Q Ú R Ú S)
Û p(5, 6, 9, 10, 12).
ù (ù A) Û consisting of missing maxterms
Û p(0,1,2,3,4,7,8,11,13,14,15)
Û M_{0}Ù M_{1}Ù M_{2}Ù M_{3}Ù M_{4}Ù M_{7}Ù M_{8}Ù M_{11}Ù M_{13}Ù M_{14}Ù M_{15
} Û (P Ú Q Ú R Ú S) Ù (P Ú Q Ú R Ú ù S) Ù (P Ú Q Ú ù R Ú S) Ù (P Ú Q Ú ù R Ú ù S) Ù (P Ú ù Q Ú R Ú S)
Ù (P Ú ù Q Ú ù R Ú ù S) Ù (ù P Ú Q Ú R Ú S) Ù (ù P Ú Q Ú ù R Ú ù S) Ù (ù P Ú ù Q Ú R Ú ù S) Ù
(ù P Ú ù Q Ú ù R Ú S) Ù (ù P Ú ù Q Ú ù R Ú ù S).
Example 7:
Obtain the product of sums canonical form of (P Ù Q) Ú (ù P Ù Q) Ú (P Ù ù Q).
Solution:
ù A Û (ù P Ú ù Q) Ù (P Ú ù Q) Ù (ù P Ú Q)
Û (P Ú ù Q) Ù (ù P Ú Q) Ù (ù P Ú ù Q)
Û p(1,2,3).
ù (ù A) Û consisting of missing maxterms
Û p(0)
Û M_{0}
Û P Ú Q.
1. Write the following statements in symbolic form using the statements
P : Sandeep is rich. Q : Sandeep is happy.
Sandeep is poor but happy. - Sandeep is rich or unhappy.
- Sandeep is neither rich nor happy.
- Sandeep is poor or he is both rich and unhappy.
2. Write the negation of each of the following statements as simply as possible.
He is tall but handsome. - He has blond hair or blue eyes.
- He is neither rich nor happy.
- He lost his job or he did not go to work today.
- Neither Siva nor Sriram is unhappy.
- Ajay speaks Bengali or Hindi, but not German.
- If he studies, he will pass the exam.
- He swims if and only if the water is warm.
- If it snows, then he does not drive the car.
- If it is cold, then he wears a coat but no sweater.
- If he studies then he will go to college or to art school.
3. Write the following statement in symbolic form using the statements
P: It is cold. Q: It rains.
It rains only if it is cold. - A necessary condition for it to be cold is that it rain.
- A sufficient condition for it to be cold is that it rain.
- Whenever it rains it is cold.
- It never rains when it is cold.
4. Write each statement in symbolic form using
P : He is rich Q : He is happy.
If he is rich then he is unhappy. - He is neither rich nor happy.
- It is necessary to be poor in order to be happy.
- To be poor is to be unhappy.
- Being rich is a sufficient condition to being happy.
- Being rich is a necessary condition to being happy.
- One is never happy when one is rich.
- He is poor only if he is happy.
- To be rich means the same as to be happy.
- He is poor or else he is both rich and happy.
5. Write the negation of each statement in as simple a sentence as possible.
If Sindhu is a poet, then she is poor. - If Madhu passed the test, then he studied.
- If x is less than zero, then x is not positive.
- If it is cold, he wears a hat.
- If productivity increases, then wages rise.
6. From the formulas given below select those which are well formed and indicate which ones are tautologies
or contradictions.
(A ® ( A Ú Q)) - ((A ® (ù A)) ® ù A)
- (ù B Ù A) Ù B
- ((A ® (B ® C)) ® ((A ® B) ® (A ® C)))
- ((ù A ® B) ® (B ® A))
- ((A Ù B) A)
7. Obtain the PCNF of the following
- ù (A B)
8. Obtain the product of sums canonical forms of the following.
(P Ù Q Ù R) Ú (ù P Ù Q Ù R) Ú (ù P Ù ù Q Ù ù R) Ú (ù P Ù ù Q Ù R). - (ù P Ù Q Ù R Ù ù S) Ú (P Ù ù Q Ù ù R Ù S) Ú (P Ù ù Q Ù R Ù ù S) Ú (ù P Ù Q Ù ù RÙ S) Ú
(P Ù Q Ù R Ù ù S). - (ù P Ù ù Q) Ú (ù P Ù Q) Ú (P Ù ù Q).
- (P Ù Q) Ú (ù P Ù Q Ù R).
9. Obtain the PDNF and PCNF of the following
(Q Ù (P Ú ù Q)). - P Ú (ù P® (Q Ú (ù Q® R))).
- (P® (Q Ù R)) Ù (ù P® (ù Q Ù ù R)).
- P ® (P Ù (Q® P)).
- (Q® P) Ù (ù P Ù Q).
2 comments:
this was very useful... thanks...
it is very useful thankxx for it.
Post a Comment