下载文档原格式
离散数学复习要点第一章命题逻辑一、典型考查点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。
离散数学必备知识点总结资料离散数学是指离散的数学概念和结构，独立于连续的数学。
它是在计算机科学、信息科学、数学基础研究、工程技术等领域中的基础课程之一。
以下是离散数学必备的一些知识点总结。
一、逻辑与集合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）每次课后布置的作业。
二、各章节提要教学目的及要求：教学内容：命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对偶与范式、推理理论。
教学重点：命题逻辑中的基本概念和基本推理方法。
教学难点：推理理论小结：学习第一章要注意以下几点：（1）弄清命题与陈述句的关系。
（2）弄清由5种基本联结词联结的复合命题的逻辑关系及其真值。
特别是要弄清蕴含式”P→Q“的逻辑关系及其真值。
（3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键问题。
（4）会准确地求出给定公式的主析取范式和主合取范式。
掌握主析取范式与真值表、成真赋值、主合取范式的关系。
（5）会用多种方法判断公式的类型及判断两个公式是否等价。
（6）会用等价变换法将一个联结词集中的公式等价地化为另一个联结词全功能集中的公式。
（7）掌握推理和判断推理是否正确的方法。
教学目的及要求：深刻理解和掌握谓词逻辑的基本概念和基本推理方法。
教学内容：谓词的概念与表示、命题函数与量词、谓词公式与翻译、变量的约束、谓词演算的等价式与蕴涵式、前束范式、谓词演算的推理理论。
教学重点：谓词逻辑中的基本概念和基本推理方法。
教学难点：谓词演算的推理理论。
小结：学习第二章要注意以下几点：(1)同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，必须弄清个体域。
(2)在将命题符号化时，要特别注意量词与联结词的搭配。
经常的情况是全称量词∀与蕴含词→搭配，存在量词∃与合取词∧搭配。
因此有下面两种形式的公式：（∀x）(A(x) →B(x)) ①（∃x）(A(x) ∧ B(x)) ②而（∀x）(A(x) ∧ B(x)) ③（∃x）(A(x) → B(x)) ④③与①，④与②的含义完全不同。
(3)记住主要的等价式。
会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。
离散数学复习资料第1章命题逻辑本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.一、重点内容1. 命题命题表述为具有确定真假意义的陈述句。
命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2. 六个联结词及真值表“⌝”否定联结词，P是命题，⌝P是P的否命题，是由联结词⌝和命题P组成的复合命题.P取真值1，⌝P取真值0，P取真值0，⌝P 取真值1. 它是一元联结词.“∧”合取联结词，P∧Q是命题P，Q的合取式，是“∧”和P，Q组成的复合命题. “∧”在语句中相当于“不但…而且…”，“既…又…”. P∧Q取值1，当且仅当P，Q均取1；P∧Q取值为0，只有P，Q之一取0.“∨”析取联结词，“⎺∨”不可兼析取(异或)联结词， P∨Q 是命题P，Q的析取式，是“∨”和P，Q组成的复合命题. P⎺∨Q是联结词“⎺∨”和P，Q组成的复合命题. 联结词“∨”或“⎺∨”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“P⎺∨Q”↔“(⌝P∧Q)∨(P∧⌝Q)”. P∨Q取值1，只要P，Q之一取值1，P∨Q取值0，只有P，Q都取值0.“→”蕴含联结词， P→Q是“→”和P，Q组成的复合命题，只有P取值为1，Q取值为0时，P→Q取值为0；其余各种情况，均有P→Q的真值为1，亦即1→0的真值为0，0→1，1→1，0→0的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“P→Q”.“↔”等价联结词，P↔Q是P，Q的等价式，是“↔”和P，Q组成的复合命题. “↔”在语句中相当于“…当且仅当…”，P↔Q 取值1当且仅当P，Q真值相同.3. 命题公式、赋值与解释，命题公式的分类与判别命题公式与赋值，命题P含有n个命题变项P1，P2,…,P n，给P1，P2,…,P n各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材P.16的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真。
离散数学复习提纲离散数学是一门关于离散对象的数学分支，它主要研究离散结构及其性质，广泛应用于计算机科学、信息技术、密码学等领域。
下面是一个离散数学的复习提纲，包括离散数学的基本概念、离散结构、图论、关系、逻辑以及集合论等内容。
一、离散数学的基本概念1.数学基础：集合、函数、关系、证明方法（数学归纳法、反证法、递归法等）；2.命题逻辑：命题、命题连接词、真值表、逻辑运算、逻辑等价、推理规则等；3.谓词逻辑：谓词、量词、公式、合取范式和析取范式、蕴含、等价、量词的否定规则等；4.证明方法：直接证明、间接证明、归谬证明、证明策略等。
二、离散结构1.图论：图的基本概念、图的表示方法、连通性、路径和回路、图的着色、最小生成树等；2.代数结构：群、环、域的定义、性质及基本例子；3.组合数学：组合基本原理、二项式系数、排列组合、生成函数、递归关系、容斥原理等；4.有限状态自动机：确定性有限状态自动机、非确定性有限状态自动机、正则表达式等。
1.图的基本概念：顶点、边、路径、回路、度等；2.图的表示：邻接矩阵、邻接表、关联矩阵等；3.图的遍历：深度优先、广度优先；4. 最短路径问题：Dijkstra算法、Floyd-Warshall算法；5. 最小生成树问题：Prim算法、Kruskal算法；6.匹配问题：最大匹配、二分图匹配等。
四、关系1.关系的基本概念：关系矩阵、关系的性质（反自反性、对称性、传递性等）；2.等价关系：等价关系的性质、等价类等；3.偏序关系：偏序关系的性质、偏序集合、哈斯图等；4.传递闭包：传递闭包的定义、传递闭包的计算方法等。
五、逻辑1.命题逻辑：命题的定义、逻辑运算、真值表、逻辑等价、推理规则等；2.谓词逻辑：量词的定义、公式的定义、量词的否定规则、等价变换等；3.命题逻辑与谓词逻辑的转换；4.形式化推理：前向链式推理、后向链式推理、消解法等。
1.集合的基本概念：子集、并集、交集、差集、补集等；2.集合运算：集合的并、交、差、补等运算的性质；3.集合的关系：包含关系、相等关系、等价关系等；4.集合的表示方法：列举法、描述法、元祖法等；5.集合的基数：有限集合的基数、无穷集合的基数、基数的性质。
百度文库离散数学复习整理离散数学复习整理离散数学复习整理函数***重点掌握：单射、满射、双射函数的概念一、函数的概念（和数学里面函数的概念差不多）A为函数f的定义域，记为domf=A；f(A)为函数f的值域，记为ranf。
|f|=|A|f(x)表示一个变值，f代表一个集合，因此f≠f(x)。
⨯|A||B||A|从A到B的不同的关系有2个；但从A到B的不同的函数却仅有|B|个。
(个数差别) 每一个函数的基数都为|A|个(|f|=|A|)，但关系的基数却为从零一直到|A|×|B|。
二、特殊函数单射：对任意x,x∈A，如果x≠x，有f(x)≠f(x)，则称f为从A到B的单射（不同的x对应121212不同的y)；满射：如果ranf＝B，则称f为从A到B的满射；（B的定义域都能通过函数f(x)求到）双射：若f是满射且是单射，则称f为从A到B的双射。
若A＝B，则称f为A上的函数；当A上的函数f是双射时，称f为一个变换。
定理：8.2.1设A，B是有限集合，且|A|=|B|，f是A到B的函数，则f是单射当且仅当f是满射。
典型(自然)映射：设R是集合A上的一个等价关系，g：A→A/R称为A对商集A/R的典型(自然) 映射，其定义为g(a)＝[a]，a∈A.R恒等函数：如果A=B，且对任意x∈A，都有f(x)=x，则称f为A上的恒等函数，记为I。
A常值函数：如果∃b∈B，且对任意x∈A，都有f(x)=b，则称f为常值函数。
上取整函数：对有理数x，f(x)为大于等于x的最小的整数，则称f(x)为上取整函数(强取整函数)，记为f(x)= ；下取整函数：对有理数x，f(x)为小于等于x的最大的整数，则称f(x)为下取整函数(弱取整函数)，记为f(x)= ；三、函数的复合运算不满足交换律，但满足结合律1.函数f和g可以复合⇔ranf⊆domg；2.dom(fog)=domf，ran(fog)⊆rang；3.对任意x∈A，有fog(x)=g(f(x))。
《离散数学》方世昌的期末复习知识点总结1.集合论-集合的定义和运算：交、并、差、补、反转。
子集与真子集的概念。
-集合的基数：有限集、无限集、可数集、不可数集的定义与特性。
-集合的运算律：交换律、结合律、分配律、幂等律、吸收律。
-集合的等价关系：等价关系的定义和性质，等价关系的划分和等价类。
2.逻辑与命题关系-命题与命题符号：命题的定义、真值表和含有逻辑连接词的复合命题。
-命题逻辑：命题的蕴涵、等价、否定、充分条件和必要条件。
-谓词逻辑：命题的全称量词、存在量词及其关系。
-命题逻辑推理：假言推理、析取推理、拒取推理、类比推理等。
3.图论-图的基本概念与术语：顶点、边、邻接、路径、回路、连通、子图、生成树等。
-图的分类：无向图、有向图、简单图、多重图、完全图。
-图的矩阵表示：邻接矩阵、关联矩阵、度矩阵等。
-图的遍历算法：深度优先、广度优先。
-图的最短路径算法：迪杰斯特拉算法、弗洛伊德算法。
4.代数系统与半群-代数结构：代数系统的定义、代数公理、代数性质。
-半群：半群的定义与性质，封闭性、结合律和单位元。
-半群的子半群与同态：子半群的概念，同态映射的定义与性质。
-有限半群与无限半群：有限半群的定义和性质，无限半群的特点与例子。
5.数论与代数-整数与整数集合的性质：整数的除法原理、整除、公约数、最大公约数和最小公倍数。
-同余关系与同余类：同余关系的定义、同余类的性质、同余关系的基本定理。
-质数与素数：质数的定义、素数的性质、素数的判定方法。
-线性同余方程：线性同余方程的解法、同余方程的应用。
以上仅是《离散数学》中的部分重要知识点总结，该教材还包括很多其他内容，如排列组合、概率论、布尔代数等等。
期末复习时，建议从教材中选取一些重点章节进行深入学习和复习，同时要进行大量的习题训练，加深对知识点的理解和掌握。
祝你在期末考试中取得好成绩！。
离散数学复习资料离散数学复习资料第1章命题逻辑本章重点：命题与联结词，公式与解释，真值表，公式的类型及判定, (主)析取(合取)范式，命题逻辑的推理理论.一、重点内容1. 命题命题表述为具有确定真假意义的陈述句。
命题必须具备二个条件：其一，语句是陈述句；其二，语句有唯一确定的真假意义.2. 六个联结词及真值表h“”否定联结词，P是命题，P是P的否命题，是由联结词和命题P组成的复合命题.P取真值1，P取真值0，P取真值0，P取真值1. 它是一元联结词.h “”合取联结词，P Q是命题P，Q的合取式，是“”和P，Q 组成的复合命题. “”在语句中相当于“不但…而且…”，“既…又…”. P Q取值1，当且仅当P，Q均取1；P Q取值为0，只有P，Q之一取0.h “”析取联结词，“”不可兼析取(异或)联结词， P Q是命题P，Q的析取式，是“”和P，Q组成的复合命题. P Q是联结词“”和P，Q组成的复合命题. 联结词“”或“”在一个语句中都表示“或”的含义，前者表示相容或，后者表示排斥或不相容的或. 即“P Q”“(P Q)(P Q)”. P Q取值1，只要P，Q之一取值1，P Q取值0，只有P，Q都取值0.h “”蕴含联结词， P Q是“”和P，Q组成的复合命题，只有P 取值为1，Q取值为0时，P Q取值为0；其余各种情况，均有P Q的真值为1，亦即10的真值为0，01，11，00的真值均为1. 在语句中，“如果P则Q”或“只有Q，才P，”表示为“P Q”.h “” 等价联结词，P Q是P，Q的等价式，是“”和P，Q组成的复合命题. “”在语句中相当于“…当且仅当…”，P Q取值1当且仅当P，Q真值相同.3. 命题公式、赋值与解释，命题公式的分类与判别h命题公式与赋值，命题P含有n个命题变项P1，P2,…,P n，给P1，P2,…,P n各指定一个真值，称为对P的一个赋值(真值指派). 若指定的一组值使P的真值为1，则这组值为P的真指派；若使P的真值为0，则称这组值称为P的假指派.h命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式；判定命题公式类型的方法：其一是真值表法，任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式.其二是推导演算法. 利用基本等值式(教材的十六个等值式或演算律)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式.既非永真，也非用假，成为非永真的可满足式.其三主析取(合取)范式法，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式.h等值式A B，命题公式A，B在任何赋值下，它们的真值均相同，称A，B等值。
定理1 设(A)是含命题公式A 的命题，(B)是用命题公式B 置换(A)中的A 之后得到的命题公式. 如果A B ，则(A)(B).4. 范式h 析取(合取)范式，仅有有限个简单合取式(析取式)构成的析取式(合取式)，就是析取(合取)范式.h 极小项(极大项)，n 个命题变项P 1,P 2,…,P n ，每个变项或它的否定两者只有其一出现且仅出现一次，第i 个命题变项或者其否定出现在从左起第i 个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项).以两个命题变项为例，m 00=P Q ，m 01=P Q,m 10=P Q,m 11=P Q 是极小项;M 00=P Q ，M 01=P Q,M 10=P Q,M 11=P Q 是极大项.h 主析取范式(主合取范式) 含有n 个命题变项的命题公式，如果与一个仅有极小项(极大项)的析取(合取)构成的析取(合取)范式等值，则该等值式称为原命题公式的主析取(合取)范式。
每项含有n 个命题变项(变项字母齐全)的合取式(析取式)的析取(合取)为主析取(合取)范式.任意命题公式都存在与之等值的范式，存在与之等值的主范式，且是惟一的.求范式，包括求析取范式、合取范式、主析取范式和主合取范式. 关键有两点：其一是准确掌握范式定义；其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律.求析取(合取)范式的步骤：① 将公式中的联结词都化成，，(即消去个数中的联结词，，)；② 将否定联结词消去或移到各命题变项之前；③ 利用分配律、结合律等，将公式化为析取(合取)范式.求命题公式A 的主析取(合取)范式的步骤：① 求公式A 的析取(合取)范式；② “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如P P(P P)用0(1)替代. 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如P P(P P)用P 替代，m i m i (Mi M i )用m i (M i )替代.③ 若析取(合取)范式的某个合取项(析取项)B 不含有命题变项P i 或P i ，则添加P i P i (P i P i )，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；④ 将极小(极大)项按由小到大的顺序排列，用()表示.5. 命题演算的推理理论h 设A 1,A 2,…,A n ,C 是命题公式，如果C A A A n →∧∧∧Λ21是重言式，称C 是前提集合{ A 1,A 2,…,A n }的有效结论或{A 1,A 2,…,A n }逻辑地推出C 。
记作C A A A n ?∧∧∧Λ21 掌握演绎或形式证明. 要理解并掌握14个重言蕴含式(即I 1～I 14)，17个等值式(E 1～E 17)；二是会使用三个规则(P 规则、T 规则和CP 规则)。
推理方法有：真值表法；等值演算法；主析取范式法，构造证明法(直接证明法、附加前提证明法和间接证明法)第2章谓词逻辑本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明.一、重点内容1. 谓词与量词h 谓词，在谓词逻辑中，原子命题分解成个体词和谓词. 个体词是可以独立存在的客体，它可以是具体事物或抽象的概念。
谓词是用来刻划个体词的性质或事物之间关系的词. 个体词分个体常项(用a,b,c,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表示具体性质和关系)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,…表示. 注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题.h 量词，是在命题中表示数量的词，量词有两类：全称量词，表示“所有的”或“每一个”；存在量词，表示“存在某个”或“至少有一个”.在谓词逻辑中，使用量词应注意以下几点：(1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变.(2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全总个体域.(3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的含义. 谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题. 所谓解释就是使公式中的每一个变项都有个体域中的元素相对应.在谓词逻辑中，命题符号化必须明确个体域，无特别说明认为是全总个体域。
一般地，使用全称量词，特性谓词后用；使用存在量词，特性谓词后用.2. 公式与解释h 谓词公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材). 命题的符号化结果都是谓词公式.例如x(F(x)G(x))，x(F(x)G(x))，x y(F(x)F(y)L(x,y)H(x,y))等都是谓词公式.h 变元与辖域，在谓词公式xA 和xA 中，x 是指导变元，A 是相应量词的辖域. 在x 和x 的辖域A 中，x 的所有出现都是约束出现，即x 是约束变元，不是约束出现的变元，就是自由变元. 也就是说，量词后面的式子是辖域. 量词只对辖域内的同一变元有效. h 换名规则，就是把公式中量词的指导变元及其辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变.h 代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的这个符号.h 解释(赋值)，谓词公式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 ∨∨∨??∧∧∧?? h 谓词公式分类，在任何解释下，谓词公式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 移至整个公式最左边；⑤ 得到公式的前束范式.4.谓词逻辑的推理理论谓词演算的推理是命题演算推理的推广和扩充，命题演算中的基本等值公式，重言蕴含式以及P ，T ，CP 规则在谓词演算中仍然使用. 在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，引入消去和附加量词的规则，有US 规则(全称量词消去规则)，UG 规则(全称量词附加规则)，ES 规则(存在量词消去规则)，EG 规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行.第3章集合与关系本章重点：集合概念，集合的运算，集合恒等式的证明，笛卡儿积.一、重点内容1. 集合的概念h 集合与元素，具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.集合A 中元素的个数为集合的元数A .h 集合的表示方法：列举法和描述法.列举集合的元素，元素不能重复出现，集合中的元素无顺序之分. 集合与其元素之间存在属于“”或不属于“”关系.2. 集合的关系：包含，子集，集合相等.h 包含(子集)，若B a A a ∈?∈?，则B 包含A(或A 包含于B)，称A 是B 的子集，记B A ?，又A B ，则A 是B 的真子集，记A B.h 集合相等，若A B ，B A ，则A ＝B.注意：元素与集合,集合与子集，子集与幂集，与()，空集与所有集合等的关系.3. 特殊集合：全集、空集和幂集.h 全集合E ，在一个具体问题中，所涉及的集合都是某个集合的子集，该集合为全集. h 空集，不含任何元素的集合为空集. 空集是惟一的，它是任何集合的子集.h 集合A 的幂集P(A)，有集合A 的所有子集构成的集合 P(A)=}{A x x ?. 若A ＝n, 则P(A)=2n .4. 集合的运算h 集合A 和B 的并A B ，由集合A 和B 的所有元素组成的集合.h 集合A 和B 的交A B ，由集合A 和B 的公共元素组成的集合.h 集合A 的补集A ，属于E 但不属于集合A 的元素组成的集合，A. 补集总相对于一个全集.h 集合A 与B 的差集A －B ，由属于A ，而不属于B 的所有元素组成的集合..h 集合A 与B 的对称差A B ，A B ＝(A －B)(B －A)或A B ＝）A B 〕－（A B ）应该很好地掌握10条运算律(运算的性质)(教材P71～72)，即交换律、结合律、分配律、幂等律、同一律、零律、补余律、吸收律、摩根律和双补律等.5. 恒等式证明集合运算部分有三个方面的问题：其一是进行集合的运算；其二是集合运算式的化简；其三是集合恒等式的推理证明.集合恒等式的证明方法通常有二：(1)要证明A ＝B ，只需要证明A B ，又A B ；(2)通过运算律进行等式推导.6. 有序对与笛卡儿积h 有序对，就是有顺序的数组，如，x,y 的位置是确定的，不能随意放置.注意：有序对，以a,b 为元素的集合{a,b}={b,a}；有序对(a,a)有意义，而集合{a,a}是单元素集合，应记作{a}.h 笛卡儿积，把集合A ，B 合成集合A ×B ，规定A ×B ＝{x A y B}由于有序对中x,y 的位置是确定的，因此A ×B 的记法也是确定的，不能写成B ×A.笛卡儿积也可以多个集合合成，A 1×A 2×…×A n .笛卡儿积的运算性质. 一般不能交换.第4章二元关系与函数本章重点：关系概念与其性质，等价关系和偏序关系，函数.一、重点内容1. 关系的概念包括定义、关系的表示方法：集合表示、矩阵表示、图形表示.h 二元关系，是一个有序对集合，设集合A,B ，},{B y A x y x R ∈∧∈><=，记作xRy二元关系的定义域：Dom(R)A ?；二元关系的值域：Ran(R)B ?h 关系的表示方法：集合表示法：关系是集合，有类似于集合的表示方法.列举法，如R ＝{<1,1>,<1,2>}；描述法：如},{B y A x y x R ∈∧∈><=关系矩阵：R A ×B ，R 的矩阵???? ??==?????/==?n j m i b R a Rb a r r M j i j i ij n m ij R ,...,2,1,...,2,101,)(关系图：R 是集合上的二元关系，若<a i="" ,b="" j="" bdsfid="240">R ，由结点a I 画有向弧到b j 构成的图形.。
