2019–2020 学年第二学期期末真题

可取 $\{\neg,\land\}$：

因为

而 $\{\neg,\land,\lor\}$ 能定义任意真值函数，所以 $\{\neg,\land\}$ 完备。

先递归定义项：常元、变元是项；若 $t_1,\ldots,t_n$ 是项且 $f$ 是 $n$ 元函词，则 $f(t_1,\ldots,t_n)$ 是项。

再递归定义公式：

1. 若 $t_1,\ldots,t_n$ 是项，$P$ 是 $n$ 元谓词，则 $P(t_1,\ldots,t_n)$ 是公式；
2. 若 $A,B$ 是公式，则 $\neg A$、$A\land B$、$A\lor B$ 是公式；
3. 若 $A$ 是公式，$x$ 是变元，则 $\forall xA$ 是公式；
4. 只有有限次应用这些规则得到的符号串才是公式。

存在量词可作为缩写：

可靠性：

即形式系统能证明的结论在所有满足前提的模型中都为真。

完备性：

即所有语义上由前提必然推出的公式都能在形式系统中证明。

使用 $\neg,\to$ 的 Hilbert 系统可写为：

推理规则为 MP：

本课程使用的安全形式是：若 $A$ 是闭公式，则

应用时可先临时把 $A$ 加入前提，证明 $B$，再把临时前提移入蕴涵前件。闭公式条件用于避免 UG 把依赖临时假设的自由变元错误概括。

自然数论域为真；整数论域为假，负整数构成反例。

在题设论域中每个对象都满足 $Q$，所以公式等价于“每个数都有更小的数”。

• 自然数论域为假：最小自然数没有更小的自然数；
• 整数论域为真：对任意 $x$ 可取 $y=x-1$。

自然数论域和整数论域都为真，因为加法在两者中都满足交换律。

• 若公式在每个模型中都为真，则为永真式或有效式；
• 若至少存在一个模型使公式为真，则为可满足式；
• 若没有模型使公式为真，则为永假式或不可满足式。

永真式一定可满足；可满足式未必永真；永假式与可满足式互斥。

UG 规则为

例如已证

可用 UG 得

在带前提推演中，还要保证被概括变量不在相关未解除前提中自由出现。

不可满足。若有赋值满足 $\Gamma$，按逻辑推论定义它也必须满足矛盾式 $\neg Q\land Q$，不可能。

可满足。$\Gamma\not\models Q$ 的定义就是存在某个模型满足 $\Gamma$ 而不满足 $Q$；这个模型已经见证了 $\Gamma$ 可满足。

不成立。左式能推出右式，反向不成立。

取论域 $\{a,b\}$，令 $Q$ 只对 $a$ 真，$R$ 只对 $b$ 真。右式为真，但没有同一个对象同时满足 $Q,R$，左式为假。

成立。前式给出一个固定见证 $c$，使每个 $y$ 都有 $P(c,y)$；对右式中的每个 $y$ 都选择同一个 $x=c$ 即可。

不成立。取论域 $\{a,b\}$，令 $Q$ 只对 $a$ 真、$R$ 只对 $b$ 真。每个对象至少满足一个谓词，所以前件真；但两个全称式都假，后件假。

公式仅在 $p=q=0$ 时为假，其余三行均为真。因此主析取范式为

不成立。取 $Q=0$。此时 $Q\to P=1$、$Q\to R=1$，所以前提为 $1\to1=1$；而结论含 $Q$，真值为 $0$。

以下使用课程已经证明的反置定理和传递定理；若考试要求把“已证定理”也展开，应继续代入 A1–A3 展开。

1. $P\to Q$，前提；
2. $$(P\to Q)\to(\neg Q\to\neg P),$$ 已证反置定理；
3. $\neg Q\to\neg P$，由 1、2 MP；
4. $R\to\neg Q$，前提；
5. $$(\neg Q\to\neg P) \to ((R\to\neg Q)\to(R\to\neg P)),$$ 已证传递定理的实例；
6. $(R\to\neg Q)\to(R\to\neg P)$，由 3、5 MP；
7. $R\to\neg P$，由 4、6 MP。

按本课程缩写

令 $A=\forall x\neg P(x)$，目标变为

它是已证命题逻辑定理 $Q\to\neg\neg Q$ 的代换实例。因此