离散数学复习指导1.doc

离散数学复习指导Ⅰ 命题逻辑部分 一 学习要求 1．理解命题、联结词的含义，掌握命题的符号化； 2．理解命题公式的赋值，能求出公式的真值表，判断公式的类型； 3. 理解公式等值的定义,记住一些基本等值式,能进行等值演算; 4. 体会公式的主范式与公式赋值之间的关系,能利用等值演算求出范式; 5. 理解公式的蕴涵及推理的含义及联系,记住一些基本的推理规则,能用演绎 推理方法进给出推理证明; 二 范例 例1 将下列命题符号化 ⑴小王聪明但不用功； ⑵ 说数理逻辑枯燥无味或毫无价值，那是不对的； ⑶ 你不及格就要补考。 ⑷ 不经一事，不长一智； 解：⑴ 设p：小王聪明，q：小王用功，则该命题可符号化为：。 ⑵ p：数理逻辑枯燥无味，q：数理逻辑毫无价值，则：。 ⑶ p：你及格了；q：你要参加补考，则：。 ⑷ p：经一事；Q：长一智，则：。 ⑸ 这是简单命题，则p：李卫与李星是兄弟。 例2 求命题公式的主析取范式和主合取范式，指出公式的成真赋值和成假赋值，并判断公式的类型。 解： （主合取范式） (主析取范式) 公式的成真赋值为：000，001，011，101，110，111 成假赋值为：010，100 公式为非重言式的可满足式 。 例3 构造下面推理的证明： 前提： 结论： 证：(1) P; (2) T(1)化简规则; (3) T(1)化简规则 (4) P; (5) r T(3)(4)假言推理; (6) P; (7) s T(3)(6)析取三段论; (8) T(5)(7)合取式. 例4. 先将下列相关命题符号化,给出推理证明 如果4是偶数,则2不能整除5. 或者7不是素数或者2整除5. 7是素数.因此4不是偶数. 解: 设p: 4是偶数; q: 2能整除5; r: 7是素数; s: 2整除5,则 前提： 结论： 证明: (1) 结论之否定; (2) T(1)等值式; (3) P; (4) T(2)(3)假言推理; (5) P; (6) T(4)(5)析取三段论; (7) P; (8) T(6)(7)合取式. 三 练习题 1． 将下列命题符号化 ⑴小王不但聪明而且美丽。 ⑵不经历风雨，就不能见彩虹。 ⑶只有天气又冷又下雨,他才乘车上班。 ⑷ 天黑了，我就回家。 ⑸ 说学生考试不及格是因为学生不聪明或基础太差是不对的。 ⑹ 进入机房者，必须换拖鞋，穿工作服，否则罚款五元。 2．求下列公式的主析取范式和主合取范式，指出公式的成真赋值和成假赋值，并判断命公式的类型 ⑴ ⑵ ⑶ ⑷ 3．构造下述推理的证明 ⑴前提：，结论： ⑵前提： 结论： ⑶前提： 结论： 4. 先将下列相关命题符号化,给出推理证明 ⑴如是我好好学习,那么我就不要补考.如果我不玩电脑游戏,我就会好好学习.我要补考.所以我玩电脑游戏了. (2) 如果一班不参加篮球赛,那么二班也不参加,如果一班参加篮球赛,那么二班和三班就参加,因此如果二班参加了篮球赛,那么三班也参加了. 谓词逻辑部分 一 学习要求 1．理解谓词逻辑的三要素，掌握命题的符号化； 2．理解谓词公式中量词的辖域、约束关系,及公式的解释，能求出在一个解释下公式的真值，能判断公式的类型； 3. 理解公式等值的定义,记住谓词公式的特殊的基本等值式,能进行等值演算; 4. 理解前束范式的定义,能利用等值演算求出公式的前束范式; 5. 理解公式的蕴涵及推理的含义及联系,特别记住谓词中的一些推理规则,能用演绎 推理方法进给出推理证明; 二 范例 例1 将下列命题符号化 ⑴ 不是所以的人都要补考,但就有人要补考. ⑵ 天下乌鸦一般黑。 ⑶ 不是所有火车都比汽车快，但有的火车比所有汽车快。 解：⑴：是人； ：要补考，则： （注意特性谓词的用法） ⑵ 设D={乌鸦}，：是黑的，则： （本题使用了论域） ⑶：是火车；：是汽车；：比快，则： 或：。 设解释I如下: D={2,3},