L

BALJK

BASIC
LOGIC
DBM 20153 :
DISCRETE
MATHEMATICS

MARINI BINTI MOHD THAIB

SITI FARAH BINTI FADZIN@FADZIL

FAIZAH BINTI ABDUL MUIN

Editors
Charles Cheng Wuen King

Writers
Marini binti Mohd Thaib
Siti Farah binti Fadzin @ Fadzil
Faizah binti Abdul Muin

Designer
Marini binti Mohd Thaib

© Mathematics, Science and Computer Department, Politeknik Balik Pulau

1st Print 2024

All rights reserved. No part of this publication may be reproduced or transmitted in any
form or by any means, electronic or mechanical, including photocopy, recording, or any
information storage and retrieval system without permission in writing from the publisher
Politeknik Balik Pulau.

Published by:
Politeknik Balik Pulau
Pinang Nirai, Mukim 6
11000 Balik Pulau

DBM20153 – DISCRETE MATHEMATICS

BASIC LOGIC

■ ■
Per~::n.Jistakaan Negara Ma~ays~a

A caJtaJfogUie record for th~s book: ~s aJVaJ~iaJble

1

firo m 1the NaJffi.on 8IJ ~ Li' braJ ry ofi Ma iaJysi 8IJ

 ACKNOWLEDGEMENT
The publication of this interactive eBook involves the
cooperation of various parties. We gratefully thank the
Instructional and Digital Learning Division, JPPKK as well
as our organization, Politeknik Balik Pulau for giving us
the golden opportunity to do this wonderful project.
Secondly, we would like to thank the designer, illustrator
and also the panelists review who has helped us in
preparing this eBook. We would also like to express our
special thanks of gratitude to ourselves as the writers
of this eBook who have been pouring our best efforts in
completing this project within the time frame. Lastly, we
would like to say a thousand thanks to anyone who has
helped us directly or indirectly in the production of this
interactive eBook. Hopefully this eBook can benefit
anyone who uses it, especially for our beloved students.
 ABSTRACT
This eBook aims to enhance students' understanding of the topic of

Boolean Algebra in Discrete Mathematics. The topic covered about

Boolean Functions, Logic Gates and Karnaugh Map. Explanations of

how to solve each tutorial question are shown in an interactive

way. The difference between this eBook and other discrete math

books is that its detailed explanations meant to serve as a

reference to students as they master the concepts learned in the

topic. In addition, every effort has been made to make this eBook

sufficient for students' self study.

TABLE OF CONTENT

EXPLAIN PROPOSITIONAL 1
LOGIC

LOGICAL CONNECTIVES 5

CONSTRUCT TRUTH
15
TABLE

LOGICAL EQUIVALENCE 19

PREDICATE LOGIC 24

QUANTIFIERS 26
 EXPLAIN PROPOSITIONAL LOGIC
Explain ·Compound proposition is
Compound the combination of two or
more propositions.
Proposition
·Proposition is a statement
·A true statement
that is either true or false, but
has truth value T
it cannot be both.
or 1, while a false
statement has
·The truth or falsity of a
statement is called its truth truth value F or 0.
value.

·Propositions can be represented by

using variables such as A, B, C, P, Q, R,
etc.

·Statements which are questions,

commands, expressions or
opinions are not propositions.

1
 EXAMPLE 1
Identify whether the following sentences
are propositions or not. For a proposition,
find its truth value and give a reason if it is
not a proposition.

a Perak is the biggest state Answer : Proposition

in Peninsular Malaysia. (True)

b 7x - 5 4 .I
1
Answer : Proposition
(False)

c Where is your hometown? Answer : Not proposition

because it is a question.
Answer : Not proposition
d Fried chicken is the most because cannot determine
delicous food in the world. the truth value since not
everyone likes fried chicken.

e Do not throw trash out of Answer : Not proposition

your vehicle. because it is a command.

f E Answer : Proposition
(True)

g Don’t miss me too much! Answer : Not proposition

because it is an expression.

h Hedgehog is an omnivore. Answer : Proposition (True)

2
 EXAMPLE 2
