离散数学命题与联接词.pptVIP

离散数学(1) 陈斌 gischen@pku.edu.cn 2009.09.15 目录 数理逻辑 集合论 图论 抽象代数 形式语言与自动机 数理逻辑 命题演算 命题与联结词 重言式 范式 命题演算形式系统 谓词演算 个体、谓词和量词 谓词演算永真式 谓词公式的前束范式 一阶谓词演算形式系统 数理逻辑 逻辑学是探索、阐述和确立有效推理原则的学科，最早由古希腊学者亚里士多德创建的。 亚里士多德在逻辑学上最重要的工作是提出三段论学说。 一个三段论就是一个包括有大前提、小前提和结论三个部分的论证。 三段论有许多不同的种类，其中最著名的例子： 凡是人都会死（大前提） 苏格拉底是人（小前提） 所以：苏格拉底会死（结论） 数理逻辑 用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑。 数理逻辑的萌芽 利用计算的方法来代替人们思维中的逻辑推理过程，这种想法早在十七世纪就有人提出过。 莱布尼茨（Leibniz）就曾经设想能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。由于当时的社会条件，他的想法并没有实现。但是他的思想却是现代数理逻辑部分内容的萌芽，从这个意义上讲，莱布尼茨的思想可以说是数理逻辑的先驱。 数理逻辑 数理逻辑的开创 1847年，英国数学家布尔G.Boole发表了《逻辑的数学分析》，建立了“布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的各种概念。布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。 数理逻辑的大发展 1884年，德国数学家弗雷格Frege出版了《数论的基础》一书，在书中引入量词的符号，使得数理逻辑的符号系统更加完备。 美国人皮尔斯Peirce，他也在著作中引入了逻辑符号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门独立的学科。 数理逻辑 数学危机和解决 在集合论的研究过程中，出现了一次称作数学史上的第三次大危机。 这次危机是由于发现了集合论的悖论引起。集合论本来是论证很严格的一个分支，被公认为是数学的基础。 1903年，英国哲学家、逻辑学家、数学家罗素Russell对集合论提出了以他名字命名的“罗素悖论”，这个悖论的提出几乎动摇了整个数学基础。 罗素提出类型论，策梅罗Zermelo提出公理化集合论来对康托尔Contour的朴素集合论进行限制，解决悖论问题。 数理逻辑 对数学进行形式化的努力 第三次数学危机解决以后，整个数学界非常乐观 希尔伯特Hilbert的形式化思想占统治地位 数学建立在集合论和数理逻辑两块基石之上 康托尔的朴素集合论已经被公理化集合论代替，消除了悖论 整个数学的基本理论是自然数的算术和实数理论，它们都已经公理化 如果能够证明这些形式系统的一致性和完全性，整个数学基础就比较牢靠了 1928年，希尔伯特提出四个问题，希望能够把整个数学理论系统形式化，并通过有限多步证明它们没有矛盾。 数理逻辑 数理逻辑的转折 1930年，哥德尔Godel宣布了不完全性定理 一个包括初等数论的形式系统，如果是一致的，那就是不完全的。而且如果初等算术系统是一致的，则一致性在算术系统内不可证明。 数理逻辑最重大的成就之一，是数理逻辑发展的一个里程碑和转折点。哥德尔在研究过程中直接考虑悖论及解决悖论的方法，从而把第三次数学危机引导至另一个方向上。 人们认识到对整个数学形式化的努力是注定要失败的。 数学基础的危机不那么突出了，绝大部分数学家仍然把自己的研究建立在朴素集合论或ZF公理集合论的基础上。 数理逻辑 数理逻辑的四大分支 悖论的提出，促使许多数学家去研究集合论的无矛盾性问题，从而产生了数理逻辑的一个重要分支—公理集合论。 为了研究数学系统的无矛盾性问题，需要以数学理论体系的概念、命题、证明等作为研究对象，研究数学系统的逻辑结构和证明的规律，这样又产生了数理逻辑的另一个分支—证明论。 数理逻辑新近还发展了许多新的分支，如递归论、模型论等。 递归论主要研究可计算性的理论，它和计算机的发展和应用有密切的关系。 模型论主要是研究形式系统和数学模型之间的关系。 命题演算：命题与联结词 命题（proposition/statements） 对确定的对象作出判断的陈述句 命题的真值（truth value） 判断正确，称该命题真（true） 否则，称该命题假（false） 基本假设：排中律 非真即假 排中律有问题？ 命题演算：命题与联结词 直觉主义对排中律的否定 直觉主义学派认为，数学的基础和出发点是自然数的理论，而自然数则是由人的原始直觉（按时间顺序出现的感觉）构造出来的。数学理论可靠性的唯一标准就是心智上的可构造性。他们有一句名言：“存在必须等于被构造。” 按照直觉主义的观点，要判定一个命题p为真，就必须给出p的