离散数学复习要点

离散数学复习要点第一章命题逻辑一、典型考查点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+y0C.空集是任意集合的真子集D.你明天能来吗?2.下列式子为重言式的是()A.P→P∨QB.(┐P∧Q)∧(P∨┐Q)C.┐(PQ)D.(P∨Q)(P→Q)3．下列为两个命题变元P，Q的小项是（）A．P∧Q∧PB．P∨QC．P∧QD．P∨P∨Q4．下列语句中是真命题的是（）A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（）A．P∧QB．P∨QC．（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，111C．全体指派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．构造命题公式（RQQP）→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)为xy，下列公式真值为真的是()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(xxxxxxxB．)(Q)(P))(Q)(P(xxxxxxxC．)(Q)(P))(Q)(P(xxxxxxxD．Q)(P)Q)(P(xxxx7．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．))(B)(A(xxxB．)(A(xxB（x））C．))(B)(A(xxxD．)(A(xxB(x))二、填空题8.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。9．（x）（y）（P（x，y）Q（y，z））∧xP（x，y）中x的辖域为________，x的辖域为________。10．公式（x）（F（x）→G(y)）→(y)(H(x)),,(Lzyx)中的自由变元为_________，约束变元为__________。三、综合应用题11．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。离散数学复习第三章集合与函数一、典型考查点1、基本概念判断：函数的入射、满射、双射及定理