Identify whether the following sentences
are propositions or not. For a proposition,
find its truth value and give a reason if it is
not a proposition.

a The rainbow has seven colors. Answer : Proposition (True)

Answer : Not proposition

b Please ask if you do not understand. because it is a
command.

c 8 is a factor of 28. Answer : Proposition (False)

d 739 > 709 Answer : Proposition (True)

e There is life on mars. Answer : Not proposition because

the truth value is unpredictable

f Tun Hussein Onn is the third Prime Answer : Proposition

Minister of Malaysia. (True)

g I love you! Answer : Not proposition because it is an

expression.
Answer : Not proposition because
h These sentences are true.
the truth value is unpredictable.
Answer : Not proposition
i How will you prove this argument? because it is a question.

j Get me a glass of iced americano. Answer : Not proposition

because it is a command.

3
 Identify whether the following sentences
are propositions or not. For a proposition,
find its truth value and give a reason if it is
not a proposition.

k Cristiano Ronaldo Answer : Not proposition because it is just

a name.

Answer :Proposition
l Crust is the earth’s outermost surface.
(True)

m Answer : Not proposition because x is

unknown.

n 32514 is an odd number. Answer : Proposition (True)

o Answer : Proposition (False)

p What is your name? Answer : Not proposition because it is

a question.

Answer : Proposition
q Kuala Lumpur is the capital city of
(False)
Singapore

r Human has 5 eyes Answer : Proposition (False)

Answer : Not proposition because it

s What a beautiful flower!
is an expression.

t Shut up! Answer : Not proposition because it is a command.

4
 LOGICAL CONNECTIVES
Negation
Read as “not P”.
Turn a true proposition
into false or a false
proposition into true.
Symbol:

Conjunction Disjunction
Read as “not P”. Read as “P and Q” or “P
Turn a true proposition but Q”.
into false or a false The proposition is TRUE
proposition into true. only when p and q are
Symbol: both true.
Symbol:

Conditional Statement (If … Biconditional Statement (if and

then … , ) only if, )
Read as “If P then Q”. Read as “P if and only if Q”.
The proposition is TRUE only when P The proposition is TRUE
and Q are both true and P is false when P and Q have the
(no matter what truth value Q has). same truth values.
Symbol : Symbol:

5
 Conditional Statement
also, can be read as:
1. If P then Q 8. P implies Q
2. If P, Q 9. P only if Q
3. P is sufficient for Q 10. A sufficient condition for Q is P
4. Q if P 11. Q whenever P
5. Q when P 12. Q is necessary for P
6. A necessary condition for P is Q 13. Q follows from P
7. Q unless ~P

P is called hypothesis and

Q is called the conclusion.

When the hypothesis and

conclusion are identified
in a conditional
statement, three other
statements can be
derived:
Converse

Let
Inverse

Contrapositive

6
 WRITE PROPOSITION
LOGIC IN ENGLISH
EXAMPLE 3
Let P: I am rich; and Q: I am happy.
Write the following compound
statements in symbolic forms.

a
I am rich and happy Answer :

b I am poor but happy Answer :

c I am not rich or not happy Answer :

d I am happy if and
Answer :
only if I am not poor

e It is not true that if I am poor, Answer :

then I am not happy

f I am rich if I am happy Answer :

7
 EXAMPLE 4
Let P : Men are immortal.
Q : Men are safe from tragedy.
R : Men are created by God
Express each of the following quantified formulas in
English sentences.

a Answer : Men are immortal or men

are safe from tragedy

Answer : If men are immortal, then

b men are safe from tragedy and men
are created by God

c Answer : If men are not safe from

tragedy, then men are not immortal

Answer : If men are not immortal,

d then men are not safe from
tragedy or men are not created
by God

e Answer : Men are safe from

tragedy and created by God if
and only if men are immortal

8
 EXAMPLE 5
Given P, Q and R are the propositions:
P : Amira will study Discrete
Mathematics.
Q : Amira will go to the beach.
R : Amira is in a good mood.
Write the following compound statements in
symbolic forms.

a Amira will not go to Answer :

the beach and she
will study the Discrete
Mathematics.

Amira does not study ~Q∧P

