Unit IV-LOGIC

Introduction
Logic is the discipline that deals with the methods of reasoning. It provides rules
and techniques for determining whether a given argument is valid or not. Logical
reasoning is used in mathematics to prove theorems, in computer science to
verify the correctness of programs and to prove theorems in physical sciences to
draw conclusions from experiments.

A systematic study of arguments by making extensive use of symbols is

known as symbolic logic.

Definition
Declarative Sentence or Non-Declarative Sentence
proposition
Declarative sentence makes a Statement that does not declares
statement that declares something or something or gives idea are called non-
gives reliable information or idea declarative sentence
Eg: Eg:
(i) Chennai is the capital of Tamilnadu (i) Imperative sentence:
(ii) 1+5 =6 Command/Request
(iii) the sun rises in the west (ii) Exclamatory sentence:
Express strong feeling
(iii)Interrogative sentence:
Question sentences

p: Today it is raining, q: I can't go to school r: my maths

teacher will scold me

Proposition[statement]
A proposition is a declarative sentence or a statement that is either true
or false but not both simultaneously.

Truth Values[true or false]

The truth or falsity of a proposition is called truth value.

 If a proposition is true, then its truth value is T

 If a proposition is false, then its truth value is F

They are also denoted by the symbols 1 and 0. Lower case letters such as
p,q,r,…. are used to denote propositions.

Examples: Determine the truth values of the following

1.The integer 5 is a prime number.-Truth value is T
2.The integer 25 is a prime number. -F
3.Addition of 2 and 4 gives 5 as their sum-F
4.There are exactly 5 odd integers between 1 and 30- F
5.The earth is round-F
6.Today is Monday-T

The statements 1 and 5 have the truth value ‘true’, while the statements 2,3,4
have a truth value ‘false’. The truth value of statement 6 depends upon the day
in which the statement is made and hence is neither true nor false.
 7. The sum of an odd and even integer is odd-T
8.The triple(3,4,5) is an integral solution of x2+y2=z2- T
9.For any real number x, x2<0 -F

Propositional Logic/Calculus:
The area of logic that deals with propositions is called proposition logic or
proposition calculus.

Logical Operators:
Logical operators are words or symbols used to combine two or more propositions
to form a new proposition.

Connectives:
Negation
If p is a statement, then its negation is ∼ p or  p , read as “not p”.
p: It is raining
 p: it is not raining

p: Bengalore is the capital of TN

 p: Bengalore is not the capital of TN

Truth table for negation

p p
T F
F T
Conjunction or AND (  )
Let p and q be two propositions. The proposition p  q is called the
conjunction of p and q. The statement p  q has a truth value T when both
p and q have the truth value T and is assigned truth value F otherwise.
Truth value for Conjunction

p q pq
T T T
T F F
F T F
F F F

Disjunction (or) OR (  )
If p and q are two statements, then the statement p  q is read as “p or q”
and is called a disjunction. The statement p  q has the truth value F only
when both p and q have the truth value F ; otherwise T .
Truth value for Disjunction

p q p  q
T T T
T F T
F T T
F F F
Conditional statement (p  q)[If ---then]
If p and q are any two statements, then the statement p  q which is
read as “if p then q” is called a conditional statement. The statement p 
q has a truth value F when p has a truth value T and q has a truth value
F ; otherwise it is T .

p q p q
T T T
T F F
F T T
F F T
Bi-conditional statement (p  q)
If p and q are any two statements, then the statement p  q which is read as “p iff
q” is called bi-conditional statement. The statement p  q has the truth value T
when both p and q have identical truth values; otherwise it has a truth value F .

p q p q
T T T
T F F
F T F
F F T
Example : Find the truth value of:

a) “ 2> 3 or 3 is a positive integer”.

Ans: Let p : 2 > 3, q : 3 is a positive integer.

The given proposition is p  q .

truth value of the statement p is false, and the truth value of the statement q is true ,

hence p  q is true.

Tautology and contradiction

A logical expression E in a certain number of logical variables is
said to be a Tautology if the truth value of E is true for all combinations of
values of the variables.
A logical expression E in a certain number of logical variables is said to
be a contradiction if the truth value of E is false for all combinations of
values of the variables involved in the expression.
Truth Table

P P P ∨P P ∧P
T F T F
F T T F

P ∨  P is a tautology, P ∧  P is a contradiction.
Worked Examples:
1.Construct the truth table for  P ∨ Q
Sol:

P Q P P ∨ Q
T T F T
T F F F
F T T T
F F T T

2.Find the truth value of (P ∨ Q) ∧ (Q ∨ R)

Sol:
P Q R P ∨Q Q∨R (P ∨ Q) ∧ (Q ∨ R)
T T T T T T
T T F T T T
T F T T T T
T F F T F F
F T T T T T
F T F T T T
F F T F T F
F F F F F F

3.Construct the truth table for (P → Q) ∨ (Q → P )

Sol:
P Q P →Q Q→P (P → Q) ∨ (Q → P )
T T T T T
T F F T T
F T T F T
F F T T T

Therefore the truth table yields Tautology

4.Write the following statement in symbolic form.

If (either Jerry takes calculus or Ken takes sociology), then Larry will take
English
Sol:
p:Jerry takes Calculus
q:Ken takes Sociology
r:Larry takes English

either Jerry takes calculus or Ken takes sociology : p ∨ q

Symbolically (p ∨ q) →r

5.Construct the truth table for  (P ∧ Q) ⇔ (  P ∨  Q)

Sol:
P Q P Q P∧Q  (P∧Q)  P∨  Q  (P∧Q) ⇔  P∨ → Q
T T F F T F F T
T F F T F T T T
F T T F F T T T
F F T T F T T T
6.Construct the truth table for  (P ∨ (Q ∧ R)) ⇔ ((P ∨ Q) ∧ (P ∨ R))
Sol: LHS RHS
 (P∨ (P∨Q) ∧  (P∨(Q∧R) ⇔
P Q R Q∧R P∨( Q∧R) (Q∧R)) P∨Q P∨R (P∨R) ((P∨Q) ∧ (P∨R)
T T T T T F T T T F
T T F F T F T T T F
T F T F T F T T T F
T F F F T F T T T F
F T T T T F T T T F
F T F F F T T F F F
F F T F F T F T F F
F F F F F T F F F F
7.Show that the statement Q ∨ (P ∧  Q) ∨ (  P ∧  Q) is a Tautology.
Sol:

Q∨ (P∧   P∧ 
P Q P  Q P∧  Q Q) Q Q∨(P∧  Q) ∨(  P∧  Q)
T T F F F T F T
T F F T T T F T
F T T F F T F T
F F T T F F T T
Hence the given statement is a tautology.

8.Indicate which ones are tautologies or contradictions.

a) ((P → (  P )) →  P )
b) (P → (P ∨ Q))
c) ((  Q ∧ P ) ∧ Q)
Sol:
a)
P 
P P P (P   P)   P
T F F T
F T T T
Hence it is a tautology.

b)

P Q PQ P  (P  Q)
T T T T
T F T T
F T T T
F F F T
Hence it is a tautology.

c)

P Q Q Q  P (  Q  P)  Q
T T F F F
T F T T F
F T F F F
F F T F F
Hence it is a contradiction.

9.Determine whether the given compound proposition is a tautology or a

contradiction.((p ∨ q) ∧ (p  r) ∧ (q  r) )  r
p q r p∨q p r ab q r  c abc (a  b  c)  r
a b

T T T T T T T T T
T T F T F F F F T
T F T T T T T T T
T F F T F F T F T
F T T T T T T T T
F T F T T T F F T
F F T F T F T F T
F F F F T F T F T
Since all the entries in the last column are T’s, the given statement is tautology.

Practice Problems
1.Using the statements: R: Mark is rich, H: Mark is happy.
Write the following statements in a symbolic form:
(a) Mark is poor but happy.
(b) Mark is rich or unhappy.
(c) Mark is neither rich nor happy.
(d) Mark is poor or he is both rich and unhappy.
2. Examine if the given proposition is a tautology or a contradiction.
(P → (Q → P ))
3. Construct a truth table for each of the following compound propositions:
(a) (p ∨ q) → p  q
(b) (p → q) → (q → p)
(c) (q →  p) ↔ (p ↔ q)

Equivalence Formulas:
Two compound propositions A(p1, p 2 ,... pn) and B(p1, p 2 ,... pn)are
equivalent if they have identical truth table values and is denoted as
A ⇔ B.
Note:
1.p ⇔ q (i.e., p is equivalent to q) iff p ↔ q is a tautology
2.  ( p ∨ q)   p   q
Implication
Let p,q be Boolean expressions. Then, p  q (i.e., p implies q) iff p  q is a tautology.
Note:
⇒ is the implication symbol.
⇔ or  is the equivalence symbol.
Problems:
1.Prove that p → q ⇔  q →  p [lhs BICONDITIONAL rhs is a tautology]
Sol: It’s enough if we prove (p → q) ↔ (  q →  p) is a tautology.
q → 
p q p  q (LHS)p → q (RHS) (p → q) ↔ (  q →  p)
p
T T F F T T T
T F F T F F T
F T T F T T T
F F T T T T T

