Tutorial 1 Solutions

Question 1 Solutions:

For each of the following, write a propositional formula that accurately represents the given English statement. Use the propositions $p$, $q$, $r$, $s$ and $t$ as needed, where: $p$ : “The program compiles.” $q$: “The input is valid.” $r$ : “The output is correct.” $s$: “The function is efficient.” $t$ : “The algorithm terminates.”

1. “If the program compiles but the input is not valid, then the output is not correct.”

Solution

$(p\wedge \neg q)\to \neg r$

1. Break down the components: “The program compiles”: $p$ “The input is not valid”: $\neg q$ “The output is not correct”: $\neg r$
2. Combine using logical operators: “The program compiles but the input is not valid” is $p\wedge \neg q$ “If … then …” translates to   $\to$  

2. “The function is efficient if and only if (both the algorithm terminates and the output is correct).”

Solution

$s\leftrightarrow (t\wedge r)$ or $(s\to (t\wedge r))\wedge ((t\wedge r)\to s)$

1. Break down the components: “The function is efficient”: $s$ “The algorithm terminates”: $t$ “The output is correct”: $r$ “Both … and …” is $\wedge$
2. Combine using logical operators: “The algorithm terminates and the output is correct” is $t\wedge r$ “If and only if” translates to an implication in both directions, ie. $(p\to q)\wedge (q\to p)$

3. “((The program compiles and the input is valid) or the function is efficient), and the algorithm does not terminate.”

Solution

$((p\wedge q)\vee s)\wedge \neg t$

1. Break down the components: “The program compiles”: $p$ “The input is valid”: $q$ “The function is efficient”: $s$ “The algorithm does not terminate”: $\neg t$ “And”: $\wedge$, “Or”: $\vee$, “But”: treated as $\wedge$ in context.
2. Combine using logical operators: “The program compiles and the input is valid” is $p\wedge q$ “The program compiles and the input is valid, or the function is efficient” is $(p\wedge q)\vee s$ “But the algorithm does not terminate” adds $\wedge \neg t$
3. The parentheses are necessary!

4. “If the program compiles, then ((either the input is valid and the output is correct), or the algorithm does not terminate).”

Solution

$p\to ((q\wedge r)\vee \neg t)$

1. Break down the components: “The program compiles”: $p$ “The input is valid”: $q$ “The output is correct”: $r$ “The algorithm does not terminate”: $\neg t$ “Either … or …” translates to $\vee$
2. Combine using logical operators: “The input is valid and the output is correct” is $q\wedge r$ “Either the input is valid and the output is correct, or the algorithm does not terminate” is $(q\wedge r)\vee \neg t$ “If … then …” translates to   $\to$

5. “The function is efficient if and only if ((the program compiles and the input is valid), or (if the output is correct implies that the algorithm terminates)).”

Solution

$s\leftrightarrow (p\wedge q)\vee (r\to t)$

1. Break down the components: “The function is efficient”: $s$ “The program compiles”: $p$ “The input is valid”: $q$ “The output is correct”: $r$ “The algorithm terminates”: $t$ “If … then …” translates to   $\to$ , “If and only if” translates to  $\leftrightarrow$.
2. Combine using logical operators: “The program compiles and the input is valid” is $p\wedge q$ “The output is correct implies that the algorithm terminates” is $r\to t$ “The function is efficient if and only if” translates to $s\leftrightarrow$
3. Combine everything: $s\leftrightarrow (p\wedge q)\vee (r\to t)$

---

Question 2: Negating Propositional Formulae [Graded Participation]

Part A Solutions:

Draw two truth tables to verify that:

1. $\neg (p\to q)$ is logically equivalent to $p\wedge \neg q$.
2. $\neg (p\wedge q)$ is logically equivalent to $\neg p\vee \neg q$.

$p$	$q$	$p\to q$	$\neg (p\to q)$	$\neg q$	$p\wedge \neg q$
$true$	$true$	$true$	$false$	$false$	$false$
$true$	$false$	$false$	$true$	$true$	$true$
$false$	$true$	$true$	$false$	$false$	$false$
$false$	$false$	$true$	$false$	$true$	$false$

Hence, $\neg (p\to q)$ and $p\wedge \neg q$ are logically equivalent.

