Unit 1: Propositional Logic

Propositional Logic:
 Statement (Proposition) : A declarative sentence to which
truth values “true” or “false” can be assigned but not both.
We call such sentences Propositions (Statements).
 Ex. Sun rises in the east.
 2+3 = 4
 Man is mortal.
 12+9 = 3-2
 It is raining.
 Mumbai is the capital of india.
 London is a city.
 Narendra Modi is the 14th prime minister of india.
 1+1=2
 The logic that depends on the analysis of
proposition/statements is known as Propositional Logic
The following sentences are not statements(propositions)
 What is your name?
 Close the door.
 A is less than 2
Atomic and Compound statements
 Atomic statement : A statement which can not be divided further, is
called atomic statement (Simple statement or primary statement).
These statements are denoted by p,q,r,s,……
Ex. Milk is white Ex. 2+3 = 5
 Compound Statement : Two or more simple statements can be
combined to form a new statement. These new statements are called
Compound statements or Molecular Statements or Propositional
function or Statement formulas.
Ex. It is raining today and there are 20 tables in this room.
 Compound statements can be formed from atomic statements
through the use of following sentential connectives.
not, and , or , if then and if and only if .
 Connectives
 Used to combine two atomic statements. In proposition
logic we have generally 5 connectives.
 Or, and, negation, if-then, if and only if
 Negation: If p is a statement, then the negation of p,
written as ~p and read as “ not p ” is a statement.
Ex. p : London is a city.
~p : London is not a city.
 The truth table for not p is given below.

p
~p
T F
F T
 Conjunction (and) pq
 If p and q are two propositions, then the conjunction of p
and q is the statement p  q which is read as “ p and q ”.
 The statement p  q has the truth value T whenever both p
and q have truth value T; otherwise it has the truth value
false.
p q pq
F F F
F F
T T F
T F T
T
 Disjunction ( Or ) pq
 If p and q are two propositions, then the disjunction of p
and q is the statement p  q which is read as “ p or q”.
 The statement pq has the truth value F only when both p
and q have truth value F; otherwise it has the truth value T.

p q pq
F F F
F T T
T F T
T T T
 Implication (Conditional) pq
 If p and q are two propositions, then the statement pq
which is read as “ if p, then q ” or “ p implies q “.
 The statement pq has truth value F only when p is true
and q is false; otherwise it has a truth value T.
p q pq

F F T
F T T
T F F
T T T
Biconditional(if and only if) pq
 Biconditional : If p and q are two propositions, then the
statement pq, which is read as “p if and only if q” is
called a biconditional statement.
 The statement pq has the truth value T whenever both p
and q have identical truth values.

p q pq
F F T
F T F
T F F
T T T
 More on Implication
 The opposite of pq is p  q
 The converse of pq is qp
 The contra positive of pq is q  p
 Note : pq is logically equivalent to q  p
i.e., pq  q  p
or pq  q  p
* Ex. p: Today is Sunday
q: Today is Holiday
p  q : If today is Sunday, then today is Holiday
q  p : If today is not Holiday, then today is not Sunday
 If pq is true then it’s converse q  p need not be true.
 If pq is true then it’s opposite p  q need not be
true.
 Truth tables
 Our basic concern is to determine the truth value of a
statement formula for each possible combination of the
truth values of the component statements.
 A table showing all such truth values is called the truth
table of the formula.
 If there are ‘n’ distinct components in a statement formula,
we need nto consider 2 possible combinations of truth
values in order to obtain the truth table.
 Ex.1 Construct truth table for the statement formula P 
Q
P Q Q P  Q
F F T T
F T F F
T F T T
T T F T
 Truth tables - Examples
Ex : 2 Construct the truth table for (PQ)  P

P Q PQ P (PQ)  P

F F F T T
F T T T T
T F T F T
T T T F T

Some examples:

P ^ ~Q

P  (QR)

(P^Q)  (P
 Q)
 Truth tables - Examples
Ex.3 Construct the truth table for (PQ)  (QP)

P Q PQ QP (PQ)  (QP)

F F T T T
F T T F F
T F F T F
T T T T T

Note:

(PQ)  {(PQ)  (QP)}

 Well formed formulas
 A well formed formula can be generated by the following rules.
