Practice Midterm 1

Practice Exam for Midterm 1

Time calibration note: Our midterm exam is 3 hours. This practice exam might be a little bit on the long side. It has one more question than the real previous exam that it is based on, because I wanted you to see examples of different question formats that are commonly used. I cut a few sub-parts here and there to balance out, but I'm not sure the cuts totally compensate for the added question.

Problem 1: Truth Tables

In this problem, we will examine how truth tables can be used to define new, made-up logical connectives. You'll be asked to discover ways to translate between our traditional connectives and the made-up ones.

As an example, consider this truth table for the made-up connective $X$:

$p$	$q$	$r$		$X(p,q,r)$
F	F	F		F
F	F	T		F
F	T	F		F
F	T	T		F
T	F	F		F
T	F	T		F
T	T	F		T
T	T	T		T

In this example, we can rewrite any proposition $X(p,q,r)$ in terms of our traditional propositional connectives as: $X(p,q,r) \equiv (p \land q \land r) \lor (p \land q \land \lnot r)$ (a simpler translation is possible, but this one is easier to map onto how we derived it from looking at the input combinations that give us T output rows in the truth table). And we can rewrite the traditional connective $\land$ as: $p \land q \equiv X(p,q,\top)$. Another valid translation is: $p \land q \equiv X(p,q,p)$.

Now consider this truth table for the made-up connective $Y$:

$p$	$q$	$r$		$Y(p,q,r)$
F	F	F		T
F	F	T		F
F	T	F		F
F	T	T		F
T	F	F		F
T	F	T		F
T	T	F		T
T	T	T		T

For the rest of this problem, you'll be translating between traditional propositional logic connectives and this new $Y$ connective.

1. Rewrite the proposition $Y(p,q,r)$ in terms of our traditional connectives (i.e., your response should use only $p, q, r, \land, \lor, \lnot, \rightarrow, \top, \bot$, and parentheses).

2. Rewrite the proposition $\lnot p$ in terms of the new connective $Y$ (i.e., your response should use only $p, Y, \top, \bot$, and parentheses).

3. Rewrite the proposition $p \to q$ in terms of the new connective $Y$ (i.e., your response should use only $p, q, Y, \top, \bot$, and parentheses).

Problem 2: Set Differences and Subsets

Theorem: For all sets $A$, $B$, and $C$, if $A \cap C = \emptyset$, then $A - (B - C) \subseteq (A - B) - C$.

Although there are a number of ways to approach this problem, we ask you to demonstrate your understanding of the Direct Proof template approach outlined in Pset 1.

1. (2pts) Write the first sentence of this proof (the "Assume" step).

2. (2pts) Write the second sentence of this proof (the "Want to Show" step).

3. (5pts) Now write the complete proof. Please do include your two sentences from above, so it reads as a complete proof.

Problem 3: Rational Numbers

You've already been introduced to several useful sets of numbers: $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{R}$, the even integers, and the odd integers. We've also proved things about these sets, for example that if a number is even, then its square is also even. Now we introduce the rational numbers, $\mathbb{Q}$, which are defined as the set of real numbers that can be written as $\frac{p}{q}$ for some $p \in \mathbb{Z}$ and $q \in \mathbb{Z}$, where $q \neq 0$.

1. (3pts) Use set builder notation to write the set of all rational numbers where the numerator is even and the denominator is odd, without using the word "even" or the word "odd."

2. (4pts) We will formally define the reciprocal of a rational number $r = \frac{p}{q}$ to be $\frac{q}{p}$. Disprove the following by counterexample: for all rational numbers $r$, the reciprocal of $r$ is also a rational number.

3. (8pts) Use Direct Proof to prove the following: for all numbers $a$ and $b$, if $a$ and $b$ are rational numbers, then $a^2 + b^2$ is also a rational number. You may cite this fact as Lemma 1: the product of nonzero integers is nonzero.

Problem Four: First-Order Logic Translantions

In each of the following, someone has attempted to write a statement in first-order logic that expresses the indicated sentence. The translations may or may not be accurate translations of the original sentence, or its negation. The statements use the following predicates:

• $x \in y$ which states that $x$ is an element of $y$, and
• $Set(x)$, which states that $x$ is a set.

For each of the following pairs of statements, state whether the sentence and the first-order logic statement are: (A) EQUIVALENT to each other (correctly translated), (B) NEGATION of each other (correctly executed transalation and negation), or (C) NEITHER equivalent nor negation of each other (i.e., some error). You do not need to justify your answer.

1. (2pts) Are these two statements equivalent, negations of each other, or neither?

   • Statement 1: "There is a set S where every element of S is also a subset of S."
   • Statement 2: $\exists S. (Set(S) \land \forall T. (T \in S \rightarrow Set(T) \land \forall y. (y \in T \rightarrow y \in S) ) )$

