离散考试复习提纲_Review2011

1、1大概的考试题型大概的考试题型选择题选择题 2*10=20填空题填空题 2*15=30 计算（简答）题计算（简答）题 10*2=20应用题应用题 10*1=10证明题证明题 10*2=202大概的考试题型大概的考试题型数理逻辑数理逻辑(第第15章章) 45分左右分左右集合论集合论(第第68章章) 55分左右分左右 第一章第一章主要内容主要内容l 命题、真值、简单命题与复合命题、命题符号化命题、真值、简单命题与复合命题、命题符号化l 联结词联结词 , , , , 及复合命题符号化及复合命题符号化l 命题公式及层次命题公式及层次l 公式的类型公式的类型l 真值表及应用真值表及应用l 基本要求基本要

2、求l 深刻理解各联结词的逻辑关系深刻理解各联结词的逻辑关系, 熟练地将命题符号化熟练地将命题符号化l 会求复合命题的真值会求复合命题的真值l 深刻理解合式公式及重言式、矛盾式、可满足式等概念深刻理解合式公式及重言式、矛盾式、可满足式等概念l 熟练地求公式的真值表，并用它求公式的成真赋值与成假熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型赋值及判断公式类型第二章第二章 命题逻辑等值演算命题逻辑等值演算主要内容主要内容l等值式与等值演算等值式与等值演算l基本等值式（基本等值式（1616组，组，2424个公式）个公式）l主析取范式与主合取范式主析取范式与主合取范式l联结词完备集

3、联结词完备集l消解法消解法基本要求基本要求l 深刻理解等值式的概念深刻理解等值式的概念l 牢记基本等值式的名称及它们的内容牢记基本等值式的名称及它们的内容l 熟练地应用基本等值式及置换规则进行等值演算熟练地应用基本等值式及置换规则进行等值演算l 理解文字、简单析取式、简单合取式、析取范式、合取范理解文字、简单析取式、简单合取式、析取范式、合取范式的概念式的概念l 深刻理解极小项、极大项的概念、名称及下角标与成真、深刻理解极小项、极大项的概念、名称及下角标与成真、成假赋值的关系，并理解简单析取式与极小项的关系成假赋值的关系，并理解简单析取式与极小项的关系l 熟练掌握求主范式的方法（等值演算、真值

4、表等）熟练掌握求主范式的方法（等值演算、真值表等）l 会用主范式求公式的成真赋值、成假赋值、判断公式的类会用主范式求公式的成真赋值、成假赋值、判断公式的类型、判断两个公式是否等值型、判断两个公式是否等值l 会将公式等值地化成指定联结词完备集中的公式会将公式等值地化成指定联结词完备集中的公式l 会用命题逻辑的概念及运算解决简单的应用问题会用命题逻辑的概念及运算解决简单的应用问题l 掌握消解规则及其性质掌握消解规则及其性质l 会用消解算法判断公式的可满足性会用消解算法判断公式的可满足性第三章第三章 命题逻辑推理理论命题逻辑推理理论主要内容主要内容l 推理的形式结构推理的形式结构l 判断推理是否正确

5、的方法判断推理是否正确的方法真值表法 等值演算法主析取范式法l 推理定律推理定律l 自然推理系统自然推理系统Pl 构造推理证明的方法构造推理证明的方法直接证明法附加前提证明法归谬法(反证法)基本要求基本要求l 理解并记住推理形式结构的两种形式：理解并记住推理形式结构的两种形式： 1. (A1 A2 Ak)B 2. 前提：前提：A1, A2, , Ak 结论：结论：Bl 熟练掌握判断推理是否正确的不同方法（如真值表法、等熟练掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）值演算法、主析取范式法等）l 牢记牢记 P 系统中各条推理规则系统中各条推理规则l 熟练掌握构造证明的