1. A statement variable standing alone is a well formed
formula.
2. If P is a well formed formula, then ~P is a well formed
formula.
3. If P and Q are well formed formulas, then (PQ) , (PQ) ,
(PQ) and (PQ) are well formed formulas.
4. A string of symbols containing the statement
variables,connectives and parenthesis is a well formed formula,
iff it can be obtained by finitely many applications of the rules
1,2 and 3.
 Ex. (PQ) , (PQ) , (P (PQ) ) , (P (Q R)) and
(PQ) (PQ) are well formed formulas.
 Ex. PQ , (PQ )Q ) and (P Q )  (Q) are not well
formed formulas.
 Tautology and Contradiction
 Tautology : A propositional function (Statement formula)
whose value is true for all possible values of the
propositional variables is called a Tautology ( A Universally
valid formula or a logical truth).
Ex: P  P is a tautology.
Ex. ( P  P )  Q is a tautology.
 Contradiction (Absurdity): A propositional function whose
truth value is always false is called a Contradiction
Ex. P  P is a Contradiction .
Ex. ( P  P )  Q is a Contradiction
 Contingency: A propositional function that is neither a
tautology nor a contradiction is called a Contingency.
Ex. P  Q , P  Q , P Q, ….
 Logical Equivalence & Tautological Implication
 Two propositional functions P and Q are logically
equivalent, if they have same truth tables. Then we write
PQ or P  Q
Ex: (P )  P
Ex: ( P  Q )  ( P  Q ).
Note : The symbol  is not a connective
 A Statement P is said to tautologically imply a Statement Q
if and only if PQ is a [Link] shall denote this as P
 Q.
 Here, P and Q are related to the extent that, Whenever P
has the truth value T then so does Q.
 Every logical implication is an implication, but all
implications are not logical implications.
More on Implications
 If P  Q and Q  P , then PQ.
 If PQ then PQ is a tautology.
 Ex: Show that ( P Q )  ( P  Q )

P Q PQ P PQ
F F T T T
F T T T T
T F F F F
T T T F T

 Since columns 3 and 5 are identical, The result follows

[Link] truth table for [(pq) (r)]  p]
 The truth table is given below

p q r pq r (pq) (r) [(pq) (r)] p]

F F F F T T F
F F T F F F T
F T F F T T F
F T T F F F T
T F F F T T T
T F T F F F F
T T F T T T T
T T T T F T T
Ex. Show that (PQ)  (Q  P)
 Let us prove the result using truth table.

P Q PQ Q P (Q P)

F F T T T T
F T T F T T
T F F T F F
T T T F F T
Ex. Using truth tables, show that ( P  Q )  (Q)
is a tautology

 The truth table is given below.

P Q PQ ( P  Q ( P  Q )  (Q)
Q)

F F T F T T
F T T F F T
T F F T T T
T T T F F T
Equivalences
Commutative laws:
P  Q  Q  P
P  Q  Q  P
Asociative laws:
( P  Q )  R  P  ( Q  R )
( P  Q )  R  P  ( Q  R )
Distributive laws:
P  ( Q  R )  ( P  Q )  ( P  R )
P  ( Q  R )  ( P  Q )  ( P  R )
Demorgan’s laws:
  ( P  Q)   P   Q
  ( P  Q)   P   Q
More Equivalences
  ( P )  P (Double negation)
P  P  P
P  P  P
P   P  T
P   P  F
R  ( P   P )  R
R  ( P   P )  R
R  ( P   P )  T
R  ( P   P )  F
 P  Q  ( P  Q)
 ( P  Q )  (P   Q)
 P  Q  ( Q   P )
More Equivalences
• PFP
• PTT
• PFF
• PTP
• P  ( Q  R)  ( P  Q )  R
  ( P  Q )  (P   Q)
• (P  Q )  [( P  Q)  ( Q  P )]
• ( P  Q )  [( P  Q)  ( P   Q )]
• Absorption laws
• P(PQ)P
• P(PQ)P
Ex. Without using truth tables, Show that
P  ( Q  R)  ( P  Q )  R

 Proof:
L.H.S = P  (Q  R)
 P  (Q  R) (Since A  B  ( A  B))
 P  (Q  R)
 (P  Q)  R (By associative property)
 ( P  Q )  R (By demorgan’s law)
 (PQ)R
