用一阶逻辑描述日常的推理。一阶逻辑在命题逻辑的基础上引入了存在 ∃\exists 和任意 ∀\forall，也有谓词符号、常量符号、函数符号，不过这些的引入也是为了配合存在和任意。

目前的一阶逻辑有一个局限，就是在同一种解释 J\mathcal{J} 下，所有的量词表示的的论域都是相同的。比如 ∀x,∃y\forall x, \exists y，在解释的时候都是同一个论域 AA。但是在日常的数学语言中，各种范围并不统一。比如：Every even integer n≥4n\ge 4 is a sum of two prime numbers. 这个命题不能直接改写成一阶逻辑的样子，因此命题可以先改写成 For every even integer n≥4n \ge 4, there exist two prime numbers xx and yy such that n=x+yn = x + y. 但是各个变量的范围依然不尽相同。

如果考虑集合论的语言，那么可以写成：

∀n:{n:N∣E(n)∧n≥4}.∃x:{n:N∣P(n)}.∃y:{n:N∣P(n)}.n=x+y\begin{aligned} &\forall n:\{ n:\mathbb{N} | E(n) \land n\ge 4 \}. \\ & \quad \exists x:\{ n: \mathbb{N}|P(n) \}. \\ & \quad \quad \exists y: \{ n:\mathbb{N} | P(n) \}. n = x + y \end{aligned}

但是这样会比较复杂。那么考虑这样的写法：

∀n:N. if E(n)∧n≥4, then ∃x:N.(P(x)∧∃y:N.(P(y)∧n=x+y))\begin{aligned} &\forall n: \mathbb{N}. \text{ if } E(n) \land n \ge 4, \text{ then } \\ & \quad \exists x: \mathbb{N}. (P(x) \land \exists y:\mathbb{N}. (P(y) \land n = x+y)) \end{aligned}

此时的 ∃,∀\exists ,\forall 都被放到同一个论域上了。

Quantifiers with restricted domains

首先引入一个不是很严格的写法：
General rule:

  • ∀x:P.Q(x)\forall x : P. Q(x) can be converted to ∀x(if P(x) then Q(x))\forall x (\text{if } P(x) \text{ then } Q(x))
  • ∃x:P.Q(x)\exists x : P. Q(x) can be converted to ∃x(P(x)∧Q(x))\exists x (P(x) \land Q(x))

The truth of “if-then”

“如果-那么”现在还不是一个逻辑连接词。逻辑连接词需要一个真值表。为了满足上面的使用，我们定义下面的真值表：

（需要一个 →\to 的真值表）

此时我们可以将 “if-then” 当做逻辑连接词：实质蕴含 →\to

Theorem 1

  • ϕ→(ψ→ϕ)\phi \to (\psi \to \phi) is a tautology (永真式)
    • 直观理解：如果 ϕ\phi 成立，我们可以用 ψ\psi 推出 ϕ\phi；相当于用 ϕ,ψ\phi, \psi 两个前提，推出 ϕ\phi 这个结论
  • (ϕ→ψ→χ)→(ϕ→ψ)→(ϕ→χ)(\phi \to \psi \to \chi) \to (\phi \to \psi) \to (\phi \to \chi) is a tautology.
    • 这里首先已经省略了一个括号。对于在第一个括号中的式子，我们需要知道 →\to 符号的结合顺序。出于实质蕴涵直观、简明的理解，我们认为是右结合的的。即 ϕ→ψ→χ\phi \to \psi \to \chi 相当于 ϕ→(ψ→χ)\phi \to (\psi \to \chi)。
    • 对于这条式子的直观理解：如果 ϕ,ψ\phi, \psi 能推出 χ\chi，并且 ϕ\phi 能推出 ψ\psi，那么 ϕ\phi 能推出 χ\chi。

Theorem 2

  • ϕ∨ψ→χ≡(ϕ→χ)∧(ψ→χ)\phi \lor \psi \to \chi \equiv (\phi \to \chi) \land (\psi \to \chi)
  • ϕ∧ψ→χ≡ϕ→(ψ→χ)\phi \land \psi\to \chi \equiv \phi \to (\psi \to \chi)

Theorem 3.

  • ϕ→ψ≡¬ϕ∨ψ\phi \to \psi \equiv \lnot \phi \lor \psi
  • ¬(ϕ→ψ)≡ϕ∧¬ψ\lnot (\phi \to \psi) \equiv \phi \land \lnot \psi
  • ¬ϕ≡ϕ→F\lnot \phi \equiv \phi \to \mathbf{F}
  • ϕ↔ψ≡(ϕ→ψ)∧(ψ→ϕ)\phi \leftrightarrow \psi \equiv (\phi \to \psi) \land (\psi \to \phi)

