Important Announcement
PubHTML5 Scheduled Server Maintenance on (GMT) Sunday, June 26th, 2:00 am - 8:00 am.
PubHTML5 site will be inoperative during the times indicated!

Home Explore Mathematical Logic and Proving Techniques Lecture Notes

Mathematical Logic and Proving Techniques Lecture Notes

Published by Fairuz Shohaimay, 2019-08-15 23:54:09

Description: Lecture Notes with Past Semester Questions
Intended for use by CS111 UiTM Kampus Raub only

Search

Read the Text Version

LECTURE NOTES MATHEMATICAL LOGIC AND PROVING TECHNIQUES with Past Semester Questions Prepared by Fairuz Shohaimay



Lecture Notes Mathematical Logic and Proving Techniques with Past Semester Questions 2019 Edition Prepared by Fairuz Shohaimay This book is intended for use by CS111 students in UiTM Kampus Raub only



CONTENTS 1 15 Set Theory 25 1.1 Sets, Subsets and Set Operations 41 1.2 Laws of Set Theory 48 1.3 Application of Venn Diagram 64 74 Logic 79 100 2.1 Logical Connectives 2.2 Logical Equivalence 127 2.3 Laws of Logic 130 2.4 Logical Implication 138 2.5 Rules of Inference 147 2.6 Quantifiers and Nested Quantifiers 155 167 Proving Techniques 172 180 3.1 Introduction 193 3.2 The Forward-Backward Method 208 3.3 Definition and Mathematical Terminology 3.4 The Construction Method 3.5 The Choose Method 3.6 The Specialization Method 3.7 The Contradiction Method 3.8 The Contrapositive Method 3.9 The Induction Method 3.10 Summary



Chapter 1: Set Theory When we talk about sets, we will immediately think about a group of things or objects or people having something in common. Like the set of students who likes to take photographs or the set of positive integers, etc. This chapter presents some of important terms, symbols and operations of sets. Finally, we present the basic laws of set theory. 1.1 Sets, Subsets and Set Operations Definition 1.1 A set is a collection of things, objects or items having similar characteristics. Definition 1.2 If ������ is one of the objects of the set ������, then a is an element of ������ (denoted by ������ ∈ ������). If it is not true that a is an element of ������, we write ������ ∉ ������. Usually we use capital letters to denote a set (e.g.: ������, ������, ������). Lower case letters (e.g.: ������, ������, ������, ������) represents elements of the set. Elements of a set are placed within set braces ‘{ }’ and separated by commas. Example 1.1 If A is the set consisting of the first five positive integers, then we write ������ = /1, 2, 3, 4, ������, {������}0. Here 2 ∈ ������ but 6 ∉ ������. Notice that, ������ ∉ ������ but {������} ∈ ������. Another standard notation for a set, ������ = {������|������ is an integer and 1 ≤ ������ ≤ 5}. Here the vertical line ‘|’ within the set braces is read “such that.” Example 1.2 If the members of a set are well known or follow by a particular pattern, we can define the set by listing a few elements followed by three dots. ℤ = {1, 2, 3, 4, … } ������ = {������, ������, ������, … , ������, ������} ������ = {−100, −99, −98, … , −2, −1} ������ = >12 , 1 , 1 , 1 , 1 , 1 , … @ The sets ������ and ������ are called finite sets. 3 4 5 6 7 The sets ℤ and ������ are called infinite sets. 1