= R.H.S
Ex. Without using truth tables, Show that
( P  Q )  P is a tautology.
Proof:
Consider, ( P  Q )  P
 ( Q  P )  P ( By commutative law )
 Q  (P  P ) ( By associative property)
 Q  T
 T
 ( P  Q )  P is a tautology.
Ex. Show that the Statement formula
( P  Q )  (PQ)  P is a tautology.
 Proof : Consider,
 {( P  Q )  (PQ)}  P (Associative law)
 {(P  Q )  (PQ)}  P ( Demorgan’s law)
  {P  (Q  Q)}  P (Distributive law)
  {P  T }  P
  {P }  P
  T
  ( P  Q )  (PQ)  P is a tautology
Ex. Show that [{( P  Q )  ( P  Q )}  R ]  R
 Proof: L.H.S = {( P  Q )  ( P  Q )}  R
  {T}R (Since P  Q  ( P  Q))
  R
 = R.H.S

 Ex. Show that {( P  Q )  ( P  Q )} is a Contradiction.

 Proof : Let P  Q = R
 Consider, {( P  Q )  ( P  Q )}
  { R  R }
  F
 { ( P  Q )  ( P  Q )} is a contradiction.
Ex. Show that (P  (Q  R))  ( Q  R )  (P  R)  R
 Proof : Consider,
 {P  (Q  R)}  ( Q  R )  (P  R)
  {(P  Q)  R}  {( Q  R )  (P  R)}, By associative law
  { (P  Q)  R}  {(Q  P )  R} , By distributive law
  {(P  Q)  R}  {(Q  P )  R} , By Demorgan’s law
  {(P  Q)  (Q  P ) } R, By distributive law
  {T } R (Since, A  A  T)
 R
Ex. S.T. ((P  Q)  (P  (Q  R)))  ( P  Q)  (P   R)

is a tautology.
 Consider,
 [(P  Q)  {P  (Q  R)}]  {(P  Q)  (P  R)}
 [(P  Q)  {P  (Q  R)}]  {(P  Q)  (P  R)}
(By De morgan’s laws)
 [(P  Q)  {P  (Q  R)}]  {(P  Q)  (P  R)}
(By De morgan’s laws)
 [(P  Q)  {P  Q) (P  R)}]  {(P  Q)  (P  R)}
(By Distributive law)
  {(P  Q)  (P  R)}  {(P  Q)  (P  R)}
(Since A  A  A)
 T ( Since A  A T)
Implications , Arguments, Inferences
 Premise: It is a proposition on the basis of which we would
able to draw a conclusion . It can be evidence or assumptions.
 Initially we assume something is true and on the basis of
that assumption, we draw some conclusion.
 Conclusion: It is a proposition that is reached from given set
of premises.
 if premise then conclusion
 Inference (Argument): Sequence of statements that ends
with a conclusion or set of 1 or more premises and a
conclusion.
or
 From a set of premises (called Hypotheses) {H1, H2, …., Hn }
a conclusion C follows logically
iff H1  H2  ….  Hn  C.
Implications ,Arguments,Inferences
• The rules of inference are criteria for determining the
validity of an argument.

• Any conclusion which is arrived at by following these rules

is called a valid conclusion, and the argument is called a
valid argument.

• The following statements are equivalent.

• 1. {H1 , H2 , …. , Hn }  C is a logical implication.
• 2. ( H1  H2  ….  Hn) C is a tautology.
• 3. {H1 , H2 ,…. , Hn }  C is a valid argument.
• Ex: “If I love cat then I love dog”
• “I love cat”
• Therefore, “I love dog”
pq
p
• .
q
..
• Or ((pq)^p)q It is a valid argument.
• Ex: “If I love cat then I love dog”
• “I love dog”
• Therefore, “I love cat”
• pq
• q
•
.

.. p
• It is an Invalid argument
Rules of inference:
Fallacies:
 1. The fallacy of affirming the Consequent (or affirming
the converse):
PQ
Q
_________
P Fallacy

Ex: Consider, the following argument

If today is Mahatma Gandhi’s Birth day, then today is October
2nd.
Today is October 2nd.
 Today is Mahatma Gandhi’s Birth day.