Theorem 4.

  • Φ,ψ⊨χ\Phi, \psi \models \chi if and only if Φ⊨ψ→χ\Phi \models \psi \to \chi
  • ϕ→ψ,ϕ⊨ψ\phi \to \psi, \phi \models \psi

虽然上面用一些直观的方式帮助理解了实质蕴涵的逻辑等价式，但是实际蕴含与自然语言中“如果-那么”还是不同的，否则会导致一些荒谬的结论。我们在引入 →\to 的时候，已经默认考虑的是 ∀x\forall x 的情况。

Example
比如考虑这个问题：
Is the following logical statement correct?

  • 甲对乙说：你知道吗？只要每次上课都第一个来教室，离散数学课的总评老师就会给你满分。
  • 乙对甲说：我不信。
  • 逻辑命题：只有发生“乙每次上课都第一个来教室并且总评分不为满分”的情况，乙才可以认为甲的说法误，不然都应当认为甲的说法正确。

这个结论显然是荒谬的。因为 ¬P(c)⊭∀x(P(x)→Q(x))\lnot P(c) \not \models \forall x(P(x) \to Q(x)) is not a tautology。

Example
Is the following logical statement correct?
“如果雪是黑的，那么 2+2=52+2=5”是一个逻辑上的真命题

  • 这句话应该要理解为：在任意的可以想象的情况下，如果在这个想象的情况中，如果雪是黑的，那么在这个想象的情况中，2+2=52+2=5。但是这两种情况显然是没有关系的，不能说这是一个真命题。
  • 对于真命题，应当像这样：如果雪是黑的，那么雪不是白的。
  • 但如果把原本命题中的任意去掉，变成一个实质蕴涵，那就成真命题了。

Example
再考虑更极端一点的例子，当“如果-那么”变成实质蕴涵，则会导致所有的虚拟语气都变成真命题。这也是不合理的。

Example
Is it true or false?

  • Symbols: Unary predicates EE and OO, binary predicate LL and S={E,O,L}S = \{E, O, L\}.
  • Proposition: ∀(x:E(x)∧O(x)).L(x,x)\forall(x: E(x) \land O(x)). L(x, x).
  • Domain: Z\mathbb{Z}
  • SS-structure: A=(Z,α)\mathcal{A} = (\mathbb{Z}, \alpha) where
    • for any a∈Za \in \mathbb{Z}, α(E,a)=T\alpha(E, a) = \mathbf{T} iff. aa is an even number;
    • for any a∈Za \in \mathbb{Z}, α(O,a)=T\alpha(O, a) = \mathbf{T} iff. aa is an odd number;
    • for any a,b∈Za, b \in \mathbb{Z}, α(L,a,b)=T\alpha(L, a, b) = \mathbf{T} iff. a<ba < b.
  • For any β\beta and J=(A,β)\mathcal{J} = (\mathcal{A}, \beta), [ ⁣[∀(x:E(x)∧O(x)).L(x,x)] ⁣]J=T[\![\forall(x: E(x) \land O(x)). L(x, x)]\!]_{\mathcal{J}} = \mathbf{T}

Is it true or false?

  • Symbols: Unary predicates EE and OO, binary predicate LL and S={E,O,L}S = \{E, O, L\}.
  • Proposition: ∃(x:E(x)∧O(x)).L(x,x)\exists (x: E(x) \land O(x)). L(x, x).
  • Domain: Z\mathbb{Z}
  • SS-structure: A=(Z,α)\mathcal{A} = (\mathbb{Z}, \alpha) where
    • for any a∈Za \in \mathbb{Z}, α(E,a)=T\alpha(E, a) = \mathbf{T} iff. aa is an even number;
    • for any a∈Za \in \mathbb{Z}, α(O,a)=T\alpha(O, a) = \mathbf{T} iff. aa is an odd number;
    • for any a,b∈Za, b \in \mathbb{Z}, α(L,a,b)=T\alpha(L, a, b) = \mathbf{T} iff. a<ba < b.
  • For any β\beta and J=(A,β)\mathcal{J} = (\mathcal{A}, \beta), [ ⁣[∃(x:E(x)∧O(x)).L(x,x)] ⁣]J=T[\![\exists (x: E(x) \land O(x)). L(x, x)]\!]_{\mathcal{J}} = \mathbf{T}

通过 ∀(x:P(x))\forall (x: P(x)) 或者 ∃(x:P(x))\exists (x:P(x)) 的方式，我们相当于限制了 xx 的论域。

Special quantified proposition

Claim: Suppose SS is a set of symbols and J\mathcal{J} is an SS-interpretation.

  • If ⟦∃xϕ⟧J=F\llbracket \exists x \phi \rrbracket_{\mathcal{J}} = \mathbf{F},
  • then
    • ⟦∀(x:ϕ).ψ⟧J=T\llbracket \forall (x: \phi). \psi \rrbracket_{\mathcal{J}} = \mathbf{T};
    • ⟦∃(x:ϕ).ψ⟧J=F\llbracket \exists (x: \phi). \psi \rrbracket_{\mathcal{J}} = \mathbf{F}.

