离散数学文档资料

离散数学离散数学概述第一部分数理逻辑第二部分集合论第三部分图论第四部分抽象代数离散数学寻找真理的人存在吗？上帝是万能的吗？你能获得会员资格吗？桌子上摆着两个盒子：一个圆盒子，一个方盒子。圆盒子上写着一句话：“申请不在盒中”。方盒子上写着一句话：“这两句话中只有一句是真话”。那么申请表在哪个盒子里呢？第一部分数理逻辑第一部分数理逻辑

一人在寻找真理，别人问他：“你真的不知道真理是什么吗？”

那个人说：“当然！”

别人又问：“你既然不知道真理是什么，当你找到真理的时候，你又如何辨别出来呢？

如果你辨别得出真理与否，那说明你已经知道了真理是什么，又何来寻找呢？”第一部分数理逻辑

上帝真的是万能的吗？

让我们来问提出一个问题：上帝是否能创造出一块连自己都举不起来的石头？

如果上帝创造出了一块连他自己都举不起来的石头，那么上帝就不是万能的，因为有一块石头他举不起来。

如果上帝不能创造出一块连他自己都举不起来的石头，那么上帝也不是万能的，因为有一块石头他创造不出来。

所以无论上帝是否能创造出这么一块石头，他都不是万能的。第一部分数理逻辑

逻辑推理俱乐部门口贴着一张布告：“欢迎你加入推理俱乐部！只要你通过推理取得一张申请表，就可以获得会员资格了！”

只见桌子上摆着两个盒子：一个圆盒子，一个方盒子。

圆盒子上写着一句话：“申请不在盒中”。

方盒子上写着一句话：“这两句话中只有一句是真话”。

那么申请表在哪个盒子里呢？1、设方盒子上写的话是真的，推出圆盒子上的话是假的，推出申请表在圆盒子中。2、设方盒子上的话是假的，推出圆盒子上的话也是假的，推出申请表在圆盒子里。3、或者方盒子上的话是真的，或者方盒子上的话是假的。总之，申请表在圆盒子中。第一部分数理逻辑数理逻辑:

是用数学方法研究逻辑或形式逻辑的学科。推理:

是由一个或几个判断推出一个新判断的思维形式。数学方法:

是指建立一套表意符号体系，对具体事物进行抽象的形式研究的方法。第一章命题逻辑第二章一阶谓词逻辑第一部分数理逻辑1.1命题和命题联结词1.2命题公式及其赋值1.3等值演算与联结词完备集1.4析取范式与合取范式1.5推理的形式结构1.6自然推理系统P第一章命题逻辑1.命题：能判断真假的陈述句。包含两层意思：1）必须是陈述句2）能够确定（分辨）其真值。1.1命题和命题联结词2.命题的真值：判断结果注意：此处不纠缠具体命题的真假问题，只是将其作为数学概念来处理。真值：真用T或1表示，假用F或0表示。3.命题和真值的符号化1.1命题和命题联结词原子命题：不能被分解为更简单的陈述句复合命题：原子命题通过联结词联结而成1.1命题和命题联结词4、命题联结词ppTFFT1.1命题和命题联结词pqpqFFFFTFTFFTTT王化不但成绩好而且品德好。p∧q：1.1命题和命题联结词pqpqFFFFTTTFTTTT1.1命题和命题联结词开关坏了或灯泡坏了。p∨q：例：1.张晓婧爱唱歌或爱听音乐。2.张晓婧是内蒙人或是陕西人。3.张晓婧只能挑选202或203房间。1.1命题和命题联结词注意：当排斥或两边的情况实际根本不可能同时发生的时候，排斥或也可抽象为∨。但为了方便起见一般不这样抽象。pqpqFFTFTTTFFTTT有位父亲对儿子说：“如果我去书店，就一定给你买电脑报“。问：在什么情况下，父亲算失信呢？1.1命题和命题联结词注意：①“只要p，就q‘，’因为p，所以q”，“p仅当q”，‘只有q，才p“，”除非q才p“，”除非q，否则非p“都可抽象为p→q。②p，q可以没有任何内在联系。例：1.如果3＋3＝6，那么雪是白的。2.除非我能工作完成了，我才去看电影。3.只要天下雨，我就回家。4.我回家仅当天下雨。p→q的逻辑关系为q是p的必要条件或p是q的充分条件。1.1命题和命题联结词pqpqFFTFTFTFFTTT1.1命题和命题联结词pq的逻辑关系为p与q互为充要条件例：1.3是有理数当且仅当加拿大位于亚洲。2.两圆的面积相等，则他们的半径相等，反之亦然。pqpqFFFFTTTFTTTF1.1