题干逐字取自教材 PDF 第 96–101 页；原解答逐字取自答案书（第 3 章习题解答与分析，答案书 p67–p79），不进折叠块。AI 补充的内容一律放在标题含「AI 生成，非原书」的
:::details折叠块中。
3.1 设个体域为实数集 \mathbf{R},F(x):x>5,求下列 0 元谓词的真值.
(1) F(5) (2) F(\sqrt{2}) (3) F(-2) (4) F(\sqrt{6})
(5) F(\sqrt{27}) (6) F(7.9)
解答 (1)\sim(4)的真值为 0,(5)与(6)的真值为 1.
分析 这里的 1 元谓词 F(F(x): x>5,x\in\mathbf{R})为谓词常项,所以(1)\sim(6)全为命题. 由于 5,\sqrt{2},-2,\sqrt{6} 全都小于或等于 5,所以(1)\sim(4)为假命题. 而 \sqrt{27} 和 7.9 均大于 5,所以(5)与(6)均为真命题.
3.2 设个体域 D=\{x\,|\,x 为英语单词\},令 F(x):x 含字母 c. 求下列各 0 元谓词的真值.
(1) F(\text{about}) (2) F(\text{call}) (3) F(\text{error}) (4) F(\text{erect})
解答 (1)与(3)的真值为 0,(2)与(4)的真值为 1.
分析 这里的 1 元谓词 F(F(x): x 含字母 c)为谓词常项,所以(1)\sim(4)全为命题,其中,(1)与(3)中单词不含字母 c,所以为假命题,而(2)与(4)中单词含字母 c,所以为真命题.
3.3 将下列命题用 0 元谓词符号化.
(1) 王小山来自山东省或河北省.
(2) 除非李联不怕吃苦,否则她不会取得这样好的成绩.
(3) \sqrt{2} 不是有理数.
(4) 3 大于 2 仅当 3 大于 4.
解答 (1) 设 F(x): x 来自山东省,G(x): x 来自河北省,a: 王小山. 命题符号化为
(2) 设 F(x): x 怕吃苦,G(x): x 取得好成绩,a: 李联. 命题符号化为
(3) 设 F(x): x 是有理数,命题符号化为
(4) 设 F(x,y): x>y,命题符号化为
分析 (1)中命题的真值要根据王小山来自哪个省而定. 若他既不是来自山东省,也不是来自河北省,则命题为假. 若他真来自山东省或河北省,则命题为真,但不可能既来自山东省又来自河北省,所以既可以符号化为排斥或,又可以符号化为相容或.
对于(2)中命题,注意"李联取得好成绩"的必要条件是"李联不怕吃苦".
另外,还应注意,(1)与(2)的真值要根据具体情况而定. 而(3)和(4)的真值是确定的,(3)是真命题,而(4)是假命题.
3.4 设个体域为 D=\{x\,|\,x 是人\}, L(x,y):x 喜欢 y. 将下列命题符号化.
(1) 所有的人都喜欢赵小宝.
(2) 所有的人都喜欢某些人.
(3) 没有人喜欢所有的人.
(4) 每个人都喜欢自己.
解答 设二元谓词 L(x,y): x 喜欢 y.
(1) 设 a: 赵小宝,命题符号化为
(2) \forall x\exists yL(x,y).
(3) \neg \exists x\forall yL(x,y).
(4) \forall xL(x,x).
3.5 设个体域为全总个体域,又令 M(x):x 是人. 将题 3.4 中 4 个命题符号化.
解答 设 M(x): x 为人,L(x,y): x 喜欢 y.
(1) 设 a: 赵小宝. \forall x(M(x)\rightarrow L(x,a)).
(2) \forall x(M(x)\rightarrow \exists y(M(y)\wedge L(x,y))).
(3) \neg \exists x(M(x)\wedge \forall y(M(y)\rightarrow L(x,y))).
(4) \forall x(M(x)\rightarrow L(x,x)).
分析 题 3.4 与题 3.5 说明: 同一个命题在不同的个体域下,可有不同形式的符号化形式,当然,也可能有相同的符号化形式. 设有命题"自然数都是整数",
① 个体域 D_1=\mathbf{R}(\mathbf{R} 为实数集),命题符号化为
其中,F(x): x 为自然数,G(x): x 为整数.
② 个体域 D_2=\mathbf{Q}(\mathbf{Q} 为有理数集),命题符号化为
F(x),G(x) 的含义同①.
③ 个体域 D_3=\mathbf{N}(\mathbf{N} 为自然数集),命题符号化为
G(x) 的含义同①.
3.6 在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值.
(1) 凡整数都能被 2 整除.
(2) 有的整数能被 2 整除.
其中,(a) 个体域为整数集合.
(b) 个体域为实数集合.
解答 (a) 个体域为整数集合:
(1) \forall xF(x),其中,F(x): x 能被 2 整除. 真值为 0. 例如,3 为整数,但 2 不能整除 3.
(2) \exists xF(x),F(x) 同(1). 真值为 1. 所有的偶数都是整数,它们都能被 2 整除.
(b) 个体域为实数集:
(1) \forall x(G(x)\rightarrow F(x)),其中,G(x): x 为整数,F(x): x 能被 2 整除,其真值为 0.
(2) \exists x(G(x)\wedge F(x)),其中,G(x),F(x) 同(1),其真值为 1.
3.7 设个体域为整数集 \mathbf{Z}, L(x,y):x+y=x-y. 求下列各式的真值.
(1) L(1,1). (2) L(2,0).
(3) \forall yL(1,y). (4) \exists xL(x,2).
(5) \exists x\exists yL(x,y). (6) \forall x\exists yL(x,y).
(7) \exists y\forall xL(x,y). (8) \forall x\forall yL(x,y).
解答 (1),(3),(4),(8)的真值为 0,而(2),(5),(6),(7)的真值为 1.
分析 (1) 因为 1+1\neq 1-1,所以 L(1,1) 为假.
(2) 因为 2+0=2-0,所以 L(2,0) 为真.
(3) 对于除 0 以外的任何 y,均有 1+y\neq 1-y,所以,\forall yL(1,y) 为假.
(4) 对于任意的 x,都有 x+2\neq x-2,所以,\exists xL(x,2) 为假.
(5) 取 y=0,均有 x+0=x-0,所以 \exists x\exists yL(x,y) 为真.
(6) 取 y=0,对于任何 x,均有 x+0=x-0,故有 \forall x\exists yL(x,y) 为真.
(7) 取 y=0,则 \forall xL(x,0)(即 \forall x(x+0=x-0))为真,故 \exists y\forall xL(x,y) 为真.
(8) 只要 y\neq 0,就有 x+y\neq x-y,所以,\forall x\forall yL(x,y) 为假.
3.8 在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值.
(1) 对于任意的 x,均有 x^2-2=(x+\sqrt{2})(x-\sqrt{2}).
(2) 存在 x,使得 x+5=9.
其中,(a) 个体域为自然数集合. (b) 个体域为实数集合.
解答 设 F(x): x^2-2=(x+\sqrt{2})(x-\sqrt{2}),G(x): x+5=9.
(a) (1) \forall xF(x),其真值为 0.
(2) \exists xG(x),其真值为 1.
(b) (1) \forall xF(x),其真值为 1.
(2) \exists xG(x),其真值为 1.
分析 本题说明,在不同个体域中,同一个命题的符号化形式可能相同,但真值可能不同.
3.9 设个体域为整数集 \mathbf{Z},确定下列各公式的真值.
(1) \forall x(x^2>0). (2) \exists x(x^2=0).
(3) \forall x(x^2\geqslant x). (4) \forall x\exists y(x^2<y).
(5) \exists x\forall y(x<y^2). (6) \forall x\exists y(x+y=0).
(7) \exists x\exists y(x^2+y^2=6). (8) \forall x\forall y\exists z(z=(x+y)/2).
解答 (1),(7),(8)的真值为 0;(2),(3),(4),(5),(6)的真值为 1.
分析 (1) 因为 0\in\mathbf{Z},而 0^2=0,所以 \forall x(x^2>0) 为假命题.
(2) 因为 0\in\mathbf{Z},且 0^2=0,所以 \exists x(x^2=0) 为真命题.
(3) \forall x\in\mathbf{Z},若 x=0,则 0^2=0,若 x\neq 0,则 x^2>x,所以命题 \forall x(x^2\geqslant x) 为真命题.
(4) 对于任意的 x\in\mathbf{Z},取 y=x^2+1,则 y\in\mathbf{Z},并且 x^2<y,所以 \forall x\exists y(x^2<y) 为真命题.
(5) 取 x 为负整数,比如 x=-1,则对于任意整数 y,均有 -1<y^2,所以 \exists x\forall y(x<y^2) 为真命题.
(6) 对于任意的 x\in\mathbf{Z},若 x=0,则取 y=0,若 x\neq 0,则取 y=-x,均有 x+y=0,所以 \forall x\exists y(x+y=0) 为真命题.
(7) 在整数集合 \mathbf{Z} 中,不存在 x,y,使得 x^2+y^2=6,所以 \exists x\exists y(x^2+y^2=6) 为假命题.
(8) 当 x 与 y 一个为奇数,另一个为偶数时,(x+y)/2 不在 \mathbf{Z} 中,所以 \forall x\forall y\exists z(z=(x+y)/2) 为假命题.
3.10 在一阶逻辑中将下列命题符号化.
(1) 没有不吃饭的人.
(2) 在北京卖菜的人不全是东北人.
(3) 自然数全是整数.
(4) 有的人天天锻炼身体.
解答 本题中没指定个体域,因而使用全总个体域,并且要引入特性谓词.
(1) \neg \exists x(F(x)\wedge \neg G(x))\Leftrightarrow \forall x(F(x)\rightarrow G(x))
其中,F(x): x 为人,G(x): x 吃饭.
(2) \neg \forall x(F(x)\rightarrow G(x))\Leftrightarrow \exists x(F(x)\wedge \neg G(x))
其中,F(x): x 在北京卖菜,G(x): x 是东北人.
(3) \forall x(F(x)\rightarrow G(x))
其中,F(x): x 为自然数,G(x): x 是整数.
(4) \exists x(F(x)\wedge G(x))
其中,F(x): x 为人,G(x): x 天天锻炼身体.
3.11 在一阶逻辑中将下列命题符号化.
(1) 火车都比汽车快.
(2) 有的火车比有的汽车快.
(3) 不存在比所有火车都快的汽车.
(4) 说凡是汽车就比火车慢是不对的.
解答 本题中没指定个体域,因而使用全总个体域. 设 F(x): x 是火车,G(y): y 是汽车,L(x,y): x 比 y 快,H(x,y): x 比 y 慢.
(1) \forall x(F(x)\rightarrow \forall y(G(y)\rightarrow L(x,y)))
(2) \exists x(F(x)\wedge \exists y(G(y)\wedge L(x,y)))
(3) \neg \exists y(G(y)\wedge \forall x(F(x)\rightarrow L(y,x)))
(4) \neg \forall y(G(y)\rightarrow \exists x(F(x)\wedge H(y,x)))
分析 以上 4 个命题的符号化还有不同形式. 利用主教材 3.2 节的等值式和置换规则可进行如下的演算.
(1)
通过以上演算可知:
因而,(1)中命题常符号化为
(2)
(3)
由以上演算可知,(3)中命题符号化为
或
都可以. 请将后一种形式翻译成自然语言.
(4)
由以上演算可知,(4)中命题可符号化为
或
请将后一种形式翻译成自然语言.
3.12 将下列命题符号化,个体域为实数集合 \mathbf{R},并指出各命题的真值.
(1) 对于任意的整数 x 和 y,存在着整数 z,使得 x-y=z.
(2) 存在着整数 x,使得对任意的整数 y 都有 x\cdot y=0.
(3) 对于任意的整数 x,存在着整数 y,使得 y=x+1.
(4) 对任意的整数 x 和 y 都有 x\cdot y=y\cdot x.
解答 (1) \forall x\exists y\exists z(x\cdot y=0),真值为 1.
(2) \exists x\forall y(x\cdot y=0),真值为 1.
(3) \forall x\exists y(y=x+1),真值为 1.
(4) \forall x\forall y(x\cdot y=y\cdot x),真值为 1.
分析 因为本题中给定的 x 与 y 的关系比较简单,因而没有引入 2 元谓词符号. 若引入 2 元谓词符号也可以. 如设 F(x,y): x\cdot y=0, G(x,y): y=x+1, H(x,y): x\cdot y=y\cdot x. 则有
(1) \forall x\exists y\exists zF(x,y).
(2) \exists x\forall yF(x,y).
(3) \forall x\exists yG(x,y).
(4) \forall x\forall yH(x,y).
3.13 将下列各公式翻译成自然语言,个体域为整数集 \mathbf{Z},并判断各命题的真假.
(1) \forall x\forall y\exists z(x-y=z). (2) \forall x\exists y(x\cdot y=1).
(3) \exists x\forall y\forall z(x+y=z).
解答 (1) "对于任意的整数 x 和 y,都存在着整数 z,使得 x-y=z"是真命题.
(2) "对于任意的整数 x,都存在着整数 y,使得 x\cdot y=1"是假命题.
(3) "存在着整数 x,对于任意的整数 y 和 z,都有 x+y=z"是假命题.
分析 ① 用反例说明(2)是假命题. 取 x=5,在 \mathbf{Z} 中不存在 y,使得 x\cdot y=1.
② 对于命题(3),不可能存在固定的 x_0,使得对于任意的 y 和 z,都有 x_0+y=z,x 应随着 y,z 的变化而变化. 例如,y=7,z=10 时,x 应为 3;当 y=2,z=9 时,x 应为 7,所以(3)为假命题. 若将(3)变为 \forall y\forall z\exists x(x+y=z),则得到一个真命题. 此例说明,量词的顺序不能随便颠倒.
3.14 指出下列公式中的指导变元,量词的辖域,各个体变项的自由出现和约束出现.
(1) \forall x(F(x)\rightarrow G(x,y)).
(2) \forall xF(x,y)\rightarrow \exists yG(x,y).
(3) \forall x\exists y(F(x,y)\wedge G(y,z))\vee \exists xH(x,y,z).
解答 (1) 在公式 \forall x(F(x)\rightarrow G(x,y)) 中,\forall x 中的 x 为指导变元. 量词 \forall 的辖域 A=(F(x)\rightarrow G(x,y)),在 A 中 x 都是约束出现的,而 y 是自由出现的.
(2) 在公式 \forall xF(x,y)\rightarrow \exists yG(x,y) 中,\forall x 中的 x 和 \exists y 中的 y 都是指导变元. \forall 的辖域为 F(x,y),其中 x 是约束出现的,而 y 是自由出现的. \exists 的辖域为 G(x,y),其中,x 是自由出现的,y 是约束出现的.
(3) 在公式 \forall x\exists y(F(x,y)\wedge G(y,z))\vee \exists xH(x,y,z) 中,\forall x 中的 x,\exists y 中的 y,\exists x 中的 x 都是指导变元. \exists y 中 \exists 的辖域为 (F(x,y)\wedge G(y,z)),\forall x 中 \forall 的辖域为 \exists y(F(x,y)\wedge G(y,z)),其中 x,y 是约束出现的,而 z 是自由出现的. \exists x 中 \exists 的辖域为 H(x,y,z),x 是约束出现的,y,z 是自由出现的. 在整个公式中,x 约束出现两次,y 约束出现两次,自由出现一次,z 自由出现两次.
3.15 给定解释 I 如下:
(a) 个体域 D_I 为实数集 \mathbf{R}.
(b) \bar{a}=0.
(c) \bar{f}(x,y)=x-y,x,y\in D_I.
(d) \bar{F}(x,y): x=y, \bar{G}(x,y): x<y,x,y\in D_I.
说明下列公式在 I 下的含义,并指出各公式的真值.
(1) \forall x\forall y(G(x,y)\rightarrow \neg F(x,y)).
(2) \forall x\forall y(F(f(x,y),a)\rightarrow G(x,y)).
(3) \forall x\forall y(G(x,y)\rightarrow \neg F(f(x,y),a)).
(4) \forall x\forall y(G(f(x,y),a)\rightarrow F(x,y)).
解答 (1) "对于任意的实数 x 和 y,若 x<y,则 x\neq y"是真命题.
(2) "对于任意的实数 x 和 y,若 x-y=0,则 x<y"是假命题.
(3) "对于任意的实数 x 和 y,若 x<y,则 x-y\neq 0"是真命题.
(4) "对于任意的实数 x 和 y,若 x-y<0,则 x=y"是假命题.
3.16 给定解释 I 如下:
(a) 个体域 D=\mathbf{N}(\mathbf{N} 为自然数集).
(b) \bar{a}=2.
(c) D 上函数 \bar{f}(x,y)=x+y,\bar{g}(x,y)=x\cdot y.
(d) D 上谓词 \bar{F}(x,y): x=y.
及赋值 \sigma: \sigma(x)=0,\sigma(y)=1,\sigma(z)=2.
说明下列各式在 I 及 \sigma 下的含义,并讨论其真值.
(1) \forall xF(g(x,a),y).
(2) \forall x(F(f(x,a),y)\rightarrow \forall yF(f(y,a),x)).
(3) \forall x\forall y\exists zF(f(x,y),z).
(4) \exists xF(f(x,y),g(x,z)).
解答 (1) "对于任意的自然数 x,均有 x\times 2=1"是假命题.
(2) "对于任意的自然数 x,如果 x+2=1,则对于任意的自然数 y,y+2=x"是真命题.
(3) "对于任意的自然数 x 和 y,都存在着自然数 z,使得 x+y=z"是真命题.
(4) "存在自然数 x,使得 x+1=2x"是真命题.
3.17 判断下列各式的类型.
(1) F(x,y)\rightarrow(G(x,y)\rightarrow F(x,y)).
(2) \forall x(F(x)\rightarrow F(x))\rightarrow \exists y(G(y)\wedge \neg G(y)).
(3) \forall x\exists yF(x,y)\rightarrow \exists y\forall xF(x,y).
(4) \exists x\forall yF(x,y)\rightarrow \forall y\exists xF(x,y).
(5) \forall x\forall y(F(x,y)\rightarrow F(y,x)).
(6) \neg(\forall xF(x)\rightarrow \exists yG(y))\wedge \exists yG(y).
(7) \exists xF(x,y).
(8) \exists xF(x,y)\rightarrow \forall yF(x,y).
解答 (1),(4)为永真式(逻辑有效式),(2),(6)为永假式(矛盾式),(3),(5),(7),(8)为非永真式的可满足式.
分析 在一阶逻辑中,判断给定公式的类型不是一件易事. 由定义 3.8 可知,A 为永真式当且仅当 A 无成假解释和赋值,A 为矛盾式当且仅当 A 无成真解释和赋值,A 为非永真式的可满足式当且仅当 A 存在成真的解释和赋值并且存在成假的解释和赋值. 由于公式的复杂性,解释的多样性,判断一阶逻辑公式的类型是不可判定的.
由于本题给出的 8 个公式的特殊性,还是可以判断其类型的. 下面逐个进行分析.
(1) 设(1)中公式为 A.
方法 1 等值演算法:
方法 2 重言式的代换实例:
注意到 p\rightarrow(q\rightarrow p) 为命题逻辑中的重言式,而公式 A 为它的代换实例,由定理 3.2 可知,A 为永真式.
(2) 设(2)中公式为 B.
由以上等值式可知,对于任意的解释 I,B 的前件均为真,而 B 的后件均为假,于是 B 为矛盾式.
(3) 设(3)中公式为 C.
下面论证 C 既有成真的解释,又有成假的解释.
设解释 I_1 为: 个体域为整数集 \mathbf{Z},F(x,y): x<y. 在 I_1 下,C 的前件 \forall x\exists yF(x,y) 为真,但 C 的后件 \exists y\forall xF(x,y) 为假,所以 I_1 为 C 的成假解释.
设解释 I_2 为: 个体域仍为 \mathbf{Z},F(x,y): x+y=x. 在 I_2 下,C 的前件与后件均为真,故 I_2 为 C 的成真解释.
综上所述,C 不是永真式,也不是矛盾式,它是非永真式的可满足式.
(4) 设(4)中公式为 D.
论证 D 无成假的解释.
设 I 为任意的解释.
① 若在 I 下,D 的前件 \exists x\forall yF(x,y) 为假,则在 I 下 D 为真.
② 若在 I 下,D 的前件 \exists x\forall yF(x,y) 为真,必存在 x_0\in D_I(I 的定义域),使得 \forall yF(x_0,y) 为真. 又由于对于任意 y\in D_I,F(x_0,y) 为真,有 \exists xF(x,y) 为真,从而 \forall y\exists xF(x,y) 为真.
由 I 的任意性可知,D 是永真式.
(5) 设(5)中公式为 E.
设解释 I_1 为: 个体域为整数集合 \mathbf{Z},F(x,y): x=y. 在 I_1 下,E 为真.
设解释 I_2 为: 个体域仍为 \mathbf{Z},F(x,y): x<y. 在 I_2 下,若 F(x,y) 为真,则 F(y,x) 为假,所以在 I_2 下 E 为假.
综上所述,E 是非永真式的可满足式.
(6) 设(6)中公式为 F,可通过等值演算证明 F 为矛盾式.
实际上,F 是矛盾式 \neg(p\rightarrow q)\wedge q 的代换实例.
(7) 设(7)中公式为 G.
取解释 I_1: 个体域 \mathbf{N},F(x,y): x=y;赋值 \sigma(y)=0. 在 I_1 和 \sigma 下,G 为"存在自然数 x,x=0."这是真命题.
取解释 I_2,把 I_1 中 x=y 改为 x<y. 在 I_2 和 \sigma 下,G 为"存在自然数 x,x<0."这是假命题.
故 G 是非永真式的可满足式.
(8) 设(8)中公式为 H.
取解释 I_1: 个体域 \mathbf{N},F(x,y): x\leqslant y;赋值 \sigma: \sigma(x)=\sigma(y)=0. 在 I_1 和 \sigma 下,H 为"存在自然数 x\leqslant 0 蕴涵所有的自然数 y\geqslant 0."这是真命题.
取解释 I_2,把 I_1 中 x\leqslant y 改为 x=y. 在 I_2 和 \sigma 下,G 为"存在自然数 x=0 蕴涵所有的自然数 y=0."这是假命题.
故 H 是非永真式的可满足式.
说明 (2),(3),(4),(5)都是闭式,只需考虑解释,而用不着赋值.
3.18 (1) 给出一个非闭式的永真式.
(2) 给出一个非闭式的永假式.
(3) 给出一个非闭式的可满足式,但不是永真式.
解答 (1) \forall xF(x,y)\rightarrow \forall xF(x,y),G(x,y,z)\vee \neg G(x,y,z) 等都是非闭式,它们都是永真式.
(2) F(x)\wedge \neg F(x),\forall xF(x,y)\wedge \exists x\neg F(x,y) 等都是非闭式,它们都是矛盾式.
(3) F(x,y)\rightarrow G(x,y) 是非闭式,它是可满足式,但不是永真式.
分析 注意(2)中后一个公式:
3.19 证明下面公式既不是永真式也不是矛盾式.
(1) \forall x(F(x)\rightarrow \exists y(G(y)\wedge H(x,y))).
(2) \forall x\forall y(F(x)\wedge G(y)\rightarrow H(x,y)).
解答 一个公式 A 不是永真式当且仅当 A 存在着成假的解释和赋值,A 不是矛盾式当且仅当 A 存在着成真的解释和赋值. 这两个公式都闭式,只需要考虑解释.
(1) 设(1)中公式为 A.
① 设解释 I_1 为: 个体域为非 0 自然数集 \mathbf{N}^+,F(x): x 为偶数,G(y): y 为奇数,H(x,y): x\,|\,y(x 整除 y). 在解释 I_1 下,A 为假命题,所以 A 不是永真式.
② 设解释 I_2 为: 个体域为实数集 \mathbf{R},F(x): x 为有理数,G(y): y 为分数,H(x,y): x=y. 在 I_2 下 A 为真命题,所以 A 不是矛盾式.
综上所述,A 为可满足式,但不是永真式.
(2) 设(2)中公式为 B.
① 设解释 I_1 为: 全总个体域,F(x): x 为马,G(y): y 为骡,H(x,y): x 与 y 跑得同样快. 在 I_1 下,B 为假命题,所以 B 不是永真式.
② 设解释 I_2 为: 全总个体域,F(x): x 为飞机,G(y): y 为轮船,H(x,y): x 比 y 快,在 I_2 下 B 为真命题,所以 B 不是矛盾式.
综上所述,B 是可满足式,但不是永真式.
3.20 将下列各式的否定号内移,使得否定号只能出现在谓词前.
(1) \neg \exists x\exists yL(x,y).
(2) \neg \forall x\forall yL(x,y).
(3) \neg \exists x(F(x)\wedge \forall y\neg L(x,y)).
(4) \neg \forall x(\exists yL(x,y)\vee \forall yH(x,y)).
解答 解本题时应该应用量词否定等值式.
(1)
(2)
(3)
最后一步也用上了双重否定律.
(4)
3.21 将下列公式化成与之等值的公式,使其没有既是约束出现的,又是自由出现的个体变项.
(1) \forall xF(x,y)\wedge \exists yG(x,y,z).
(2) \exists x(F(x,y)\wedge \forall yG(x,y)).
解答 解本题时,使用换名规则.
(1)
(2)
3.22 证明:
(1) \forall x(A(x)\rightarrow B(x))\not\Leftrightarrow \forall x(A(x)\wedge B(x)).
(2) \exists x(A(x)\wedge B(x))\not\Leftrightarrow \exists x(A(x)\rightarrow B(x)).
其中,A(x),B(x) 为含 x 自由出现的公式.
解答 证明本题,只需要找到解释 I,用具体的谓词代替 A(x) 和 B(x),使其对应的两个命题不等值即可.
(1) 取解释 I_1: 个体域为全总个体域,取 A(x): x 为人,B(x): x 呼吸. 此时,"\forall x(A(x)\rightarrow B(x))"翻译成自然语言为"人都呼吸",这是真命题. 而"\forall x(A(x)\wedge B(x))"翻译成自然语言应为"宇宙中的一切事物都是人并且呼吸",这显然是假命题. 这说明公式 (\forall x(A(x)\rightarrow B(x))\leftrightarrow(\forall x(A(x)\wedge B(x))) 存在着成假的解释,因而
(2) 取解释 I_2: 个体域为自然数集合 \mathbf{N},A(x): x 为奇数,B(x): x 为偶数,此时,"\exists x(A(x)\wedge B(x))"翻译成自然语言为"存在自然数 x 既是奇数,又是偶数",这是假命题. 而"\exists x(A(x)\rightarrow B(x))"翻译成自然语言为"存在自然数 x,如果 x 是奇数,则 x 是偶数",这是真命题(例如 A(0)\rightarrow B(0),A(2)\rightarrow B(2) 等均为真),这说明 \exists x(A(x)\wedge B(x))\leftrightarrow \exists x(A(x)\rightarrow B(x)) 存在成假解释,因而
分析 (1) 本题说明"\forall x(A(x)\rightarrow B(x))"与"\forall x(A(x)\wedge B(x))"不等值. 命题"人都吃饭"、"偶数都能被 2 整除"、"兔子跑得快"等都是全称量词加蕴涵语句,都应符号化为"\forall x(A(x)\rightarrow B(x))"的形式,而不能符号化为"\forall x(A(x)\wedge B(x))"的形式.
(2) 本题说明"\exists x(A(x)\wedge B(x))"与"\exists x(A(x)\rightarrow B(x))"不等值. 命题"有的人吸烟"、"存在偶数"、"有百岁老人"等都应符号化为"\exists x(A(x)\wedge B(x))"的形式,而不应该符号化为"\exists x(A(x)\rightarrow B(x))"的形式.
3.23 设个体域 D=\{a,b\},消去下列各公式的量词.
(1) \forall x\exists y(F(x)\wedge G(y)).
(2) \forall x\exists y(F(x)\wedge G(x,y)).
(3) \exists xF(x)\wedge \forall xG(x).
(4) \exists x(F(x,y)\vee \forall yG(y)).
解答 解本题需要注意的是,若量词的辖域能收缩就收缩,使演算的步骤尽量少.
(1)
(2)
(3)
(4)
分析 (1) 若不将量词辖域收缩,则演算过程要长些,特别是,若个体域中元素较多时,过程会更长.
这里没有使用量词辖域收缩与扩张等值式,显然演算过程就长多了,所以,若能应用量词辖域收缩与扩张等值式就应该先用它,然后再消量词. 但如果量词辖域不能缩小,那就只好直接演算了.
(2) 演算到 \forall x(F(x)\wedge \exists yG(x,y)) 后,\forall 的辖域不能再缩小了. 演算也可以如下进行:
(3) \exists xF(x)\wedge \forall xG(x) 的辖域已经不能再缩小了,所以对它消量词最简单,但有人先将它化成前束范式后再消量词,那是自找麻烦.
(4) 注意 F(x,y) 中的 y 在公式中是自由出现的,消量词之后,它依然自由出现.
3.24 设个体域 D=\{a,b,c\},消去下列各公式中的量词.
(1) \forall xF(x)\rightarrow \forall yG(y).
(2) \forall x(F(x,y)\rightarrow \exists yG(y)).
解答 (1) 本题量词辖域已不能再缩小,因而直接消量词.
(2) 注意 F(x,y) 中的 y 在公式中是自由出现的,\exists yG(y) 中不含 x,因而 \forall 的辖域可以缩小.
3.25 设个体域 D=\{1,2\},请给出两种不同的解释 I_1 和 I_2,使得下面公式在 I_1 下都是真命题,而在 I_2 下都是假命题.
(1) \forall x(F(x)\rightarrow G(x)).
(2) \exists x(F(x)\wedge G(x)).
解答 解此题,先消去量词比较方便.
(1)
(2)
取 I_1: 个体域 D=\{1,2\},F(x): x\geqslant 1,G(x): x\leqslant 2,在 I_1 下,F(1),F(2),G(1),G(2) 均为真,所以,(1)与(2)中公式在 I_1 下全真.
取 I_2: 个体域 D=\{1,2\},F(1)=1,F(2)=0,G(1)=0,G(2)=1,在 I_2 下,(1)与(2)中公式全为假.
3.26 给定公式 A=\exists xF(x)\rightarrow \forall xF(x).
(1) 在解释 I_1 中,个体域 D_1=\{a\},证明公式 A 在 I_1 下的真值为 1.
(2) 在解释 I_2 中,个体域 D_2=\{a_1,a_2,\cdots,a_n\},n\geqslant 2,A 在 I_2 下的真值还一定是 1 吗? 为什么?
解答 (1) 在 I_1 下,公式 A=\exists xF(x)\rightarrow \forall xF(x)\Leftrightarrow F(a)\rightarrow F(a)\Leftrightarrow \neg F(a)\vee F(a)\Leftrightarrow 1,所以,在 I_1 下公式 A 为真.
(2) 在 I_2 下,A 不一定为真.
在 D_2 中消去量词,得
当 F(a_1),F(a_2),\cdots,F(a_n) 中至少有 1 个为真,但不全为真时,蕴涵式的前件为真,后件为假,所以蕴涵式为假. 当 F(a_1),F(a_2),\cdots,F(a_n) 全为真时,A 为真.
3.27 给定解释 I 如下:
(a) 个体域 D=\{3,4\}.
(b) \bar{f}(x) 为 \bar{f}(3)=4,\bar{f}(4)=3.
(c) \bar{F}(x,y) 为 \bar{F}(3,3)=\bar{F}(4,4)=0,\bar{F}(3,4)=\bar{F}(4,3)=1.
试求下列公式在 I 下的真值.
(1) \forall x\exists yF(x,y).
解答 在本题中,由于个体域 D 中只含 2 个元素,因而可以消去量词,进行演算.
(1)
(2)
(3)
3.28 在一阶逻辑中将下面命题符号化,要求用两种不同的等值形式.
(1) 没有小于负数的正数.
(2) 相等的两个角未必都是对顶角.
解答 本题中没有指定个体域,因而使用全总个体域.
(1) 设 F(x): x 为正数,G(y): y 为负数,H(x,y): x<y.
① \neg \exists x\exists y(F(x)\wedge G(y)\wedge H(x,y)).
② \forall x\forall y(F(x)\wedge G(y)\rightarrow \neg H(x,y)).
(2) 设 F(x): x 为角,H(x,y): x=y,L(x,y): x 与 y 为对顶角.
① \neg \forall x\forall y(F(x)\wedge F(y)\wedge H(x,y)\rightarrow L(x,y)).
② \exists x\exists y(F(x)\wedge F(y)\wedge H(x,y)\wedge \neg L(x,y)).
分析 证明两种不同形式的符号化形式是等值的.
(1)
由以上的证明可知,①\Leftrightarrow②.
其实,由②开始演算也可以.
(2)
由以上演算可知①\Leftrightarrow②.
从②开始演算也可以.
3.29 求下列各式的前束范式.
(1) \exists xF(x)\rightarrow \forall yG(x,y).
(2) \forall x(F(x,y)\rightarrow \forall yG(x,y,z)).
解答
(1)
(2)
3.30 求下列各式的前束范式.
(1) F(x)\wedge G(x)\rightarrow L(x,y).
(2) \forall x_1(F(x_1)\rightarrow G(x_1,x_2))\rightarrow(\exists x_2H(x_2)\rightarrow \exists x_3L(x_2,x_3)).
(3) \exists x_1F(x_1,x_2)\rightarrow(H(x_1)\rightarrow \neg \exists x_2G(x_1,x_2)).
解答 (1) F(x)\wedge G(x)\rightarrow L(x,y) 已为前束范式.
(2)
在以上演算中,第一步使用换名规则,将指导变元 x_1 及其 2 个约束出现替换成 x_4,将指导变元 x_2 及紧随其后的一个约束出现替换成 x_5;在第二步和第三步将蕴涵式的后件用量词辖域收缩与扩张等值式化成前束范式;第四步\sim第六步将整个公式化成了前束范式. 在演算中注意正确地使用量词辖域收缩与扩张等值式.
(3)
3.31 将下列命题符号化,要求符号化的公式为前束范式.
(1) 有的汽车比有的火车跑得快.
(2) 有的火车比所有的汽车跑得快.
(3) 说所有的火车比所有汽车都跑得快是不对的.
(4) 说有的飞机比有的汽车慢是不对的.
解答 本题没指定个体域,因而使用全总个体域.
(1) 设 F(x): x 为汽车,G(y): y 是火车,H(x,y): x 比 y 跑得快,则
最后一步用量词辖域收缩与扩张等值式及结合律,所得公式为前束范式.
(2) 设 F(x): x 是火车,G(y): y 是汽车,H(x,y): x 比 y 跑得快,则
最后一步所得公式为前束范式.
(3) 设 F(x): x 是火车,G(y): y 是汽车,H(x,y): x 比 y 跑得快,则
最后一步得公式即所求前束范式.
(4) 设 F(x): x 为飞机,G(y): y 为汽车,H(x,y): x 比 y 慢,则
最后一步所得公式为前束范式.
3.32 求下列各公式的前束范式.
(1) \exists xF(x)\vee \exists xG(x)\vee L(x,y).
(2) \neg(\forall xF(x)\vee \forall xG(x)).
解答 (1) 可用两种方法求(1)中公式的前束范式.
方法 1 利用存在量词 \exists 对 \vee 适合分配律.
方法 2 不用 \exists 对 \vee 的分配律.
(2)
最后两步所得公式都是前束范式. 注意,\forall 对 \vee 无分配律.