Discrete Mathematics Answers

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-   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 (n³ - 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?

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?

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, knows how to write programs in Java. Everyone who knows how to write

programs in Java can get a high-paying job. Therefore, someone in this class can get a high-paying job.”

b) “Somebody in this class enjoys whale watching. Every person who enjoys whale watching cares about

ocean pollution. Therefore, there is a person in this class who cares about ocean pollution.”

c) “Each of the 50 students in this class has a laptop. Everyone who has a laptop can use a word processing

program. Therefore, Asim, a student in this class, can use a word processing program.”

d) “Everyone in Karachi lives within 50 miles of the ocean. Someone in Karachi has never seen the ocean.

Therefore, someone who lives within 50 miles of the ocean has never seen the ocean.”

 What is the domain and range of the function f that assigns to each pair of negative integers x and y, the value x + y.