《离散数学期末复习纲要》由会员分享，可在线阅读，更多相关《离散数学期末复习纲要（166页珍藏版）》请在金锄头文库上搜索。
1、（1）需要熟练掌握的知识点包括：命题 的定义、逻辑联结词、命题变元、命题 公式（合式公式）、永真式、永假式、 可满足式、等价式、蕴涵式、极小项、 极大项、主析取范式、主合取范式。第1章命题逻辑重点（2）掌握基本的等价式和蕴涵式，并掌 握常用的等价式和蕴涵式的证明方法（ 替换规则和推论规则）。第1章命题逻辑重点（续）（3）要能准确地求出命题公式的主析取范 式和主合取范式。掌握主析取范式和主合取 范式与真值表的对应关系，主析取范式和主 合取范式的关系。第1章命题逻辑重点（续）（4）掌握命题符号化的原则；（5）熟练掌握四个推论规则（P、T、CP、 F）进行有效性论证。第1章命题逻辑重点（续）证明等价
2、式:P41#8(1)(1)P(QP)P(PQ) 左式P(QP) T 右式P(PQ) P(PQ) T 所以： P(QP)P(PQ)P41#8(5) (5)(PQAC)(A PQC) (A(PQ)C 左式 (PQAC)(APQC ) (PQA)(APQ)C (A(PQ)(PQ)C (A(PQ)(PQ)C (A(PQ)(PQ)C (A(PQ)C (A(PQ)C 右式P41#11(2) 将下列公式用只含和的等价式表示: (2)(P (Q R) P Q ( P (Q R) P Q( P Q R) P Q ( P Q R) P Q)求命题公式的主范式P42#17(1)(PQ)(PQ) (PQ)(PQ)(P
3、Q) (PQ)(PQ)(PQ)011011(m1,m2,m3) (M0)PQ求命题公式的主范式P42#17(6)(PQR)(PQR) (P(QR)(P(QR) (PQ)(PR)(PQ)(PR) (PQ)(RR)(PR) (QQ) (PQ) (RR)(PR)(QQ) (PQR)(PQR)(PQR) (PQR) (PQR)(PQR) (PQR)(PQ R) (M1 , M2 , M3 , M4 , M5 , M6)(m0,m7) (PQR)(PQR)CP规则的使用P42#22(3)(PQ)R(PQ)RnPQ P规则（附加前提）nPT规则(1)nQ T规则(1)nPQT规则(2)(3)n(PQ)R
4、P规则nRT规则(4)(5)n(PQ)RCP规则(1)(6)F规则的使用P43#23(2)SQ,RS, R, P Q P nPP规则（假设前提）nP QP规则nQT规则（1）（2）nSQP规则nST规则（3）（4）nRSP规则nRT规则（5）（6）nRP规则nR RT规则（1）（8）矛盾式nPF规则（1）（9）符号化并验证结论的有效 P43#25(1)1）如果6是偶数，则2不能整除7； 2）或者5不是素数，或者2整除7； 3）5是素数；结论：因此6是奇数。符号化P:6是偶数; Q:2能整除7; R: 5是素数;如果6是偶数，则2不能整除7:PQ或者5不是素数，或者2整除7:RQ5是素数:R 6
5、是奇数:P证明nRP规则nRQP规则nQT规则(1)(2)nPQP规则nPT规则(3)(4)PQRQRPP43#25(6) 符号化: P:今天是星期二; Q:我们有离散数学测验; R:我们有高等数学测验; S:高等数学老师生病;PQ RSRPSQP43#25(6)(续)PQ RSRPSQ (1) PS(P规则 )(2) P(T规则 (1)(3) S(T规则(1) (4) SR (P规则) (5) R (T规则 (3)(4)(6) PQ R (P规则) (7) Q R (T规则 (2)(6)(8) Q (T规则 (5)(7)第2章 谓词逻辑重点（1）需要熟练掌握的知识点包括：谓词 、全称量词(x
6、)、存在量词 (x) 、个 体、个体域、个体变元（约束变元和自 由变元）、谓词公式的解释（永真、永 假、可满足）、谓词公式的基本的等价 式和蕴涵式。第2章 谓词逻辑重点（续）（2）在符号化时要特别注意量词和逻辑 联结词的搭配：全称量词对应逻辑联结 词“”，存在量词对应逻辑联结词“” 。 （3）在谓词逻辑推理的证明中，要特别 注意US，ES，UG，EG规则成立的条件 （用ES规则指定的个体不能用UG规则加 以推广）。符号化并证明结论的有效性P64#18(1)1）所有有理数是实数； 2）某些有理数是整数； 结论：某些实数是整数。 符号化特性谓词:Q(x):x是有理数； I(x):x是整数；R(x)
7、:x是实数；(x) ( )所有有理数是实数：(x) ( )Q(x)R(x)某些有理数是整数:(x) ( )Q(x)I(x)某些实数是整数:R(x)I(x)证明(x)(Q(x)R(x), (x)(Q(x)I(x) (x)(R(x)I(x) (1) (x)(Q(x)I(x)P规则 (2) Q(a)I(a)ES规则 (3) Q(a)T规则（2） (4) I(a) T规则（2） (5) (x)(Q(x)R(x) P规则 (6) Q(a)R(a) US规则 (5) (7) R(a) T规则（3） (6) (8) R(a) I(a) T规则（ 4）(7) (9) (x)(R(x)I(x) UG规则(8)首
8、先使用含 有存在量词 的前提符号化并证明结论的有效性 P64#18(2)任何人如果他喜欢步行，他就不 喜欢乘车。每个人或者喜欢乘车或 者喜欢骑自行车；有的人不爱骑自 行车，因而有的人不爱步行。符号化特性谓词: P(x):x是人； W(x):x喜欢步行; T(x):x喜欢乘车;B(x):x喜欢骑自行车 任何人如果他喜欢步行，他就不喜欢乘车 :(x)( )P(x)(W(x)T(x)(x)( )(P(x)W(x)T(x) 每个人或者喜欢乘车或者喜欢骑自行车: (x)( )P(x)(T(x)R(x)符号化(续) 有的人不爱骑自行车:(x) ( ) P(x)R(x)有的人不爱步行:(x) ( ) P(x
9、)W(x)证明(x)(P(x)(W(x)T(x),(x)(P(x)(T(x)R(x), (x) (P(x)R(x) (x) (P(x)W(x) n(x) (P(x)R(x)P规则nP(a)R(a)ES规则nP(a)T规则(2)nR(a)T规则(2)n(x)(P(x)(T(x)R(x)P规则nP(a)(T(a)R(a)US规则(5)nT(a)R(a)T规则(3)(6)nT(a)T规则(4)(7)n(x)(P(x)(W(x)T(x)P规则nP(a)(W(a)T(a)US规则(9)nW(a)T(a)T规则(3)(10)nW(a)T规则(8)(11)nP(a) W(a)T规则(3)(12)n(x) (
10、P(x)W(x)EG规则(13)首先使用含 有存在量词 的前提符号化并证明结论的有效性 P64#18(3)任何人违反交通规则，都要被罚 款，因此，如果没有罚款，则没有 人违反交通规则。符号化特性谓词: M(x):x是人；P(x):x违反交通规则；Q(x):x被罚款。任何人违反交通规则，都要被罚款： (x)( )M(x)(P(x)Q(x)(x)( )(M(x)P(x)Q(x)如果没有罚款，则没有人违反交通规则：(x)Q(x)(x)(M(x)P(x)证明(x)(M(x)(P(x)Q(x) (x)Q(x)(x)(M(x)P(x)n(x)Q(x)P规则（附加前提）n(x)Q(x)T规则(1)nQ(a)
11、US规则(2)n(x)(M(x)(P(x)Q(x)P规则 nM(a)(P(a)Q(a)US规则(4)nM(a)P(a)Q(a)T规则(5)nM(a)P(a)T规则(3)(6)n(M(a)P(a)T规则(7)n(x) (M(a)P(a)UG规则(8)n(x)(M(x)P(x)T规则(9)n(x)Q(x)(x)(M(x)P(x)CP规则(1)(10)第三章 集合(1)掌握集合的基本概念及其表示，集合之间的 关系（子集 、真子集 ）、元素与集合的 关系（属于 ）、全集、空集、幂集、笛卡尔 乘积等概念。 (2)能熟练地证明集合中的相等关系、包含关系 。 (3)掌握集合的五种基本运算： A、A B、A
12、B、A-B、A B 及集合运算的基本定律。P84#4A=1 B=1 C=1 满足：A B,B C,但是A CP84#5(1)T (2)F :A=1,B=1,C=1,2 (3)F: A=1,B=1,2,C=1,2,3 (4)F:A=1,B=1,2,C=1,2,3P84#6是。 AB=AC B-A=C-A B=(AB)(B-A) = (AC)(C-A) =CP84#8(1)否：A=1,2,B=1,C=2 (2)否:A=1,B=1,2,C=1,2,3 (3)是: AB=AC A(AB)=A(AC) (AA)B=(AA)C B=C B=CP85#11证明：对任意的xAxBxA xCxAC (AC BC
13、) xBCxB xC xC xAC(ACBC) xBC xB P85#12(1)必要性：已知CA，证明 (AB)C=A(BC) 左式(AB)C = (CB) (AC) ( CA) =A(BC)=右式P85#12（续）(2)充分性：已知(AB)C=A(BC)证明CA 对任意的xC x (AB)C x A(BC) (AB)C=A(BC) x A CAP85#17(1)A-(B C) =A (B C) = A B C =(A B) (A C) =(A-B) (A-C)第四章二元关系(1)掌握关系矩阵和关系图的表示方法。 (2)掌握合成运算、逆运算、闭包运算的概 念。 (3)熟练掌握关系的性质（自反性、反自反 性、对称性、反对称性、可传递性）及 其判别方法。第四章二元关系（续）(4)掌握等价关系（自反、对称、可传递） 和偏序关系（自反、反对称、可传递） 的概念及证明。 (5)掌握等价关系和划分之间的相互关系。 (6)掌握偏序关系和哈斯图，并会求极大（ 小）元、最大（小）元、上（下）界、 上（下）确界。P125#10(2)对任意的RSRSRS (R、S是对称 的) RS RS是对称的P125#12(1)对任意的R1
