离散数学与期末复习纲要 .ppt

第1章命题逻辑重点 （1）需要熟练掌握的知识点包括：命题的定义、逻辑联结词、命题变元、命题公式（合式公式）、永真式、永假式、可满足式、等价式、蕴涵式、极小项、极大项、主析取范式、主合取范式。 第1章命题逻辑重点（续） （2）掌握基本的等价式和蕴涵式，并掌握常用的等价式和蕴涵式的证明方法（替换规则和推论规则）。 证明等价式:P41#8(1) (1)P→(Q→P)??P→(P→Q) 左式??P∨(?Q∨P) ?T 右式???P∨(?P∨Q) ?P∨(?P∨Q) ?T 所以： P→(Q→P)??P→(P→Q) P41#8(5) (5)(P∧Q∧A→C)∧(A→ P∨Q∨C) ?(A∧(P?Q))→C 左式 ?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ?(?A∨((?P∨?Q)∧(P∨Q)))∨C ?(?A∨?((P∧Q)∨(?P∧?Q)))∨C ??(A∧((P∧Q)∨(?P∧?Q)))∨C ??(A∧(P?Q))∨C ? (A∧(P?Q))→C ?右式 P41#11(2) 求命题公式的主范式P42#17 (1)(?P∨?Q)→(P??Q) ??(?P∨?Q)∨(P∧?Q)∨(?P∧??Q) ? (P∧Q)∨(P∧?Q)∨(?P∧Q) 求命题公式的主范式P42#17 (6)(P→Q∧R))∧(?P→?Q∧?R)) ?(?P∨(Q∧R))∧(??P∨(?Q∧?R)) ?(?P∨Q)∧(?P∨R)∧(P∨?Q)∧(P∨?R) ?((?P∨Q)∨(R∧?R))∧((?P∨R) ∨(Q∧?Q)) ∧((P∨?Q) ∨(R∧?R))∧((P∨?R)∨(Q∧?Q)) ? (?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨Q∨R) ∧(?P∨?Q∨R) ∧(P∨?Q∨R)∧(P∨?Q∨?R) ∧(P∨Q∨?R)∧(P∨?Q ∨?R) ? ∏(M1 , M2 , M3 , M4 , M5 , M6)?∑(m0,m7) ?(?P∧?Q∧?R)∨(P∧Q∧R) CP规则的使用P42#22(3) (P∨Q)→R?(P∧Q)→R P∧Q P规则（附加前提） P T规则(1) Q T规则(1) P∨Q T规则(2)(3) (P∨Q)→R P规则 R T规则(4)(5) (P∧Q)→R CP规则(1)(6) F规则的使用P43#23(2) S→?Q,R∨S, ?R, ?P? Q? P ?P P规则（假设前提） ?P? Q P规则 Q T规则（1）（2） S→?Q P规则 ?S T规则（3）（4） R∨S P规则 R T规则（5）（6） ?R P规则 R∧ ?R T规则（1）（8）矛盾式 P F规则（1）（9） 符号化并验证结论的有效P43#25(1) 1）如果6是偶数，则2不能整除7； 2）或者5不是素数，或者2整除7； 3）5是素数； 结论：因此6是奇数。 符号化 证明 R P规则 ?R∨Q P规则 Q T规则(1)(2) P→?Q P规则 ?P T规则(3)(4) P43#25(6) P43#25(6)(续) 第2章 谓词逻辑重点 （1）需要熟练掌握的知识点包括：谓词、全称量词(?x)、存在量词 (?x) 、个体、个体域、个体变元（约束变元和自由变元）、谓词公式的解释（永真、永假、可满足）、谓词公式的基本的等价式和蕴涵式。 第2章 谓词逻辑重点（续） （2）在符号化时要特别注意量词和逻辑联结词的搭配：全称量词对应逻辑联结词“→”，存在量词对应逻辑联结词“∧”。 （3）在谓词逻辑推理的证明中，要特别注意US，ES，UG，EG规则成立的条件（用ES规则指定的个体不能用UG规则加以推广）。 符号化并证明结论的有效性P64#18(1) 1）所有有理数是实数； 2）某些有理数是整数； 结论：某些实数是整数。 ? 符号化 特性谓词:Q(x):x是有理数； I(x):x是整数；R(x):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) 符号化并证明结论