Below are some common sets in the real number system and their notations. a) ℤ = {… , −1,0, 1, 2, 3, 4, … } = The set of integers b) ℕ = {0, 1, 2, 3, 4, … } = The set of natural numbers (or nonnegative integers) c) ℤG = {1, 2, 3,4, … } = {������ ∈ ℤ|������ > 0} = The set of positive integers 0 is neither positive nor negative integer d) ℤI = {… , −4, −3, −2, −1} = {������ ∈ ℤ|������ < 0} =the set of negative integers e) ℚ = L������ = N |������, ������ ∈ ℤ, ������ ≠ 0S = The set of rational numbers O f) ℚT = /√2, ������, ������, √5, X√4, … 0 = The set of irrational numbers g) ℝ = The set of real numbers Definition 1.3 The cardinality of a set ������, ������(������)or |������| is the number of different (distinct) elements in a set. Example 1.3 Given ������ = {������, ������, ������, ������, ������, ������} and ������ = /2, 4, {5, 6}0. Then, ������(������) = and ������(������) = Definition 1.4 A set A is a subset of a set B (denoted: ������ ⊆ ������) if every element of ������ is an element of ������; that is, if ������ ∈ ������, then ������ ∈ ������. If it is not true that ������ is a subset of ������, we write ������ ⊄ ������. Definition 1.5 If ������ ⊆ ������ and ������ ≠ ������, then ������ is a proper subset of ������ (denoted: ������ ⊂ ������). Example 1.4 {1, 2, 3} ⊂ {1, 2, 3, 4}, but {1, 2, 5} ⊄ {1, 2, 3, 4}. Also, every set is a subset of itself, so {1, 2, 3} ⊆ {1, 2, 3} Example 1.5 If ������ = {������|������ is a football player in UiTM Raub}, ������ = {������|������ is an athlete in UiTM Raub}, and ������ = {������|������ is a CS111 student in UiTM Raub}, then ������ ⊂ ������, ������ ⊂ ������, and ������ ⊆ ������, but ������ ⊄ ������. 2

Definition 1.6 If ������ and ������ are sets, then ������ equals ������ (denoted: ������ = ������), whenever, for any x, ������ ∈ ������ if and only if ������ ∈ ������. An alternative definition is that ������ = ������ if and only if ������ ⊂ ������ and ������ ⊂ ������. Example 1.6 {1, 2, 4, 6} = {2, 4, 6, 2, 1} Since a set is defined only by the elements that it contains, there is no order implied in the listing of the elements. Definition 1.7 The empty set, denoted by ∅ or by { }, is the set, which contains no elements. Definition 1.8 The universal set ������ (or ������) is a set of all elements under discussion for possible membership in a set. Example 1.7 In number theory, ������ is usually the set of all integers of the positive integers. In calculus, ������ may be the set of all real numbers. By definition, every set is a set of universal set. The empty set is a subset of any given set ������ since every element of the empty set contained in ������. Definition 1.9 The power set of ������, ������(������) is the collection (or set) of all subsets of ������. For any finite set ������ with |������| = ������ ≥ 0, |������(������)| = 2j. Example 1.8 For the set ������ = {������, 2, ������}, ������(������) = /{������}, {2}, {������}, {������, 2}, {������, ������}, {2, ������}, {������, 2, ������}, ∅0. Also, |������| = 3, then |������(������)| = 2k = 8. 3

Definition 1.10 The intersection of sets ������ and ������ (������ ∩ ������) is the set of all elements that are in both ������ and ������. ������ ∩ ������ = {������|������ ∈ ������ ������������������ ������ ∈ ������} Example 1.9 If ������ = {1, 2, 3, 4, 5} and ������ = {2, 3, 5, 7}, then ������ ∩ ������ = Definition 1.11 The union of sets ������ and ������ (������ ∪ ������) is the set of all elements that are either in ������ or ������. ������ ∪ ������ = {������|������ ∈ ������ ������������ ������ ∈ ������} Example 1.10 If ������ = {1, 2, 3, 4, 5} and ������ = {2, 3, 5, 7}, then ������ ∪ ������ = 4

Definition 1.12 The set difference ������\\������ (or ������ − ������) is the set of all elements, which are in ������ but are not in ������. ������\\������ = {������|������ ∈ ������ and ������ ∉ ������} Definition of set difference: ������\\������ = ������ ∩ ������T Example 1.11 and ������\\������ = If ������ = {1, 2, 3, 4, 5} and ������ = {2, 3, 5, 7}, then ������\\������ = Definition 1.13 The complement of set ������, denoted ������T, is the set of all elements of the universe which are not in ������. ������T = ������\\������ = {������|������ ∈ ������ and ������ ∉ ������} Example 1.12 If ������ is the set of positive integers and ������ = {2, 4, 6, 8, … } is the set of all positive even integers, then ������T = {1, 3, 5, 7, … } is the set of all positive odd integers. 5

Exercise 1.1 September 2013 Q1(a) Given the sets ������ = /1, {4}0 and ������ = {1, 2, 4, ������} i) State the number of subsets for set ������. ii) List all the subsets for set ������. iii) List all the elements of ������ ∩ ������. Exercise 1.2 September 2013 Q1(b) List the members in the following sets: i) ������ = {������|������y = 16} ii) ������ = {(������, ������)|������, ������ ∈ ������, ������ = ������y + 1, −2 ≤ ������ < 2} 6

