离散数学习题解 17
习题四
4.1. 将下面命题用 0 元谓词符号化: (1)小王学过英
语和法语. (2)除非李建是东北人, 否则他一定怕冷.
(1) 令 F(x): x 学过英语; F(x): x 学过法语; a: 小王. 符号化为
F(a)?F(b).
或进一步细分, 令 L(x, y): x 学过 y; a: 小王; b1: 英语; b2: 法语. 则符号化为
L(a, b1)?L(a, b2).
(2) 令 F(x): x 是东北人; G(x): x 怕冷; a: 李建. 符号化为
?F(a)?G(a) 或 ?G(a)?F(a).
或进一步细分, 令 H(x, y): x 是 y 地方人; G(x): x 怕冷; a: 小王; b: 东北. 则符号化为
?H(a, b)?G(a) 或 ?G(a)??H(a, b).
4.2. 在一阶逻辑中将下面命题符号化, 并分别讨论个体域限制为(a),(b)时命题的真值:
(1)凡有理数都能被 2 整除.
(2)有的有理数能被 2 整除. 其中(a)个体域为有理数集合, (b)个体域为实数集合.
(1)(a)中, ?xF(x), 其中, F(x): x 能被 2 整除, 真值为 0.
(b)中, ?x(G(x) ?F(x)), 其中, G(x): x 为有理数, F(x)同(a)中, 真值为 0. (2)(a)中, ?xF(x), 其中, F(x): x 能被 2 整除, 真值为 1.
(b)中, ?x(G(x) ?F(x)), 其中, F(x)同(a)中, G(x): x 为有理数, 真值为 1.
4.3. 在一阶逻辑中将下面命题符号化, 并分别讨论个体域限制为(a),(b)时命题的真值: (1)对于任意的 x, 均有 x2?2=(x+ 2 )(x????2 ). (2)存在 x, 使得 x+5=9. 其中(a)个体域为自然数集合, (b)个体域为实数集合.
(1)(a)中, ?x(x2?2=(x+ 2 )(x????2 )), 真值为 1.
(b)中, ?x(F(x) ??(x2?2=(x+ 2 )(x????2 )))), 其中, F(x): x 为实数, 真值为 1. (2)(a)中, ?x(x+5=9), 真值为 1.
(b)中, ?x(F(x) ??(x+5=9)), 其中, F(x): x 为实数, 真值为 1.
4.4. 在一阶逻辑中将下列命题符号化: (1)没有不能表示成分数的有理数. (2)在北京卖菜的人不全是外地人.
离散数学习题解
(3)乌鸦都是黑色的. (4)有的人天天锻炼身体.
18
没指定个体域, 因而使用全总个体域.
(1) ??x(F(x) ??G(x))或?x(F(x) ?G(x)), 其中, F(x): x 为有理数, G(x): x 能表示成分数. (2) ??x(F(x) ?G(x))或?x(F(x) ??G(x)), 其中, F(x): x 在北京卖菜, G(x): x 是外地人. (3) ?x(F(x) ?G(x)), 其中, F(x): x 是乌鸦, G(x): x 是黑色的. (4) ?x(F(x) ?G(x)), 其中, F(x): x 是人, G(x): x 天天锻炼身体.
4.5. 在一阶逻辑中将下列命题符号化: (1)火车都比
轮船快. (2)有的火车比有的汽车快. (3)不存在比所有火车都快的汽车. (4)“凡是汽车就比火车慢”是不对的.
因为没指明个体域, 因而使用全总个体域
(1) ?x?y(F(x) ?G(y) ?H(x,y)), 其中, F(x): x 是火车, G(y): y 是轮船, H(x,y):x 比 y 快. (2) ?x?y(F(x) ?G(y) ?H(x,y)), 其中, F(x): x 是火车, G(y): y 是汽车, H(x,y):x 比 y 快. (3) ??x(F(x) ??y(G(y) ?H(x,y)))
或?x(F(x) ??y(G(y) ??H(x,y))), 其中, F(x): x 是汽车, G(y): y 是火车, H(x,y):x 比 y 快. (4) ??x?y(F(x) ?G(y) ?H(x,y))
或?x?y(F(x) ?G(y) ??H(x,y) ), 其中, F(x): x 是汽车, G(y): y 是火车, H(x,y):x 比 y 慢.
4.6. 略
4.7. 将下列各公式翻译成自然语言, 个体域为整数集 ?, 并判断各命题的真假.
(1) ?x?y?z(x ??y = z); (2) ?x?y(x?y = 1).
(1) 可选的翻译:
①“任意两个整数的差是整数.”
② “对于任意两个整数, 都存在第三个整数, 它等于这两个整数相减.” ③ “对于任意整数 x 和 y, 都存在整数 z, 使得 x ??y = z.” 选③, 直接翻译, 无需数理逻辑以外的知识. 以下翻译意思相同, 都是错的:
??“有个整数, 它是任意两个整数的差.”
??“存在一个整数, 对于任意两个整数, 第一个整数都等于这两个整数相减.” ??“存在整数 z, 使得对于任意整数 x 和 y, 都有 x ??y = z.” 这 3 个句子都可以符号化为
?z?x?y(x ??y = z).
0量词顺序不可随意调换. (2) 可选的翻译:
离散数学习题解
①“每个整数都有一个倒数.”
② “对于每个整数, 都能找到另一个整数, 它们相乘结果是零.” ③ “对于任意整数 x, 都存在整数 y, 使得 x?y = z.” 选③, 是直接翻译, 无需数理逻辑以外的知识.
19
4.8. 指出下列公式中的指导变元, 量词的辖域, 各个体变项的自由出现和约束出现: (3)?x?y(F(x, y) ??G(y, z)) ???xH(x, y, z)
?x?y(F(x, y) ??G(y, z)) ???xH(x, y, z)
前件 ?x?y(F(x, y)?G(y, z)) 中, ??的指导变元是 x, ??的辖域是 ?y(F(x, y)?G(y, z)); ??的指导变元是 y, ??的辖域 是 (F(x, y)?G(y, z)).
后件 ?xH(x, y, z) 中, ??的指导变元是 x, ??的辖域是 H(x, y, z).
整个公式中, x 约束出现两次, y 约束出现两次, 自由出现一次; z 自由出现两次.
4.9. 给定解释 I 如下: (a)个体
域 DI 为实数集合\\.
(b)DI 中特定元素?a =0. (c)特定函数?f (x,y)=x?y, x,y∈DI.
(d)特定谓词?F(x,y): x=y,?G(x,y): x (4) ?x?y(G(f(x,y),a) ?F(x,y)) (1) ?x?y(x 4.10.给定解释 I 如下: (a)个体域 D=?(?为自然数). (b)D 中特定元素?a=2. (c)D 上函数?f (x,y)=x+y,?g (x,y)=x·y. (d)D 上谓词?F (x,y): x=y. 说明下列公式在 I 下的含义, 并指出各公式的真值: (1) ?xF(g(x,a),x) (2) ?x?y(F(f(x,a),y) ?F(f(y,a),x)) (3) ?x?y?z(F(f(x,y),z) (4) ?xF(f(x,x),g(x,x)) 离散数学习题解 (1) ?x(x·2=x), 真值为 0. (2) ?x?y((x+2=y) ??(y+2=x)), 真值为 0. (3) ?x?y?z(x+y=z),真值为 1. (4) ?x(x+x=x·x),真值为 1. 20 4.11.判断下列各式的类型: (1) F(x, y) ??(G(x, y) ??F(x, y)). (3) ?x?yF(x, y) ???x?yF(x, y). (5) ?x?y(F(x, y) ??F(y, x)). (1) 是命题重言式 p ??(q ??p) 的代换实例, 所以是永真式. (3) 在某些解释下为假(举例), 在某些解释下为真(举例), 所以是非永真式的可满足式. (5) 同(3). 4.12.P69 12. 设 I 为一个任意的解释, 在解释 I 下, 下面哪些公式一定是命题? (1) ?xF(x, y) ???yG(x, y). (2) ?x(F(x) ??G(x)) ???y(F( y) ??H( y)). (3) ?x(?yF(x, y) ???yG(x, y)). (4) ?x(F(x) ??G(x)) ??H( y). (2), (3) 一定是命题, 因为它们是闭式. 4.13.略 4.14.证明下面公式既不是永真式也不是矛盾式: (1) ?x(F(x) ??y(G(y) ?H(x,y))) (2) ?x?y(F(x) ?G(y) ?H(x,y)) (1) 取个体域为全总个体域. 解释 I1: F(x): x 为有理数, G(y): y 为整数, H(x,y): x 在 I1 下: ?x(F(x) ??y(G(y) ?H(x,y)))为真命题, 所以该公式不是矛盾式. 解释 I2: F(x),G(y)同 I1, H(x,y): y 整除 x. 在 I2 下: ?x(F(x) ??y(G(y) ?H(x,y)))为假命题, 所以该公式不是永真式. (2) 请读者给出不同解释, 使其分别为成真和成假的命题即可. 4.15.(1) 给出一个非闭式的永真式. (2) 给出一个非闭式的永假式. (3) 给出一个非闭式的可满足式, 但不是永真式. (1) F(x) ???F(x). (2) F(x) ???F(x). (3) ?x(F(x, y) ??F(y, x)).