Course Material

Textbook:
Discrete Mathematics for Computer
Science
Gary Haggard John Schlipf
Sue Whitesides

Other Reference:
Johnsonbaugh R,(2005).
Discrete Mathematics. Fifth Edition.
Singapore: Prentice Hall, Inc.

Kolman, B., Busby, R., Ross, S. (1996).

Discrete Mathematical Structures.
New Jersey: Prentice Hall, Inc.

D.S Malik and M.K.Sen. (2004).

Discrete Mathematical Structures : Theory & Application
United State: Thomson Course Technology.

James L. H. (2002).
Discrete Structures, Logic, and Computability.
Second Edition. John and Bartlett Pub. Co.
 Course Assessment
Pemberat Elemen
Perkara (Item) Domain
(Weightage) (Element)

Kognitif
Kuiz (Quiz) 5%
(Cognitive) Pengetahuan
Kognitif (Knowledge)
Ujian (Test) 20 %
(Cognitive)

Psikomotor Praktikal
Kerja Kursus Tutorial 10%
(Psychomotor) (Practical)
(Coursework)

Psikomotor Praktikal
15 %
Projek (Project) / (Psychomotor) (Practical)
Tugasan (Assignment)
Afektif KI
10 %
(Affective) (Soft-skills)

Peperiksaan Akhir Peperiksaan Akhir Kognitif Pengetahuan

40 %
(Final Examination) (Final Examination) (Cognitive) (Knowledge)

JUMLAH (TOTAL) 100 %

 What is discrete mathematics?

Logic: artificial intelligence (AI), database, circuit design

Number theory: cryptography, coding theory

Counting: probability, analysis of algorithm

Graph theory: computer network, data structures

logic, sets, functions, relations, etc

FUNDAMENTALS
OF
MATHEMATICAL LOGIC
 Logic and Proofs

How do computers think?

Logic: propositional logic, first order logic

Proof: induction, contradiction

Artificial intelligence, database, circuit, algorithms

Proposition

A declarative sentence or any meaningful

statement that is either True or False,
but not both.

Statements that are not propositions

include questions and commands.
Proposition

use lowercase letters, such as p, q, r, · · · , to represent

propositions notation.

p:2+2=3

P defined as the proposition 2+2 = 3.

The truth value of a proposition :

true, denoted by T, if it is a true statement

false, denoted by F, if it is a false statement.
Example 1.1

Which of the following are propositions? Give the truth

value of the propositions.

a. 5 - 11 = 7.

b. Dato’ Prof Ismail Bakar is a vice-chancellor of UTHM.

c. How do you do?

d. Look at the weather!

Example 1.2

Which of the following are propositions?

Give the truth value of the propositions.

a. You and me.

b. 2 is even number

c. Kuala Lumpur is the capital city of

Malaysia

d. How are you?

propositional variables
New propositions can be constructed from existing
propositions by using symbolic connectives or logical
operators.

∧ ::= AND ∨ ::= OR

Conjunction

Let p and q be propositions.

The conjunction of p and q,

denoted p Λ q,

is the proposition: p and q.

This proposition is defined to be true only

when both p and q are true and it is false
otherwise.
Disjunction

Let p and q be propositions.

The disjunction of p and q,

denoted p V q,

is the proposition: p or q.

The ’or’ is used in an inclusive way. This proposition

is false only when both p and q are false, otherwise
it is true.
 Example 1.3

Assume that

p:5<9

q:9<7

Construct the propositions p Λ q and p V q.

Solution.
The conjunction of the propositions p and q is the proposition
p Λ q : 5 < 9 and 9 < 7

The disjunction of the propositions p and q is the proposition

p V q : 5 < 9 or 9 < 7
 Example 1.4

Consider the following propositions

p : It is a monkey

q : It is a banana.

Construct the propositions p Λ q and p V q.

Solution.
The conjunction of the propositions p and q is the proposition
p Λ q : It is a monkey and it is a banana

The disjunction of the propositions p and q is the proposition

p V q : It is a monkey or it is a banana
Truth Table

A truth table displays the relationships

between the truth values of propositions

