Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
Study Material
(Discrete Mathema cs (PCC-CSM405)
_____________________________________________________________________________________________
Table of Contents
Module III:
Propositional Logic
Sl no. Topic Page no.
1. Introduction 2
2. Proposition 2
3. Connec ves 2
4. Toutology 4
5. Contradic ons 5
6. Propositional Equivalences 6
7. Normal Forms 8
8. Practice question 20
9. References 24
Department of Mathema cs
Brainware University, Kolkata 1
,Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
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.
Proposi onal 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.
Defini on: A proposi on is a collec on of declara ve statements that has either a truth value "true” or a truth value
"false". A proposi onal consists of proposi onal variables and connec ves. We denote the proposi onal variables
by capital le ers (A, B, etc). The connec ves connect the proposi onal variables.
Truth value of a Proposi on:
(1) Let p: 4+5=10. p is proposi on which is false So p takes the Truth value F or 0.
(2) q: Every ac on has an equal and opposite reac on. This is a proposi on which is true. So, the truth value of q is
T or 1.
Note: The le ers p, q, … etc. are also known as proposi onal 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 (∧),
● Nega on/ 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 proposi onal 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 Mathema cs
Brainware University, Kolkata 2
, Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
2. AND (∧): The AND operation of two propositions A and B (written as A∧B) is true if both the
proposi onal 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. Nega on (¬/∼) − 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. Implica on / 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 Mathema cs
Brainware University, Kolkata 3
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
Study Material
(Discrete Mathema cs (PCC-CSM405)
_____________________________________________________________________________________________
Table of Contents
Module III:
Propositional Logic
Sl no. Topic Page no.
1. Introduction 2
2. Proposition 2
3. Connec ves 2
4. Toutology 4
5. Contradic ons 5
6. Propositional Equivalences 6
7. Normal Forms 8
8. Practice question 20
9. References 24
Department of Mathema cs
Brainware University, Kolkata 1
,Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
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.
Proposi onal 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.
Defini on: A proposi on is a collec on of declara ve statements that has either a truth value "true” or a truth value
"false". A proposi onal consists of proposi onal variables and connec ves. We denote the proposi onal variables
by capital le ers (A, B, etc). The connec ves connect the proposi onal variables.
Truth value of a Proposi on:
(1) Let p: 4+5=10. p is proposi on which is false So p takes the Truth value F or 0.
(2) q: Every ac on has an equal and opposite reac on. This is a proposi on which is true. So, the truth value of q is
T or 1.
Note: The le ers p, q, … etc. are also known as proposi onal 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 (∧),
● Nega on/ 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 proposi onal 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 Mathema cs
Brainware University, Kolkata 2
, Programme Name and Semester: B. Tech CSE (AIML_DS_General), 4th semester
Course Name (Course Code): Discrete Mathema cs (PCC-CSM405_ PCC-CSD405_ PCC-CSG405)
Academic Session: 2024-25
2. AND (∧): The AND operation of two propositions A and B (written as A∧B) is true if both the
proposi onal 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. Nega on (¬/∼) − 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. Implica on / 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 Mathema cs
Brainware University, Kolkata 3
