Concordia University Name: Comp 232-AA Assignment One Student number: Instructor: Robert Mearns Due: 2017/05/18 Show all work on these sheets. In proofs use formats employed in the completed Note Outlines (Sec 1.1-1.8) done in class. If not indicated in question text, state the type of proof being used. [04] 1. Write each statement and its indicated form as: If then (i) n2 is greater than 9 only if n is greater than 3 statement: converse: (ii) x 0 is necessary for |x| = x statement: contrapositve: (ii) x 0 is sucient for |x| = x statement: inverse: (iii) I will drve to work unless it does not rain. statement: inverse of contrapositve: [05] 2. Knights always tell the truth, Knaves always tell a lie and Spies can tell the truth or a lie. You meet three people A, B, C one of each type. Each of A, B, C knows what the other types are. A says ”I am the Knight”, B says ”I am the Knave”, C says ”I am not the knave”. Let p represent A is the Knight, q represent B is the Knight and r represent C is the Knight. Use a truth table to assist in the determination of the type of each person. [06] 3. Simplify each statement using logical equivalences then state whether each statement is a Tautology, Contradiction or Contingency. If statement is a Contingency state one set of values for p, q that make statement T and one set that makes it F. a) (¬p ^ (p ! q)) ! ¬q b) (p ! q) ^ (q ! ¬p) ^ (p _ q) [05] 4. P(x) is statement ” Student x knows Calculus”, Q(y) is statement ”Class y contains a student who knows Calculus”. Express each statement below using quantifiers for P, Q a) Some students know Calculus b) Not every student knows Calculus c) Every student in every class knows Calculus d) Every class contains a student who knows Calculus e) There is at least one class with no students who know Calculus [06] 5. P(x, y) means 3xy + x = 7, where x, y are Real numbers. Determine the truth value of each statement below and justify your answer. a) 8x9yP(x, y) b) ¬8x9y¬P(x, y) [06] 6. Determine if each equivalence is valid or invalid. If valid justify, if invalid list a counter example. a) 9x(P(x) _ Q(x)) ⌘ 9xP(x) _ 9xQ(x) b) 8x(P(x) _ Q(x)) ⌘ 8xP(x) _ 8xQ(x) c) 8x(P(x) () Q(x)) ⌘ 8xP(x) () 8xQ(x) [04] 7. For this question form solutions using Boolean Algebra notation instead of ^, _, ¬ , T, F. Consider the decision table: pqr False False False False False True False True False False True True a) Beside each row write the Conjunction expression in terms of p, q, r b) Write the Disjunction of the four answers in a) c) Evaluate the simplified Boolean Algebra expression for the answer in b) [06] 8. Consider the Theorem: If 3n2 + 8 is even then n is even. Prove this Theorem three ways: a) Proof by Contraposition: b) Direct proof: c) Proof by Contradiction: [03] 9. Given a group of 40 people prove that at least four of these people were born in the same month. [03] 10. Prove 8x, x 6= 0, x✏R : x4 + 9 x4 6 Hint: Use backword reasoning to discover an equation to start a Direct proof. [03] 11. The notation max(x, y), where x, y ✏R, x 6= y implies the greater of values x, y. Use a proof by cases to prove max(a, max(b, c)) = max(max(a, b), c) where a, b, c ✏R, a 6= b 6= c [09] 12 a) Prove that: If a is an even integer then an, n✏Z+ is an even Integer. b) Prove that: If a is an odd integer then an, n✏Z+ is an odd Integer. c) Assuming the results in a) and b prove that log3 4 is Irrational. total 60 marks