The argument is not valid
2. Fallacy of denying the antecedent
( Or Assuming the opposite)
 Consider the following
PQ
P
_________
Q Fallacy
 Ex: Consider the following argument:
H1 : If today is Sunday, then today is Holiday
H2 : Today is not Sunday
C :  Today is not Holiday
The argument is not [Link] is the fallacy of assuming the
opposite.
[Link] non sequitur fallacy
 P,Q
---------
 R is a fallacy.
Ex: Consider the following argument:
1. India’s Capital is New Delhi
2. Milk is White
C:  Sun rises in the East.
The conclusion does not follow from the premises.
Hence, the argument is invalid.
Ex: Show that R follows logically from the premises
PQ, QR, P

 Proof: Consider the premises,

PQ -----(1)
QR -----(2)
P ------(3)
From (1) and (2), By the rule of transitivity,we have
PR --------(4)
From (3) and (4), By the rule of Modus ponens,
R follows.
 R logically follows from the given premises
Ex: Show that P follows logically from the premises
PQ, QR, R
 Proof: Consider the premises,
PQ -----(1)
QR -----(2)
R ------(3)
From (1) and (2), By the rule of transitivity,we have
PR --------(4)
From (3) and (4), By the rule of Modus tollens,
P follows.
 P logically follows from the given premises
Ex: Show that R follows logically from the premises
PQ, QR, PM, M
 Proof: Consider the premises,
PQ -----(1)
Q  R -----(2)
P  M -----(3)
M ------(4)
From (3) and (4), By the rule of Modus tollens, we have
P --------(5)
From (1) and (5), By the rule of Disjunctive Syllogism,we
have
Q --------(4)
From (2) and (4), By the rule of Modus ponens,
R follows.
Ex: Show that (R  S) follows logically from the premises
C  D, (C  D) H, H (A B), (A B)  (R  S )
 Proof: Consider the premises,
(C  D) -----(1)
(C  D)  H -----(2)
H  (A B) -----(3)
(A B)  (R  S ) ------(4)

From (2),(3) and (4), By the rule of Transitivity, we have

(C  D)  (R  S ) --------(5)

From (1) and (5), By the rule of Modus ponens,

(R  S) follows.
Ex: Show that S follows logically from the premises
P  (R S), RP, P
 Proof: Consider the premises,
P  (R S) -----(1)
R  P -----(2)
P -----(3)
From (1) and (3), By the rule of Modus ponens, we have
(R S) ------(4)
From (2), By Contra positive equivalence, we have
PR -------(5)
(3) and (5), By the rule of Modus ponens, we have
R --------(6)
From (4) and (6), By the rule of Modus ponens, S follows.
Ex: Show that W follows logically from the premises
TR, S, T  W, R  S.
 Proof: Consider the premises,
T  R ------(1)
S -----(2)
TW -----(3)
RS -----(4)
From (1), By Contra positive equivalence, we have
RT -------(5)
From, (5) and (3), By the rule of Transitivity, we have
R W --------(6)
From (4) and (2), By the rule of Disjunctive syllogism,we have
R ---------- (7)
 From(6)and (7), By the rule of Modus ponens, W follows
Ex: Show that TP follows logically from the premises
R(ST), R  W, P S, W
 Proof: Consider the premises,
R(ST) ------(1)
R  W -----(2)
P S -----(3)
W -----(4)
From (2) and (4), By the rule of Disjunctive syllogism,we have
R ---------(5)
From(1)and (5), By the rule of Modus ponens, we have
S T ---------(6)
From, (3) and (6), By the rule of Transitivity, we have
P  T ---------(7)
 ( T P ) (By Contra positive equivalence)
Conditional Proof (CP rule)
 Theorem : If {H1, H2, …., Hn } and P imply Q , then
{H1, H2, …., Hn } imply (PQ)

 Proof : From our assumption we have,

(H1 H2  ….  Hn  P)  Q
This assumption means (H1 H2  ….  Hn  P)  Q is a tautology.
Using the equivalence P (Q R)  (P  Q)  R
We can say that (H1 H2  ….  Hn)  ( PQ ) is a tautology.
Hence the theorem.
 Rule CP : If we can derive Q from P and a set of premises,
