离散数学 命题逻辑

《离散数学 命题逻辑》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学陆玫mlu@math.tsinghua.edu.cn绪论离散数学的性质、内容学习此课的目的学习此课的方法内容：1.数理逻辑2.集合论3.代数系统4.图论教材《离散数学》作者：左孝凌、李为鑑、刘永才上海科学技术出版社出版参考书《离散数学》耿素云等编著《数理逻辑与集合论》石纯一等编著《图论与代数结构》戴一奇等编著作业要求与答疑安排请使用作业纸，写清名字与学号。每周一下午交作业，各班课代表收作业,，作业箱号码为48#。答疑时间：每周三下午4：00---5：00地点：理科楼A402。欢迎通过邮箱(mlu@math.tsinghua.edu.

2、cn)答疑总成绩=平时成绩（10%）+期末考试成绩（90%）第一篇数理逻辑逻辑--是研究人的思维的科学。1.辩证逻辑：是研究人的思维中的辩证法。2.形式逻辑：是研究人的思维的形式和一般规律。人的思维过程：概念判断推理形式逻辑主要是研究推理的。推理:是由若干个已知的判断(前提)，推出新的判断(结论)的思维过程。推理方法类比推理：由个别事实推出个别结论。归纳推理：由若干个别事实推出一般结论。演绎推理：由一般规律、个别事实推出个别结论。形式逻辑主要是研究演绎推理的。例1：如果天下雨，则路上有水。(一般规律)天下雨了。(个别事实)推出结论：路上

3、有水。(个别结论)例2：(大前提)：所有金属都导电。(一般规律)(小前提)：铜是金属。(个别事实)推出结论：铜能导电。(个别结论)逻辑的历史莱布尼茨　（GottfriedWilhelmvonLeibniz，1646-1716）：把数学引入形式逻辑布尔　（GeorgeBoole1815-1864）：实现了命题逻辑，布尔代数弗雷格　（GottlobFrege，1848-1925）：建立了第一个谓词演算系统哥德尔　（KurtGodel,1906-1978）：不完全性定理，递归函数的可计算性数理逻辑与计算机什么是程序？程序＝算法＋数据算法＝逻辑＋控

4、制钱学森谈“计算机与数理逻辑”电子计算机与数理逻辑具有非常密切的关系。正是在数理逻辑中，把人类的推理过程分解成一些非常简单原始的、非常机械的动作，才使得用机器代替人类的推理的设想有了实现的可能。有了电子计算机，使用它时，必须先进行程序设计，把整个推理、计算过程，丝毫不漏地考虑到，统统编入程序，而机器则依次而运行；如稍有错误，将立即得到毫无意义的结果。可见必须有足够的数理逻辑的训练，熟悉推理过程的全部细节,才能从事程序设计。此外，程序设计是一个很细致又很麻烦的工作，如何从事程序设计，如何防止在计算过程中出错，如何很快地发现这种错误而及时加以改

5、正，都是程序设计理论(软件理)中非常根本又非常重要的内容，大家都认为，这些内容都与数理逻辑息息相关。正如著名的计算机软件大师戴克斯特拉(E.W.Dijkstra)曾经说过：我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想，假如我早在数理逻辑上好好下点功夫的话，我就不会犯这么多错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻20岁的话，我就会回去学逻辑。第一章命题逻辑这章是以“命题”为中心主要讨论：命题的表示、命题的演算命题演算中的公式，及其应用命题逻辑推理一.命题的概念命题是一个非真即假（不可兼）的陈述句。二

6、.命题的真值真值为真:所作的判断与客观一致,记作T(True)。真值为假:所作的判断与客观不一致,记作F(False)。判定下面这些句子哪些是命题。（1）2是个素数。（2）雪是黑色的。（3）2015年人类将到达火星。（4）如果a>b且b>c，则a>c。（5）x+y<5（6）请打开书！（7）您去吗？（8）明天上午十点左右下雨。（9）我正在说谎。命题标识符（命题变元）：表示命题的符号。约定：用英文大写字母表示命题。P：雪是白的。命题与命题变元的区别：命题指具体的陈述句，有确定的真值，而命题变元的真值不定。三.原子命题与复合命题简单命题(原子命题

7、)：由最简单的陈述句构成的命题.复合命题(分子命题)：由若干个原子命题构成的命题。例：如果f(x)在[a，b]上连续，而且f(a)f(b)<0，则存在a

8、被否定命题的全部，而不是一部分。PPTFFT二.合取“∧”（二元联结词）表示：“并且”、“不但…而且...”、“既…又...”“尽管…还…”例2P：小王能唱歌。Q：小王能跳舞。