6、直接证明法、附加前提证明法和归谬熟练掌握构造证明的直接证明法、附加前提证明法和归谬 法法l 会解决实际中的简单推理问题会解决实际中的简单推理问题第四章第四章 一阶逻辑基本概念一阶逻辑基本概念主要内容主要内容l 个体词、谓词、量词个体词、谓词、量词l 一阶逻辑命题符号化一阶逻辑命题符号化l 一阶语言一阶语言L 项、原子公式、项、原子公式、合式公式合式公式l 公式的解释公式的解释 量词的辖域、指导变元、个体变项的自由出现与约束出量词的辖域、指导变元、个体变项的自由出现与约束出现、闭式、解释现、闭式、解释l 公式的类型公式的类型 永真式永真式(逻辑有效式逻辑有效式)、矛盾式、矛盾式(永假式永假式)、

7、可满足式、可满足式基本要求基本要求l 准确地将给定命题符号化准确地将给定命题符号化l 理解一阶语言的概念理解一阶语言的概念l 深刻理解一阶语言的解释深刻理解一阶语言的解释l 熟练地给出公式的解释熟练地给出公式的解释l 记住闭式的性质并能应用它记住闭式的性质并能应用它l 深刻理解永真式、矛盾式、可满足式的概念深刻理解永真式、矛盾式、可满足式的概念, 会会判断简单公式的类型判断简单公式的类型第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理主要内容主要内容l 一阶逻辑等值式一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则基本等值式，置换规则、换名规则、代替规则l 前束范式前束范式l

8、 推理的形式结构推理的形式结构l 自然推理系统自然推理系统NL 推理定律、推理规则推理定律、推理规则基本要求基本要求l 深刻理解并牢记一阶逻辑中的重要等值式深刻理解并牢记一阶逻辑中的重要等值式, 并能并能准确而熟练地应用它们准确而熟练地应用它们l 熟练正确地使用置换规则、换名规则、代替规则熟练正确地使用置换规则、换名规则、代替规则l 熟练地求出给定公式的前束范式熟练地求出给定公式的前束范式l 深刻理解自然推理系统深刻理解自然推理系统NL 的定义，牢记的定义，牢记NL 中的中的各条推理规则，特别是注意使用各条推理规则，特别是注意使用UI、UG、EI、EG 4条推理规则的条件条推理规则的条件（注意

9、看教学课件）（注意看教学课件）l 能正确地给出有效推理的证明能正确地给出有效推理的证明 全称量词消去规则全称量词消去规则(简记为简记为UI规则或规则或UI)含义含义：如果个体域的所有元素都具有性质：如果个体域的所有元素都具有性质A，则个体域中的任，则个体域中的任一元素具有性质一元素具有性质A。 两式成立的条件两式成立的条件： (1)在第一式中，取代在第一式中，取代x的的y应为任意的应为任意的不不在在A(x)中中约束出现约束出现的的个体变项。个体变项。 (2)在第二式中，在第二式中，c为任意个体变项。为任意个体变项。 (3)用用y或或c去取代去取代A(x)中自由出现的中自由出现的x时，一定要在时

10、，一定要在x自由出现自由出现的一切地方进行取代。的一切地方进行取代。 A A( (c c) )x xA A( (x x) )或或A A( (y y) )x xA A( (x x) )全称量词引入规则全称量词引入规则(简记为简记为UG规则或规则或UG)该式成立的条件是：该式成立的条件是： (1)无论无论A(y)中自由出现的个体变项中自由出现的个体变项y取何值，取何值，A(y)应该均为真。应该均为真。 (2)取代自由出现的取代自由出现的y的的x也不能在也不能在A(y)中约束出现。中约束出现。 x xA A( (x x) )A A( (y y) )存在量词引入规则存在量词引入规则(简称简称EG规则或

11、规则或EG) 该式成立的条件是：该式成立的条件是： (1)c是特定的个体常项。是特定的个体常项。(2)取代取代c的的x不能在不能在A(c)中出现过。中出现过。 x xA A( (x x) )A A( (c c) )存在量词消去规则存在量词消去规则(简记为简记为EI规则或规则或EI) 该式成立的条件是：该式成立的条件是： (1)c是使是使A为真的特定的个体常项。为真的特定的个体常项。 (2)c不在不在A(x)中出现。中出现。 (3)若若A(x)中除自由出现的中除自由出现的x外，还有其它自由外，还有其它自由出现的个体变项，此规则不能使用。出现的个体变项，此规则不能使用。 A A( (c c) )x

