离散数学复习要点第一章命题逻辑一、典型考查点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，最小联结词组详见P157、等价式详见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。
(12) 双条件式转化律：A↔B⇔(A→B)∧(B→A)⇔(A∧B)∨(⎤A∧⎤B)8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。
④用定义，证A⇒B，即证A→B是永真式。
9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和⎤以外公式中出现的所有联结词；②使用⎤(⎤P)⇔P和德·摩根律，将公式中出现的联结词⎤都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。
10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P⇔P。
(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P⇔P∧（⎤Q∨Q)或P⇔P∨（⎤Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。
注意：主析取范式与主合取范式之间的联系。
例如：(P→Q)∧Q⇔m1∨m3⇔M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。
详见P1611、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。
重点规则（主要蕴含式）：(1) P∧Q⇒P化简(2) P∧Q⇒Q化简(3) P⇒P∨Q附加(4) ⎤P⇒P→Q变形附加(5)Q⇒P→Q变形附加(6) ⎤(P→Q)⇒P变形化简(7) ⎤(P→Q)⎤⇒Q变形化简(8) P，(P→Q)⇒Q假言推理(9) ⎤Q，(P→Q)⎤⇒P拒取式(10) ⎤P，(P∨Q)⇒Q析取三段论(11) (P→Q)，(Q→R)⇒P→R条件三段论(12) (P↔Q)，(Q↔R)⇒P↔R 双条件三段论文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。
详见P21二、强化练习1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗?2.下列式子为重言式的是( )A.P→P∨QB.(┐P∧Q)∧(P∨┐Q)C.┐ (P Q)D.(P∨Q) (P→Q)3．下列为两个命题变元P，Q的小项是（）A．P∧Q∧⎤ P B．⎤ P∨Q C．⎤ P∧Q D．⎤ P∨P∨Q4．下列语句中是真命题的是（）A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的5．设P：我们划船，Q：我们跑步。
命题“我们不能既划船又跑步”符号化为（）A．⎤ P∧⎤ Q B．⎤ P∨⎤ Q C．⎤（P↔Q） D．⎤（⎤ P∨⎤ Q）6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式7．命题公式⎤（P∧Q）→R的成真指派是（）A．000，001，110，B．001，011，101，110，111 C．全体指派D．无8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A ．⎤ P ∧QB ．P ∧⎤ QC ．P →⎤ QD ．P ∨⎤ Q9．下面联结词运算不可交换的是（ ）A ．∧ B ．→ C ．∨ D ．10下列命题公式不是重言式的是（ ）A ．Q →（P ∨Q ）B ．（P ∧Q ）→PC ．⎤（P ∧⎤ Q ）∧（⎤ P ∨Q ）D ．（P →Q ）（⎤ P ∨Q ）11.设命题变元为P ，Q ，R ，则小项m100=________，大项M010=________。
12.置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以________，记为________规则。
13.请用联结词┐，∧表示联结词∨和联结词 ：________，________。
14．两个重言式的析取是________式，一个重言式与一个矛盾式的析取是________式。
15．命题公式（P ∧Q ）→⎤ P 的成真指派为__________，成假指派为__________。
16.用等值演算求(P →Q)→R 的主合取范式。
17.列出(P →(Q ∨R)) (P →Q)的真值表。
19．构造命题公式（（P ∧Q ）→P ）∨R 的真值表。
20．求下列公式的主合取范式和主析取范式：P ∨（⎤ P →（Q ∨（⎤ Q →R ）））21．构造命题公式（R Q Q P ∧→∨）→P ∧⎤ R 的真值表。
22．求下列公式的主析取范式和主合取范式：（P →（Q ∧R ））∧（⎤ P →（⎤ Q →R ））。
23.用推理方法证明：P ∨Q ，P →R ，Q →S├R ∨S 。
24．构造下面推理的证明。
如果小张和小王去看电影，则小李也去看电影。
小赵不去看电影或小张去看电影。
小王去看电影。
所以，当小赵去看电影时，小李也去。
25．构造下面推理的证明。
只要A 曾到过受害者房间并且11点以前没离开，A 就犯了谋杀罪。
A 曾到过受害者房间。
如果在11点以前离开，看门人会看见他。
看门人没有看见他。
所以A 犯了谋杀罪。
离散数学复习要点 第二章谓词逻辑一、典型考查点1、基本概念：个体词、个体域、谓词、特性谓词、辖域，详见P27；前束范式详见P362、谓词符号化 步骤：①正确理解给定命题。
必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。
②把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。
③找出恰当量词。
应注意全称量词(∀x)后跟条件式，存在量词(∃x)后跟合取式。
④用恰当的联结词把给定命题表示出来。
详见P303、谓词公式类型的判定（永真式、永假式、可满足式） 方法：利用论域翻译成自然语言后进行判断。
详见P344、自由变元与约束变元的判定 方法：按定义，关键是要看它在A 中是约束出现，还是自由出现，若与量词的指导变元相同，就是约束出现，不同就是自由出现。
详见P31。
5、等价式 (1)量词否定等价式：(a)⎤(∀x)A ⇔(∃x)⎤A(b)⎤(∃x)A ⇔(∀x)⎤A(2) 量词辖域缩小或扩大等价式(a) (∀x)(A(x)∧B)⇔(∀x)A(x)∧B (b) (∀x)(A(x)∨B)⇔(∀x)A(x)∨B(c) (∀x)(A(x)→B)⇔(∃x)A(x)→B (d) (∀x)(B →A(x))⇔B →(∀x)A(x)(e) (∃x)(A(x)∧B)⇔(∃x)A(x)∧B (f) (∃x)(A(x)∨B)⇔(∃x)A(x)∨B(g) (∃x)(A(x)→B)⇔(∀x)A(x)→B (h) (∃x)(B →A(x))⇔B →(∃x)A(x)。
(3) 量词分配律等价式：(a) (∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x) (b)(∃x)(A(x)∨B(x))⇔(∃x)A(x)∨(∃x)B(x)其中，A(x)，B(x)为有x 自由出现的任何公式。
详见P34356、蕴含式(a)(∀x)A(x)∨(∀x)B(x)⇒(∀x)(A(x)∨B(x))(b) (∃x)(A(x)∧B(x))⇒(∃x)A(x)∧(∃x)B(x)(c) (∀x)(A(x)→B(x))⇒(∀x)A(x)→(∀x)B(x)(d) (∀x)(A(x)→B(x))⇒(∃x)A(x)→(∃x)B(x)其中，A(x)和B(x)为含有x 自由出现的任意公式。
详见P356、前束范式 方法：①把量词全部通过等值演算化到整个谓词公式的前面②把量词前面的┐全部通过德摩根定律化到谓词公式的内部。
详见P367、推理：方法：演绎（常用格式）、反证法、CP 规则即附加前提等。
对于命题逻辑中的所有规则都可用。
特殊规则：(1)量词消去 (简称UI 或US 规则) (∀x)A(x)⇒A(c) (∀x)A(x)⇒A(y) (∃x)A(x)⇒A(c)量词产生规则(简称EG 或UG 规则) A(c)⇒(∃y)A(y) A(x)⇒(∀y)A(y) 详见P38二、强化练习1.下列式子不是谓词合式公式的是( )A.(∀x)(P(x)→(∃x)(Q(x) ∧A(x ，y)))B.(∀x)∧(∃y)∨P(x ，y)C.(∀x)P(x)→R(y)D.(∃x)P(x)∧Q(y ，z)2.设个体域为实数集，特定元素a=0，函数f(x ，y)=x-y ，特定谓词F(x ，y)为x<y ，下列公式真值为真的是( )A.(∀x)(∀y)F(x ，f(f(x ，y)，y))B.(∀x)(∀y)(┐F(f(x ，y)，x))C.(∀x)(∀y)(∀z)(F(x ，y)→F(f(x ，z)，f(y ，z)))D.(∀x)F(f(a ，x)，a)3.对于公式(∀x)(∀y)P(x ，y)∨Q(x ，z)∧(∃x)P(x ，y)，下列说法正确的是( )A.x 是自由变元B.x 是约束变元C.( ∀x)的辖域是P(x ，y)∨Q(x ，z)D.(∀x)的辖域是P(x ，y)4.设论域为{1，2}，与公式(∀x)┐A(X)等价的是( )A. ┐A(1) ∨┐A(2) B . ┐A(1)→┐(A2)C. ┐A(1) ∧┐A(2)D. A(1) →A(2)5．在公式（x ∀）F （x ，y ）→（∃ y ）G （x ，y ）中变元x 是（ ）A ．自由变元B ．约束变元C ．既是自由变元，又是约束变元D ．既不是自由变元，又不是约束变元6．下列等价式不正确的是（ ）A ．)(Q )(P ))(Q )(P (x x x x x x x ∀∨∀⇔∨∀B ．)(Q )(P ))(Q )(P (x x x x x x x ∀∧∀⇔∧∀C ．)(Q )(P ))(Q )(P (x x x x x x x ∃∨∃⇔∨∃D ．Q )(P )Q )(P (∧∀⇔∧∀x x x x7．设A （x ）:x 是人，B （x ）：x 犯错误，命题“没有不犯错误的人”符号化为（ ）A ．))(B )(A (x x x ∧∀ B ．⎤→∃)(A (x x ⎤ B （x ））C ．⎤))(B )(A (x x x ∧∃D ．⎤∧∃)(A (x x ⎤ B(x))二、填空题8.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。