Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

COMPUTATIONAL MATHEMATICS
SUBJECT CODE-24BSCSMA11

Dr. Vishal Patil

Module-2: Mathematical Logic
Dr. Vishal Patil
AIML-A
Department of Basic Sciences- Mathematics

FET, Jain(Deemed-to-be-University)
CONTENT MODULE – 2
Mathematical Logic
10 hours

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

• Logical Connectives and Truth Tables
Propositions
• Tautology; Contradiction

Logical Equivalence and

• Converse, Inverse and Contrapositive; Logical Implication

Dr. Vishal Patil

the Laws of Logic

• Definitions and Examples

Rules of Inference
• Problems

Open statements; • Definition and Example

Quantifiers • Problems

• Definitions with Examples

Logical Implication
• Problems
involving Quantifiers
• Statements with more than one variables

18/09/24 Module-2: Mathematical Logic 2

Propositions

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Propositions- Proposition is a declarative statement which in a given context is either true or
false but not both.
Propositions Examples-
• 7 + 4 = 10

Dr. Vishal Patil

• Apples are black.
• Narendra Modi is president of India.
• Two and two makes 5.
• 2016 will be the leap year.
• Delhi is in India.
All these statements are propositions. This is because they are either true or false but not both.
Truth Values
If proposition is True its value is ‘1’ If proposition is False its value is ‘0’
18/09/24 Module-2: Mathematical Logic 3
Types Of Propositions-

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Atomic Propositions- Compound Propositions-

Dr. Vishal Patil

Atomic propositions are those •Compound propositions are those propositions that
propositions that can not be divided are formed by combining one or more atomic
further. propositions using connectives.
Small letters like p, q, r, s etc. are used to •In other words, compound propositions are those
represent atomic propositions. propositions that contain some connective.
Examples- •Capital letters like P, Q, R, S etc. are used to
p : Sun rises in the east. represent compound propositions.
q : Sun sets in the west. Examples-
r : Apples are red. P : Sun rises in the east and Sun sets in the west.
s : Grapes are green Q : Apples are red and Grapes are green.
18/09/24 Module-2: Mathematical Logic 4
 Statements That Are Not Propositions- Example:
Following kinds of statements are not propositions- Following statements are not propositions-

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

A predicate is an expression of one
[Link] •Close the door. (Command)
or more variables defined on some
[Link] •Do you speak French? (Question)
specific domain
[Link] •What a beautiful picture! (Exclamation)
[Link] •I always tell lie. (Inconsistent)
[Link] or Proposition Function •P(x) : x + 3 = 5 (Predicate)

Dr. Vishal Patil

PRACTICE PROBLEMS BASED ON PROPOSITIONS-
Identify which of the following
statements are propositions- 10. Not a proposition (Command)
10. Open the door. 11. Not a proposition (Question)
1. France is a country. 1. Proposition (True) 11. Are you tired? 12. Not a proposition
2. 2020 will be a leap year. 2. Proposition (True) 12. What a bright sunny (Exclamation)
3. Proposition (False) day! 13. Proposition (True)
3. Sun rises in the west. 13. Mumbai is in India. 14. Proposition (True)
4. Not a proposition (Predicate)
4. P(x) : x + 6 = 7 5. Proposition (False) 14. I always tell truth. 15. Not a proposition (Inconsistent)
5. P(5) : 5 + 6 = 2 6. Proposition (False) 15. I always tell lie. 16. Not a proposition (Command)
6. Apples are oranges. 7. Proposition (False) 16. Do not go there. 17. Proposition (Will be confirmed
7. Grapes are black. 8. Proposition (True) 17. It will rain tomorrow. tomorrow whether true or
8. Two and two makes 4. 9. Not a proposition (Predicate) 18. Fan is rotating. false)
9. x > 10 18. Proposition (True if fan is
rotating otherwise false)
18/09/24 Module-2: Mathematical Logic 5
Logical Connectives-
Connectives are the operators that are used to combine one or more propositions.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Name of Connective Connective Word Symbol

Negation Not ¬ or ∼ or ‘ or –

Dr. Vishal Patil

Conjunction And ∧

Disjunction Or ∨

Conditional If-then →

Biconditional If and only if ↔

18/09/24 Module-2: Mathematical Logic 6

1. Negation- 2. Conjunction- 3. Disjunction- If p and q are two propositions,
If p and q are two propositions, then disjunction of p and q is a proposition which
If p is a proposition, then
then conjunction of p and q is is-
negation of p is a proposition

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

• If any one is true – True
which is- a proposition which is-
• True when p is false • if both are true ----True p q p∨q
• False when p is true. • else False
0 0 0
p ∼p or ¬𝐩 P q p∧q
0 1 1

Dr. Vishal Patil

0 1 0 0 0
1 0 1
1 0 0 1 0
1 1 1
Example- 1 0 0
Example- If p and q are two propositions
1 1 1 where-
If p : It is raining outside. •p : 2 + 4 = 6
Then, Negation of p is- Example- If p and q are two
propositions where-
•q : It is raining outside
∼p : It is not raining outside. Then, disjunction of p and q is-
• p:2+4=6
• q : It is raining outside. p ∨ q : 2 + 4 = 6 or it is raining outside
hen, conjunction of p and q is- p ∧
q : 2 + 4 = 6 and it is raining outside

18/09/24 Module-2: Mathematical Logic 7

4. Conditional- If p and q are two propositions, 5. Biconditional- If p and q are two propositions, then-
then- • Proposition of the type “p if and only if q” is called a
• Proposition of the type “If p then q” is called a biconditional or bi-implication proposition.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

