Fall 2010 Final CC-BY-NC

Maintainer: admin

1Question 1


Translate into propositional formulas and determine validity.

(a) If queens are quizzical or rooks run rampant, then pawns don't prefer palindromes. Either pawns prefer palindromes and queens are quizzical, or rooks run rampant. Therefore pawns don't prefer palindromes and rooks run rampant. (5 marks)
(b) If queens are quizzical and roks run rampant, then pawns don't prefer palindromes. Either pawns prefer palinromes and queens are quizzical, or rooks run rampant. Therefore pawns don't prefer palindromes and rooks run rampant. (5 marks)


(a) $(q \lor r) \to \neg p,\, (p \land q) \lor r \vdash \neg p \land r$. This is valid, as it's impossible to invalidate it. This can be proved by contradiction. Assume there is a valuation $V$ that makes all the premises come out $\top$ but makes the conclusion come out $\bot$. To make the second premise come out $\top$, there are two possibilities. The first is that $V(r) = \top$, in which case, for the first premise to come out $\top$, we must have $V(p) = \bot$, in which case the conclusion would also come out $\top$. The second is that $V(p) = V(q) = \top$. But in this case, the first premise would evaluate to $V(\top \to \bot)$ which comes out $\bot$. So there is no valuation that invalidates this argument and so the argument is valid.
(b) $(q \land r) \to \neg p, \, (p \land q) \lor r \vdash \neg p \land r$. This is invalid. For instance, if $V(p) = V(q) = \top$ and $V(r) = \bot$, then the conclusion comes out $\bot$ due to the valuation of $r$ but the premises both come out $\top$, as the first premise becomes $V(\bot \to \bot)$ and the second becomes $V(\top \lor \bot)$. So this is an invalid argument as there is a valuation that invalidates it.

1.3Accuracy and discussion

I think

2Question 2


Suppose that $R$ is a binary relation on the non-empty set $A$. We define another binary relation $S \subseteq A \times A$ as follows: for $a, b \in A$ we put $(a, b) \in S$ if and only if there is a natural number $n$ and $a_0, a_1 ... a_n$ such that $a_0 = a$, $a_n = b$ and for each $j < n$, $(a_j, a_{j+1}) \in R$.

(a) Show that $S$ is transitive and $R \subseteq S$. (5 marks)
(b) Prove that, if $T \subseteq A \times A$ is transitive and $R \subseteq T$, then $S \subseteq T$. (5 marks)
(c) Show that, if $R$ is reflexive and symmetric, then $S$ is an equivalence relation. (5 marks)


(a) Transitivity of $S$: Later

2.3Accuracy and discussion


3Question 3


(a) Suppose that $(L_1; \leq_1)$ and $(L_2; \leq_2)$ are lattices such that $L_1 \cap L_2 = \{ \top_2 = \bot_1 \}$. That is, the bottom element of $L_1$ is the top element of $L_2$, and otherwise they have no elements in common. Show that the lattice $L$ with underlying set $L_1 \cup L_2$ is modular if and only if each of $L_1$ and $L_2$ is; show that $L$ is distributive if and only if each of $L_1$ and $L_2$ is. (So the order on $L$ is given by $a \leq b$ for any $a \in L_2$, $b \in L_1$; and if both $a, b \in L_j$, then $a \leq b$ if and only if $a \leq_j b$ for $j = 1, 2$. (8 marks)
(b) Hasse diagram not included, can't do this question


(a) Later

3.3Accuracy and discussion


4Question 4


One of the following can be proved logically; i.e., it is valid. The other is not. Identify which is which. Give a quasi-formal proof for the valid one, and a structure showing that the other is not valid. [$f$, $g$ and $h$ are unary function symbols. You may use transitivity and symmetry of equality freely in your proof.]

$$\forall (gfx = hfx), \forall y \exists x (fx = y) \vdash \forall y (gy = hy)$$

$$\forall (fgx = fhx),\, \forall y \exists x (fy = y) \vdash \forall y (gy = hy)$$


The first is valid, the second is not.

A short and elegant proof of the first1:

Sequent Justification
(1) $\forall x(gfx = hfx) \vdash gfx = hfx$ Straightforward $\forall$-elimination
(2) $\forall y \exists x(fx = y) \vdash \exists x (fx = y)$ $\forall$-elimination
(3) $fx = y, gfx = hfx \vdash gy = hy$ Substitution rule 1
(4) $\forall x (gfx = hfx), fx = y \vdash gy = hy$ Informal transitivity using (1), (3)2
(5) $\forall x (gfx=hfx),\,\exists x (fx=y) \vdash gy = hy$ $\exists$-elimination from (4)
(6) $\forall x(gfx=hfx),\,\forall y \exists x (fx=y) \vdash gy=hy$ Informal transitivity using (2), (5)
(7) $\forall x (gfx=hfx), \, \forall y \exists x (fx=y) \vdash \forall y gy=hy)$ $\forall$-introduction from (6)