$p$	$q$	$p\wedge q$	$\neg p$	$\neg q$	$\neg (p\wedge q)$	$\neg p\vee \neg q$
$true$	$true$	$true$	$false$	$false$	$false$	$false$
$true$	$false$	$false$	$false$	$true$	$true$	$true$
$false$	$true$	$false$	$true$	$false$	$true$	$true$
$false$	$false$	$false$	$true$	$true$	$true$	$true$

Hence, $\neg (p\wedge q)$ and $\neg p\vee \neg q$ are logically equivalent.

Part B Solutions:

To see how these equivalences may be used, let $p$ be the statement “It is raining” and let $q$ be the statement “It is cold”. Match each of the following statements with its logically equivalent; you might rewrite each statement using $p$ and $q$ to assist you.

Statements:

1. It is not the case that it is raining or cold.
2. It is not raining or it is not cold.
3. It is not raining and it is not cold.
4. It is not the case that it is both raining and cold.

Rewriting the 4 statements using $p$ and $q$, we get:

1. $\neg (p\vee q)$
2. $\neg p\vee \neg q$
3. $\neg p\wedge \neg q$
4. $\neg (p\wedge q)$

Using De Morgan’s Laws, statements 1 and 3 and logically equivalent, and statements 2 and 4 are logically equivalent.

Question 3 Solutions:

Aiken promises Dueet that if Dueet watches anime with him, then Aiken will treat Dueet to a pizza dinner.

a. How would you write this sentence in propositional logic?

Solution

We let the proposition “Dueet watches anime with Aiken” to be $p$ and “Aiken treats Dueet to a pizza dinner” to be $q$.

Then we can write this sentence as $p\to q$.

b. Determine whether the promise has been broken in each of the following cases:

1. Dueet watches anime with Aiken, and Aiken treats Dueet to a pizza dinner.
2. Dueet watches anime with Aiken, but Aiken does not treat Dueet to a pizza dinner.
3. Dueet does not watch anime with Aiken, and Aiken treats Dueet to a pizza dinner.
4. Dueet does not watch anime with Aiken, and Aiken does not treat Dueet to a pizza dinner.

Solution

In the examples we have seen truth tables where different truth values of $p$ and $q$ lead to a different truth value of $p\to q$. To make sense of this, we can look at this example.

Case 1 definitely doesn’t break the promise. Dueet watches anime, and Aiken keeps his promise. Case 2 breaks the promise because Dueet does his part and watches anime with Aiken, but Aiken didn’t buy pizza like he had promised. Up to now it’s all very intuitive.

Case 4 doesn’t break the promise either; since Dueet didn’t do his part, he gets no pizza. But Case 3 doesn’t break the promise either!

Why is this so? In the notes we said that in an implication, we don’t really care about what happens when the antecedent is false. An implication, or Aiken’s promise, only guarantees what happens when the antecedent is true. If we know $p$ is true, we know that $q$ will follow through. It doesn’t promise us anything about what happens when the antecedent $p$ is false!

Another example would be buying things from a store. You could pay for a soda, and get the soda (Case 1). Or don’t pay for the soda, and leave (Case 4). Or the owner might give it to you as a free gift, and you didn’t pay for the soda (Case 3). The only case that is upsetting is when you pay but you don’t get the soda (Case 2).

---

Question 4 Solutions:

Let:

• $R=\{A,B,C\}$ be the set of circles,
• $S=\{E,G,H,J\}$ be the set of squares,
• $T=\{D,F,I\}$ be the set of triangles, and
• $U=\{A,B,C,D,E,F,G,H,I\}$ be the set containing all the objects.

You are also given the following predicates, which you may use freely in your answers:

• $Above(x,y)$ is true when object $x$ is above object $y$ in the grid.
• $Blue(x)$ is true when object $x$ is blue.
• $Grey(x)$ is true when object $x$ is grey.
• $Orange(x)$ is true when the object $x$ is orange.
• $Circle(x)$ is true when the object $x$ is a circle
• $Square(x)$ is true when $x$ is a square object.
• $Triangle(x)$ is true when $x$ is a triangular object.

Determine whether the following statements are true or false for the picture: 5. $\exists u\in U[Orange(u)\wedge Triangle(u)]$ 6. $\forall u\in U[Circle(u)\to Blue(u)]$ 7. $\forall s\in S,\exists t\in T[Above(t,s)]$ 8. $\forall r\in R,\forall s\in S[Above(r,s)]$ 9. $\exists u\in U,\forall r\in R[Above(u,r)]$ 10. $\exists r\in R,\exists t\in T[Grey(r)\vee \neg Orange(t)]$