Discrete Mathematics Answer :

b
if and only if Amira is
not in a good mood.

Amira will go to the

C
beach if she is in a
good mood.
Answer :

9
 EXAMPLE 6
For each of the symbolic expression, write the
corresponding (compound) statement base
on the given primary statements.
P : A circle is a conic.
Q : is an irrational number.
R : Exponential series is convergent.

Answer : A circle is a
a conic and is not an
irrational number.

Answer : A circle is not a b

conic or is an irrational
number.

Answer : If a circle is a conic,

then is an irrational number
or exponential series is
convergent.

d Answer : A circle is not a conic if and only

if is an irrational number and
exponential series is not convergent.
10
 Example 7: Write the converse, inverse and
contrapositive statements for each of the
following conditional statement
If lines m and n are parallel,
If it is sunny, then I will then lines m and n do not
play baseball intersect
Answer:
Answer: Converse :
Converse : If lines m and n do not intersect, then
If I will play baseball, then it is sunny. lines m and n are parallel.
Inverse : Inverse :
If it is not sunny, then I will not play If lines m and n are not parallel, then lines
baseball. m and n will intersect.
Contrapositive : Contrapositive :
If I will not play baseball, then it is not If lines m and n are intersecting, then lines
sunny. and n are not parallel.

If Aaron did his

homework, then he will If x + 5 = 13, then x = 8
pass this test
Answer: Answer:
Converse : Converse :
If Aaron pass this test, then he did his If x = 8, then x + 5 = 13.
homework. Inverse :
Inverse : If x + 5 ≠ 13, then x ≠ 8.
If Aaron did not do his homework, Contrapositive :
then he will fail this test. If x ≠ 8, then x + 5 ≠ 13.
Contrapositive :
If Aaron did not pass this test, then he
did not do his homework.

If an angle not measure 90°, then it is not a

right angle
Answer:
Converse : If it is not a right angle, then an angle will not measure 90°.
Inverse : If an angle measures 90°, then it is a right angle.
Contrapositive : If it is a right angle, then an angle will measure 90°.
11
 EXERCISE 1
1. Which of these sentences are propositions? What are the truth values of those that are propositions?
a. Ipoh is the capital city of Selangor. g. Do not pass go.
b. Shah Alam is the capital city of Selangor. h. What time is it?
c. 2 + 3 = 5 i. 4 + x = 5
d. 5 + 7 = 10 j. The moon is made of green cheese.
e. x + 2 = 11 k. 2n > 100
f. Answer this question.

2. What is the negation of each of these propositions?

a. Today is Thursday.
b. There is no pollution in Kuala Lumpur.
c. 2 + 1 = 3
d. The weather in Malaysia is hot and sunny.

4. Let p and q be the propositions

p: It is below freezing.
q: It is snowing.

Write these propositions using p and q and logical connectives.

a. It is below freezing and snowing.
b. It is below freezing and but not snowing.
c. It is not below freezing and it is not snowing.
d. It is either snowing or below freezing (or both).
e. If it is below freezing, it is also snowing.
f. It is either below freezing or it is snowing, but it is not snowing if it is below freezing.
g. That it is below freezing is necessary and sufficient for it to be snowing.

12
 5. Let p and q be the propositions
p: You drive over 65 miles per hour.
q: You get a speeding ticket.

Write these propositions using p and q and logical connectives.

a.You do not drive over 65 miles per hour.
b.You drive over 65 miles per hour, but you do not get a speeding ticket.
c.You will get a speeding ticket if you drive over 65 miles per hour.
d.If you do not drive over 65 miles per hour, then you will not get a speeding ticket.
e.Driving over 65 miles per hour is sufficient for getting a speeding ticket.
f.You get a speeding ticket, but you do not drive over 65 miles per hour.
g.Whenever you get a speeding ticket, you are driving over 65 miles per hour.

7. Let p, q and r be the propositions

p: You get an A on the final exam.
q: You do every exercise in this book.
r: You get an A in this class.

Write these propositions using p, q and r and logical connectives.