Exercise 1.3 September 2013 Q2 Fill in the blanks. a) If ������ = {∅}, then ������(������) =____________ but if ������ = ∅, then ������(������) =____________. b) If ������ = {1, 6, 7} and ������ = {2, 8, 9}, then |������ ∩ ������| =______ and |������ ∪ ������| =______. c) Given ������ = /∅, 1, 6, 7, {9}0, then ∅ is an ____________ of ������ and {∅} is a ____________ of ������. d) {2, 3, 5, 7, 11, … } is called the set of _________ numbers while {2, 4, 6, 8, 10, … } is called the set of _____________ numbers. e) ������\\������ symbolizes ___________________ while the union of the sets ������ and ������ is symbolized by _________. Exercise 1.4 March 2014 Q1(a) Consider the universal set, ������ = {������ ∈ ������|1 ≤ ������ ≤ 20} and the sets ������ = {all prime numbers} ������ = {even numbers} ������ = {multiples of 3} List the elements in the following sets: i) ������T ii) ������ − ������ iii) ������T ∩ ������T iv) (������ − ������) ∪ (������ − ������) 7

Exercise 1.5 September 2014 Q1(a) State whether each of the following statement in TRUE or FALSE. i) 0 ∈ ∅ ii) ������ ∈ /������, {������}0 iii) {−5, 4, 2, 0} ⊆ {−5, 4, {2}, 0} Exercise 1.6 September 2014 Q1(b) Given the following sets: ������ = {������|������ ∈ ������, 11 ≤ ������ < 21} ������ = {������|������ is a multiple of 3} ������ = {������|������ is a factor of 60} ������ = {������|the difference between the digits of the elements in the universal set is exactly 2} i) List down all the elements in the universal set ������, ������, ������ and ������. ii) List the elements for the set (������\\������T) ∩ ������. iii) Find |(������ ∪ ������)T ∪ ������|. 8

Exercise 1.7 March 2015 Q1(a) State whether each of the following is true or false: i) {������, ������} ⊂ {������, ������, ������} ii) ∅ ⊄ ������ where ������ = {������, ������} iii) If ������ = {������, ������}, then the power of the set ������ can be written as Power(������) = {∅, {������}, {������}, {������, ������}, ������} iv) {−2, −1,0} ⊂ ������ v) Let ������ = /������, {������}0, then ������ ∈ ������, ������ ∈ ������, ������ ⊂ ������, and ������ ⊂ ������. Exercise 1.8 March 2015 Q1(b) Given the following sets: ������ = {������|������ ∈ ������, 0 < ������ < 14} ������ = {������|������ ∈ ������ and 0 < ������ < 8} ������ = {2������ + 1|������ is an even integer between 1 and 8} ������ = {������|������ is an odd prime less than 14} i) List down all the elements in the universal set ������, ������, ������ and ������. ii) List the element/s of the set (������\\������) ∩ ������T. iii) Find |(������ ∪ ������) ∩ ������|. 9

Exercise 1.9 September 2015 Q1(b) Consider set ������ = /1, 2, {4}0 and ������ = {1, {2}, 4}. Determine whether each of the statement is true or false. i) { } ⊆ ������ ii) 2 ∈ ������ iii) 1 ∉ ������ ∩ ������ iv) {4} ⊂ ������ Exercise 1.10 March 2016 Q1(a) Given the following sets: ������ = {2, 3, 4, 5, 6, 7, 8, 9, 10, 11} ������ = {������|������ is a natural number less than or equal to 7} ������ = {������|������ is a multiple of 3} ������ = {������|������ is a prime number} i) List down all the elements of sets ������, ������ and ������. ii) List down the elements of set (������ − ������T) ∩ ������. iii) Find |(������ ∩ ������) ∪ (������T ∩ ������)|. 10

Exercise 1.11 October 2016 Q1(a) List the elements in the following sets: i) ������ = {������|������y = 36} ii) ������ = {(������, ������)|������, ������ ∈ ������G, ������ = ������k + 1, −2 ≤ ������ ≤ 2} iii) ������ = {3������ + 1|������ is an odd integer between 2 and 10} Exercise 1.12 March 2017 Q1(a) Given the following sets: ������ = {������|2 ≤ ������ < 13, ������ ∈ ������} ������ = {������|������ is a prime number} ������ = {������|������ is divisible of 2} ������ = {������|������ is multiple of 4} i) List down all the elements in set ������, ������ and ������. ii) List down the elements of set (������T − ������T) ∪ ������. iii) Find |(������T ∪ ������) ∩ (������ ∪ ������T)|. 11

