Question 1:
https://blog.yexca.net/en/archives/198
Question 2: This article
Question 3:
https://blog.yexca.net/en/archives/200
Question 4:
https://blog.yexca.net/en/archives/202
Question 5:
https://blog.yexca.net/en/archives/203
Introduction
At first glance, I thought this question belonged to formal languages (and automata theory), but it’s actually mathematical logic. It’s not too difficult—especially if you’ve practiced University of Tokyo exams—but you still need a solid theoretical foundation to solve it.
Question copyright belongs to the Institute of Science Tokyo. Quoted here for educational purposes only.
1
Consider propositional logic. Let proposition $\varphi$ be $(\neg p_0 \to \neg p_1) \wedge (\neg p_1 \to p_0)$, where $p_0, p_1$ are propositional symbols.
a) Fill in (A) to (D) so that the following is the truth table for $\varphi$. Note: 1 represents true, 0 represents false.
| $p_0$ | $p_1$ | $\varphi$ |
|---|---|---|
| 0 | 0 | (A) |
| 0 | 1 | (B) |
| 1 | 0 | (C) |
| 1 | 1 | (D) |
b) State whether proposition $\varphi$ is a tautology.
c) State whether proposition $\varphi$ is satisfiable.
1-a
First, simplify proposition $\varphi$:
$$ \begin{align} \varphi &= (\neg p_0 \to \neg p_1) \wedge (\neg p_1 \to p_0) \\ &= (p_0 \vee \neg p_1) \wedge (p_1 \vee p_0) \end{align} $$From this:
| $p_0$ | $p_1$ | $\varphi$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Therefore: (A): 0, (B): 0, (C): 1, (D): 1.
1-b
Since there are cases where $\varphi=0$, it is not a tautology.
1-c
Since there are cases where $\varphi=1$, it is satisfiable.
2
Consider natural deduction in propositional logic. $p_1, p_2, p_3$ are symbols. $\wedge I$ is conjunction introduction, $\wedge E_L$ is conjunction elimination (left), $\wedge E_R$ is conjunction elimination (right), and $\to E$ is implication elimination.
a) Assume $(p_1 \wedge p_2) \wedge p_3$ and conclude $p_1 \wedge (p_2 \wedge p_3)$. Complete the following proof tree by filling in (A) to (E).
$$ \cfrac{ \cfrac{ \cfrac{(p_1 \wedge p_2)\wedge p_3}{(A)}\wedge E_L }{p_1}\wedge E_L \quad \cfrac{ \cfrac{ \cfrac{(p_1 \wedge p_2) \wedge p_3}{(B)}\wedge E_L }{(C)}\wedge E_R \quad \cfrac{(p_1 \wedge p_2) \wedge p_3}{(D)}\wedge E_R }{(E)}\wedge I }{p_1 \wedge (p_2 \wedge p_3)}\wedge I $$b) Assume $p_1 \wedge p_2$ and $p_1 \to (p_2 \to p_3)$ and conclude $p_3$. Complete the following proof tree by filling in (A) to (D).
$$ \cfrac{ \cfrac{(A)}{p_2}\wedge E_R \quad \cfrac{ \cfrac{(B)}{p_1}\wedge E_L \quad (C) }{(D)}\to E }{p_3}\to E $$c) Determine if the set of propositions $\{ \neg p_0 \to \neg p_1, \neg p_1 \to p_0 \}$ is consistent or inconsistent, and state the reason.
2 Solution
The first two parts are straightforward if you know the rules:
$\wedge I$ (Introduction): Combines $A$ and $B$ into $A \wedge B$.
$\wedge E_L$ (Elimination Left): Extracts $A$ from $A \wedge B$.
$\wedge E_R$ (Elimination Right): Extracts $B$ from $A \wedge B$.
$\to E$ (Elimination): Modus Ponens; derives $B$ from $A$ and $A \to B$.
2-a
- (A): $p_1 \wedge p_2$
- (B): $p_1 \wedge p_2$
- (C): $p_2$
- (D): $p_3$
- (E): $p_2 \wedge p_3$
2-b
- (A): $p_1 \wedge p_2$
- (B): $p_1 \wedge p_2$
- (C): $p_1 \to (p_2 \to p_3)$
- (D): $p_2 \to p_3$
2-c
It is consistent. Simplify the propositions:
$$ \neg p_0 \to \neg p_1 \equiv p_0 \vee \neg p_1 \\ \neg p_1 \to p_0 \equiv p_1 \vee p_0 $$Truth table:
| $p_0$ | $p_1$ | $\neg p_0 \to \neg p_1$ | $\neg p_1 \to p_0$ |
|---|---|---|---|
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 1 |
When $(p_0=1, p_1=0)$ or $(p_0=1, p_1=1)$, both propositions hold.
Since there is at least one truth assignment where all propositions in the set are true, the set $\{ \neg p_0 \to \neg p_1, \neg p_1 \to p_0 \}$ is consistent.
3
Consider first-order predicate logic.
a) Does a model for the following formula exist? If so, state the minimum cardinality of the universe. If not, explain why.
$$ \exists x \exists y \exists z \space \neg(x=y) \wedge \neg(y=z) \wedge \neg(z=x) $$b) Does a model for the following formula exist? If so, provide one example. If not, explain why.
$$ \exists x \forall y(x=y) $$3-a
A model exists. The minimum cardinality of the universe is 3.
3-b
A model exists. For example, set the universe $U = \{a\}$. In this case, for $x=a$, every element $y$ in $U$ equals $x$, so the formula holds.
4
Consider natural deduction in first-order predicate logic. State whether the following holds and explain why. $P$ is a binary predicate symbol.
$$ \vdash (\forall x \exists y P(x,y)) \to \exists x \forall y P(x,y) $$4 Solution
This does not hold. Here is a counterexample:
Define the universe as $\{ m, n, a, b \}$. Define the interpretation of $P(x,y)$ such that:
$$ P(m,a) = \text{True} \quad P(a,m) = \text{False} \\ P(n,b) = \text{True} \quad P(b,n) = \text{False} $$In this model, $\forall x \exists y P(x,y)$ can be true (e.g., if every $x$ has some $y$ that makes $P$ true), but $\exists x \forall y P(x,y)$ is false (there is no single $x$ that is related to every $y$).