信本《离散数学(第四版)》复习纲要【DOC精选】.doc

10信本《离散数学》复习纲要 卷子结构 选择题 10题，每题2分，共20分 填空题 5题，每题3分，共15分 计算题 4题，共40分 证明题 3题，共25分 考试内容 1.1-1.3；1.5-1.6，即1.4不要求 2.1-2.3 3.1-3.2，即3.3不要求 4.1-4.5，即4.6-4.7不要求 5.1-5.3 6.1-6.3 7.1-7.3，即7.4不要求 8.1-8.3，即8.4不要求 9.1-9.2 （其余章节均不要求） 复习要点 第1章 命题逻辑 1、理解命题概念，会判别语句是不是命题。理解五个联结词：否定联结词(p、析取联结词(、合取联结词(、蕴涵联结词(、和等价联结词(及其真值表，会将简单命题符号化。 能判断真假的陈述句称为命题。 命题必须具备：其一，语句是陈述句；其二，语句有唯一确定的真假意义。 2、了解公式的概念(公式、赋值、成真赋值和成假赋值)和公式真值表的构造方法。能熟练地作公式真值表。理解永真式和永假式概念，掌握其判别方法。 判定命题公式类型的方法：其一是真值表法，其二是等价演算法。 3、了解公式等价概念，掌握公式的重要等价式和判断两个公式是否等价的有效方法：等价演算法、列真值表法和主范式方法。 4、理解析取范式和合取范式、极大项和极小项、主析取范式和主合取范式的概念，熟练掌握它们的求法。 命题公式的范式不唯一，但主范式是唯一的。 命题公式A有n个命题变元，A的主析取范式有k个极小项，有m个极大项，则 于是有 (1) A是永真式(k=2n(m=0)；(2) A是永假式(m＝2n(k=0)； 5、了解C是前提集合{A1,A2,…,Am}的有效结论或由A1, A2, …, Am 逻辑地推出C的概念。要理解并掌握推理理论的规则、重言蕴含式和等价式，掌握命题公式的证明方法：真值表法、直接证法、间接证法。 重点：命题与联结词，公式与解释，真值表，公式的类型及判定，主析取(合取)范式，命题演算的推理理论。 第2章 谓词逻辑 1、理解谓词、量词、个体词、个体域，会将简单命题符号化。 原子命题分成个体词和谓词，个体词可以是具体事物或抽象的概念，分个体常项和个体变项。谓词用来刻划个体词的性质或之间的关系。 量词分全称量词(，存在量词(。 命题符号化注意：使用全称量词(，特性谓词后用(；使用存在量词(，特性谓词后用(。 2、了解原子公式、谓词公式、变元(约束变元和自由变元)与辖域等概念。掌握在有限个体域下消去公式的量词和求公式在给定解释下真值的方法。 由原子公式、联结词和量词构成谓词公式。谓词公式具有真值时，才是命题。 在谓词公式(xA或(xA中，x是指导变元，A是量词的辖域。会区分约束变元和自由变元。 在非空集合D(个体域)上谓词公式A的一个解释或赋值有3个条件。 在任何解释下，谓词公式A取真值1，A为逻辑有效式(永真式)；公式A取真值0，A为永假式；至少有一个解释使公式A取真值1，A称为可满足式。 在有限个体域下，消除量词的规则为：设D＝{a1, a2, …, an}，则 会求谓词公式的真值，量词的辖域，自由变元、约束变元，以及换名规则、代入规则等。 掌握谓词演算的等价式和重言蕴含式。并进行谓词公式的等价演算。 3、了解前束范式的概念，会求公式的前束范式的方法。 若一个谓词公式F等价地转化成 ，那么就是F的前束范式，其中Q1，Q2，…，Qk只能是(或(，而x1, x2, …, xk是个体变元，B是不含量词的谓词公式。前束范式仍然是谓词公式。 重点：谓词与量词，公式与解释，一阶逻辑等值式。 第3章 集合及其运算 1、理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法。 具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.。 集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分。 掌握集合包含(子集)、真子集、集合相等等概念。 注意：元素与集合，集合与子集，子集与幂集，(与(((),空集(与所有集合等的关系. 空集(，是惟一的，它是任何集合的子集。 集合A的幂集P(A)＝， A的所有子集构成的集合。若(A(＝n，则(P(A)(=2n。 2、熟练掌握集合A和B的并A(B，交A(B，补集(A((A补集总相对于一个全集).差集A－B，对称差(，A(B＝(A－B)((B－A)，或A(B＝(A(B)－（A(B）等运算。 掌握集合运算律(见教材第61～62页)(运算的性质). 3、掌握用集合运算基本规律证明集合恒等式的方法。 集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明。 证明方法有二：(1)要证明A＝B，只需证明A(B，又A(