Exercise 1.13 January 2018 Q1(a) Given the universal set ������ = {������|������ ∈ ������G, ������ ≤ 25} and the sets ������ = L���3��� ∈ ������G|������ ≤ 25S ������ = {������ ∈ ������G|������ is divisible by 5} ������ = {������ ∈ ������G|������ is an even number} i) List the elements of sets ������, ������, and ������. ii) List the elements of ������\\(������ ∪ ������). iii) Find |������T ∩ (������ ∪ ������)T|. 12

Exercise 1.14 June 2018 Q1(a) Given the following sets where ������, ������ ⊆ ������: ������ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10} ������ = {������|������ is a prime number} ������ = L���2��� |������ ∈ ������S i) List down the elements of ������T. ii) Find ������(������ − ������T). iii) If ������ = {5, 6, 7}, is (������ ∩ ������) ⊆ ������? Exercise 1.15 December 2018 Q1(a) Given the following sets where ������, ������ ⊆ ������: ������ = {Set of all alphabets} ������ = {������|������ is vowel letters} ������ = {������, ������, ������, ������, ������, ������, ������, ℎ, ������, ������} i) List down the elements of ������. ii) Find (������ ∪ ������)T. iii) Is ������ ⊆ ������? State the reason. 13

Exercise 1.16 June 2019 Q1(a) Consider the universal set, ������ = {������|������ ∈ ������, 1 < ������ ≤ 24} and the sets ������ = {������|������ is not divisible by 2} ������ = {������|3 < 3������ ≤ 23} ������ = {������|the difference between the digits of the elements in universal set is exactly 2} i) List the elements of sets ������, ������ and ������. ii) List the elements of set (������ ∪ ������)\\������. iii) Find ������œ(������ ∪ ������)\\������T• iv) Is œ(������ ∪ ������)\\������T• ∈ ������? 14

1.2 Laws of Set Theory For any sets ������, ������ and ������ taken from a universal set ������, also ∅ is an empty set. a) Double Complement Law (������T)T = ������ b) De Morgan’s Law c) Commutative Law (������ ∪ ������)T = (������T ∩ ������T) d) Associative Law (������ ∩ ������)T = (������T ∪ ������T) e) Distributive Law f) Idempotent Law ������ ∪ ������ = ������ ∪ ������ g) Identity Law ������ ∩ ������ = ������ ∩ ������ h) Dominance Law i) Inverse Law ������ ∪ (������ ∪ ������) = (������ ∪ ������) ∪ ������ j) Absorption Law ������ ∩ (������ ∩ ������) = (������ ∩ ������) ∩ ������ ������ ∪ (������ ∩ ������) = (������ ∪ ������) ∩ (������ ∪ ������) ������ ∩ (������ ∪ ������) = (������ ∩ ������) ∪ (������ ∩ ������) ������ ∪ ������ = ������ ������ ∩ ������ = ������ ������ ∪ ∅ = ������ ������ ∩ ������ = ������ ������ ∩ ∅ = ∅ ������ ∪ ������ = ������ ������ ∪ ������T = ������ ������ ∩ ������T = ∅ ������ ∪ (������ ∩ ������) = ������ ������ ∩ (������ ∪ ������) = ������ Example 1.13 Reasons Simplify ������ ∩ (������\\������). ������ ∩ (������\\������) = ������ ∩ (������ ∩ ������T) = ������ ∩ (������T ∩ ������) = (������ ∩ ������T) ∩ ������ = ∅ ∩ ������ =∅ 15

