《离散数学复习指导1》由会员分享,可在线阅读,更多相关《离散数学复习指导1(4页珍藏版)》请在金锄头文库上搜索。
1、离散数学复习指导命题逻辑部分一 学习要求 1理解命题、联结词的含义,掌握命题的符号化; 2理解命题公式的赋值,能求出公式的真值表,判断公式的类型;3. 理解公式等值的定义,记住一些基本等值式,能进行等值演算;4. 体会公式的主范式与公式赋值之间的关系,能利用等值演算求出范式;5. 理解公式的蕴涵及推理的含义及联系,记住一些基本的推理规则,能用演绎推理方法进给出推理证明;二 范例例1 将下列命题符号化 小王聪明但不用功; 说数理逻辑枯燥无味或毫无价值,那是不对的; 你不及格就要补考。 不经一事,不长一智;解: 设p:小王聪明,q:小王用功,则该命题可符号化为:。 p:数理逻辑枯燥无味,q:数理逻
2、辑毫无价值,则:。 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)
3、 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 将下列命题符号化小王不但聪明而且美丽。不经历风雨,就不能见彩虹。只有天气又冷又下雨,他才乘车上班。 天黑了,我就回家。 说学生考试不及格
4、是因为学生不聪明或基础太差是不对的。 进入机房者,必须换拖鞋,穿工作服,否则罚款五元。2求下列公式的主析取范式和主合取范式,指出公式的成真赋值和成假赋值,并判断命公式的类型3构造下述推理的证明前提:,结论:前提: 结论:前提: 结论:4. 先将下列相关命题符号化,给出推理证明如是我好好学习,那么我就不要补考.如果我不玩电脑游戏,我就会好好学习.我要补考.所以我玩电脑游戏了.(2) 如果一班不参加篮球赛,那么二班也不参加,如果一班参加篮球赛,那么二班和三班就参加,因此如果二班参加了篮球赛,那么三班也参加了.谓词逻辑部分一 学习要求 1理解谓词逻辑的三要素,掌握命题的符号化; 2理解谓词公式中量词
5、的辖域、约束关系,及公式的解释,能求出在一个解释下公式的真值,能判断公式的类型;3. 理解公式等值的定义,记住谓词公式的特殊的基本等值式,能进行等值演算;4. 理解前束范式的定义,能利用等值演算求出公式的前束范式;5. 理解公式的蕴涵及推理的含义及联系,特别记住谓词中的一些推理规则,能用演绎推理方法进给出推理证明;二 范例例1 将下列命题符号化 不是所以的人都要补考,但就有人要补考. 天下乌鸦一般黑。 不是所有火车都比汽车快,但有的火车比所有汽车快。解:是人; :要补考,则: (注意特性谓词的用法) 设D=乌鸦,:是黑的,则: (本题使用了论域):是火车;:是汽车;:比快,则:或:。例2 设解
6、释I如下:D=2,3,.试求出下列公式在解释I下的真值. 解: 在解释I下: 例3 求公式的前束范式.解: (前束范式)例4 构造推理证明,前题: ,结论:证明:(1) 附加前题; (2) T(1) EI规则; (3) P; (4) T(3) UI规则; (5) T(2)(4)假言推理规则; (6) P; (7) T(6) UI规则; (8) T(5)(7)析取三段论. (9) T(8) EG规则.三 练习题 1 将下列命题符号化 所有的学生都通过了计算机等级考试或英语等级考试. 是金子都会发光.但发光的不一定是金子. 如果学生都认真学习了,就不会有毕不了业的学生了. 如果没有了罪犯,也就没有了警察. 没有搬不动的山,只有愚死的汉. 所有人的指纹都不一样. 不管白猫黑猫,抓住老鼠就是好猫. 2. 设解释I如下:D=0,1, a =0,b=1,,.试求出下列公式在解释I下的真值. 。 3求下列公式的前束范式 4将下列命题符号化,并证明之 没有不守信用的人是可以信赖的.有些可以信赖的人是受过教育的.因此有些受过教育的人是守信用的. 有些人喜欢所有的花.但人人都不喜欢杂草.所以花不是杂草. 三好生都是成绩好的学生. 学生干部不一定成绩好,所以学生干部不一定是三好生.