# Exam #1 Review Problems

Propositional Logic

1. Write truth tables for $(p \rightarrow q) \wedge (q \rightarrow \lnot p)$ $(p \wedge q) \vee (\lnot p \rightarrow \lnot q)$, and $(p \wedge q) \rightarrow (q \vee r)$.
2. Using truth tables, prove the following equivalences: $p \rightarrow q \equiv \lnot p \vee q$, $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$, $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$, $p \vee q \equiv \lnot p \rightarrow q$.

Sets and Set Operations

1. List the elements of the power set of { a, b, c }.
2. If X = { 0, 1, 2, 3, 4, 5 } and Y = { 2, 4, 5, 8, 22 }, find $X \cap Y$, $X \cup Y$, $X \setminus Y$ and $Y \setminus X$.
3. Let our universal set be $\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$. If $A = \{ 1, 2, 4, 8 \}$, find $\overline{A}$.
4. Prove that, if A and B are sets, $A \subseteq A \cup B$ and $A \cap B \subseteq A$.
5. Prove that, if $B \subseteq A$, then $A = A \cup B$ and $B = A \cap B$.
6. Prove that $A \setminus B = A \cap \overline{B}$.
7. Prove that $\overline{A \cup B} = \overline{A} \cap \overline{B}$.
8. Prove that $\overline{A \cap B} = \overline{A} \cup \overline{B}$.
9. Prove that if $A \subseteq B$, then $\overline{B} \subseteq \overline{A}$.

Functions

1. Find a bijection between the sets $\{ 0, 1, 2, 3 \}$ and $\mathcal{P}(\{ a, b \})$ (remember that $\mathcal{P}(X)$ is the power set of X, the collection of all subsets of X).
2. Find a bijection between the sets $\mathbb{N}$ and $\{-1, 0, 1, 2, 3, \ldots \}$ (that is, the set $\mathbb{N}$ with one more element -1 tacked on).
3. Determine if the following functions are injections, surjections, both (bijections) or neither:
• $f : \mathbb{N} \to \mathbb{Z}$ defined by $f(n) = n^2$
• $g : \mathbb{Z} \to \mathbb{Z}$ defined by $g(n) = n^2$
• $h : \mathbb{R} \to \mathbb{R}$ defined by $h(x) = x^2$
• $F : \mathbb{N} \to \mathbb{N}$ defined by $F(n) = n + 1$.
• $G : \mathbb{Z} \to \mathbb{Z}$ defined by $G(n) = n + 1$.

Relations

1. Let R be a relation on the set $\mathbb{N}$ defined so that $(x, y) \in R$ 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 $(x, y) \in R$. 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.)
2. Let $X = \mathcal{P}(\{0, 1, 2, 3, 4, 5 \})$ and define the relation R on X as follows: $R = \{ (A, B) : A \subseteq B \}$. Determine if this relation is symmetric, anti-symmetric, transitive and/or total.
3. Define the relation R on the set of natural numbers as follows: $R = \{ (a, b) : a - b$ is a multiple of $5 \}$. Show that R is an equivalence relation (that is, that R is reflexive, symmetric, and transitive). Find numbers a and b so that $(a, b) \not \in R$.

Predicate Logic

1. Suppose our universe is $\mathbb{Z}$. 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:
• $\forall z \forall x \exists y Q(x, y, z)$.
• $\exists x \forall y (x = y \vee P(x, y))$.
• $\forall x \exists y (\lnot x = y \wedge \lnot P(x, y))$.
2. Find the negations of the following statements and determine if the original statement or the negation is true if the universe is $\mathbb{N}$:
• $\forall x \exists y (x + y = 0)$.
• $\forall x \exists y \lnot (x + y = y)$.
• $\forall x \exists y (x + x = x \vee xy > 0)$.

Proof by Induction

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

1. Prove, by induction, that $1 + 3 + 5 + \ldots + (2n - 1) = n^2$ (The sum of the first $n$ odd numbers is $n^2$; you may want to make a table first to find this sum for the first few odd numbers).
2. Prove, by induction, that for any n, $3^n - 1$ is a multiple of 2 (in other words, it’s an even number).
3. Prove, by induction, that $1 + 2 + 4 + \ldots + 2^{n-1} = 2^n - 1$ (we did this one in class, but try it again on your own).
4. Prove, by induction, that $1 + 10 + 100 + \ldots + 10^{n-1} = \frac{10^n - 1}{9}$.

Logic Puzzles

1. 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.
2. 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.
3. 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.