离散数学及其应用01 数理逻辑

第一篇数理逻辑数理逻辑是应用数学方法引进一套符号系统来研究思维的形式结构和规律的学科，它起源于公元十七世纪。

十九世纪英国的德·摩根和乔治·布尔发展了逻辑代数，二十世纪三十年代数理逻辑进入了成熟时期，基本内容（命题逻辑和谓词逻辑）有了明确的理论基础，成为数学的一个重要分支，同时也是电子元件设计和性质分析的工具。

冯·诺意曼，图灵，克林，…等人研究了逻辑与计算的关系。

基于理论研究和实践，随着1946年第一台通用电子数字计算机的诞生和近代科学的发展，计算技术中提出了大量的逻辑问题，逻辑程序设计语言的研制，更促进了数理逻辑的发展。

除古典二值（真，假）逻辑外，还研究了多值逻辑、模态逻辑、概率逻辑、模糊逻辑、非单调逻辑等。

不仅有演绎逻辑，也还有归纳逻辑。

计算机科学中还专门研究计算逻辑、程序逻辑、时序逻辑等。

现代数理逻辑分为四论：证明论，递归论（它们与形式语言语法有关），模型论，公理化集合论（它们与形式语言的语义有关）。

第1-1章命题逻辑学习要求: 掌握命题，命题公式，重言式，等价式，蕴涵式等基本概念，能利用逻辑联结词或真值表，等价式与蕴涵式进行命题演算和推理；学习范式时与集合的范式进行对比。

表述客观世界的各种现象，表述人们的思想，表述各门学科的规则、理论等，除使用自然语言（这常常是上有歧异性的）外，还要使用一些特定的术语、符号、规律等“对象语言”，这些是所研究学科的一种特殊的形式化语言，研究思维结构与规律的逻辑学也有其对象语言。

本章就是讨论逻辑学中的对象语言—命题及其演算，它相当于自然语言中的语句。

§1-1-1 命题逻辑联结词与真值表一、命题的基本概念首先我们从下面的例子加以分析。

例1-1-1.1人总是要死的。

例1-1-1.2苏格拉底是人。

例1-1-1.3苏格拉底是要死的。

例1-1-1.4中国人民是勤劳和勇敢的。

例1-1-1.5鸵鸟是鸟。

例1-1-1.6 1是质（素）数。

离散数学中的逻辑关系及其应用离散数学是数学的一个分支，主要研究离散的结构及其上的操作。

逻辑关系是离散数学中的一个重要概念，它在数学、计算机科学等领域都有广泛应用。

本文将介绍离散数学中的逻辑关系及其应用。

1. 逻辑关系的定义及性质离散数学中的逻辑关系是指一种二元关系，即对于某个集合中的两个元素，这两个元素之间有一种特定的关系。

在逻辑中，这个关系通常表示为“P → Q”，其中P和Q是两个命题，表示“如果P成立，则Q也成立”的关系。

逻辑关系有以下几种性质：（1）自反性：对于任意元素a，a与自己之间存在关系。

（2）对称性：对于任意元素a和b，如果a与b之间存在关系，那么b与a之间也存在关系。

（3）传递性：对于任意元素a、b和c，如果a与b之间存在关系，b与c之间也存在关系，那么a与c之间也存在关系。

2. 逻辑关系的应用（1）逻辑门电路逻辑门电路是计算机硬件的基本组成部分，它们的功能是根据输入的命题逻辑值计算出输出的命题逻辑值。

逻辑门电路包括与门、或门及非门等，它们之间的逻辑关系可以用逻辑代数中的公式来表示。

（2）判断与证明逻辑关系在数学证明中有广泛应用，可以用来判断某些语句、假设或结论是否成立。

常见的逻辑关系有蕴含关系、等价关系和充分必要条件等，它们在判断和证明中有重要作用。

（3）数据结构逻辑关系在数据结构中也有着广泛的应用。

例如在二叉树中，每个节点有两个子节点，子节点之间存在着父子关系。

在图论中，节点之间则存在着边的关系。

这些关系可以使用逻辑关系来描述和分析。

3. 总结逻辑关系是离散数学中的重要概念，它无处不在，在数学、计算机科学等领域都有着广泛的应用。