2.Prove that (p → q) ∧ p ⇒ q
Sol: Its enough if we prove (p → q) ∧ p → q is a tautology.

p q p→q (p → q)  p (p → q)  p → q
T T T T T
T F F F T
F T T F T
F F T F T
3.Prove that (p → q) ∧  q ⇒  p.
Sol:Its enough if we prove (p → q) ∧  q →  p is a tautology.

p q p q p→q (p → q)   q (p → q)   q →  p)
T T F F T F T
T F F T F F T
F T T F T F T
F F T T T T T
4.Prove (P ∨  P ) ⇔ (Q ∨  Q) [  equivalent]
Sol:Its enough if we prove (P ∨  P ) ↔ (Q ∨ YQ) is a tautology.
P Q P Q P∨  P Q∨  Q (P∨  P) ↔ ( Q∨  Q)
T T F F T T T
T F F T T T T
F T T F T T T
F F T T T T T

Practice Problems:
Show that the following statements are true:
1.  (P  Q) ⇔  P∨  Q
2.  (P∨Q) ⇔  P   Q
3.  (P→Q) ⇔P ∧  Q
4.  (P↔Q) ⇔(P∧  Q)∨(  P ∧ Q)
[LHS  (P↔Q) and RHS (P∧  Q)∨(  P ∧ Q) ]
5. (p → (q→s)) ∧ ( r ∨ p) ∧q ⇒ r→s
 p q r s

T T T T
T T T F
T T F T
T T F F
T F T T
T F T F
T F F T
T F F F
F T T T
F 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

Algebra of Propositions:
Basic Logical Laws

S.No. Laws Name of the

Law
1 p ∨ p ⇔p Idempotent
p ∧ p⇔p
2 (p ∨ q) ∨ r ⇔ p ∨ (q ∨ r) Associative
(p ∧ q) ∧ r ⇔ p ∧ (q ∧ r)
3 p ∨q ⇔q∨p Commutative
p ∧q ⇔q∧p
4 p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r) Distributive
p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)
5 p ∨ F ⇔ p ; p ∧ T⇔ p Identity
6 p ∨T⇔T : p ∧F⇔F Null/Dominant
7 p ∨  p ⇔ T; p ∧  p ⇔ F Complement
8 p ∨ (p ∧ q) ⇔ p Adsorption
p ∧ (p ∨ q) ⇔ p
9  (p ∨ q) ⇔  p ∧  q De Morgan’s
 (p ∧ q) ⇔  p ∨  q
10  (  p )⇔p Involution

Equivalences Involving Conditionals and Bi-Conditionals

S.No. Laws
1 p → q ≡  p ∨ q conditional
equivalence
2 p → q ≡  q→  p (contrapositive)
3 p ∨ q ≡ p → q
4 p ∧ q ≡  (p→  q)
5  (p → q) ≡ p ∧  q
6 (p → q)∧( p → r) ≡ p→(q ∧ r)
7 (p → r)∧( q → r) ≡ (p ∨ q)→ r
8 (p → q) ∨ ( p → r) ≡ p→(q ∨ r)
 9 (p → r) ∨ ( q → r) ≡ (p ∧ q)→ r
10 p↔ q ≡ (p → q)∧( q→p)
11 p↔ q ≡  p ↔  q
12 p↔ q ≡ (p ∧ q) ∨ (  p ∧  q)
13  (p↔ q) ≡ p↔  q
p ∨ q ≡ p → q
p ∧ q ≡  (p→  q)
 (p → q) ≡ p ∧  q
p↔ q ≡  p ↔  q

1) p ∨ q ≡ p →  q
2) p ∧ q ≡  (p→  q)
3)  (p → q) ≡ p ∧ q
4)p↔ q ≡  p ↔  q

Example. The contrapositive of a statement is “If I don’t catch the train, then I am not
early”. Write the original statement .

Given: q  p ≡ p  q

Given q : I don’t catch the train and p : I am not early

Hence, p : I am early, q : I catch the train

The original statement is p  q , ie., If I am early, I catch the train. p  q

Problems:
1.Show that P→(Q→R) ⇔P→(  Q ∨ R) ⇔(P ∧ Q) →R without using truth
table.
Sol:

LHS

P → (Q → R)⇔ P → (  Q ∨ R)Conditional equivalence p → q ≡  p ∨ q

⇔  P ∨ (  Q ∨ R) Conditional equivalence
⇔ (  P ∨  Q) ∨ R Associative
⇔  (P ∧ Q) ∨ R De Morgan’s Law  (p ∧ q) ⇔  p ∨  q

⇔ (P ∧ Q) → R Conditional equivalence
2. Show that the following equivalences are true:

(i) P → (Q → P ) ⇔  P → (P → Q)
(ii) P → (Q ∨ R) ⇔ (P → Q) ∨ (P → R).
Sol:
(i) P → (Q → P ) ⇔ P → (  Q ∨ P )Conditional equivalence p → q
≡ p ∨q
⇔  P ∨ (  Q ∨ P ) Conditional equivalence
⇔  P ∨ (P ∨  Q) Commutative (p ∨q≡ q ∨p)
⇔ (P ∨P) ∨ Q Associative
⇔ T ∨ Q ⇔ T Dominant Law
Also
 P → (P → Q) ⇔  P → (  P ∨ Q) Conditional equivalence
⇔   P ∨ (  P ∨ Q) Conditional equivalence
⇔ P ∨ (  P ∨ Q) Involution
⇔ (P ∨  P ) ∨ Q Associative
⇔ T ∨Q Dominant Law
⇔ T Dominant Law

(ii) P → (Q ∨ R) ⇔ (  P ∨ (Q ∨ R)) Conditional equivalence