Example 1.14 (������\\������)T Reasons Simplify (������\\������)T. Definition of set difference De Morgan’s Law = Double Complement Law = = Reasons Example 1.15 Reasons Simplify ������ ∩ [(������ ∪ ������) ∪ ������′]. ������ ∩ [(������ ∪ ������) ∪ ������′] = ������ ∩ [������ ∪ (������ ∪ ������T)] = ������ ∩ (������ ∪ ������) = ������ ∩ ������ = ������ Example 1.16 Simplify ¤œ(������ ∪ ������) ∩ ������•T ∪ ������T¥T. ¤œ(������ ∪ ������) ∩ ������•T ∪ ������T¥T = ¤œ(������ ∪ ������) ∩ ������•T T ∩ (������T)T ¥ = œ(������ ∪ ������) ∩ ������• ∩ ������ = ������ ∩ œ(������ ∪ ������) ∩ ������• = œ������ ∩ (������ ∪ ������)• ∩ ������ = ������ ∩ ������ 16

Example 1.17 Reasons Simplify (������ ∪ ������) ∩ (������T ∩ ������)T. = = = = = Example 1.18 Reasons Simplify (������ ∪ ������)T ∩ (������ ∩ ������T)T. = = = = = = Exercise 1.17 March 2012 Q2(a) Using the laws of set theory, show that (������ ∪ ������T) ∩ (������ ∪ ������T) = (������ ∩ ������) ∪ (������ ∪ ������)T 17

Exercise 1.18 March 2013 Q2(a) Simplify the following by using the laws of set theory. (������\\������)T ∪ [(������ ∪ ������) ∩ (������ ∪ ������T)] Exercise 1.19 September 2013 Q3(a) Simplify the following using the laws of set theory: i) œ������T ∪ (������ ∩ ������T)•T ii) [������ ∩ (������ ∩ ������)] ∪ (∅ ∩ ������) 18

Exercise 1.20 March 2014 Q2(b) Show that (������ ∩ ������T) ∩ (������ ∪ ������T) = ������ ∩ (������ ∪ ������)T using the laws of set theory. Exercise 1.21 September 2014 Q2(b) Simplify the following expression using the laws of set theory. ������ ∪ [(������ ∪ ������T)\\������T] 19

Exercise 1.22 March 2015 Q2(b) Simplify ((������\\������)T ∩ ������) ∪ ∅ using the laws of set theory. Exercise 1.23 September 2015 Q2(a) Simplify the expression ������ ∪ [(������ − ������)T ∩ ������] using the laws of set theory. 20

Exercise 1.24 March 2016 Q1(c) Simplify [(������ ∪ ������T)T ∪ (������T ∪ ������T)]\\������ using the laws of set theory. State your steps and reasons in your answer. Exercise 1.25 October 2016 Q1 (c) Simplify the following by using the laws of set theory. (������ ∪ ������)T ∩ [������ ∩ (������ ∪ ������)] 21

Exercise 1.26 March 2017 Q1(c) By using the laws of set theory, simplify [(������T ∩ ������T) ∪ (������ ∩ ������)T] − ������. State your steps and reasons in your answer. Exercise 1.27 January 2018 Q1(c) State the steps and reasons using the laws of set theory. [(������ ∪ ������)\\(������\\������)]\\������ 22

Exercise 1.28 June 2018 Q1(c) Simplify the following expression and state the reason using the laws of set theory. [(������ − ������) ∪ (������ ∪ ������T)T]T Exercise 1.29 December 2018 Q1(c) Proof using the laws of set theory (������T ∩ ������T)T ∩ ������T = ������ ∩ ������T. 23

Exercise 1.30 June 2019 Q1(c) Simplify the following statement and state the reasons using the laws of set theory. (������\\������)T ∪ œ������ ∩ (������ ∪ ������T)• 24

1.3 Application of Venn Diagram A Venn diagram is used to represent finite elements of sets, sometimes overlapping with each other. We write the number of elements in each region. There is no formal rule for constructing a Venn diagram. However, the following formula might be useful. If ������ and ������ are finite sets, then |������ ∪ ������| = |������| + |������| − |������ ∩ ������| If also, ������ is a finite set, then |������ ∪ ������ ∪ ������| = |������| + |������| + |������| − |������ ∩ ������| − |������ ∩ ������| − |������ ∩ ������| + |������ ∩ ������ ∩ ������| From the formula for |������ ∪ ������ ∪ ������|and De Morgan’s Law, we find that if ������, ������, and ������ are sets from a finite universe ������, then |(������ ∪ ������ ∪ ������)T| = |������| − |������ ∪ ������ ∪ ������|. Example 1.19 For a total of 95 students, 54 are studying MAT222, 66 are studying STA220, and 30 are studying both courses. How many students are studying either courses? Let U 5 ������ = the class of 95 students ������ = the subset of students studying MAT222 A 36 ������ = the subset of students studying STA220 24 30 B |������| = 54, |������| = 66, |������ ∩ ������| = 30 The number of students studying either MAT222 or STA220 |������ ∪ ������| = |������| + |������| − |������ ∩ ������| = = 25