then we can derive PQ from the set of premises alone
Ex:Show that RS can be derived from the premises
p (Q S), RP, Q

 Solution: Instead of deriving RS, we shall include R as an

additional premise and show S first.
p (Q S) …..(1)
RP …..(2)
Q ……(3)
R …….(4)
From (2) and (4), By the rule of Disjunctive syllogism,we have
P ---------(5)
From(1)and (5), By the rule of Modus ponens, we have
Q S ………….(6)
From(3)and (6), By the rule of Modus ponens, S follows
 By CP rule, RS follows from the given premises.
Consistency, Inconsistency and Proof by Contradiction
 A set of formulas {H1, H2, …., Hn} is said to be consistent, if
their conjunction has truth value T for some assignment of
the truth values to the atomic variables appearing in H 1, H2,
…., Hn .
 A set of formulas {H1, H2, …., Hn} is said to be inconsistent,
if their conjunction implies a contradiction. that is
(H1 H2  ….  Hn )  (R  R) where R is any formula.
 Proof by Contradiction :
In order to show that,a conclusion C logically follows from
the premises H1, H2, …., Hn ,We assume that C is false and
Consider C as additional premise.
If the new set of premises is inconsistent, then our
assumption is wrong. Hence C follows.
Ex: Show that the following set of premises are inconsistent.
P Q, P R, Q  R, P
 Proof: Consider the premises,
PQ ------(1)
PR -----(2)
Q R -----(3)
P ----(4)
From (1) and (3), By the rule of transitivity, we have
P R …….(5)
From(2)and (4), By the rule of Modus ponens, R follows
From(4)and (5), By the rule of Modus ponens, R follows
But, R and R cannot be simultaneously true
(Contradiction). Hence, the given premises are
inconsistent.
Ex: Show that the following set of premises are inconsistent.
R  M, R  S, M, S
 Proof: Consider the premises,
RM ------(1)
R  S ----(2)
M -----(3)
S ----------(4)
From (1) and (3), By the rule of Disjunctive Syllogism,we have
R ……….(5)
From(2)and (4), By the rule of Disjunctive Syllogism, We have
R ………..(6)
But, R and R cannot be simultaneously true (Contradiction).
Hence, the given premises are inconsistent.
Ex: Show that (PQ) follows from (P  Q)
 Solution: Let us introduce (PQ) as an additional premise
and show that this leads to contradiction.
(PQ) ….(1)
Which is equivalent to
(PQ) ….(2)
From (2), P follows
Given that, (P  Q) …..(3)
From (3), P follows
But, P and P cannot be simultaneously true (Contradiction).
 Our assumption is false.
Hence (PQ) follows from (P  Q)
Ex: Show that P follows from the premises PQ, (P  Q)
 Solution: Let us introduce P as an additional premise and
show that this leads to contradiction.
P ….(1)
PQ …..(2)
(PQ) ….(3)
From (1) and (2), By the rule of Moden ponens, we have
Q …….(4)
From (1) and (4), We have
( PQ) …….(5)
But, (3) and (5) cannot be simultaneously true
(Contradiction).
 Our assumption is false.
Hence, P follows from the premises PQ, (P  Q)
Ex: Verify that the following argument is valid by using the rules of inference
(Here, H1 , H2 , …. are premises and C is conclusion) :
H1 : If Joe is a Mathematician, then he is ambitious.
H2 : If Joe is an early riser, then he does not like oat meal.
H3 : If Joe is ambitious, then he is an early riser
C : Hence, if Joe is a Mathematician, then he does not like
oat meal.
 Solution: Let us make the following representations
p : Joe is a Mathematician.
q : Joe is ambitious
r : Joe is an early riser
s : Joe likes oat meal
The symbolic form of the given argument is
Contd.,
H1 : pq ….(1)
H2 : rs ….(2)
H3 : qr …..(3)
From (1) and (3), By the rule of transitivity, we have
pr ……(4)
From (4) and (2), By the rule of transitivity, we have
p  s ……(5)
i.e., if Joe is a Mathematician, then he does not like oat meal.
 The conclusion logically follows from the premises.