⇔ (  P ∨ Q) ∨ (  P ∨ R) Associative
⇔ (P → Q) ∨ (P → R) Conditional equivalence
Hence proved.
3.Without using truth tables, prove that
((p ∨ q) ∧  (  p ∧ (  q ∨  r))) ∨ (  p ∧  q) ∨ (  p ∧  r) is a tautology
Sol: ((p ∨ q) ∧  (  p ∧ (  q ∨  r))) ∨ (  p ∧  q) ∨ (  p ∧  r)
≡ ((p ∨ q) ∧  (  p∧  (q ∧ r)) ∨  (p ∨ q) ∨  (p ∨ r)(De Morgans law)
≡ ((p ∨ q) ∧ (p ∨ (q ∧ r))) ∨ (  (p ∨ q) ∨  (p ∨ r)) (De Morgans law)
≡ ((p ∨ q) ∧ [(p ∨ q) ∧ (p ∨ r)]) ∨  ((p ∨ q) ∧ (p ∨ r)) (Distributive law) (DeMorgans)
≡ [(p ∨ q) ∧ (p ∨ r)] ∨  [(p ∨ q) ∧ (p ∨ r)](Idempotent and De Morgan’s law)
≡ T (p ∨  p =T)
Hence the given statement is a tautology.

Normal Forms
Disjunctive(OR) and conjunctive(AND) normal forms
A product of the variables and their negations is called an elementary product
(AND). A sum of the variables and their negations is called an elementary sum
(OR).

A compound proposition which consists of a sum of elementary products (inside

the brackets AND, outside the brackets OR)and which is equivalent to a given
proposition is called a disjunctive normal form (DNF) of the given proposition.

A formula which consists of a product of elementary sums and which is equivalent

to a given formula is called a conjunctive normal form (CNF) of the given formula

Procedure to Obtain the DNF (AND) or CNF (OR)

1. If the connectives → and ↔ are present in the given formula, they are
replaced by ∧, ∨ and  [conditional equivalence formula]
2. If the negation is present before the given formula or a part of the
given formula, De Morgan’s Laws are applied so that the negation is brought before
the variables only.
* If necessary, the distributive and idempotent laws are applied.

Principal Disjunctive Normal form (PDNF)

and Principal Conjunctive Normal form (PCNF)
• Given a number of variables, the products (AND) in which each variable or its
negation, but not both, occurs only once are called minterms.
• Given a number of variables, the sums (OR)in which each variable or its
negation, but not both, occurs only once is called the maxterms.
• A formula consisting of disjunction of minterms (inside AND outside OR)in the
variables only and equivalent to a given formula is known as its principal
 disjunctive normal form (PDNF) (sum of products) (inside AND outside OR.)
• A formula consisting of conjunction of maxterms in the variables only and
equivalent to a given formula is known as its principal conjunctive normal
forms (PCNF) (product of sums) (inside OR outside AND)
Note:
PDNF: Sum of the minterm – whose truth value is ‘T’
PCNF :(product of the maxterm)’ – whose truth value is ‘F’

Problems:
1. Obtain the PDNF and PCNF of p ∧ (p → q)
Sol:
Minterm
p q p→q (p → q)  p (for PDNF)
T T T T p q
T F F F
F T T F
F F T F
Hence the PDNF is S: p ∧ q.
To find PCNF

Let  S = S  ( p  q )  ( p  q )  ( p   q ) [missed min terms]

(S )  S  [(p  q)  ( p  q)  (p  q)]

 (p  q)  ( p  q)  (p  q)
PCNF  ( p  q)  (p  q)  ( p  q)

2. Obtain the PDNF and PCNF of (p ∧ q) ∨ (  p ∧ r) ∨ (q ∧ r)

Sol:
Minterm
p q r p pq p r q r (p  q)∨(  p  r) ∨(q  r) (For
PDNF)
T T T F T F T T p ∧q ∧r
T T F F T F F T p∧q ∧ r
T F T F F F F F
T F F F F F F F
F T T T F T T T  p ∧q ∧r
F T F T F F F F
F F T T F T F T p∧ q∧r
F F F T F F F F

PDNF = sum of the minterms

S = (p ∧ q ∧ r) ∨ (p ∧ q ∧  r) ∨ (  p ∧ q ∧ r) ∨ (  p ∧  q ∧ r)
To find PCNF = product of max terms
S  ((p  q  r)  (p  q  r)  (p  q  r)  (p  q  r) )
Let (S )  S  (p  q  r )  (p  q  r )  ( p  q  r )  ( p  q  r )
PCNF : (p  q  r )  (p  q  r )  ( p  q  r )  ( p  q  r )
 3. Obtain the PDNF of (  p → r) ∧ (q ↔ p)
Sol:
p (  p→r) 
p q r  p→r q ↔p Minterm
(q↔p)
T T T F T T T
T T F F T T T
T F T F T F F p ∧ q ∧ r
F T T T T F F p∧q ∧r
T F F F T F F p∧ q∧ r
F T F T F F F p∧q ∧ r
F F T T T T T
F F F T F T F p ∧ q ∧ r

PCNF = (sum of the minterm)’

=[(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)

4. Obtain the principal disjunctive and conjunctive normal forms:

(p → (q ∧ r))∧(  p→(  q ∧  r))

Sol:
p→ q∧ p → (p→(q ∧ r))∧ Max
(q∧r) r (  q∧  r) (  p→(  q∧ Minterm
p terms
p q r q r q∧r  r)) for
for
PDNF
PCNF
T T T F F F T T F T T p∧q ∧r
T T F F F T F F F T F p∨q∨
r
T F T F T F F F F T F p ∨ q ∨
r
F T T T F F T T F F F
T F F F T T F F T T F
F T F T F T F T F F F
F F T T T F F T F F F
F F F T T T F T T T T p ∧ q
∧ r

PDNF = sum of the minterm

= (p ∧ q ∧ r) ∨ (  p ∧  q ∧  r)
PCNF = (product of the max terms) =( sum of the minterm)’
= [(  p ∨  q ∨ r) ∧ (  p ∨ q ∨  r) ∧ (p ∨  q ∨  r) ∧ (  p ∨ q ∨ r)
∧ (p ∨  q ∨ r) ∧ (p ∨ q ∨  r)]

S.No. Laws
1 p → q ≡  p ∨ q conditional
equivalence
2 p → q ≡  q→  p (contrapositive)
3 p ∨ q ≡ p → q
4 p ∧ q ≡  (p→  q)
5  (p → q) ≡ p ∧  q
 6 (p → q)∧( p → r) ≡ p→(q ∧ r)
7 (p → r)∧( q → r) ≡ (p ∨ q)→ r
8 (p → q) ∨ ( p → r) ≡ p→(q ∨ r)
9 (p → r) ∨ ( q → r) ≡ (p ∧ q)→ r
10 p↔ q ≡ (p → q)∧( q→p)
11 p↔ q ≡  p ↔  q
12 p↔ q ≡ (p ∧ q) ∨ (  p ∧  q)
13  (p↔ q) ≡ p↔  q
Procedure to Obtain the DNF (AND) or CNF (OR)
1. If the connectives → and ↔ are present in the given formula, they are
replaced by ∧, ∨ and  [conditional equivalence formula]
2. If the negation is present before the given formula or a part of the
given formula, De Morgan’s Laws are applied so that the negation is brought before
the variables only.
* If necessary, the distributive and idempotent laws are applied.

5.Without constructing the truth tables, find the PDNF of the following
statements:
(a) (  p → q) ∧ (q ↔ p)

≡ (p ∨ q) ∧ [(q ∧ p) ∨ (  q ∧  p)] [12] conditional equivalence

≡ [(p ∨ q) ∧ (q ∧ p)] ∨ [(p ∨ q) ∧ (  q ∧  p)] distributive law

≡ [(p ∨ q) ∧ (p ∧ q)] ∨ [(p ∨ q) ∧  (p ∨ q)] [Demorgan's law]

≡ (p ∨ q) ∧ (p ∧ q) ∨ ≡ [p ∧ (p ∧ q)] ∨ [q ∧ (p ∧ q)]
[distributive law] [(A∨B) ∧C= (A∧C) ∨(B∧C)]
≡ (p ∧ q) ∨ (p ∧ q) = p ∧ q which is the PDNF

(b) (p ∧ q) ∨ (  p ∧ q) ∨ (q ∧ r)

= (p ∧ q∧T) ∨ (  p ∧ q∧T) ∨ (q ∧ r∧T)

≡ [(p ∧ q) ∧ (r ∨  r)] ∨ [(  p ∧ q) ∧ (r ∨  r)] ∨ [(q ∧ r) ∧ (p ∨  p)]

≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧  r) ∨ (  p ∧ q ∧ r) ∨ (  p ∧ q ∧  r)
∨ (q ∧ r ∧ p) ∨ (q ∧ r ∧  p)
All the brackets use distributive law[A ∧ (B ∨C)= (A ∧ B) ∨ (A ∧ C)

S ≡ (p ∧ q ∧ r) ∨ (p ∧ q ∧  r) ∨ (  p ∧ q ∧ r) ∨ (  p ∧ q ∧  r) is the PDNF.
To find PCNF from PDNF by using S ⇔  (  S)
 S⇔(p ∧  q ∧ r) ∨( p ∧  q ∧  r)) ∨(  p ∧  q ∧ r) ∨(  p ∧  q ∧  r)
PCNF:
S ⇔  (  S)=  [(p ∧  q ∧ r) ∨( p ∧  q ∧  r)) ∨(  p ∧  q ∧ r) ∨(  p ∧  q ∧  r)]
Demorgan's law-  (p ∨ q)=  p∧  p
=  (p ∧  q ∧ r) ∧  (p ∧  q ∧  r) ∧  (  p ∧  q ∧ r) ∧  (  p ∧  q ∧  r)]

=(  p∨q∨  r) ∧(  p∨q∨r) ∧(p∨q∨  r)) ∧(p∨q∨r)

.
6.Obtain the PCNF for S : (  p → r) ∧ (q ↔ p) and hence obtain the PDNF for S
Sol: S : (  p → r) ∧ (q ↔ p)
⇔ (p ∨ r) ∧ (q → p) ∧ (p → q) conditional equivalence
 ⇔ (p ∨ r) ∧ (  q ∨ p) ∧ (  p ∨ q) conditional
equivalence
[include the terms F=(q ∧  q) , F=(p ∧  q), F=(r ∧  r) where
ever required]
⇔ ((p ∨ r) ∨ (q ∧  q)) ∧ ((  q ∨ p) ∨ (  r ∧ r))∧ ((  p ∨ q) ∨ (r ∧  r))
distributive laws[A ∨(B ∧C)= (A ∨ B) ∧ (A ∨ C)]
⇔ (p ∨ r ∨ q) ∧ (p ∨ r ∨  q) ∧ (  q ∨ p ∨  r) ∧ (  q ∨ p ∨ r)∧
(  p ∨ q ∨ r) ∧ (  p ∨ q ∨  r)
PCNF S ⇔ (p ∨ r ∨ q) ∧ (p ∨ r ∨  q) ∧ (  q ∨ p ∨  r) ∧ (  p ∨ q ∨ r)∧
(  p ∨ q ∨  r)
To find PDNF from PCNF
 S ⇔ (p ∨ q ∨  r) ∧ (  p ∨  q ∨ r) ∧ (  p ∨  q ∨  r)
i.e.,  s write the remaining minterms which do not appear in S

S ⇔  (  S) ⇔  [(p ∨ q ∨  r) ∧ (  p ∨  q ∨ r) ∧ (  p ∨  q ∨  r)]

De Morgans Law

[  (p ∨ q ∨  r) ∨  (  p ∨  q ∨ r) ∨  (  p ∨  q ∨  r)]

De Morgans Law for the bracket terms

⇔ (  p ∧  q ∧ r) ∨ (p ∧ q ∧  r) ∨ (p ∧ q ∧ r)
Which is the PDNF

7.Obtain the principal disjunctive and conjunctive normal forms of