Solution:

1. $\exists u\in U[Orange(u)\wedge Triangle(u)]$ True; let that object $u$ be the orange triangle $F$.

2. $\forall u\in U[Circle(u)\to Blue(u)]$ False; consider letting the object $u$ be the orange circle $b$.

   • The predicate $Circle(b)$ is true.
   • The predicate $Blue(b)$ is false.
   • But, $Circle(b)\to Blue(b)$ evaluates to false. Since $\forall u\in U[Circle(u)\to Blue(u)]$ is stating that: “For every object $u$, if $u$ is a circle then $u$ is blue”, and we have found a circle that is not blue, the statement is false.

3. $\forall s\in S,\exists t\in T[Above(t,s)]$ True; no matter which square $s$ is picked, we can always find at least one triangle $t$ such that $t$ lies above $s$ in the grid: consider triangle $d$, it is above all squares.

4. $\forall r\in R,\forall s\in S[Above(r,s)]$ True; no matter which circle $r$ and which square $s$ are picked from the sets of circles and squares, $r$ will lie above $s$ in the grid, since all the circles lie above all the squares.

5. $\exists u\in U,\forall r\in R[Above(u,r)]$ False; no matter which object $u$ is picked, we can always find at least circle $r$ such that $u$ does not lie above $r$, since there is no object that lies above the circle $a$.

6. $\exists r\in R,\exists t\in T[Grey(r)\vee \neg Orange(t)]$ True; consider letting the object $r$ be the blue circle $a$ and letting the object $t$ be the grey triangle $d$.

   • The predicate $Grey(a)$ is false.
   • The predicate $Orange(d)$ is false, and so $\neg Orange(d)$ is true.
   • Thus, $Grey(a)\vee \neg Orange(d)$ evaluates to true.

---

Question 5 Solutions:

Consider the following first order logic statements:

1. $\exists x\in D[P(x)\wedge Q(x)]$
2. $\forall x\in D[P(x)\vee Q(x)]$
3. $\forall x\in D,\exists y\in E[P(x,y)\wedge Q(y)]$
4. $\exists x\in D,\forall y\in E[P(x,y)\to Q(y)]$

Write the negation for each of the statements.

Part 1 Solutions:

Solution

1. Put a negation sign outside: $\neg (\exists x\in D[P(x)\wedge Q(x)])$
2. Using negation of an existential quantifier: $\forall x\in D[\neg (P(x)\wedge Q(x)\left)\right]$
3. Using De Morgan’s Law: $\forall x\in D[\neg P(x)\vee \neg Q(x)]$

Further

Sometimes we may be confused when we see a bunch of mathematical symbols. It certainly takes time to familiarise yourselves with FOL. When it comes to negating these statements, one way to think about it is to translate it into English.

Statement 1 is an existential statement. What is means, essentially, is that there exists some $x$ in set $D$ such that both $P(x)$ and $Q(x)$ is true. To negate it, think of the opposite.

If there exists NO $x$ in set $D$ such that $P(x)$ and $Q(x)$ are both true, this means that for ALL $x$ in set $D$, it either does not satisfy $P(x)$, or it doesn’t satisfy $Q(x)$. There is just no $x$ that satisfies both at the same time.

And how would we then write this into FOL? We would write $\forall x\in D[\neg P(x)\vee \neg Q(x)]$.

Part 2 Solutions:

Solution

1. Put a negation sign outside: $\neg (\forall x\in D[P(x)\vee Q(x)\left]\right)$
2. Using negation of an existential quantifier: $\exists x\in D[\neg (P(x)\vee Q(x)\left)\right]$
3. Using De Morgan’s Law: $\exists x\in D[\neg P(x)\wedge \neg Q(x)]$

Further

Statement 2 is a universal statement that says: Every $x$ in set $D$ satisfies $P(x)$ or $Q(x)$ (or both), either one of them is fine. To negate it, think of the opposite.

NOT every $x$ in set $D$ satisfies at least one of $P(x)$ or $Q(x)$. This means that there exists one (or more) $x$ that does not satisfy both $P(x)$ and $Q(x)$.

And then we write this into FOL, $\exists x\in D[\neg P(x)\wedge \neg Q(x)]$.

Part 3 Solutions:

Solution

