※ 歡迎指正

Proof System: Hausman, Alan & Kahane, Howard & Tidman, Paul (2010) Logic and Philosophy A Modern Introduction.原本想用 Robert Causey 的 Logic, Sets, and Recursion 的推論系統，不過那套太冷門，改用在台灣比較通俗的 Hausman, Alan & Kahane, Howard & Tidman, Paul 的 Logic and Philosophy A Modern Introduction. 若發現問題請糾正。
1. Translate the following English sentences into well-formed formulas, with English alphabets standing for atomic sentences - that is, those sentences that are not built up out of other sentences.
(a) Either Sam will come to the party and Max will not, or Sam will not come to the party and Max will enjoy himself.
(b) Fiorello goes to the movies only if a comedy is playing.

1. $S$: Sam will come to the party
$M$: Max will come to the party
$E$: Max will enjoy himself
$(S∧∼M)∨(∼S∧E)$我不知道 “enjoy himself” 在這個脈絡是甚麼意思，所以譯成一個新的基本語句。有人說在這個脈絡是 going to the party ，若是的話這句要譯成 $(S∧∼M)∨(∼S∧M)$ 。
2. $F$: Fiorello goes to the movies
$P$: a comedy is playing
$F→P$

2. Use the truth table method to show the validity of the following argument.
$(A∧B)∨C, ∼(A∨B) /∴ C$

 $A$ $B$ $C$ $((A∧B)∨C)∧∼(A∨B))→C$ T T T T T T F T T F T T T F F T F T T T F T F T F F T T F F F T

3. Prove that the following argument is a valid argument (no semantic method).
$∼(P∧∼Q), ∼Q∨M, R→∼M /∴ P→∼(R∨∼M)$

 1 $∼(P∧∼Q)$ p 2 $∼Q∨M$ p 3 $R→∼M$ p 4 $P$ AP (Conditional Proof) 5 $∼P∨∼∼Q$ 1 DeM 6 $∼∼P$ 4 DN 7 $∼∼Q$ 5, 6 DS 8 $M$ 2, 7 DS 9 $∼∼M$ 8 DN 10 $∼R$ 3, 9 MT 11 $∼R∧∼∼M$ 9, 10 Conj 12 $∼(R∨∼M)$ 11 DeM 13 $P→∼(R∨∼M)$ 4-12 CP

4. Prove that $(∼A∧(A∨B))→B$ is a tautology (no semantic method).題目是 “$(∼A∧(A∨B))→B)$” ，左右括號不平衡，應該是 typo 。

 1 $∼((∼A∧(A∨B))→B)$ AP (Reductio Ad Absurdum) 2 $∼(∼(∼A∧(A∨B))∨B)$ 1 Impl 3 $∼∼(∼A∧(A∨B))∧∼B$ 2 DeM 4 $(∼A∧(A∨B))∧∼B$ 3 DN 5 $∼A∧(A∨B)$ 4 Simp 6 $∼B$ 4 Simp 7 $∼A$ 5 Simp 8 $A∨B$ 5 Simp 9 $B$ 7, 8 DS 10 $B∧∼B$ 6, 9 Conj 11 $(∼A∧(A∨B))→B$ 1-10 IP

5. Translate the following sentences into well-formed formulas in first-order logic.
(a) Anyone who is persistent can learn logic.
(b) John hates everyone who does not hate himself.
(c) Everyone loves somebody and no one loves everybody, or somebody loves everybody and someone loves nobody.

1. Domain $=\{x: x \text{ is a human being}\}$
$Px$: $x$ is persistent
$Lx$: $x$ can learn logic
$(x)(Px→Lx)$
2. Domain $=\{x: x \text{ is a human being}\}$
$Hxy$: $x$ hates $y$
$a$: John
$(x)(Hax↔∼Hxx)$
3. Domain $=\{x: x \text{ is a human being}\}$
$Lxy$: $x$ loves $y$
$[(x)(∃y)Lxy∧∼(∃x)(y)Lxy]∨[(∃x)(y)Lxy∧(∃x)∼(∃y)Lxy]$

