离散数学复习要点第一章命题逻辑
一、典型考查点
1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1
2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5
3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5
4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9
5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。
6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15
7、等价式详见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 m1m3M0M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16
11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、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∨Q
B.(┐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∨Q
4．下列语句中是真命题的是（）
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 ∧Q
B ．P ∧ Q
C ．P → Q
D ．P ∨ Q
9．下面联结词运算不可交换的是（ ）A ．∧ B ．→ C ．∨ D ．
10下列命题公式不是重言式的是（ ）
A ．Q →（P ∨Q ）
B ．（P ∧Q ）→P
C ．（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；前束范式详见P36
2、谓词符号化 步骤：①正确理解给定命题。必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。②把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。③找出恰当量词。应注意全称量词(x)后跟条件式，存在量词(x)后跟合取式。④用恰当的联结词把给定命题表示出来。详见P30
3、谓词公式类型的判定（永真式、永假式、可满足式） 方法：利用论域翻译成自然语言后进行判断。详见P34
4、自由变元与约束变元的判定 方法：按定义，关键是要看它在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 自由出现的任何公式。详见P3435
6、蕴含式(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 自由出现的任意公式。详见P35
6、前束范式 方法：①把量词全部通过等值演算化到整个谓词公式的前面②把量词前面的┐全部通过德摩根定律化到谓词公式的内部。详见P36
7、推理：方法：演绎（常用格式）、反证法、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 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 x 7．设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.一个公式，如果量词均在全式的________，其作用域延伸到整个公式的________，则该公式称为前束范式。 9．（?x ）（?y ）（P （x ，y ）Q （y ，z ））∧?xP （x ，y ）中?x 的辖域为________，?x 的辖域为________。 10．公式（x ?）（F （x ）→G(y)）→(y ?)(H(x)),,(L z y x ∧)中的自由变元为_________，约束变元为__________。 三、综合应用题 11．符号化下面命题，并构造推理证明：人是要死的，苏格拉底是人，所以苏格拉底是要死的。 离散数学复习第三章集合与函数 一、典型考查点 1、基本概念判断：函数的入射、满射、双射及定理、复合运算，详见P72，73，75。幂集、差集、对称差、笛卡尔积，详见P46，47，43，49。全序关系，详见P68.。方法：理解概念即可，按定义的步骤计算。 2、关系的相关概念判断：①特殊关系：若R=，为空关系；若R=A B ，为全域关系。R={ 自反性 反自反性 对称性 反对称性 传递性 定义 x x A xRx x A yRz → xRz 矩阵特征主对角线全为1 主对角线全为0 沿对角线对 称 沿主对角线不对称 图特征每个顶点都有环每顶点都没有 环 有边则双向 边 若有边，则是单向边 集合特征IA ?R IA ?R=ΦR-1=R IA ?R?IA 4、关系的运算：①关系的集合运算，按集合的运算规律即可：交、并、补、差、对称差等。②复合运算：按顺序运算，逆运算，交换每个元的第一、二位元素的位置即 5、等价关系和划分的判断及证明：①等价关系的证明：自反、对称、传递三个性质逐一验证。要注意给出的等价关系的条件的变通。②等价关系与划分一一对应，等价关系的等价类即为确定的划分的分块，即有关系的，划在同一块。划分中凡在同一个分块中的元，都写成满足关系的元，这样写出的关系R就是一个等价关系。 6、相容关系和覆盖的判断：相容关系两个性质：自反和对称，注意：相容关系图的画法省略了自反和对称。覆盖按定义判断即可。详见P61 7、偏序关系与哈斯图：①基本概念：三个性质：自反、反对称和传递；可比，就是有关系，a≤b b≤a；盖住，就是直接关系，中间没有第三个元，即若a 8、求偏序关系的特殊元：设 ②若(x)(x B x≤b)为真，则称b为B的最大元。③若(x)(b x x≤b)为真，则称b为B的极小元。④若(x)(b x b≤x)为真，则称b为B的极大元。 根据定义判断时，最小（大）元与极小（大）元是有区别的，最小（大）元是B中最小（大）的元素，它与B中其他元素都可比；而极小（大）元不一定与B中元素都可比，只要没有比它小（大）的元素，它就是极小（大）元。对于有穷集B，极小（大）元一定存在，且可能有多个，但最小（大）元不一定存在，若存在则必唯一。若B中只有一个极小（大）元，则它一定是B的最小（大）元。详见P68 9、求上界下界上确界和下确界：设 判断时注意，上界下界上确界和下确界是A集合上来找的，B的上界，下界，最小上界，最大下界都可能不存在。若存在，最小上界和最大下界是唯一的。详见P69 二、强化练习 1.设Z+是正整数集，f：Z+×Z+→Z+，f(n，m)=nm，则f( ) A.仅是入射B.仅是满射C.是双射D.不是函数 ]2.关系矩阵所对应的关系具有自反性( ) A. ? ? ? ? ? ? ? ? ? ? 1 1 1 1 1 1 B. ? ? ? ? ? ? ? ? ? ? 1 1 1 1 1 C. ? ? ? ? ? ? ? ? ? ? 1 1 1 D. ? ? ? ? ? ? ? ? ? ? 1 1 1 1 3.设R1和R2是集合A上的相容关系，不是相容关系( ) A.R1?R2 B.Rl?R2 C.R1-1 D.Rl R2 4．集合A={1，2，…，10}上的关系R={ 5．若R和S是集合A上的两个关系，则下述结论正确的是（） A．若R和S是自反的，则R∩S是自反的B．若R和S是对称的，则R S是对称的 C．若R和S是反对称的，则R S是反对称的D．若R和S是传递的，则R∪S是传递的 6．R={<1，4>，<2，3>，<3，1>，<4，3>}，则下列不是t（R）中元素的是（） A．<1，1>B．<1，2>C．<1，3>D．<1，4> 7．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（） A．1∈A B．{1，2，3}?A C．{{4，5}}?A D．∈A 8．设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)·f2(x)=0的解为（） A ．M ∩N B ．M ∪N C ．M N D ．M-N 9．设A-B=，则有（ ）A ．B= B ．B ≠ C ．A ?B D ．A ?B 10．A ，B 是集合，P （A ），P （B ）为其幂集，且A ∩B=，则P(A)∩P(B)为（ ） A ． B ．{} C ．{{}} D ．{，{}} 11．设A={1，2，3，4，5}，B={6，7，8，9，10}，以下关系是从A 到B 的入射函数的是 A ．f ={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B ．f ={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C ．f ={<1,6>,<2,7>,<4,9>,<3,8>} D ．f ={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} 12．下面关于关系R 的传递闭包t(R)的描述最确切的是（ ） A ．t(R)是包含R 的二元关系 B ．t(R)是包含R 的最小传递关系 C ．t(R)是包含R 的一个传递关系 D ．t(R)是任何包含R 的传递关系 13.设A={l ，2，3，4}，A 上的二元关系R={<1，2>，<3，4>，<4，3>}，S={ 14．设N 是自然数集合，f 和g 是N 到N 的函数，且f （n ）=2n+1，g （n ）=n2，那么复合函数（f f ）（n ）=________（g f ）（n ）=________。 15．设复合函数g f 是从A 到C 的函数，如果g f 是满射，那么________必是满射，如果g f 是入射，那么________必是入射。 16．设A={1，2}，B={2，3}，则A-A=________，A-B=________。 17．设A={1，2}，B={2，3}，则A ⊕A=__________，A ⊕B=__________。 18．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R 的自反闭包r(R)= _________，对称闭包S （R ）=__________。 19．设f :R →R,f (x)=x2-2,g :R →R,g(x)=x-1,那么复合函数))((x g f =__________，))((x f g =__________。 20．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A ∪B)=_______,ran(A ∩B)= __________。 18．已知A={{}，{，1}}，B={{，1}，{1}}，计算A ∪B ，A ○+B ，A 的幂集P （A ）。 21．设A={a,b,c,d}，R={，，， 22.设A={2，3，6，12，24，36}，请画出A 上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。 23．设A={1，2，3，4，6，8，12，24}，R 为A 上的整除关系，试画的哈斯图，并求A 中的最大元、最小元、极大元、极小元。 24．若集合A={1，{2，3}}的幂集为P （A ），集合B={{?，2}，{2}}的幂集为P （B ），求 P(A)∩P(B)。 25． X={1 2 3 4}，R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。 （1）画出R 的关系图；（2）写出R 的关系矩阵；（3）说明R 是否具有自反、反自反、对称、传递性质。 26．设A={a,b,c},P(A)是A 的幂集，R 为A 上的包含关系，试给出 27．设R 为N ×N 上的二元关系，对任意, 28.设A={|a ，b ∈Z+，Z+为整数集}，A 上的关系R={<, 29．R 是集合A 上自反和传递的关系，试证明：R R=R 。 离散数学复习第四章代数系统 一、典型考查要点： 1、运算的判断：方法：运算满足封闭性，即运算后产生的象仍在同一个集合中。详见P77 2、运算性质的判断：运算性质：封闭、结合、交换、分配、幂等、吸收、消去 方法：根据定义，在所讨论的集中任取元素，符合定义即可。在运算表中可以判断：1）运算*具有封闭性，当且仅当运算表中的每个元素都属于A 。2）运算*具有可交换性，当且仅当运算表关于主对角线是对称的。3）运算*具有等幂性，当且仅当运算表的主对角线上的每一元素与它所在行（列）的表头元素相同。详见P79 3、代数系统中特殊元：么元（单位元）、零元、逆元 判断方法：根据定义，在所讨论的集中找到特殊元，符合定义即可。在运算表中可以判断：1）A 中关于运算*具有零元，当且仅当该元素所对应的行和列中的元素都与该元素相同。2） A中关于运算*具有幺元，当且仅当该元素所对应的行和列依次与运算表的行和列相一致。3）设A中关于运算*具有幺元，a和b互逆，当且仅当位于a所在行和b所在列的元素及b所在行和a 所在列的元素都是幺元。详见P80 4、子代数的判定：关键两个条件:B?A, 5、特殊代数系统判定：（G， ）封闭→广群结合→半群么元→独异点可逆→群，根据定义，满足条件即可。详见P86 6、群的证明：方法：根据群的四个条件，逐一验证即可，注意：对于么元和逆元，先根据运算特点解出么元和逆元，再验证。详见P86 7、群的性质：1、 8、子群及判定：三个判定定理根据已知条件选择，给定群 a⊙b∈H，a-1∈H 2、 11、格、子格、分配格、有补格的判定：1、格：即 二、强化练习 1.在整数集上，不是二元运算( )A.加法 B.减法 C.乘法D.除法 2.设A是奇数集合，×为乘法运算，则 3.不满足结合律是( )A.a*b=min(a，b) B.a*b=max(a，b)C.a*b=2(a+b) D.a*b=2ab 4．在N上，可结合的是（）A．a*b=a-2b B．a*b=min{a，b} C．a*b=-a-b D．a*b=|a-b| 5．整环和域是（）A整环一定是域B域不一定是整环C域一定是整环D域一定不是整环 6．设集合A={1，2，3，……，10}，A上是不封闭的是（）A．x*y=max{x,y} B．x*y=min{x,y}C．x*y=GCD{x,y},即x,y的最大公约数D．x*y=LCM{x,y},即x,y的最小公倍数 7．设H，K是群（G， ）的子群，下面代数系统是（G， ）的子群的是（） A．（H∩K， ）B．（H∪K， ）C．（K-H， ）D．（H-K， ） 4．下列所示的哈斯图所对应的偏序集中能构成格的是（） A．B．C．D． 8.代数系统 9.在实数集R上定义运算a b=a+b+ab，则幺元为________，元素2的逆元为________。 10．设S是非空有限集，代数系统 11．在 12．设 13．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是__________，设a有逆元，则其逆元a-1=__________。 14． 15．设H 是形如??? ??101x 的2×2阶矩阵的集合，H 中定义通常的矩阵乘法运算。验证H 是群，1 101-??? ??x =??? ??-101x 。 16．在整数集Z 上定义：Z ,,2∈?-+=b a b a b a ，证明： 17．设H 是G 的有限子集，则 离散数学复习第五章图论 一、典型考查要点 1、图的基本概念：方法：度：点连接的边的条数，自环算2度；生成子图：点不减少，边减少；完全图：每个点都与余下的点有边；同构：两个图总可以画成相同的。详见P110 2、握手定理：结点度数总和等于边数的两倍，即∑deg(v)=2|E|，用于边点度之间的计算。 3、路的两个定理及证明： 1、在一个具有n 个结点的图中，如果从结点vj 到vk 存在一条路，则从结点vj 到vk 存在一条不多于n-1条边的路。推论：在一个具有n 个结点的图中，若从结点vj 到vk 存在一条路，则必存在一条从vj 到vk 而边数小于n 的通路。详见P115 4、连通图的判定及证明：1、无向连通图：任意两点都有路，即都走得通，只有一个连通分支。2、有向图中：强连通，任意两点都有路，即都走得通；弱连通，去掉方向后才连通；单侧连通， 每对点，只要一个点可达另一点。3、强连通的充要条件证明：一个有向图是强连通的充分必要条件是G 有一个回路，它至少包含每个结点一次。详见P116-117 5、边割集、点割集的判定及证明：点割集：图中去掉这些点及关联的边后，恰好不连通。定理：一个连通无向图G 中的结点v 是割点的充分必要条件是存在两个结点u 和w ，使得结点u 和w 的每一条路都通过v 。 边割集：图中去掉这些边后，恰好不连通，连通分支变为2。定理：G 的一条边e 不包含在G 的回路中当且仅当e 是G 的割边。详见P116-117 6、邻接矩阵、可达矩阵的表示：邻接矩阵：10i j ij i j v adj v a v nadj v ori j ?=?=?，表示图中点与点的关系，可以利用它的Ak 来求长度为k 的路的条数，即定理：设A 为简单图G 的邻接矩阵，则Ak 中的i 行j 列元素akij 等于G 中联结vi 到vj 的 长度为k 的链(或路)的数目。可达矩阵：1v 0v i j ij i j v P v ??=???从到至少存在一条路从到不存在路可以利用它来判定连通性，全为1，就是连通的。 详见P117-118 7、欧拉图及应用：欧拉路：边遍行且只能一次的路，点可以重复。欧拉回路：边遍行且只能一次的回路。判定：欧拉路存在当且仅当G 连通，且有零个或两个奇数度结点。欧拉回路存在当且仅当G 连通，并且所有点度数都为偶数。应用到一笔画问题，即有没有欧拉路。 8、汉密尔顿图及应用：汉密尔顿路：点遍行且只能一次的路。汉密尔顿回路：点遍行且只能一次的回路。判定：1、必要条件：若图有汉密尔顿回路，则V 的每个非空子集S 均有W(G-S)≤|S|，其中W(G-S)是G-S 的连通分支数。可以利用这个必要条件来判定有些图不是汉密尔顿图。2、充分条件：图G 有n 个点的简单图,如果每一对结点度数之和大于等于n-1,则G 中存在一条汉密尔顿路。若每一对结点度数之和大于等于n,则存在汉密尔顿回路。3、应用到网路连通、朋友开会排座位等，就是先利用题目中的联系，有关系就确定一条边，构造一个图，找一条汉密尔顿路或汉密尔顿回路即可。详见P121 9、平面图的判定：1、平面图：画在平面上，边不相交叉。判定：平面图不含与K3,3,或K5同胚的子图。K3,3,K5及彼得森图都不是平面图。2、欧拉公式：n-m+r=2,计算边点面之间的关系问题。面的次数即围着这个面的边的条数，单独的边要算2次。必要条件：给定连通简单平面图G= 10、树的6个等价定义：(1)无回路的连通图(2)无回路且e=v-1 (3)连通且e=v-1(4)无回路，但增加一边后得到且仅得一个回路(5)连通，但删去任一边后就不连通(6)每一对结点间有且仅有一条通路。利用e=v-1和握手定理计算边点的数目。详见P128 11、最小生成树：连通图中权之各最小的生成树，利用避圈法：边的权由小到大依次画入生成树中，但不能形成回路，若有回路就不画入，这样直到形成生成树为止，最小生成树不唯一。应用在网络连通上，造价最少的问题中。详见P129 12、M 叉树详见P120，根树表示算式：根据算式运算的顺序，由内向外形成根树。详见P131 二、强化练习 13.13图的最小入度是( )A.0 B.1 C.2 D.3 2.下面既是汉密尔顿图又是欧拉图的图形是( ) ??????????1001001111011010 3.树有3个5度点、1个4度点、3个2度点，其它的都是1度，边是( ) A.17 B.18 C.19 D.20 5．G 是 n 个结点的简单图，有（ ）A ．Δ(G)＜nB ．Δ(G)≤nC ．Δ(G)＞nD ．Δ(G)≥n 6．具有4个结点的非同构的无向树的数目是（ ）A ．2 B ．3 C ．4 D ．5 7．简单图G 所有结点的度数之和为12，则G 边一定有（ ）A ．3 B4 C ．5 D ．6 8．下列不一定是树的是（ ）A ．无回路的连通图 B ．有n 个结点，n-1条边的连通图 C ．每对结点之间都有通路的图 D ．连通但删去一条边则不连通的图 9．欧拉回路是（ ）A ．路径 B ．迹C ．既是初级回路也是迹 D ．既非初级回路也非迹 10.若回路中，除________外________各不相同，则此回路称为圈(或初级回路)。 11.偶图记为Kn,m 那么当________时，Kn,m 是平面图，当________时，Kn,m 是非平面图。 12.若图中存在________，它经过图中所有的边恰好________次，则称该图为欧拉图。 13．在24图中，结点v2的度数是________。25．设图D= 14．如14图的有补格中，c 的补元是____，b 的补元是_____。 15．在根树中，若每一个结点的出度___m,则称这棵树为m 叉树。如果每一个结点的出度_____m 或0，则称这棵树为完全m 叉树。 16．简单图G 有n 个结点，m 条边，设m> 21 (n-1)(n-2)，证明：G 是连通的。 17.求30图所示格的所有5元子格。18.用矩阵的方法求31图中结点u2，u5之间长为2的路径的数目。19．28给出了一个有向图。（1）求出它的邻接矩阵A ；（2）求出A2，A3，A4及可达矩阵P 。 20．证明：一个图是强连通的，当且仅当图中有一个回路，它至少包含每个结点一次。 21．证明：边e 是图G 的一条割边，当且仅当图G 中不存在包含边e 的简单回路。 22．今有n 个人，已知他们中任何2人的朋友合起来一定包含其余n-2人。试证明： （1）当n ≥3时，这n 个人能排成一列，使得中间任何人是其两旁的人的朋友，而两头的人是其左边（或右边）的人的朋友。 （2）当n ≥4时，这n 个人能排成一圆圈，使得每个人是其两旁的人的朋友。 23．在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。 1、欧拉图判定和应用 【实验内容】 判断一个图是不是，如果是，求出所有欧拉路 【实验原理和方法】 （1）用关系矩阵R=n n ij r )(表示图。 （2）对无向图而言，若所有结点的度都是偶数，则该图为欧拉图。 C 语言算法： flag=1; for(i=1;i<=n && flag;i++) { sum=0; for(j=1;j<=n;j++) if(r[i][j]) sum++; if(sum%2==0) flag=0; } 如果 flag 该无向图是欧拉图 （3）对有向图而言，若所有结点的入度等于出度，则该图为欧拉图。 C 语言算法： flag=1; for(i=1;i<=n && flag;i++) { sum1=0; sum2=0; for(j=1;j<=n;j++) if(r[i][j]) sum1++; for(j=1;j<=n;j++) if(r[j][i]) sum2++; if(sum1%2==0 || sum2%2==0) flag=0; } 如果 flag 该有向图是欧拉图 （4）求出欧拉路的方法：欧拉路经过每条边一次且仅一次。可用回溯的方法求得所有欧拉路。 C 语言算法： int count=0,cur=0,r[N][N]; // r[N][N]为图的邻接矩阵，cur 为当前结点编号，count 为欧拉路的数量。 int sequence[M];// sequence 保留访问点的序列，M 为图的边数 输入图信息; void try1(int k) //k 表示边的序号 { int i,pre=cur; //j保留前一个点的位置,pre为前一结点的编号 for (i=0;i 实验一命题逻辑公式化简 【实验目的】加深对五个基本联结词（否定、合取、析取、条件、双条件）的理解、掌握利用基本等价公式化简公式的方法。 【实验内容】用化简命题逻辑公式的方法设计一个表决开关电路。 实验用例：用化简命题逻辑公式的方法设计一个 5 人表决开关电路，要求 3 人以上（含 3 人）同意则表决通过（表决开关亮）。 【实验原理和方法】 （1）写出5人表决开关电路真值表，从真值表得出5 人表决开关电路的主合取公式（或主析取公式），将公式化简成尽可能含五个基本联结词最少的等价公式。 （2）上面公式中的每一个联结词是一个开关元件，将它们定义成 C 语言中的函数。 （3）输入5人表决值（0或1），调用上面定义的函数，将5人表决开关电路真值表的等价公式写成一个函数表达式。 （4）输出函数表达式的结果，如果是1，则表明表决通过，否则表决不通过。 参考代码： #include 《离散数学》实验报告专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一.实验目的 通过上机实验操作,将命题连接词运算融入到C语言的程序编写中,一方面加强对命题连接词运算的理解,另一方面通过编程实现命题连接词运算,帮助学生复习与锻炼C语言知识,将理论知识与实际操作结合,让学生更加容易理解与记忆命题连接词运算。 二.实验原理 (1) 非运算, 符号:? ,当P=T时 ,?P为F, 当P=F时 ,?P为T 。 (2) 合取, 符号: ∧ , 当且仅当P与Q的真值同为真,命题P∧Q的真值才为真;否则,P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P与Q的真值同为假,命题P∨Q的真值才为假;否则,P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P与Q的真值不同时,命题P▽Q的真值才为真;否则,P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时,命题P→Q的真值才为假;否则,P→Q 的真值为真。 (6) 等价, 符号: ? , 当且仅当P,Q的真值不同时,命题P?Q的真值才为假;否 则,P→Q的真值为真。 三.实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include 离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间 目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。 《离散数学》 课程设计 学院计算机学院 学生姓名 学号 指导教师 评阅意见 提交日期 2011 年 11 月 25 日 引言 《离散数学》是现代数学的一个重要分支，也是计算机科学与技术，电子信息技术，生物技术等的核心基础课程。它是研究离散量（如整数、有理数、有限字母表等）的数学结构、性质及关系的学问。它一方面充分地描述了计算机科学离散性的特点，为学生进一步学习算法与数据结构、程序设计语言、操作系统、编译原理、电路设计、软件工程与方法学、数据库与信息检索系统、人工智能、网络、计算机图形学等专业课打好数学基础；另一方面，通过学习离散数学课程，学生在获得离散问题建模、离散数学理论、计算机求解方法和技术知识的同时，还可以培养和提高抽象思维能力和严密的逻辑推理能力，为今后爱念族皮及用计算机处理大量的日常事务和科研项目、从事计算机科学和应用打下坚实基础。特别是对于那些从事计算机科学与理论研究的高层次计算机人员来说，离散数学更是必不可少的基础理论工具。 实验一、编程判断一个二元关系的性质（是否具有自反性、反自反性、对称性、反对称性和传递性） 一、前言引语：二元关系是离散数学中重要的内容。因为事物之间总是可以根据需要确定相应的关系。从数学的角度来看，这类联系就是某个集合中元素之 间存在的关系。 二、数学原理：自反、对称、传递关系 设A和B都是已知的集合，R是A到B的一个确定的二元关系，那么集合R 就是A×B的一个合于{()∈A×}的子集合 设R是集合A上的二元关系： 自反关系：对任意的x∈A,都满足<>∈R，则称R是自反的，或称R具有自反性，即R在A上是自反的?(?x)((x∈A)→(<>∈R))=1 对称关系：对任意的∈A，如果<>∈R，那么<>∈R，则称关系R是对称的，或称R具有对称性，即R在A上是对称的? (?x)(?y)((x∈A)∧(y∈A)∧(<>∈R)→(<>∈R))=1 传递关系：对任意的∈A，如果<>∈R且<>∈R，那么<>∈R，则称关系R是传递的，或称R具有传递性，即R在A上是传递的? (?x)(?y)(?z)[(x∈A)∧(y∈A)∧(z ∈A)∧((<>∈R)∧(<>∈R)→(<>∈R))]=1 三、实验原理：通过二元关系与关系矩阵的联系，可以引入N维数组，以数组的运算来实现二元关系的判断。 图示： 第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若 2+2=4,则 3+3=6. (2)若 2+2=4,则 3+3≠6. (3)若 2+2≠4,则 3+3=6. (4)若 2+2≠4,则 3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。 《离散数学》实验报告 专业网络工程 班级 姓名 学号 授课教师 二 O 一六年十二月 目录 实验一联结词的运算 实验二根据矩阵的乘法求复合关系 实验三利用warshall算法求关系的传递闭包实验四图的可达矩阵实现 实验一联结词的运算 一．实验目的 通过上机实验操作，将命题连接词运算融入到C语言的程序编写中，一方面加强对命题连接词运算的理解，另一方面通过编程实现命题连接词运算，帮助学生复习和锻炼C语言知识，将理论知识与实际操作结合，让学生更加容易理解和记忆命题连接词运算。二．实验原理 (1) 非运算, 符号: ,当P=T时，P为F, 当P=F时，P为T 。 (2) 合取, 符号: ∧ , 当且仅当P和Q的真值同为真，命题P∧Q的真值才为真；否则，P∧Q的真值为假。 (3) 析取, 符号: ∨ , 当且仅当P和Q的真值同为假，命题P∨Q的真值才为假；否则，P∨Q的真值为真。 (4) 异或, 符号: ▽ , 当且仅当P和Q的真值不同时，命题P▽Q的真值才为真；否则，P▽Q的真值为真。 (5) 蕴涵, 符号: →, 当且仅当P为T,Q为F时，命题P→Q的真值才为假；否则，P→Q 的真值为真。 (6) 等价, 符号: ?, 当且仅当P,Q的真值不同时，命题P?Q的真值才为假；否则，P→Q的真值为真。 三．实验内容 编写一个程序实现非运算、合取运算、析取运算、异或运算、蕴涵运算、等价运算。四．算法程序 #include 欢迎共阅 一、填空题 1设集合A,B ，其中A ＝{1,2,3},B={1,2},则A-B ＝____________________; ?(A)-?(B)＝__________________________. 2.设有限集合A,|A|=n,则|?(A×A)|=__________________________. 3.设集合A={a ,b },B={1,2},则从A 到B 的所有映射是_______________________________________,其中双射的是__________________________. 4.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题 离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若 离散数学考试题(后附详细答案) 一、命题符号化(共6小题,每小题3分,共计18分) 1.用命题逻辑把下列命题符号化 a)假如上午不下雨,我去瞧电影,否则就在家里读书或瞧报。 设P表示命题“上午下雨”,Q表示命题“我去瞧电影”,R表示命题“在家里读书”,S表示命题“在家瞧报”,命题符号化为:(?P?Q)∧(P?R∨S) b)我今天进城,除非下雨。 设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:?Q→P或?P→Q c)仅当您走,我将留下。 设P表示命题“您走”,Q表示命题“我留下”,命题符号化为: Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不就是有理数 设R(x)表示“x就是实数”,Q(x)表示“x就是有理数”,命题符号化为: ?x(R(x) ∧?Q(x)) 或??x(R(x) →Q(x)) b)对于所有非零实数x,总存在y使得xy=1。 设R(x)表示“x就是实数”,E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为: ?x(R(x) ∧?E(x,0) →?y(R(y) ∧E(f(x,y),1)))) c) f 就是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b、 设F(f)表示“f就是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为:F(f)??a(A(a)→?b(B(b) ∧ E(f(a),b) ∧?c(S(c) ∧ E(f(a),c) →E(a,b)))) 二、简答题(共6道题,共32分) 1.求命题公式(P→(Q→R))?(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋 值。(5分) (P→(Q→R))?(R→(Q→P))?(?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) 这就是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 (?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) 2.设个体域为{1,2,3},求下列命题的真值(4分) a)?x?y(x+y=4) b)?y?x (x+y=4) a) T b) F 3.求?x(F(x)→G(x))→(?xF(x)→?xG(x))的前束范式。(4分) ?x(F(x)→G(x))→(?xF(x)→?xG(x)) ??x(F(x)→G(x))→(?yF(y)→?zG(z))??x(F(x)→G(x))→?y?z(F(y)→G(z)) ??x?y?z((F(x)→G(x))→ (F(y)→G(z))) 4.判断下面命题的真假,并说明原因。(每小题2分,共4分) a)(A?B)－C=(A-B) ?(A-C) b)若f就是从集合A到集合B的入射函数,则|A|≤|B| a) 真命题。因为(A?B)－C=(A?B)?~C=(A?~C)?(B?~C)=(A-C)?(B-C) b) 真命题。因为如果f就是从集合A到集合B的入射函数,则|ranf|=|A|,且ranf?B,故命题 成立。 实验报告 （2013 / 2014 学年第一学期） 课程名称离散数学 实验名称利用真值表法求取主析取范式 以及主合取范式的实现 实验时间2013 年10 月23 日指导单位计算机学院、软件学院 指导教师 学生姓名班级学号 学院(系) 计算机、软件 专业软件工程 学院 实验报告 实验名称利用真值表法求取主析取范式 指导教师 以及主合取范式的实现 实验类型验证实验学时 4 实验时间2013.10.23 一、实验目的和要求 1、编程实现用真值表法求取含三个以内变量的合式公式的主析取范式和主合取范式。 2、要求： 1)从屏幕输入含三个以内变量的合式公式（其中联结词按照从高到底 的顺序出现） 2)规范列出所输合式公式的真值表 3)给出相应主析取和主合取范式 二、实验内容 1.可用字符数组a记录输入的合式公式（其中'&'代表与，'|'代表或，'~' 代表非，'>'代表单条件，'='代表双条件) 2.多重循环显示真值表（1表示T，0表示F，先1后0）并对公式进行相 应赋值得数组b 3.函数递归计算各种赋值情况下b的取值 4.联接词运算符定义 三、实验设计及代码 1、求取真值表 void truetable(){ /*求真值表函数*/ char s1[30],s2[30],s3[30],s4[30]; int n,i,j,k,m; printf("您要计算真值表！\n"); printf("***************** 输入要计算的表达式(A~Z,a~z) ****" "************ \n"); printf("(其中'&'代表与 '|'代表或 '~'代表非 '>'代表单条件 " "'='代表双条件)\n"); gets(s4); printf(" \n您输入要计算的表达式为：%s \n",s4); n=got(s1, s4); if(!n) {printf("输入有误！\n");return;} m = (int)pow(2,n); printf("计算真值表如下:\n"); for(j=0;j<(int)strlen(s1);j++){ printf("%c ",s1[j]); } printf(" %s\n",s4); for(j=0;j 数理逻辑部分 选择、填空及判断 ?下列语句不是命题的（ A ）。 (A) 你打算考硕士研究生吗？ (B) 太阳系以外的星球上有生物。 (C) 离散数学是计算机系的一门必修课。 (D) 雪是黑色的。 ?命题公式P→(P∨?P)的类型是（ A ） (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A是重言式，那么A的否定式是( A ) A. 矛盾式 B. 重言式 C. 可满足式 D.不能确定 ?以下命题公式中，为永假式的是( C ) A. p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值是( D ) A. 00,11 B. 00,01,11 C.10,11 D. 10 ?谓词公式) x xP∧ ?中，变元x是 ( B ) R , ( x ) (y A. 自由变元 B. 既是自由变元也是约束变元 C. 约束变元 D. 既不是自由变元也不是约束变元 ?命题公式P→(Q∨?Q)的类型是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x，) x x→ ?等值于( A ) A ) ( (B A. B ( D. B x xA→ x ?) ( ( ? C. B x∧ A ?) ( B. ) ?) xA→ x ) ( A x (B x∨ ?下列语句中是真命题的是( D )。 A．你是杰克吗？ B．凡石头都可练成金。 C．如果2+2=4，那么雪是黑的。 D．如果1+2=4，那么雪是黑的。 ?从集合分类的角度看，命题公式可分为( B ) A. 永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A. ﹁p∨q B. ﹁(p∨q) C. ﹁p∧q D. p→﹁q ?一个公式在等价意义下，下面写法唯一的是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p，q，r的公式中，是主析取范式的是( D )。 离散数学实验指导书2015 年3月6 日 绪言 通常对离散数学教学的认识就是上课老师讲述一个个概念、定理、公式和例题，学生背概念、公式，理解基础上记忆定理，然后据此做证明题、计算以及解题。实质上离散数学不仅仅是这些，还有实验。在理论教学过程中，学生的活动只是“智力活动”，或更为直接地说是解题活动，教师在上面讲离散数学，而学生则每天在课堂上听课并在纸上做题目。这样，对多数学生而言，离散数学的发现探索活动没有能够真正开展起来。 离散数学实验教学，通常由教师提出问题，让学生在计算机上做实验，利用小组合作学习或者组织全班讨论，开展研究性学习活动；实验过程中，依靠计算机，让学生主动参与发展、探究、解决问题，从中获得离散数学研究、解决实际问题的过程体验、情感体验，产生成就感，进而开发学生的创新潜能，因而对离散数学实验课程教学进行研究具有重要意义。 利用计算机进行离散数学实验教学，不仅是开展离散数学研究性学习的一种有效方式，而且也为数据结构及程序设计课程教学的开展提升了层次。知识经济时代对创新人才的需求与离散数学教育中忽视学生创造性能力培养的矛盾日益凸显。在教学中倡导研究性学习，开展离散数学实验课程教学的研究与探索，与当前社会对离散数学教学的需求是一致的。 目前国内外很少有人对离散数学实验课程教学进行研究，尤其是国内进行这方面研究的人员更少，人们更重视离散数学理论课程教学的研究，忽视了离散数学实验课程对理论课程教学的辅助与促进作用，也忽视了离散数学实验课程与数据结构等课程的有机联系。因而本学期离散数学课程组依据“2014培养方案”准备进行离散数学实验课程教学的研究与探索，以便更好的做好离散数学课程的教学改革工作。 主要包括四个部分：集合与关系、数理逻辑、代数系统、图论。要求学生了解算法，理解运用C或C++语言（也可以是其他高级程序设计语言）把书中的部分内容的算法编写出能在计算机上运行的程序的思想，掌握实现离散数学部分算法程序设计的基本编程技术。 学生实验报告 学院：软件与通信工程学院 课程名称：离散数学（软件） 专业班级： 12软件 3 班 姓名：简建敏 学号： 0123897 学生实验报告（1） 一、实验综述 1、实验目的及要求 （1）掌握关系的性质的概念； （2）掌握关系性质的判别方法及算法； （3）编写程序，根据关系矩阵计算判别关系的性质； （4）进一步熟悉和掌握C++程序开发。 实验要求： 认真完成实验题，能正确运行，提交实验报告并上传程序，实验报告要求写出操作步骤、结果、问题、解决方法、体会等。 实验题： ，判设A={a,b,c,d}，A上的关系R={ 离散数学实践内容 ●内容： 从下列题目中任意选择1个，完成相应写作或编程，并制作一个技术报告，包括书面报告和口头报告两部分。 ●目的： ? 选择一个自己感兴趣的主题作较深入的学习和研究。 ? 培养阅读和查找技术文献的能力。 ? 作技术报告的能力(口头和书面) ●报告的具体要求： a. 书面报告: word文档文字5页左右（不包括图表），一般包括以下部分: i. 摘要–对所选题目做一个简短、完整的描述。 ii. 目的–介绍选题目的，为什么这个题目有趣/有用。 iii. 背景–介绍相关定义、术语，或其它背景知识。 iv. 主体部分–介绍具体内容，从所选题目中学到什么新的知识？前人的观点，和你的观点？通过对比、引用、论证等方法来陈述。 v. 结论–总结新知识点及其用途。 vi. 引用的文献。 b. 口头: 制作ppt，并作一个15分钟左右的口头报告，用通俗易懂的方式把 你所获得的知识和大家分享。口头报告时间是在第6周到第16周《离散数学应用实践课程》中，按照选课学生的学号顺序进行演讲。 ●选题内容 1.讨论逻辑悖论，例如：说谎者悖论，纸牌悖论，理发师悖论等，说明如何解决它们。 2.讨论模糊逻辑怎样用于实际应用。 3.介绍Prolog逻辑程序设计语言(一个用自然语言进行人机对话的软件工具)，解释Prolog 是如何使用消解的。 4. “自动定理证明”(ATP)是使用计算机来完成机械地证明定理的任务。讨论自动定理证明 的目标和应用，以及在开发自动定理证明器上取得的进步。 5. 讨论函数概念的发展历史及其应用。 6. 鸽巢原理又名抽屉原理或狄利克雷原理,它由德国数学家狄利克雷 (Divichlet,1805-1855)首先发现。鸽巢原理在组合学中占据着非常重要的地位,它常被用来证明一些关于存在性的数学问题,并且在数论和密码学中也有着广泛的应用。讨论它的历史和应用。 7. 描述关系数据库的基本原理。关系数据库与其它类型的数据库相比，使用面有多 广？ 《离散数学》 实验报告 题目 专业 学号 姓名 指导教师 提交日期 实验一五种连结词的逻辑运算 一.实验目的 用C语言实现两个命题变元的合取、析取、蕴涵和等价表达式的计算。熟悉连接词逻辑运算规则，利用程序语言实现逻辑这几种逻辑运算。 二.实验内容 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、蕴涵和等价四种运算的的真值。要求对输入内容进行分析，如果不符合0、1条件需要重新输入，程序有良好的输入输出界面。 三. 实验过程 1. 算法分析： 编程语言为c语言 合取/\：p，q都为1的时候为1，其他为0 析取\/：p，q都为0的时候为0，其他为1 蕴含->：p为1，q为0时为0，其他为1 等价<->：p，q同真同假 流程图 2. 程序代码： #include do{ printf("请输入q的值(0或1)"); scanf("%d",&q); if(q!=0&&q!=1) printf("输入有误"); }while(q!=0&&q!=1); do{ printf("请选择要进行的操作\n"); printf("1:合取\n2:析取\n3:蕴含\n4:等价\n"); scanf("%d",&i); switch(i){ case 1:{ if(p&&q) printf("合取运算：p/\q=1\n"); else printf("合取运算：p/\q=0\n"); break; } case 2:{ if(p||q) printf("析取运算：p\/q=1\n"); else printf("析取运算：p\/q=0\n"); break; } case 3:{ if(p&&!q) printf("蕴含：p->q=0\n"); else printf("蕴含：p->q=1\n"); break;} case 4:{ if((p&&q)||(!p&&!q)) printf("等价运算：p<->q=1\n"); else printf("等价运算：p<->q=0\n"); break; } }printf("是否继续运算1\\0\n"); scanf("%d",&t); }while(t); return 0; } 大连民族学院 计算机科学与工程学院实验报告实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络111班 学生姓名：张山学号：2011083123 实验日期：2013年12月22日实验地点：I区实验机房 实验学时：8小时实验成绩： 指导教师签字：年月日老师评语： 1 实验题目：集合的运算 实验原理： 1、实验内容与要求： 实验内容：本实验求两个集合间的运算，给定两个集合A、B，求集合A与集合B之间的交集、并集、差集、对称差集和笛卡尔乘积。 实验要求：对于给定的集合A、B。用C++/C语言设计一个程序（本实验采用 C++），该程序能够完成两个集合间的各种运算，可根据需要选择输出某种运算结果，也可一次输出所有运算结果。 2、实验算法： 实验算法分为如下几步： （1）、设计整体框架 该程序采取操作、打印分离（求解和输出分开）的思想。即先设计函数求解各部分运算并将相应结果传入数组（所求集合）中，然后根据需要打印运算结果。 （2）、建立一个集合类（Gather） 类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口（实现操作的函数）包括构造函数，菜单显示函数，求解操作函数，打印各种运算结果等函数。 （3）、设计类体中的接口 构造函数：对对象进行初始化，建立集合A与集合B。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下： 2 1*求交集：根据集合中交集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着 离散数学实验报告 1．【实验题目】 实验一命题逻辑（1） 2．【实验目的】 熟悉掌握命题逻辑中的联接词，实现二元合取、析取、蕴涵和等价表达式的计算，熟悉连接词逻辑运算规则，利用程序语言实现其逻辑运算。 3．【实验内容】 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。 4. 【实验要求】 通过以下界面提示实现相应逻辑运算，给出具体逻辑值 **************************************************************** 请输入变量命题P和Q的值（1或0）： 请选择（1—5）要进行的逻辑运算： 1.合取运算（P∧Q） 2.析取运算（P∨Q） 3.条件运算（P→Q） 4.双条件运算（P←→Q） 5.继续/退出（y/n） **************************************************************** 5. 【算法描述】 1.合取运算（P∧Q），P、Q同真时为真，其余为假。 2.析取运算（P∨Q），P、Q同假时为假，其余为真。 3.条件运算（P→Q），P为真，Q为假时，为假，其余为真。 4.双条件运算（P←→Q），P、Q同真同假是为真。 6. 【源程序（带注释）】 #include class math { char p,q; int result; public: math(char x,char y); int pdp(char x); int pdq(char y); hequ(char x,char y,int t); xiqu(char x,char y,int t); tiaojian(char x,char y,int t); shuangtiaojian(char x,char y,int t); caidan(); }; //判断p是否为1或0 int math::pdp(char x) { int a; p=x; if(x!='0'&&x!='1') { //cout<<"错误"< 离散数学实验报告 姓名： 学号： 班级： 实验地点： 实验时间： 1实验目的和要求 运用最小生成树思想和求最小生成树程序解决实际问题。实际问题描述如下： 八口海上油井相互间距离如下表，其中1号井离海岸最近，为5km。问从海岸经1号井铺设油管把各井连接起来，怎样连油管长度最短（为便于检修，油管只准在油井处分叉）？ 2实验环境和工具 实验环境：Windows 7 旗舰版 工具：Dev-C++ 5.8.3 3实验过程 3.1算法流程图 3.2程序核心代码 //油管铺设问题Prim算法实现 #include for (j=0;j离散数学 欧拉图实验
(完整版)离散数学实验指导书及其答案
离散数学实验报告
离散数学实验报告
离散数学实验报告四个实验
离散数学(屈婉玲版)第一章部分习题分解
离散数学实验报告()
《离散数学》试习题及答案
离散数学题目大汇总
离散数学考试题详细答案
离散数学实验一
离散数学题库及答案
离散数学实验指导书
离散数学实验报告一
离散数学实验
离散数学实验报告
离散数学集合的运算实验报告
离散数学实验一：命题逻辑(1).
离散数学实验报告
相关主题
文本预览