p → ((p → q) ∧  (  p ∨  q))
Sol:
p → ((p → q) ∧  (  p ∨  q)) Conditional equivalence
⇔  p ∨ ((  p ∨ q) ∧ (q ∧ p)

Include the terms (q ∨  q) and (p ∨  p) whereever required

⇔ (  p ∧ (q ∨  q)) ∨ (  p ∧ (q ∨  q)) ∨ (q ∧ (q ∧ p))
⇔ (  p ∧ q) ∨ (  p ∧  q) ∨ (  p ∧ q) ∨ (  p ∧  q) ∨ (q ∧ p)
S ⇔ (  p ∧ q) ∨ (  p ∧  q) ∨ (q ∧ p) is the PDNF
i.e.,  S ⇔ (p ∧  q)
i.e.,  (  S) ⇔  (p ∧  q) ⇔  p ∨ q is the PCNF

8.Obtain the PDNF of (p ∧ q) ∨ (  p ∧ r) ∨ (q ∧ r).

Sol:
(p ∧ q) ∨ (  p ∧ r) ∨ (q ∧ r) ⇔ ((p ∧ q) ∧ (r ∨  r)) ∨ ((  p ∧ r) ∧ (q ∨  q))
∨ ((q ∧ r) ∧ (p ∨ Yp))
⇔ (p ∧ q ∧ r) ∨ (p ∧ q ∧  r) ∨ (  p ∧ r ∧ q) ∨ (  p ∧ r ∧  q) ∨ (q ∧ r ∧ p)
∨ (q ∧ r ∧  p)
⇔ (p ∧ q ∧ r) ∨ (p ∧ q ∧  r) ∨ (  p ∧ r ∧ q) ∨ (  p ∧ r ∧  q)

Practice Problems:

Obtain the PDNF and PCNF of the following:

(i) (  p ∨  q) → (p ↔  q)
(ii) q ∧ (p ∨  q)
(iii) p → (p ∧ (q → p))
(iv) p ∨ (  p → (q ∨ (  q → r)))
(v) (q → p) ∧ (  p ∧ q)

Theory of Inference
[To check validity of the argument ]
Introduction
Inference theory is concerned with the inferring of a conclusion from a set
of premises (hypothesis or basic assumptions) by applying certain
principles of reasoning called the rules of inferences.
The processs of getting the conclusion by the rules of inferences in a
sequence of steps is called the arguments.
The conclusion arrived is called the valid conclusion and the argument is
called the valid argument.
Two methods are available to arrive the valid conclusion.
1. Truth table technique
2. Rules of inference
Truth table Technique
1. H 1, H 2, H 3,.......Hn be the set of premises and C be the conclusion of
the premises.

2. C is the valid conclusion if ( H 1  H 2  H 3  .......Hn)  C

3. By constructing relevant truth tables it is possible to determine

whether the conclusion is derived from the premises.
4. whenever the premises are true, the corresponding conclusion should
be true. then only the conclusion is valid, otherwise not a valid
conclusion.
Examples.
Check whether the conclusion is valid
H1, H2 - premises

1) H 1 : p, H 2 : p  q, C : q . (Conclusion)
Truth table

p q p pq
T T F T

T F F T

F T T T

F F T F

C-conclusion H1 H2
H1 and H2 are true only in the third row, in which C is also true. Hence C
is a valid conclusion.

2) H 1 : p  q, H 2 : q, C : p conclusuon

p q pq
T T T

T F F

F T T

F F T

C-conclusion H2 H1
H1 and H2 are true in the third row, but C is not true. Hence C is not a
valid conclusion.

Note. The truth table is tedious if the premises contain a large number of
variables.

Rules of inference
We give two rules of inference which are called rules P and T.
Rule P: A premises[statement] may be introduced at any point in the
derivation
Rule T: A formula can be introduced provided it is tautologically implied
by any one or more of the preceding formulas in the derivation.

Laws of Implication and Equivalence

Law Name

(p → q)∧p ⇒ q Detachment (Modes ponens)

(p → q)∧ q → p (Modus tollens)

p ⇒ p∨q, q ⇒ p∨q Disjunctive addition

p∧q ⇒ p , p∧q ⇒ q Conjunctive simplification

(p∨q)∧  p ⇒ q;( p∨q)∧  q ⇒ p Disjunctive simplification

( p → q)∧(q → r)⇒(p → r) Chain rule

( p → q)⇔(  q →  p)⇔(  p∨q) Conditional equivalence

( p → q)⇔(p → q)∧(q → p)⇔(p∧q∨  q∧  p) Bi-conditional equivalence

S.No. Laws
1 p → q ≡ p ∨ q
2 p → q ≡  q→  p contrapositive
 3 p ∨ q ≡ p → q
4 p ∧ q ≡  (p→  q)
5  (p → q) ≡ p ∧  q
6 (p → q)∧( p → r) ≡ p→(q ∧ r)
7 (p → r)∧( q → r) ≡ (p ∨ q)→ r
8 (p → q) ∨ ( p → r) ≡ p→(q ∨ r)
9 (p → r) ∨ ( q → r) ≡ (p ∧ q)→ r
10 p↔ q ≡ (p → q)∧( q→p)
11 p↔ q ≡  p ↔  q
12 p↔ q ≡ (p ∧ q) ∨ (  p ∧  q)
13  (p↔ q) ≡ p↔  q

Problems in Inference theory

1. Demonstrate that r is a valid inference from the premises
p → q, q → r, p.
Solution:
S.No. Proposition Explanation
1. p→q Given premise -Rule P
2. p Given premise -Rule P
3. q Modus ponens for 1), 2) (p → q)∧p ⇒ q
4. q→r Given premise -Rule P
5. r Modus ponens on (3), (4)
2. Using rules of inference, show that s ∨ r is tautologically implied by
p ∨ q, p → r, q → s.
Solution:
S.No. Proposition Explanation
1. p∨q Rule p
2. p → q Conditional Equivalance on (1) p → q ≡ p ∨q

3. q→s Rule p
4. p → s Chain rule (2), (3) ( p → q)∧(q → r)⇒(p → r)

5. p→r Rule p
6. s → p contrapositive (4) p→q ≡  q→ p
7. s → r Chain rule 6, 5 ( p → q)∧(q → r)⇒(p → r)
8. s∨r Conditional Equivalance on (7) p → q ≡  p ∨ q

3. If it rains heavily, the travelling will be difficult. If students arrive on

time, then the travelling was not difficult. They arrived on time. Therefore
it did not rained heavily.
 p: It rains heavily
q: Travelling is difficult
r: students arrived on time

premises : p  q, r  q , r
Conclusion : p
Step no. Statement Reason

1 pq Rule p

2 q  p Contra positive p → q ≡  q→ p
3 r  q Rule p

4 r  p 3,2 chain rule ( p → q)∧(q → r)⇒(p → r)

5 r Rule p

6 p 4,5 modus ponens (p → q)∧p ⇒ q

.Inconsistency of Premises
A set of premises p1,p2,...pn is said to be inconsistent if their conjunction
implies a contradiction.
Here also we can use both truth table techniques or rules of inference
based on the no. of premises given.
Example.
1. Show that p → q, p→ r, q →  r and p are inconsistent.
Step Statement reason
no.

1 p→q Rule p

2 q→ r Rule P

3 p→ r 1,2 chain rule

4 P Rule P

5 r 3,4 modus ponens

6 p→r Rule p

7 r → p 6 equivalence in
 contrapositive

8 p 5,7 modes ponens

9 p  p - contradiction Inconsistent

2. 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 p : Jack misses many classes p  q, q  s , r  s p  r
q : Jack fails high school
r : Jack reads a lot of books
s : Jack is uneducated
The premises are p → q, q → s, r →  s, p∧ r.
Step Statement reason
no.

1 p→q Rule p

2 q→s Rule P

3 p→s 1,2 chain rule

4 r→ s Rule P

5 s→ r 4 equivalence contrapositive
p→q ≡  q→ p
6 p→ r 3,5 chain rule

7  p∨  r 6 conditional equivalence p → q =  p∨q

8  ( p∧ r) De Morgan's law

9 p∧ r Rule P

9 (p∧ r) ∧  ( p∧ r) =F 8, 9 Inconsistent
5.Show that the premises E → S, S → H, A →  H, E ∧A are inconsistent.
S.No. Proposition Explanation
1. E→S Rule P
2. S→H Rule P
3. E→H Chain Rule (1) (2)
4. E ∧A Rule P
5. E Conjunctive simplification (4)
6. A Conjunctive simplification (4)
7. A→ H Rule P
8. H modes ponens (6), (7)
9. H modes ponens (3), (5)
10. H ∧  H =F Contradiction.
Hence the given premises are inconsistent.

(p → q)∧p ⇒ q Detachment (Modes ponens)

(p → q)∧ q → p (Modus tollens)

p∧q =q or p∧q =p

6. Test the validity of the following argument: It is not sunny this