熟练掌握逻辑关系的定义及性质，对于深入理解离散数学和其它相关领域有着重要的意义。

离散数学在计算机中的应用(一)离散数学在计算机中的应用1. 布尔代数（Boolean Algebra）布尔代数是离散数学中的一个分支，它在计算机科学中有着广泛的应用。

布尔代数主要研究逻辑运算和二进制数字系统。

在计算机中，布尔代数用于逻辑电路的设计和分析，如与门、或门、非门等。

布尔代数的原理为计算机内部的逻辑运算提供了基础。

2. 集合论（Set Theory）集合论是离散数学的另一个重要分支，它在计算机科学中也有着广泛的应用。

在计算机中，集合论用于数据的存储和处理。

例如，数据库系统中使用集合论的概念来表示和操作数据集合，例如关系代数和关系演算。

另外，集合论的概念也被用于算法设计和分析中，例如集合的交集、并集和差集等操作。

3. 图论（Graph Theory）图论是离散数学中的一个分支，它研究图的性质和图的应用。

在计算机科学中，图论被广泛应用于解决各种问题，如网络路由、社交网络分析、搜索引擎优化等。

例如，使用图论的算法可以在互联网中找到最短路径，帮助搜索引擎快速检索相关结果。

此外，图的着色和匹配问题也被用于任务调度和资源分配等方面。

4. 数理逻辑（Mathematical Logic）数理逻辑是离散数学中的一个重要分支，它研究命题的真假和推理的规律。

在计算机科学中，数理逻辑被广泛应用于计算机程序的验证和验证工具的设计。

例如，使用数理逻辑的模型检测方法可以自动验证程序的正确性，帮助程序员发现潜在的错误。

此外，数理逻辑的概念也被用于设计数据库查询语言和编程语言的语义。

5. 组合数学（Combinatorics）组合数学是离散数学中研究离散结构的一门学科，它关注事物之间的选择、排列和组合方式。

在计算机科学中，组合数学被广泛应用于算法设计和分析。

例如，在密码学中，组合数学的概念被用于设计和分析密码系统的安全性。

此外，组合数学的技术也被用于网络优化、图像处理和信息检索等领域。

6. 概率论（Probability Theory）概率论是离散数学中研究随机事件的概率分布和统计规律的学科。

《离散数学》资料库第一章数理逻辑1、数理逻辑的历史。

逻辑是研究人类思维学科，最早是由古希腊学者亚里士多德创建的，他的《工具论》奠定了逻辑学的理论基础。

中国最早的一部逻辑专著--《墨经》也创造了一个比较完整的逻辑体系。

b5E2RGbCAP 根据所研究的对象和方法的不同，逻辑学可分为形式逻辑、辩证逻辑和数理逻辑。

数理逻辑得用数学方法研究推理，利用符号体系研究推理过程中前提和结论之间的关系，因此也叫符号逻辑。

plEanqFDPw从十七世纪开始，就有一些学者试图用数学的方法来研究逻辑。

德国的哲学家的数学家莱布尼兹&".10让血2＞被公认为是数理逻辑的创始人。

他认为数学之所以能发展如此迅速，数学知识之所以能如此有效，就是因为数学使用了特别的符号语言。

这种符号语言为表达思想和进行推理提供了非常良好的条件。

因此他提出了用一种象数学一样的表意符号体系来研究思维形式和规律，能简洁地表达出各种的推理的逻辑关系，使得推理过程就象数学一样可以利用公式来进行计算，以便用计算来解决争论。

DXDiTa9E3d1847年，英国数学家、逻辑学家布尔（G.Boole＞发表了《逻辑的数学分析》（The mathematical Analysis of Logic＞，建立了“布尔代数”（Boolean Algebra＞，并创造一套符号系统，利用符号来表示逻辑中的各种概念。

布尔建立了一系列的运算法则，利用代数的方法研究逻辑问题，初步奠定了数理逻辑的基础。

RTCrpUDGiT十九世纪七十年代末至二十世纪初，为了理解数学命题的性质和数学思维规律，德国的弗雷格（G.Frege＞、意大利的皮亚诺（G.Peano ＞和英国的罗素（B.Russell＞建立了古典逻辑演算、命题演算和谓词演算。