conditional or implication proposition. • If Both Are Same ---- True
Only in one case you get False
• 1st Is True 2nd is False--- False
• Else True

Dr. Vishal Patil

p q p→q q→p p↔q
p q p→q
0 0 1 1 1
0 0 1
0 1 1 0 0
0 1 1
1 0 0 1 0
1 0 0
1 1 1 1 1
1 1 1

Examples- Examples-
• If a = b and b = c then a = c. He goes to play a match if and only if it does not rain.
• If I will go to Australia, then I will earn more •Birds fly if and only if sky is clear.
money.

18/09/24 Module-2: Mathematical Logic 8

Ex-1 let,

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p : A circle is a conic,
q : √5 is a real number.
r : Exponential series is convergent.
Express the following compound propositions in words:

Dr. Vishal Patil

1. p ^ (~q) A circle is a conic and √5 is not a real number.

2. (~p) ˅ q A circle is not a conic or √5 is a real

number.
3. q → (~p) If √5 is a real number, then a circle is not a conic.
If a circle is not a conic then √5 is a real number and if √5 is a real number then a circle is
4. ~p ↔ q not a conic

18/09/24 Module-2: Mathematical Logic 9

Ex-2: Construct the truth tables for the following compound propositions:(i) p ^ (~q) (ii) (~p) ˅ q (iii) p → (~q)

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p q ~p ~q p ^ (~q) (~p) ˅ q p → (~q)
0 0 1 1 0 1 1
0 1 1 0 0 1 1
1 0 0 1 1 0 1
1 1 0 0 0 1 0

Dr. Vishal Patil

Ex-3: Let p and q be primitive statements for which the conditional p → q is false. Determine the truth values of the
following compound propositions:
(i) p ^ q (ii) (~p) ˅ q (iii) q → p (iv) (~q) → (~p)

Solution:
Since p → q is given to be 0, p has to be 1 and q has to be 0. Consequently, (~p) has to be 0 and (~q) has to be 1,
therefore:
i) Since p is 1 and q is 0
By conjunction: T T =T , else F
the truth value of p ^ q is 0 (False)

18/09/24 Module-2: Mathematical Logic 10

Ex-3: Let p and q be primitive statements for which the conditional p → q is false. Determine the truth values of the
following compound propositions:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

(i) p ^ q (ii) (~p) ˅ q (iii) q → p (iv) (~q) → (~p)
Solution: Conj:
ii) Since ~p is 0 and q is 0, then
∧ --- Both are T=T, Else F
By Disjunction; F F = F
Disjun:

Dr. Vishal Patil

hence the truth value of (~p) ˅ q is 0.
∨ -- Any one T=T, or Both
iii) Since q is 0 , p is 1
False=F
Then by conditional, F T = T,
𝐂𝐨𝐧𝐝:
so the truth value of q → p is 1.
iv) Since ~q is 1, ~p is 0 → --- T F – F else T
By conditional, T F= F Bi Cond
the truth value of (~q) → (~p) is 0. ↔ both same then T

18/09/24 Module-2: Mathematical Logic 11

Ex-4: Let p, q and r be propositions having truth values 0, 0 and 1 respectively. Find the truth values of the following
compound propositions
(1) (p ˅ q) ˅ r (2) (p ^ q) ^ r (3) (p ^ q) → r

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

(4) p → (q ^ r) (5) p ^ (r → q) (6) p → (q → (~r))
Solution:
Since p, q and r having truth values 0, 0 and 1, ~r is 0 Conj:
1) Since both p and q are 0,
∧ --- Both are T=T, Else F

Dr. Vishal Patil

By disjunction: “0 0 = 0”
=> (p ˅ q) is 0 Since r is 1, Disjun:
By disjunction: 0 1 = 1
=> (p ˅ q) ˅ r is 1 ∨ -- Any one T=T, or Both False=F

2) Since both p and q are 0, 𝐂𝐨𝐧𝐝:

By Conjunction: “0 0= 0” → --- T F – F else T
p ^ q is 0.
Since p ^ q is 0 and r is 1, Bi Cond
By Conjunction: 0 1= 0 ↔ both same then T
Thus, the truth value of (p ^ q) ^ r is 0.

18/09/24 Module-2: Mathematical Logic 12

Ex-4: Let p, q and r be propositions having truth values 0, 0 and 1 respectively. Find the truth values of the following
compound propositions
(1) (p ˅ q) ˅ r (2) (p ^ q) ^ r (3) (p ^ q) → r

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

(4) p → (q ^ r) (5) p ^ (r → q) (6) p → (q → (~r))
3) From (2) Since p ^ q is 0 and r is 1, 5) Since r is 1 and q is 0
By Conditional: “1 0 = 0, else 1” By conditional: “1 0 = 0”, else 0
Hence (p ^ q) → r gives “0 1 = 1” , (p ^ q) → r is 1. r → q gives “1 0” which is 0

Dr. Vishal Patil

Thus, the truth value of (p ^ q) → r is 1. Also, p is 0.
Hence, p ^ (r → q) gives 0 0
4) Since q is 0 and r is 1, By conjunction: “0 0 = 0”
By conjunction: 1 1=1, else 0 Thus, the truth value of p ^ (r → q) is 0.
Hence q ^ r gives 0 1 = 0. , q ^ r is 0
Also, p is 0. 6) Since r is 1, ~r is 0. Since q is 0,
Therefore, p → (q ^ r) gives 0 0 q → (~r) gives 1 0
By conditional “1 0 = 0 else 1” By conditional: 1 0 = 0
Therefore, q → (~r) is 0
Thus, the truth value of p → (q ^ r) is 1.
Also, p is 0. Therefore, p → (q → (~r)) gives 0 0
By conditional: 1 0 =0 else 1
Thus, the truth value of p → (q → (~r)) is 1.

