下载文档原格式
离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。
其它疑问句、祈使句、感叹句、悖论等皆不是。
详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。
特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q →P；除非P否则Q，应为┐P→Q。
B设出原子命题写出符号化公式。
详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。
详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。
②对每个指派，以二进制数从小到大或从大到小顺序列出。
③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。
详见P8。
6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15,7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A B的充要条件是A B且B A。
主要等价式：(1)双否定：A A。
(2)交换律：A∧B B∧A，A∨B B∨A，A B B A。
3)结合律：(A∧B)∧C A ∧(B∧C)，(A∨B)∨C A∨(B∨C)，(A B)C A(B C)。
(4) 分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。
(5) 德·摩根律：(A∧B)A∨B，(A∨B)A∧B。
(6) 等幂律：A∧A A，A∨A A。
(7) 同一律：A∧T A，A∨F A。
(8) 零律：A∧F F，A∨T T。
(9) 吸收律：A∧(A∨B)A，A∨(A∧B)A。
(10) 互补律：A ∧A F，(矛盾律)，A∨A T。
(排中律)(11) 条件式转化律：A→B A∨B，A→B B→A。
02324离散数学知识点
离散数学是研究离散对象和离散结构的数学分支，其知识点包括但不限于集合论、图论、逻辑学、组合数学等。
以下是其中一些重要的知识点：
1. 集合论：集合论是离散数学的基石，它研究集合、集合之间的关系和集合的性质。
2. 图论：图论是离散数学的重要组成部分，它研究图（由节点和边构成的结构）的性质和分类。
3. 逻辑学：逻辑学是离散数学的另一个重要组成部分，它研究推理的规则和形式。
在离散数学中，逻辑通常用于描述和证明一些结构或系统的性质。
4. 组合数学：组合数学是离散数学的一个分支，它研究计数、排列和组合问题。
5. 离散概率论：离散概率论是离散数学的另一个分支，它研究离散随机事件的数学模型。
6. 离散概率分布：离散概率分布是描述离散随机事件发生概率的数学模型。
7. 离散随机变量：离散随机变量是能够取到可数无穷多个值的随机变量。
8. 离散概率空间：离散概率空间是一个集合，它包含一个可数无穷多的元素，每个元素都有一个与之相关的概率值。
9. 离散随机过程：离散随机过程是离散随机事件在时间或空间上的序列。
这些知识点都是离散数学的重要组成部分，它们在计算机科学、数学、物理学等领域都有广泛的应用。
离散数学必备知识点总结资料离散数学是指离散的数学概念和结构，独立于连续的数学。
它是在计算机科学、信息科学、数学基础研究、工程技术等领域中的基础课程之一。
以下是离散数学必备的一些知识点总结。
一、逻辑与集合1. 命题与谓词：命题是一个陈述，可以被判断为真或假，而谓词是一种用来描述命题所涉及实体之间关系的语句。
2. 命题逻辑：重点关注命题真假和与或非等运算关系，包括真值表和主范式。
3. 一阶谓词逻辑：注意包含全称量词和存在量词，也包括a|b, a//b等符号的理解。
4. 集合与运算：集合是指不同元素组成的一个整体。
基本的集合运算包括并、交、差等。
5. 关系与函数：关系是一种元素之间的对应关系，而函数是一种具有确定性的关系，即每一个自变量都对应唯一的函数值。
6. 等价关系与划分：等价关系是指满足自反性、对称性和传递性的关系。
划分是指将一个集合分成若干个不相交的子集，每个子集称为一个等价类。
二、图论1. 图的定义和基本概念：图由节点和边构成，节点间的连线称为边。
包括度、路径、连通性等概念。
2. 图的表示方法：邻接矩阵和邻接表。
3. 欧拉图与哈密顿图：欧拉图是指能够一笔画出的图，哈密顿图是指含有一条经过每个节点恰好一次的路径的图。
4. 最短路径与最小生成树：最短路径问题是指在图中找出从一个节点到另一个节点的最短路径。
最小生成树问题是指在图中找出一棵覆盖所有节点的树，使得边权之和最小。
三、代数系统1. 代数结构：包括群、环、域等概念。
2. 群的定义和基本概念：群是在一个集合中定义一种二元运算满足结合律、单位元存在和逆元存在的代数结构。
四、组合数学1. 排列、组合和二项式系数：排列是指从n个元素中任选r个进行排序，组合是指从n个元素中任选r个但不考虑排序，二项式系数是指组合数。
2. 生成函数：将组合数与多项式联系起来的一种工具，用于求出某种算法或结构的某些特定函数。
3. 容斥原理：一个集合的容斥原理指在集合的并、交、补之间的关系。
离散数学复习要点离散数学是数学的一个分支领域，主要研究离散的结构和离散情形下的数学对象及其相关性质。
它与连续数学不同，离散数学的对象是离散的，如集合、图、布尔代数等。
在计算机科学、信息科学、通信工程等领域中，离散数学的理论和方法被广泛应用。
以下是离散数学的一些重要的复习要点：1.集合论：集合是离散数学的基础，集合的基本运算如交、并、差等，以及集合的基本性质如并集和交集的结合律、分配律等，都是需要复习的内容。
此外，还需要了解集合的基数和幂集等概念。
2.命题逻辑：命题是一个可以判断真假的陈述句，命题逻辑是研究命题及其逻辑关系的数学体系。
需要复习的内容包括命题的逻辑运算，如非、与、或、异或等，以及逻辑等价、逻辑推理等。
3.谓词逻辑：谓词逻辑是对自然语言中的谓词进行形式化表示和推理的系统。
复习重点包括一阶谓词逻辑的基本概念，如谓词、量词、域、项等，以及谓词的合取、析取、全称量词和存在量词等逻辑联结词的语义。
4.图论：图论是研究图及其性质的数学分支。
需要复习的内容包括图的基本概念，如顶点、边、路径、圈等，以及图的表示方法、图的遍历算法、连通图、树等。
5. 网络流模型：网络流模型是研究流动网络的数学方法，主要包括最大流、最小割等问题。
需要复习的内容包括网络的基本概念，如容量、割、流等，以及Ford-Fulkerson算法等解决网络流问题的方法。
6.布尔代数：布尔代数是一种关于逻辑运算的代数系统，常用于电路设计和逻辑推理。
需要复习的内容包括布尔代数的基本运算，如与、或、非等，以及布尔函数的最小项与最大项表示、卡诺图等。
7.组合数学：组合数学是研究离散中的计数问题的数学分支。
需要复习的内容包括排列、组合、多元排列组合等的计数方法，如乘法原理、加法原理、排列组合的顺序问题等。
8.代数系统：代数系统是研究代数结构及其性质的数学分支，包括群、环、域等。
需要复习的内容包括群的基本概念和性质，如封闭性、结合律、单位元、逆元等。
离散数学知识点总结 一、各章复习要求与重点第一章 集 合[复习知识点]1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图3、序偶与迪卡尔积本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。
[本章重点习题]P5~6，4、6； P14~15，3、6、7； P20，5、7。
[疑难解析] 1、集合的概念因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。
2、集合恒等式的证明通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。
实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~⋂=-证明中的特殊作用。
[例题分析]例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。
解}}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A}}2,1{},2{},1{,{)(φρ=B于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ例2 设{}{}Φ=,,,,b a b a A ，试求：(1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。
解 (1){}{}{}Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{}Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~⋂⋃⋂=⋃⋂⋃ 证明()()()()()()()()()()()()()()()()()()B A B A B A B A B B B A A B A A B B A A B A B A B A ~~~~~~~~~~~~~⋂⋃⋂=Φ⋃⋂⋃⋂⋃Φ=⋂⋃⋂⋃⋂⋃⋂=⋂⋃⋃⋂⋃=⋃⋂⋃第二章 二元关系[复习知识点]1、关系、关系矩阵与关系图2、复合关系与逆关系3、关系的性质（自反性、对称性、反对称性、传递性）4、关系的闭包（自反闭包、对称闭包、传递闭包）5、等价关系与等价类6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界7、函数及其性质（单射、满射、双射）8、复合函数与反函数本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念 [复习要求]1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
高三离散数学知识点汇总离散数学是计算机科学、信息技术以及其他相关领域中的重要基础学科，是高中阶段的数学课程之一。
下面将对高三离散数学的主要知识点进行汇总，以帮助学生更好地复习和掌握这门学科。
一、命题逻辑命题逻辑是离散数学的基础，它研究命题的逻辑关系及其合成。
以下是命题逻辑中常见的知识点：1. 命题与命题的合取（与）、析取（或）、非（非）运算；2. 命题的真值表与真值；3. 命题的等价、蕴含、互斥等逻辑关系；4. 命题的可满足性与有效性。
二、集合与关系集合论是离散数学中的另一重要组成部分，它研究集合及其间的关系。
以下是集合与关系中的主要知识点：1. 集合的表示方式与基本操作，如并集、交集、差集和补集；2. 笛卡尔积与关系的定义；3. 关系的性质，如自反性、对称性、传递性等；4. 等价关系与偏序关系的概念与判断；5. 关系的闭包与传递闭包。
三、图论图论是离散数学中的重要分支，它研究图及其相关的性质与算法。
以下是图论中的常见知识点：1. 图的基本概念与表示方式，如顶点、边、度、路径等；2. 树与森林的定义与性质，包括最小生成树与最短路径树等；3. 图的连通性与强连通性的判定；4. 图的着色与平面图的概念；5. 图的网络流与匹配等问题。
四、代数系统代数系统是离散数学的重要组成部分，它研究运算规则及其相应的结构。
以下是代数系统中的主要知识点：1. 半群、幺半群、群的概念与性质；2. 环、域的定义与性质；3. 线性方程组与矩阵的基本运算；4. 同余与剩余类的概念与应用。
五、概率与统计概率与统计是离散数学的重要应用领域，它研究随机事件及其规律性。
以下是概率与统计中的常见知识点：1. 随机事件的基本概念与性质；2. 概率的计算方法，包括古典概型、几何概型、条件概率等；3. 随机变量与概率分布的概念与应用；4. 抽样与统计推断，包括参数估计与假设检验等。
综上所述，高三离散数学的知识点涵盖了命题逻辑、集合与关系、图论、代数系统以及概率与统计等方面。
离散数学复习资料离散数学是计算机科学与数学领域中的重要学科，它研究的是离散的数学结构和离散的数学对象。
在计算机科学领域，离散数学是构建算法和设计计算机系统的基础。
为了更好地复习离散数学，我们可以从以下几个方面入手。
一、集合论集合论是离散数学的基础，它研究的是集合及其运算。
在集合论中，我们需要了解集合的定义、基本运算和集合间的关系。
此外，还需要掌握集合的代数运算法则，如交、并、差和补集等。
复习时可以通过解题来加深理解，例如证明集合之间的等价关系、集合的幂集等。
二、逻辑与命题逻辑是离散数学中的重要分支，它研究的是推理和论证的规则。
在逻辑中，命题是最基本的逻辑单位。
复习时需要了解命题的定义和常见的逻辑运算符，如非、与、或、异或等。
此外，还需要熟悉命题的真值表和命题之间的逻辑等价关系。
通过解题和推理，可以提高对逻辑的理解和应用能力。
三、图论图论是离散数学中的一个重要分支，它研究的是图及其性质。
在图论中，我们需要了解图的基本概念，如顶点、边、路径、环等。
此外，还需要熟悉图的表示方法，如邻接矩阵和邻接表。
复习时可以通过解题来加深对图的理解，例如求最短路径、判断图的连通性等。
四、代数系统代数系统是离散数学中的一个重要内容，它研究的是代数结构及其性质。
在代数系统中，我们需要了解群、环、域等代数结构的定义和性质。
此外，还需要熟悉代数运算法则和代数结构之间的关系。
复习时可以通过解题来加深对代数系统的理解，例如证明一个集合构成一个群、判断一个环是否是域等。
五、概率论与统计学概率论与统计学是离散数学中的一个重要分支，它研究的是随机事件和随机变量的概率性质。
在概率论与统计学中，我们需要了解概率的定义和性质，掌握常见的概率分布和统计方法。
此外，还需要熟悉概率的运算法则和统计推断的基本原理。
复习时可以通过解题和实际问题的分析来加深对概率论与统计学的理解。
总之，离散数学作为计算机科学与数学领域中的重要学科，对于计算机科学专业的学生来说具有重要意义。
离散数学必备知识点总结汇总
1.集合论：集合的概念、元素、子集、交集、并集、差集、补集、空集、集合的运算、集合的等价关系、集合的序关系等。
2.命题逻辑：命题的概念、命题的联接词（与、或、非）、命题的否
定形式、命题的蕴涵、等价命题、命题的充分条件和必要条件、命题的合
取范式和析取范式、蕴涵式、逻辑等价式、命题的否定形式的推理。
3.谓词逻辑：谓词的概念、谓词的量化、全称量化和存在量化、谓词
逻辑的等价式和推理规则、归纳定理和应用。
4.关系：关系的概念、关系的性质、关系的运算、关系的性质和关系
的代数结构。
5.图论：图的概念、图的表示、连通图、树、度数和定理、欧拉图、
哈密顿图、图的平面性质等。
6.混合图：有向图、无向图、有向图和无向图的表示、混合图的回路、可达矩阵、连通度、强连通图等。
7.布尔代数：布尔运算、布尔函数、布尔代数的运算规则、完备性和
最小化。
8.代数结构：半群、群、环、域的定义和性质、同态和同构。
9.组合数学：排列组合、二项式系数、排列、组合、分配原理、鸽巢
原理、生成函数、容斥原理等。
10.图的着色：图的着色问题、邻接矩阵、边界点、图的着色问题的
算法、四色定理等。
11.概率论：基本概念、概率的性质、条件概率、独立事件、贝叶斯定理、随机变量、概率分布函数、期望、方差、协方差、相关系数、大数定理和中心极限定理等。
12.递归：递归关系、递归函数、递归算法、递归树、递归求解等。
离散数学知识点总结离散数学是数学的一个分支，主要研究离散的数学结构和离散的数学对象。
它包括了许多重要的概念和技术，是计算机科学、通信工程、数学和逻辑学等领域的基础。
本文将对离散数学的一些核心知识点进行总结，包括命题逻辑、一阶逻辑、图论、集合论和组合数学等内容。
1. 命题逻辑命题逻辑是离散数学的一个重要分支，研究命题之间的逻辑关系。
命题是一个陈述语句，要么为真，要么为假，而且不能同时为真和为假。
命题逻辑包括逻辑运算和逻辑推理等内容，是离散数学的基础之一。
1.1 逻辑运算逻辑运算包括与（∧）、或（∨）、非（¬）、蕴含（→）和双条件（↔）等运算。
与、或和非是三种基本的逻辑运算，蕴含和双条件则是基于这三种基本运算得到的复合运算。
1.2 逻辑等值式逻辑等值式是指在命题逻辑中具有相同真值的两个复合命题。
常见的逻辑等值式包括德摩根定律、双重否定定律、分配率等。
1.3 形式化证明形式化证明是命题逻辑的一个重要内容，研究如何利用逻辑规则和等值式来推导出给定命题的真值。
形式化证明包括直接证明、间接证明和反证法等方法，是离散数学中的常见技巧。
2. 一阶逻辑一阶逻辑是命题逻辑的延伸，研究命题中的量词和谓词等概念。
一阶逻辑包括量词、谓词逻辑和形式化证明等内容，是离散数学中的重要部分。
2.1 量词量词包括全称量词（∀）和存在量词（∃），用来对命题中的变量进行量化。
全称量词表示对所有元素都成立的命题，而存在量词表示至少存在一个元素使命题成立。
2.2 谓词逻辑谓词逻辑是一阶逻辑的核心内容，研究带有量词的语句和谓词的逻辑关系。
谓词是含有变量的函数，它可以表示一类对象的性质或关系。
2.3 形式化证明形式化证明在一阶逻辑中同样起着重要作用，通过逻辑规则和等值式来推导出给定命题的真值。
一阶逻辑的形式化证明和命题逻辑类似，但更复杂和抽象。
3. 图论图论是离散数学中的一个重要分支，研究图和图的性质。
图是由节点和边组成的数学对象，图论包括图的表示、图的遍历、最短路径、最小生成树等内容，是离散数学中的一大亮点。
离散数学复习要点第一章命题逻辑一、典型考查点1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。
其它疑问句、祈使句、感叹句、悖论等皆不是。
详见教材P12、联结词运算定律┐∧∨→记住特殊的：1∧1⇔1，0∨0⇔0，1→0⇔0，11⇔1，00⇔1详见P53、命题符号化步骤：A划分原子命题，找准联结词。
特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。
B设出原子命题写出符号化公式。
详见P54、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。
详见P95、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。
②对每个指派，以二进制数从小到大或从大到小顺序列出。
③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。
详见P8。
6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P157、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A⇔B的充要条件是A⇒B且B⇒A。
主要等价式：(1)双否定：⎤⎤A⇔A。
(2)交换律：A∧B⇔B∧A，A∨B⇔B∨A，A↔B⇔B↔A。
3)结合律：(A∧B)∧C⇔A ∧(B∧C)，(A∨B)∨C⇔A∨(B∨C)，(A↔B)↔C⇔A↔(B↔C)。
(4) 分配律：A∧(B∨C)⇔(A∧B)∨(A∧C)，A∨(B∧C)⇔(A∨B)∧(A∨C)。
(5) 德·摩根律：⎤(A∧B)⎤⇔A∨⎤B，⎤(A∨B)⎤⇔A∧⎤B。
(6) 等幂律：A∧A⇔A，A∨A⇔A。
(7) 同一律：A∧T⇔A，A∨F⇔A。
(8) 零律：A∧F⇔F，A∨T⇔T。
(9) 吸收律：A∧(A∨B)⇔A，A∨(A∧B)⇔A。
(10) 互补律：A∧⎤A⇔F，(矛盾律)，A∨⎤A⇔T。
(排中律)(11) 条件式转化律：A→B⎤⇔A∨B，A→B⎤⇔B→⎤A。
(12) 双条件式转化律：A↔B⇔(A→B)∧(B→A)⇔(A∧B)∨(⎤A∧⎤B)8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。
④用定义，证A⇒B，即证A→B是永真式。
9、范式求法步骤：①使用命题定律，消去公式中除、和以外公式中出现的所有联结词；②使用(P)P 和德·摩根律，将公式中出现的联结词都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。
10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P P。
(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P P∧（Q∨Q)或P P∨（Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。
注意：主析取范式与主合取范式之间的联系。
例如：(P Q)Q m1m3M0M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。
详见P1611、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。
重点规则（主要蕴含式）：(1) P∧Q⇒P化简(2) P∧Q⇒Q化简(3) P⇒P∨Q附加(4) ⎤P⇒P→Q变形附加(5)Q⇒P→Q变形附加(6) ⎤(P→Q)⇒P变形化简(7) ⎤(P→Q)⎤⇒Q变形化简(8) P，(P→Q)⇒Q假言推理(9) ⎤Q，(P→Q)⎤⇒P拒取式(10) ⎤P，(P∨Q)⇒Q析取三段论(11) (P→Q)，(Q→R)⇒P→R条件三段论(12) (P↔Q)，(Q↔R)⇒P↔R 双条件三段论文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。
详见P21二、强化练习1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗?2.下列式子为重言式的是( )A.P→P∨QB.(┐P∧Q)∧(P∨┐Q)C.┐ (P Q)D.(P∨Q) (P→Q)3．下列为两个命题变元P，Q的小项是（）A．P∧Q∧⎤ P B．⎤ P∨Q C．⎤ P∧Q D．⎤ P∨P∨Q4．下列语句中是真命题的是（）A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的5．设P：我们划船，Q：我们跑步。
命题“我们不能既划船又跑步”符号化为（）A．⎤ P∧⎤ Q B．⎤ P∨⎤ Q C．⎤（P Q）D．⎤（⎤ P∨⎤ Q）6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式7．命题公式⎤（P∧Q）→R的成真指派是（）A．000，001，110，B．001，011，101，110，111 C．全体指派D．无8．设P ：他聪明，Q ：他用功，命题“他虽聪明但不用功”的符号化正确的是（ ）A ． P ∧QB ．P ∧ QC ．P → QD ．P ∨ Q9．下面联结词运算不可交换的是（ ）A ．∧ B ．→ C ．∨ D ．10下列命题公式不是重言式的是（ ）A ．Q →（P ∨Q ）B ．（P ∧Q ）→PC ．（P ∧ Q ）∧（ P ∨Q ）D ．（P →Q ）（ P ∨Q ）11.设命题变元为P ，Q ，R ，则小项m100=________，大项M010=________。
12.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以________，记为________规则。
13.请用联结词┐，∧表示联结词∨和联结词 ：________，________。
14．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是________式。
15．命题公式（P ∧Q ）→ P 的成真指派为__________，成假指派为__________。
16.用等值演算求(P →Q)→R 的主合取范式。
17.列出(P →(Q ∨R)) (P →Q)的真值表。
19．构造命题公式（（P ∧Q ）→P ）∨R 的真值表。
20．求下列公式的主合取范式和主析取范式：P ∨（⎤ P →（Q ∨（⎤ Q →R ）））21．构造命题公式（R Q Q P ∧→∨）→P ∧ R 的真值表。
22．求下列公式的主析取范式和主合取范式：（P →（Q ∧R ））∧（ P →（ Q →R ））。
23.用推理方法证明：P ∨Q ，P →R ，Q →S├R ∨S 。
24．构造下面推理的证明。
如果小张和小王去看电影，则小李也去看电影。
小赵不去看电影或小张去看电影。
小王去看电影。
所以，当小赵去看电影时，小李也去。
25．构造下面推理的证明。
只要A 曾到过受害者房间并且11点以前没离开，A 就犯了谋杀罪。
A 曾到过受害者房间。
如果在11点以前离开，看门人会看见他。
看门人没有看见他。
所以A 犯了谋杀罪。
离散数学复习要点 第二章谓词逻辑一、典型考查点1、基本概念：个体词、个体域、谓词、特性谓词、辖域，详见P27；前束范式详见P362、谓词符号化 步骤：①正确理解给定命题。
必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。
②把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。
③找出恰当量词。
应注意全称量词(x)后跟条件式，存在量词(x)后跟合取式。
④用恰当的联结词把给定命题表示出来。
详见P303、谓词公式类型的判定（永真式、永假式、可满足式） 方法：利用论域翻译成自然语言后进行判断。
详见P344、自由变元与约束变元的判定 方法：按定义，关键是要看它在A 中是约束出现，还是自由出现，若与量词的指导变元相同，就是约束出现，不同就是自由出现。
详见P31。
5、等价式 (1)量词否定等价式：(a)(x)A (x)A(b)(x)A (x) A(2) 量词辖域缩小或扩大等价式(a) (x)(A(x)∧B)(x)A(x)∧B (b) (x)(A(x)∨B)(x)A(x)∨B(c) (x)(A(x)→B)(x)A(x)→B (d) (x)(B →A(x))B →(x)A(x)(e) (x)(A(x)∧B)(x)A(x)∧B (f) (x)(A(x)∨B)(x)A(x)∨B(g) (x)(A(x)→B)(x)A(x)→B (h) (x)(B →A(x))B →(x)A(x)。
(3) 量词分配律等价式：(a) (x)(A(x)∧B(x))(x)A(x)∧(x)B(x) (b)(x)(A(x)∨B(x))(x)A(x)∨(x)B(x)其中，A(x)，B(x)为有x 自由出现的任何公式。
详见P34356、蕴含式(a)(x)A(x)∨(x)B(x)(x)(A(x)∨B(x))(b) (x)(A(x)∧B(x))(x)A(x)∧(x)B(x)(c) (x)(A(x)→B(x))(x)A(x)→(x)B(x)(d) (x)(A(x)→B(x))(x)A(x)→(x)B(x)其中，A(x)和B(x)为含有x 自由出现的任意公式。
详见P356、前束范式 方法：①把量词全部通过等值演算化到整个谓词公式的前面②把量词前面的┐全部通过德摩根定律化到谓词公式的内部。
详见P367、推理：方法：演绎（常用格式）、反证法、CP 规则即附加前提等。
对于命题逻辑中的所有规则都可用。
特殊规则：(1)量词消去 (简称UI 或US 规则) (x)A(x)A(c) (x)A(x)A(y) (x)A(x)A(c)量词产生规则(简称EG 或UG 规则) A(c)(y)A(y) A(x)(y)A(y) 详见P38二、强化练习1.下列式子不是谓词合式公式的是( )A.(∀x)(P(x)→(x)(Q(x) ∧A(x ，y)))B.(∀x)∧(y)∨P(x ，y)C.(∀x)P(x)→R(y)D.(x)P(x)∧Q(y ，z) 2.设个体域为实数集，特定元素a=0，函数f(x ，y)=x-y ，特定谓词F(x ，y)为x<y ，下列公式真值为真的是( )A.(∀x)(∀y)F(x ，f(f(x ，y)，y))B.(∀x)(∀y)(┐F(f(x ，y)，x))C.(∀x)(∀y)(∀z)(F(x ，y)→F(f(x ，z)，f(y ，z)))D.(∀x)F(f(a ，x)，a)3.对于公式(∀x)(∀y)P(x ，y)∨Q(x ，z)∧(x)P(x ，y)，下列说法正确的是( )A.x 是自由变元B.x 是约束变元C.( ∀x)的辖域是P(x ，y)∨Q(x ，z)D.(∀x)的辖域是P(x ，y)4.设论域为{1，2}，与公式(∀x)┐A(X)等价的是( )A. ┐A(1) ∨┐A(2) B . ┐A(1)→┐(A2)C. ┐A(1) ∧┐A(2)D. A(1) →A(2)5．在公式（x ∀）F （x ，y ）→（∃ y ）G （x ，y ）中变元x 是（ ）A ．自由变元B ．约束变元C ．既是自由变元，又是约束变元D ．既不是自由变元，又不是约束变元6．下列等价式不正确的是（ ）A ．)(Q )(P ))(Q )(P (x x x x x x x ∀∨∀⇔∨∀B ．)(Q )(P ))(Q )(P (x x x x x x x ∀∧∀⇔∧∀C ．)(Q )(P ))(Q )(P (x x x x x x x ∃∨∃⇔∨∃D ．Q )(P )Q )(P (∧∀⇔∧∀x x x x7．设A （x ）:x 是人，B （x ）：x 犯错误，命题“没有不犯错误的人”符号化为（ ）A ．))(B )(A (x x x ∧∀ B ．→∃)(A (x x B （x ））C ．))(B )(A (x x x ∧∃D ．∧∃)(A (x x B(x))二、填空题8.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。