Hence, the argument is valid
Ex: Verify that the following argument is valid by using the rules of inference
(Here, H1 , H2 , …. are premises and C is conclusion) :
H1 : If Cliffton does not live in France, then he does not
speak French.
H2 : Cliffton does not drive a Datsun.
H3 : If Cliffton lives in France, then he rides a Bicycle.
H4 : Either Cliffton speaks French,or he drives a Datsun.
C : Hence, Cliffton drives a bicycle.
 Solution: Let us make the following representations
p : Cliffton lives in France.
q : Cliffton speaks French.
r : Cliffton drives a Datsun.
s : Cliffton drives a Bicycle.
The symbolic form of the given argument is
Contd.,
 H1 : p q …..(1)
H2 : r …..(2)
H3 : p  s …..(3)
H4 : q  r …….(4)
From (2) and (4), By the rule of Disjunctive Syllogism,we
have
q ……..(5)
(1)  q  p …….(6)
From (5) and (6), By the rule of Modus ponens, we have
P ……(7)
From (3) and (7), By the rule of Modus ponens, s follows
 The conclusion logically follows from the premises.
Hence, the argument is valid
Ex:Using Symbolic logic, Show that the following premises are
inconsistent
1. If Jack misses many classes through illness,then he fails
high school.
2. If Jack fails high school, then he is uneducated.
3. If Jack reads a lot of books, then he is not uneducated.
4. Jack misses many classes through illness and reads a lot of
books.
 Solution: Let us make the following representations
p : Jack misses many classes through illness
q : Jack fails high school
r : Jack is uneducated
s : Jack reads a lot of books
Now, the given premises can be represented as
Contd.,
p  q …..(1) q  r …..(2)
s  r …..(3) ps …..(4)
From (1) and (2), By transitivity, p r …..(5)
From(3), By Contra positive equivalence, r  s ….. (6)
From (5) and (6), By transitivity, we have
p s …..(7)
From(4), we have
p …..(8)
From (7) and (8), By the rule of modus ponens, s follows
From (4), s follows
But, s and s cannot be simultaneously true (Contradiction).
Hence, the given premises are inconsistent
Ex:Using Symbolic logic,prove the following argument

If A works hard, then either B or C will enjoy themselves.

If B enjoys himself, then A will not work hard.
If D enjoys himself, then C will not enjoy himself.
Therefore, If A works hard, then D will not enjoy himself .
 Solution: Let us use the following representations.
A : A works hard.
B : B will enjoy himself.
C : C will enjoy himself.
D : D will enjoy himself.
Now, we have to show that, A  D follows from
A (B  C) , B  A and D  C
Contd.,
A (B  C) ….(1) B  A ….(2)
D  C ….(3) A …. (4) ( Additional
premise)
From, (1) and (4), By modus ponens, We have
(B  C) ……(5)
(2)  A  B …. (6)
From, (4) and (6), By modus ponens, B ….(7) follows.
From (5) and (7), By the rule of Disjunctive Syllogism, we
have
C ….(8)
(3)  C D …. (9)
From (8) and (9), By modus ponens, D follows
Hence, By CP rule, A  D follows
Properties of operations on implication
(P  Q)  ((~P)  Q)
(P  Q)  (~Q  ~P)
(P  Q)  ((P  Q)  (Q  P))
~(P  Q)  (P  ~Q)
~(P  Q)  ((P  ~Q)  (Q  ~P))
P Q  (P  Q)  (~P  ~Q)
Normal forms
 Elementary product:A product of the variables and their
negations in a formula is called an Elementary product.
Ex: P, PQ, PQ, PQ R
 Elementary Sum: A Sum of the variables and their
negations in a formula is called an Elementary Sum.
Ex: P, P  Q, P  Q, P Q R
 Disjunctive normal form: A formula which is equivalent to a
given formula and which consists of a sum of elementary
products is called a disjunctive normal form.
 Ex: (P )  ( PQ )  (PQ).
 Ex: ( PQ )  (PQ)  (PQ R ).
Normal forms (contd.,)
 Conjunctive normal form: A formula which is equivalent to
a given formula and which consists of a product of
elementary sums is called a conjunctive normal form.
Ex: (P )  ( P  Q ) (P  Q).
Ex: ( P  Q )  (P  Q) (P  Q  R ).
Disjunctive Normal Forms
A formula equivalent to a given formula and consists of a
sum of elementary products of the given formula.