afternoon and it is colder than yesterday. We will go swimming only if it is
sunny. If we do not go swimming then we will take a trip and if we take a
trip then will be home by sun set leads to the conclusion “we will be home
by sun set”.
p: It is sunny, q: It is colder than yesterday, r: We will go swimming,
s: We take a trip, t: We go home by sun set.
The premises are
p∧q, r → p, r → s, s → t ⇒ t
Argument
It consists of premises together with a conclusion. The argument is said
to be valid if p1 ∧p2 ∧p3 ∧...∧pn ⇒ C. Otherwise the argument is invalid.
Direct Proof
A direct proof is a proof in which the truth of the premises directly show
the truth of the conclusion.
Indirect Proof (Assuming the negation of the conclusion as one of the
premise and arriving a contradiction.)
An indirect proof proceeds by assuming that not only P is true, but also C
is false and then using P,  C as well as other premises, deduce a
contradiction.
Rules to derive direct and indirect proof:
(i) A proof must end in a finite number of steps.
(ii) Each step must be either a premise or a proposition that is implied
from previous steps using any valid equivalence or implication.
(iii) For a direct proof, the last must be the conclusion. For an indirect
proof, the last must be a contradiction.
Example.
1. Find the direct proof of  p∨q, s∨p,  q ⇒ s -conclusion.

Step Statement reason

no.

1  p∨q Rule p

2 p→q Conditional Equivalence on (1)

3 q → p Contra positive on (2) p→q ≡  q→ p

4 q Rule P

5 p 3,4 modes ponens

6 s∨p Rule p

7  s→ p 6, conditional equivalence

8  p→ s 7, equivalence in contrapositive

9 s 5,8 modes ponens

2.Use indirect proof method to show that r →  q, r∨s, s→  q, p→q⇒  p.

Solution. To use indirect proof method , we will include negation of the
conclusion as an additional premise and prove a contradiction.
Let   p= p as an additional premise
Step Statement reason
no.

1 P P(additional)

2 p→q Rule p

3 q 1,2 modes ponens

4 r → q Rule p

5 s→  q Rule p

6 (r∨s)→  q 4,5 and equivalence

7 (r∨s) Rule p

8 q 6,7 modes ponens

9 q∧  q 3,8 conjunction

10 F 9 and negation law

Therefore our conclusion that p is wrong , hence  p is the valid

conclusion.
3. Obtain the direct and indirect proof of p → q, q → r,  (p∧r), p∨r ⇒ r.
Direct Proof.
S.No. Proposition Explanation
1. p→q Rule P
2. q→r Rule P
3. p→r Chain Rule (1),(2)
4.  p∨r Conditional Equivalence (3)
5.  (p∧r) Rule P
6.  p∨  r De Morgan’s Law (5)

7. (  p∨r)∧(  p∨  r) By (4) and (6)

8.  p∨(r∧  r) Distributive Law
9. p Identity law
10. p∨r Rule P
11.  p∧(p∨r) By (9), (10)
12. (  p∧p)∨(  p∧r) Distributive Law

13.  p∧r
14. r Conjunctive simplification
 Indirect proof
S.No. Proposition Explanation
1. r Negated conclusion
2.  (p∧r) Rule P
3.  p∨  r De Morgan’s Law
4. p→q Rule P
5. q→r Rule P
6. p→r (4), (5) Chain Rule
7.  p∨r (6) Conditional equivalence
8. p∨r Rule P
9. (  p∨r)∧(p∨r) (7), (8)
10. (  p∧p)∨r Distributive Law
11. r Identity Law
12. r∧  r (1), ( 12) Contradiction
Therefore  r is the valid conclusion.
4. Give direct and indirect proof of a → b, c → b, d →(a∨c), d ⇒ b.
S.No. Proposition Explanation
1. a→b Rule P
2.  a∨b Equivalence (1)
3. c→b Rule P
4.  c∨b Equivalence (3)
5. (  a∨b)∧(  c∨b) By (2), (4)
6. (  a∨  c)∨b Distributive Law
7.  (a∨c)∨b De Morgan’s Law
8. d →(a∨c) Rule P
9. d Rule P
10. (a∨c)→ b Conditional Equivalence (7)
11. d→b Chain Rule (8), (10)
12. d Rule P
13. b Conditional Equivalence (11),(12)

Indirect Proof:
S.No. Proposition Explanation
1. b Negated conclusion
2. a→b Rule P
3. b → a (2) Contrapositive
4. c→b Rule P
5. b → c (4) Contrapositive
6. a (1),(3) Detachment
7. c ( 1), (6) Detachment
8.  a∧  c (6), (7)
9.  (a∨c) De Morgan’s Law
10. d →(a∨c) Rule P
11.  (a∨c)→  d (10) Contrapositive
12. d (9), (11) Detachment
13. d Rule P
14. d∧  d (12), (13) Contradiction

5. Test the validity of the following argument:

If I study, then I will not fail in Mathematics. If I do not play Basket ball,
then I will study. But I failed in Mathematics. Therefore I must have
played Basket ball.
p: i will study, q: not fail in Mathematics, r: do not play basket ball
To prove that

𝑝 → 𝑞, 𝑟 → 𝑝,  q ⇒  r

S.No. Proposition Explanation

1. r→p Rule P

2. p→q Rule P

3. r→q Chain Rule

4. q→r Contrapositive

5. q Rule P

6. r Detachment
 Predicate Calculus
Definition : Predicates or simple statements which turn out to be
prepositions involving the variables whose values or not well specified. A
predicate tells something about one or more objects.
Notations: Capital letters are used to denote the predicates and the
objects by the variables denoted by small letters in parenthesis example.
Example: The statement “ x is smaller than 10 ”. Hear the predicate is
smaller than 10 and the subject of the statement is x . Therefore the
given statement is denoted by P(x)

One place predicate : “ x is an integer” is denoted by I(x).

Two place predicate : “ x is less than y” Here the predicate is “ less
than” it is denoted by L(x, y).
Three place predicate: “Ram stands between Shyam and Mohan”.
Here the predicate is “stands between”. Denote it by S
Subject is Ram, Shyam, Mohan. Denote it by r, s, m respectively.
The symbolic form is S(r,s,m).

Remark: The statement P(x) is also said to be the value of the

proposition function P at x.

Equivalent predicate: If two predicates possess the same truth value

for all values of the variable then they are said to be equivalent.
Valid predicate : If all values satisfy a predicate then it is called valid
predicate.
Example: If P(x) denotes the statement “X greater than 7” then the truth
values of P(5) and P( 8) or false and true respectively.

Statement function: A single statement function of one variable is a

kind of expression containing the predicate and an individual variable.
The statement is obtained from the statement function by replacing the
variable by the name of objects. The statement so obtained is called as a
substitution instance of the statement function.
Example 1: Let B represent the predicate “ is tall” and let X be an
individual. Then B(X) will not be a simple statement function unless X is
replaced by the name of an object.
Example 2: Let B represent the predicate “ is tall” and let S be the name
of an object that is Shanthi then B(S) is a statement function.

Statement function of two variables: This statement function of two

variables can be viewed as an extension of one variable.
Example : Let F(x,y): X is shorter than y.
Replacing x and y by the names of objects Ram and Shyam we obtain the
following statement.
“Ram is shorter than Shyam”.

Compound statement: A compound statement is one which can be

obtained by combining one or more statement functions and using logical
connectives (AND,OR, Conditional, bi conditional and negation)as follows.
Example: Sita is intelligent and the house is white .
Let I(s) : Sita is intelligent .
W(h) : The house is white.
Now the symbolic form is I(s)∧W(h).

Quantifiers
When all the variables in a propositional function are assigned values, the
resulting statement has a truth value.
There is an another important way called quantification to create a
statement from a statement function.
There are two types of quantification.
1) Universal quantification (∀x) [for all, for every,each]
2) Existential quantification. (∃x) [there exists, for some, for few,
specifically]

Universal quantifier :
“For all x, x is an integer” is denoted by (∀x)I(x) or (x)I(x).
Here “for all x” is called the universal quantifier and it is denoted by the
symbol “∀”
Existential quantifier:
“There exists an integer x which is prime” can be written as (∃x)P(x)
where the phrase “ there exists” is called an existential quantifier.

Meaning of quantifiers:
(∀x)Q(x) means the predicate Q(x) is true for all values in the universe of
x.
(∃x)Q(x) means that the predicate Q(x) is satisfied if there exists at least
one value in the universe of the variable x.

Universe of discourse:
It is defined as a set of all values taken by a variable. The universe of
discourse specifies the possible values of the variable x. Therefore it is
defined as the domain of the variable in a proportional function.
Example: Let us consider the universe of discourse by the following sets.
i) {−1, 7, 8, 11, 12}
ii) {−3, 8, 9, −2}
iii) {2, 3, 4}
iv){11, 13, 20}

Free and bound variables:

 The variable x is the statement “P(x) : The number (x + 2) is an
even integer” is a free variable.
 The variable in the statement (∀x)P(x) and (∃x)P(x) is said to be
bound variable. It is bounded by the existential and universal
quantifier.
 Here the scope of the quantifier is P(x).
 Example:
