Exam #1 Review Problems

Propositional Logic

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)$ .
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

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 $X \cap Y$ , $X \cup Y$ , $X \setminus Y$ and $Y \setminus X$ .
Let our universal set be $\{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 \}$ . If $A = \{ 1, 2, 4, 8 \}$ , find $\overline{A}$ .
Prove that, if A and B are sets, $A \subseteq A \cup B$ and $A \cap B \subseteq A$ .
Prove that, if $B \subseteq A$ , then $A = A \cup B$ and $B = A \cap B$ .
Prove that $A \setminus B = A \cap \overline{B}$ .
Prove that $\overline{A \cup B} = \overline{A} \cap \overline{B}$ .
Prove that $\overline{A \cap B} = \overline{A} \cup \overline{B}$ .
Prove that if $A \subseteq B$ , then $\overline{B} \subseteq \overline{A}$ .

Functions

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).
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).
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

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.)
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.
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

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:
- $\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))$ .
Find the negations of the following statements and determine if the original statement or the negation is true if the universe is :
- $\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.

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).
Prove, by induction, that for any n, $3^n - 1$ is a multiple of 2 (in other words, it’s an even number).
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).
Prove, by induction, that $1 + 10 + 100 + \ldots + 10^{n-1} = \frac{10^n - 1}{9}$ .

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.

Athar Abdul-Quader