Search & Filtering
2.Determine the cardinality of each of the sets, A, B, and C defined below, and prove the cardinality of any set that you claim is countably infinite.
A is the set of negative odd integers
B is the set of positive integers less than 1000
C is the set of positive rational numbers with numerator equal to 1
(a) Use rules of inference and laws of logical equivalence (given in Tables 7.6–7.8 in the Unit Notes) to prove the following:
(p → q) ∧ (r → s) ∧ [t → ⇁(q ∨ s)] ∧ t) ⇒ (⇁p ∧ ⇁r)
(b) Use the MATLAB program truth.m and a modified version of propos.m to verify the validity of the inference in part (a).
A- For all integers a and b, if a + b is odd, then a is odd or b is odd.
B- For any integer n the number (n3 - n) is even.
C- Proof of De-Morgan’s Law
Write the following logical arguments as predicate expressions, defining the predicates used and domains of
variables. For each argument, mention the inference rules used in each step. [6 marks]
a) “Asim, a student in this class, owns a Honda bike. Everyone who owns a Honda bike has gotten at least
one traffic violation challan. Therefore, someone in this class has gotten a traffic violation challan.”
b) “Every student who has taken discrete structures course can take algorithms course. Haris, Nouman, and
Azhar, has taken discrete structures course. Therefore, all five roommates can take algorithms course.”
c) “All movies produced by John Sayles are wonderful. John Sayles produced a movie about coal miners.
Therefore, there is a wonderful movie about coal miners.”
d) “There is someone in this class who has been to Saudi Arabia. Everyone who goes to Saudi Arabia
performs Umrah. Therefore, someone in this class has performed Umrah.”
Determine whether this statement about Fibonacci numbers is true.
2𝐹𝒙 − 𝐹𝒙−2 = 𝐹𝒙+1 for x> 1 where 𝐹𝒙 is the 𝒙𝑡ℎ Fibonacci number.
If 𝑈 = {1,2,3,4,5,6,7,8,9,10,11,12}, 𝐴 = {2,3,5,6},
𝐵 = { 1,5,7,8,10,12}, 𝐶 = {8,10,11,12}. 𝐹𝑖𝑛𝑑 𝐴 ∪ 𝐵,
𝐴 ⊕ 𝐵, 𝐵 ∖ 𝐶, |𝑃(𝐴)|
In an exam, a student is required to answer 10 out of 13 questions. Find the number of
possible choices if the student must answer:
(a) the first two questions;
(b) the first or second question, but not both;
(c) exactly 3 out of the first 5 questions;
(d) at least 3 out of the first 5 questions.
(a) In how many different ways can the letters of the word donkey be arranged?
(b) In how many different ways can the letters of the word donkey be arranged if the letters wo must remain together (in this order)?
(c) How many different 3-letter words can be formed from the letters of the word donkey? And what if d must be the first letter of any such 3-letter word?
Express the following argument in symbolic form, and use the rules of inference and also
MATLAB to show that it is logically valid.
Ben is a student or a taxi driver.
If Ben is a taxi driver, then he has a taxi licence.
Ben has a car but he does not have a taxi licence.
Therefore Ben is a student.
Use the pigeonhole principle to give solutions to the following problems:
(a) How many times must a single die be rolled to guarantee that some number is obtained at least twice?
(b) How many times must two dice be rolled to guarantee that the same total score is obtained at least twice?
(c) How many times must two dice be rolled to guarantee that the same total score is obtained at least three times?