Exercise 1.31 March 2012 Q1 (a) The Venn diagram below shows sets ������, ������ and ������. Shade the region for ������ ������ ������ i) ������\\������ ii) (������ ∪ ������T) ∩ ������ 26

Exercise 1.32 March 2012 Q1(b) A certain school has 320 students who stay in the school hostel. 400 students, including some who stay in the hostel, participate in a written quiz. The various groups of students in the school are denoted as: ������ = {all students in the school} ������ = {students who stay in the school hostel} ������ = {students who participate in the quiz} i) Draw a Venn diagram to illustrate the relationship between ������, ������ and ������. ii) It is given that the number of students who stay in the hostel but do not participate in the quiz is ������. This number represents ¬ of the students who participate in the quiz but - do not stay in the hostel. Calculate the value of ������. 27

Exercise 1.33 March 2013 Q1 Every year in December, Samad as a Marketing Executive for Gwen Travel Agency presents the three most visited states in Malaysia. In his record for 2012, he found that the three most visited states were Malacca (������), Johor (������) and Penang (������) with a total number of visitors of 1480. Here is the additional information to help him with his presentation • |������| = 410 • |������| = 620 • |������| = 830 • |������ ∩ ������ ∩ ������| = 100 • |������\\(������ ∪ ������)| = 600 • |������\\(������ ∪ ������)| = 400 a) Indicate the above information in a single Venn diagram. b) Determine number of visitors for Penang only. c) Determine number of visitors for Malacca and Johor only. 28

Exercise 1.34 March 2014 Q2(a) A telecommunication company performed a survey on 100 smart phone owners. The following information was gathered for the top three brands of smart phones: • 56 owned an iPhone • 16 owned a Blackberry only • 17 owned a Samsung Galaxy Note and an iPhone • 10 owned a Samsung Galaxy Note and a Blackberry • 28 owned an iPhone and a Blackberry • 23 owned a Samsung Galaxy Note but not a Blackberry • 10 owned an iPhone, a Samsung Galaxy Note and a Blackberry Answer the following questions: i) Express the above information in a single Venn diagram. ii) How many own a Samsung Galaxy Note and a Blackberry only? iii) How many own an iPhone and a Samsung Galaxy Note but not a Blackberry? iv) How many do not own any of the above brands of smart phones? 29

Exercise 1.35 September 2014 Q2(a) A survey of 56 people during a book fair in Kuala Lumpur found that there are three most favourite novel authors among book readers. 19 readers enjoyed reading books written by Mitch Albom but not Sydney Sheldon. 19 enjoyed reading books written by Sydney Sheldon but not Dan Brown. 2 readers enjoyed reading books by all the three authors. lf 12 readers enjoyed reading books written by Dan Brown only, determine the number of readers who enjoyed reading books written by Sydney Sheldon and Dan Brown? 30

Exercise 1.36 March 2015 Q2(a) A highway survey crew gathered the following information about 500 drivers on three (3) driver behaviours while driving: 100 drivers were smoking (A) 200 drivers were texting (B) 300 drivers were crossing the red lights (C) In addition, 50 drivers were smoking and texting, 40 drivers were smoking and crossing the red lights, and 30 drivers were texting and crossing the red lights. Determine the number of drivers who were smoking, texting and crossing the red lights. 31

Exercise 1.37 September 2015 Q1(a) The following information was obtained from a survey on 280 customers at Aladdin book store who purchased several kinds of magazines. It was found out that 98 purchased Times 48 purchased Readers Digest only 64 purchased Newsweek only 44 purchased Newsweek and Readers Digest 30 purchased Newsweek and Times 40 did not purchase anything. In addition, the number of customers who purchased Readers Digest and Times only is twice the number of customers who purchased all the three magazines. i) Illustrate the above information in a single Venn diagram. ii) How many customers purchased all the three items? 32

Exercise 1.38 September 2015 Q2(b) For each of the Venn diagram below, shade the region(s) based on the set expression. i) (������ − ������) − ������T ������ ������ ii) ������T ∪ ������ ������ ������ ������ iii) ������ ∩ ������T ������ ������ 33

