1) Verify the following identities (distribution laws) via truth table or by giving a short justification: A ? (B ? C) ? (A ? B) ? (A ? C)

A ? (B ? C) ? (A ? B) ? (A ? C).

2) Verify the following identities (de Morgans Laws) via truth table or by giving a short justification:

(A ? B) ? (A) ? (B) (A ? B) ? (A) ? (B).

3) Someone hands you a small stack of cards. Each card has a letter on one side, and a number on the other. They tell you, Each card with a vowel on one side has an even number on the other. Dealing out the first four cards, you see an A, a 7, a 10, and a B.

What does the persons rule tell you about the hidden side of each card?

If you want to check or verify the persons rule by flipping over a card or cards, which cards should you

flip, and what should you conclude from the reverse side?

4) Find a satisfying assignment for the following, or show that one does not exist.

(A ? B ? C) ? (A ? B ? C) ? (A ? B ? C). (48)

5) Verify the following as true or provide a counter example:

(A xor B) ? (A ? B). (49)

6) Answer the following, justifying your answer logically.

Allmenmustdie. Iamnotaman. MustIdie? Allmenmustdie. Imustdie. AmIaman? All men must die. I must not die. Must I die? All men must die. Must Socrates die?

All men must die. John Tucker must die. Is John Tucker Socrates?

10) Argue that modus ponens is actually just a special case of the resolution inference rule.

11) It can be argued that the resolution inference rule is in fact complete, in the sense that it is the only rule needed to infer everything that can be inferred. Why might other inference rules (not just modus ponens) be useful to know?

12) Suppose that the following premises are granted as an initial knowledge base: B ? C, B ? C, A ? B, A ? C, A ? B ? C (50)

We might attempt to infer that A is true, via contradiction, in the following way. Suppose an additional premise that A is true, and derive a contradiction using a general resolution inference rule:

If P1 ?P2 ?...?Pn and Pi, then P1 ?...?Pi?1 ?Pi+1 ?...Pn.

Show your steps, what you conclude along the way, and identify the final contradiction. Conclude, from this contradiction, that A must be false.

13) Consider the following statement: where A(x) is the statement that x is made of cheese, and B(x) is the statement that x orbits the Earth. Let

the domain of interest be the set of satellites in orbit around the earth. Is P true?

14) Consider the following statement, where the domain of interest is the integers:

?n : n not divisible by 3 =? n2 gives a remainder of 1 when divided by 3.. (52)

What would the initial step / formulation of a direct proof look like? What would the initial step / formulation of a proof by contrapositive look like? What would the initial step / formulation of a proof by contradiction look like? What would the inductive step of a proof by induction look like? Which of these approaches seems most promising? Why?

An alternative approach might be to consider proof by cases. In particular, for any n, n gives a remainder of 0, 1, or 2 when divided by 3. By considering these three cases separately, prove the claim for a given n.

15) Prove that over the domain of non-negative integers, ?n : n2 + n is even. (53)

Can you construct a proof by minimal counter example? What is the best approach to take here?

16) ConsideragaintheFibonaccinumbers,definedbythesequencef(0)=1,f(1)=1,andf(n+2)=f(n)+f(n+1) for n ? 0. In the sections above, we proved that f(n) ? 2n for all n. What is the smallest positive number ? you can find such that the proof can be adapted to show

?n ? 0 : f(n) ? ?n? (54)

17) Show that for n ? 3 over the set of positive integers, we have

1 + 1 + 1 + . . . + 1 ? 2 ln(n). (55) 123 n

You may find the inequality x ? ?2 ln(1 ? x) for 0 < x < 1 useful here.

18) Suppose that cats are sold in sets of 3 or sets of 5. Show that for any n ? 8, someone can buy exactly n cats.