《离散数学全校公选课第2次作业小结.111023》由会员分享,可在线阅读,更多相关《离散数学全校公选课第2次作业小结.111023(3页珍藏版)》请在金锄头文库上搜索。
1、全校公选课全校公选课离散数学第离散数学第 2 次作业小结次作业小结1 习题五的第习题五的第 24 题:题: 每个喜欢步行的人都不喜欢骑自行车。每个喜欢步行的人都不喜欢骑自行车。 每个人或者喜欢骑自行车或者喜欢乘汽车。每个人或者喜欢骑自行车或者喜欢乘汽车。 有的人不喜欢乘汽车。所以有的人不喜欢有的人不喜欢乘汽车。所以有的人不喜欢 步行。步行。 (个体域为人类集合)(个体域为人类集合) 这是一个较为全面考查数理逻辑的基这是一个较为全面考查数理逻辑的基 本知识和方法掌握情况的习题。要明确处本知识和方法掌握情况的习题。要明确处 理这类问题的基本步骤:理这类问题的基本步骤: 1)利用一阶逻辑知识,构造基
2、本的谓词利用一阶逻辑知识,构造基本的谓词 2)将问题翻译成谓词公式,分别列出前提将问题翻译成谓词公式,分别列出前提 和结论;和结论; 3)在自然推理系统在自然推理系统 F F 中中构造证明。这其中构造证明。这其中 正确的使用量词的消去与引入规则是很正确的使用量词的消去与引入规则是很 重要。一定要记住在有个体常项或存在重要。一定要记住在有个体常项或存在 量词时,使用量词消去规则时,个体常量词时,使用量词消去规则时,个体常 项或存在量词时消去要优先于全称量词项或存在量词时消去要优先于全称量词 的处理。的处理。命题符号化命题符号化:喜欢乘汽车喜欢骑自行车,喜欢步行,设xxHxxGxxF: )(: )
3、(: )(前提前提: ),()(xGxFx),()(xHxGx)(xHx结论结论: )(xFx证明证明: 前提引入前提引入)(xHx EIEI 规则规则)(cH 前提引入前提引入)()(xHxGx UIUI 规则规则)()(cHcG 析取三段论析取三段论)(cG 前提引入前提引入)()(xGxFx UIUI 规则规则)()(cGcF 拒取式拒取式)(cF EGEG 规则规则)(xFx注意注意:第第步中的步中的 c c 表示的是特定的个体常表示的是特定的个体常 项项, ,使得使得为真为真. 有部分同学在第有部分同学在第中中)(cH使用使用 EIEI 规则后得到规则后得到,而此时的而此时的 y 表示表示)(yH的是个体变项的是个体变项,代表个体域中的任何元素代表个体域中的任何元素,这这显然与显然与所表示的意思是不同的所表示的意思是不同的.)(xHx在写出证明公式序列之前,画出“证明树” ,明确前提的使用过程。杨忠鹏杨忠鹏20111023