6. Prove the validity of the following arguments.
(a) $(x)[(Fx∨Gx)→Hx], (x)[(Hx∨Kx)→Lx] /∴ (x)(Fx→Lx)$
(b) $(x)(∃y)Fxy→(x)(∃y)Gxy, (∃x)(y)∼Gxy /∴ (∃x)(y)∼Fxy$

 1 $(x)[(Fx∨Gx)→Hx]$ p 2 $(x)[(Hx∨Kx)→Lx]$ p 3 $Fx$ AP (Conditional Proof) 4 $(Fx∨Gx)→Hx$ 1 UI 5 $(Hx∨Kx)→Lx$ 2 UI 6 $Fx∨Gx$ 3 Add 7 $Hx$ 4, 6 MP 8 $Hx∨Kx$ 7 Add 9 $Lx$ 5, 8 MP 10 $Fx→Lx$ 3-9 CP 11 $(x)(Fx→Lx)$ 10 UG

 1 $(x)(∃y)Fxy→(x)(∃y)Gxy$ p 2 $(∃x)(y)∼Gxy$ p 3 $(∃x)∼(∃y)∼∼Gxy$ 2 QN 4 $(∃x)∼(∃y)Gxy$ 3 DN 5 $∼(x)∼∼(∃y)Gxy$ 4 QN 6 $∼(x)(∃y)Gxy$ 5 DN 7 $∼(x)(∃y)Fxy$ 1, 6 MT 8 $∼∼(∃x)∼(∃y)Fxy$ 7 QN 9 $(∃x)∼(∃y)Fxy$ 8 DN 10 $(∃x)∼∼(y)∼Fxy$ 9 QN 11 $(∃x)(y)∼Fxy$ 10 DN

7. Show that the following arguments are invalid.
(a) $(x)(Px→Qx), (x)(Qx→Rx) /∴ (x)(Px∧Rx)$題目打錯符號，用了未定義的 “$⊃$” 。
(b) $(x)(∃y)(Fxy→Gxy), (x)(∃y)(Gxy→Hxy) /∴ (x)(∃y)(Fxy→Hxy)$

1. Domain $=\{a,b\}$
$\mathcal{I}(Px)=\{a\}$
$\mathcal{I}(Qx)=\{a\}$
$\mathcal{I}(Rx)=\{a\}$
2. Domain $=\{a,b\}$
$\mathcal{I}(Fxy)=\{<a,a>,<a,b>,<b,a>,<b,b>\}$
$\mathcal{I}(Gxy)=\{<a,a>,<b,a>\}$
$\mathcal{I}(Hxy)=\{\}$

8. Let $\Gamma_0, \Gamma_1,...,\Gamma_n,...$ be a sequence of sets such that $\Gamma_i⊆\Gamma_{i+1}$ and $\Gamma^{\ast}=\sideset{}{_{i=0}^\infty}\bigcup \Gamma_i$. Prove that if $\Gamma'$ is a finite subset of $\Gamma^{\ast}$, then $\Gamma'⊆\Gamma_i$ for some $i$.

Suppose that $\Gamma'$ is a finite subset of $\Gamma^{\ast}$. By the definition of $\Gamma^{\ast}$, every member of $\Gamma^{\ast}$ is a member of $\Gamma_n$ for some $n$. It follows that every member of $\Gamma'$ is a member of $\Gamma_n$ for some $n$. Let members of $\Gamma'$ be $a1, a2, a3, ..., an$. Each of them is a member of at least one $\Gamma_n$. Let $\Gamma_{a1}$ be one of the sets that contain $a1$, $\Gamma_{a2}$ be one of the sets that contain $a2$, and so on. The sets $\Gamma_{a1}, \Gamma_{a2}, ..., \Gamma_{an}$ can be enumerated in terms of subset relation. Since $\Gamma'$ is finite, there must be a $\Gamma_k$ such that $\Gamma_{a1}, \Gamma_{a2}, ..., \Gamma_{an}$ are all subsets of $\Gamma_k$. Members of $\Gamma_{a1}∪\Gamma_{a2}∪...∪\Gamma_{an}$ are members of $\Gamma_k$. Also, members of $\Gamma'$ are members of $\Gamma_{a1}∪\Gamma_{a2}∪...∪\Gamma_{an}$. Thus, $\Gamma'$ is a subset of $\Gamma_k$. Consequently, $\Gamma'$ is a subset of $\Gamma_i$ for some $i$.

#### 1 則留言:

1. I think "enjoy himself" just means going to the party.