第3章命题逻辑

《第3章命题逻辑》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、离散数学计算机科学与工程学院2011年•秋第二部分数理逻辑第3章命题逻辑第4章谓词逻辑逻辑学是研究思维形式及思维规律尤其是推理的学科,早在两千多年前就受到人们的重视。逻辑学古希腊（逻辑）战国（名学）古印度（因明）德国数学家、哲学家莱布尼茨(1647~1716)首先提出用数学方法研究逻辑,就是建立一套表意符号体系,在符号之间进行形式推理.莱布尼茨是数理逻辑的创始人。也正因为这样,数理逻辑又称为符号逻辑。数理逻辑概述数理逻辑是一门新兴的边缘性学科，分为五个部分：即逻辑演算、证明论、公理集合论、递归论和模型论。从创始至今约有300年的历史。特别是近百年来,它取得了长足的发展,在现代

2、的数学、计算机科学以及自然科学和社会科学中都有广泛的应用。数理逻辑概述数理逻辑是用数学的方法来研究人类思维活动的一门数学学科，其显著特征是：符号化、形式化即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划,并基于符号串形式的演算来描述推理过程的一般规律。数理逻辑概述回顾计算机科学的发展，我们可以清晰地发现数理逻辑一直是计算机科学的理论基础和发展动力。数理逻辑的起源与计算机科学数理逻辑计算机科学同一个人同一时间设想用机械模拟人的思维活动。“这种算术机器所进行的工作，比动物的行为更接近人类的思维”。让我们来算一下！思维机械化《逻辑的数学分析》《思维规律的研究》关系

3、逻辑德摩根定律数理逻辑的起源与计算机科学《概念演算》一种按算术语言构成的思维符号语言德国G.W.Leibniz(1626-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。英国G.Boole(1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。德国G.Frege(1848-1925)在1879年建立了第一个谓词演算系统。英国B.Russell(1872-1970)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。奥地利K.Godel(1906-1978)在1931年提出Godel不完全性定理。英国AlanM.Turing(1912-1

4、954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机——一种理想的计算机。数理逻辑发展史中的代表人物数理逻辑的学习“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。”——Edsger.W.Dijkstra1972年Turing奖获得者(1930-2002)单源点最短路径算法学习数理逻辑⑴曹雪芹是《红楼梦》的作者。⑵曹雪芹是小说家。⑶小说家是文学家。数理逻辑是以数学的方法研究推理的形式结构和规律的数

5、学学科。所谓数学方法，是指建立一套符号，其作用是为了避免用自然语言讨论问题时所带来的歧义性。如，下面三条语句均用“是”作谓语动词：三个语句中的三个“是”含义各不同。⑴曹雪芹是《红楼梦》的作者。此句中的“是”表示“＝”，其主语和谓语是对等的；⑵曹雪芹是小说家。此句中的“是”表示“∈”，小说家是集合，曹雪芹只是其中的一分子；⑶小说家是文学家。此句中的“是”表示“”，文学家是包含着小说家的一个更大的集合。显然，符号准确地表达了语句的含义。学习数理逻辑玉龙雪山下的审判在玉龙雪山脚下东巴谷的一条小路上立有一块木牌，请过路行人对一个案子进行审判。说的是有三个人，甲、乙、丙在玉龙山上射杀

6、了一只老鹰，这三个人的行为因违反《野生动物保护法》而被警察拘捕，但是这三个人都否认老鹰是自己射杀的。经过盘查和询问，警察得出如下三个结论：⑴如果甲是无罪的，则乙和丙都有罪；⑵乙和丙中必有一人有罪；⑶要么甲无罪，要么乙有罪（但两者不能同时成立）。现在警方请求你协助判断甲、乙、丙三人谁有罪，谁没有罪，并在你认为有罪的人前面的筐里投入一块石头。笔者查看三个筐发现，乙的筐里石头最多，甲和丙的筐里则差不多。你认为游客们的判断是否正确呢？第3章命题逻辑命题公式及真值表3逻辑等值的命题公式4命题的有关概念1逻辑联结词2命题公式的范式5命题逻辑中的推理7本章学习要求重点掌握熟练掌握了解11命

7、题演算基础2命题演算的推理3命题公式的标准化31对偶原理2命题符号化21命题的定义2联结词的含义3真值表的使用4基本等值式和蕴含式5命题公式的定义3.1命题的定义命题命题是能判断出真假的语句.⑴你妈喊你回家吃饭.⑵《建国大业》里面有大腕儿.⑶北京是中国的首都.⑻火星上有生物.⑷x>3。⑸立正！⑹这朵花真漂亮！⑺你喜欢网络游戏吗?⑼我说的都是假话。⑽雨上得泰山真火。3.1命题的定义⑴必须是一个完整的句子，包括用数学式子表达；⑵句子必须具有真假意义（即有对错之分）；⑶句子能判断出是真还是假。特征陈述句真