P Q P Q P Q P Q
T T T T T T
T F F T F T
F T F F T T
F F F F F F
Exclusive-Or ⊕
Let p and q be two propositions.

The exclusive or of p and q, denoted p ⊕ q,

is the proposition that is true when exactly one of
p and q is true and is false otherwise.
The truth table of the exclusive ’or’ is displayed below

p q p⊕q
T T F
T F T
F T T
F F F
 Example 1.5

a. Construct a truth table for (p⊕ q)⊕ r

p q r p⊕ q (p⊕ q) ⊕r
Solution.
T T T F T
T T F F F
T F T T F
T F F T T
F T T T F
F T F T T
F F T F T
F F F F F
 Example 1.5

b. Construct a truth table for (p⊕ p)

Solution. p p
T F
F F
Negation (Logical Operator)

The final operation on a proposition p that we

discuss is the negation of p.

The negation of p, denoted ~ p, is the proposition

not p.

The truth table of ~ p is displayed below

p ~p
T F
F T
Example 1.6

Find the negation of the proposition

p : -5 < x = 0

Solution

The negation of p is the proposition

~ p : x > 0 or x = -5
Example 1.7

Consider the following propositions:

p: UTHM is located in Parit Raja.

q: 2 + 5 = 7.
r: There is pollution in Parit Raja.

Question :

Construct the truth table of [~ (p Λ q)] V r.

solution

p q r pΛq ~ (p Λ q) [~ (p Λ q)] V r

T T T T F T
T T F T F F
T F T F T T
T F F F T T
F T T F T T
F T F F T T
F F T F T T
F F F F T T
Tautology

A compound proposition is called a

tautology if it is always true,
regardless of the truth values of the
basic propositions which comprise it.
 Example 1.8

a. Construct the truth table of the proposition

(p Λq) V (~ p V ~ q).

Determine if this proposition is a tautology.

p q ~p ~q (~ p V ~ q) (p Λ q) (p Λ q) V (~ p V ~ q)
T T F F F T T
T F F T T F T
F T T F T F T
F F T T T F T
Example 1.8

Determine if this proposition is a tautology.

b. Show that p V ~ p is a tautology.

Equivalent

Two propositions are equivalent if they have exactly

the same truth values under all circumstances.

We write p = q.

Example 1.9

a. Show that ~ (p V q) =~ p Λ ~ q
b. Show that ~ (p Λ q) =~ p V ~ q
c. Show that ~ (~ p) = p.
a. and b. are known as DeMorgan’s laws.

(Do it your self ! )

 Conditional
and
Biconditional Propositions
Implication

Let p and q be propositions.

The implication p→q is the proposition that

is false only when p is true and q is false;
otherwise it is true.

p is called the hypothesis and q is called the

conclusion.

The connective → is called the conditional

connective.
The implication of two propositions:
p→q
(if p then q)
is false
only when p is true and q is false.

The biconditional p q
(p if and only if q)
is true
only when the values of p and q are the same,

p⊕q
(either p or q but not both)
is true only
when the values of p and q are not the same.
Example 2.1

Construct the truth table of the implication p→ q.

Solution: The truth table is

p q p→q
T T T
T F F
F T T
F F T
Example 2.2

Show that p→ q ≡ ~ p V q.

Solution:

p q ~p p→q ~pVq
T T F T T
T F F F F
F T T T T
F F T T T
In terms of words the proposition p → q also reads:

(a)if p then q.

(b) p implies q.

(c) p is a sufficient condition for q.

(d) q is a necessary condition for p.

(e) p only if q
Example 2.3

Use the if-then form to rewrite the statement

”I become sleepy if I eat ‘nasi lemak’ in the morning.”

Solution:

If I ,eat ‘nasi lemak’ in the morning then I become

sleepy.

In propositional functions that involve the connectives

~, ∧ , ∨ and → the order of operations is that ~ is
performed first and → is performed last.
As a conclusion:

Understand the concept of fundamentals of math logic,

What is proposition and other terminology in logic,

Construct the compound propositions, and

display the truth table.

Thank you
 Assignment:

A CNF (Conjunctive Normal Form)

DNF (Disjunctive Normal Form)

Example: Convert [(p q) ⊕-p] → -q to a CNF and to a DNF.