BITS-Pilani
1st Semester 2023-24
MATH F213
BITS Pilani (Discrete Mathematics)
Pilani|Dubai|Goa|Hyderabad
Welcome to
MATH F213 : Discrete Mathematics
I-C : Pradipkumar H. Keskar
Handout is available at AUGSD website.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Brief Details
Text Book :
J. [Link] , A. Kandel, and T. P. Baker :
Discrete Mathematics for Computer Scientists & Mathematicians
PHI, 2e, 2008.
For a few topics we will use
R1. B. Kolman , R. C. Busby, S. C. Ross: Discrete Mathematical
Structures, Pearson , 4e, 2004
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Make up Policy
• MAKE-UP Policy: Prior permission needed for make-up of Test and
Comprehensive Examination. For those who missed either mid-sem
test or comprehensive exam due to genuine reason, a make-up test
will be provided at a time specified separately.
• No make-up will be provided for Quiz component.
• Procedures announced by AUGSD (on its website or through
mail) will be followed.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Why do we study Discrete Mathematics
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Why do we study Discrete Mathematics
The question you can ask either person is, "What path would the
other person tell me is the correct one?“
The answer will always be the wrong path to take, and you can
safely take the other path.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Why do we study Discrete Mathematics
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Section 1.4 (Self study)
Some methods of proof and problem solving strategies
This section informally dwells on some situations in which the
course will be useful. In particular, it discusses how this course will
be useful in developing strategies for problem solving.
You will benefit by going through the material yourself in leisurely
manner and reflecting on it.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani
Pilani | Dubai | Goa | Hyderabad
Section 1.5: Fundamentals of Logic
Today’s agenda
Propositions and Connectives
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Learning Objectives
•Why logic?
•Structure and basic ingredients of propositional Calculus
•To express given statements symbolically and reverse.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
What is logic for?
➢ Logic?
the study of correct reasoning
➢ Use of logic
▪ In mathematics?
to prove theorems
▪ In computer science?
to prove that programs do what they are supposed to do
▪ In electric circuits : for which positions (on/off) of switches
will the current be carried through
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Proposition or Statement
How do you define a proposition?
Which of the following is a proposition?
Two plus two equals four
Two plus two equals five
Two plus x equals four
A proposition is a declarative sentence which is
either true or false.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Which of the following is a proposition?
The sun revolves around the earth.
Y
Does the sun revolve around the earth?
X
Sun revolves around the earth in x days.
X
2+3=7
Y
Classroom is both hot and cold.
X
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Which of the following is a proposition?
42 is a perfect square.
Y
1+2+3+4
X
The sum of two squares
X
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Propositions
A proposition is a statement or a sentence that
satisfies both of the following
(a) (Law of excluded middle) it is either true or
false,
(b) (Law of contradiction) it can’t be both true
and false.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Which of the following is a proposition?
• What a beautiful evening!
• Get up and do your exercises.
• How are you?
Remark. Imperative (an instruction), interrogative
(ask a question) or exclamatory (expresses
sudden or strong emotions) sentences can’t be
treated as propositions.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Sentences in which they themselves are
talked about (self-referential sentences),
despite being declarative, are not
considered as propositions.
Example :
• All Greeks are liars.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Connectives
Let p, q, r are propositions such that
Let (p, q, r,)=(T, F, F), what can about
(p implies q) or (p and not r)
True
From a given collection of propositions, how can
you build other propositions? What could be
most common connectives
And, or, not
if … then
if and only if
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Logical Connectives
From a given collection of propositions, we can build other
propositions using connectives. The resulting proposition is
called a compound proposition.
Most common connectives:
Conjunction (and) Symbol
Disjunction (or) Symbol
Negation (It is not that ---) Symbol ~ (or )
Implication (If –then--) Symbol →
Double implication (-- if and only if --) Symbol
In negation, only one proposition is required to build a new one
(unary operation).
In other connectives, we require two propositions (binary
operation)
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
More on implication
In how many different ways p→q can be read ?
1) p implies q 2) If p then q
3) p only if q 4) p is sufficient for q
5) q is necessary for p 6) q if p
7) q follows from p 8) q provided p
9) q is a consequence of p 10) q whenever p
In p→q,
p is called a premise or hypothesis or antecedent.
q is called a conclusion or consequent.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Examples
If p is the proposition ‘2 is a prime number’ and q is the
proposition ‘2 is odd’ then
• pq is the proposition
‘2 is a prime number or 2 is odd’ which is true.
• pq is the proposition
‘2 is a prime number and 2 is odd’ which is false.
• p is the proposition
‘2 is not a prime number’ which is false.
• (p q) is the proposition
• ‘It is not that 2 is a prime number or 2 is not odd’ which is false.
• (The negation of “A or B” is “not(A) and not(B).)
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
More examples
Let p : Arjun is playing pool, q : Arjun is inside,
r : Arjun is doing his homework, s : Arjun is listening to music.
Translate the following sentences using p, q, r, s and logical
connectives ~, , .
• Arjun is inside doing his homework while listening to music, and
he is not playing pool.
• q r s (~p)
• Arjun is not listening to music, nor is he playing pool, neither is
he doing his homework.
• (~s) (~p) (~r) (Use parentheses judiciously)
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Ex 4(e), p 44
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Necessary and Sufficient conditions
If you eat too many sweets, you will gain weight.
A sufficient condition is
only one of the means to
achieve a particular outcome.
This means that there could
be other means to achieve the
outcome.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
More Examples (Cont.)
Restate the following as implication “If … then …”
• Sufficient condition that ABCD is a rectangle is that it is a
square.
ABCD is a square is sufficient for ABCD is a rectangle
• If ABCD is a square then it is a rectangle.
• A necessary condition that a given integer is divisible by 9 is
that it is divisible by 3.
It is divisible by 3 is necessary
• If a given integer is divisible by 9 then it is divisible by 3.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
Quiz-I Question
• Knowing truth values of p and q, how did we decide the truth or
falsities of compound proposition? We will come to rules soon.
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956
BITS Pilani, Deemed to be University under Section 3 of UGC Act, 1956