离散数学（第3版）课件ch1(1) 命题逻辑1.1-1.4 贲

1

美国数学家柯朗在《数学是什么》一书中的说：“数学，作为人类智慧的一种表达形式，反映生动活泼的意念，深入细致的思考，以及完美和谐的愿望，它的基础是逻辑和直觉，分析和推进，共性和个性。”

法国数学家庞加莱：“数学是给予不同的东西以相同的名称的技术。”2“数学的贡献在于对整个科学技术（尤其是高新科技）水平的推进与提高，对科技人才的培育和滋润，对经济建设的繁荣，对全体人民的科学思维与文化素质的哺育，这四方面的作用是极为巨大的，也是其他学科所不能全面比拟的。”（王梓坤）数学的意义张恭庆(北京大学数学科学学院教授、中国科学院院士、第三世界科学院院士）一、世界强国与数学强国

二、数学及其基本特征

三、数学与当代科学技术

（一）数学与科学革命和技术革命

（二）数学与自然科学

（三）数学与社会科学

（四）数学与数据科学

（五）数学与技术科学

四、数学与国防

五、数学与国民经济

六、数学与文化教育

561Algorithms,Numbers,andMachines2Sets,Sequences,andCounting3BooleanExpressions,Logic,andProof4SearchingandSorting5GraphsandTrees6Relations:Especiallyon(Integer)Sequences7SequencesandSeries8GeneratingSequencesandSubsets9DiscreteProbabilityandAverage-CaseComplexity10TuringMachines7一、学科专业整体介绍二、什么是离散数学三、离散数学的主要内容四、离散数学的发展史五、学习离散数学的作用和目的六、课程特点与教学要求课程介绍8计算机科学与技术一、学科专业整体介绍9二、什么是离散数学

离散数学是一门重要理论基础课，它所研究的对象是离散的数学关系和离散的数学结构模型。通过例子理解“离散数学”（1）**是***；**不是***（2）帽子问题。甲乙丙3人，5顶帽子（3红2白）（3）三叉路口问题。（4）家庭舞会。（5）火柴游戏。（6）九宫图问题。10一副牌随便你拦腰斩，斩了很多次之后，把前面的五张拿出来，分别发给5个人，然后魔术师心灵感应一下，就可以知道这五张牌是什么。魔术师请拿红牌的人帮一个忙，往前走一步。例如，魔术师知道这五张牌的红黑顺序是“黑红黑红红”，然后魔术师就可以心灵感应出这五张牌是（

）。请问这其中的奥秘是什么呢？11

金银铜小像不在这只匣里小像在这只匣里小像不在金匣里

金银铜小像放在某一匣中。这3个陈述中至多有一个为真。问小像在哪一匣中？小像不在银匣里小像不在这只匣里小像在这只匣里小像放在某一匣中。这3个陈述中至少一真、至少一假。问小像在哪一匣中？12三、离散数学的主要内容数理逻辑集合论图论代数结构教材：《离散数学（第3版）》，2021清华大学出版社，高等学校计算机教育规划教材作者：贲可荣、袁景凌、谢茜《离散数学解题指导（第2版）》，2016清华大学出版社，作者：贲可荣、袁景凌、高志华13四、离散数学的发展史主要从四方面介绍。参考教材的附录。14为学习各专业课程作必要的数学准备；培养学生的学习能力、逻辑推理能力、抽象思维能力，提高学生综合素质。五、学习离散数学的作用和目的15面向不同培养目标的离散数学定位培养类型科学型工程型应用型培养要求基础理论和核心技术研究；原始创新基本理论与原理的综合应用（创新性应用）计算机应用人才人才定位学术研究IT企事业应用领域信息化人才培养人数少较多多离散数学的基础熟练掌握形式描述、变换、推理和证明方法；熟练掌握离散系统的描述与分析方法；了解实际离散系统的建模熟悉形式描述、变换、推理和证明方法；熟练掌握离散系统的描述与分析方法；了解实际离散系统的建模简要了解形式描述、变换、推理和证明方法；掌握离散系统描述与分析方法；熟悉常用的实际离散系统模型涉及其他专业课算法与数据结构、数据库系统原理、操作系统、编译原理、软件工程、人工智能、数字逻辑、计算机网络算法与数据结构、数据库系统原理、操作系统、编译原理、软件工程、数字逻辑、计算机网络数据结构与算法、数据库与信息管理技术、计算机网络与互联网学时安排建议学时：72-108建议学时：72-90建议学时：51-7216课程特点：内容繁多定义定理多抽象思维性强教学要求：适当地做笔记注意预习复习独立完成作业六、课程特点与教学要求教学时数：171.1现代逻辑学的基本研究方法1.2命题及其表示法1.3命题公式与语句形式化1.4重言式1.5对偶与范式1.6其他联结词1.7命题演算的推理理论1.8命题演算中的归结推理命题逻辑第1章181.1现代逻辑学

逻辑学的发展历史现代逻辑学的主要内容逻辑与计算机科学的联系19逻辑发展历史——三个阶段初始阶段：1660年代—19世纪末，数学应用于逻辑。Aristotle：形式逻辑（主词和谓词逻辑）Leibniz(1646-1716)

：建立直观而又精确的思维演算作为数理逻辑的创始人，建立一个“普遍的符号语言”“思维的演算”，成功地将命题形式表达为符号公式，构成了一个关于两个概念相结合的演算。

GeorgeBoole(1815-1864)

:逻辑代数DeMorgan(1806-1871)

:关系逻辑过渡阶段：成熟阶段：20逻辑发展历史——三个阶段初始阶段：过渡阶段：19世纪末—1940前后，逻辑应用于数学。非欧几何与公理化方法微积分与实数理论，Piano算术

GiuseppePePeano(1858-1932)

集合论与数学基础(1900年世界数学家大会)悖论与第三次数学危机，Hilbert（1862～1943）计划成熟阶段21逻辑发展历史——三个阶段初始阶段：过渡阶段：成熟阶段：1930s—1970年，成为数学的独立分支。KurtGödel(1906-1978)1930年发表的完全性定理说明了，形式系统可以从一阶逻辑演算得到足够的基本逻辑工具。Gödel于1931年的论文证明了公理化方法有局限性。Gödel不完全性定理：对任何一个包含Peano算术的有穷形式化的公理系统而言，必定存在一个明确定义的命题，在该系统中既不能证明它是真的，也不能证明它是假的。22现代逻辑学求助数学——符号化现代逻辑学追随数学——公理化现代逻辑学改造数学——形式化现代逻辑学的主要内容

现代逻辑学包括：命题逻辑、谓词逻辑、模态逻辑、时序逻辑、动态逻辑、多值逻辑、模糊逻辑等。23逻辑与计算机科学的联系数字电路：布尔逻辑。计算理论：可计算性，Turing机，形式语言，自动机，计算复杂性。程序语义与验证技术。程序的自动生成与转换。SQL:本质上等价于一阶逻辑。Prolog语言：以逻辑演算为基础。LISP语言：以λ演算为基础。人工智能。信息安全。……24（从知道问题看推理）老师手中握有一副牌（黑桃5、4、8、J；红心A、Q、4；◆A、5；梅花K、Q、5、4），我想好一张牌，并将该牌的花色告诉学生甲，将该牌的点数告诉学生乙。甲说：我敢肯定你不知道这张牌。乙说：那么我现在知道了。甲说：那么我也知道了。请问这张牌是什么牌？251.1现代逻辑学的基本研究方法1.2命题及其表示法1.3命题公式与语句形式化1.4重言式1.5对偶与范式1.6其他联结词1.7命题演算的推理理论1.8命题演算中的归结推理命题逻辑第1章261.2命题及其表示法思考题：相传在古代有一个残酷的国王，为了不准别人进入他的领地而制定了一个法规：“凡进入者若讲真话则杀头，若讲假话则淹死”。并要求士兵严格执行上述命令。一天，一个人进来说了一句话，导致士兵无法执行命令。请问这个人说了什么？一、命题的定义27例1判断下列句子是否为命题。

(1)3是素数。

(2)2是无理数。

(3)x大于y。

(4)土星上有冰。

(5)2100年元旦是晴天。

(6)我正在说假话。

(7)请不要吸烟！

(8)这朵花真美丽啊！

(9)3大于5吗？符号化——命题一般用英文字母表示。定义1命题是一个可以判断真假的陈述句。

28二、复合命题（1）4是偶数且是2的倍数。（2）武汉不是个小城市。（3）小王或小李考试得第一。（4）如果你努力，则你能成功。（5）三角形是等边三角形，当且仅当三边相等。

上述命题都是通过诸如“或”，“且”、“如果……，则……”等连词联结而成，这样命题，称为复合命题。相对地，构成复合命题的命题称为简单命题。那么，命题联结词用什么符号表示呢？29三、命题联结词定义2否定联结词┐设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作┐p，符号┐称作否定联结词。并规定┐p为真当且仅当p为假。30定义3合取联结词∧设p,q为二个命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q，∧称作合取联结词。并规定p∧q为真当且仅当p与q同时为真。31定义4析取联结词∨设p，q为二个命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词。并规定p∨q为假当且仅当p与q同时为假。32定义5蕴涵联结词→设p，q为二个命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作p→q，→称作蕴涵联结词。并规定p→q为假当且仅当p为真q为假。注意：在自然语言中，“如果p，则q”中的前件p与后件q往往具有某种内在联系。而在数理逻辑中，p与q可以无任何内在联系。33定义6等价联结词

设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p

q，

称作等价联结词。p

q的逻辑关系表示q是p的充分必要条件。341.1现代逻辑学的基本研究方法1.2命题及其表示法1.3命题公式与语句形式化1.4重言式1.5对偶与范式1.6其他联结词1.7命题演算的推理理论1.8命题演算中的归结推理命题逻辑第1章351.3命题公式与语句形式化

一个赋予特定内容的命题的真值是确定的，只有“T”和“F”两种，即命题常项或称为命题常元。一个没有任何意义的没有赋予具体内容的命题是一个命题变元。一、命题公式的定义下面我们正式定义命题变元：定义：以“真”“假”为其值域的变元称为命题变元。36定义(命题公式)(1)单个命题变元或命题常元是合式公式，并称为原子命题公式。(2)若A是合式公式，则(┐A)也是合式公式。(3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A

B)也是合式公式。(4)只有有限次地应用(1)～(3)形式的符号串才是合式公式。

合式公式就是形式上合法的公式。well-formedformula,wff37(1)

P,Q,R是合式公式;(2)

若A是合式公式，则(┐A)也是合式公式;(3)

若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A

B)也是；(4)