1) (x) P(x) ∧(Q(x) ∨R(x))
P(x) is the bounded occurence, Q(x), R(x) free occurence

 2) (∃x)(P(x) ∧(Q(y) ∨ (∀x)R(x))

 free variable =y
  bounded variable =x
 free occurence :Q(y)
 bounded occurence:P(x), R(x)

Problems: Representation of expression using quantifiers:

Q.NO.1 Symbolise the statement.
i) All Men should be educated
ii) All complex numbers composed of real and imaginary parts.
iii) All lions are dangerous.
iv) All dogs bark.
Answer:
i) M(x): x is a man.
E(x) : x is educated.
Therefore (∀x)(M(x)→E(x))
ii) C(x): x is a complex number.
R(x) : x is composed of real and imaginary parts.
Therefore (∀x)(C(x)→R(x))
iii) L(x): x is a Lion.
D(x) : x is dangerous.
Therefore (∀x)(L(x)→D(x))
iv) L(x): x is a dog
D(x) : x barks
Therefore (∀x)(L(x)→D(x))

Problems under truth values of quantified statements

1) If the universe of discourse is {3,-2,7,8,-2} then what is the truth
value of (∀x)Q(X)and (∋ x)(Q(x) where Q(x):x is less than 5
Solution: (∀x)Q(X) is false (F) and (∋ x)(Q(x) is true (T).

2) If the universe of discourse is {1,2} then what is the truth value of

(∀x)(P(x)⋁Q(X) where P(x):x=1 and Q(x):x=2
Solution: (∀x)(P(x)⋁Q(X) is true.

3) Let Q(x,y) denote x+y=0 what are the truth values of the quantified
statements (∋ y)(∀x)Q(x, y)and (∀x)(∋ y)Q(x, y)?
Solution: (∋ y)(∀x)Q(x, y) is false and (∀x)(∋ y)Q(x, y) is true.

4) If the universe of discourse is {1} and T is any tautology then what is

the truth value of (∋ x)(P(x) → Q(x)) ∧ T where P(x):x>2 and Q(x):x=0
Solution: (∋ x)(P(x) → Q(x)) ∧ T is true.

Logical equivalences and Logical implications of quantified

statements:
Logical equivalence:
Let P(x) and Q(x) be open statements defined for a given universe. They
are said to be logically equivalent if P(a)⟷Q(a) is true for each
replacement ‘a’ from the universe.
i.e., P(a)⟷Q(a) for each ‘a’ in the universe.
Then we write (∀x)(P(x) ⇔ Q(x)
Logical implication:
If the implication P(a)→Q(a) is true for each ‘a’ in the universe then we
write (∀x)(P(x)⟹Q(x)) and we say that P(x) logically implies Q(x).

Converse, Inverse and Contrapositive of a statement of the

formula (∀𝐱)(𝐏(𝐱)⟶𝐐(𝐱))
i) The converse statement is (∀x)(Q(x)⟶P(x))
ii) The inverse statement is (∀x)(¬P(x)⟶¬Q(x))
iii)The Contra positive statement is (∀x)(¬Q(x)⟶¬P(x))

Important equivalence statements

i) The statement (∀x)(P(x)⟶Q(x)) and its Contra positive
(∀x)(¬Q(x)⟶¬P(x)) statements are logically equivalent.
i.e., (∀x)(P(x)⟶Q(x)) ⟺(∀x)(¬Q(x)⟶¬P(x))
ii) The Converse and Inverse statements are logically equivalent.
i.e., (∀x)(Q(x)⟶P(x)) ⟺ (∀x)(¬P(x)⟶¬Q(x))

***************************************************************************************

Logical equivalences and implications for quantified statement in

one variable:
For any set of open statements in the variable 𝑥 and for prescribed
universe , we have the following logical implications and equivalences.
1. (∀𝑥)[𝑃(𝑥) ∨ 𝑄(𝑥)] ⇔ (∀𝑥)(𝑃(𝑥) ∨ (∀𝑥)𝑄(𝑥)

2. (∀𝑥)[𝑃(𝑥) ∧ 𝑄(𝑥)] ⇔ (∀𝑥)𝑃(𝑥) ∧ (∀𝑥)𝑄(𝑥)

3. (∀𝑥)[𝑃(𝑥) ∧ 𝑄(𝑥) ∧ 𝑅(𝑥)] ⇔ (∀𝑥)𝑃(𝑥) ∧ (∀𝑥)𝑄(𝑥) ∧ (∀𝑥)𝑅(𝑥)
4. (∀𝑥)⅂[⅂𝑃(𝑥)] ⇔ (∀𝑥)[𝑃(𝑥)] ⅂ − 𝑛𝑒𝑔𝑎𝑡𝑖𝑜𝑛
5. (∀𝑥)⅂[𝑃(𝑥) ∧ 𝑄(𝑥)] ⇔ (∀𝑥)[⅂𝑃(𝑥) ∨ ⅂𝑄(𝑥)]
6. (∀𝑥)⅂[𝑃(𝑥) ∨ 𝑄(𝑥)] ⇔ (∀𝑥)[⅂𝑃(𝑥) ∧ ⅂𝑄(𝑥)]

7. (∀𝑥)[𝑃(𝑥) → 𝑄(𝑥)] ⇔ (∀𝑥)𝑃(𝑥) → (∀𝑥)𝑄(𝑥)

8. (∃𝑥)[𝑃(𝑥) ∧ 𝑄(𝑥)] ⇔ (∃𝑥)𝑃(𝑥) ∧ (∃𝑥)𝑄(𝑥)
9. (∃𝑥)[𝑃(𝑥) → 𝑄(𝑥)] ⇒ (∃𝑥)[⅂𝑃(𝑥) ∨ 𝑄(𝑥)

Negation of Quantified statement

1. ⅂(∀𝑥)[𝑃(𝑥)] ⇔ (∃𝑥)[ ⅂ 𝑃(𝑥)]

2. ⅂(∃𝑥)[𝑃(𝑥)] ⇔ (∀𝑥)[ ⅂ 𝑃(𝑥)]

3. ⅂[(∀𝑥) ⅂ 𝑃(𝑥)] ⇔ (∃𝑥)[𝑃(𝑥)]

4. ⅂[(∃𝑥)⅂𝑃(𝑥)] ⇔ (∀𝑥)[𝑃(𝑥)]

Laws of Implication and Equivalence (propositional calculus)

Law Name

(p → q)∧p ⇒ q Detachment (Modes ponens)

(p → q)∧ q → p (Modus tollens)

p ⇒ p∨q, q ⇒ p∨q Disjunctive addition

p∧q ⇒ p : p∧q ⇒ q Conjunctive simplification

(p∨q)∧  p ⇒ q;( p∨q)∧  q ⇒ p Disjunctive simplification

( p → q)∧(q → r)⇒(p → r) Chain rule

( p → q)⇔(  q →  p)⇔(  p∨q) Conditional equivalence

( p → q)⇔(p → q)∧(q → p)⇔(p∧q∨  q∧  p) Bi-conditional equivalence

Theory of inference and valid arguments in predicate calculus

1. Universal specification rule [US rule]

(∀𝑥)[𝑃(𝑥)] ⇒ 𝑃(𝑦)( 𝑦 𝑖𝑠 𝑝𝑎𝑟𝑡𝑖𝑐𝑢𝑙𝑎𝑟)

ie. (∀𝑥)[𝑃(𝑥)] ⇒ 𝑃(𝑧), 𝑃(𝑦), 𝑃(𝑎), … ..

2. Existential specification rule [ES rule]

(∃𝑥)[𝑃(𝑥)] ⇒ 𝑃(𝑎) (𝑜𝑟) 𝑃(𝑏) (𝑜𝑟) 𝑃(𝑐) … ..

ie. (∃𝑥)[𝑃(𝑥)] ⇒ 𝑃(𝑦)
3. Universal generalisation rule [UG rule]

𝑃(𝑦) ⇒ (∀𝑥)[𝑃(𝑥)]

ie. From 𝑃(𝑦), we can drive (∀𝑥)[𝑃(𝑥)]

4. Existential generalisation rule [EG rule]

𝑃(𝑦) ⇒ (∃𝑥)[𝑃(𝑥)]

ie. From 𝑃(𝑥) or 𝑃(𝑎) we can drive (∃𝑥)[𝑃(𝑥)]

Problems:

1) Use predicate logic to prove (∀𝑥)[𝑃(𝑥) → 𝑄(𝑥)] ∧ (∀𝑥)𝑃(𝑥) ⇒ (∀𝑥)[𝑄(𝑥)]

(∀𝑥)[𝑃(𝑥) → 𝑄(𝑥)], (∀𝑥)𝑃(𝑥)𝑎𝑟𝑒 𝑡ℎ𝑒 𝑝𝑟𝑒𝑚𝑖𝑠𝑒𝑠

(∀𝑥)[𝑄(𝑥)] − 𝑐𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛

Soln.
Steps Premise Reason
1. (∀𝑥)[𝑃(𝑥) → 𝑄(𝑥)] Rule P

2. 𝑃(𝑦) → 𝑄(𝑦) (1) Rule US

3. (∀𝑥)𝑃(𝑥) Rule P
4. 𝑃(𝑦) Rule US (3)
5. 𝑄(𝑦) 2,4 [ Modus Ponens (2), (4) (p → q)∧p ⇒ q]
6. (∀𝑥)𝑄(𝑥) Rule UG (5)
2) Prove that (∀𝑥)[𝑃(𝑥) ∧ 𝑄(𝑥)] ⇒ (∀𝑥)[𝑃(𝑥)] ∧ (∀𝑥)[𝑄(𝑥)].
Premises: (∀𝑥)[𝑃(𝑥) ∧ 𝑄(𝑥)]
Conclusion: (∀𝑥)[𝑃(𝑥)] ∧ (∀𝑥)[𝑄(𝑥)].