Remark: ∀xϕ\forall x \phi and ∃xϕ\exists x \phi is still legal proposition even if xx does not occur in ϕ\phi.

Interpreting informal proofs

Example 5.
Proof of ∀ε>0,∃N,∀n>N,∣1n∣<ε\forall \varepsilon > 0, \exists N, \forall n > N, \left| \frac{1}{n} \right| < \varepsilon.
Given a fixed ε>0\varepsilon > 0, let N=[1ε]+1N = \left[ \frac{1}{\varepsilon} \right] + 1 then for any n>Nn > N,

∣1n∣=1n<1N<11ε=ε.\left| \frac{1}{n} \right| = \frac{1}{n} < \frac{1}{N} < \frac{1}{\frac{1}{\varepsilon}} = \varepsilon.

Qed.

Proof step: In order to prove ∀ε>0,∃N,∀n>N,∣1n∣<ε\forall \varepsilon > 0, \exists N, \forall n > N, \left| \frac{1}{n} \right| < \varepsilon, it suffices to prove: if ε>0\varepsilon > 0 then ∃N,∀n>N,∣1n∣<ε\exists N, \forall n > N, \left| \frac{1}{n} \right| < \varepsilon.

Logic: If Φ\Phi does not talk about ε\varepsilon and Φ,ψ⊢χ\Phi, \psi \vdash \chi then Φ⊢∀ε(ψ→χ)\Phi \vdash \forall \varepsilon (\psi \rightarrow \chi).

Proof step: In order to prove ∃N,∀n>N,∣1n∣<ε\exists N, \forall n > N, \left| \frac{1}{n} \right| < \varepsilon, it suffices to prove ∀n>[1ε]+1,∣1n∣<ε\forall n > \left[ \frac{1}{\varepsilon} \right] + 1, \left| \frac{1}{n} \right| < \varepsilon.

Logic: If Φ⊢ψ[N↦t]\Phi \vdash \psi [N \mapsto t] then Φ⊢∃Nψ\Phi \vdash \exists N \psi.

Example 6.
Proof of:

¬∃x∈N.∃y∈N.gcd⁡(x,y)=1 and x2=2y2.\lnot \exists x \in \mathbb{N}. \exists y \in \mathbb{N}. \gcd(x, y) = 1 \text{ and } x^2 = 2y^2.

Suppose there exists x∈Nx \in \mathbb{N} and y∈Ny \in \mathbb{N} s.t. x2=2y2x^2 = 2y^2.
Thus, xx must be an even number and we can assume x=2x0x = 2x_0.
Now, we have y2=2x02y^2 = 2x_0^2.
Thus, yy must be an even number two and we can assume y=2y0y = 2y_0.
Therefore, gcd⁡(x,y)≠1\gcd(x, y) \neq 1.
Qed.

Proof step: In order to prove ¬∃x∈N.∃y∈N.gcd⁡(x,y)=1\lnot \exists x \in \mathbb{N}. \exists y \in \mathbb{N}. \gcd(x, y) = 1 and x2=2y2x^2 = 2y^2, it suffices to prove that if x∈Nx \in \mathbb{N}, y∈Ny \in \mathbb{N} and x2=2y2x^2 = 2y^2 then gcd⁡(x,y)≠1\gcd(x, y) \neq 1.

Logic: If Φ\Phi does not talk about xx and yy, ψ1\psi_1 does not talk about yy, and Φ,ψ1,ψ2,ψ3⊢¬χ\Phi, \psi_1, \psi_2, \psi_3 \vdash \lnot \chi, then Φ⊢¬∃x(ψ1∧∃y(ψ2∧ψ3∧χ))\Phi \vdash \lnot \exists x (\psi_1 \land \exists y (\psi_2 \land \psi_3 \land \chi)).

Proof step: If x2=2y2x^2 = 2y^2, then xx is an even number.

No logic. It is a math fact.

Logic (in the bigger picture): If Φ⊢ψ\Phi \vdash \psi and Φ,ψ⊢χ\Phi, \psi \vdash \chi, then Φ⊢χ\Phi \vdash \chi.

Proof step: Because there exists x0∈Nx_0 \in \mathbb{N} s.t. x=2x0x = 2x_0, we can use x0x_0 to represent this natural number in later proofs.

Logic: If neither Φ\Phi nor χ\chi does mention x0x_0, and Φ,ψ⊢χ\Phi, \psi \vdash \chi, then Φ,∃x0ψ⊢χ\Phi, \exists x_0 \psi \vdash \chi.