没有了。证明：（1）P,Q,R是wff（2）(P∧Q),(Q∨R)是wff（3）┐(Q∨R)是wff（4）((P∧Q)→(┐(Q∨R)))是wff证明((P∧Q)→(┐(Q∨R)))是wff。38

可用命题公式表示复合命题，常将这个过程称为语句形式化，或命题的符号化，或称为命题的翻译。

命题的翻译可按如下步骤进行：①找出复合命题中的简单命题。②用英文字母表示这些简单命题。③使用命题联结词将这些英文字母连接起来。二、语句形式化39例试翻译下列命题。(1)这部分内容无趣,习题也不难,而且这门课程也不使人喜欢。(2)如果这部分内容无趣,或者习题难,

那么这门课程就不使人喜欢。(3)这部分内容有趣,意味着习题难,反之亦然。解：设P表示“这部分内容有趣”,Q表示“这些习题难”,R表示“这门课使人喜欢”,40例

用A表示“明天早晨七点下雨”,B表示“明天早晨七点刮风”,C表示“我去学校”,

试用A，B，C表示下列复合命题：(1)如果明天早晨七点下雨但不刮风，则我去学校；(2)如果明天早晨七点不下雨并且也不刮风，则我去学校；(3)如果明天早晨七点下雨或不刮风，则我去学校；(4)明天我风雨无阻，一定去学校；(5)只有当明天早晨七点不下雨并且也不刮风时，我才去学校；(6)只有当明天早晨七点下雨或刮风都不发生时，我才去学校。41三、真值表的构建定义