数理逻辑突破了古典形式逻辑的局限，形成了一个完整的逻辑体系.5PCzVD7HxA而德国的希尔伯特（D.Hilbert^D哥德尔（K.Godel＞的研究努力又使数理逻辑成为一门内容丰富的独立学科。

数理逻辑与离散数学数理逻辑与离散数学是一门研究数学中的逻辑和离散结构的学科。

它们在数学领域中扮演着重要的角色，为数学家和计算机科学家提供了强大的工具和方法。

在这篇文章中，我们将探讨数理逻辑与离散数学的基本概念、应用和发展。

1. 数理逻辑的基本概念数理逻辑是研究逻辑的数学分支，它主要关注命题、谓词和推理的形式化。

数理逻辑的基本概念包括命题逻辑、谓词逻辑和形式系统等。

命题逻辑研究的是命题的真假和推理的正确性，谓词逻辑则引入了个体和谓词的概念，用于描述更加复杂的逻辑结构。

形式系统则是数理逻辑的基础，它定义了逻辑推理的规则和语法。

2. 离散数学的基本概念离散数学是研究离散结构的数学分支，它主要关注离散对象和离散关系的性质。

离散数学的基本概念包括集合论、图论、代数结构等。

集合论研究的是集合的性质和运算，图论则研究的是图的性质和算法。

代数结构则是研究代数系统的抽象结构，包括群、环和域等。

3. 数理逻辑与离散数学的应用数理逻辑和离散数学在数学和计算机科学中有广泛的应用。

在数学领域，它们被用于证明和推理，帮助数学家发现新的定理和结论。

在计算机科学领域，数理逻辑和离散数学为计算机科学家提供了建模和分析的工具。

例如，图论被广泛应用于网络和路由算法的设计，离散数学的概念被用于设计和分析算法的正确性和复杂性。

4. 数理逻辑与离散数学的发展数理逻辑和离散数学作为学科的发展可以追溯到19世纪末。

随着数学和计算机科学的发展，它们变得越来越重要。

在20世纪，数理逻辑和离散数学得到了快速发展，涌现出了许多重要的理论和方法。

例如，哥德尔的不完备性定理揭示了数理逻辑的局限性，图论的四色定理解决了染色问题的一个重要难题。

总结起来，数理逻辑与离散数学是一门研究数学逻辑和离散结构的学科，它们在数学和计算机科学中有重要的应用和发展。

通过形式化和抽象化，数理逻辑和离散数学帮助数学家和计算机科学家研究和理解复杂的问题。

随着科学技术的不断进步，数理逻辑和离散数学将继续发展，为人类的认知和计算能力提供更强大的支持。

离散数学与其他学科之间的联系摘要：离散数学，又称为组合数学。

离散数学是计算机出现以后迅速发展起来的一门数学分支。

计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。

离散数学的发展改变了传统数学中分析和代数占统治地位的局面。

它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

关键词：离散数学电路设计软件技术人工智能应用等1、离散数学的相关介绍1.1离散数学的简介离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。

它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。

由于离散数学在计算机科学中的重要作用，国内外几乎所有大学的计算机类专业的教学计划中都将其列为核心课程进行重点建设，它是其他骨干课程，如数据结构、操作系统、人工智能、计算机网络、软件工程、编译原理等的先修课程，国内许多大学将其作为计算机专业类研究生入学考试的内容。

1.2离散数学的发展20世纪的计算机出现，带动了世界性的信息革命的伟大进程。

计算机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科地位一样，由计算机出现带动的信息革命当然计算机科学将起着主导的作用。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

第1 章命题逻辑逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。

辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。

形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。

数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。

所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。

因此数理逻辑也称为符号逻辑。

数理逻辑的基础部分是命题逻辑和谓词逻辑。

本章主要讲述命题逻辑，谓词逻辑将在第2 章进行讨论。

1.1命题及其表示1.1.1命题的基本概念数理逻辑研究的中心问题是推理（Inference)，而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。

在数理逻辑中，将能够判断真假的陈述句称为命题。

因此命题就成为推理的基本单位。