a. You get an A in this class, but you do not do every exercise in this book.
b. You get an A on the final, you do every exercise in this book, and you get an A in this class.
c. To get an A in this class, it is necessary for you to get an A on the final.
d. You get an A on the final, but you don’t do every exercise in this book, nevertheless, you get an A in this
class.
e. Getting an A on the final and doing every exercise in this book is sufficient for getting an A in this class.
f. You will get an A in this class if and only if you either do every exercise in this book or you get an A on the
final.

8. Write the converse, inverse and contrapositive statements for each of the following conditional statement.
a. If two triangles are not similar, then their corresponding angles are not congruent.
b. If Ammara works hard, then she succeeds.
c. If the waves are small, I do not go surfing.
d. If x is an even integer, then (x + 1) is an odd integer.
e. If I am tall, then I will bump my head.

13
MORE NOTES
AND EXERCISES VIA ONLINE

Explore these links to enhance your

knowledge and understanding :

VIDEO
https://www.youtube.com/watch?v=hUMAyRcPZmo

https://www.youtube.com/watch?v=2UB9hMSAcl4

ONLINE ASSESSMENT
https://quizizz.com/join?gc=98555637

https://quizizz.com/join?gc=73879342
hello@reallygreatsite.com 14
www.reallygreatsite.com
 Construct Truth Table

Tautology is a compound
proposition that is
Truth table is used to “always true”.
show the truth value of
the compound
proposition.
Contradiction is a
compound
The truth value of proposition that is
a compound “always false”.
proposition built
with logical
connective is
depends on the
truth or falsify of
its components. ·Contingency is
a compound
proposition that
is “neither
·Recommended sequence of contradiction
logical connectives in truth table: nor tautology”.

15
 EXAMPLE 8

Construct the truth table for each of the

following compound propositions and
determine whether it is tautology,
contradiction or contingency

16
 EXAMPLE 9
Construct the truth table for each of the following
compound propositions and determine whether it is
tautology, contradiction or contingency

17
 EXAMPLE 10
Construct the truth table for each of the following
compound propositions and determine whether it is
tautology, contradiction or contingency

18
 Logical
Equivalence
1 Logical equivalence is one
of the features of
propositional logic.

Two propositions are said to be

2 logically equivalent if and only if both
columns in the truth table are identical
to each other.

3 The notation or denotes that

P and Q are logically equivalent.

19
 EXAMPLE 11
a) Show that and
are logically equivalent

b) Show that

20
 EXAMPLE 12
Construct the truth table for each of the following
compound propositions and determine whether it is
logically equivalent or not.

21
EXERCISE 2

22
MORE NOTES
AND EXERCISES VIA ONLINE

Explore these links to enhance your

knowledge and understanding :

VIDEO
https://www.youtube.com/watch?v=XwC2L_zu-DM

ONLINE ASSESSMENT
https://quizizz.com/join?gc=83736291
https://quizizz.com/join?gc=73441462
hello@reallygreatsite.com 23
www.reallygreatsite.com
 PREDICATE LOGIC
PREDICATE LOGIC

01.
COMPOUND STATEMENT IS
THE COMBINATION OF
STATEMENTS BY USING
LOGICAL CONNECTIVES.

02.
PREDICATE IS AN EXPRESSION OR A VERB
PHRASE TEMPLATE THAT DESCRIBES A
PROPERTY OF OBJECTS OR A RELATIONSHIP
AMONG OBJECTS REPRESENTED BY ONE OR
MORE VARIABLES.

03. FOR
EXAMPLES:

24
 EXAMPLE 13
State the expression of predicate in
the following statements:

a Answer :
The car, Karim is
Blue (car)
driving is blue.
Blue (sky)
The sky is blue. Blue (cover of
The cover of this book)
book is blue. ∴ B (x)

b Ali gives the book to Answer :

Mariam. Gives (Ali, book,
Mariam)
Karim gives a loaf of
Gives (Karim,
bread to Abu. bread, Abu)
Aminah gives a Gives (Aminah,
lecture to Mariam. lecture, Mariam)
∴ G (x, y, z)
25
 QUANTIFIERS
01
·The variable of predicates is
quantified by quantifiers.

·Predicates are used alongside quantifiers