Examples
1. Obtain Disjunctive Normal Form of P  (P  Q).
P  (P  Q)  P  (~P  Q)
 (P  ~P)  (P  Q)
[Link] Disjunctive Normal Form of ~(P  Q)  (P  Q).
~(P  Q)  (P  Q)
 (~(P  Q)  (P  Q))  ((P  Q)  ~(P  Q))
since [R  S  (R  S)  (~R  ~S)]
~(P  Q)  (P  Q)
 (~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  Q)  (P  ~P)  (Q  ~P)

 (P  ~Q)  (Q  ~Q)
Conjunctive Normal Forms
A formula equivalent to a given formula and consists of a
product of elementary sums of the given formula.

Examples
1. Obtain Conjunctive Normal Form of P  (P  Q).
P  (P  Q)  P  (~P  Q)
[Link] Conjunctive Normal Form of ~(P  Q)  (P
 Q).
~(P  Q)  (P  Q)
 (~(P  Q)  (P  Q))  ((P  Q)  ~(P  Q))
since [R  S  (R  S)  (S  R)]

~(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)
[Link] Conjunctive Normal Form of Q  (P  ~Q)  (~P
 ~Q).
Q  (P  ~Q)  (~P  ~Q)
 Q  ((P  ~P)  ~Q)

 (Q  (P  ~P))  (Q  ~Q)

 (Q  P  ~P)  (Q  ~Q)
1. DNF of P {(P Q) ~(~Q  ~ P))
2. DNF,CNF of ~{P(QR)}
3. DNF of (~P  ~ Q) (P  ~ Q)
4. CNF of (P (Q R))(~P  (~Q  ~ R))
5. DNF (~P  ~ Q) (P  ~ Q)
Principal Disjunctive Normal Forms
 Let P and Q be two statement variables.
 Let us construct all possible formulas which consists of
conjunctions of P or its negation and conjunctions of Q or its
negation.
 None of the formulas should contain both a variable and its
negation.
Ex: either P  Q or Q  P is included but not both.
 For two variables P and Q , there are 22 such formulas given by

P  Q, P  ~ Q , ~ P  Q and ~ P  ~ Q
 these formulas are called minterms.
 From the truth tables of these minterms, it is clear that no two
minterms are equivalent
 Each minterm has the truth value T for exactly one
combination of the truth values of the variables P and Q.
 For a given formula , an equivalent formula consisting of
disjunction of minterms only is known as its principal
disjunctive normal form.
 Also called sum-of –products canonical form.
 Min terms: Let P and Q are two statement variables. Let us
construct all possible formulas which consist of conjunctions
of P or its negation and conjunctions of Q or its negation.
For two variables P and Q, there are 2 2 such formulas given
by
PQ, PQ, PQ, PQ
These formulas are called ‘min terms’.
 For three variables P,Q and R, there are 23 such formulas
given by
PQ R, PQ R, PQ R, PQ R,
PQ R, PQ R, PQ R, PQ R
These min terms are denoted by m0, m1 , …, m7
respectively.

 In general, there are 2n min terms for n variables.

Ex. Obtain the Principal Disjunctive normal forms of the following
PQ , P  Q, (PQ)

 Solution:
P Q PQ PQ PQ (PQ
)
F F T F F T
F T T T F T
T F F T F T
T T T T T F
 PQ  (PQ)  (PQ)  (PQ)
 P  Q  (PQ)  (PQ)  (PQ)
 (PQ)  (PQ)  (PQ)  (PQ)
Ex. Obtain the Principal Disjunctive normal form of the following
P  {(PQ)  (P  Q)}

 Given formula is, [ P  {(PQ)  (P  Q)} ] = A (say)

The truth table for A is given below.

P Q PQ P  Q {(PQ)  A
(P 
Q)}
F F T F F T
F T T F F T
T F F F F F
T T T T T T
 A  (PQ)  (PQ)  (PQ)
 Which is the PDNF for A .
Ex. Obtain the Principal Disjunctive normal form of the following
(P  Q)  (Q  R)  (P  R )

 Solution: Consider, (P  Q)  (Q  R)  (P  R )

  {(P  Q)  (R  R)} 
{(P  P)  (Q  R) } 
{(P  R )  (Q  Q)}

