离散数学答案(尹宝林版)第二章习题解答

第二章第二章 谓词逻辑谓词逻辑 习题与解答习题与解答 1 将下列命题符号化 1 所有的火车都比某些汽车快 2 任何金属都可以溶解在某种液体中 3 至少有一种金属可以溶解在所有液体中 4 每个人都有自己喜欢的职业 5 有些职业是所有的人都喜欢的 解解 1 取论域为所有交通工具的集合 令 是火车 是汽车 比y跑得快 xxT xxC xyxF 所有的火车都比某些汽车快 可以符号化为 yxFyCyxTx 2 取论域为所有物质的集合 令 是金属 是液体 可以溶解在y中 xxM xxL xyxD 任何金属都可以溶解在某种液体中 可以符号化为 yxDyLyxMx 3 论域和谓词与 2 同 至少有一种金属可以溶解在所有液体中 可以符号化为 yxDyLyxMx 4 取论域为所有事物的集合 令 是人 是职业 喜欢y xxM xxJ xyxL 每个人都有自己喜欢的职业 可以符号化为 yxLyJyxMx 5 论域和谓词与 4 同 有些职业是所有的人都喜欢的 可以符号化为 xyLyMyxJx 2 取论域为正整数集 用函数 加法 乘法 和谓词 将下列命题符号化 1 没有既是奇数 又是偶数的正整数 2 任何两个正整数都有最小公倍数 3 没有最大的素数 4 并非所有的素数都不是偶数 解解 先引进一些谓词如下 能被y整除 可表示为 xyxD yxD xyvv 是奇数 可表示为 xxJ xJ 2 xvv 是偶数 可表示为 xxE xE 2 xvv 是素数 可表示为 xxP xP 1 1 xuuxuvvux 1 没有既是奇数 又是偶数的正整数 可表示为 xExJx 并可进一步符号化为 2 2 xvvxvvx 2 任何两个正整数都有最小公倍数 可表示为 uzuzyuDxuDuyzDxzDzyx 并可进一步符号化为 uzuzuyvvuxvvuzyvvzxvvzyx 3 没有最大的素数 可表示为 xyxyyPyxPx 并可进一步符号化为 1 1 1 1 xyxyyuuyuvvuyy xuuxuvvuxx 4 并非所有的素数都不是偶数 可表示为 并可进一步符号化 xExPx 为 2 1 1 xvvxuuxuvvuxx 3 取论域为实数集合 用函数 减法 和谓词 将下列命题符号化 1 没有最大的实数 2 任何两个不同的实数之间必有另一实数 3 函数在点a处连续 xf 4 函数恰有一个根 xf 5 函数是严格单调递增函数 xf 解解 1 没有最大的实数 符号化为 xyxyyx 2 任何两个不同的实数之间必有另一实数 符号化为 yzzxzyxyx 3 函数在点a处连续 的定义是 xf 任给 总可以找到 使得只要就有 0 0 ax afxf 函数在点a处连续 符号化为 xf 0 0 afxfxfafaxxax 4 函数恰有一个根 符号化为 xf 0 0 xyyfyxfx 5 函数是严格单调递增函数 符号化为 xf yfxfyxyx 4 指出下列公式中变元的约束出现和自由出现 并对量词的每次出现指出其辖域 1 axPxyPx 2 yxzQxxP 3 xQxxPxRxPx 4 yxgzxPxyxfPy 5 xRxxRxQxPx 解解 1 变元 x 在中三次出现都是约束出现 x 的唯一出现的辖 axPxyPx 域是 P y x P x a 2 变元 x 在中的头两次出现是约束出现 第三次出现是自由出现 yxzQxxP 变元 y 在中的唯一出现是自由出现 变元 z 在 yxzQxxP 中的唯一出现是约束出现 x 的唯一出现的辖域是 P x z 的唯 yxzQxxP 一出现的辖域是 Q x y 3 变元 x 在中的头五次出现是约束出现 第六次出 xQxxPxRxPx 现是自由出现 x 的第一次出现的辖域是 P x R x 第二次出现的辖域是 P x 4 变元 x 在中的头两次出现是自由出现 后两次 yxgzxPxyxfPy 出现是约束出现 x 的唯一出现的辖域是 P z g x y y 的唯一出现的辖域是 P f x y x xP z g x y 5 变元 x 在中的头五次出现是约束出现 第六次出 xRxxRxQxPx 现是自由出现 x 的唯一出现的辖域是 P x Q x xR x x 的唯一出现的辖域是 R x 5 归纳证明 若t 是项 则也是项 t x t t 证明证明 若t是x 则是 是项 x t t t x t t 若t是不同于x的变元y 则仍是y 是项 x t t x t t 若t是常元a 则仍是a 是项 x t t x t t 若t是 则是 由归纳假设知都是项 1n ttf x t t 1 x tn x t ttf x tn x t tt 1 所以是项 x t t 6 归纳证明 若t是项 A是公式 则也是公式 x t A 证明证明 若A是 则是 由上题知都 1n ttP x t A 1 x tn x t ttP x tn x t tt 1 是项 所以是公式 x t A 若A是 则是 由归纳假设知是公式 所以是公式 B x t A x t B x t B x t A 若A是 则是 由归纳假设知和都是公式 所以是公CB x t A x t x t CB x t B x t C x t A 式 若A是 则仍是A 是公式 xB x t A x t A 若A是 其中y是不同于x的变元 则是 由归纳假设知是公式 yB x t A x t yB x t B 所以是公式 x t A 7 给定解释I和I中赋值v如下 2 1 I D1 I a2 I b2 1 I f1 2 I f 1 2 1 1 1 II PP0 2 2 1 2 II PP1 xv1 yv 计算下列公式在解释I和赋值I中v下的真值 1 xyfPbfxPxfaP 2 xyyPx 3 yfxfPyxPyx 解解 1 vxyfPbfxPxfaPI xvyvfPbfxvPxvfaP IIIIIIII 1 1 2 1 1 1 IIIIII fPfPfP 0011 1 2 1 1 2 1 III PPP 2 vxyyPxI 2 1 xvxyyPIxvxyyPI 2 1 1 1 yxvxyPIyxvxyPI 2 2 1 2 yxvxyPIyxvxyPI 2 2 2 1 1 2 1 1 IIII PPPP 1 01 01 3 vyfxfPyxPyxI 2 1 2 1 1 1 1 1 IIIIIIII ffPPffPP 2 2 2 2 1 2 1 2 IIIIIIII ffPPffPP 1 1 2 2 2 1 1 2 1 2 2 1 2 2 1 1 IIIIIIII PPPPPPPP 01100 10 10 01 01 7 给定解释I如下 baDI 1 bbPaaP II 0 abPbaP II 判断I是不是以下语句的模型 1 yxyPx 2 yxyPx 3 yxyPx 4 yxPyx 5 xyPyxPyx 6 xxxP 解解 1 yxyPxI 1 10 01 bbPabPbaPaaP IIII 2 yxyPxI 01001 bbPabPbaPaaP IIII 3 yxyPxI 0 10 01 bbPabPbaPaaP IIII 4 yxPyxI 10110 bbPabPbaPaaP IIII 5 xyPyxPyxI abPbaPaaPaaP IIII bbPbbPbaPabP IIII 1 11 00 00 11 6 111 bbPaaPxxxPI II 9 写出一个语句A 使得A有模型 并且A的每个模型的论域至少有三个元素 解解 语句A为 给定解释如下 acPcbPbaPxxPx I 为自然数集合 当且仅当 I D 1 yxPIyx 1 I a2 I b3 I c 则是A的模型 A有模型 I 任取满足语句A的解释I 则 又因为1 IIIIIIIII acPcbPbaP 所以 是论域中三个不同元素 论域中至少有三1 xxPxI I a I b I c I D I D 个元素 10 写出一个语句A 使得A有模型 并且A的每个模型的论域有无穷多个元素 解解 语句A为 给定解 yxyPxzxPzyPyxPyxxxPx 释如下 I 为自然数集合 当且仅当 I D 1 yxPIyx 则是A的模型 A有模型 I 任取满足语句A的解释I 取 因为 所以有使得 I Dd 1 1 yxyPxI I Dd 2 又因为 故 因为 所1 21 ddPI1 xxPxI 21 dd 1 yxyPxI 以有使得 又因为 故 因为 I Dd 3 1 32 ddPI1 xxPxI 23 dd 所以 故 因此 1 zxPzyPyxPyxI1 31 ddPI 13 dd 是论域中的三个不同元素 这个过程可以不断进行下去 得到 1 d 2 d 3 d 因此 论域 DI 中必然有无穷多个元素 321 ddd 11 判断以下公式是不是永真式 永假式 可满足式 并说明理由 1 xQxPxxxQxxP 2 xQxPxxxQxxP 3 xxQxxPxQxPx 4 yxyPxxxxP 5 xQxPxxxQxxP 6 xQxPxxxQxxP 7 xxQxxPxQxPx 解解 1 是永真式 若解释I使得 xQxPxxxQxxP 则或 1 xxQxxPI1 xxPI1 xxQI 若 则存在使得 1 xxPI I Dd 1 dPI1 dQdP II 若 则存在使得 1 xxQI I Dd 1 dQI1 dQdP II 因此 1 xQxPxI 2 是非永真的可满足式 给定解释I如下 xQxPxxxQxxP dDI 1 dPI1 dQI 则 1 xQxPxxxQxxPI 给定解释如下 I baDI 1 aPI0 bPI0 aQI1 bQI 则 0 xQxPxxxQxxPI 3 是非永真的可满足式 给定解释I如下 xxQxxPxQxPx dDI 1 dPI1 dQI 则 1 xxQxxPxQxPxI 给定解释如下 I baDI 1 aPI0 bPI0 aQI1 bQI 则 0 xxQxxPxQxPxI 4 是非永真的可满足式 给定解释I如下 yxyPxxxxP dDI 1 ddPI 则 1 yxyPxxxxPI 给定解释如下 I baDI 1 bbPaaP II 0 abPbaP II 则 0 yxyPxxxxPI 5 是非永真的可满足式 给定解释I如下 xQxPxxxQxxP dDI 1 dPI1 dQI 则 1 xQxPxxxQxxPI 给定解释如下 I baDI 1 aPI0 bPI0 aQI1 bQI 则 0 xQxPxxxQxxPI 6 是永真式 若解释I使得 xQxPxxxQxxP 则存在使得 因此且0 xQxPxI I Dd 0 dQdP II 1 dPI 且 0 dQI1 xxPI0 xxQI0 xxQxxPI 7 是永真式 若解释I使得 xxQxxPxQxPx 则且 存在使得0 xxQxxPI1 xxPI0 xxQI I Dd 又因为 所以 因此 1 dPI0 xxQI0 dQI0 dQdP II 0 xQxPxI 12 设A B是任意公式 证明以下公式是永真式 1 其中项t对于A中的x是可代入的 xAAx t 2 AxxA 3 AxxA 4 xBxABAx 5 BAxxBxA 6 其中x不是A的自由变元 xBABAx 解解 1 任取解释I和I中赋值v 若 则1 vAI x t 所以 这表明是永真式 1 vtIxvAIvAI x t 1 vxAIxAAx t 2 任取解释I和I中赋值v 1 vxAI 当且仅当 0 vxAI 当且仅当 存在使得 I Dd 0 dxvAI 当且仅当 存在使得 I Dd 1 dxvAI 当且仅当 1 vAxI 这表明是永真式 AxxA 3 任取解释I和I中赋值v 0 vxAI 当且仅当 1 vxAI 当且仅当 存在使得 I Dd 1 dxvAI 当且仅当 存在使得 I Dd 0 dxvAI 当且仅当 0 vAxI 这表明是永真式 AxxA 4 任取解释I和I中赋值v 若 则存在使得1 vBAxI I Dd 且1 dxvBAI1 dxvBIdxvAI1 vxAI 这表明是永真式 1 vxBI1 vxBxAIxBxABAx 5 任取解释I和I中赋值v 若 则存在使得0 vBAxI I Dd 0 dxvBAI0 dxvBIdxvAI0 vxBxAI 这表明是永真式 BAxxBxA 6 任取解释I和I中赋值v 若 则对于每个 1 vAIvBAxI I Dd 因为x不是A的自由变元 所以 1 dxvBAI1 vAIdxvAI 因此 这表明是永真式 1 dxvBI1 vxBI xBABAx 13 设是公式A的闭包 是 其中 证明 1 A 2 AAxx n 1 Var 1n xxA 1 A是永真式当且仅当是永真式 1 A 2 A是可满足式当且仅当是可满足式 2 A 证明证明 1 首先证明 若A是永真式 则是永真式 设A是永真式 任取解 xA 释I和I中赋值v 任取 因为也是I中赋值 所以 I Dd dxv1 dxvAI 是永真式 若A是永真式 则是永真式 1 vxAIxA Axn 是永真式 Axx n 1 因为是永真式 所以若是永真式 则A是永真式 AAxx n 1 Axx n 1 2 因为是永真式 所以若解释I和I中赋值v满足A 则I和 AxxA n 1 v满足 Axx n 1 若解释I和I中赋值v满足 则有使得 Axx n 1In Ddd 1 I和I中赋值满足A 1 11 nn dxdxvAI 11nn dxdxv 14 判断以下等值式是否成立 并说明理由 1 xxQxxPxQxPx 2 xxQxxPxQxPx 3 xPxxP 4 xxPxxPx 5 yyQxxPyyQxPx 6 yyQxxPyyQxPx 解解 1 不成立 取解释I如下 baDI 0 aPI1 bPI1 aQI0 bQI 则且 0 xQxPxI1 xxQxxPI 2 不成立 取解释I如下 baDI 0 aPI1 bPI1 aQI0 bQI 则且 0 xQxPxI1 xxQxxPI 3 不成立 取解释I和I中赋值v下 baDI 0 aPI1 bPIbxv 则且 0 vxxPI1 vxPI 4 成立 任取解释I和I中赋值v 因为x不是中的自由变元 所以对于每个 xxP I Dd vxxPIdxvxxPI 1 vxxPxI 当且仅当对于每个 I Dd 1 dxvxxPI 当且仅当1 vxxPI 5 不成立 取解释I如下 baDI 0 aPI1 bPI1 aQI0 bQI 则且 0 yyQxPxI1 yyQxxPI 6 不成立 取解释I如下 baDI 1 aPI0 bPI1 bQaQ II 则且 0 yyQxPxI1 yyQxxPI 15 设A B是任意公式 证明以下等值式 1 其中y在A中不出现 x y AyAx 2 BxAxBAx 3 其中x不是B的自由变元 y不是A的自由变元 ByAxBAyx 4 其中x不是B的自由变元 y不是A的自由变元 ByAxBAyx 5 其中x不是B的自由变元 y不是A的自由变元 ByAxBAyx 6 AxyAyx 证明证明 1 x y x y AyAyAxAx 2 BxAxBxAxBxAxBAxBAx 3 ByAxByAxBAyx 4 ByAxyBAxBAyx 5 ByAxyBAxBAyx 6 任取解释I和I中赋值v 0 vyAxI 当且仅当有使得 I Dd 0 dxvyAI 当且仅当有使得 I Dcd 0 cydxvAI 当且仅当有使得 I Dcd 0 dxcyvAI 当且仅当有使得 I Dc 0 cyvxAI 当且仅当0 vxAyI 16 判断以下逻辑推论关系是否成立 并说明理由 1 xxQxxPxQxPx 2 xQxPxxxQxxP 3 xQxPxxxQxPx 4 xQxPxxxQxPx 5 xxQxxPxQxPx 6 xxxPyxyPx 解解 1 不成立 取解释I如下 baDI 0 aPI1 bPI1 aQI0 bQI 则且 这表明1 xQxPxI0 xxQxxPI xxQxxPxQxPx 2 不成立 取解释I如下 baDI 0 aPI1 bPI1 aQI0 bQI 则且 这表明1 xxQxxPI0 xQxPxI xQxPxxxQxxP 3 不成立 取解释I如下 baDI 0 bPaP II 1 aQI0 bQI 则且 这表明1 xxQxPxI0 xQxPxI xQxPxxxQxPx 4 若解释I使得 则有使得 0 xQxPxI I Dd 0 dQdP II 且 这表明1 dPI0 dQI0 xxQI0 xxQxPxI xQxPxxxQxPx 5 不成立 取解释I如下 baDI 1 aPI0 bPI0 bQaQ II 则且 这表明1 xxPIxQxPxI0 xxQI xxQxxPxQxPx 6 不成立 取解释I如下 baDI 1 baPI0 bbPabPaaP III 则 但 所以 1 yxyPxI0 xxxPI xxxPyxyPx 17 设A B是任意公式 证明以下结论 1 xBxABAx 2 xBxABAx 3 其中x对于A中的y是可代入的 AyxAx y x 4 BAxBxAx 证明证明 1 若解释I和I中赋值v使得 则有使得1 vBAxI I Dd 且1 dxvBAI1 dxvBIdxvAI1 vxAI 这表明 1 vxBI1 vxBxAIxBxABAx 2 若解释I和I中赋值v使得 则对于每个 1 vxAIvBAxI I Dd 这表明1 dxvA