to express the extent to which a 02
predicate is true over a range of
elements.

03 ·There are two types of quantifier:

·There are two types of quantifier:

26
 01
·Statements which
contain quantifier
words such as “all”,
“none”, “some” or
“there exists” are
called quantified 02
statements. ·When reading
quantified
statements in
English, read
them from left
to right.

·For example, let the universe of discourse be the set of

cars and the predicate F (x, y) denote as “x is faster
than y”.

27
 EXAMPLE 14
Let E (x) = x is even and G (x, y) = x > y as the
universe of discourse be the set of natural
numbers. Write the following predicate logic
to English sentences and vice versa.

a Answer : Every number is greater

than some numbers.

b Answer :Some numbers are

greater than every number.

c Answer : Some numbers are not even.

d Answer : Every number is even.

e 6 is an even number. Answer : E(6)

Answer :
f Some numbers are greater than some
numbers.

g Some numbers are greater than Answer :

10.
28
 EXAMPLE 15
Let T (x, y) = x is taller than y as the universe
of discourse be the set of people. Write the
following predicate logic to English
sentences and vice versa.

a Answer : Everyone is taller than

someone.

b Answer : Someone is taller

than everyone.

c Answer : Someone is not taller than

everyone.

d Answer : Not everyone is taller than

someone.

Answer :
e Someone is not taller than someone.

f Alia is taller than Amin. Answer : T(Alia, Amin)

g Someone is taller than Rashid. Answer :

29
 EXAMPLE 16
1.Let H (x) be the statement “x is happy”, where
the universe of discourse for x is the set of
people. Express each of the following
quantifications in English.

a Answer : Someone is
happy.

Answer : Not everyone is b

not happy.

Answer : Someone is not

happy.

d
Answer : Everyone is not happy.

30
 1.Let P (x) be the statement “x likes reading”
and Q (x) be the predicate “x can speak French”.
The domain for both predicates are lecturers in
PBU. Use quantifiers and logical connectives to
express each of the following statements.

Answer :
a Some lecturers in PBU like
reading and can speak French.
b Every lecturer in PBU likes reading if Answer :
they cannot speak French
C Someone can speak French. Answer :

Everyone likes reading or can Answer :

d
speak French.

e If everyone likes to read, then

someone can speak French.
Answer :

f Sabrina likes to read.

Answer : P (Sabrina)

g Ali cannot speak French.

Answer :

31
EXERCISE 3

32
MORE NOTES
AND EXERCISES VIA ONLINE

Explore these links to enhance your

knowledge and understanding :

VIDEO
https://www.youtube.com/watch?v=VPn7ArmFNYA

ONLINE ASSESSMENT
https://quizizz.com/join?gc=88042202

hello@reallygreatsite.com 33
www.reallygreatsite.com
 REFERENCES
Kevin, F. (2017). Discrete Mathematics and
Applications (2nd), Chapman and Hall (GB).

Marini, M.T., Siti Farah, F. & Faizah, A.M.,

(2020). Discrete Mathematics for Polytechnic
Students Second Edition. Malaysia: Azimat Advance
Ventures.

Oscar, L., (2019). Discrete Mathematics an Open Introduction

3RD Edition. University of Northern Colorado.

Richard, J. (2017). Discrete Mathematics. (8th Edition). USA:

Pearson.

Rosen, K. H. (2018). Discrete Mathematics and Its

Applications, 8th Edition. USA: McGraw-Hill Education.

Wang Wei, Dr. Wong Sin Mong, (2010). SUCCESS Additional

Mathematics SPM. Malaysia: Oxford Fajar Sdn. Bhd

34
 WRITERS :
MARINI BINTI MOHD THAIB

SITI FARAH BINTI FADZIN@FADZIL

FAIZAH BINTI ABDUL MUIN

POLITEKNIK BALIK EMAIL :

PULAU PINANG NIRAI, TEL : 04-868 9000 polibalikpulau@pbu.edu.my
MUKIM 6, 11000 BALIK FAX : 04-869 2061 WEBSITE :
PULAU, PULAU PINANG. pbu.mypolycc.edu.my