Exercise 1.39 March 2016 Q1(b) The MPH book store manager conducted a survey on 2220 customers who bought books from the store. The survey was conducted on three bestselling books namely 'Romeo and Juliet (R)', 'Lord of the Rings (L)' and 'Harry Potter (H)'. 615 customers bought 'Romeo and Juliet'. 930 customers bought 'Lord of the Rings'. 1245 customers bought 'Harry Potter'. 150 customers bought all three books. 600 customers bought 'Lord of the Rings' but did not buy either of the other two books. 900 customers bought 'Harry Potter' but did not buy either of the other two books. i) Express the information in a single Venn diagram. ii) Find the number of customers who bought 'Romeo and Juliet' only. iii) Find the number of customers who bought 'Harry Potter' and 'Lord of the Rings'. 34

Exercise 1.40 October 2016 Q1(b) Sandy conducted a research on the most visited shopping malls in Kuala Lumpur. Based on the result, she found that the three most visited shopping malls were Suria KLCC (S), Mid Valley Megamall (M) and Sunway Pyramid (P) with a total number of visitors of 148,000. Additional information regarding her research is given below: |������| = 41,000 |������| = 83,000 |������| = 62,000 |������ ∩ ������ ∩ ������| = 10,000 |������\\(������ ∪ ������)| = 40,000 |������\\(������ ∪ ������)| = 60,000 i) Indicate the above information in a Venn diagram. ii) Determine the number of visitors for Suria KLCC (S) only. iii) Determine the number of visitors for Mid Valley Megamall and Sunway Pyramid. 35

Exercise 1.41 March 2017 Q1(b) E-Techno store manager was doing a survey among the customer for three types of notebooks which were Acer Aspire (AA), Dell Latitude (DL) and Asus Zenbook (AZ). He obtained the information from 1210 customers. • 350 customers bought (AA). • 570 customers bought (DL). • 630 customers bought (AZ). • 85 customers bought all three notebooks. • 410 customers bought (AZ) but did not buy neither (AA) nor (DL) notebooks. (Hint: |������������\\(������������ ∪ ������������)|). • 370 customers bought (DL) but did not buy neither (AA) nor (AZ) notebooks. (Hint: |������������\\(������������ ∪ ������������)|). i) Express the information in a single Venn diagram. ii) Find the number of customers bought Acer Aspire only. iii) Find the number of customers bought Dell Latitude and Asus Zenbook. 36

Exercise 1.42 January 2018 Q1(b) Rihanna surveyed college students about how they communicated with their friends over the previous weeks by percentage. 66% of the students used e-mail 76% of the students used text messages 34% of the students used social networks 56% of the students used e-mail and text messages 18% of the students used e-mail and social networks 19% of the students used text messages and social networks 12% of the students used all three types of communication i) Present the above information in a Venn diagram. ii) Determine the percentage of students who used at least one of these three types of communication. iii) How many students do not use any of the three types of communication, if this survey involves 120 college students? 37

Exercise 1.43 June 2018 Q1(b) A study was conducted among 500 people regarding the countries in the world that they had visited. It was found that: 50 had visited Egypt, Jordan and Saudi Arabia ������ had visited Egypt and Jordan only ������ had visited Egypt and Saudi Arabia only 96 had visited Jordan and Saudi Arabia 100 had visited Egypt only 15 had visited Jordan only 20 had visited Saudi Arabia only i) Draw a single Venn diagram to represent the above information. ii) Calculate the value of ������ and ������ if the number of people who had visited Jordan exceeded the number of people who had visited Saudi Arabia by 20. 38

Exercise 1.44 December 2018 Q1(b) Given 3 subsets ������, ������ and ������ of universal set ������. Suppose: ������(������) = 68, ������(������ ∪ ������ ∪ ������) = 64, ������(������) = 50, ������(������) = 49, ������(������) = 46, ������(������ ∩ ������) = 39, ������(������ ∩ ������) = 33, ������(������ ∩ ������) = 36 i) Draw a single Venn diagram to represent the above information. ii) Find ������(������ ∪ ������ ∪ ������)T. iii) Find the cardinality of (������ ∩ ������ ∩ ������). 39