设p1,p2,…,pn是出现在公式A中的全部命题符号，给p1,p2,…,pn各指定一个真值，称为对A的一个赋值或解释。定义

在命题公式A中，对A的每一个赋值，就确定了A的一个真值，把它们汇列成表，称该表为命题公式A

的真值表。42定义

设A和B是两个命题公式，若对A和B的所有赋值，A和B的真值都相同，则称A和B是逻辑等价的，记为A

B。例构建下列命题公式的真值表。(1)(p∧┐q)∨(┐p∧q)(2)┐(p→q)→p(3)(p∧┐q)∧┐p(4)┐

(p

q)43第1章命题逻辑1.1现代逻辑学1.2命题及其表示法1.3命题公式与语句形式化1.4重言式1.5对偶与范式1.6其他联结词1.7命题演算的推理理论1.8命题演算中的归结推理441.4重言式定义1.11

设A为任一命题公式。若A在它的各种指派下取值均为真,则称A是重言式(tautology)

或永真式。(2)若A在它的各种指派下取值均为假,则称A是矛盾式(falsity)或永假式。(3)若A不是矛盾式,则称A是可满足式。

45定义1.12

设A和B是两个命题公式，如果A

B是重言式，即A与B对任何指派都有相同的真值，则称A与B逻辑等价(等值)，记为AB。46以下给出16组重要的命题等价式，其中A,B,C为命题变元。

1.双重否定律

A

A2.幂等律

A

A∨A,A

A∧A3.交换律

A∨B

B∨A，A∧B

B∧A4.结合律

(A∨B)∨C

A∨(B∨C)(A∧B)∧C

A∧(B∧C)475.分配律

A∨(B∧C)

(A∨B)∧(A∨C)（∨对∧的分配律）

A∧(B∨C)

(A∧B)∨(A∧C)（∧对∨的分配律）6.德摩根律

(A∨B)

A∧

B，

(A∧B)

A∨

B7.吸收律

A∨(A∧B)

A，A∧(A∨B)

A

8.零律

A∨T

T,A∧F

F

489.同一律

A∨F

A，A∧T

A

10.排中律

A∨

A

T

11.矛盾律

A∧

A

F

12.蕴涵表达式

A→B

A∨B4913.等价表达式

(A

B)

(A→B)∧(B→A)14.假言易位

A→BB→┐A15.等价否定等价式

A

B

A

┐B

16.归谬论

(A→B)∧(A→

B)

A50例用等值演算的方法验证下列等价关系（1）(P→Q)→R

(Q∧P)∨R（2）P→(Q→R)

(P∧Q)→R51例用等值演算的方法判断下列公式类型（1）Q∨((P∨Q)∧P)（2）(P∨P)→((Q∧Q)∧R)命题等价式

1.双重否定律

A

A2.幂等律A

A∨A,A

A∧A3.交换律A∨B

B∨A，A∧B

B∧A4.结合律

(A∨B)∨C

A∨(B∨C)，(A∧B)∧C

A∧(B∧C)5.分配律