Programme Name and Semester: B.

Tech CSE (AIML_AIR_CYS), 3rd semester

Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Study Material
(Discrete Mathematics (BBS00008)
_____________________________________________________________________________________________

Table of Contents

Module III:
Propositional Logic

Sl no. Topic Page no.

1. Introduction 2
2. Proposition 2
3. Connectives 2
4. Toutology 4
5. Contradictions 5
6. Propositional Equivalences 6
7. Normal Forms 8
8. Practice question 20
9. References 24

Department of Mathematics
Brainware University, Kolkata 1
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Module 3 Propositional Logic

P ropositional logic, also known as sentential logic or statement logic, is a branch of classical logic that deals
with the logical relationships between propositions (statements) that are either true or false. In propositional
logic, the basic building blocks are simple propositions, and complex propositions are formed by combining
these using logical connectives.

Propositional Logic is concerned with statements to which the truth values, “true” and “false”, can be assigned. The
purpose is to analyses these statements either individually or in a composite manner.

Definition: A proposition is a collection of declarative statements that has either a truth value "true” or a truth value
"false". A propositional consists of propositional variables and connectives. We denote the propositional variables
by capital letters (A, B, etc). The connectives connect the propositional variables.

Truth value of a Proposition:

(1) Let p: 4+5=10. p is proposition which is false So p takes the Truth value F or 0.

(2) q: Every action has an equal and opposite reaction. This is a proposition which is true. So, the truth value of q is
T or 1.

Note: The letters p, q, … etc. are also known as propositional variables because these may take the two different
values T or F.

Connectives: In propositional logic generally, we use five connectives which are

● OR (∨), AND (∧),
● Negation/ NOT (¬/∽)
● Implication / if-then (→)
● If and only if (⟷)
1. OR (∨):The OR operation of two propositions A and B (written as A∨B) is true if at least any
of the propositional variable A or B is true.

The truth table is as follows –

A B A∨B

T T T

T F T

F T T

F F F

Department of Mathematics
Brainware University, Kolkata 2
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

2. AND (∧): The AND operation of two propositions A and B (written as A∧B) is true if both the
propositional variable A and B is true.

The truth table is as follows –

A B A∧B

T T T

T F F

F T F

F F F

3. Negation (¬/∼) − The negation of a proposition A (written as ¬A) is false when A is

true and is true when A is false.

The truth table is as follows −

A ∼A

T F

F T

4. Implication / if-then (→): An implication A→B is the proposition “if A, then B”. It is false
if A is true and B is false. The rest cases are true.

The truth table is as follows −

A B A→ B

T T T

T F F

Department of Mathematics
Brainware University, Kolkata 3
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

F T T

F F T

5. If and only if (↔): A↔B is bi-conditional logical connective which is true when p and q are same, i.e. both are
false or both are true.

The truth table is as follows −

A B A↔B

T T T

T F F

F T F

F F T

Tautologies
A Tautology is a formula which is always true for every value of its propositional variables.

Example − Prove [(A→B) ∧A] →B is a tautology

The truth table is as follows −

A B A→ B (A → B) ∧ [(A → B) ∧ A]
A →B

T T T T T

T F F F T

F T T F T

F F T F T

As we can see every value of [(A→B) ∧A] →B is "True", it is a tautology.

Contradictions
A Contradiction is a formula which is always false for every value of its propositional variables.
Department of Mathematics
Brainware University, Kolkata 4
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Example − Prove (A∨B) ∧[(∼A) ∧(∼B)] is a contradiction

The truth table is as follows −

A B A ∨ ∽A ∼B (∼ A) ∧ ( ∼ (A ∨ B) ∧ [( ∼ A) ∧
B B) (∼ B)]

T T T F F F F

T F T F T F F

F T T T F F F

F F F T T T F

As we can see every value of (A∨B) ∧[(∼A) ∧(∼B)] is “False”, it is a contradiction.

Contingency
A Contingency is a formula which has both some true and some false values for every value of its propositional
variables.

Example − Prove (A∨B) ∧(∼A) a contingency

The truth table is as follows −

A B A∨B ∼A (A ∨ B) ∧ (∼ A)

T T T F F

T F T F F

F T T T T

F F F T F

Department of Mathematics
Brainware University, Kolkata 5
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

As we can see every value of (A∨B)∧(∽A) has both “True” and “False”, it is a contingency.

Propositional Equivalences

Two statements X and Y are logically equivalent if any of the following two
conditions hold −
●The truth tables of each statement have the same truth values.
●The bi-conditional statement X↔Y is a tautology.
Example − Prove ∼(A∨B)and[(∽A)∧(∼B)] are equivalent

Testing by 1st method (Matching truth table)

A B A∨B ∼(A ∨ B) ∼A ∼B [(∼ A) ∧ (∼ B)]

T T T F F F F

T F T F F T F

F T T F T F F

F F F T T T T

Here, we can see the truth values of ∼(A∨B)and[(∼A)∧(∼B)] are same, hence the statements are
equivalent.
Testing by 2nd method (Bi-conditionality)
A B ∼ (A ∨ B ) [(∼A) ∧ (∼ B)] [∼ (A ∨ B)] ↔ [(∼ A ) ∧ (∼ B)]

T T F F T

T F F F T

F T F F T

F F T T T

As [∼ (A∨B)]↔[( ∼A)∧( ∼B)] is a tautology, the statements are equivalent.

Department of Mathematics
Brainware University, Kolkata 6
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Inverse, Converse, and Contra-positive

Implication / if-then (→) is also called a conditional statement. It has two parts −
● Hypothesis, p
● Conclusion, q
As mentioned earlier, it is denoted as p→q

Example of Conditional Statement − “If you do your homework, you will not be punished.”
Here, "you do your homework" is the hypothesis, p, and "you will not be punished" is
the conclusion, q.

Inverse − An inverse of the conditional statement is the negation of both the

hypothesis and the conclusion. If the statement is “If p, then q”, the inverse will be
“If not p, then not q”. Thus the inverse of p→q is ∽p→∽q

Example − The inverse of “If you do your homework, you will not be punished” is “If
you do not do your homework, you will be punished.”

Converse − The converse of the conditional statement is computed by interchanging

the hypothesis and the conclusion. If the statement is “If p, then q”, the converse
will be “If q, then p”. The converse of p→q is q→p.

Example − The converse of "If you do your homework, you will not be punished" is "If
you will not be punished, you do your homework”.

Contra-positive − The contra-positive of the conditional is computed by interchanging

the hypothesis and the conclusion of the inverse statement. If the statement is “If
p, then q”, the contra-positive will be “If not q, then not p”. The contra-positive
of p→q is ∽q→∽p

Example − The Contra-positive of " If you do your homework, you will not be
punished” is "If you are punished, you did not do your homework”.

● When we were looking at propositional logic operations, we defined several things using and/or/not.
o For example:

p⊕q ≡(p∨q)∧¬(p∧q)

p→q ,≡¬p∨q

p↔q≡(p→q)∧(q→p)≡(¬p∨q)∧(¬q∨p).

● We did that to help us understand the new symbols in terms of things we already knew.
o But it is also nice to have a standard definition of the operators we can use.
o When proving equivalences, it let us apply equivalences we already had that used and/or/not.

● We also had some equivalence rules that helped us rearrange propositions so we could get at the parts we
needed:

Department of Mathematics
Brainware University, Kolkata 7
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Name Equivalences

Double Negation ¬(¬p)≡p

p∨q≡q∨p
Commutative
p∧q≡q∧p

(p∨q)∨r≡p∨(q∨r)
Associative
(p∧q)∧r≡p∧(q∧r)

p∨(q∧r)≡(p∨q)∧(p∨r)
Distributive
p∧(q∨r)≡(p∧q)∨(p∧r)

¬(p∧q)≡¬p∨¬q
De Morgan's Law
¬(p∨q)≡¬p∧¬q

Normal Forms

● Remember that we also called “or” “disjunction” and “and” “conjunction”.

● A clause that contains only ∨ is called a disjunctive clause and only ∧ is called a conjunctive clause.
o Negation is allowed, but only directly on variables.
o p∨¬q∨r: a disjunctive clause
o ¬p∧q∧¬r: a conjunctive clause
o ¬p∧¬q∨r: neither
● If we put a bunch of disjunctive clauses together with ∧, it is called conjunctive normal form.
o For example: (p∨r)∧(¬q∨¬r)∧q is in conjunctive normal form.
● Similarly, putting conjunctive clauses together with ∨, it is called disjunctive normal form.
o For example: (p∧¬q∧r)∨(¬q∧¬r) is in disjunctive normal form.

● More examples:
o (p∧q∧¬r∧s)∨(¬q∧s)∨(p∧s) is in disjunctive normal form.
o (p∨q∨¬r∨s)∧(¬q∨s)∧¬s is in conjunctive normal form.
o (p∨r)∧(q∧(p∨¬q)) is not in a normal form.
o ¬p∨q∨r and ¬p∧q∧r are in both normal forms.

● It turns out we can turn any proposition into either normal form.
o We can use the definitions to get rid of →, ↔, and ⊕.
o Use DeMorgan's laws to move any ¬ in past parens, so they sit on the variables.
o Use double negation to get rid of any ¬¬ that showed up.
o Use the distributive rules to move things in/out of parens as we need to.

● For example, converting to conjunctive normal form:

¬((¬p→¬q)∧¬r)≡¬((¬¬p∨¬q)∧¬r) [definition]

≡¬((p∨¬q)∧¬r) [double negation]

Department of Mathematics
Brainware University, Kolkata 8
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

≡¬(p∨¬q)∨¬¬r [DeMorgan's]

≡¬(p∨¬q)∨r [double negation]

≡(¬p∧¬¬q)∨r [DeMorgan's]

≡(¬p∧q)∨r [double negation]

≡(¬p∨r)∧(q∨r) [distributive]

o It was actually in disjunctive normal form in the second-last step.

● Why would we want to convert to a normal form?

o May be easier to prove equivalence: to show A≡B, convert both to normal form, and then re-write
one proof backwards.
o Maybe we simplify a lot: if we end up with (p∨¬p∨⋯) terms, we know they are true.
o Proving theorems about all propositions: only have to handle boolean expressions in a normal form
and that covers every proposition.
o Shows that we can use circuitry to calculate any boolean expression with two layers of logic gates.

● Another example:

(p→q)→(¬r∧q)≡¬(p→q)∨(¬r∧q) [definition]

≡¬(¬p∨q)∨(¬r∧q) [definition]

≡(¬¬p∧¬q)∨(¬r∧q) [DeMorgan's]

≡(p∧¬q)∨(¬r∧q) [double negation]

o At this point, it's in DNF. Continuing…

(p→q)→(¬r∧q)≡(p∧¬q)∨(¬r∧q) [as above]

≡(p∨(¬r∧q))∧(¬q∨(¬r∧q)) [distributive]

≡(p∨(¬r∧q))∧(¬q∨¬r)∧(¬q∨q) [distributive]

≡(p∨(¬r∧q))∧(¬q∨¬r)∧T [negation]

≡(p∨(¬r∧q))∧(¬q∨¬r) [identity]

≡(p∨¬r)∧(p∨q)∧(¬q∨¬r [distributive]
Department of Mathematics
Brainware University, Kolkata 9
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Exercise: Find the truth table for 𝑃 ↔ 𝑄

Answer:

P Q P↔Q

T T T

T F F

F T F

F F T

Exercise: Construct a truth table for the formula ~𝑃 ∧ (𝑃 → 𝑄).

Answer:

P Q ~P P→ ~P ∧ (P →
Q Q)

T T F T F

T F F F F

F T T T T

F F T T T

Exercise: Construct a truth table for (P → Q) ∧ (Q → R).

Answer:

P Q R P→ Q→ (P → Q) ∧ (Q →
Q R R)

T T T T T T

T T F T F F

T F T F T F

T F F F T F

Department of Mathematics
Brainware University, Kolkata 10
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

F T T T T T

F T F T F F

F F T T T T

F F F T T T

Exercise: Show that (P → Q) ∨ (Q → P ) is a tautology.

Answer:

P Q P→Q Q→ (P → Q) ∨ (Q → P
Exercise: Verify the distributive Law
P ) 𝑝⋀(𝑞⋁𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
T T T T T Solution: We are using truth table to verify
the law
T F F T T
The truth table of 𝑝 ∧ (𝑞 ∨ 𝑟)
F T T F T

F F T T T

p q r q∨ 𝑟 𝑝 ∧ (𝑞 ∨ 𝑟)

T T T T T

T F T T T

F T T T F

F F T T F

F T F T F

F F F F F

T T F T T

T F F F F

The truth table of (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

p q r q∧ 𝑞 𝑝∧𝑟 (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

T T T T T T

T F T F T T

F T T F F F

F F T F F F

Department of Mathematics
Brainware University, Kolkata 11
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

F T F F F F

F F F F F F

T T F T F T

T F F F F F

From the above we see the two propositions 𝑝 ∧ (𝑞 ∨ 𝑟) and (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟) have same truth table.

Exercise: Verify the D’Morgan’s law∼ (𝑝 ∨ 𝑞) ≡ (∼ 𝑝) ∧ (∼ 𝑞)

Solution: We are using truth table to verify the law

The truth table of ∼ (𝑝 ∨ 𝑞)

p q 𝑝∨𝑞 ∼ (𝑝 ∨ 𝑞)

T T T F

F F F T

T F T F

F T T F

The truth table of (∼ 𝑝) ∧ (∼ 𝑞)

p q ∼𝑝 ∼𝑞 (∼ 𝑝) ∧ (
∼ 𝑞)

T T F F F

F F T T T

T F F T F

F T T F F

The above two table are identical.

Theorem: 𝑝 → 𝑞 ≡∼ 𝑝 ∨ 𝑞

Proof: Truth table for 𝑝 → 𝑞

p q 𝑝→𝑞

T T T

T F F

F T T

Department of Mathematics
Brainware University, Kolkata 12
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

F F T

Truth table for ∼ 𝑝 ∨ 𝑞

p q ∼𝑝 ∼𝑝∨𝑞

T T F T

T F F F

F T T T

F F T T

We see the truth tables of 𝑝 → 𝑞 and ∼ 𝑝 ∨ 𝑞 are same. Hence the theorem is proved.

Theorem: 𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞)⋀(𝑞 → 𝑝)

Proof:

Truth table for 𝑝 ↔ 𝑞

p q 𝑝↔𝑞

T T T

T F F

F T F

F F T

Truth table for (𝑝 → 𝑞)⋀(𝑞 → 𝑝)

p q 𝑝→𝑞 𝑞→𝑝 (𝑝 → 𝑞)⋀(𝑞

→ 𝑝)

T T T T T

T F F T F

F T T F F

Department of Mathematics
Brainware University, Kolkata 13
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

F F T T T

We see both the two truth tables are identical. So 𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞)⋀(𝑞 → 𝑝)

Example: Find the truth tables of the followings: (i) ∼ (𝑝 ∧∼ 𝑞) (ii) (𝑝 → 𝑞) ↔ (∼ 𝑞 →∼ 𝑝) (iii) [(p∧ 𝑞) ∨ (∼
𝑟)] ↔ 𝑝
Solution:

(i) Truth table for ∼ (𝑝 ∧∼ 𝑞)

p q ∼𝑞 𝑝 ∧∼ 𝑞 ∼ (𝑝 ∧∼ 𝑞)

T T F F T

T F T T F

F T F F T

F F T F T

(ii) Truth table for (𝑝 → 𝑞) ↔ (∼ 𝑞 →∼ 𝑝)

p q ∼𝑝 ∼𝑞 𝑝→𝑞 ∼𝑞→ (𝑝 → 𝑞) ↔ (∼ 𝑞 →∼ 𝑝)
∼𝑝

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

(iii) Truth table for [(p∧ 𝑞) ∨ (∼ 𝑟)] ↔ 𝑝

p q r p⋀𝑞 ∼𝑟 (p⋀𝑞) ∨ ∼ [(p∧ 𝑞) ∨ (∼ 𝑟)] ↔

𝑟 𝑝

T T T T F T T

T T F T T T T

T F T F F F F

F T T F F F T

T F F F T T T

Department of Mathematics
Brainware University, Kolkata 14
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

F T F F T T F

F F T F F F T

F F F F T T F

Exercise: Verify the distributive Law 𝑝⋀(𝑞⋁𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

Answer:

We are using truth table to verify the law

The truth table of 𝑝 ∧ (𝑞 ∨ 𝑟)

p q r q∨ 𝑟 𝑝 ∧ (𝑞 ∨ 𝑟)

T T T T T

T F T T T

F T T T F

F F T T F

F T F T F

F F F F F

T T F T T

T F F F F

The truth table of (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

p q r q∧ 𝑞 𝑝∧𝑟 (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)

T T T T T T

T F T F T T

F T T F F F

F F T F F F

F T F F F F

F F F F F F

T T F T F T

T F F F F F

From the above we see the two propositions 𝑝 ∧ (𝑞 ∨ 𝑟) and (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟) have same truth table.

Department of Mathematics
Brainware University, Kolkata 15
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Exercise: Verify the D’Morgan’s law∼ (𝑝 ∨ 𝑞) ≡ (∼ 𝑝) ∧ (∼ 𝑞).

Answer: We are using truth table to verify the law

The truth table of ∼ (𝑝 ∨ 𝑞)

p q 𝑝∨𝑞 ∼ (𝑝 ∨ 𝑞)

T T T F

F F F T

T F T F

F T T F

The truth table of (∼ 𝑝) ∧ (∼ 𝑞)

p q ∼𝑝 ∼𝑞 (∼ 𝑝) ∧ (
∼ 𝑞)

T T F F F

F F T T T

T F F T F

F T T F F

The above two table are identical.

Theorem1:𝑝 → 𝑞 ≡∼ 𝑝 ∨ 𝑞

Proof: Truth table for 𝑝 → 𝑞

p q 𝑝→𝑞

T T T

T F F

F T T

F F T

Truth table for ∼ 𝑝 ∨ 𝑞

p q ∼𝑝 ∼𝑝∨𝑞

T T F T

T F F F

F T T T

Department of Mathematics
Brainware University, Kolkata 16
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

F F T T

We see the truth tables of 𝑝 → 𝑞 and ∼ 𝑝 ∨ 𝑞 are same. Hence the theorem is proved.

Theorem 2: 𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞)⋀(𝑞 → 𝑝)

Proof: Truth table for 𝑝 ↔ 𝑞

p q 𝑝↔𝑞

T T T

T F F

F T F

F F T

Truth table for (𝑝 → 𝑞)⋀(𝑞 → 𝑝)

p q 𝑝→𝑞 𝑞→𝑝 (𝑝 → 𝑞)⋀(𝑞 → 𝑝)

T T T T T

T F F T F

F T T F F

F F T T T

We see both the two truth tables are identical. So 𝑝 ↔ 𝑞 ≡ (𝑝 → 𝑞)⋀(𝑞 → 𝑝)

Example: Find the truth tables of the followings: (i) ∼ (𝑝 ∧∼ 𝑞) (ii) (𝑝 → 𝑞) ↔ (∼ 𝑞 →∼ 𝑝) (iii) [(p∧ 𝑞) ∨ (∼
𝑟)] ↔ 𝑝
Solution:

(i)

p q ∼𝑞 𝑝 ∧∼ 𝑞 ∼ (𝑝 ∧∼ 𝑞)

T T F F T

T F T T F

F T F F T

F F T F T

Department of Mathematics
Brainware University, Kolkata 17
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

(ii)

p q ∼𝑝 ∼𝑞 𝑝→𝑞 ∼𝑞→ (𝑝 → 𝑞) ↔ (∼ 𝑞 →∼ 𝑝)
∼𝑝

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

(iii) Truth table for [(p∧ 𝑞) ∨ (∼ 𝑟)] ↔ 𝑝

p q r p⋀𝑞 ∼𝑟 (p⋀𝑞) ∨ ∼ [(p∧ 𝑞) ∨ (∼ 𝑟)] ↔

𝑟 𝑝

T T T T F T T

T T F T T T T

T F T F F F F

F T T F F F T

T F F F T T T

F T F F T T F

F F T F F F T

F F F F T T F

Department of Mathematics
Brainware University, Kolkata 18
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Questions for Practice.

A. MCQ Answer Type Questions:

Question
No.
1 Express ¬(𝑝 ∨ 𝑞) ∨ (𝑝 ∧ ¬𝑞) in simplest form

a.  p b. p

c.
q d.

2 Identify the negation of  xy , p( x, y)

a.
x y , p( x, y ) b. x y , p( x, y)
c. x y , p( x, y) d. none of these
3 Select the correct option. The statement [~p v (p → q)] → ~p is

a. Tautology b. Contingency
c. Contradiction d. None of these
4 Identify the contrapositive of " p → q " .

a. p→q b. q → p
q → p q → p
c. d.

5 Identify the truth value of the statement x2 = x holds for all real values of x.
a. T b. F
c. Neither T nor F d. none of these
If p:”Ashok is rich” and q:”Kamal is poor” then express the symbolic form of the statement
6
“Either Ashok or Kamal is rich”.

a.
pq b.
p  q

c. p  q d. ( p  q)
7 For the statement p and q, ( p  q) can be converted to

a.
p  q b. p  q
c. ( p  q) d. None of these

Department of Mathematics
Brainware University, Kolkata 19
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

8 p  q  ( p → q)  r
If , then illustrate the value of r

a. p→q b.  p

c.
q→ p d.
q
9 Select the correct option. A statement T is called tautology if
a. T is true for all possible values
b. T is false for all values of its variables
of its variables
c. T is true as well as false for few
d. None of these
possible values of its variables
10 Illustrate the negation of “All students live in dormitories”
a. All students do not live in
b. No student live in dormitories.
dormitories.
c. One student does not live in
d. Some students do not live in dormitories.
dormitories.
Let P: We should be honest., Q: We should be dedicated .,R: We should be overconfident.
11
Then ‘We should be honest or dedicated but not overconfident.’ is best expressed by
a. ~P V ~Q V R b. P ∧ ~Q ∧ R
c. P V Q ∧ R d. P V Q ∧ ~R
Let P: If Sahil bowls, Saurabh hits a century. Q: If Raju bowls , Sahil gets out on first ball.
12
Now if P is true and Q is false then identify the correct statement.
a. Raju bowled and Sahil got out
b. Raju did not bowled
on first ball
c. Sahil bowled and Saurabh hits
d. Sahil bowled and Saurabh got out
a century

13 “ ∀𝑥 ∈ ℝ such that x2 = 4 ” can be expressed as

a. If x is real number then x2 = 4 b. Some real numbers have square 4

c. Square of no real number is 4 d. None of these

Estimate the Truth value of the proposition “All the angles of an equilateral triangle are
14
equal”
a. True b. False
c. Not a proposition d. None of these

Department of Mathematics
Brainware University, Kolkata 20
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

Let P(x) states “x is wealthy” and Q(x) states “x is married”. Domain is “all men”, then
15
∃𝑥𝑃(𝑥) can be illustrated as
a. All men are wealthy b. At least one man is wealthy
c. No man is wealthy d. None of these
16 Select the correct option. 𝑝 ∨ (𝑝 ∧ 𝑞) ≡

a. p b. q

c. pq d. None of these

17 Inverse of “ p → q ” can be expressed as

a. p→q b. p → q

c.
p → q d.
q →  p

18 Converse of “ p → q ”can be expressed as

a. p → q b. q → p

c.
q →  p d.
q → p
19 Select the correct option. p → q is logically equivalent to
a. ¬p ∨ ¬q b. p ∨ ¬q
c. ¬p ∨ q d. ¬p ∧ q
Let 𝑈 = {0,1,2,3,4,5,6}, 𝑉 = {10,1,2,3,4,5,6} and 𝑊 = {1,2,3,4,5,6} and 𝑃(𝑥) be "𝑥 < 10".
20
Identify the set such that ∀𝑥𝑃(𝑥) has truth values F.
a. U b. V
c. W d. None of these
Syntax in propositional logic refers to
21

a. Meaning of statements b. Truth value of formulas

c. Structure and formation rules of
d. Interpretation of symbols
formulas
Semantics of a logical expression deals with
22

a. Symbol arrangement b. Valid inference rules

c. Truth assignment and meaning d. Grammar of logic

Department of Mathematics
Brainware University, Kolkata 21
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

A formula that is true for at least one interpretation is called

23

a. Unsatisfiable b. Valid
c. Satisfiable d. Contradiction
Logical connective representing conjunction is
24

a. ∨ b. →
c. ∧ d. ↔
Two propositions are logically equivalent when
25

a. Both are satisfiable b. Both have same truth table

c. Both are valid d. Both are contradictions
Idempotent law is expressed as
26

a. p ∧ T ≡ p b. p ∨ F ≡ p
c. p ∧ p ≡ p d. p ∨ ¬p ≡ T
27 Logical implication p→q is equivalent to
a. p ∧ q b. ¬p ∨ q
c. p ∨ q d. ¬p ∧ q
Universal quantifier is denoted by
28

a. ∃ b. ∀
c. ⇒ d. ↔
Existential quantifier is denoted by
29

a. ∀ b. ∧
c. ∃ d. ∨
Negation of ∀x P(x) is
30

a. ∀x ¬P(x) b. ¬∀x P(x)

c. ∃x ¬P(x) d. ∃x P(x)

Department of Mathematics
Brainware University, Kolkata 22
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

B. Short Answer Type Questions:

No. Question
1. Illustrate Tautology with an example.
2. Illustrate Contradiction with an example.
Show that the following compound proposition is a Tautology (using truth table)
3.
((𝑝 → 𝑞) ∧ (𝑞 → 𝑟)) → (𝑝 → 𝑟).
Show that the following compound proposition is a Tautology (using truth table) (𝑝 → (𝑞 →
4.
𝑝)).
5. Describe Logical equivalence with example.

If p: Today is Friday
q: It is raining
6.
r: It is hot
Cite the following Symbol
(i) ∽ 𝑞 → (𝑟 ⋀ 𝑝), (ii) (𝑝⋀ ∽ 𝑞) →∽ 𝑟, (𝑖𝑖𝑖) (𝑝 ∨ 𝑞) ⟷ 𝑟.
7. If p is true and q is false then cite the truth value of (𝑝 ∧ 𝑞) → (𝑝 ⋁ 𝑞).
8. Cite the truth table for the proposition: 𝑝 ↔ 𝑞 and 𝑝 → 𝑞.
Examine the following compound proposition is a Tautology (using truth table)
9.
((p→q)↔(∽q→∽p)).
Using truth table, examine the following compound proposition is a contradiction ¬(𝑞 →
10.
𝑟)˄𝑟 → (𝑝 → 𝑞).
Using truth table, examine the following compound proposition is a contradiction
11.
(p⋀q)⋀(∽p⋁q).
12. Explain the concepts of validity, satisfiability, and contradiction with examples.
13. Explain converse, inverse, and contrapositive of an implication.
14. Examine p→q and ∽p⋁q are logical equivalence.

C. Long Answer Type Questions:

No. Question
1. Use the truth tables method to deduce if (~𝑝 ∨ 𝑞) ∧ (𝑞 → ~𝑟 ∧ ~𝑝) ∧ (𝑝 ∨ 𝑟) is
always true or not.
2. Calculate the truth table for (𝑝⋀𝑞) ∨ ~𝑟 and (𝑝 ∨ 𝑞)⋀~𝑟.
3. Identify the truth table for (𝑝 ∨ 𝑞)⋀~𝑟.
4. Examine if (p∧q) → p⋁q is a tautology or not (without using truth table).
5. Let p: He is intelligent and q: He is tall be two propositions. Represent the following
statements in symbolic from using p and q:
(i) He is tall but not intelligent.
(ii) He is neither tall nor intelligent.
(iii) He is intelligent or he is tall.
(iv) It is not true that he is intelligent or tall.

Department of Mathematics
Brainware University, Kolkata 23
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

(v) It is not true that he is not tall or not intelligent.

6. If p: Madhu goes to cinema and q: Ram goes to cinema be two propositions then represent
the symbolic from of the statements:
(i) Both of Madhu and Ram goes to cinema.
(ii) At least one of Madhu and Ram goes to cinema.
(iii) Madhu does not go to cinema but Ram goes to cinema.
(iv) Either Madhu or Ram goes to cinema.
(v)If Ram goes to cinema then Madhu also goes to cinema.

7. Deduce that ((p  q)  (p  r)) → (q  r) is a tautology.

8. Deduce that (p → q) → (r → s) and (p → r) → (q → s) are not logically equivalent.

9. Let’s consider a propositional language where

A= “Angelo comes to the party”,
B= “Bruno comes to the party”,
C= “Carlo comes to the party”,
D= “Davide comes to the party”.

Transform the following sentences in propositional language:

i. “If Davide comes to the party then Bruno and Carlo come too”.
ii. “Carlo comes to the party only if Angelo and Bruno do not come”.
iii. “Davide comes to the party if and only if Carlo comes and
Angelo doesn’t come”.
iv. “If Davide comes to the party, then, if Carlo doesn’t come then
Angelo comes”.
v. “Carlo comes to the party provided that Davide doesn’t come,
but, if Davide comes, then Bruno doesn’t come”.
10. Deduce that p → q and ∼q → ∼p are logically equivalent by using truth table as well as
without using the truth table.
11 Apply logical equivalence laws to show that (𝑝˄(𝑞 → 𝑟)) → (¬𝑟 → ¬𝑝) is a tautology.

12
(i) Translate the statement
“All students in a class have solved at least one problem”
into predicate logic and obtain its negation using quantifier rules.

(ii) Transform the predicate formula

¬∃𝑥[𝑃(𝑥)˄∀𝑦𝑄(𝑥, 𝑦)]

into an equivalent formula containing no negation symbol outside atomic predicates.

Department of Mathematics
Brainware University, Kolkata 24
Programme Name and Semester: B. Tech CSE (AIML_AIR_CYS), 3rd semester
Course Name (Course Code): Discrete Mathematics (BBS00008)
Academic Session: 2025-26

13 (i) Examine validity of the argument in predicate logic:

∀ 𝑥 (𝑃(𝑥) → 𝑄(𝑥)), ∃ 𝑥 𝑃(𝑥) ⊢ ∃𝑥 𝑄(𝑥)

using formal logical reasoning.

(ii) Negate the quantified statement

∀𝑥 ∃ 𝑦(𝑥 < 𝑦 ˄ 𝑃(𝑦))

and simplify the result into standard logical form.

14 Using laws of logic, examine the proposition

(𝑝 ∨ 𝑞)˄(¬𝑝 ∨ 𝑟)˄(¬𝑞˅𝑟)

and prove that it is logically equivalent to

𝑟˅(𝑝˄𝑞)

Department of Mathematics
Brainware University, Kolkata 25