18/09/24 Module-2: Mathematical Logic 13

Ex-5: Find the Possible truth values of p, q and r in the following cases:
(1) p → (q V r) is false
(2) p ∧ (q →r) is true

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Sol
1) p → (q V r) is false
Means , p → (q V r) is 0 Conj:
Which is only possible by conditional when “1 0 = 0”
i.e. p is 1 and (q V r) is 0
∧ --- Both are T=T, Else F

Dr. Vishal Patil

Þ (q V r) is 0 when by disjunction “0 0 = 0” Disjun:
Þ i.e. q is 0 and r is 0 ∨ -- Any one T=T, or Both
Þ hence the possible Truth values for p, q and r is 1,0,0
False=F
Sol
𝐂𝐨𝐧𝐝:
2) p ∧ (q →r) is true
(1) Means , p ∧ (q →r) is 1 → --- T F – F , else T
Which is only possible by conjunction when both are T = T p q r Bi Cond
i.e. “1 ∧ 1 = 1” ,
1 0 1 ↔ both same then T
i.e. p is 1, and (q →r) is 1
Þ And (q →r) is 1 when by conditional “0 → 1 = 1”, “1 → 1=1”, “0 → 0=1” 1 1 1
Þ i.e. q is 0,1,0 and r is 1,1,0 1 0 0
Þ hence the possible Truth values for p, q and r is
18/09/24 Module-2: Mathematical Logic 14
Ex-6: Construct the truth tables for the following compound propositions:
(i) (p ˅ q) ^ r (ii) p ˅ (q ^ r)

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p q r p˅q (p ˅ q) ^ r q^r p ˅ (q ^ r)
0 0 0 0 0 0 0

Dr. Vishal Patil

0 0 1 0 0 0 0
0 1 0 1 0 0 0
0 1 1 1 1 1 1
1 0 0 1 0 0 1
1 0 1 1 1 0 1
1 1 0 1 0 0 1
1 1 1 1 1 1 1

18/09/24 Module-2: Mathematical Logic 15

Ex-7: Construct the truth tables for the following compound propositions: (i) (p ^ q) (ii) q ^ ((~r) → p)

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p q r ~r (p ^ q) (p ^ q) → (~r) (~r) → p q ^ ((~r) → p)
0 0 0 1 0 1 0 0
0 0 1 0 0 1 1 0
0 1 0 1 0 1 0 0

Dr. Vishal Patil

0 1 1 0 0 1 1 1
1 0 0 1 0 1 1 0
1 0 1 0 0 1 1 0
1 1 0 1 1 1 1 1
1 1 1 0 1 0 1 1

18/09/24 Module-2: Mathematical Logic 16

Ex-8: If a proposition q has the truth value 1, determine all truth value assignments for the primitive propositions p, r
and s for which the truth value of the following compound proposition is 1.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

[q →{(~p ˅ r) ^ ~s}] ^ {~s → (~r ^ q)}

Solution: Since ~s has the truth value 1 and v has the truth value 1,
The given compound proposition is of the form u ^ v, the truth value of (~r ^ q) must be 1.

Dr. Vishal Patil

where Since q has the truth value 1, it follows that ~r must also
u ≡ q →{(~p ˅ r) ^ ~s} and v ≡ ~s → (~r ^ q) have the truth value 1;
Since the truth value of this compound proposition is 1, that is r must have the truth value 0.
the truth value of each of u and v is 1. Since (~p ˅ r) has the truth value 1 and r has the truth
Since q has the truth value 1, and u has the truth value 1 it value 0, it follows that ~p must have truth value 1; that is,
follows that the truth value of (~p ˅ r) ^ ~s must also be 1. p must have the truth value 0.
Consequently, ~p ˅ r has the truth value 1 and ~s has the Thus, all of p, r, s must have the truth value 0.
truth value 1.
Consequently, s hast the truth value 0.

18/09/24 Module-2: Mathematical Logic 17

Ex-9: Indicate how many rows are needed in the truth table for the compound proposition.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

(p ˅ ~q) ↔ {(~r ^ s) → t}, Find the truth value of this proposition if p and r are true and q, s, t are false.

Solution : The given compound proposition contains five primitives (components) p, q, r, s, t. Therefore, the number
of possible combinations of the truth values of these components which we have to consider 2! = 32. Hence, 32

Dr. Vishal Patil

rows are needed in the truth table for the given compound proposition.

Next, suppose that p and r are true and q, s, r are false. Then ~q is true and ~r is false. Since p is true and ~q is true, p
˅ ~q is true. On the other hand, since ~r is false and s is false, ~r ^ s is false. Also, r is false. Hence (~r ^ s) → t is true.

Since (p ˅ ~q) is true and (~r ^ s) → t is true, it follows that the truth value of the given proposition

(p ˅ ~q) ↔ {(~r ^ s) → t} is 1.

18/09/24 Module-2: Mathematical Logic 18

Tautology and Contradiction

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

An expression involving logical variables that is true in An expression involving logical variables that is false in all
all cases is a tautology. We use the number 1 to cases is a contradiction. We use the number 0 to
symbolize a tautology. symbolize a contradiction.

