Discrete Mathematics I


(1) Let G represent the set of all T.V. game shows. Let P be the set of people in your neighbourhood. Let 0(1), 9) be

the predicate that the person p appeared on game show 9 and D(p) be the predicate the p is a doctor. Using the above
definitions,( i ) translate: “There is a person in your neighbourhood who has been a contestant on a game show but is

not a doctor” into symbolic notation.
ii ) Negate your symbolic expression (show steps). () Finally, translate the statement from ( ii ) into English.
(2) (a) Express symbolically, using quantifiers, carefully defining the domain ofdefinition and your predicates:
“If a quadrilateral is a rectangle then it has four equal angles
(b) Write the converse of your quantified statement above.
(c) Is the implication true? Is the converse true?
(d) In light of your answers to the last two questions above, express a quan-
tified statement to identify rectangles
(3) Determine whether each statement below is true or false (give a brief expl.
for your answer), and in each case, obtain the negation of the quantified
(a) Va,b
(b) VaE [0,00),3 IER such that x2 =a/-it2 =a
(c) Va ? N,3 b,c ? N such that ab ? c3
(d) 3x ? Z such that Vy ? ??? ? Z
(4) Prove that Vm ? N; 3k: ? N ? (in-n)2 > m2 Vn > k:
(Note: ? stands for “such that”).
(5) (a) Prove that if a ? Z then a is even if and only if a2 is even
(b) Prove that if a ? Z then a is odd if and only if a2 is odd
(c) Hence show that Vn ? Z; n3 + n is even
(6) (a) Given the premises h/ ? r and (h / n) ?? r show that you can conclude
n, using proof by contradiction.
(b) If 100 coins are distributed over nine bags, then one bag contains at least
12 coins. Use proof by contradiction).