在命题逻辑中，对命题的组成部分不再进一步细分。

定义1.1.1 能够判断真假的陈述句称为命题（Proposition）。

命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。

真值为真的命题称为真命题，真值为假的命题称为假命题。

从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。

例1.1.1 判断下列句子是否为命题（1）北京是中国的首都。

（2）请勿吸烟！（3）雪是黑的。

（4）明天开会吗？（5）x+y=5。

（6）我正在说谎。

（7）9+5≤12 。

（8）1+101=110 。

（9）今天天气多好啊！（10）别的星球上有生物。

解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y 取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。

广东工业大学考博考试大纲：离散数学及其应用
导读：本文广东工业大学考博考试大纲：离散数学及其应用，仅供参考，如果觉得很不错，欢迎点评和分享。

基本内容: (300字以内)
1、数理逻辑
命题逻辑等值演算，主析取与主合取范式，联结词完备集，命题逻辑推理理论，谓词逻辑，谓词逻辑等值演算，谓词逻辑推理理论。

2、集合论
二元关系，关系的运算，关系的性质，等价关系，偏序关系，哈斯图，函数。

3、代数系统
代数系统，二元运算及其性质，半群与群，格与布尔代数。

4、图论
无向图与有向图、，通路与回路，图的连通性，图的表示，树，生成树与最小生成树，根树，树，欧拉图，哈密顿图，偶图，平面图。

5、计算机科学中的应用
串和语言，形式文法，有限状态自动机，两类自动机的转换。

题型要求及分数比例：(博士生满分100分，学术型、专业学位硕士生满分均150分)
解答题：100分
参考书目(包括作者、书目、出版社、出版时间)：
1、《离散数学》，左孝凌、李为鑑、刘永才，上海科学技术文献出版社，
2012。

2、《离散数学》，屈婉玲,耿素云，张立昂编，高等教育出版社，2008年。

3、《Discrete Mathematics and Its Applications》，Kenneth H.Rosen著，(《离散数学及其应用》袁崇义，屈婉玲，张桂芸译)，机械工业出版社，2011年。

作业答案：数理逻辑部分P14：习题一1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（3 答：简单命题，真命题。

（9）吸烟请到吸烟室去！ 答：不是命题。

（12）8是偶数的充分必要条件是8能被3整除。

答：复合命题，假命题。

14、讲下列命题符号化。

（6）王强与刘威都学过法语。

答：:p 王强学过法语；:q 刘威学过法语。

符号化为：p q ∧（10）除非天下大雨，他就乘班车上班。

答：:p 天下大雨；:q 他乘班车上班。

符号化为：p q →（13）“2或4是素数，这是不对的”是不对的。

答：:p 2是素数；:q 4是素数。

符号化为：(())p q ⌝⌝∨15、设:p 2+3=5. :q 大熊猫产在中国。

:r 太阳从西方升起。

求下列复合命题的真值。

（2）(())r p q p →∧↔⌝（4）()(())p q r p q r ∧∧⌝↔⌝∨⌝→ 解答： p 真值为1；q 真值为1；r 真值为0.（2）p q ∧真值为1；()r p q →∧真值为1；p ⌝真值为0；所以(())r p q p →∧↔⌝真值为0.（4）p q r ∧∧⌝真值为1，p q ⌝∨⌝真值为0，()p q r ⌝∨⌝→真值为1；所以()(())p q r p q r ∧∧⌝↔⌝∨⌝→真值为1.19、用真值表判断下列公式的类型。

（4）()()p q q p →→⌝→⌝所以为重言式。

（7）所以为可满足式。

P36:习题二3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。

（1）()p q q ⌝∧→ 解答：()(())(())()10p q q p q q p q q p q q ⌝∧→⇔⌝⌝∧∨⇔⌝⌝∨⌝∨⇔⌝⌝∨⌝∨⇔⌝⇔所以为永假式。

（2）(())()p p q p r →∨∨→ 解答：(())()(())()()()1()1p p q p r p p q p r p p q p r p r →∨∨→⇔⌝∨∨∨⌝∨⇔⌝∨∨∨⌝∨⇔∨⌝∨⇔ 所以因为永真式。