Dr. Vishal Patil

Ex-1: Prove that for any proposition p, the compound proposition p V ¬p is a tautology and the compound proposition
p ∧ ¬p is contradiction

p ¬p p V ¬p p ∧ ¬p
0 1 1 0 Conj: ∧ --- Both are T=T, Else F
1 0 1 0 Disjunct: ∨ --- Any one T=T, or Both False=F

18/09/24 Module-2: Mathematical Logic 19

Ex-2: Show that, for any propositions p and q, the compound proposition p →(p ∨q) is a tautology and the compound
proposition p ∧(¬p ∧ q) is a contradiction.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p q p∨q p →(p ∨q) ¬p ¬p ∧ q p ∧ (¬p ∧ q)
0 0 0 1 1 0 0
0 1 1 1 1 1 0
1 0 1 1 0 0 0

Dr. Vishal Patil

1 1 1 1 0 0 0

Ex-3: Show that, the truth values of following compound proposition are independent of the truth values of their
components: 1) {p ∧ (p → q)} →q 2) (p → q) ↔ (¬p V q)
p q p→q r = p ∧ (p → q) r→q
p q u= p → q ¬p r = ¬p V q u ↔ r
0 0 1 0 1
0 0 1 1 1 1
0 1 1 0 1
0 1 1 1 1 1
1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1
1 1 1 0 1 1

18/09/24 Module-2: Mathematical Logic 20

Ex-4: Prove that, for any proposition p, q, r the compound proposition {p → (q → r)} →{(p →q) →(p →r)} is a
tautology.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p q r p →q q→r p →r p → (q → r) (p →q) →(p →r) p → (q → r)} →{(p →q) →(p →r)}
0 0 0 1 1 1 1 1 1
𝐂𝐨𝐧𝐝:
0 0 1 1 1 1 1 1 1
→ --- T F – F ,
0 1 0 1 0 1 1 1 1
else T

Dr. Vishal Patil

0 1 1 1 1 1 1 1 1
1 0 0 0 1 0 1 1 1
1 0 1 0 1 1 1 1 1
1 1 0 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1
Homework problems:
1. Prove that, following are tautology.
i) p V [(¬p ∧ q)] ii) (p V q) V ¬p

2. Find the Possible truth values of p, q, r, s, t for which following are contradiction
i) [(p V q) ∧r] →(s V t)

18/09/24 Module-2: Mathematical Logic 21

Logical Equivalence and The Law of Logics

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Definition : Two Propositions u and v are said to be logically equivalent or simply equivalent whenever u and v have
same truth values, or equivalently, the biconditional u ↔ v is a tautology.

Then we write u⇔v. Here symbol ⇔ stands for “logically equivalent to”

Dr. Vishal Patil

When the proposition are not logically equivalent we write u<≠>v.

logically equivalent propositions are treated as identical propositions

Ex:1 let x be a specific positive integer. Consider the following propositions:

p: x is an odd integer q: x is not divisible by 2
Are p and q logically equivalent?

Sol: we note that p, q have the same truth values. As p and q are logically equivalent; i.e. p ⇔q

18/09/24 Module-2: Mathematical Logic 22

Ex:2 For any two proposition p, q, prove that (p →q) ⇔(¬p) V q

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Observe that p →q and (¬p) V q have same truth values for all possible truth values of p, q.

Therefore p →q ⇔ (¬p) V q

Dr. Vishal Patil

p q p →q ¬p (¬p) V q
0 0 1 1 1
0 1 1 1 1
1 0 0 0 0
1 1 1 0 1

18/09/24 Module-2: Mathematical Logic 23

Ex:3 Prove that for any three propositions p, q and r: [(pVq)→r] ⇔ [(p →r) ∧(q →r)]

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p q r pVq (pVq)→r p →r q →r (p →r) ∧(q →r)

0 0 0 0 1 1 1 1

0 0 1 0 1 1 1 1

Dr. Vishal Patil

0 1 0 1 0 1 0 0

0 1 1 1 1 1 1 1

1 0 0 1 0 0 1 0

1 0 1 1 1 1 1 1

1 1 0 1 0 0 0 0

1 1 1 1 1 1 1 1

18/09/24 Module-2: Mathematical Logic 24

Properties of Logical Equivalence. 6. Commutative Laws
(i) p ∨ q ≡ q ∨ p 10. Distributive Laws
(ii) p ∧ q ≡ q ∧ p . (i) p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r)

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

1. Law of double negation (ii) p ∧ ( q ∨ r ) ≡ ( p ∧ q ) ∨ ( p ∧ r)
(i) ~(~p) ≡ p
7. Absorption Laws
2. Idempotent Laws (i) p ∨ ( p ∧ q ) ≡ p 11. Equivalence of conditional :
(i) p ∨ p ≡ p (ii) p ∧ ( p ∨ q ) ≡ p (p → q) ⇔ (¬p V q)

Dr. Vishal Patil

(ii) p ∧ p ≡ p ¬[p → q] ⇔ p ∧ ¬q

3. Identity Laws 8. de Morgan’s Laws

(i) p ∨ F ≡ p (i) ¬ ( p ∨ q) ≡ ¬p ∧ ¬q
(ii) p ∧ T ≡ p (ii) ¬ ( p ∧ q) ≡ ¬ p ∨ ¬q Try
9. Associative Laws ¬p∧( ¬p∨ ¬q)
4. Inverse Laws
(i) p ∨ ~p ≡ T (i) p ∨ ( q ∨ r ) ≡ ( p ∨ q ) ∨ r
(ii) p ∧ ~p ≡ F (ii) p ∧ ( q ∧ r ) ≡ ( p ∧ q ) ∧ r .

