Problems

Here are some problems designed to get you started thinking in terms of first order logic.

Translation

Translate the following formal logic into sentences. The predicate $M(x)$ is “does math”, the predicate $L(x)$ is “knows logic”, and the predicate $H(x)$ is “is happy”. The predicate $K(x, y)$ is “$x$ knows of $y$”. You can assume the “universe” (the values all variables can take) is “people” (every variable stands for a person).

1. $\forall x, M(x)\implies L(x)$
2. $\exists x\text{ s.t. } L(x) \land\lnot H(x)$
3. $\forall x, \exists y\text{ s.t. } K(x, y)$
4. $\forall x, \exists y\text{ s.t. } K(x, y) \implies H(x)$
5. $\forall x, \exists y\text{ s.t. } K(x, y) \implies \lnot H(x)$
6. $\forall x, L(x)\implies H(x)$
7. $\exists x \text{ s.t. } M(x)\land \lnot L(x)$
8. $\exists x \text{ s.t. } \forall y, K(x, y)\implies M(y)$
9. $\forall x, \forall y, K(x, y) \implies K(y, x)$
10. $\forall y,\exists x \text{ s.t. } K(x, y)\land \lnot M(y)$.

Translate the following sentences into formal logic (symbols). You may need to make up predicates, such as $M(x)$ for “is a man”, and $S(x)$ for “is Socrates”

1. All men are mortal.
2. Socrates is a Man.
   1. This is a little tricky; you can’t just say “$s$ is Socrates, $M(s)$ is true”. You’ll need to use an implication.
3. If all men are mortal and Socrates is a man, then Socrates is mortal.
4. If a man is Socrates, and knows logic, then that man is happy.

Proof

First, translate all logical expressions. Then prove the follwing equivalences by writing out truth tables. If you can, also prove them by arguing using equivalences you have already derived.

1. Prove $\lnot(P(x)\land Q(x))$ is equivalent to $\lnot P(x)\lor \lnot Q(x)$
2. Prove that $\lnot(P(x)\implies Q(x))$ is equivalent to $P(x)\land \lnot Q(x)$.
3. Prove that $P(x)\implies Q(x)$ is equivalent to $\lnot Q(x)\implies \lnot P(x)$.
4. Determine which of the translation problems can mutually be true (some are contradictary; why?)