2. (2pts) Are these two statements equivalent, negations of each other, or neither?

   • Statement 1: "There is a set S where exactly two subsets of S are also elements of S."
   • Statement 2: $\exists S. (Set(S) \land \exists T. \exists U. (T \in S \land U \in S \land Set(T) \land Set(U) \land \forall x.(x \in T \rightarrow x \in S) \land \forall x. (x \in U \rightarrow x \in S)))$

3. (2pts) Are these two statements equivalent, negations of each other, or neither?

   • Statement 1: "There is a set S where every subset of S is also an element of S."
   • Statement 2: $\forall S. (\exists T. (Set(T) \land \forall x. (x \in T \rightarrow x \in S) \land T \not \in S) \lor \lnot Set(S))$

Now, we consider whether these statements are true or false.

4. (3pts) "There is a set S where every element of S is also a subset of S." Prove this statement is true by giving an example, or write "no such set" (you do not need to write a disproof).

5. (3pts) "There is a set S where at least two elements of S are also subsets of S." Prove this statement is true by giving an example, or write "no such set" (you do not need to write a disproof).

SOLUTIONS

Problem 1 Solution:

Part i: $(p \land q \land r) \lor (p \land q \land \lnot r) \lor (\lnot p \land \lnot q \land \lnot r)$

Part ii: $Y(\bot, \bot, p)$

Part iii: $Y(Y(\bot, \bot, p), Y(\bot, \bot, p), Y(\bot, \bot, q))$

Problem 2 Solution:

Part i: Pick arbitrary sets $A$, $B$, and $C$, where $A \cap C = \emptyset$.

Part ii: We want to show that $A - (B - C) \subseteq (A - B) - C$.

Part iii: Pick arbitrary sets $A$, $B$, and $C$, where $A \cap C = \emptyset$. We want to show that $A - (B - C) \subseteq (A - B) - C$. Pick an arbitrary $x \in A - (B - C)$. We want to show that $x \in (A - B) - C$. In other words, we need to show three things: $x \in A$, $x \not \in B$, and $x \not \in C$. Since $x \in A - (B - C)$, we know that $x \in A$, and that $x \not \in B$ or $x \in C$. This shows that $x \in A$. Since $x \in A$ and $A \cap C = \emptyset$, we know that $x \not \in C$. Since $x \not \in B$ or $x \in C$, and we already know that $x \not \in C$, it must be that $x \not \in B$, which is what we wanted to show. $\qed$

Problem 3 Solution:

Part i: {$ \frac{2k}{2m + 1} \mid k, m \in \mathbb{Z}$}

Part ii: Consider $r = \frac{0}{1}$, which is rational because $0, 1 \in \mathbb{Z}$, and $1 \neq 0$. But the reciprocal, $\frac{1}{0}$, is not rational, because the denominator is 0.

Part iii: Pick arbitrary rational numbers $a$ and $b$. We want to show that $a^2 + b^2$ is rational. Since $a$ is rational, we know there exist integers $p$ and $q$ such that $a = \frac{p}{q}$, and $q \neq 0$. Similarly, since $b$ is rational, we know there exist integers $s$ and $t$ such that $b = \frac{s}{t}$, and $t \neq 0$. We can substitute these into the sum of squares of $a$ and $b$ as follows:

$a^2 + b^2 = (\frac{p}{q})^2 + (\frac{s}{t})^2$

$= \frac{p^2}{q^2} + \frac{s^2}{t^2}$

$= \frac{p^2t^2}{q^2t^2} + \frac{s^2q^2}{t^2q^2}$

$= \frac{p^2t^2 + s^2q^2}{q^2t^2}$.

So we see that $a^2 + b^2$ can be written as $\frac{c}{d}$, where $c = p^2t^2 + s^2q^2$ and $d = q^2t^2$. We further observe that because $p,q,s,t \in \mathbb{Z}$, and integers are closed under addition and multiplication, then $c,d \in \mathbb{Z}$. Finally, because $q \neq 0$ and $t \neq 0$, $d \neq 0$. So $a^2 + b^2$ is rational. $\qed$

Problem 4 Solution:

Part i: (A)

Part ii: (C)

Part iii: (B)

Part iv: There are many correct solutions. Here are 3 examples: $\emptyset$, {$\emptyset$}, {$\emptyset$, {$\emptyset$}}

Part v: There are many correct solutions. Here are 3 examples: {$\emptyset$, {$\emptyset$}}, {$\emptyset$, 1, {1}}, {1, 2, {1}, {2}}