离散数学(谓词逻辑)课后总结

第2章 谓词逻辑一、重点内容1．谓词与量词谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念．谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项(用a , b , c ,…表示)和个体变项(用x , y , z ,…表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F , G , P ,…表示. 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.量词，是在命题中表示数量的词，量词有两类：全称量词∀，表示“所有的”或“每一个”；存在量词∃，表示“存在某个”或“至少有一个”.在谓词逻辑中，使用量词应注意以下几点：(1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变.(2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域.(3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义. 谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应. 在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域．一般地，使用全称量词∀，特性谓词后用→；使用存在量词∃，特性谓词后用∧.2．公式与解释谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式.例如∀x (F (x )→G (x ))，∃x (F (x )∧G (x ))，∀x ∀y (F (x )∧F (y )∧L (x ,y )→H (x ,y ))等都是谓词公式. 变元与辖域，在谓词公式∀xA 和∃xA 中，x 是指导变元，A 是相应量词的辖域. 在∀x 和∃x 的辖域A 中，x 的所有出现都是约束出现，即x 是约束变元，不是约束出现的变元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效.换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变.代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号.解释(赋值)，谓词公式A 的个体域D 是非空集合，则(1) 每一个常项指定D 中一个元素；(2) 每一个n 元函数指定D n 到D 的一个函数；(3) 每一个n 元谓词指定D n 到{0,1}的一个谓词；按这个规则做的一组指派，称为A 的一个解释或赋值.在有限个体域下，消除量词的规则为：如D ＝{a 1,a 2,…,a n }，则)(...)()()()(...)()()(2121n n a A a A a A x xA a A a A a A x xA ∨∨∨⇔∃∧∧∧⇔∀ 谓词公式分类，在任何解释下，谓词公式A 取真值1，公式A 为逻辑有效式(永真式)；在任何解释下谓词公式A 取真值0，公式A 为永假式；至少有一个解释使公式A 取真值1，公式A 称为可满足式.3．前束范式 一个谓词公式的前束范式仍是谓词公式. 若谓词公式F 等值地转化成 B x Q x Q x Q k k (2211)那么B x Q x Q x Q k k ...2211就是F 的前束范式，其中Q 1，Q 2，…，Q k 只能是∀或∃，x 1,x 2,…,x k 是个体变元，B 是不含量词的谓词公式.每个谓词公式F 都可以变换成与它等值的前束范式. 其步骤如下：① 消去联结词→，↔；② 将联结词⌝移至原子谓词公式之前；③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；④将∀x ,∃x 移至整个公式最左边；⑤ 得到公式的前束范式.二、实例 例1 将下列命题符号化：(1) 每个自然数都是整数，而有些整数不是自然数．(2) 不是所有的素数都不是偶数(3) 鸟会飞．注意：一般地，全称量词“∀”后，跟条件联结词“→”；存在量词“∃”后，跟合取联结词“∧”.解 (1) 设N (x )：x 是自然数，Z (y )；y 是整数，则命题符号化为：))()(())()((x N x Z x x Z x N x ⌝∧∃∧→∀．(2) 设F (x )：x 是素数，E (x )：x 是偶数，命题符号化为：⌝∀x (F (x )→⌝E (x ))或∃x （F （x ）∧E （x ））(3) 设F (x )：x 是鸟，G (x )：x 会飞翔．则命题符号化为：)()((x G x F x →∀) ． 例2 设谓词公式)(),()),,(),((y F z y yR z x y zQ y x P x ↔∀∧∀→∃，试写出量词的辖域，并指出该公式的自由变元和约束变元．解 ∃x 的辖域是：P (x , y )→∀zQ (y , x , z )；∀z 的辖域是：Q (y , x , z )；∀y 的辖域是：R (y , x )公式的自由变元是：y , z ；约束变元是：x , y , z ．例3 求谓词公式))(())((a f R x Q P x ∧→∀的真值．其中P ：4>3，Q （x ）：x >1，R （x ）：x ≤2．f （-3）=1，f （1）=5，f （5）= -3．a ：5．个体域D =（-3，1，5）．解 ))(())((a f R x Q P x ∧→∀=))5(())5(())1(())3((f R Q P Q P Q P ∧→∧→∧-→=)3()11()01()01(-∧→∧→∧→R01100=∧∧∧=注：这是给定解释下，求谓词公式的真值，个体域有限，比较好求．只需将量词消去，函数值代入谓词，根据谓词的真值，即可求出谓词公式的真值.要判断一个谓词公式的真、假是较为难的. 在谓词逻辑中，在任何解释下都真的公式，才是永真式；在任何解释下公式A 为假，才是永假式；公式A 不总是假，或者至少有一个解释使得公式A 为真，才是可满足式. 困难之点是在全总个体域中所有的解释如何说清楚. 因此只能要求会作简单问题.例 4 将谓词公式),()()),()()((z x zS x xR z x Q x R x P x ∃→∃∧∨→∀中的约束变元换名．解 ),()()),()()((z x zS x xR z x Q x R x P x ∃→∃∧∨→∀=),()()),()()((w x wS v vR z u Q u R u P u ∃→∃∧∨→∀例5 求谓词公式),,()),,()((z y x zH z y x yG x F x ∃→∀∧∃的前束范式．. 解 ①消去联结词→(若有↔也要消去).),,()),,()((z y x zH z y x yG x F x ∃→∀∧∃),,()),,()((z y x zG z y x yG x F x ∃∨∀∧⌝∃⇔② 将联结词⌝移至原子公式之前.),,()),,()((z y x zH z y x G y x F x ∃∨⌝∃∨⌝∀⇔③ 换名.),,()),,()((w y x wH z v u G v u F u ∃∨⌝∃∨⌝∀⇔(自由变元的x , y , z 未改) ④ 把量词提到整个公式的前面.)),,(),,()((w y x H z v u G u F w v u ∨⌝∨⌝∃∃∀⇔ (前束范式) (或))),,(),,()((w y x H z v u G u F w v u →∧∃∃∀⇔为所求前束范式.注：变元字母表示不惟一．写在一起，所求前束范式是),,()),,()((z y x zH z y x yG x F x ∃→∀∧∃),,()),,()((z y x zG z y x yG x F x ∃∨∀∧⌝∃⇔),,()),,()((z y x zH z y x G y x F x ∃∨⌝∃∨⌝∀⇔),,()),,()((w y x wH z v u G v u F u ∃∨⌝∃∨⌝∀⇔)),,(),,()((w y x H z v u G u F w v u ∨⌝∨⌝∃∃∀⇔ (前束范式) (或))),,(),,()((w y x H z v u G u F w v u →∧∃∃∀⇔为所求前束范式.注：重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为量词在最前面，后面不含量词的公式，即前束范式. 虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的.三、练习题 1. 选择填空题：(1) 谓词公式)())()((x Q y yR x P x →∃∨∀中量词∀x 的辖域是( C )(A) ))()((y yR x P x ∃∨∀ (B) P (x ) (C) )()(y yR x P ∃∨ (D) )(x Q(2) 谓词公式∃xA (x )∧⌝∃xA (x )的类型是（ B ）(A) 永真式 (B) 矛盾式(C) 非永真式的可满足式 (D) 不属于(A),(B),(C)任何类型(3) 设个体域为整数集，下列公式中其真值为1的是( A )(A) )0(=+∃∀y x y x (B) )0(=+∀∃y x x y(C))0(=+∀∀y x y x (D) )0(=+∃⌝∃y x y x(4) 公式))(),()),()((x S z y zR y x Q x P x →∃∨→∀的自由变元是 , 约束变元是：y ,x ; x ,z(5) 换名规则施于 变元，代入规则施于 变元(6) 谓词公式))()(()(x xQ x Q x x xP ⌝∃→⌝∀→∀的类型是(A )(A) 永真式 (B) 永假式 (C) 非永真的可满足式 (D) 蕴涵式(7) 设个体域是整数集合，P 代表∀x ∀y ((x <y )→(x -y )<x )，下面4个命题中为真的是( C )(A)P 是真命题 (B) P 是假命题(C) P 是谓词公式，但不是命题 (D) P 不是谓词公式(8) 设个体域D ＝{a ,b },公式)),()((y x yH x G x ∃→∀消去量词化为7. (G (a )→(H (a ,a )∨H (a ,b )))∧ (G (b )→(H (b ,a )∨H (b ,b ))) ．2. 设个体域D ＝{岳飞，文天祥，秦荟}，谓词F (x )：x 是民族英雄．求∀xF (x )的真值．3. 设P 是二元谓词，给定解释I 如下：D ＝{a ,b },P (a ,a )=P (b ,a )=1，P (b ,a )=P (b ,b )=0 求下列公式的真值：(1) ),(x x xP ∀； (2) ),(y x yP x ∃∀; (3) ),(y x yP x ∃∃4. 用归谬法，构造下面的推理证明.)()(x xB x xA ∀→∃⇒))()((x B x A x →∀四、练习题答案1. (1) C (2) B (3) A (4) y ,x ; x , z (5) 约束，自由 (6) A(7) C (8) (G (a )→(H (a , a )∨H (a , b )))∧ (G (b )→(H (b , a )∨H (b , b ))) ．2. 设a , b , c 分别为岳飞，文天祥和秦桧，∀xF (x )⇔F (a )∧F (b )∧F (c )⇔03. (1)0；(2)∀x ∃y (P (y , x )⇔∃yP (y , a )∧∃yP (y , b )⇔(P (a , a )∨P (b , a ))∧(P (a , b )∨ P (b , b ))⇔1∧0⇔0(3) ∃x ∃y (P (x , y )⇔∃yP (a , y )∨∃xP (b , y )=P (a , a )∨P (a , b )∨P (b , a )∨P (b . b )⇔14. 前提：)()(x xB x xA ∀→∃ 结论：))()((x B x A x →∀证明：① )))()(((x B x A x →∀⌝ 附加前提② )))()(((x B x A x →⌝∃ T ①E③ ))()((c B c A →⌝ T ①②ES④ A (c )∧⌝B (c ) T ③ E⑤ A (c ) T ④ I⑥ ⌝B (c )∧A (c ) T ④ .E⑦ ⌝B (c ) T ⑥ I⑧ )()(x xB x xA ∀→∃ P⑨ ∀x (⌝A (x )∨B (x )) T ⑧ E ⑩ ⌝A (c )∨B (c ) T ⑨ US11 ⌝A (c ) T ⑩ ,⑦ I12 )()(c A c A ∧⌝ T 11 , ⑤I可见，推理成立．。

2024年学习《离散数学》心得体会模板《离散数学》学习心得体会随着信息科学技术的不断发展，离散数学作为计算机科学与技术中的重要学科，越来越受到学生们的关注与重视。

作为一门理论性较强的课程，《离散数学》涉及到一系列的离散结构、数学推理和证明方法等内容，对于学生来说具有一定的挑战性。

在2024年的学习过程中，我对《离散数学》有着一些新的体会和收获。

首先，通过学习《离散数学》，我对离散结构有了更深入的了解。

离散结构是计算机科学与技术的基础，也是离散数学的重要内容。

在这门课程中，我学习了集合论、关系、函数、图论等各种离散结构的概念和性质。

通过对离散结构的学习，我逐渐认识到离散数学在计算机科学中的重要性，这为我以后的学习和研究奠定了坚实的基础。

其次，学习《离散数学》让我了解到数学推理的重要性。

离散数学是一门很有理论性的学科，需要进行严密的推理和证明。

在学习中，我逐渐熟悉了数学推理的方法和步骤，比如直接证明、归纳法、反证法等。

这些方法不仅在离散数学中有所应用，在其他学科中也有很大的作用。

通过锻炼数学推理的能力，我对问题的思考和解决能力也有了明显的提升。

此外，学习《离散数学》还让我明白了数学的抽象思维的重要性。

离散数学中的很多概念和性质都具有很高的抽象程度，需要我们用抽象的思维方式去理解和运用。

在学习过程中，我逐渐适应了这种抽象思维的方式，并通过解决问题和做题的过程中熟练掌握了抽象思维的技巧。

这对于我以后在计算机科学和其他领域的学习和研究有着重要的借鉴意义。

此外，通过学习《离散数学》，我也提高了自己的问题解决能力。

离散数学中的问题往往需要我们通过分析和推理找到解决的方法，这对于培养我们的问题解决能力非常重要。

通过实践和思考，我逐渐掌握了解决问题的一般步骤和方法，提高了自己的问题解决能力。

这对于我以后在工作和生活中遇到问题时会有极大的帮助。

综上所述，通过学习《离散数学》，我对离散结构有了更深入的了解，对数学推理和抽象思维有了更高的要求，并提高了自己的问题解决能力。

注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。

也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。

选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。

关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。

当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。

蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。

《离散数学》课程总结第一篇：《离散数学》课程总结《离散数学》学期总结转眼之间，这学期要结束了。

我们的离散数学，这门课程的学习也即将接近尾声。

下面就是我对这门课一些认识及自己的学习心得。

首先我们这门课程离散数学到底包含了哪几大部分？每部分具体又有什么内？这门课程在计算机科学中有什么地位？这门课程在我们以后的学习生活中，以及在将来的工作中有什么帮助？下面我将以上几个方面具体谈一谈并将总结一下自己本人在这门课程学习过程中遇到的一些问题和心得体会。

这门课程有数理逻辑，集合论，代数系统和图论四部分。

这四大部分通常被称为离散数学的四大体系。

其中每一部分都是一个独立的学科，内容丰富。

而我们离散数学中的内容是其中最基本，最重要且和计算机科学最密切相关的内容吸收到离散数学中来，并使它们前后贯通，形成一个有机整体。

这门课的主要内容有命题逻辑、谓词逻辑，属于数理逻辑部分，集合论中有集合、二元关系、函数，代数系统包含代数系统基础、群、环、域以及格和布尔代数的知识（这部分我们没有涉及）。

那么这门课程在计算机科学中有着什么样的地位呢，这门课程是计算机科学专业中重要的专业基础课程，核心课程，可以这么说，离散数学，既是一门专业基础课，是一门工具性学科。

这门课讲授的内容，与后续专学习业密切相关。

在这门课里我们讲授了大量的计算机学科专业必要的基本概念，基本理论和基本方法。

为我们以后的学习，工作打下良好基础。

在算法设计，人工智能，计算机网络，神经网络，智能计算等学科中有着重要的作用。

在计算机科学中有着广泛的应用。

通过这门课可以对我们计算机算法的理解和逻辑思维得到提高。

那么我们具体学了什么内容呢？（一）首先集合论是整个数学的基础，（不管是离散数学还是连续数学）如果没有专门学过，那么出现在离散数学中还是很合适的。

至于由集合论引出的二元关系，函数的内容，也是理所应当的。

数理逻辑是一个让人眼前一亮的东西。

我第一次发现，原来有些复杂的推理问题是可以通过“计算”的方法解决的。

离散数学（课件上习题）第一章例1-1.1 判定下面这些句子哪些是命题。

⑴2是个素数。

⑵雪是黑色的。

⑶2013年人类将到达火星。

⑷如果a>b且b>c，则a>c 。

（其中a,b,c都是确定的实数）⑸x+y<5⑹请打开书！⑺您去吗？⑴⑵⑶⑷是命题例1-2.1 P：2是素数。

⌝P：2不是素数。

例1-2.2 P：小王能唱歌。

Q：小王能跳舞。

P∧Q：小王能歌善舞。

例1-2.3. 灯泡或者线路有故障。

（析取“∨”）例1-2.4. 第一节课上数学或者上英语。

（异或、排斥或。

即“⊽”）注意：P ⊽Q 与(P∧⌝Q)∨(Q∧⌝P ) 是一样的。

归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定“⌝”(2) 合取“∧”(3) 析取“∨”(4) 异或“⊽”(5) 蕴涵“→”(6) 等价“↔”例1-2.5：P表示：缺少水分。

Q表示：植物会死亡。

P→Q：如果缺少水分，植物就会死亡。

P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”。

也说成P是P→Q 的前件，Q是P→Q的后件。

还可以说P是Q的充分条件，Q是P的必要条件。

以下是关于蕴含式的一个例子P：天气好。

Q：我去公园。

1.如果天气好，我就去公园。

2.只要天气好，我就去公园。

3.天气好，我就去公园。

4.仅当天气好，我才去公园。

5.只有天气好，我才去公园。

6.我去公园，仅当天气好。

命题1.、2.、3.写成：P→Q命题4.、5.、6.写成：Q→P例1-2.6：P：△ABC 是等边三角形。

Q ：△ABC是等角三角形。

P↔Q ：△ABC 是等边三角形当且仅当它是等角三角形。

课后练习：填空已知P∧Q为T，则P为( )，Q为( )。

已知P∨Q为F，则P为( )，Q为( )。

已知P为F，则P∧Q为( )。

已知P为T，则P∨Q为( )。

已知P∨Q为T，且P为F ，则Q为( )。

已知P→Q为F，则P为( )，Q为( )。

已知P为F，则P→Q为( )。

离散数学笔记总结一、命题逻辑。

1. 基本概念。

- 命题：能够判断真假的陈述句。

例如“2 + 3 = 5”是真命题，“1 > 2”是假命题。

- 命题变元：用字母表示命题，如p,q,r等。

2. 逻辑联结词。

- 否定¬：¬ p表示对命题p的否定，若p为真，则¬ p为假，反之亦然。

- 合取wedge：pwedge q表示p并且q，只有当p和q都为真时，pwedge q才为真。

- 析取vee：pvee q表示p或者q，当p和q至少有一个为真时，pvee q为真。

- 蕴含to：pto q表示若p则q，只有当p为真且q为假时，pto q为假。

- 等价↔：p↔ q表示p当且仅当q，当p和q同真同假时，p↔ q为真。

3. 命题公式。

- 定义：由命题变元、逻辑联结词和括号按照一定规则组成的符号串。

- 赋值：给命题变元赋予真假值，从而确定命题公式的真值。

- 分类：重言式（永真式）、矛盾式（永假式）、可满足式。

4. 逻辑等价与范式。

- 逻辑等价：若A↔ B是重言式，则称A与B逻辑等价，记作A≡ B。

例如¬(pwedge q)≡¬ pvee¬ q（德摩根律）。

- 范式：- 析取范式：由有限个简单合取式的析取组成的命题公式。

- 合取范式：由有限个简单析取式的合取组成的命题公式。

- 主析取范式：每个简单合取式都是极小项（包含所有命题变元的合取式，每个变元只出现一次）的析取范式。

- 主合取范式：每个简单析取式都是极大项（包含所有命题变元的析取式，每个变元只出现一次）的合取范式。

二、谓词逻辑。

1. 基本概念。

- 个体：可以独立存在的事物，如人、数等。

- 谓词：用来刻画个体性质或个体之间关系的词。

例如P(x)表示x具有性质P，R(x,y)表示x和y具有关系R。

- 量词：- 全称量词∀：∀ xP(x)表示对于所有的x，P(x)成立。

- 存在量词∃：∃ xP(x)表示存在某个x，使得P(x)成立。

总结离散数学知识点第二章命题逻辑1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假；2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反；4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写；6.真值表中值为1的项为极小项，值为0的项为极大项；7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取；8.永真式没有主合取范式，永假式没有主析取范式；9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假)10.命题逻辑的推理演算方法：P规则，T规则①真值表法；②直接证法；③归谬法；④附加前提法；第三章谓词逻辑1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质；多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；2.全称量词用蕴含→，存在量词用合取^;3.既有存在又有全称量词时，先消存在量词，再消全称量词；第四章集合1.N，表示自然数集，1,2,3……，不包括0；2.基：集合A中不同元素的个数，|A|；3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)；4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2；5.集合的分划：(等价关系)①每一个分划都是由集合A的几个子集构成的集合；②这几个子集相交为空，相并为全(A)；6.集合的分划与覆盖的比较：分划：每个元素均应出现且仅出现一次在子集中；覆盖：只要求每个元素都出现，没有要求只出现一次；第五章关系1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数为2种不同的关系；mn，A到B上可以定义mn2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；3.全关系的性质：自反性，对称性，传递性；空关系的性质：反自反性，反对称性，传递性；全封闭环的性质：自反性，对称性，反对称性，传递性；4.前域(domR)：所有元素x组成的集合；后域(ranR)：所有元素y组成的集合；5.自反闭包：r(R)=RUI;x对称闭包：s(R)=RU1-R;传递闭包：t(R)=RU2R U3R U……6.等价关系：集合A上的二元关系R满足自反性，对称性和传递性，则R称为等价关系；7.偏序关系：集合A上的关系R满足自反性，反对称性和传递性，则称R是A上的一个偏序关系；8.covA={<x,y>|x,y属于A，y盖住x}；9.极小元：集合A中没有比它更小的元素(若存在可能不唯一)；极大元：集合A中没有比它更大的元素(若存在可能不唯一)；最小元：比集合A中任何其他元素都小(若存在就一定唯一)；最大元：比集合A中任何其他元素都大(若存在就一定唯一)；10.前提：B是A的子集上界：A中的某个元素比B中任意元素都大，称这个元素是B的上界(若存在，可能不唯一)；下界：A中的某个元素比B中任意元素都小，称这个元素是B的下界(若存在，可能不唯一)；上确界：最小的上界(若存在就一定唯一)；下确界：最大的下界(若存在就一定唯一)；第六章函数2种不同的关系，有m n种不同的函1.若|X|=m,|Y|=n,则从X到Y有mn数；2.在一个有n个元素的集合上，可以有22n种不同的关系，有n n种不同的函数，有n!种不同的双射；3.若|X|=m,|Y|=n，且m<=n，则从X到Y有A m n种不同的单射；4.单射：f:X-Y，对任意x,2x属于X,且1x≠2x，若f(1x)≠f(2x)；1满射：f:X-Y，对值域中任意一个元素y在前域中都有一个或多个元素对应；双射：f:X-Y，若f既是单射又是满射，则f是双射；5.复合函数：fºg=g(f(x));6.设函数f:A-B，g:B-C，那么①如果f,g都是单射，则fºg也是单射；②如果f,g都是满射，则fºg也是满射；③如果f,g都是双射，则fºg也是双射；④如果fºg是双射，则f是单射，g是满射；第七章代数系统1.二元运算：集合A上的二元运算就是2A到A的映射；2.集合A上可定义的二元运算个数就是从A×A到A上的映射的个数，即从从A×A到A上函数的个数，若|A|=2,则集合A上的二元运算的个数为2*22=42=16种；3.判断二元运算的性质方法：①封闭性：运算表内只有所给元素；②交换律：主对角线两边元素对称相等；③幂等律：主对角线上每个元素与所在行列表头元素相同；④有幺元：元素所对应的行和列的元素依次与运算表的行和列相同；⑤有零元：元素所对应的行和列的元素都与该元素相同；4.同态映射：<A,*>,<B,^>,满足f(a*b)=f(a)^f(b),则f为由<A,*>到<B,^>的同态映射；若f是双射，则称为同构；第八章群1.广群的性质：封闭性；半群的性质：封闭性，结合律；含幺半群(独异点)：封闭性，结合律，有幺元；群的性质：封闭性，结合律，有幺元，有逆元；2.群没有零元；3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律；4.循环群中幺元不能是生成元；5.任何一个循环群必定是阿贝尔群；第十章格与布尔代数1.格：偏序集合A中任意两个元素都有上、下确界；2.格的基本性质：1) 自反性a≤a 对偶: a≥a2) 反对称性a≤b ^ b≥a => a=b对偶:a≥b ^ b≤a => a=b3) 传递性a≤b ^ b≤c => a≤c对偶:a≥b ^ b≥c => a≥c4) 最大下界描述之一a^b≤a 对偶 avb≥aA^b≤b 对偶 avb≥b5）最大下界描述之二c≤a,c≤b => c≤a^b对偶c≥a,c≥b =>c≥avb6) 结合律a^(b^c)=(a^b)^c对偶 av(bvc)=(avb)vc7)等幂律a^a=a 对偶 ava=a8) 吸收律a^(avb)=a 对偶 av(a^b)=a9) a≤b <=> a^b=a avb=b10) a≤c,b≤d => a^b≤c^d avb≤cvd11) 保序性b≤c => a^b≤a^c avb≤avc12）分配不等式av(b^c)≤(avb)^(avc)对偶 a^(bvc)≥(a^b)v(a^c)13）模不等式a≤c <=> av(b^c)≤(avb)^c3.分配格：满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)；4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构；5.链格一定是分配格，分配格必定是模格；6.全上界：集合A中的某个元素a大于等于该集合中的任何元素，则称a为格<A,<=>的全上界，记为1；(若存在则唯一)全下界：集合A中的某个元素b小于等于该集合中的任何元素，则称b为格<A,<=>的全下界，记为0；(若存在则唯一)7.有界格：有全上界和全下界的格称为有界格，即有0和1的格；8.补元：在有界格内，如果a^b=0,avb=1，则a和b互为补元；9.有补格：在有界格内，每个元素都至少有一个补元；10.有补分配格(布尔格)：既是有补格，又是分配格；11.布尔代数：一个有补分配格称为布尔代数；第十一章图论1.邻接：两点之间有边连接，则点与点邻接；2.关联：两点之间有边连接，则这两点与边关联；3.平凡图：只有一个孤立点构成的图；4.简单图：不含平行边和环的图；5.无向完全图：n个节点任意两个节点之间都有边相连的简单无向图；有向完全图:n个节点任意两个节点之间都有边相连的简单有向图；6.无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边；7.r-正则图：每个节点度数均为r的图；8.握手定理：节点度数的总和等于边的两倍；9.任何图中，度数为奇数的节点个数必定是偶数个；10.任何有向图中，所有节点入度之和等于所有节点的出度之和；11.每个节点的度数至少为2的图必定包含一条回路；12.可达：对于图中的两个节点v,j v，若存在连接i v到j v的路，则称i vi与v相互可达，也称i v与j v是连通的；在有向图中，若存在i v到j v的j路，则称v到j v可达；i13.强连通：有向图章任意两节点相互可达；单向连通：图中两节点至少有一个方向可达；弱连通：无向图的连通；(弱连通必定是单向连通)14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集；割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点；15.关联矩阵：M(G)，m是i v与j e关联的次数，节点为行，边为列；ij无向图：点与边无关系关联数为0，有关系为1，有环为2；有向图：点与边无关系关联数为0，有关系起点为1终点为-1，关联矩阵的特点：无向图：①行：每个节点关联的边，即节点的度；②列：每条边关联的节点；有向图：③所有的入度(1)=所有的出度(0);16.邻接矩阵：A(G)，a是i v邻接到j v的边的数目，点为行，点为列；ij17.可达矩阵：P(G)，至少存在一条回路的矩阵，点为行，点为列； P(G)=A(G)+2A(G)+3A(G)+4A(G)可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路；A(G)中所有数的和：表示图中路径长度为1的通路条数；2A(G)中所有数的和：表示图中路径长度为2的通路条数；3A(G)中所有数的和：表示图中路径长度为3的通路条数；4A(G)中所有数的和：表示图中路径长度为4的通路条数；P(G)中主对角线所有数的和：表示图中的回路条数；18.布尔矩阵：B(G)，v到j v有路为1，无路则为0，点为行，点为列；i19.代价矩阵：邻接矩阵元素为1的用权值表示，为0的用无穷大表示，节点自身到自身的权值为0；20.生成树：只访问每个节点一次，经过的节点和边构成的子图；21.构造生成树的两种方法：深度优先；广度优先；深度优先：①选定起始点v；②选择一个与v邻接且未被访问过的节点1v；③从v出发按邻接方向继续访问，当遇到一个节点所1有邻接点均已被访问时，回到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次；广度优先：①选定起始点v；②访问与v邻接的所有节点1v,2v,……,k v,这些作为第一层节点；③在第一层节点中选定一个节点v为起点；1④重复②③，直到所有节点都被访问过一次；22.最小生成树：具有最小权值(T)的生成树；23.构造最小生成树的三种方法：克鲁斯卡尔方法；管梅谷算法；普利姆算法；（1）克鲁斯卡尔方法①将所有权值按从小到大排列；②先画权值最小的边，然后去掉其边值；重新按小到大排序；③再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去掉其边值；重新按小到大排序；④重复③，直到所有节点都被访问过一次；（2）管梅谷算法(破圈法)①在图中取一回路，去掉回路中最大权值的边得一子图；②在子图中再取一回路，去掉回路中最大权值的边再得一子图；③重复②，直到所有节点都被访问过一次；（3）普利姆算法①在图中任取一点为起点v，连接边值最小的邻接点2v；1②以邻接点v为起点，找到2v邻接的最小边值，如果最小边值2比v邻接的所有边值都小(除已连接的边值)，直接连接，否则退回1v，1连接v现在的最小边值(除已连接的边值)；1③重复操作，直到所有节点都被访问过一次；24.关键路径例2 求PERT图中各顶点的最早完成时间, 最晚完成时间, 缓冲时间及关键路径.解：最早完成时间TE(v1)=0TE(v2)=max{0+1}=1TE(v3)=max{0+2,1+0}=2TE(v4)=max{0+3,2+2}=4TE(v5)=max{1+3,4+4}=8TE(v6)=max{2+4,8+1}=9TE(v7)=max{1+4,2+4}=6TE(v8)=max{9+1,6+6}=12 最晚完成时间TL(v8)=12TL(v7)=min{12-6}=6TL(v6)=min{12-1}=11TL(v5)=min{11-1}=10TL(v4)=min{10-4}=6TL(v3)=min{6-2,11-4,6-4}=2 TL(v2)=min{2-0,10-3,6-4}=2 TL(v1)=min{2-1,2-2,6-3}=0 缓冲时间TS(v1)=0-0=0TS(v2)=2-1=1TS(v3)=2-2=0TS(v4)=6-4=2TS(v5=10-8=2TS(v6)=11-9=2TS(v7)=6-6=0TS(v8)=12-12=0关键路径: v1-v3-v7-v825.欧拉路：经过图中每条边一次且仅一次的通路；欧拉回路：经过图中每条边一次且仅一次的回路；欧拉图：具有欧拉回路的图；单向欧拉路：经过有向图中每条边一次且仅一次的单向路；欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路；26.（1）无向图中存在欧拉路的充要条件：①连通图；②有0个或2个奇数度节点；（2）无向图中存在欧拉回路的充要条件：①连通图；②所有节点度数均为偶数；（3）连通有向图含有单向欧拉路的充要条件：①除两个节点外，每个节点入度=出度；②这两个节点中，一个节点的入度比出度多1，另一个节点的入；度比出度少1；（4）连通有向图含有单向欧拉回路的充要条件：图中每个节点的出度=入度；27.哈密顿路：经过图中每个节点一次且仅一次的通路；哈密顿回路：经过图中每个节点一次且仅一次的回路；哈密顿图：具有哈密顿回路的图；28.判定哈密顿图（没有充要条件）必要条件：任意去掉图中n个节点及关联的边后，得到的分图数目小于等于n；充分条件：图中每一对节点的度数之和都大于等于图中的总节点数；29.哈密顿图的应用：安排圆桌会议；方法：将每一个人看做一个节点，将每个人与和他能交流的人连接，找到一条经过每个节点一次且仅一次的回路(哈密顿图)，即可；30.平面图：将图形的交叉边进行改造后，不会出现边的交叉，则是平面图；31.面次：面的边界回路长度称为该面的次；32.一个有限平面图，面的次数之和等于其边数的两倍；33.欧拉定理：假设一个连通平面图有v个节点，e条边，r个面，则 v-e+r=2；34.判断是平面图的必要条件：(若不满足，就一定不是平面图)设图G是v个节点，e条边的简单连通平面图，若v>=3，则e<=3v-6；35.同胚：对于两个图G1,G2，如果它们是同构的，或者通过反复插入和除去2度节点可以变成同构的图，则称G1，G2是同胚的；36.判断G是平面图的充要条件：图G不含同胚于K3.3或K5的子图；37.二部图：①无向图的节点集合可以划分为两个子集V1，V2；②图中每条边的一个端点在V1，另一个则在V2中；完全二部图：二部图中V1的每个节点都与V2的每个节点邻接；判定无向图G为二部图的充要条件：图中每条回路经过边的条数均为偶数；38.树：具有n个顶点n-1条边的无回路连通无向图；39.节点的层数：从树根到该节点经过的边的条数；40.树高：层数最大的顶点的层数；41.二叉树：①二叉树额基本结构状态有5种；②二叉树内节点的度数只考虑出度，不考虑入度；③二叉树内树叶的节点度数为0，而树内树叶节点度数为1；④二叉树内节点的度数=边的总数(只算出度)；握手定理“节点数=边的两倍”是在同时计算入度和出度的时成立；⑤二叉树内节点的总数=边的总数+1；⑥位于二叉树第k层上的节点，最多有12 k个(k>=1)；⑦深度为k的二叉树的节点总数最多为k2-1个，最少k个(k>=1)；⑧如果有n个叶子，2n个2度节点，则0n=2n+1；42.二叉树的节点遍历方法：先根顺序（DLR）；中根顺序（LDR）；后根顺序（LRD）；43.哈夫曼树：用哈夫曼算法构造的最优二叉树；44.最优二叉树的构造方法：①将给定的权值按从小到大排序；②取两个最小值分支点的左右子树(左小右大)，去掉已选的这两个权值，并将这两个最小值加起来作为下一轮排序的权值；③重复②，直达所有权值构造完毕；45.哈夫曼编码：在最优二叉树上，按照左0右1的规则，用0和1代替所有边的权值；每个节点的编码：从根到该节点经过的0和1组成的一排编码；欢迎您的下载，资料仅供参考！致力为企业和个人提供合同协议，策划案计划书，学习课件等等打造全网一站式需求。

第二章谓词逻辑2—1基本概念例题１. 所有的自然数都是整数。

设N(x)：x是自然数。

I(x)：x是整数。

此命题可以写成∀x(N(x)→I(x))例题２. 有些自然数是偶数。

设E(x)：x是偶数。

此命题可以写成∃x(N(x)∧E(x))例题3. 每个人都有一个生母。

设P(x):x是个人。

M(x,y):y是x的生母。

此命题可以写成：∀x(P(x)→∃y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化例题1. 如果x是奇数，则2x是偶数。

其中客体x与客体2x之间就有函数关系，可以设客体函数g(x)=2x，谓词O(x)：x是奇数，E(x)：x是偶数，则此命题可以表示为：∀x(O(x)→E(g(x)))例题2 小王的父亲是个医生。

设函数f(x)=x的父亲，谓词D(x):x是个医生，a:小王，此命题可以表示为D(f(a))。

例题3 如果x和y都是奇数，则x+y是偶数。

设h(x,y)=x+y ，此命题可以表示为:∀x∀y((O(x)∧O(y))→E(h(x,y))命题的符号表达式与论域有关系两个公式：一般地，设论域为{a1,a2,....,an}，则有(1). ∀xA(x)⇔A(a1)∧A(a2)∧......∧A(an)(2). ∃xB(x)⇔B(a1)∨B(a2)∨......∨B(an)1.每个自然数都是整数。

该命题的真值是真的。

表达式∀x(N(x)→I(x))在全总个体域的真值是真的,因∀x(N(x)→I(x))⇔(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an))式中的x不论用自然数客体代入，还是用非自然数客体代入均为真。

例如(N(0.1)→I(0.1))也为真。

而∀x(N(x)∧I(x))在全总个体域却不是永真式。

∀x(N(x)∧I(x))⇔(N(a1)∧I(a1))∧(N(a2)∧I(a2)) ∧…∧(N(an)∧I(an))比如x用0.2代入(N(0.2)∧I(0.2))就为假。

离散数学谓词逻辑
1.谓词逻辑基本概念
能够独立存在的具体或抽象的事物，称之为个体，也称之为客体。

通常用小写英文字母a、b、c…表示
例如：小张、小李、8，a，沈阳，社会主义都是客体。

个体常项:具体的或特定的个体。

常用a,b,c,…等小写字母表示
个体变元:泛指某一个个体。

常用x,y,z,…等小写字母表示
谓词：用以刻化个体属性或者表达个体之间关系的词，即为谓词。

谓词用大写字母表示。

谓词也有常项与变项之分。

表示具体性质与关系的谓词称为谓词常项。

泛指某–性质或关系的谓词称为谓词变项。

将不带个体变元的谓词称为0元谓词。

例如，S(a)，G(3,7) 等。

当谓词是常项时，0元谓词是命题;否则当谓词是变项时，0 元谓词是命题变元。

含有n个变元的命题函数是以个体域为定义域，以{ F,T }为值域的n元函数。

注意:命题函数本身并不是命题，只有在括号内填入足够的具体客体，或用足够的量词约束后才变成命题。

个体变元的取值范围，称之为个体域，也称之为论域。

由所有个体构成的个体域，称之为全总个体域。

它是“最大的个体域。

约定:对于一个命题函数，如果没有指明其个体域，则假定其个体域是全总个体域。