Counterexample to the second:

Let $f(x) = \left \lfloor \frac{x}{2} \right \rfloor$, $g(x) = 0$, $h(x) = 1$, over the natural numbers. The first premise, that $\forall (fgx = fhx)$, is indeed true, as $f(0) = \left \lfloor 0 \right \rfloor = 0 = \left \lfloor 0.5 \right \rfloor = f(1)$. The second premise is also true, as $f(x)$ is indeed onto. However, it is not true that $\forall y (gy = hy)$, since $g(y) = 0$ and $h(y) = 1$ and $0 \neq 1$.

4.3Accuracy and discussion

Done in-class on Friday, November 25.

5Question 5


We invent a structure $\mathcal{M} = (M; f^{\mathcal{M}}, P^{\mathcal{M}})$, where $f$ is a unary function symbol and $P$ is a binary relation symbol as follows: $M = \{a, b, c, d\}, f^{\mathcal{M}}(a) = f^{\mathcal{M}}(b) = d, f^{\mathcal{M}}(c) = a, f^{\mathcal{M}}(d) = b$, and $P^{\mathcal{M}} = \{(a, b), (a, d), (b, c), (c, a), (d, b), (d, c)\}$. Decide whether or not

$$\mathcal{M} \models \forall x \exists y (Pfyfx)$$

and justify your answer.


No. This fails if $x = c$, because then $Pfyfx = P(fy)a$, and so $fy$ must be $c$ in order for $P(fy)a$ to be true. But there is no $x$ in the domain such that $fx = c$.

5.3Accuracy and discussion

A bit short but it should be right?

6Question 6


Give an informal proof from Peano arithmetic of the following. You may use anything done in class or on the assignments, but for not instance the fundamental theorem of arithmetic, since we did not prove that. Recall we use the abbreviation $\Phi(x)$ for "$x$ is a prime number". (15 marks)

$$\forall x \forall y \forall z ((\Pi(x) \land \Pi(y) \land \Pi(y) \land y \neq z) \to x \cdot x \neq y \cdot z)$$



6.3Accuracy and discussion


7Question 7


One of the following distributive laws holds for all ordinals and the other sometimes doesn't. Give an informal proof for the true one, and a counterexample for the (sometimes) false one. (The addition and multiplcation are of course ordinal addition and multiplication). (10 marks)

$$\alpha \cdot (\beta + \gamma) = (\alpha \cdot \beta) + (\alpha \cdot \gamma)$$

$$(\alpha + \beta) \cdot \gamma = (\alpha \cdot \gamma) + (\beta \cdot \gamma)$$



7.3Accuracy and discussion


8Question 8


Give a formal in Prenex normal form which is equivalent to the formula

$$(\exists Pxy \to \forall x Qxy) \land \neg \forall y \exists x ((Pxy \lor \neg Qyx) \land \neg Pxz)$$

Here of course P and Q are binary predicate symbols. (10 marks)


Sequent Justification
$(\exists x Pxy \to \forall x Qxy) \land \exists y \forall x(\neg ((Pxy \lor \neg Qyx) \land \neg Pxz)))$ Not sure how this is justified but it works
$(\neg \exists x Pxy \lor \forall x Qxy) \land ...$ Replacing the implies
$(\forall x \neg Pxy \lor \forall x Qxy) \land ...$ Replacing $\neg \exists$ with $\forall \neg$
$(\forall u \neg Puy \lor \forall x Qxy) \land ...$ Change of bound variables
$\forall u (\neg Puy \lor \forall v Qvy) \land ...$ Moving a $\forall$ outside, changing a bound variable
$\forall u \forall v (\neg Puy \lor Qvy) \land ...$ Moving another $\forall$ outside
$\forall u \forall v \exists y \exists x (...)$ Moving everything outside

8.3Accuracy and discussion

Done in class, something might have been incorrectly copied though. Not sure about the justification.

  1. Incidentally, if one wanted to prove the following statement (same meaning as the given theorem, just expressed slightly differently):

    $$\forall x (gfx =hfx),\,\forall x \exists y (fy=x) \vdash \forall x(gx = hx)$$

    one would have to do some changing of bound variables first:

    Sequent Justification
    (8) $\forall x \exists y (fy=x) \vdash \forall y \exists x(fx=y)$ Change of bound variables, twice (informal)
    (9) $\forall x \exists y(fy=x), \, \forall x(gfx=hfx) \vdash \forall y (gy=hy)$ Informal transitivity using (7), (8)
    (10) $\forall y (gy=hy) \vdash \forall x (gx=hx)$ Change of bound variables
    (11) $\forall x (gfx =hfx),\,\forall x \exists y (fy=x) \vdash \forall x(gx = hx)$ Transitivity using (9), (10)

  2. "Informal" because the premises haven't been explicitly fattened out using monotonicity. This is fine for a quasi-formal proof though.