1. Put a negation sign outside: $\neg (\forall x\in D,\exists y\in E[P(x,y)\wedge Q(y)\left]\right)$

2. Using negation of a universal quantifier: $\exists x\in D,\neg (\exists y\in E[P(x,y)\wedge Q(y)\left]\right)$

3. Using negation of an existential quantifier: $\exists x\in D,\forall y\in E[\neg (P(x,y)\wedge Q(y)\left)\right]$

4. Using De Morgan’s Law: $\exists x\in D,\forall y\in E[\neg P(x,y)\vee \neg Q(y)]$

Further

Statement 3 is a little more complex. What it means is that for every $x$ in set $D$, there exists some corresponding $y$ in set $E$, such that both $P(x,y)$ and $Q(y)$ are true. To negate this, think of the opposite.

NOT every $x$ in set $D$ has some corresponding $y$ in set $E$ such that both $P(x,y)$ and $Q(y)$ are true. This means that there should exist (at least one) $x$ in set $D$ where you CANNOT find any $y$ in set $E$ such that both $P(x,y)$ and $Q(y)$ are true. In other words, there exists $x$ in set $D$ where for ALL $y$ in set $E$, $P(x,y)$ and $Q(y)$ are not true at the same time (ie. at least one of them is not true), so either $P(x,y)$ is not true, or $Q(y)$ is not true, or both.

Now we just write this into FOL. There exists $x$ in set $D$ where for all $y$ in set $E$, either $P(x,y)$ is not true, or $Q(y)$ is not true. Thus we write $\exists x\in D,\forall y\in E[\neg P(x,y)\vee \neg Q(y)]$.

Part 4 Solutions:

Solution

1. Put a negative sign outside: $\neg (\exists x\in D,\forall y\in E[P(x,y)\to Q(y)\left]\right)$

2. Using negation of an existential quantifier: $\forall x\in D,\neg (\forall y\in E[P(x,y)\to Q(y)\left]\right)$

3. Using negation of a universal quantifier: $\forall x\in D,\exists y\in E[\neg (P(x,y)\to Q(y)\left)\right]$

4. Using implication law: $P(x,y)\to Q(y)\equiv \neg P(x,y)\vee Q(y)$, we replace $P(x,y)\to Q(y)$ with $\neg P(x,y)\vee Q(y)$, thus we write: $\forall x\in D,\exists y\in E[\neg (\neg P(x,y)\vee Q(y)\left)\right]$.

5. Using De Morgan’s Law: $\forall x\in D,\exists y\in E[\neg (\neg P(x,y))\wedge \neg Q(y)]$

6. Double negation: $\neg (\neg P(x,y))\equiv P(x,y)$, thus we get $\forall x\in D,\exists y\in E[P(x,y)\wedge \neg Q(y)]$.

Further

After looking at the statement 3, this one should make more sense. What this statement means is that there exists some $x$ in set $D$ where for all $y$ in set $E$, $P(x,y)\to Q(y)$ is true. To negate this, think of the opposite.

If there exists NO $x$ in set $D$ where for every $y$ in set $E$ satisfies $P(x,y)\to Q(y)$, it means that for every $x$ in set $D$, there has to exist some $y$ in set $E$ that doesn’t satisfy $P(x,y)\to Q(y)$, which means that $P(x,y)\to Q(y)$ is false.

To negate an implication, we use implication law to turn it into something we can work with. So we replace $P(x,y)\to Q(y)$ with $\neg P(x,y)\vee Q(y)$, and then negate it, which gives us $\neg (\neg P(x,y)\vee Q(y))$. Then we use De Morgan’s Law to further simplify into $P(x,y)\vee \neg Q(y)$.

In other words, for every $x$ in set $D$, there exists some $y$ in set $E$, such that $P(x,y)\wedge \neg Q(y)$. Now we just have to translate this into FOL, and we have $\forall x\in D,\exists y\in E[P(x,y)\wedge \neg Q(y)]$.

---

Question 6 Solutions:

Part A Solutions:

1. (True) $\exists x\in \mathbb{N},\forall y\in \mathbb{Z}[x\ne y]$

Explanation

This is a practice on negating multiple quantifiers in the same statement.

