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
                                
                                
                                Search
                            
                            Read the Text Version
- 1
 - 2
 - 3
 - 4
 - 5
 - 6
 - 7
 - 8
 - 9
 - 10
 - 11
 - 12
 - 13
 - 14
 - 15
 - 16
 - 17
 - 18
 - 19
 - 20
 - 21
 - 22
 - 23
 - 24
 - 25
 - 26
 - 27
 - 28
 - 29
 - 30
 - 31
 - 32
 - 33
 - 34
 - 35
 - 36
 - 37
 - 38
 - 39
 - 40
 - 41
 - 42
 - 43
 - 44
 - 45
 - 46
 - 47
 - 48
 - 49
 - 50
 - 51
 - 52
 - 53
 - 54
 - 55
 - 56
 - 57
 - 58
 - 59
 - 60
 - 61
 - 62
 - 63
 - 64
 - 65
 - 66
 - 67
 - 68
 - 69
 - 70
 - 71
 - 72
 - 73
 - 74
 - 75
 - 76
 - 77
 - 78
 - 79
 - 80
 - 81
 - 82
 - 83
 - 84
 - 85
 - 86
 - 87
 - 88
 - 89
 - 90
 - 91
 - 92
 - 93
 - 94
 - 95
 - 96
 - 97
 - 98
 - 99
 - 100
 - 101
 - 102
 - 103
 - 104
 - 105
 - 106
 - 107
 - 108
 - 109
 - 110
 - 111
 - 112
 - 113
 - 114
 - 115
 - 116
 - 117
 - 118
 - 119
 - 120
 - 121
 - 122
 - 123
 - 124
 - 125
 - 126
 - 127
 - 128
 - 129
 - 130
 - 131
 - 132
 - 133
 - 134
 - 135
 - 136
 - 137
 - 138
 - 139
 - 140
 - 141
 - 142
 - 143
 - 144
 - 145
 - 146
 - 147
 - 148
 - 149
 - 150
 - 151
 - 152
 - 153
 - 154
 - 155
 - 156
 - 157
 - 158
 - 159
 - 160
 - 161
 - 162
 - 163
 - 164
 - 165
 - 166
 - 167
 - 168
 - 169
 - 170
 - 171
 - 172
 - 173
 - 174
 - 175
 - 176
 - 177
 - 178
 - 179
 - 180
 - 181
 - 182
 - 183
 - 184
 - 185
 - 186
 - 187
 - 188
 - 189
 - 190
 - 191
 - 192
 - 193
 - 194
 - 195
 - 196
 - 197
 - 198
 - 199
 - 200
 - 201
 - 202
 - 203
 - 204
 - 205
 - 206
 - 207
 - 208
 - 209
 - 210
 - 211
 - 212
 - 213
 - 214
 - 215
 - 216
 - 217
 - 218
 - 219
 - 220