Before you start your homework, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)

Classify the following statements as being one of the following, where x and y are arbitrary propositions, and justify your answers (e.g., using a truth table)

• True for all combinations of x and y (Tautology)
• False for all combinations of x and y (Contradiction)
• Neither
• x(x = y)(y)
• x = (xy)
• (xy)(xy)
• (x = y)(x = y)
• (xy)((xy))
• (x = y)(x = y)(y)

2 Miscellaneous Logic

• Let the statement, (x R)(y R) G(x,y), be true for predicate G(x,y).

For each of the following statements, decide if the statement is certainly true, certainly false, or possibly true, and justify your solution. (If possibly true, provide a specific example where the statement is false and a specific example where the statement is true.)

• G(3,4)
• (x R) G(x,3)
• y G(3,y)
• y G(3,y)
• x G(x,4)

• Give an expression using terms involving , and which is true if and only if exactly one of X,Y, and Z is true.

3 Propositional Practice

Convert the following English sentences into propositional logic and the following propositions into English. State whether or not each statement is true with brief justification.

• There is a real number which is not rational.
• All integers are natural numbers or are negative, but not both.
• If a natural number is divisible by 6, it is divisible by 2 or it is divisible by 3.
• (x R)(x C)
• (x Z)(((2 | x)(3 | x)) = (6 | x)) (f) (x N)((x > 7) = ((a,b N)(a+b = x)))

4 Proof by?

• Prove that if for any two integers x and y, if 10 does not divide xy, then 10 does not divide x and 10 does not divide y. In notation: (x,y Z) (10 xy) = ((10 x) (10 y)). What proof technique did you use?
• Prove or disprove the contrapositive.
• Prove or disprove the converse.

5 Prove or Disprove

• (n N) if n is odd then n² +2n is odd.
• (x,y R) min(x,y)=(x+y|xy|)/
• (a,b R) if a+b 10 then a 7 or b
• (r R) if r is irrational then r+1 is irrational.
• (n Z⁺) 10n² > n!.

6 Preserving Set Operations

For a function f, define the image of a set X to be the set f(X)= {y | y = f(x) for some x X}. Define the inverse image or preimage of a set Y to be the set f¹(Y)= {x | f(x) Y}. Prove the following statements, in which A and B are sets. By doing so, you will show that inverse images preserve set operations, but images typically do not.

Hint: For sets X and Y, X =Y if and only if X Y and Y X. To prove that X Y, it is sufficient to show that (x)((x X) = (x Y)).

(a) f¹(AB)= f¹(A) f¹(B). (b) f¹(AB)= f¹(A) f¹(B).

• f¹(AB)= f¹(A) f¹(B).
• f(AB)= f(A) f(B).
• f(AB) f(A) f(B), and give an example where equality does not hold.
• f(AB) f(A) f(B), and give an example where equality does not hold.