离散数学朱保平

第一章 命题演算基础 第一章 命题演算基础 1.1 判断下列语句是否为命题，若是请翻译为符号公式；若不是说明由。 （1）请给我一支笔！ （2）火星上有生物。 （3） （4）只有努力工作，方能把事情做好。 （5）如果嫦娥是虚构的，而圣诞老人也是虚构的，那么许多孩子受骗了。 解 （1）不为命题，因为它不是陈述句。 （2）是命题，用命题变元 表示该命题。 （3）不为命题，虽为陈述句，但不能判断其真假性。 （4）是命题。设 表示努力工作， 表示把事情做好，则原句翻译为命题公式 。 （5）是命题。设 表示嫦娥是虚构的， 表示圣诞老人也是虚构的， 表示许多孩子受骗了，则原句翻译为 。 1.2 试判定下列公式的永真性和可满足性。 （1） 解 （1）当 时， 原式= = = = 当 = 时，上式= ；当 时，上式= ，因此公式存在成真解释 ，存在成假解释 ，故公式可满足，但非永真。 （2） 解 当 时 原式= = = 当 = 时 上式= = = 当 = 时 上式= = = = 当 时，上式= ，因此公式存在成真解释 ，存在成假解释 ，故公式可满足，但非永真。 （3） 解 当 时 原式= = = 当 时 上式= = 当 时，上式= ，当 时，上式= ，因此，公式存在成真解释 ，存在成假解释 ，故公式可满足，但非永真。 （4） 解 当 时 原式= = = = 当 时 上式= = = 当 时，上式= ，当 时，上式= ，因此，公式存在成真解释 ，存在成假解释 ，故公式可满足，但非永真。 1.3 试求下列公式的成真解释和成假解释 （1） 解 （1）当 时 原式= = = 当 时，上式= ，当 时，上式= 。 当 时 原式= = 当 时 上式= = = 当 时 上式= = = 当 时，上式= ，当 时，上式= ， 因此，公式的成真解释为 ；成假解释为 。 （2） 解 当 时 原式= = = = 当 时，上式= ；当 时，上式= 。 当 时 原式= = = = 因此，公式的成真解释为 ；成假解释为 。 （3） 解 当 时 原式= = = 当 时 上式= = = 当 时，上式= ；当 时，上式= 。 当 时 上式= = 当 时 原式= = = = 因此，公式的成真解释为 ；成假解释为 。 （4） 解 当 时 原式= = = 当 时 上式= = = 当 时 上式= = = 当 时，上式= ；当 时，上式= 。 当 时 原式= = = = 当 时，上式= ；当 时，上式= 。 因此，公式的成真解释为 ；成假解释为 。 1.4 试写出下列公式的对偶式和内否式 （1） （2） （3） （4） 解 （1） 内否式为 消去“ ”得式子 对偶式= （2）内否式为 消去“ ”得式子 对偶式为 （3）内否式为 消去“ ”得式子 对偶式为 （4）内否式为 消去“ ”得式子 对偶式为 1.5 试证明联结词集合{ }是完备的。 证明 因为， 所以，联结词集合 可以表示集合 。 又因为，联结词集合 是完备的，即 可以表示任何一个命题演算公式，所以 可以表示任何一个命题演算公式，故联结词集合 是完备的。 1.6 试证明联结词集合 不是完备的。 证明 设集合 是完备的，则由联结词集合的完备性定义知 。当 全取为真时，上式左边= ，右边= ，矛盾。 因此 不是完备的。 设集合 是完备的，则由联结词集合的完备性定义知 ，其中 表示“ ”。当 全取为真时，上式左边= ，右边= ，矛盾。 因此 不是完备的。 1.7 试求下列公式的析取范式和合取范式 （1） 解 原式= = = （析取范式） = = = （合取范式） （2） 解 原式= = = = （合取范式和析取范式） （3） 解 原式= = （合取范式） = = = （析取范式） （4） 解 原式= = = （析取范式） = = = = = = = （合取范式） 1.8 试求下列公式的主析取范式和主合取范式 （1） 解 原式= = = = = = = = = （2） 解 原式= = = = = = = = = （3） 解 原式= = = = （4） 解 原式= = = = = = = 1.9 用把公式化为主范式的方法判断下列各题中两式是否等价 （1） 解 （1） = = = = = = = = 由此可见两公式的主析取范式不相等，因此，两公式不等价。 （2） 解 = = = = = = = = = = = = 由此可见两公式的主合取范式相等，因此，两公式等价。 第二章 命题演算的推理理论 2.1 用永真公理系统证明下列公式 （1） 证明 （1） 公理1 （2） 公理13 （3） 用 代入 （4） 分（3）（1） （5） 分（4）（1） （6） 公理11 （7） 用 代入 （8） 公理7 （9） 用 代入 （10） 分（9）（7） （11） 分（10）（5） （2） 证明 （1） 公理14 （2） 用 代入， 用 代入 （3） 公理15 （4） 定理 （5） 用 代入， 用 代入， 用 代入 （6） 分（5）（3） （7） 公理3 （8） 用 代入， 用 代入， 用 代入 （9） 分（8）（2） （10） 分（9）（6） （11） 定理 （12） （4）式中 用 代入， 用 代入， 用 代入 （13） 分（12）（11） （14） （7）式中 用 代入， 用 代入， 用 代入 （15） 分（14）（13） （16） 分（15）（10） （3） 证明 （1） 公理11 （2） 用 代入 （3） 定理 （4） 用 代入 （5） 分（4）（3） （6） 公理12 （7） 用 代入 （8） 公理3 （9） 用 代入， 用 代入， 用 代入 （10） 分（9）（5） （11） 分（10）（7） （12） 定理 （13） 用 代入 （14） 分（13）（11） （4） 证明 （1） 公理1 （2） 用 代入 （3） 定理 （4） 用 代入， 用 代入 （5） 分（4）（2） （6） 公理3 （7） 用 代入， 用 ， 用 代入 （8） 分（7）（5） 2.2 已知公理： 及分离规则和代入规则。 试证明（1） 为定理 （2） 为定理。 证明 （1） 公理 （2） 公理 （3） 用 代入 （4） 公理 （5） 用 代入， 用 代入 （6） 分（5）（1） （7） 分（6）（3） （8） （2）式中 用 代入， 用 代入 （9） 分（8）（7） （10） 公理 （11） 用 代入， 用 代入 （12） 分（11）（9） 2.3 用假设推理系统证明下列公式 （1） 证明 （1） 假设 （2） 假设 （3） 后件的否定 （4） 公理15 （5） 分（4）（3） （6） 分（1）（5） （7） 分（2）（5） （6）（7）矛盾 由反证法推理定理知 ， ├ 由推理定理知 （2） 证明 （1） 假设 （2） 假设 （3） 假设 （4） 分（1）（3） （5） 分（2）（3） （6） 分（4）（5） 由假设推理过程的定义知 ， ， ├ 由推理定理知 （3） 证明 （1） 假设 （2） 假设 （3） 假设 （4） 公理10 （5） 分（4）（2） （6） 分（5）（3） （7） 分（1）（6） 由假设推理过程的定义知 ， ， ├ 由推理定理知 （4） 证明 （1） 假设 （2） 公理8 （3） 公理9 （4） （2）式中 用 代入， 用 代入 （5） （3）式中 用 代入， 用 代入 （6） 分（4）（1） （7） 分（5）（1） （8） 分（2）（6） （9） 分（3）（6） （10） （2）式中 用 ， 用 代入 （11） （3）式中 用 ， 用 代入 （12） 分（10）（7） （13） 分（11）（7） （14） 分（12）（8） （15） 分（13）（9） （16） 公理10 （17） 用 ， 用 代入 （18） 分（17）（14） （19） 分（18）（15） 由假设推理过程的定义知 ├ 由推理定理知 2.4 用归结原理证明下列公式 （1） 证明 化为合取范式： = = 建立子句集 （1） （2） （3） （4） （5） （6） （1）（3）归结 （7） （5）（6）归结 （8） （4）（7）归结 （9） （2）（8）归结 （2） 证明 化为合取范式： = = 建立子句集： （1） （2） （3） （4） （1）（3）归结 （5） （2）（3）归结 （6） （4）（5）归结 （3） 证明 化为合取范式： = 建立子句集： （1） （2） （3） （4） （5） （1）（4）归结 （6） （2）（3）归结 （7） （5）（6）归结 （4） 证明 化为合取范式： = 化为子句集： （1） （2） （3） （1）（2）归结 第三章 谓词演算基础 3.1试把下列语句符号化 （1）如果我知道你不在家，我就不去找你了。 解 设 表示 知道 不在家； 表示 去找 ； 表示我； 表示你； 则原句表示为： 。 （2）他送给我这只大的红气球。 解 设 表示 送给 ； 表示 为大的； 表示 为红的； 表示 为气球； 表示他， 表示我， 表示这只； 则原句译为： 。 （3）苏州位于南京与上海之间。 解 设 表示 位于 与 之间； 表示苏州， 表示南京， 表示上海； 则原句表示为： 。 （4）他既熟悉C++语言，又熟悉PASCAL语言。 解 设 表示 熟悉 ； 表示他， 表示C++语言， 表示PASCAL语言； 则原句译为： 。 3.2 试将下列语句符号化为含有量词的谓词演算公式： （1）没有不犯错误的人。 解 设 表示 为人； 表示 为错误； 表示 犯 。 则原句译为： 。 （2）有不是奇数的质数。 解 设 表示 为奇数； 表示 为质数。 则原句译为： 。 （3）尽管有人能干，但未必一切人能干。 解 设 表示 为人； 表示 能干。 则原句译为： 。 （4）鱼我所欲，熊掌亦我所欲。 解 设 表示 为鱼； 表示 为熊掌； 表示 所欲 。 表示我； 则原句表示为： 。 （5）人不犯我，我不犯人；人若犯我，我必犯人。 解 设 表示 为人； 表示 犯 。 表示我； 则原句译为： 。 （6）有一种液体可熔化任何金属。 解 设 表示 为液体； 表示 为金属； 表示 熔化 。 则原句可译为： 。 （7）并非“人为财死，鸟为食亡”。 解 设 表示 为人； 表示 为财； 表示 为鸟； 表示 为食； 表示 为 死； 表示 为 亡。 则原句译为： （8）若要人不知，除非己莫为。 解 设 表示 为人； 表示 为某一事情； 表示 做了 ； 表示 知道 做了 。 则原句译为： （9）任何一数均有一数比它大。 解 设 表示 为数； 表示 比 大； 则原句译为： （10）每个作家均写过作品。 解 设 表示 为作家； 表示 为作品； 表示 写了 。 则原句译为： （11）有些作家没写过小说。 解 设 表示 为作家； 表示 为小说； 表示 写了 。 则原句译为： （12）天下乌鸦一般黑。 解 设 表示 为乌鸦； 表示 与 一样黑。 则原句译为： 3.3 令 表示“ 为质数”； 表示“ 为偶数”； 表示“ 为奇数”； 表示“ 除尽 ”。 试把下列语句翻译为日常语句： （1） 解 2为偶数且2为质数。 （2） 解 任何能被2除尽的数均为偶数。 （3） 解 任何不是偶数的数均不能被2除尽。 （4） 解 任何一个数，若能被任何偶数除尽，则该数一定是偶数。 （5） 解 有是偶数的质数。 3.4 指出下列公式的约束关系、自由变元和约束变元： （1） 解 中的 和 中的 受 约束； 中的 受 约束； 中的 为约束变元， 中的 和 为约束变元； 中的 和 中的 为自由变元。 （2） 解 中的 受 约束， 中的 受 约束； 中的 和 中的 为约束变元； 中的 和 中的 为自由变元。 3.5 已知公式 （1）试对公式中的自由变元 代以 。 解 先对公式改名，以防止代入后改变变元的约束关系 原式= 公式中的自由变元 代以 后得： （2）试对公式中的谓词变元 代以式子 。 解 先对公式和代入进行改名，以防止代入后改变变元的约束关系 原式改名为： 代入式改名为： 代入后的式子为： 3.6 试讨论公式 在个体域 上的成真解释和成假解释。 解 个体域 上的二元谓词共有16类谓词，见下表： 所以，公式的成假解释为 其中 ；成真解释为 。 3.7 利用量词的等价公式判断下列两组公式是否等价，其中 中不含自由的 。 （1） 和 解 因为 = = = 所以，两公式等价。 （2） 解 因为 所以，两公式不等价。 3.8 试讨论公式 的永真性和可满足性。 解 （1）讨论公式在1域 上的情况 原式= 公式在1域上永真。 （2）讨论公式在2域 上的情况 2域上的一元谓词共有四类，见下表： 因为公式在解释 下 原式= = = = 所以，公式在2域上存在成假解释。 又因为公式在1域上永真，所以由定理知，公式在2域上可满足。 综上，公式在2域上可满足，但非永真。 （3）讨论公式在 域上的情况 因为公式在2域上可满足，所以由定理知，公式在 域上可满足。 假设公式在 域上永真，由定理大永真可推出小永真知，公式在2域上永真，矛盾，因此公式在 域上非永真。 3.9 试讨论公式 的永真性和可满足性。 解 公式在 域 上永真。 因为 所以，公式在 域 上永真。 3.10 试求出下列公式的前束范式和SKOLEM 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 形。 （1） 解 原式= = = （前束范式） （SKOLEM标准形） （2） 解 原式= = = （前束范式） （SKOLEM标准形） 3.11 试用唯一性量词或摹状词符号化下列语句： （1）只有一个人去过南极。 解 令 表示 为人； 表示 去过 ； 表示南极； 则原句译为： （2）最后一个离开办公室的人关门窗关电源。 解 令 表示 为人； 表示 比 晚离开办公室； 表示 关 ； 表示门窗； 表示电源； 又令 则原句译为： 。 （3）并非年龄最大的人最有知识。 解 令 表示 为人； 表示 比 年龄大； 表示 比 有知识； 又令 则原句译为： 。 （4）每个数均有唯一的一个数是它的后继。 解 令 表示 为数； 表示 是 的后继； 则原句译为： 。 第四章 谓演算的推理理论 4.1 用永真的公理系统证明下列定理 （1） 证明 先证 （1） 公理20 （2） 全2规则（1） 再证 （3） 公理20 （4） 定理 （5） 分（4）（3） （6） 全规则（5） （7） 公理7 （8） 分（7）（2） （9） 分（8）（6） （2） 证明 先证 （1） 公理20 （2） 存1规则（1） 再证 （3） 公理21 （4） 公理3 （5） 分（4）（3） （6） 全（5） （7） 公理7 （8） 分（7）（（2） （9） 分（8）（6） 4.2 已知公理 及分离规则和全称规则，全称规则为： ├ 试证明：全0规则 ├ 。 证明 （1） （2） 公理 （3） 分（2）（1） （4） 公理 （5） 分（4）（3） （6） 全（5） （7） 公理 （8） 分（6）（7） （9） 分（8）（7） 4.3 指出下列推理过程的错误所在 （1）① 假设 ② 全称量词消去 ③ 额外假设引入 ④ 全0规则 ⑤ 全称量词消去 ⑥ 全0规则 解 第④步有错，因为额外假设中的自由变元不能实施全0称规则。 （2） 的证明过程如下： ① 假设 ② 额外假设 ③ 全0规则 解 第③步有错，因为额外假设中的自由变元不能实施全0称规则。 （3）① 假设 ② 假设 ③ 全称量词消去 ④ 额外假设引入 ⑤ 分③④ ⑥ 存在量词引入 解 第④步 中的 为使用过的变元，额外假设要求引入的变元为未使用过的变元。 4.4 用假设推理证明下列公式 （1） 证明 （1） 假设 （2） 假设 （3） 假设 （4） 全称量词消去规则（1） （5） 全称量词消去规则（3） （6） 分（4）（5） （7） 全0规则（6） （8） 分（2）（7） 由假设推理的定义过程知 ， ， ├ 由推理定理知 （2） ， ├ 证明 （1） 假设 （2） 假设 （3） 分（1）（2） （4） 额外假设 （5） 公理11 （6） 分（5）（4） （7） 全称量词消去（3） （8） 分（7）（6） （9） 额外假设 （10） 公理11 （11） 分（10）（9） （12） 全称量词消去（3） （13） 分（12）（11） （14） 合取规则（8）（13） （15） 公理21 （16） 分（15）（14） （17） 公理21 （18） 分（17）（16） 由假设推理过程的定义知 ， ├ 4.5 已知知识如下： （1）桌子上的每本 书 关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf 均是杰作； （2）写出杰作的人是天才； （3）某个不出名的人写了桌上某本书； 结论：某个不出名的人是天才。 （1）试用归结原理证明之； （2）试用假设推理证明之。 证明 先对知识符号化 令 表示 为人； 表示 为桌子的书； 表示 为杰作； 表示 写了 ； 表示 出名； 表示 为天才。 则已知知识翻译为： （1） （2） （3） 结论翻译为： 归结原理证明 （1） （2） （3） （4） （5） （6） （7） （8） （7）（3）归结 （9） （4）（8）归结 （10） （9）（2）归结 （11） （3）（10）归结 （12） （11）（6）归结 （13） （12）（1）归结 （14）□ （13）（5）归结 假设推理证明 （1） 假设 （2） 假设 （3） 假设 （4） 额外假设 （5） 公理 （6） 公理 （7） 公理 （8） 公理 （9） 分（5）（4） （10） 分（6）（4） （11） 分（7）（4） （12） 分（8）（4） （13） 全称量词消去（1） （14） 分（13）（11） （15） 全称量词消去（2） （16） 合取（9）（14）（12） （17） 分（15）（16） （18） 合取（9）（10）（17） （19） 公理21 （20） 分（19）（18） 4.6 用归结方法证明下列公式 （1） ， ， ├ 证明 （1） （2） （3） （4） （5） （4）（1）归结 （6） （2）（5）归结 （7）□ （6）（3）归结 （2） 证明 目标公式的否定 = = 化为子句集： （1） （2） （3） （4） （1）（3）归结 （5） （4）（2）归结 （6）□ （5）（1）归结 4.7 已知知识如下： （1）每个程序员均写过程序； （2）病毒是一种程序； （3）有些程序员没写过病毒。 结论：有些程序不是病毒。 试用霍恩子句逻辑程序证明之。 证明 先对知识符号化 令 表示 为程序员； 表示 为程序； 表示 为病毒； 表示 写了 则已知知识翻译为： （1） （2） （3） 结论翻译为： （1） （2） （3） （4） （5） （6） （7） （5）（6）归结 （8） （7）（1）归结 （9） （8）（4）归结 （10） （9）（2）归结 （11）□ （4）（10）归结 4.8 已知有关公司信息的知识： （1）John是PD公司经理； （2）Smith在PD公司任职； （3）Jones在PD公司任职； （4）Peter在PD公司任职； （5）Hall是SD公司经理； （6）Mary在SD公司任职； （7）Bell在SD公司任职； （8）Jones和Mary已结婚； （9）在某家公司当经理者必在该公司任职； （10）在某家公司当经理者必是在该公司任职的人的老板； （11） 和 结婚，则 和 结婚； （12）一对夫妇不在同一公司任职； （13）所有在SD公司任职的已婚者可享有EC保险的人寿保险。 现在查询： Mary是否在SD公司任职？她结婚了吗？丈夫是谁？她是否享有保险？ 试用霍恩子句逻辑程序证明之。 证明 令 表示 为 公司的经理； 表示 为 公司的任职； 表示 和 夫妇； 表示 为 的老板； 表示 享有 的人寿保险； 表示 已婚； 表示 为人； 表示 为公司； 表示 已婚； 化为霍恩子句： （1） （2） （3） （4） （5） （6） （7） （8） （9） （10） （11） （12） （13） （14） （15） （16） （17） （18） （19） （20） 问Mary是否在SD公司任职？翻译为子句： （21） （22）□ （21）（6）归结 所以Mary在SD公司任职。 问她结婚了吗？翻译为子句： （23） （24）□ （23）（9）归结 所以MARY已婚。 问丈夫是谁？翻译为子句： （25） （26）□ （25）（8）归结 所以Mary的丈夫是Jones。 她是否享有保险？翻译为子句： （27） （28） （27）（20）归结 （29） （28）（（6）归结 （30）□ （29）（9）归结 所以她享有保险。 第五章 递归函数论 5.1 写出下列语句的特征函数 （1） 大于等于 。 解 （2） 为 的公倍数。 解 （3） 为质数。 解 （4） 为 的倍数且 为平方数。 解 为 的倍数的特征函数为： 为平方数的特征函数为： 故原句的特征函数为： （5） 为非负数或 为平方数。 解 为非负数的特征函数为： 为平方数的特征函数为： 故原句的特征函数为： （6）在 ， 间的一切 均使得 成立。 解 （7）在 ， 间有一个 使得 成立。 解 5.2 试把下列公式化为标准迭置 （1） 解 其中 （2） 解 其中 5.3 用凑合定义法定义函数 ，并把它化为迭置。 解 5.4 试证明下列函数为原始递归函数 （1） 证明 因为 其中 为 ，也就是说 可用原始递归式表示。 所以 为原始递归函数。 （2） 证明 因为 其中 为 ，也就是说 可用原始递归式表示。 所以 为原始递归函数。 （3） 证明 因为 为本原函数，而本原函数为原始递归函数。 所以 为原始递归函数。 （4） 证明 因为 ，且 和 为原始递归函数，所以 是由原始递归函数 和 利用迭置而得。根据原始递归函数的定义知， 为原始递归函数。 （5） 证明 因为 ，且 和 为原始递归函数，所以 是由原始递归函数 和 利用迭置而得。根据原始递归函数的定义知， 为原始递归函数。 （6） 证明 因为 其中 为 ，也不是说 可用原始递归式表示。 所以 为原始递归函数。