12、 xA A( (x x) )第六章第六章 集合代数集合代数主要内容主要内容l 集合的两种表示法集合的两种表示法l 集合与元素之间的隶属关系、集合之间的包含关系的区集合与元素之间的隶属关系、集合之间的包含关系的区别与联系别与联系l 特殊集合：空集、全集、幂集特殊集合：空集、全集、幂集l 文氏图及有穷集合的计数文氏图及有穷集合的计数l 集合的集合的 , , , , 等运算以及广义等运算以及广义 , 运算运算l 集合运算的算律及其应用集合运算的算律及其应用基本要求基本要求l 熟练掌握集合的两种表示法熟练掌握集合的两种表示法l 能够判别元素是否属于给定的集合能够判别元素是否属于给定的集合l 能够判别两

13、个集合之间是否存在包含、相等、真包含等关能够判别两个集合之间是否存在包含、相等、真包含等关系系l 熟练掌握集合的基本运算（普通运算和广义运算）熟练掌握集合的基本运算（普通运算和广义运算）l 掌握证明集合等式或者包含关系的基本方法掌握证明集合等式或者包含关系的基本方法第七章第七章 二元关系二元关系 主要内容主要内容l 有序对与笛卡儿积的定义与性质有序对与笛卡儿积的定义与性质l 二元关系、从二元关系、从A到到B的关系、的关系、A上的关系上的关系l 关系的表示法：关系表达式、关系矩阵、关系图关系的表示法：关系表达式、关系矩阵、关系图l 关系的运算：定义域、值域、域、逆、合成、限制、像、关系的运算：定

14、义域、值域、域、逆、合成、限制、像、幂幂l 关系运算的性质关系运算的性质: A上关系的自反、反自反、对称、反对上关系的自反、反自反、对称、反对称、传递的性质称、传递的性质l A上关系的自反、对称、传递闭包上关系的自反、对称、传递闭包l A上的等价关系、等价类、商集与上的等价关系、等价类、商集与A的划分的划分l A上的偏序关系与偏序集上的偏序关系与偏序集基本要求基本要求l 熟练掌握关系的三种表示法熟练掌握关系的三种表示法 l 能够判定关系的性质（等价关系或偏序关系）能够判定关系的性质（等价关系或偏序关系）l 掌握含有关系运算的集合等式掌握含有关系运算的集合等式l 掌握等价关系、等价类、商集、划分

15、、哈斯图、偏序集等掌握等价关系、等价类、商集、划分、哈斯图、偏序集等概念概念l 计算计算A B, dom R, ranR, fldR, R 1, R S , Rn , r(R), s(R), t(R)l 求等价类和商集求等价类和商集A/Rl 给定给定A的划分的划分 ，求出，求出 所对应的等价关系所对应的等价关系l 求偏序集中的极大元、极小元、最大元、最小元、上界、求偏序集中的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界下界、上确界、下确界l 掌握基本的证明方法掌握基本的证明方法 证明涉及关系运算的集合等式证明涉及关系运算的集合等式 证明关系的性质、证明关系是等价关系或偏序关系证明

16、关系的性质、证明关系是等价关系或偏序关系第八章第八章 习题课习题课主要内容主要内容l 函数，函数，从从A到到B的函数的函数 f:AB，BA，函数的像与完全原像，函数的像与完全原像l 函数的性质：单射、满射、双射函数函数的性质：单射、满射、双射函数l 重要函数：恒等函数、常函数、单调函数、集合的特征函重要函数：恒等函数、常函数、单调函数、集合的特征函 数、自然映射数、自然映射l 集合等势的定义与性质集合等势的定义与性质l 集合优势的定义与性质集合优势的定义与性质l 重要的集合等势以及优势的结果重要的集合等势以及优势的结果l 可数集与不可数集可数集与不可数集l 集合基数的定义集合基数的定义基本要求基本要求l 给定给定 f, A, B, 判别判别 f 是否为从是否为从A到到B的函数的函数l 判别函数判