DISCRETE

MATHEMATICS
• INTRODUCTION
• PROPOSITIONAL LOGIC
 CDM 1101/CCS 2101 Course Outline

1. Logic and Proofs

2. Basic Set Theory
3. Relations and Functions
4. Sequences and Summations
5. Counting Techniques
6. Binomial Theorem
7. Mathematical Induction
M1: ACT1

1. What is Discrete Mathematics?

2. Why study Discrete Mathematics?

3. What are the applications of Discrete Mathematics?

4. What is a Proposition?

5. Enumerate the different logical operations and

describe each briefly.

6. References
What is Discrete Mathematics?

 Discrete Mathematics is the study of discrete

objects.
 An object is discrete if it is not continuous.
 In short, discrete objects is something that is
countable.
Examples of Discrete Objects
 People, students

 Chairs, tables, balls

 Integers

 Rational Numbers

 Finite Sets

 Functions from {1, 2, …, n}

 (x, y)  N such that y = x^3

Why do we have to study Discrete
Mathematics?

 Discrete Mathematics is a foundation course for

Mathematics and Computer Science.

 Many problems we face or encounter in our lives

involve discrete objects.
 SOME APPLICATIONS OF
DISCRETE MATHEMATICS
• Discrete Mathematics in Cryptography for creating security
passwords for computers and other electronic systems.-
Number Theory

• Discrete Mathematics in Relational Database for keeping

track of employees, clients or resources. - Set Theory

• Discrete Mathematics in Logistics for organizing the flow of

information, goods and services. - Graph Theory

• Discrete Mathematics in Computer Algorithms/Programming

because the algorithm rules are created through the laws
of discrete mathematics. - Proposition, Set Theory, etc
PROPOSITION
 Proposition
An assertion is a statement/sentence.

Kinds of Sentences
1. Declarative
2. Interrogative
3. Imperative
4. Exclamatory

Proposition
 An assertion which is either true or false but not both.
 A declarative statement.
 Two (2) TRUTH VALUES

• TRUE denoted by 1

• FALSE denoted by 0
 Examples of Proposition
 3 is a prime number.
 4+3=8
 The moon is made of cheese.
 x + 3 = 3x when x = -2
 All cows are brown.
 There is life in heaven.
 3*3=6
 The earth is further from the sun than Jupiter.
Examples of NOT a proposition
 x+y>7
 x=5
 Are you watching?
 Buy me a food, pls.
 Look out!
 How dangerous is the COVID delta variant?
 x + 3 = 2x
 Do you want to be vaccinated?
 Clean up your room!
 2x = 9 - x
 This statement is false. -> Liar Paradox
 Propositional Variables

 Denotes an arbitrary propositions with unspecified true

value.

 The usual variables used are p, q and r.

 Logical Connectives:

 p and q

 p or q

 not p
Examples:
p: Dan is 6’ tall.
q: There are 5 cows in the barn.
r: Diego is 5’5” tall.
s: Juanma is 4’ tall.
p and q: Dan is 6’ tall and there are 5 cows in the barn.
p or q: Dan is 6’ tall or there are 5 cows in the barn.
p and r and s:
Not a good translation: Dan is 6’ tall and Diego is 5’5” tall and
Juanma is 4’ tall.
A good translation: Dan, Diego and Juanma are 6’, 5’5” and 4’ tall,
respectively.
 LOGICAL OPERATORS
 Unary Operator negation: “not p”,  p.

 Binary Operators

 Conjunction: “p and q”, p q.

 Disjunction: “p or q”, p q

 Exclusive OR: “exactly one of p or q”, “p xor q”, p  q

“Either p or q”

 Implication: “if p then q”, p  q

 Biconditional: “p if and only if q”, p  q

Negation. Negation Operator, “not”, has symbol 
Example:
p: This book is interesting.

 p can be read as:

 This book is not interesting.
 This book is uninteresting.
 It is not the case that this book is interesting.

 Truth Table:

p p
0 1
1 0
Conjunction. Conjunction Operator, “and”, has symbol 
Example:
p: This book is interesting.
q: I am staying at home.

p  q: This book is interesting, and I am staying at home.

Truth Table:

p q pq
0 0 0
0 1 0
1 0 0
1 1 1
Disjunction. Disjunction Operator, “or”, has symbol 
Example:
p: This book is interesting.
q: I am staying at home.

p  q: This book is interesting, or I am staying at home.

Truth Table:

p q p q
0 0 0
0 1 1
1 0 1
1 1 1
Exclusive-OR. Exclusive-OR Operator, “xor”, has symbol 

Example:
p: This book is interesting.
q: I am staying at home.

Either p or q

p  q: Either this book is interesting, or I am staying at home.

Truth Table:

p q p q
0 0 0
0 1 1
1 0 1
1 1 0
Implication. Implication Operator, “if… then”, has symbol 

Example:
p: This book is interesting.
q: I am staying at home.

If p then q

p  q: If this book is interesting, then I am staying at home.

Truth Table:
p q pq
0 0 1
0 1 1
1 0 0
1 1 1
Implication. Implication Operator, “if… then”, has symbol 

Example:
p: This book is interesting.
q: I am staying at home.

p  q: If this book is interesting, then I am staying at home.

If p then q
Alternatives:
 p implies q
 If p, q
 p only if q
 p is a sufficient condition for q
 q if p
 q whenever p
 q is a necessary condition for p
 q provided p
Exercise 1:
Which of the following statements are equivalent to “If x is even,
then y is odd”? There may be more than one or none answer.
p implies q
pq
If p, q
p: x is even
p only if q
q: y is odd
p is a sufficient condition
for q

1. y is odd only if x is even. q if p

q whenever p
2. x is even is sufficient for y to be odd. q is a necessary condition
for p
3. x is even is necessary for y to be odd.
q provided p
4. If x is odd, then y is even.
5. x is even and y is even.
6. x is odd or y is odd.
Terminologies:

Implication p  q

 p is called the premise, hypothesis, or the antecedent.

 q is called the conclusion or subsequent.

 q  p is the converse of p  q.
  p   q is the inverse of p  q.
  q   p is the contrapositive of p  q.

 Example:
 Implication: If this book is interesting, then I am staying at home.

 Converse: If I am staying at home, then this book is interesting.

 Inverse: If this book is not interesting, then I am not staying at
home.
 Contrapositive: : If I am not staying at home, then this book is
not interesting.
Biconditional. Biconditional Operator, “if and only if”, has symbol 

Example:
p: This book is interesting.
q: I am staying at home.

p if and only if q

p  q: This book is interesting if and only if I am staying at home.

Truth Table:

p q pq
0 0 1
0 1 0
1 0 0
1 1 1
Biconditional. Biconditional Operator, “if and only if”, has symbol 

Example:
p: This book is interesting.
q: I am staying at home.

p  q: This book is interesting if and only if I am staying at home.

p if and only if q

Alternatives:
 p is equivalent to q
 p iff q
 p is a necessary and sufficient condition for q
Summary:

Binary Operators

p q p AND q p OR q Either p OR q If p then q p if and only if q

0 0

0 1

1 0

1 1
Terminologies:

 Tautology – a propositional form whose truth value is true

for all possible values of its propositional variables.

 Ex. p   p

 Contradiction or Absurdity – a propositional form which is

always false.

 Ex. p   p

 Contingency – a propositional form which is neither

tautology nor a contradiction.