离散数学期末总结（共6篇）
离散数学期末总结 篇1
1、设集合M={a，}，N ={{a}，}则MN=（）。A、 B、{} C、{a} D、{{a}，，a}
2、设关系F={<1，a >，<2，2>，
A、{<1，b>，<1，c>，
B、{，，<1，b>} C、{，<1，2>}
D、{，<2，2>，<1，b>}
3、设集合H={1，2，3，4}，则H上的关系R={
。x +y是偶数}具有（）A、自反性、反对称性和传递性
B、反自反性、反对称性和传递性
C、反自反性、对称性和传递性
D、自反性、对称性和传递性
4、设T是一棵完全二叉树，则T的每个结点都（）。
A、至少有两个子结点
B、至多有两个子结点
C、恰有两个子结点
D、可以有任意多个子结点
5、设R是实数集，“+，—，A、 >是群 B、 >是半群 D、 6、下面关系中，函数关系是（）。 A、{ B、{ D、{ 7、设 A、结合律 B、交换律 C、分配律 D、幂等律 8、设Z是整数集，“—”是整数减法，则下列说法正确的是（）。A、 B、 C、 D、 9、设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条（）。A、简单通路 B、初级通路 C、简单回路 D、初级回路 10、设G有6个3度点，2个4度点，其余顶点的度数均为0，则G的边数是（）。A、10 B、13 C、11 D、6 二、填空题(本大题共8题，共10个空，每空2分，共20分) 1、设关系R={，<2，1>，<2，b>}，则R逆关系R1=_______________________________。 2、在代数系统 3、设集合M={1，2，3，5}，则M的幂集P（M）包含___________个元素。 4、设T是一棵有n(n2)个顶点的树，则T有_____________条边。 5、设 6、设 7、设D是有向图，若D的基图是连通图，则称D是_________________图 8、既不含________________也不含____________________的无向图称为简单图。 三、计算题(本大题共3小题，每小题10分，共30分) 1、用等值演算法求公式A=(pq)(pr)的主析取范式。 2、求公式x(Q(x)G(x，s))(yP(y)zH(y，z))的前束范式。 3、设集合A={1，2，3，4，5}，关系R={ R； （3）求偏序集的极大元、极小元和最小元。 四、应用题(本大题共2小题，每小题5分，共10分) 1、用命题公式将下列命题符号化： 2和5是偶数，当且仅当5>2。 2、用谓词公式将下列命题符号化： 每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。 五、证明题（本大题共2小题，每小题10分，共20分） 1、在命题逻辑系统中用归结法证明下列推理是有效的： 前提：sq，pq，s 结论：p 2、在谓词逻辑系统中写出下列推理的（形式）证明： 前提：x(M(x)P(x))，x(M(x)G(x))，x(G(x))结论：xP(x) 计算题 6.设命题公式G = (P→Q)∨(Q∧(P→R)), 求G的主析取范式。 7.(9分)设一阶逻辑公式：G =(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A = {a, b, c, d}.R是A上的二元关系, R = {(a,b),(b,a),(b,c),(c,d)},(1)求出r(R), s(R), t(R)；(2)画出r(R), s(R), t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价： (1)G =(P∧Q)∨(P∧Q∧R) (2)H =(P∨(Q∧R))∧(Q∨(P∧R))13.设R和S是集合A＝{a, b, c, d}上的关系，其中R＝{(a, a),(a, c),(b, c),(c, d)}，S＝ {(a, b),(b, c),(b, d),(d, d)}.(1)试写出R和S的关系矩阵；(2)计算R•S, R∪S, R1, S1•R1.－ － －证明题 1.利用形式演绎法证明：{P→Q, R→S, P∨R}蕴涵Q∨S。2.设A,B为任意集合，证明：(A-B)-C = A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B, C→B, C→D}蕴涵A→D。4.(本题10分)A, B为两个任意集合，求证： A－(A∩B)=(A∪B)－B.答案： 1-5 BADBB 6-10 BBABB 1.{<1，a>，<1，2>， 环 三． (pq)(pr)(pq)(pr)1.(pqr)(pqr)(pqr)(pqr)m011m010m111m1012.x(Q(x)G(x,s))yz(P(y)H(y,z)) yzx((Q(x)G(x,s))(P(y)H(y,z))3.(1)R{1,1,2,2,3,3,4,4,5,5,1,2,1,3,1,4,1,5,2,4} 12(2)MR345123451111101010 （3）最小元=1 极小元=1 极大元=5 001000001000001四 1.令p表示2是偶数；令q表示5是偶数；r表示5>2； (pq)r 2.S（x）：x是计算机专业的学生；G（x）：x要学《编译原理》； F（x）：x学经济学； x(S(x)G(x))x(S(x)F(x)) 五 1，（1） s 前提引入（2） sq 前提引入（3） qs 置换规则 （4） q 1,3析取三段论（5） pq 前提引入（6） p 4,5拒取 （1） x(M(x)G(x)) 前提引入（2） M（x）v G（x） EI规则（3） x(G(x)) 前提引入（4） G(x)（5） M(x) AI规则 2,4析取三段论 （6） x(M(x)P(x)) 前提引入（7） M(x)→P（x） AI规则（8） P（x） 5,7假言推理（9） xP(x) EG规则 6.G = (P→Q)∨(Q∧(P→R)) = (P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧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)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)= m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7).7.G =(xP(x)∨yQ(y))→xR(x) = (xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)= xyz((P(x)∧Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)}, s(R)＝R∪R1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)}, －t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；(2) 关系图: abr(R)dcabs(R)dabt(R)dc c 11.G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3 ＝(3, 6, 7)H =(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7 ＝(3, 6, 7)G,H的主析取范式相同，所以G = H.1013.(1)MR00000011000000 MS10001000010001 01(2)R•S＝{(a, b),(c, d)}, R∪S＝{(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R1＝{(a, a),(c, a),(c, b),(d, c)}, －S1•R1＝{(b, a),(d, c)}.－－四 证明题 1.证明：{P→Q, R→S, P∨R}蕴涵Q∨S (1)P∨R (2)R→P(3)P→Q(4)R→Q(5)Q→R(6)R→S P Q(1)P Q(2)(3)Q(4)P (7)Q→S(8)Q∨S Q(5)(6)Q(7)2.证明：(A-B)-C =(A∩~B)∩~C 3.= A∩(~B∩~C)= A∩~(B∪C)= A-(B∪C)证明：{A∨B, C→B, C→D}蕴涵A→D(1)A D(附加)P(2)A∨B(3)B Q(1)(2)P Q(4)(4)C→B(5)B→C(6)C Q(3)(5)P(7)C→D(8)D Q(6)(7)D(1)(8)(9)A→D 所以 {A∨B, C→B, C→D}蕴涵A→D.1.证明：A－(A∩B) 一、【单项选择题】 (本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有()种不同的关系。 [A] 3 [B] 8 [C]9 [D]272、设A1,2,3,5,8,B1,2,5,7,则AB()。 [A] 3,8 [B]3 [C]8 [D]3,83、若X是Y的子集，则一定有()。 [A]X不属于Y [B]X∈Y [C]X真包含于 Y [D]X∩Y=X4、下列关系中是等价关系的是()。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A到集合B的映射，下列表述中错误的是()。 [A]对A的每个元素都要有象 [B] 对A的每个元素都只有一个象 [C]对B的每个元素都有原象 [D] 对B的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为()。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q7、设A={a,b,c},则A到A的双射共有()。 [A]3个 [B]6个 [C]8个 [D]9个 8、一个连通G具有以下何种条件时，能一笔画出：即从某结点出发，经过中每边仅一次回到该结点()。 [A] G没有奇数度结点 [B] G有1个奇数度结点 [C] G有2个奇数度结点 [D] G没有或有2个奇数度结点 9、设〈G,*〉是群，且|G|>1，则下列命题不成立的是()。 [A] G中有幺元 [B] G中么元是唯一的[C] G中任一元素有逆元 [D] G中除了幺元外无其他幂等元 10、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为() [A] p→┐q [B] p∨┐q [C] p∧q [D] p∧┐q11、设G=的结点集为V={v1,v2,v3},边集为E={,}.则G的割(点)集是()。 [A]{v1} [B]{v2} [C]{v3} [D]{v2,v3} 12、下面4个推理定律中，不正确的为()。 [A]A=>(A∨B)(附加律)[B](A∨B)∧┐A=>B(析取三段论) [C](A→B)∧A=>B(假言推理)[D](A→B)∧┐B=>A(拒取式) 13、在右边中过v1,v2的初级回路有多少条() [A] 1 [B] 2 [C] 3 [D] 414、若R，是环，且R中乘法适合消去律，则R是()。 [A]无零因子环 [C]整环 [B]除环 [D]域 15、无向G中有16条边，且每个结点的度数均为2，则结点数是()。 [A]8 [B]16 [C]4 [D] 32二、【判断题】 (本大题共8小题，每小题3分，共24分)正确的填T，错误的填F，填在答题卷相应题号处。 16、是空集。() 17、设S,T为任意集合，如果S—T=，则S=T。() 18、在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。() 19、关系的复合运算满足交换律。() 20、集合A上任一运算对A是封闭的。() 21、0,1,2,3,4,max,min是格。() 22、强连通有向一定是单向连通的。() 23、设都是命题公式，则(PQ)QP。() 三、【解答题】 (本大题共3小题，24、25每小题10分，26小题11分，共31分)请将答案填写在答题卷相应题号处。 24、设集合A={a, b, c}，B={b, d, e}，求 (1)BA;(2)AB;(3)A-B;(4)BA.25、设非空集合A，验证(P(A)，,~，A)是布尔代数 26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。 离散数学试题答案 一、【单项选择题】(本大题共15小题，每小题3分，共45分) BDDCCCBABDADCBB 二、【判断题】(本大题共8小题，每小题3分，共24分) FFTFTTTF 三、【解答题】(本大题共3小题，24、25每小题10分，26小题11分，共31分) 24、设集合A={a, b, c}，B={b, d, e}，求(1)BA;(2)AB;(3)A-B;(4)BA.标准答案：(1)BA={a, b, c}{b, d, e}={ b } (2)AB={a, b, c}{b, d, e}={a, b, c, d, e } (3)A-B={a, b, c}-{b, d, e}={a, c} (4)BA= AB-BA={a, b, c, d, e }-{ b }={a, c, d, e } 复习范围或考核目标：考察集合的基本运算，包括交集，并集,见课件第一章第二节,集合的运算。 25、设非空集合A，验证(P(A)，,~，A)是布尔代数 标准答案：证明 因为集合A非空，故P(A)至少有两个元素，显然，是P(A)上的二元运算.由定理10，任给B,C,DP(A), H1 BD=DC CD=DC H2 B(CD)=(BC)(BD)B(CD)=(BC)(BD) H3 P(A)存在和A，BP(A), 有B=B，BA=B H4，BP(A), BA，存在A~B，有 BA~B)= A B(A～B)= 所以(P(A)，,~，A)是布尔代数.复习范围或考核目标：考察布尔代数的基本概念，集合的运算，见课件代数系统中布尔代数小节。 26、如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。 标准答案：令p：他是计算机系本科生 q：他是计算机系研究生 r：他学过DELPHI语言 s:他学过C++语言 t:他会编程序 前提：(p∨q)→(r∧s),(r∨s)→t 结论：p→t 证①p P(附加前提) ②p∨q T①I ③(p∨q)→(r∧s)P(前提引入) ④r∧s T②③I ⑤r T④I ⑥r∨s T⑤I ⑦(r∨s)→t P(前提引入) 第一章 集合 １．分别用穷举法，描述法写出下列集合（１）偶数集合 （２）36的正因子集合（３）自然数中3的倍数（４）大于１的正奇数 (1)E={，-6，-4，-2，0，2，4，6，} ={2 i | i I } (2)D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3)N3= { 3, 6, 9, ```} = { 3n | nN } (4)Ad= {3, 5, 7, 9, ```} = { 2n+1 | nN } ２．确定下列结论正确与否（１）φφ ×（２）φ｛φ｝√（３）φφ√（４）φ｛φ｝√（５）φ｛ａ｝×（６）φ｛ａ｝√ （７）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝×（８）｛ａ，ｂ｝｛ａ，ｂ，ｃ，｛ａ，ｂ，ｃ｝｝√（９）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝×（１０）｛ａ，ｂ｝｛ａ，ｂ，｛｛ａ，ｂ｝｝｝√ ３．写出下列集合的幂集（１）｛｛ａ｝｝ {φ, {{ a }}} (2)φ {φ}（３）｛φ，｛φ｝｝ {φ, {φ}, {{φ}}, {φ,{φ}} }（４）｛φ，ａ，｛ａ，ｂ｝｝ {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}，{a, {a b }}, {φ,a,{ a, b }} }（５）Ｐ（Ｐ（φ）） {φ, {φ}, {{φ}}, {φ,{φ}} } ４．对任意集合Ａ，Ｂ，Ｃ，确定下列结论的正确与否（１）若ＡＢ，且ＢＣ，则ＡＣ√（２）若ＡＢ，且ＢＣ，则ＡＣ×（３）若ＡＢ，且ＢＣ，则ＡＣ×（４）若ＡＢ，且ＢＣ，则ＡＣ × ５．对任意集合Ａ，Ｂ，Ｃ，证明 (1)A(BC)(AB)(AC)左差A(BC)差A(BC)D.MA(BC) 分配(AB)(AC)右(2)A(BC)(AB)(AC)1)左差A(BC)(1)的结论(AB)(AC)差(AB)(AC)右 2)左差A(BC)D.MA(BC)分配(AB)(AC)差(AB)(AC)右(3)A(BC)(AB)(AC)左差A(BC)D.MA(BC)幂等(AA)(BC) 结合,交换(AB)(AC)右(4)(AB)BAB 左差(AB)B对称差((AB)B)((AB)B) 分配,结合((AB)(BB))(A(B)B)) 互补((AB)U)(A) 零一 (AB)(AB)右(5)(AB)CA(BC)左差(AB)C结合A(BC) D.MA(BC)差A(BC)(6)(AB)C(AC)B左差(AB)C结合A(BC)交换A(CB)结合(AC)B 差(AC)B右(7)(AB)C(AC)(BC)右(5)A(C(BC))差A(C(BC))分配A((CB)(CC))互补A((CB)U) 零一A(CB)交换A(BC)(5)(AB)C左 ６．问在什么条件下，集合Ａ，Ｂ，Ｃ满足下列等式 (1)A(BC)(AB)C左(AB)(AC)右若要右左,须CA(BC)，CA时等式成立 (2)ABA左右是显然的,AABAB,AB，AB时等式成立 (3)ABBABB,BB,B,代入原式得A，AB时等式成立 (4)ABBAABBA,只能AB,AB, BA,BA,AB时等式成立 (5)ABAB,若B,bB，当bA,bABA矛盾;当bA,bABA矛盾 (6)ABAB右左是显然的,ABAB,AAB,ABBAB,BAABAB时等式成立 (7)(AB)(AC)A左(AB)(AC)A(BC)A(BC)A(BC)A ABC时等式成立 (8)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC) A(BC),AB,AC时等式成立 (9)(AB)(AC)左(AB)(AC)A(BC)A(BC)A(BC) A(BC)时等式成立 (10)(AB)(AC)((AB)(AC))((AB)(AC))(AB)(AC)(AB)(AC) 由(6)知,(AB)(AC),ABAC,ABAC时等式成立 (11)A(BA)BA(BA)(AB)(AA)(AB)U(AB)B AB时等式成立 ７．设Ａ＝｛ａ，ｂ，｛ａ，ｂ｝，｝，求下列各式（１）φ∩｛φ｝=φ（２）｛φ｝∩｛φ｝={φ} （３）｛φ，｛φ｝｝－φ={φ,{φ}}（４）｛φ，｛φ｝｝－｛φ｝= {{φ}}（５）｛φ，｛φ｝｝－｛｛φ｝｝={φ}（６）Ａ－｛ａ，ｂ｝={{a,b}, φ}（７）Ａ－φ = A（８）Ａ－｛φ｝={a,b,{a,b}}（９）φ－Ａ=φ（１０）｛φ｝－Ａ=φ ８．在下列条件下，一定有Ｂ＝Ｃ吗？（１）ABAC 否，例：A={1，2，3}，B={4}，C={3,4}, ABAC{1,2,3,4},而BC。 （２）ABAC 否，例：A={1，2，3}，B={2，3}，C={2，3，4} ABAC{2,3},而BC。 （３）ABAC 对,若BC,不妨,aB,aC,若aA,aAB,aAB,aAB,aAC,aAC,aAC;若aA,aAB,aAB,aAB,aAC,aAC,aAC矛盾（４）ABAC且ABAC bB,若bA,bABAC,bC,若bA,bABAC,bC，BC,同理,CB,BC 9.(1)(AB)(BC)AB 证:a左,a(BC),aB,aB;a(AB),而aB,aA,aAB (2)若A(BC)且B(AC),则B。 若B,aB(AC)(AC),aA(BC),aC,aB即aB,矛盾 10．化简 ((ABC)(AB))((A(BC))A)(AB)A(AB)A (AA)(BA)(BA)BA11.设A={2，3，4}，B={1，2}，C={4，5，6}，求（１）AB{1, 3, 4} （２）ABC{1,3,5,6}（３）(AB)(BC){2,3,5,6} 12.设A={1，2，3，4}，B={1，2，5}，求 (1)P(A)P(B){φ,{1},{2},{1,2}} (2)P(A)P(B) {φ,{1},{2},{3},{4},{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}, {1,2,3,},{1,2,4,},{1,3,4,},{2,3,4},{1,2,3,4,},{5},{1,5}, {2,5},{1,2} } (3)P(A)P(B) { {3},{4},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{1,2,4},{1,3,4}，{2,3,4},{1,2,3,4} } (4)P(A)P(B) 计科系10级 计本 一、对课程的理解 个人认为离散数学是一门综合性非常强的学科。本书分为六个部分。为数理 逻辑、集合论、代数结构、组合数学、图论和初等数论。其中由于课时紧凑我们忽略了部分学习内容。感觉它是一门集理论思维与抽象思维于一身的学科。 开始学习大家可能会觉得很简单，学得很轻松，第一部分的数理逻辑在高中时也 有所接触，只是现在在高中的基础上更深层次的加入一些元素。第二部分集合论 高中也学过一点基本的，多了二元关系之类。据课本介绍，其中的偏序关系广泛 用于实际问题中，调度问题就是典型的实例。第三部分的代数结构是完全新的学习内容，开始带有抽象的色彩。接下来就学习了图论，是个很有意思的部分，不 像之前那么枯燥，可以有图形与关系之间的转换。 搜集有关资料得知《离散数学》的特点是： 1、知识点集中，概念和定理多：《离散数学》是建立在大量概念之上的逻辑 推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都 会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从 而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解 上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直 接证明法、反证法、归纳法、构造性证明法），同一个题也可能有几种方法。但 是《离散数学》证明 题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法。 同时要善于总结。 通过以上特点介绍使我对离散数学有了不一样的认识。我们是学计算机专 业的学生，离散数学的学习给了我们很多的帮助，虽然这门每个部分的联系不是 很紧密。今年我们开设的专业课有《数据库》，其中二元关系这部分与之就有了 很大的联系，听过离散数学后，数据库中这些关系的理解起来就不必那么费事了。 还有专业课《数据结构与算法》，这部分联系的就多了，主要是图论这部分。使 在学习数据结构时节省了不少时间，老师说起来也轻松。 二、对课程的建议 《离散数学》这本书中我们只学了四个部分：数理逻辑、集合论、代数系统、图论．这四部分内容中每一个部分都可以是一门独立的课程，它们分别作为《离 散数学》课程的一部分，容易造成教学内容繁多与教学课时数偏少相矛盾，使教 学过程具有很大的难度．这几部分的内容我们只是选择性的部分详细讲解，我觉 得在教学过程中对讲授内容的设置上应当有所侧重，比如学生对集合论基础的很 多内容在中学数学中已经有所了解，所以这部分内容只需要简要介绍一下，重点放在用集合论的方法解决实际应用问题上．对于二元关系这部分，侧重点是加强对与二元关系的几个性质相关问题的论证方法的训练．在数理逻辑上通过将一般命题公式和一阶逻辑公式化成范式，达到强化训练学生逻辑演算能力，并通过逻辑推理理论的学习来提高逻辑推理能力．图论部分重点放在基本概念的理解和实际问题的处理上，通过对相关定理及其证明思路的理解来体会图论的研究方法．代数系统这部分内容重点放在群论上，尤其要在代数系统、群、子群、循环群、变换群、正规子群的概念及相关问题的理解上下功夫，特别要掌握同构和同态的概念及应用，对于其它的代数系统如环、域及布尔代数则可以略讲．另外，现行大多数教材，主要是集中在从纯数学理论角度教授基本内容，这也是不利于学生的理解学习的．如果选择了这种教材，在教学过程中，应穿插介绍一些知识点在计算机科学中的应用，将之与离散数学理论结合介绍给学生，使学生重视这一课程的学习，产生学习兴趣，主动地进行学习．这将有利于学生理解理论知识，又为后续课程的学习奠定基础． 三、对老师的建议 第1章 命题逻辑 1.1 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母 p, q, r, … ,pi,qi,ri(i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令 p： 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义 设p为命题，复合命题 “非p”（或 “p的否定”）称 为p的否定式，记作p.符号称作否定联结词，并规定p 为真当且仅当p为假.2.合取式与合取联结词“∧” 定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q.∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例 将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解 令 p：王晓用功，q：王晓聪明，则 (1)p∧q (2)p∧q (3)p∧q.令 r : 张辉是三好学生，s :王丽是三好学生 (4)r∧s.(5)令 t : 张辉与王丽是同学，t 是简单命题.说明: (1)~(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨” 定义 设 p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q.∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例 将下列命题符号化 (1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解 令 p:2是素数, q:3是素数, r:4是素数, s:6是素数，则(1),(2),(3)均为相容或.分别符号化为: p∨r , p∨q, r∨s，它们的真值分别为 1, 1, 0.而(4),(5)为排斥或.令 t :小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为 (t∧u)∨(t∧u).令v :王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧w)∨(v∧w), 又可符号化为 v∨w , 为什么? 4.蕴涵式与蕴涵联结词“” 定义 设 p,q为二命题，复合命题 “如果p,则q” 称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.pq 的逻辑关系：q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p.当 p 为假时，pq 为真 常出现的错误：不分充分与必要条件 5.等价式与等价联结词“” 定义 设p，q为二命题，复合命题 “p当且仅当q”称作p与q的等价式，记作pq.称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.说明: (1)pq 的逻辑关系:p与q互为充分必要条件 (2)pq为真当且仅当p与q同真或同假 联结词优先级:(),, , , , 同级按从左到右的顺序进行 以上给出了5个联结词：, , , , ，组成 一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ;如果出 现的联结词同级，又无括号时，则按从左到右 的顺序运算;若遇有括号时，应该先进行括号 中的运算.注意: 本书中使用的 括号全为园括号. 命题常项 命题变项 1.2 命题公式及分类 命题变项与合式公式 命题常项：简单命题 命题变项：真值不确定的陈述句 定义 合式公式(命题公式, 公式)递归定义如下： (1)单个命题常项或变项 p,q,r,…,pi ,qi ,ri ,…,0,1 是合式公式 (2)若A是合式公式，则(A)也是合式公式 (3)若A, B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式 (4)只有有限次地应用(1)~(3)形成的符号串才是合式公式 说明: 元语言与对象语言，外层括号可以省去 合式公式的层次 定义 (1)若公式A是单个的命题变项, 则称A为0层公式.(2)称A是n+1(n≥0)层公式是指下面情况之一： (a)A=B, B是n层公式； (b)A=BC, 其中B,C分别为i层和j层公式，且 n=max(i, j)； (c)A=BC, 其中B,C的层次及n同(b)； (d)A=BC, 其中B,C的层次及n同(b)； (e)A=BC, 其中B,C的层次及n同(b).例如 公式 p p pq (pq)r ((pq)r)(rs) 公式的赋值 定义 给公式A中的命题变项 p1, p2, … , pn指定 一组真值称为对A的一个赋值或解释 成真赋值: 使公式为真的赋值 成假赋值: 使公式为假的赋值 说明： 0层 1层 2层 3层 4层 赋值=12…n之间不加标点符号，i=0或1. A中仅出现 p1, p2, …, pn，给A赋值12…n是 指 p1=1, p2=2, …, pn=n A中仅出现 p, q, r, …, 给A赋值123…是指 p=1,q=2 , r=3 … 含n个变项的公式有2n个赋值. 真值表 真值表: 公式A在所有赋值下的取值情况列成的表 例 给出公式的真值表 A=(qp)qp 的真值表 例 B = (pq)q 的真值表 例 C=(pq)r 的真值表 命题的分类 重言式 矛盾式 可满足式 定义 设A为一个命题公式 (1)若A无成假赋值，则称A为重言式(也称永真式) (2)若A无成真赋值，则称A为矛盾式(也称永假式) (3)若A不是矛盾式，则称A为可满足式 注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式 A=(qp)qp，B =(pq)q，C=(pq)r 1.3 等值演算 等值式 定义 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式 说明：定义中，A,B,均为元语言符号, A或B中 可能有哑元出现.例如，在(pq)((pq)(rr))中，r为左边 公式的哑元.用真值表可验证两个公式是否等值 请验证：p(qr)(pq)r p(qr) (pq)r 基本等值式 双重否定律 : AA 等幂律： AAA, AAA 交换律: ABBA, ABBA 结合律: (AB)CA(BC) (AB)CA(BC)分配律: A(BC)(AB)(AC) A(BC)(AB)(AC)德·摩根律: (AB)AB (AB)AB 吸收律: A(AB)A，A(AB)A 零律: A11，A00 同一律: A0A，A1A 排中律: AA1 矛盾律: AA0 等值演算: 由已知的等值式推演出新的等值式的过程 置换规则：若AB, 则(B)(A)等值演算的基础： (1)等值关系的性质：自反、对称、传递 (2)基本的等值式 (3)置换规则 应用举例——证明两个公式等值 例1 证明 p(qr)(pq)r 证 p(qr) p(qr) （蕴涵等值式，置换规则） (pq)r （结合律，置换规则） (pq)r （德摩根律，置换规则） (pq)r （蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍） 因为每一步都用置换规则，故可不写出 熟练后，基本等值式也可以不写出 应用举例——证明两个公式不等值 例2 证明: p(qr) (pq)r 用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假.方法一 真值表法（自己证） 方法二 观察赋值法.容易看出000, 010等是左边的 的成真赋值，是右边的成假赋值.方法三 用等值演算先化简两个公式，再观察.应用举例——判断公式类型 例3 用等值演算法判断下列公式的类型 (1)q(pq)解 q(pq) q(pq) （蕴涵等值式） q(pq) （德摩根律） p(qq) （交换律，结合律） p0 （矛盾律） 0 （零律） 由最后一步可知，该式为矛盾式.(2)(pq)(qp)解 (pq)(qp) (pq)(qp) （蕴涵等值式） (pq)(pq) （交换律） 1 由最后一步可知，该式为重言式.问：最后一步为什么等值于1？ (3)((pq)(pq))r) 解 ((pq)(pq))r) (p(qq))r （分配律） p1r （排中律） pr （同一律） 这不是矛盾式，也不是重言式，而是非重言式的可 满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1 说明：演算步骤不惟一,应尽量使演算短些 1.5 对偶与范式 对偶式与对偶原理 定义 在仅含有联结词, ∧,∨的命题公式A中，将 ∨换成∧, ∧换成∨，若A中含有0或1，就将0换成 1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A 定理 设A和A*互为对偶式，p1,p2,…,pn是出现在A和 A*中的全部命题变项，将A和A*写成n元函数形式，则(1) A(p1,p2,…,pn) A*( p1, p2,…, pn) (2)A( p1, p2,…, pn) A*(p1,p2,…,pn)定理（对偶原理）设A，B为两个命题公式，若A B，则A* B*.析取范式与合取范式 文字:命题变项及其否定的总称 简单析取式:有限个文字构成的析取式 如 p, q, pq, pqr, … 简单合取式:有限个文字构成的合取式 如 p, q, pq, pqr, … 析取范式:由有限个简单合取式组成的析取式 A1A2Ar, 其中A1,A2,,Ar是简单合取式 合取范式:由有限个简单析取式组成的合取式 A1A2Ar , 其中A1,A2,,Ar是简单析取式 范式:析取范式与合取范式的总称 公式A的析取范式: 与A等值的析取范式 公式A的合取范式: 与A等值的合取范式 说明： 单个文字既是简单析取式，又是简单合取式 pqr, pqr既是析取范式，又是合取范式(为什么?) 命题公式的范式 定理 任何命题公式都存在着与之等值的析取范式 与合取范式.求公式A的范式的步骤： (1)消去A中的, （若存在） (2)否定联结词的内移或消去 (3)使用分配律 对分配（析取范式） 对分配（合取范式） 公式的范式存在，但不惟一 求公式的范式举例 例 求下列公式的析取范式与合取范式 (1)A=(pq)r 解 (pq)r (pq)r （消去） pqr （结合律） 这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式） (2)B=(pq)r 解 (pq)r (pq)r （消去第一个） (pq)r （消去第二个） (pq)r （否定号内移——德摩根律） 这一步已为析取范式（两个简单合取式构成） 继续： (pq)r (pr)(qr) （对分配律） 这一步得到合取范式（由两个简单析取式构成） 极小项与极大项 定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一 次，而且第i（1in）个文字出现在左起第i位上，称这样 的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项 2n个极小项（极大项）均互不等值 用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系: mi Mi ，Mi mi 主析取范式与主合取范式 主析取范式: 由极小项构成的析取范式 主合取范式: 由极大项构成的合取范式 例如，n=3, 命题变项为p, q, r时，(pqr)(pqr) m1m3 是主析取范式 (pqr)(pqr) M1M5 是主合取范式 A的主析取范式: 与A等值的主析取范式 A的主合取范式: 与A等值的主合取范式.定理 任何命题公式都存在着与之等值的主析取范 式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤： (1)先求析取范式（合取范式） (2)将不是极小项（极大项）的简单合取式（简 单析取式）化成与之等值的若干个极小项的析 取（极大项的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并 按角标从小到大顺序排序.求公式的主范式 例 求公式 A=(pq)r的主析取范式与主合取范式.(1)求主析取范式 (pq)r (pq)r ，（析取范式） ① (pq) (pq)(rr) (pqr)(pqr) m6m7 ，r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 ③ ②, ③代入①并排序，得 (pq)r m1m3m5 m6m7（主析取范式） (2)求A的主合取范式 (pq)r (pr)(qr)，（合取范式） ① pr p(qq)r (pqr)(pqr) M0M2, qr (pp)qr (pqr)(pqr) M0M4 ②, ③代入①并排序，得 (pq)r M0M2M4 （主合取范式）主范式的用途——与真值表相同(1)求公式的成真赋值和成假赋值 例如 (pq)r m1m3m5 m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成 ②③ 假赋值和成真赋值.(2)判断公式的类型 设A含n个命题变项，则 A为重言式A的主析取范式含2n个极小项 A的主合取范式为1.A为矛盾式 A的主析取范式为0 A的主合取范式含2n个极大项 A为非重言式的可满足式 A的主析取范式中至少含一个且不含全部极小项 A的主合取范式中至少含一个且不含全部极大项 例 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习.选派必须 满足以下条件： (1)若赵去，钱也去； (2)李、周两人中至少有一人去； (3)钱、孙两人中有一人去且仅去一人； (4)孙、李两人同去或同不去； (5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出 国？ 解此类问题的步骤为： ① 将简单命题符号化 ② 写出各复合命题 ③ 写出由②中复合命题组成的合取式 ④ 求③中所得公式的主析取范式 解 ① 设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.②(1)(pq) (2)(su) (3)((qr)(qr)) (4)((rs)(rs)) (5)(u(pq)) ③(1)~(5)构成的合取式为 A=(pq)(su)((qr)(qr)) ((rs)(rs))(u(pq))④ A (pqrsu)(pqrsu)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下: A (pq)((qr)(qr))(su)(u(pq)) ((rs)(rs)) （交换律)B1=(pq)((qr)(qr)) ((pqr)(pqr)(qr))（分配律） B2=(su)(u(pq)) ((su)(pqs)(pqu)) （分配律） B1B2 (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru)再令 B3 =((rs)(rs))得 A B1B2B3 (pqrsu)(pqrsu)注意：在以上演算中多次用矛盾律 要求：自己演算一遍 1.6 推理理论 推理的形式结构 推理的形式结构—问题的引入 推理举例: (1)正项级数收敛当且仅当部分和有上界.(2)若 推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法 • 真值表法 • 等值演算法 判断推理是否正确 • 主析取范式法 • 构造证明法 证明推理正确 说明：当命题变项比较少时，用前3个方法比较方 便, 此时采用形式结构“造证明时，采用“前提: ”.而在构 , 结论: B”.推理定律与推理规则 推理定律——重言蕴涵式 构造证明——直接证明法 例 构造下面推理的证明： 若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解 设 p：明天是星期一，q：明天是星期三，r：我有课，s：我备课 推理的形式结构为 例 构造下面推理的证明: 2是素数或合数.若2是素数，则 是无理数.若 是无理数，则4不是素数.所以，如果4是 素数，则2是合数.用附加前提证明法构造证明 解 设 p：2是素数，q：2是合数，r： 是无理数，s：4是素数 推理的形式结构 前提：p∨q, pr, rs 结论：sq 证明 ① s 附加前提引入 ②pr 前提引入 ③rs 前提引入 ④ps ②③假言三段论 ⑤p ①④拒取式 ⑥p∨q 前提引入 ⑦q 九年级是初中三年的关键时刻，学生取得好成绩才是最重要的事情。九年级学生整体学习风气很浓，学习数学的进取性也很高，还有一些同学经过一个学期的努力，基础知识有了必须的提高，学习态度也端正了许多，但班级两极分化还是很严重。今后还应当在这方面多多研究。 二、教学工作方面 1、备好课。本学期我每一节课前都认真钻研教材，对教材的基本思想、基本概念，了解教材的结构，重点与难点，掌握知识的逻辑，能运用自如，明白应补充哪些资料，怎样才能教好。了解学生的兴趣、需要、方法、习惯，学习新知识可能会有哪些困难，采取相应的预防措施。研究教法，解决如何把已掌握的教材传授给学生，包括如何组织教材、如何安排每节课的活动。 2、在课堂上，组织好课堂教学，关注全体学生，注意信息反馈，调动学生的学习进取性，课堂语言简洁明了，课堂提问面向全体学生，注意引发学生学数学的兴趣，课堂上讲练结合，精讲多练。 三、总复习工作面向全体学生 1、让学生板演，加强解题过程训练。如果只分析，优等生还能够，但有些学生就可能跟不上，并且让学生板演还能让不一样层次学生都有机会表现，因为学生板演可为教师供给反馈信息，如暴露知识上的缺欠，可弥补讲课中的不足，同时，学生板演中出现的优秀解题方法，为教师供给向学生学习的良好机会;另外也能够培养学生胆识，培养学生独立思考本事，促进记忆。 2、注重学生解题中的错误分析 在总复习中，学生在解题中出现错误是不可避免，教师针对错误进行系统分析是重要的，首先能够经过错误来发现教学中的不足，从而采取措施进行补救;错误从一个特定角度揭示了学生掌握知识的过程，是学生在学习中对所学知识不断尝试的结果，教师认真总结，能够成为学生知识宝库中的重要组成部分，使学生领略解决问题中的探索、调试过程，这对学生本事的培养会产生有益影响。 首先，应预防错误的发生，要了解不一样层次学生对知识的掌握情景，调查中发现： (1)审题本事差。 (2)分析本事差。 (3)缺少创新思维。 并针对以上情景进行了单独训练，效果较好。 其次，在复习过程中，提问是重要复习手段，对于学生错误的回答，要分析其原因进行有针对性的讲解，这样能够利用反面知识巩固正面知识。 最终，课后的讲评要抓住典型加以评述。事实证明，练是实践，评是升华，只讲不评，练习往往走过场。 四、自我提高 本学期在工作中不断积累经验，并及时构成了材料。在中考复习中，发现问题及时进行小结并进行有针对性的训练。本学期我认真学习信息技术，不断提高自身业务素质。此刻网络资源十分丰富，在网上能够找到很多有关中考的题和信息，给中考复习带来了很大的方便。同时应用多媒体教学，对学生进行知识的传授，激发和培养学生的学习兴趣，都有很大的帮忙。 在本学期我严格要求自我，坚持岗位练功，在教学中虚心向别的教师请教。并利用业余时间读了《有效教学的基本功――新课程下中小学教师备课技能指导》、《新课程》、《新教育》、《吉林教育》等有关的书籍与刊物，了解先进的教育教学方法，学习与借鉴对自我有用的教育学生的方法。加强理论学习，并在学习的同时，做了学习笔记和读书的心得笔记，努力提高自我的教育理念与自身素质。 【离散数学期末总结】推荐阅读： 电大离散数学期末试题08-27 离散数学 期末考试试卷答案06-30 电大 离散数学 期末考试历届真题试卷06-23 《李刚版离散数学》大一期末考试复习方向07-02 离散数学归纳06-18 离散数学一07-22 离散数学考试范围05-12 离散数学课件06-04 复习提纲离散数学07-07 离散数学经典例题08-01离散数学期末考试试题及答案 篇2
离散数学期末总结 篇3
离散数学课程总结 篇4
离散数学期末总结 篇5
初三数学期末总结 篇6