1. $\neg (\forall x\in \mathbb{N},\exists y\in \mathbb{Z}[x=y])$
2. $\equiv \exists x\in \mathbb{N},\neg (\exists y\in \mathbb{Z}[x=y])$ (Negation of universal quantifier)
3. $\equiv \exists x\in \mathbb{N},\forall y\in \mathbb{Z},[\neg (x=y)]$ (Negation of existential quantifier)
4. $\equiv \exists x\in \mathbb{N},\forall y\in \mathbb{Z}[x\ne y]$ (Negation of equals)

Deciphering the statement: This statement says that every natural number, is equal to some integer. We know this to be intuitively true, by the definition of the sets of $\mathbb{N}$ and $\mathbb{Z}$.

2. (False) $\exists p,q\in \mathbb{Q}[q\ne p]$

Explanation

This is a practice on negating multiple objects in the same quantifier.

1. $\neg (\forall p,q\in \mathbb{Q}[q=p])$
2. $\equiv \exists p,q\in \mathbb{Q}[\neg (q=p)]$ (Negation of universal quantifier)
3. $\equiv \exists p,q\in \mathbb{Q}[q\ne p]$ (Negation of equals)

Deciphering the statement: This statement says any 2 rational numbers are equal. We know this to be false.

3. (False) $\exists a,b,c\in \mathbb{Z}[a\ne b\wedge a\ne c]$

Explanation

This is a practice on applying De Morgan’s Law.

1. $\neg (\forall a,b,c\in \mathbb{Z}[a=b\vee a=c])$
2. $\equiv \exists a,b,c\in \mathbb{Z}[\neg (a=b\vee a=c)]$ (Negation of universal quantifier)
3. $\equiv \exists a,b,c\in \mathbb{Z}[a\ne b\wedge a\ne c]$ (De Morgan’s Law and negation of equals)

Deciphering the statement: This statement says when you pick any 3 integers, one of the integers you picked will be equal to one of the other 2 integers.

This is false.

4. (True) $\exists x\in \mathbb{Z},\forall y,z\in \mathbb{Q}[x\ne 3y\vee x\ne 5z]$

Explanation

This is another practice on applying De Morgan’s Law, but with a little more complexity.

1. $\neg (\forall x\in \mathbb{Z},\exists y,z\in \mathbb{Q}[x=3y\wedge x=5z])$
2. $\equiv \exists x\in \mathbb{Z},\neg (\exists y,z\in \mathbb{Q}[x=3y\wedge x=5z])$ (Negation of universal quantifier)
3. $\equiv \exists x\in \mathbb{Z},\forall y,z\in \mathbb{Q}[\neg (x=3y\wedge x=5z)]$ (Negation of existential quantifier)
4. $\equiv \exists x\in \mathbb{Z},\forall y,z\in \mathbb{Q}[x\ne 3y\vee x\ne 5z]$ (De Morgan’s Law and negation of equals)

Deciphering the statement: This statement is a little tricker to unpack. It says that every integer, is 3 times of some rational number, and 5 times of another rational number.

This is true, as for any integer $x$, $3\cdot \frac{x}{3}=x$ and $5\cdot \frac{x}{5}=x$, and we know that $\frac{x}{3}$ and $\frac{x}{5}$ are rational numbers.

5. (False) $\forall p,q\in \mathbb{Z},\exists r\in \mathbb{Z}[p+q=r]$

Explanation

This is an example of when negating a statement can make it easier to understand.

1. $\neg (\exists p,q\in \mathbb{Z},\forall r\in \mathbb{Z}[p+q\ne r])$
2. $\equiv \forall p,q\in \mathbb{Z},\neg (\forall r\in \mathbb{Z}[p+q\ne r])$ (Negation of existential quantifier)
3. $\equiv \forall p,q\in \mathbb{Z},\exists r\in \mathbb{Z}[\neg (p+q\ne r)]$ (Negation of universal quantifier)
4. $\equiv \forall p,q\in \mathbb{Z},\exists r\in \mathbb{Z}[p+q=r]$ (Negation of equals)

Deciphering the statement: This statement is not so easy to intuitively determine if it is true just by looking at the original statement, so we will instead consider the negation.

The negation says, any 2 integers added together is equal to another integer.

We know this to be true. Therefore, the original statement must be false.

In contrast, the original says, there are 2 integers that are not equal to any integer when added together. Not that it is impossible to tell this is false, but consider how much easier negating the statement made it to digest the statement.

6. (False) $\exists a,b\in \mathbb{Z}[a^2=b^2\wedge a\ne b]$