5. Domination Laws The laws of double negation and idempotent law and
(i) p ∨ T ≡ T commutative laws are trivially true, other laws can be
(ii) p ∧ F ≡ F verified with the aid of truth tables

18/09/24 Module-2: Mathematical Logic 25

Proof of 8. de Morgan’s Laws p q p ∨ q ¬ ( p ∨ q) ¬p ¬q ¬ p ∧ ¬q
(i) ¬ ( p ∨ q) ≡ ¬p ∧ ¬q 0 0 0 1 1 1 1

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

0 1 1 0 0 0 0
1 0 1 0 0 1 0
Proof of 9. Distributive Laws 1 1 1 0 0 0 0
(i) p ∨ ( q ∧ r ) ≡ ( p ∨ q ) ∧ ( p ∨ r)

Dr. Vishal Patil

p q r q∧r p∨(q∧r) p∨q p∨r ( p ∨ q ) ∧ ( p ∨ r)
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1

18/09/24 Module-2: Mathematical Logic 26

Remarks: Table for Negation of compound proposition
Logically equivalence propositions are
treated as identical proposition. In view

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Proposition Negation
of laws of indicated above we have
following results ¬p p
1. ¬ (p ∨ q) ≡ ¬p ∧ ¬q p∧q ¬p v ¬q
2. ¬ (p ∧ q) ≡ ¬ p ∨ ¬q

Dr. Vishal Patil

3. ¬ (p ⟶ q) ≡ (p ∧ ¬q) pvq ¬p ∧ ¬q
4. (p ⟶ q) ≡ ¬ ¬ (p ⟶ q)
≡ ¬ (p ∧ ¬ q) p⟶q p ∧ ¬q
≡¬p∨q

Ex:1 let x be specified number. Write down the negation of the following conditional
“ if x is an integer, then x is a rational number.”

Sol: p: x is an integer; Negation of given statement reads

q: x is a rational number x is an integer and x is not a rational
the given condition is p ⟶ q where number.”
Hence according to the result
¬ (p ⟶ q) ≡ (p ∧ ¬q)
18/09/24 Module-2: Mathematical Logic 27
Ex:2 let x be specified number. Write down the negation of the following conditional
“ if x is not a real number, then it is not a rational number and not an irrational number.”

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Sol: p: x is not a real number
q: x is not a rational number
r : x is not a irrational number

Dr. Vishal Patil

The given proposition reads: p ⟶ (q ∧ r)

Therefore, negation of the proposition is