Exercise 1.45 June 2019 Q1(b) A group of final year students conducted a survey on 500 college students regarding their extra-mural activities during the previous semester. 270 students participate in the debate club 248 students participate in the chess club 237 students participate in the tennis club 105 students participate in the chess club only 130 students participate in the debate club only 80 students participate in all the three club activities i) Present the above information in a single Venn diagram. ii) Determine the number of students who like to participate in only one activity. iii) Calculate the percentage of students who participate in debate and tennis club but not in the chess club activity. 40

Chapter 2: Logic Logic is the essence of reasoning. We use logic in our everyday lives. We determine whether a statement is true or false. We use logical rules for control systems to define how they should operate. For example, in washing machines, the logical rule could be programmed as 'If the laundry weighs more than 5 kg, then fill the washing tub with 50 litres of water'. Apart from that, we also use logic to deduce the conclusion of an argument. In this chapter, we will look at the basics in the algebra of propositions and the use of quantifiers in mathematical statements and their truth values. 2.1 Logical Connectives Definition 2.1 Statements (or propositions) are declarative sentences that are either true or false – but not both. Example 2.1 We usually use the lowercase letters (e.g. ������, ������ and ������) to represent these statements: ������: This book has 100 pages. ������: The cover of this book is green in colour. ������: Three authors write this book. However, we don’t consider these sentences as statements because they are neither true nor false. Do your homework. Why is the world almost round? What a beautiful morning! The statements ������, ������ and ������, are examples of primitive statements. Compound statements are statements that contain logical connectives, such as not, and, or, if … then, and if and only if. The five logical connectives are denoted by their logical symbols. We use truth tables to represent all possible truth values of a statement. 41

Definition 2.2 Negation (¬): translated as “not” or “it is not the case that”. Example 2.2 The negation of statement ������ is denoted by ¬������. For the statement ������ above, ¬������ is the statement “This book does not have 100 pages.”. ¬������: ¬������: The effect of the symbol ¬ on the meaning of a sentence is illustrated by the following table, which is called a truth table for ¬: ������ ¬������ Truth values: T = true, F = false OR 1 = true, 0 = false Definition 2.3 Conjunction (Ù): translated as “and” or sometimes “but”. Example 2.3 The conjunction of the statement ������, ������ is denoted by ������ ∧ ������. In our example, the statement ������ ∧ ������ is read “This book has 100 pages, and its cover is green in colour.”. ������ ������ ������ ∧ ������ The statement ������ ∧ ������ is true when both ������ and ������ must be true. If either ������ or ������ is false, then ������ ∧ ������ is false. 42

Definition 2.4 Disjunction (Ú): translated as inclusive “or”. Example 2.4 The disjunction of the statements ������, ������ is denoted as ������ ∨ ������. From the previous example, the statement ������ ∨ ������ is read “This book has 100 pages or its cover is green in colour.”. ������ ������ ������ ∨ ������ Consequently, ������ ∨ ������ is true if one or the other or both of the statements p and q are true. Definition 2.5 Implication (®): translated as “if … then …”. Example 2.5 If we write ������ → ������ (also read as: ������ implies ������), then we say: • If ������, then ������ • ������ only if ������ • ������ is sufficient for ������ • ������ is necessary for ������ • ������ is a sufficient condition for ������ • ������ is a necessary condition for ������ Consider the statement ������ → ������: If I eat ice cream every day, then I will be happy. The statement ������ is called the hypothesis of the implication; ������ is called the conclusion. ������ ������ ������ → ������ The truth value of ������ → ������ is false only when the hypothesis ������ is true, and the conclusion ������ is false. For other cases, the truth value of ������ → ������ is true. 43

Definition 2.6 Biconditional («): translated as “if and only if” (or “iff”) Example 2.6 From the previous example, the statement ������ ↔ ������ is read \"This book has 100 pages if and only if its cover is green in colour.”. ������ ������ ������ ↔ ������ The statement ������ ↔ ������ is true whenever ������ and ������ have the same truth values. Example 2.7 Consider the following primitive statements: ������: My computer is high-speed. ������: I will finish my project on time. ������: I will pass the course. Express the following sentences as symbolic expressions: a) My computer is not very fast, or I would finish my project on time. b) I will not finish my project on time and pass the course. c) It is not true that I will finish my project on time and pass the course. d) My computer is high-speed, or I will not finish my project on time and pass the course. 44


Like this book? You can publish your book online for free in a few minutes!
Create your own flipbook