1.  (20 points)

Let p and q be the propositions:

p :  You get a speeding ticket.

q :  You drive over 80 miles per hour.

Write these propositions using p and q and logical connectives (including negations).

(a) If you do not drive over 80 miles per hour, then you will not get a speeding ticket.

(b) You drive over 80 miles per hour, but you do not get a speeding ticket.

(c) You will get a speeding ticket if you drive over 80 miles per hour.

Whenever you get a speeding ticket, you are driving over 80 miles per hour.

2.  (20 points)

(a)  Show that -p - (q - r) and q - (p V r) are logically equivalent.

Since the last column matches the fifth column, the statements are logically equivalent.

(b)  Show that ((p V q) V (-p V r)) - (q V r) is a tautology.

Since the last column is all true, ((p V q) V (-p V r)) - (q V r) is a tautology.

3.  (20 points)

(a) Prove that for all integers n, n is even if and only if n2 + 5 is odd.

Suppose n is even. Then 3k e z such that n = 2k . Then n2 +5 = 4k2 +5 = 2(2k2 +2)+1. Since k is an integer, so is 2k2 + 1. Since n2 + 5 is twice an integer plus one, it is odd.

Need to show if n2 + 5 is odd then n is even. Suppose n is odd. Then 3k e z such that n = 2k + 1.  Then n2 + 5 = 4k2 + 4k + 1 + 5 = 2(2k2 + 2k + 3).  Since k e z, we have 2k2 + 2k + 3 e z, so n2 + 5 is twice an integer, so it’s even. That’s a contradiction, so n cannot be odd, so must be even.

(b) Prove or disprove the following statement:  the sum of any two irrational numbers is irrational.

This is not true.  For example let x = ^2 and y = _^2.  We know from class that x is irrational.  y is also irrational, since if it were rational, x, which is _y would also be rational. So, x, y are both irrational, but x + y = 0 is rational.

4.  (20 points)  Let A, B and C be sets. Prove or give a counter example. If proving that two sets are equal, you should show that an arbitrary element from the first set is in the second set and that an arbitrary element from the second set is in the first set. Simply giving a membership table will earn very little credit, if any.

(a)  (A u B) _ A = B _ (A n B)

Suppose x e (A u B) _ A.  Then x e A u B and x  A.  x e A u B means x e A or x e B . But we know x  A so we must have x e B .  On the other hand x  A implies x  A n B . Since x e B and x  A n B we have x e B _ (A n B). Since this holds for every x e (A u B) _ A, we have (A u B) _ A c B _ (A n B).

Now, suppose x e B _ (A n B).  Then x e B and x  A n B .  It follows that x \inA. Now, x e B implies x e A u B . Combined with x  A gives x e (A u B) _ A. Since this holds for all x e B _ (A n B), we have B _ (A n B) c (A u B) _ A.

Combining the two parts we obtain B _ (A n B) = (A u B) _ A

(b) A _ (B _ C) = (A _ B) u C

This is not true. For example let A and B be empty, but C = {1}. Then A _ (B _ C) is empty but (A _ B) u C = {1}.

Of course there are many examples.  One way to come up with examples is to draw a Venn diagram or an inclusion table.

5.  (20 points)

(a) Rewrite each statement below as a logically equivalent statement, with all implications replaced by a combination of logical connectives (-,  V,  V), and such that all negation symbols appear immediately before a predicate (that is, not before a quantifier, a logical connective or a parenthesis).

(i)  -Ay3x(P (x, y) V Q(x, y))

-(3x3y-P (x, y) V AxAyQ(x, y))