¬ [p ⟶ (q ∧ r)] ≡ ¬ [¬ p v (q ∧ r)] (Equivalence of conditional) p ⟶q ≡ (¬p ∨ q)
≡ [¬¬p∧¬(q ∧ r) (De Morgan's law)
≡ [p∧ (¬q v¬ r) (Double negation and De Morgan's law)
≡ [p∧ ¬q) v(P ∧ ¬ r) (Distributive)

Hence the negation of the given statement is:

“x is not a real number but a rational number or x is not a real number but it is an irrational number”

18/09/24 Module-2: Mathematical Logic 28

Ex-1: Prove following logical equivalence without using Truth table.
1. p ∨ [ p ∧ (p ∨ q)] ⇔ p

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

2. [p ∨ q ∨ (¬ p ∧ ¬q ∧ r)]⇔ (p ∨ q∨ r)

Solution:
1. p ∨ [ p ∧ (p ∨ q)] ⇔ p
Þ p ∨ [ p ∧ (p ∨ q)] ≡ p ∨ [(p ∧ p) ∨ (p ∧ q)] -------- Distributive law

Dr. Vishal Patil

Þ p ∨ [p∨ (p ∧ q)] -------- Idempotent Law
Þ p∨p -------- Absorption Law
Þp -------- Idempotent Law

2. [p ∨ q ∨ (¬ p ∧ ¬q ∧ r)] ⇔ (p ∨ q∨ r)
Þ [p ∨ q ∨ (¬ p ∧ ¬q ∧ r)] ≡ {p ∨ q ∨ [¬ (p ∨ q) ∧ r} de Morgan’s Laws
Þ ≡ {(p ∨ q) ∨ [¬ (p ∨ q) ∧ r} Associative Laws
Þ ≡ [(p ∨ q) ∨ ¬ (p ∨ q)] ∧ [(p ∨ q) ∨ r] Distributive law
Þ ≡ [T∧ [(p ∨ q) ∨ r]
Þ ≡ [(p ∨ q) ∨ r]

18/09/24 Module-2: Mathematical Logic 29

Ex-2: Prove following logical equivalence without using Truth table.
1. [(p ∨ q ) ∧ (p ∨ ¬q)] ∨ q ⇔ p ∨ q

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution: [(p ∨ q ) ∧ (p ∨ ¬q)] ∨ q ≡ [p ∨ (q ∧ p ) ∨ (q ∧ ¬q)] ∨ q Distributive
Þ ≡ [p ∨ (q ∧ ¬q)] ∨ q Commutative
Þ ≡ [p ∨ (F)] ∨ q inverse law
Þ ≡p∨q Absorption Law and identity law
(pVF)=p

Dr. Vishal Patil

Ex-3: Prove by using laws of logic. (p → q) ∧ [¬q ∧ (r ∨ ¬q)] ⇔ ¬(q ∨ p)

Solution: (p → q) ∧ [¬q ∧ (r ∨ ¬q)] ⇔ (p → q) ∧ [¬q ∧ (¬q ∨ r) (Commutative law)

⇔ (¬p ∨ q) ∧ ¬q ( Absorption law)
⇔ ¬q ∧ (¬p ∨ q) (Commutative law)
⇔ (¬q ∧ ¬p) ∨ (¬q ∧ q) (Distributive law)
⇔ (¬q ∧ ¬p) ∨ F (∵ u ∧ ¬u ⇔ F)
⇔ (¬q ∧ ¬p) (∵ u ∨ F ⇔ u)
⇔ ¬(q ∨ p) (De Morgan’s law)

18/09/24 Module-2: Mathematical Logic 30

Ex-4: Prove without using Truth table. [∼ p ∧ (∼ q ∧ r)] ∨ [(q ∧ r) ∨ (p ∧ r)] ⇔ r

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution [∼ p ∧ (∼ q ∧ r)] ∨ [(q ∧ r) ∨ (p ∧ r)]
⇔ [(∼ p∧ ∼ q) ∧ r)] ∨ [(r ∧ q) ∨ (r ∧ p)] (commutative)
⇔ [(∼ p∧ ∼ q) ∧ r)] ∨ [(r ∧ (q ∨ p)] (Distributive)
⇔ [(∼ (p ∨ q) ∧ r)] ∨ [(r ∧ (p ∨ q)] (De Morgan's and commutative)
⇔ [r∧ ∼ (p ∨ q)] ∨ [r ∧ (p ∨ q)] (commutative)
⇔ [r ∧ {∼ (p ∨ q) ∨ (p ∨ q)}] (Distributive)
⇔r∧T (∵∼ u ∨ u ⇔ T.

Dr. Vishal Patil

Here u : (p ∨ q) ⇔ r (∵ v ∧ T ⇔ v)

Ex-5: Prove that (p ∨ q) ∧ ((p ∧ (p ∧ q)) ⇔ (p ∧ q), by using rules of Logic.

Solution LHS ⇔ (p ∨ q) ∧ ((p ∧ p) ∧ q) (Associative rule)

⇔ (p ∨ q) ∧ (p ∧ q) (Idempotent law)
⇔ (p ∧ q) ∧ (p ∨ q) (commutative law)
⇔ p ∧ [q ∧ (p ∨ q)] (Associative law)
⇔ p ∧ [q ∧ (q ∨ p)] (commutative law)
⇔p∧q (Absorption law)

18/09/24 Module-2: Mathematical Logic 31

Ex-6: Prove the following using laws of logic : p → (q → r) ⇔ (p ∧ q) → r

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Solution p → (q → r) ⇔ p → (¬q ∨ r) (Equivalence of Conditional)
⇔ ¬p ∨ (¬q ∨ r) (Equivalence of Conditional)
⇔ (¬p ∨ ¬q) ∨ r (Associative law)
⇔ ¬(p ∧ q) ∨ r (De Morgan's law)
⇔ (p ∧ q) → r (Equivalence of Conditional

Dr. Vishal Patil

Ex-7: Simplify ¬ [¬{(p ∨ q) ∧ r} ∨ ¬q]

Solution ¬ [¬{(p ∨ q) ∧ r} ∨ ¬q] ≡ [¬¬{(p ∨ q) ∧ r} ∨ ¬¬q] using Dem organ Law

≡ {(p ∨ q) ∧ r)} ∧ q, using the Law of double negation
≡ {q ∧ (p ∨ q)} ∧ r, using Associative law
≡ {q ∧ (q ∨ p)} ∧ r, Commutative law
≡ q ∧ r, using Absorption law

18/09/24 Module-2: Mathematical Logic 32

Ex-8: Prove that (¬p ∧ q) ∨ ¬ (p ∨ q) ⇔ ¬p.
Solution : (¬p ∧ q) ∨ ¬(p ∨ q) ⇔ (¬p ∧ q) ∨ (¬p ∧ ¬q) (DeMorgan0 slaw)

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

⇔ ¬p ∧ (q ∨ ¬q) (Distributive law)
⇔ ¬p ∧ T0 (Inverse law)
⇔ ¬p (Identity law)
Ex-9: Prove that [(¬p ∨ ¬q) → (p ∧ q ∧ r) ⇔ p ∧ q

Dr. Vishal Patil

Solution: (¬p ∨ ¬q) → (p ∧ q ∧ r) ⇔ ¬(¬p ∨ ¬q) ∨ (p ∧ q ∧ r), (Equivalence of conditional)
⇔ (¬¬p ∨ ¬¬q) ∨ (p ∧ q ∧ r), (De Morgans law)
⇔ (p ∧ q) ∨ [(p ∧ q) ∧ r], Double Negation and Associative Law
⇔ p ∧ q, by Absorption Law
Ex-10: Establish the following logical equivalence. (p ∨ q) ∨ (¬p ∧ ¬q ∧ r) ⇔ (p ∨ q ∨ r)
Solution:
(p ∨ q) ∨ (¬p ∧ ¬q ∧ r) ⇔ (p ∨ q) ∨ (¬p ∧ ¬q) ∧ r, by Associative Law
⇔ (p ∨ q) ∨ [¬(p ∨ q) ∧ r] by De Morgan Law.
⇔ [(p ∨ q) ∨ ¬(p ∨ q)] ∧ [(p ∨ q) ∨ r] (Distributive)
⇔ T0 ∧ [(p ∨ q) ∨ r] (∵ u ∨ ¬u ⇔ T, Here, u : (p ∨ q))
⇔ (p ∨ q) ∨ r (∵ T ∧ v ⇔ v, Here v : (p ∨ q) ∨ r)

18/09/24 Module-2: Mathematical Logic 33

Ex-11: Prove that (p → r) ∨ (q → r) ≡ (p ∧ q) → r
Solution:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

(p → r) ∨ (q → r) ⇔ (¬p ∨ r) ∨ (¬q ∨ r) (Equivalence of conditional)
⇔ (¬p ∨ ¬q) ∨ (r ∨ r) (Associative )
⇔ (¬p ∨ ¬q) ∨ r (∵ r ∨ r ⇔ r)
⇔ ¬(p ∧ q) ∨ r ( De Morgan’s law )
⇔ (p ∧ q) → r (Equivalence of conditional

Dr. Vishal Patil

Ex-12: Using Laws of Logic Prove that ¬(p ∨ (¬p ∧ q)) and ¬p ∧ ¬q are logically equivalent.

Solution: ¬(p ∨ (¬p ∧ q)) ⇔ ¬p ∧ ¬(¬p ∧ q), (by the De Morgan law)
⇔ ¬p ∧ [¬(¬p) ∨ ¬q] (De Morgan law)
⇔ ¬p ∧ (p ∨ ¬q) (double negation law)
⇔ (¬p ∧ p) ∨ (¬p ∧ ¬q) (distributive law )
⇔ F0 ∨ (¬p ∧ ¬q) (∵ ¬p ∧ p ⇔ F0) ⇔ (¬p ∧ ¬q) (∵ F0 ∨ u ⇔ u)

18/09/24 Module-2: Mathematical Logic 34

Converse, Inverse and Contrapositive; Logical implication
Consider a conditional p → q then: • ¬p → ¬q is called the inverse of p → q

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

• q → p is called the converse of p → q • ¬q → ¬p is called the contrapositive of p → q.
For Ex, Let Truth Table for Converse, Inverse and Contrapositive
p: 2 is an integer
q: 9 is a multiple of 3. p q ¬p ¬q p→q q→p ¬p → ¬q ¬q → ¬p

Dr. Vishal Patil

Then, 0 0 1 1 1 1 1 1
p → q: if 2 is an integer, then 9 is a multiple of 3
0 1 1 0 1 0 0 1
Converse of this condition is 1 0 0 1 0 1 1 0
q → p: If 9 is a multiple of 3, then 2 is an integer 1 1 0 0 1 1 1 1

inverse of this condition is p → q and ¬q → ¬p have same truth values

¬p → ¬q: if 2 is not an integer, then 9 is not a Also q → p and ¬p → ¬q have same truth values in all possible
multiple of 3 situation. And we have following two important results:
1. p → q ⇔ ¬q → ¬p (Conditional and its contrapositive are
contrapositive of this condition is logically equivalent)
¬q → ¬p: If 9 is not a multiple of 3, then 2 is not an 2. q → p ⇔ ¬p → ¬q (Converse and the inverse are logically
integer equivalent)
18/09/24 Module-2: Mathematical Logic 35
Logical implication
let say, p: 6 is a multiple of 2 , q: 3 is a prime number, and we get

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

conditional p → q : if 6 is a multiple of 2, then 3 is a prime number

Because there is no
The Answer is NO consistency in the
p is true q is true statement p → q

Dr. Vishal Patil

(all tough it is logically true)
hence p → q is true But question is does this conditional p → q make any sense ?
Ex- consider the proposition p: 4 is a odd number, q: Bangalore is not in Karnataka

p is False q is False

But p → q is true: if 4 is odd no, then Bangalore is not in Karnataka is true

which is logically True but makes no sense!

18/09/24 Module-2: Mathematical Logic 36

We do not deal with conditional as stated above,
Our interest lies in conditional p → q where p and q are related in some way so that truth values of q depends upon
truth values of p or vice-versa. Such Condition are called hypothetical (implicative) statements

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

When hypothetical statement p → q is such that q is true whenever p is true, we say that p (logically) implies q.
Symbolically written as p => q

When hypothetical statement p → q is such that q is not necessarily true whenever p is true, we say that p (logically)

Dr. Vishal Patil

does not implies q. Symbolically written as p =/> q

18/09/24 Module-2: Mathematical Logic 37

Necessary and Sufficient condition

Necessary Condition:

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Suppose that p and q are statements. We say that the statement p is necessary for the statement q if q cannot be true
unless p is also true.
In other words, q requires p However it is possible for p to be true even if q is not true. We write p ⇐ q
For example, suppose p is the statement “you sit the exam” and q is the statement “you pass the exam”.
You cannot pass the exam without sitting the exam: sitting the exam is a necessary condition for passing the exam.

Dr. Vishal Patil

However sitting the exam does not mean that you will necessarily pass the exam.
Sufficient Condition
The statement p is said to be a sufficient condition for the statement q if knowing that p is true guarantees that q is
also true.
However knowing that q is true does not guarantee that p is true. That is, q needn't be a sufficient condition for p.
We write p⇒q
For example, suppose p is the statement “you achieve an overall grade of over 70% in all of the modules that you have
studied as part of your economics degree”
q is the statement “you get a first class degree in economics”.
Achieving an overall grade of over 70% in all of the modules that you have studied as part of your economics degree
means that you will get a first class in economics.
However, getting a first class degree in economics does not necessarily mean that you achieved a first in all of your
economics
18/09/24 modules. Module-2: Mathematical Logic 38
Necessary and Sufficient Condition
We say that the statement p is a necessary and sufficient condition for the

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

statement q when q is true if and only if p is also true.
That is, either p and q are both true, or they are both false.
Note that if p is necessary and sufficient for q, then q is necessary and sufficient for p. We write
p ⇔ q.

Dr. Vishal Patil

For example, the statement “I am a male sibling” is necessary and sufficient for the truth of the
statement “I am a brother”.
EX- let C denote some specific city, consider following propositions:
p: the city C is in Karnataka
q: the city C is in India
Þq is true does not guarantee that p is true,
ÞThat is, q needn't be a sufficient condition for p
Here p => q but q =/> p .
or we can say that p is sufficient but not necessary condition for q.

18/09/24 Module-2: Mathematical Logic 39

EX- consider a specific integer x and let :

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

p: the integer x is even
q: the integer x is divisible by 2
=> See that q is true if and only if p is also true
i.e. , either p and q are both true, or they are both false

Dr. Vishal Patil

We say that the statement A is a necessary and sufficient condition for the statement B
i.e., p => q and q => p or, p ⇔ q

Q-1- Write down the contrapositive of [p → (q → r)] with

a) Only one occurrence of the connective →
b) No occurrence of connective →

Sol: contrapositive of [p → (q → r)] is [~(q → r) →(~p)]

[~(q → r) →(~p)] ⇔ ~ [~(q → r)] V ~p
⇔ (q → r) V ~p ------(a)
⇔ (~q V r) V ~p -----(b)

18/09/24 Module-2: Mathematical Logic 40

Q-2Write inverse, converse and contrapositive of “If you do your homework, you will not be punished

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

Sol: The inverse of the given statement is (¬p → ¬q): “If you do not do your homework, you will be punished.”
Converse (q → p) : “If you will not be punished, then you do your homework”.
contrapositive (¬q → ¬p) : “If you will be punished, then you do not your homework”

Dr. Vishal Patil

Q-3 Replace the following statement with its contrapositive: ”If x and y are rational, then x + y is rational.”

Solution : p : x is rational,
q : y is rational,
r: x + y is rational.
This statement is in the form (p ∧ q) → r.
Its contrapositive statement is (¬q → ¬p) : ∼ r →∼ (p ∧ q)
Using De Morgans law, this can be written as ∼ r → (∼ p∨ ∼ q)
Hence contrapositive is the statement: ” If x + y is irrational, then either x is irrational or y is irrational

18/09/24 Module-2: Mathematical Logic 41

Q-4: Write converse, inverse and contrapositive of
(1) If a quadrilateral is a parallelogram, then its diagonals bisect each other.
(2) If a real number 𝑥 " is greater than zero, then x is not equal to zero.

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

(3) If a triangle is not isosceles, then it is not equilateral. (4) If two lines are parallel, then they are equidistant.
Solution :
(1) converse : If the diagonals of a quadrilateral bisect each other, then it is a parallelogram.
inverse : If a quadrilateral is not a parallelogram, then its diagonals do not bisect each other.

Dr. Vishal Patil

contrapositive : If the diagonals of a quadrilateral do not bisect each other, then it is not a
parallelogram.
(2) Converse : If a real number x is not equal to zero, then 𝑥 " is greater than zero.
inverse : If a real number 𝑥 " is not greater than zero, then x is equal to zero.
contrapositive : If a real number x is equal to zero, then 𝑥 " is not greater than zero.
(3) converse : If a triangle is not equilateral, then it is not isosceles.
inverse : If a triangle is isosceles, then it is equilateral.
contrapositive : If a triangle is equilateral, then it is isosceles

18/09/24 Module-2: Mathematical Logic 42

Q-5: Prove the Following :
i. [p ∧ (p →q)] => q

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

ii. [(p→q) ∧ ~q]=> ~p
iii. [(p V q) ∧~p]=> q
p q ¬p ¬q pVq p→q
0 0 1 1 0 1

Dr. Vishal Patil

0 1 1 0 1 1
1 0 0 1 1 0
1 1 0 0 1 1

i. From table we find that both p v q and p->q is true then q is true [p ∧ (p→q)] =>q
ii. From table we find that both p→q and ~q is true then ~p is true [(p→q) ∧ ~q]=> ~p
iii. From table we find that both p V q and ~p is true then q is true [(p V q) ∧~p]=> q

18/09/24 Module-2: Mathematical Logic 43

Q-6: Prove the Following :
i. [p ∧ (p→q) ∧ r] => [(p V q)→r]

Assistant Professor, JAIN (Deemed-to-be UNIVERSITY)

ii. {[p V (q V r)] ∧~q }=> p V r
p q r p V (q V r) ~q [p V (q V r)] ∧~q pVr
p q r p →q pVq (p V q) →r
0 0 0 0 1 0 0
0 0 0 1 0 1
0 0 1 1 0 1 0 0 1 1 1 1 1

Dr. Vishal Patil

0 1 0 1 1 0 0 1 0 1 0 0 0
0 1 1 1 1 1
0 1 1 1 0 0 1
1 0 0 0 1 0
1 0 0 1 1 1 1
1 0 1 0 1 1
1 1 0 1 1 0 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1 0 1 0 0 1

1 1 1 1 0 0 1
i. From table we find that both p, p->q and
r is true then [(p V q)→r is true: ii From table we find that {[p V (q V r)] ∧~q } is true then p V r is true
p ∧ (p→q) ∧ r] => [(p V q)→r]

18/09/24 Module-2: Mathematical Logic 44