**Propositional Logic**

- Write truth tables for , , and .
- Using truth tables, prove the following equivalences: , , , .

**Sets and Set Operations**

- List the elements of the power set of { a, b, c }.
- If X = { 0, 1, 2, 3, 4, 5 } and Y = { 2, 4, 5, 8, 22 }, find , , and .
- Let our universal set be . If , find .
- Prove that, if A and B are sets, and .
- Prove that, if , then and .
- Prove that .
- Prove that .
- Prove that .
- Prove that if , then .

**Functions**

- Find a bijection between the sets and (remember that is the power set of X, the collection of all subsets of X).
- Find a bijection between the sets and (that is, the set with one more element -1 tacked on).
- Determine if the following functions are injections, surjections, both (bijections) or neither:
- defined by
- defined by
- defined by
- defined by .
- defined by .

**Relations**

- Let R be a relation on the set defined so that if and only if the ones digit of x is greater than or equal to the ones digit of y. Find an example of two numbers x and y such that . Determine if this relation is symmetric, anti-symmetric, reflexive, transitive, and/or total. (It may be none of these, it may be more than one of these. Refer to homework 2 for the definitions of these properties.)
- Let and define the relation R on X as follows: . Determine if this relation is symmetric, anti-symmetric, transitive and/or total.
- Define the relation R on the set of natural numbers as follows: is a multiple of . Show that R is an equivalence relation (that is, that R is reflexive, symmetric, and transitive). Find numbers a and b so that .

**Predicate Logic**

- Suppose our universe is . Suppose P(x, y) is true if x < y and Q(x, y, z) is true if xy = z. Determine if the following statements are true or false and explain why:
- .
- .
- .

- Find the negations of the following statements and determine if the original statement or the negation is true if the universe is :
- .
- .
- .

**Proof by Induction**

In some of these, the base case may be 1, and in some, the base case may be 0.

- Prove, by induction, that (The sum of the first odd numbers is ; you may want to make a table first to find this sum for the first few odd numbers).
- Prove, by induction, that for any n, is a multiple of 2 (in other words, it’s an even number).
- Prove, by induction, that (we did this one in class, but try it again on your own).
- Prove, by induction, that .

**Logic Puzzles**

- You are on an island where everyone is either a knight (who always tells the truth) or a knave (who always lies). You meet two people, A and B. A says “B is a knight.” B says “The two of us are of opposite types.” Determine the identities of A and B.
- You are on an island where everyone is either a knight (who always tells the truth) or a knave (who always lies). You meet two people, A and B. A says “We are both knaves.” Determine the identities of A and B.
- You are on an island where everyone is either a knight (who always tells the truth) or a knave (who always lies). You meet two people, A and B. A says “We are the same (either both of us are knights or both of us are knaves).” B says “The two of us are of opposite types.” Determine the identities of A and B.