Soln.
Steps Premise Reason
1. (∀𝑥)[𝑃(𝑥) ∧ 𝑄(𝑥)] Rule P
2. 𝑃(𝑦) ∧ 𝑄(𝑦) Rule US (1)
3. 𝑃(𝑦) Rule T (2) conjunctive simplification
𝑃 ∧ 𝑄 𝑖𝑚𝑝𝑙𝑖𝑒𝑠 𝑃
4. (∀𝑥)[𝑃(𝑥)] Rule UG (3)

5. 𝑄(𝑦) Rule T (2) simplification 𝑃 ∧ 𝑄 𝑖𝑚𝑝𝑙𝑖𝑒𝑠 𝑄

6. (∀𝑥)[𝑄(𝑥)] Rule UG (5)
7. (∀𝑥)[𝑃(𝑥)] ∧ (∀𝑥)[𝑄(𝑥)] Rule T (4), (6) conjunction

3) Show that the following argument is valid. “Every microcomputer has a

serial interface port. Some microcomputers have a parallel port.
Therefore, some microcomputers have both serial and parallel port.
Soln.
Let 𝑀(𝑥): x is a microcomputer
𝑆(𝑥): x has serial port
𝑃(𝑥): x has parallel port

premises : (∀𝑥)[𝑀(𝑥) → 𝑆(𝑥)], (∃𝑥)[𝑀(𝑥) ∧ 𝑃(𝑥)]

conclusion: (∃𝑥)[𝑀(𝑥) ∧ 𝑆(𝑥) ∧ 𝑃(𝑥)]

Therefore, given argument is

(∀𝑥)[𝑀(𝑥) → 𝑆(𝑥)] ∧(∃𝑥)[𝑀(𝑥) ∧ 𝑃(𝑥)] ⇒ (∃𝑥)[𝑀(𝑥) ∧ 𝑆(𝑥) ∧ 𝑃(𝑥)]

Steps Premise Reason

1. (∀𝑥)[𝑀(𝑥) → 𝑆(𝑥)] Rule P
2. [𝑀(𝑦) → 𝑆(𝑦)] Rule US (1)
3. (∃𝑥)[𝑀(𝑥) ∧ 𝑃(𝑥)] Rule P
4. 𝑀(𝑦) ∧ 𝑃(𝑦) Rule ES (3)
5. 𝑀(𝑦) Rule T (4) , simplification P∧Q ⇒P
6. 𝑃(𝑦) Rule T (5), simplification P∧Q ⇒Q
7. 𝑆(𝑦) Rule T (5),(2) 𝑚𝑜𝑑𝑢𝑠 𝑝𝑜𝑛𝑒𝑛𝑠 𝑃 ∧ (𝑃 → 𝑄) ⇒ 𝑄
8. 𝑀(𝑦) ∧ 𝑃(𝑦) ∧ 𝑆(𝑦) Rule T(4),(7) 𝑃, 𝑄, 𝑅 ⇒ 𝑃 ∧ 𝑄 ∧ 𝑅 conjunction
9. (∃𝑥)[𝑀(𝑥) ∧ 𝑃(𝑥) ∧ 𝑆(𝑥)] ES (8)2

4) Prove that the premises “Everyone in the Discrete Mathematics class

has taken a course in Computer Science. Mala is a student in this class
imply the conclusion Mala has taken a course in Computer Science.”
Soln.
Assume 𝐷(𝑥): x is in the Discrete Mathematics class
𝐶(𝑥):x has taken a course in Computer Science
𝐷(𝑚): Mala is a student in the Discrete Mathematics class.
Premises: (∀𝑥)[𝐷(𝑥) → 𝐶(𝑥)], 𝐷(𝑚)
conclusion: 𝐶(𝑚)

To prove
(∀𝑥)[𝐷(𝑥) → 𝐶(𝑥)] ∧ 𝐷(𝑚) ⇒ 𝐶(𝑚)

Steps Premise Reason

1. (∀𝑥)[𝐷(𝑥) → 𝐶(𝑥)] Rule P
2. 𝐷(𝑚) → 𝐶(𝑚) US (1)
3. 𝐷(𝑚) Rule P
4. 𝐶(𝑚) Rule T (2), (3) Modus Ponens
𝑃 ∧ (𝑃 → 𝑄) ⇒ 𝑄
5) Show by indirect method of proof, that
∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) ⇒ (∀𝑥𝑃(𝑥)) ∨ (∃𝑥𝑄(𝑥))
Soln. For indirect proof method negated conclusion is the additional
premise and arrive a contradiction
Let us assume that ⅂[(∀𝑥𝑃(𝑥) ∨ (∃𝑥𝑄(𝑥))] as an additional premise and
prove a contradiction.
Steps Premise Reason
1. ⅂[(∀𝑥𝑃(𝑥) ∨ (∃𝑥𝑄(𝑥))] P (additional)

2. ⅂(∀𝑥𝑃(𝑥) ∧ ⅂(∃𝑥𝑄(𝑥)) T, De Morgan’s law (1) ⅂(𝑝 ∨ 𝑞) = ⅂𝑝 ∧ ⅂𝑞

3. ⅂(∀𝑥𝑃(𝑥)) T, simplification (2) P∧Q ⇒P
4. ⅂(∃𝑥𝑄(𝑥)) T, simplification (2) P∧Q ⇒Q

5. ∃𝑥⅂𝑃(𝑥) T, negation (3)

6. ∀𝑥⅂𝑄(𝑥) T, negation (4)

7. ⅂𝑃(𝑎) ES (5)
8. ⅂Q(a) US (6)
9. ⅂𝑃(𝑎) ∧ ⅂𝑄(𝑎) T, conjunction (7), (8) p,q ⇒ 𝑝 ∧ 𝑞
10. ⅂(𝑃(𝑎) ∨ 𝑄(𝑎)) T, De Morgan’s law (9) ⅂(𝑝 ∨ 𝑞) = ⅂𝑝 ∧ ⅂𝑞
11. ∀𝑥(𝑃(𝑥) ∨ 𝑄(𝑥)) Rule P
12. 𝑃(𝑎) ∨ 𝑄(𝑎) US (11)
13. (𝑃(𝑎) ∨ 𝑄(𝑎)) ∧ ⅂(𝑃(𝑎) ∧ 𝑄(𝑎)) T, conjunction (10), (12)
14. F T, (13)
This False (F) is because of our assumption of the negated conclusion ,
Therefore our conclusion must be [(∀𝑥𝑃(𝑥) ∨ (∃𝑥𝑄(𝑥))]

6)Prove that ∀𝑥 (𝑃(𝑥) → (𝑄(𝑦) ∧ 𝑅(𝑥))) , ∃𝑥 𝑃(𝑥) ⇒ 𝑄(𝑦) ∧ ∃𝑥(𝑃(𝑥) ∧ 𝑅(𝑥)).

Soln.
Steps Premise Reason

1. ∀𝑥 (𝑃(𝑥) → (𝑄(𝑦) ∧ 𝑅(𝑥))) P

2. 𝑃(𝑧) → (𝑄(𝑦) ∧ 𝑅(𝑧)) US (1)

3. ∃𝑥 𝑃(𝑥) P
4. 𝑃(𝑧) ES (3)
5. 𝑄(𝑦) ∧ 𝑅(𝑧) T, Modus Ponens 𝑃 ∧ (𝑃 → 𝑄) ⇒ 𝑄
6. 𝑄(𝑦) T, simplification (5)
7. 𝑅(𝑧) T, simplification (5)
8. 𝑃(𝑧) ∧ 𝑅(𝑧) T, conjunction (4), (7)
9. ∃𝑥 (𝑃(𝑥) ∧ 𝑅(𝑥)) EG (8)
10. 𝑄(𝑦) ∧ ∃𝑥(𝑃(𝑥) ∧ 𝑅(𝑥) T, conjunction (6), (10)

7)Show that the conclusion ∀𝑥(𝑃(𝑥)) → ⅂𝑄(𝑥)) follows from the premises
∃𝑥 (𝑃(𝑥) ∧ 𝑄(𝑥)) → ∀𝑦(𝑅(𝑦) → 𝑆(𝑦)) and ∃𝑦 (𝑅(𝑦) ∧ ⅂𝑆(𝑦)) .

Soln.
Steps Premise Reason
1. ∃𝑦 (𝑅(𝑦) ∧ ⅂𝑆(𝑦)) P
2. 𝑅(𝑎) ∧ ⅂𝑆(𝑎)) ES (1)
3. ⅂(𝑅(𝑎) → 𝑆(𝑎)) T, (2) and equivalence

4. ∃𝑦[ ⅂(𝑅(𝑦) → 𝑆(𝑦))] EG, (3)

5. ⅂∀𝑦(𝑅(𝑦) → 𝑆(𝑦)) T, (4) and negationEquivalence

6. ∃𝑥 (𝑃(𝑥) ∧ 𝑄(𝑥)) → ∀𝑦(𝑅(𝑦) → 𝑆(𝑦)) P
7. ⅂∃𝑥 (𝑃(𝑥) ∧ 𝑄(𝑥)) T, (5), (6) andmodus tollens
8. ∀𝑥 ⅂(𝑃(𝑥) ∧ 𝑄(𝑥)) T, (7) and negative Equivalence
9. ⅂(𝑃(𝑏) ∧ 𝑄(𝑏)) US , (8)

10. ⅂𝑃(𝑏) ∨ ⅂𝑄(𝑏) T, (9) De Morgan’s law

11. 𝑃(𝑏) → ⅂𝑄(𝑏) T, (10) , Equivalence
12. ∀𝑥(𝑃(𝑥) → ⅂𝑄(𝑥)) UG, (11)
8) Prove the implication