Explanation

This is a practice on negating implication statements.

1. $\neg (\forall a,b\in \mathbb{Z}[a^2=b^2\to a=b])$
2. $\equiv \exists a,b\in \mathbb{Z}[\neg (a^2=b^2\to a=b)]$ (Negation of universal quantifier)
3. $\equiv \exists a,b\in \mathbb{Z}[a^2=b^2\wedge a\ne b]$ (Substitute with a logically equivalent proposition)

Deciphering the statement: This statement says if the squares of 2 integers are equal, the 2 integers are also equal.

This is false as the square of a number and its negative counterpart are equal.

Important to note is the use of a commonly used logical equivalence to substitute away the implication connective, as that is the easiest way to negate them.

Part B Solutions:

1. (True) $\forall a,b\in \mathbb{Z}[a=b\to a^2=b^2]$

Explanation

This is a practice on finding the contrapositive of a simple implication statement.

1. $\forall a,b\in \mathbb{Z}[a^2\ne b^2\to a\ne b]$
2. $\equiv \forall a,b\in \mathbb{Z}[a=b\to a^2=b^2]$ (Substitution of contrapositive form)

Deciphering the statement: This statement says if the squares of 2 integers are not equal, the 2 integers are also not equal.

This might be tricky to justify, so let’s consider the contrapositive.

The contrapositive says that if 2 integers are equal, the squares of the 2 integers are also equal.

Ah, this is significantly easier to justify and imagine.

The contrapositive is thus true, making the original statement true.

2. (True) $\forall p\in \mathbb{Z}[(p>5\wedge p\le 26)\to p\ge 0]$

Explanation

This is a practice on finding the contrapositive of an implication statement with connectives.

1. $\forall p\in \mathbb{Z}[p<0\to (p\le 5\vee p>26)]$
2. $\equiv \forall p\in \mathbb{Z}[\neg (p\le 5\vee p>26)\to p\ge 0]$ (Substitution of contrapositive form)
3. $\equiv \forall p\in \mathbb{Z}[(p>5\wedge p\le 26)\to p\ge 0]$ (De Morgan’s Law)

Deciphering the statement: This statement says that any integer more than 5 and less than equal to 26 must be more than equal to 0.

This statement is true.

Technique of note in this question is the use of De Morgan’s Law even when finding a contrapositive.

3. (True) $\forall x\in \mathbb{Z}(x>5\to \exists y\in \mathbb{N}[x=y])$

Explanation

This is a practice on finding the contrapositive of an implication statement with quantifiers.

1. $\forall x\in \mathbb{Z}(\forall y\in \mathbb{N}[x\ne y]\to x\le 5)$
2. $\equiv \forall x\in \mathbb{Z}(x>5\to \neg (\forall y\in \mathbb{N}[x\ne y]))$ (Substitution of contrapositive form)
3. $\equiv \forall x\in \mathbb{Z}(x>5\to \exists y\in \mathbb{N}[\neg (x\ne y)])$ (Negation of universal quantifier)
4. $\equiv \forall x\in \mathbb{Z}(x>5\to \exists y\in \mathbb{N}[x=y])$ (Negation of equals)

Deciphering the statement: This statement says that any integer and any natural number, if the numbers are not equal, the integer is less than or equal to 5.

This statement is quite confusing to even approach from this angle, so let’s consider the contrapositive.

The contrapositive says that any integer greater than 5 has a natural number equal to it.

Again, this is significantly easier to justify and digest.

The contrapositive is thus true, making the original statement true.

---

Question 7 Solutions [Graded Participation]:

Prove the following statement:

Theorem

$\forall x\in \mathbb{Z}[\neg (even(x)\wedge odd(x))]$

Where we define the predicate $even(x)$ to be: $even(x)\equiv \exists k\in \mathbb{Z}[2k=x]$, and we define the predicate $odd(x)$ to be: $odd(x)\equiv \exists j\in \mathbb{Z}[2j+1=x]$

Solution

Proof:

1. Let $x\in \mathbb{Z}$, arbitrarily chosen.
2. Assume for the sake of contradiction that $even(x)\wedge odd(x)$.
3. $even(x)$. [Specialisation on line 2]
4. $\exists k\in \mathbb{Z}[2k=x]$. [Unpacking definition of $even(x)$]
5. Let $s\in \mathbb{Z}$ be such that $2s=x$. [Existential instantiation on line 2.2]
6. $odd(x)$. [Specialisation on line 2]
7. $\exists j\in \mathbb{Z}[2j+1=x]$. [Unpacking definition of $odd(x)$]
8. Let $t\in \mathbb{Z}$ be such that $2t+1=x$. [Existential instantiation on line 2.5]
9. Then, we have $2s=2t+1$. [Basic algebra, from lines 2.3 and 2.6]
10. $2(s-t)=1$. [Basic algebra]
11. $s-t=\frac{1}{2}$. [Basic algebra]
12. $\neg (s-t\in \mathbb{Z})$. [Basic algebra, from line 2.9]
13. Since $s\in \mathbb{Z}$ and $t\in \mathbb{Z}$, we have $s-t\in \mathbb{Z}$. [Basic algebra, from lines 2.3 and 2.6]
14. $(s-t\in \mathbb{Z})\wedge \neg (s-t\in \mathbb{Z})$. [Conjunction on lines 2.10 and 2.11]
15. $\perp$. [Contradiction rule on line 2.12]
16. $\neg (even(x)\wedge odd(x))$. [Proof by contradiction rule on line 2.13]
17. $\forall x\in \mathbb{Z}[\neg (even(x)\wedge odd(x))]$. [Universal generalisation on lines 1 and 3]

---

Question 8:

You are tasked with building a load balancer that services $C$ clients, and has to balance them between $S$ servers. All clients will request to be serviced at the same time at the start of the day, and the load balancer must assign each client a server immediately at the start of the day.

Your boss tells you to keep costs down, that each server must service less than $\frac{C}{S}$ clients in total. Let $c_i$ be the number of clients that the $i^{th}$ server has to service. e.g., $c_1$ is the number of clients for the first server, $c_2$ is the number of clients for the second server, and so on. Since we have $S$ servers, we have quantities $c_1,c_2,\dots ,c_S$.

Question: Prove to yourself and your boss that this is impossible.

Solution:

Before we begin the proof, let’s formalise what the question wants us to prove. We need to show that the following statement is true:

Given $C\in \mathbb{N},S\in \mathbb{N},c_1\in \mathbb{N},c_2\in \mathbb{Z},\dots ,c_S\in \mathbb{N}$ such that $(C>0)\wedge ({\sum }_{i=1}^S{c}_i=C)$, and the set $[S]=\{1,2,\dots ,S\}$ (refer to Common Sets for Numbers for an explanation of this notation),

$\neg (\forall i\in [S][c_i<\frac{C}{S}\left]\right)$

Essentially, that it is impossible (indicated by the "$\neg$" symbol) for all servers to service fewer than $\frac{C}{S}$ clients. Now that we have a concrete statement down, we can continue proving it:

Solution

Proof:

1. Let $c_1,c_2,\dots ,c_S\in \mathbb{N}$, arbitrarily chosen, be such that ${\sum }_{i=1}^S{c}_i=C$.
2. Assume for the sake of contradiction that $\forall i\in [S][c_i<\frac{C}{S}]$.
3. Then, we must have that $c_1<\frac{C}{S}$, $c_2<\frac{C}{S}$, $\dots$, $c_S<\frac{C}{S}$. [Universal instantiation on line 2.1]
4. ${\sum }_{i=1}^S{c}_i=c_1+c_2+\cdots +c_S<\frac{C}{S}+\frac{C}{S}+\cdots +\frac{C}{S}=S\cdot \frac{C}{S}=C$. Rewriting this (for presentation’s sake), we have ${\sum }_{i=1}^S{c}_i<C$. [Basic algebra]
5. In particular, $\neg ({\sum }_{i=1}^S{c}_i=C)$. [Basic algebra]
6. $({\sum }_{i=1}^S{c}_i=C)\wedge \neg ({\sum }_{i=1}^S{c}_i=C)$. [Conjunction on lines 1 and 2.3]
7. $\perp$. [Contradiction rule on line 2.4]
8. $\neg (\forall i\in [S][c_i<\frac{C}{S}\left]\right)$. [Proof by contradiction rule on line 2.5]
9. Therefore, $\forall c_1,c_2,\dots ,c_S\in \mathbb{N}[\neg (\forall i\in [S][c_i<\frac{C}{S}]\left)\right]$ [Universal generalisation on lines 1 and 3]

Thus, such a task is impossible.