Determine the truth value of the statement

Discrete Mathematics Assignment

You are required to write down your answers with steps on papers (and write your name and student ID on the first page), take photos on them, convert them to a PDF file, and then submit to OLE. You may use the mobile app CamScanner. Note that computer-typed answers are not accepted.

Question 1:Rewrite each of the following propositions such that negation appear only within predicates. For example,  ?y ?x P (x, y) should be rewritten as ?y ?x P (x, y).
(a)  ?x ?y P (x, y)
(b)  ?y (?x ?z P (x, y, z) ? ?x ?z Q(x, y, z))

Question 2:Let N be a set of sets defined as follows:
 N contains the empty set ?;
 if N contains the set x, then N contains the set x ? {x}.
(a) Give any five distinct elements of N .

(b) Determine the truth value of the statement "Each element of N is a set containing a distinct number of elements".
(c) Use proof by contradiction to show that N is an infinite set.
(d) Prove or disprove that N ? N .

Question 3 Let S be any infinite set, and let T = {f | f : S ? S} be the set of functions from S to S. Prove that S and T do not have the same cardinality.

Question 4 Twelve basketball players, whose uniforms are numbered 1 through 12, stand around the center ring on the court in an arbitrary arrangement. Show that some three consecutive players have the sum of their numbers at least 20.

Question 5 Give a combinatorial argument to prove that
n  4n-1= ?nk=0C(n, k) 3k (n - k).
You may consider the scenario that n people go to a wine tour by car. One person is the driver who must not drink. The other people can choose one of the 3 alcoholic menus or a non-alcoholic menu.

Note that a non-combinatorial proof will receive 0 marks.

Question 6 Use mathematical induction to show that for all events E1, E2, . . . , En,

p(E1? E2?  ? En) ? ?ni=1p(Ei) .