∀𝑥 (𝑃(𝑥) → 𝑄(𝑥)), ∀𝑥(𝑅(𝑥) → ⅂𝑄(𝑥)) ⇒ ∀𝑥(𝑅(𝑥) → ⅂𝑃(𝑥))

Soln.
Steps Premise Reason

1. ∀𝑥 (𝑃(𝑥) → 𝑄(𝑥)) P

2. 𝑃(𝑎) → 𝑄(𝑎) US , (1)

3. ∀𝑥 (𝑅(𝑥) → ⅂𝑄(𝑥)) P
4. 𝑅(𝑎) → ⅂𝑄(𝑎) US, (2)
5. 𝑄(𝑎) → ⅂𝑅(𝑎) T, (4) and

Equivalence
6. 𝑃(𝑎) → ⅂𝑅(𝑎) T, (2), (5) ,

hypothetical syllogism or chain rule

7. 𝑅(𝑎) → ⅂𝑃(𝑎) T, (6) and equivalence
8. ∀𝑥 (𝑅(𝑥) → ⅂𝑃(𝑥)) UG, (7)

9) Use the indirect method to prove that the conclusion ∃𝑧 𝑄(𝑧) follows
from the premises ∀𝑥 (𝑃(𝑥) → 𝑄(𝑥)) and ∃𝑦𝑃(𝑦).

Soln.
Steps Premise Reason
1. ⅂(∃𝑧 𝑄(𝑧)) P (additional) - negated conclusion
2. ∀𝑧 (⅂𝑄(𝑧)) T, (1) and negative equivalence
3. ⅂ 𝑄(𝑎) US, (2)
4. ∃𝑦 𝑃(𝑦) Rule P
5. 𝑃(𝑎) ES , (4)

6. 𝑃(𝑎) ∧ ⅂𝑄(𝑎) T, (3),(5), Conjunction

7. ⅂( ⅂ 𝑃(𝑎) ∨ 𝑄(𝑎)) T, (6) and Equivalence [DeMorgan's]
⅂(𝑝 ∨ 𝑞) = ⅂𝑝 ∧ ⅂𝑞
8. ⅂ (𝑃(𝑎) → 𝑄(𝑎)) T, (7) and conditional Equivalence
( p → q)⇔(  p∨q)
9. ∀𝑥 (𝑃(𝑥) → 𝑄(𝑥)) Rule P
10. 𝑃(𝑎) → 𝑄(𝑎) US , (9)

11. (𝑃(𝑎) → 𝑄(𝑎)) ∧ ⅂(𝑃(𝑎) → 𝑄(𝑎)) T, (8), (10) and Conjunction

12. F T, (11) and negative law

This False (F) is because of our assumption of the negated conclusion ,
Therefore our conclusion must be (∃𝑧 𝑄(𝑧)

10) Show that ∀𝑥 (𝑃(𝑥) ∨ 𝑄(𝑥)) ⇒ ∀𝑥 𝑃(𝑥) ∨ ∃𝑥 𝑄(𝑥) using the indirect

method.
Soln.
Steps Premise Reason
1. ⅂ (⅂ (∀𝑥 𝑃(𝑥) ∨ ∃𝑥 𝑄(𝑥)) P (additional)
2. ⅂ (∀𝑥 𝑃(𝑥) ∧ ⅂(∃𝑥 𝑄(𝑥)) T, (1) and De Morgan’s law

3. ∃𝑥 ( ⅂ 𝑃(𝑥)) ∧ ∀𝑥 ( ⅂ 𝑄(𝑥)) T, (2) and negationEquivalence

4. ∃𝑥 ( ⅂ 𝑃(𝑥)) T, (3) and Simplification

5. ∀𝑥 ( ⅂ 𝑄(𝑥)) T, (3) and Simplification
6. ⅂ 𝑃(𝑎) ES , (4)

7. ⅂ 𝑄(𝑎) US , (5)
8. ⅂ 𝑃(𝑎) ∧ ⅂ 𝑄(𝑎) T, (6), (7) and Conjunction
9. ⅂ (𝑃(𝑎) ∨ 𝑄(𝑎)) T, (8) and De Morgan’s law
10. ∀𝑥 (𝑃(𝑥) ∨ 𝑄(𝑥)) P

11. 𝑃(𝑎) ∨ 𝑄(𝑎) US, (10)

12. (𝑃(𝑎) ∨ 𝑄(𝑎)) ∨ ⅂ (𝑃(𝑎) ∨ 𝑄(𝑎)) T, (9), (11) andConjunction

13. F T, (12) and negation law

11) Verify the validity of the following argument:

Lions are dangerous animals. There are lions. Therefore there are
dangerous animals.

Soln.

Let L(x): x is a lion

D(x): x is a dangerous animal

We need to show:
(∀𝑥)(𝐿(𝑥) → 𝐷(𝑥)), (∃𝑥)(𝐿(𝑥)) ⇒ (∃𝑥)(𝐷(𝑥))

Steps Premise Reason

1. (∃𝑥)(𝐿(𝑥)) P
2. 𝐿(𝑏) ES, (1)

3. (∀𝑥)(𝐿(𝑥) → 𝐷(𝑥)) P

4. 𝐿(𝑏) → 𝐷(𝑏) US, (3)

5. 𝐷(𝑏) Detachment (2),(4)
6. (∃𝑥)(𝐷(𝑥)) EG, (5)

Thus the inference is valid.

12) Give an argument which will establish the validity of the following
inference:
All integers are rational numbers. Some integers are powers of 2.
Therefore, some rational numbers are powers of 2.

Solution:
Let P(x): x is an integer
R(x): x is a rational number
S(x): x is the power of 2
We need to show:
(∀𝑥 )(𝑃(𝑥) → 𝑅(𝑥)), (∃𝑥)(𝑃(𝑥) ∧ 𝑆(𝑥)) ⇒ (∃𝑥)(𝑅(𝑥) ∧ 𝑆(𝑥))

Steps Premise Reason

1. (∃𝑥)(𝑃(𝑥) ∧ 𝑆(𝑥)) Rule P

2. 𝑃(𝑏) ∧ 𝑆(𝑏) ES , (1)

3. 𝑃(𝑏) Conjunction simplification (2)
4. 𝑆(𝑏) Conjunction simplification (2)

5. (∀𝑥 )(𝑃(𝑥) → 𝑅(𝑥)) Rule P

6. 𝑃(𝑏) → 𝑅(𝑏) US , (5)

7. 𝑅(𝑏) Detachment (3), (6) modus ponens
8. R(𝑏) ∧ 𝑆(𝑏) Conjunction (4), (7)
9. (∃𝑥)(𝑅(𝑥) ∧ 𝑆(𝑥)) EG (8)

13) Prove that (∀𝑥)(𝐻(𝑥) → 𝑀(𝑥)) ∧ 𝐻(𝑆) ⇒ 𝑀(𝑆).

Soln.
Steps Premise Reason
1. (∀𝑥)(𝐻(𝑥) → 𝑀(𝑥)) Rule P
2. 𝐻(𝑆) → 𝑀(𝑆) US (1)

3. 𝐻(𝑆) Rule P
4. 𝑀(𝑆) Detachment (2), (3)

14) Prove that the premises, “A student in the class has not read the book
and everyone in the class passed the first exam” imply the conclusion
“someone who passed the first exam has not read the book.”
(Hint):
Assume Universe: Set of all students in the college
𝐶(𝑥): x is in the class
𝐵(𝑥): x has read the book
𝑃(𝑥): x passed the first exam
To prove (∃𝑥)[𝐶(𝑥) ∧ 𝐵(𝑥)] ∧ (∀𝑥)[𝐶(𝑥) → 𝑃(𝑥)] ⇒ (∃𝑥)[𝑃(𝑥) ∧ ⅂𝐵(𝑥)]