(PQ R)  (PQ R)  (PQ R) (PQ R)

Which is the PDNF for the given formula.

Ex. Obtain the Principal Disjunctive normal form of the following
(P  Q)  (P  R )
= A (say)

P Q R P  Q P (P  R) A
F F F T T F F
F F T T T T T
F T F F T F F
F T T F T T F
T F F F F T F
T F T F F T F
T T F T F T T
T T T T F T T
 A  (PQ R)  (PQ R)  (PQ R) =  (m1, m6, m7)
Principal Conjunctive normal forms (Product of
Sums canonical forms)
 Max terms: For a given number of variables, the max term
consists of disjunctions in which each variable or its
negation, but not both, appears only once.
For two variables P and Q, there are 22 such formulas
given by
(P  Q), (P  Q), (P  Q), (P  Q).
These formulas are called ‘max terms’.
 For three variables P,Q and R, there are 23 such formulas
given by
PQR, P  Q  R, P  Q  R, P  Q  R,
P  Q  R, P  Q  R, P  Q  R, P  Q  R
These max terms are denoted by M0, M1 , …, M7
respectively.
 In general, there are 2n Max terms for n variables.
PCNF (Contd.,)
 Mi =  mi
 M0 =  m0
= (PQ R) = (P  Q  R)
 M1 =  m1
= (PQ R) = (P  Q   R)
 M2 =  m2
= (PQ R) = (P   Q  R)
 Principal Conjunctive normal form (Product of Sums
canonical form) : For a given formula, an
equivalent formula consisting of conjunctions of max
terms only is known as Principal Conjunctive normal
form.
Principal Conjunctive Normal Forms
 Let us construct all possible formulas which consists of
conjunctions of P or its negation and conjunctions of Q or
its negation.
 None of the formulas should contain both a variable and its
negation.
Ex: either P  Q or Q  P is included but not both.
 For two variables P and Q , there are 22 such formulas
given by
P  Q, P  ~ Q , ~ P  Q and ~ P  ~ Q
 these formulas are called maxterms.
 For a given formula , an equivalent formula consisting of
conjunctions of maxterms only is known as its principal
conjunctive normal form.
 Also called products-of-sums canonical form.
Ex. Obtain the Principal Conjunctive normal forms of the following
PQ , P  Q, (PQ)

P Q PQ PQ PQ (PQ)

F F T F T F
F T T F F T
T F F F F T
T T T T T F

 The PCNF’s are

 PQ  (P  Q)
 P  Q  (P  Q)  (P  Q)  (P  Q)
 (PQ)  (P  Q)  (P  Q)
EX. Obtain the Principal Conjunctive normal form of the formula given by (P
 R)  (Q  P)
 Solution: (P  R)  (Q  P)
 (P  R)  {(PQ)  (QP)}
 (P  R)  (P  Q)  (Q  P)
 { (P  R)  (Q  Q) } 
{ (P  Q)  (R  R) } 
{ (Q  P)  (R  R) }
 (P  Q  R)  (P  Q  R)  (P  Q  R) 
( P  Q  R)  (P  Q  R)
= (0,2,3,4,5)
Which is the required PCNF.
Max terms and Min terms
*
P Q R Min terms mi Max terms Mi

F F F m0 : PQ R M0 : P  Q  R
F F T m1 : PQ R M1 : P  Q  R
F T F m2 : PQ R M2 : P  Q  R
F T T m3 : PQ R M3 : P  Q  R
T F F
m4 : PQ R M4 : P  Q  R
T F T
m5 : PQ R M5 : P  Q  R
T T F
T T T m6 : PQ R M6 : P  Q  R
m7 : PQ R M7 : P  Q  R
Ex. Obtain the Principal Conjunctive normal form and Principal disjunctive
normal form of A, where A = (P  Q) (P  R )
P Q R PQ P P  R A
F F F F T F F
F F T F T T T
F T F F T F F
F T T F T T T
T F F F F F F
T F T F F F F
T T F T F F T
T T T T F F T
The PCNF of A = (0,2,4,5)
A  (P  Q  R)  (P  Q  R)  (P  Q  R) (P  Q  R)
Contd.,
The PDNF of A = (1,3,6,7)
A  (PQ R)  (PQ R)  (PQ R)  (PQ R)