离散数学(三)

a t a t i m e an dA l lt h i ng si nt h ei r be i ng ar eg oo df o r so me t hi n 3-5.1 列出所有从X={a,b,c}到Y={s}的关系。

解：Z 1={<a,s>}Z 2={<b,s>} Z 3={<c,s>}Z 4={<a,s>,<b,s>} Z 5={<a,s>,<c,s>} Z 6={<b,s>,<c,s>}Z 7={<a,s>,<b,s>,<c,s>}3-5.2 在一个有n 个元素的集合上，可以有多少种不同的关系。

解 因为在X 中的任何二元关系都是X ×X 的子集，而X ×X=X 2中共有n 2个元素，取0个到n 2个元素，共可组成22n 个子集，即22|)(|n X X =⨯℘。

3-5.3 设A ＝{6：00，6：30,7：30，…, 9：30,10：30}表示在晚上每隔半小时的九个时刻的集合，设B={3,12,15,17}表示本地四个电视频道的集合,设R 1和R 2是从A 到B 的两个二元关系，对于二无关系R 1，R 2，R 1∪R 2，R 1∩R 2，R 1⊕R 2和R 1-R 2可分别得出怎样的解释。

解：A ×B 表示在晚上九个时刻和四个电视频道所组成的电视节目表。

R 1和R 2分别是A ×B 的两个子集，例如R 1表示音乐节目播出的时间表，R 2是戏曲节日的播出时间表，则R 1∪R 2表示音乐或戏曲节目的播出时间表，R 1∩R 2表示音乐和戏曲一起播出的时间表，R 1⊕R 2表示音乐节目表以及戏曲节目表，但不是音乐和戏曲一起的节日表，R 1-R 2表示不是戏曲时间的音乐节目时间麦。

3-5.4 设L 表示关系“小于或等于”，D 表示‘整除”关系,L 和D 刀均定义于解：L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>, <3,6>,<1,1>,<2,2>,<3,3>,<6,6>}D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} L ∩D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>}3-5.5对下列每一式，给出A 上的二元关系，试给出关系图：a){<x,y>|0≤x ∧y ≤3}，这里A={1,2,3,4}；b){<x,y>|2≤x,y ≤7且x 除尽y ,这里A ＝{n|n ∈N ∧n ≤10}c) {<x,y>|0≤x-y<3}，这里A={0,1,2,3,4}；d){<x,y>|x,y 是互质的}，这里A={2,3,4,5,6}解：a) R={<0,0>,<0,1>,<0,2>,<0,3>, <1,0>,<1,1>,<1,2>,<1,3>, <2,0>,<2,1>,<2,2>,<2,3>, <3,0>,<3,1>,<3,2>,<3,3>,} 其关系图b) R={<2,0>,<2,2>,<2,4>,<2,6>,<3,0>,<3,3>,<3,6>, <4,0>,<4,4>, <5,0>,<5,5>,i m e an dA l lt h in gs in th ei r be i ng ar eg oo df o rsa）若R1和R2是自反的，则R1○R2也是自反的；b）若R1和R2是反自反的，则R1○R2也是反自反的；c）若R1和R2是对称的，则R1○R2也是对称的；d）若R1和R2是传递的，则R1○R2也是传递的。

《离散数学》试题带答案试卷十四试题与答案一、 填空 10% （每小题 2分）1、 设>-∧∨<,,,A 是由有限布尔格≤><,A 诱导的代数系统，S 是布尔格≤><,A ，中所有原子的集合，则>-∧∨<,,,A ～ 。

2、 集合S={α，β，γ，δ}上的二元运算*为那么，代数系统<S, *>中的幺元是 , α的逆元是 。

3、 设I 是整数集合，Z 3是由模3的同余类组成的同余类集，在Z 3上定义+3如下：]3m od )[(][][3j i j i +=+，则+3的运算表为 ；<Z +,+3>是否构成群 。

4、 设G 是n 阶完全图，则G 的边数m= 。

5、 如果有一台计算机，它有一条加法指令，可计算四数的和。

现有28个数需要计算和，它至少要执行 次这个加法指令。

二、 选择 20% （每小题 2分）1、 在有理数集Q 上定义的二元运算*，Q y x ∈∀,有xy y x y x -+=*，则Q 中满足（ ）。

A 、 所有元素都有逆元；B 、只有唯一逆元；C 、1,≠∈∀x Q x 时有逆元1-x ； D 、所有元素都无逆元。

2、 设S={0，1}，*为普通乘法，则< S , * >是（ ）。

A 、 半群，但不是独异点；B 、只是独异点，但不是群；C 、群；D 、环，但不是群。

3、图 给出一个格L ，则L 是（ ）。

A 、分配格；B 、有补格；C 、布尔格；D 、 A,B,C 都不对。

3、 有向图D=<V , E>，则41v v 到长度为2的通路有（ ）条。

A 、0；B 、1；C 、2；D 、3 。

4、 在Peterson 图中，至少填加（ ）条边才能构成Euler图。

A 、1；B 、2；C 、4；D 、5 。

三、 判断 10% （每小题 2分）1、 在代数系统<A,*>中如果元素A a ∈的左逆元1-e a 存在，则它一定唯一且11--=e a a 。

3.9解：符号化：p：a是奇数. q：a是偶数. r：a能被2整除前提：(p→¬r),(q→r)结论：(q→¬p)证明：确。

方法2（等值演算法）(p→¬r)∧(q→r) →(q→¬p)⇔(¬p∨¬r)∧(¬q∨r) →(¬q∨¬p)⇔(p∧r) ∨(q∧¬r) ∨¬q∨¬p⇔((p∧r) ∨¬p)∨((q∧¬r) ∨¬q)⇔(r∨¬p) ∨(¬r∨¬q)⇔¬p∨(r∨¬r) ∨¬q⇔1即证得该式为重言式，则原结论正确。

方法3（主析取范式法）(p→¬r)∧(q→r) →(q→¬p)⇔(¬p∨¬r)∧(¬q∨r) →(¬q∨¬p)⇔(p∧r) ∨(q∧¬r) ∨¬q∨¬p⇔m0+ m1+ m2+ m3+ m4+ m5+ m6+ m7可知该式为重言式，则结论推理正确。

3.10. 解：符号化：p：a是负数. q：b是负数. r：a、b之积为负前提： r→(p∧¬q) ∨(¬p∧q)结论：¬r→(¬p∧¬q)方法1（真值法）证明：不正确。

方法2（主析取范式法）证明：(r→(p∧¬q) ∨(¬p∧q)) →(¬r→(¬p∧¬q))⇔¬ (¬r∨(p∧¬q) ∨(¬p∧q)) ∨(r∨(¬p∧¬q))⇔r∨(¬p∧¬q)⇔m0+m2+m4+m6+m7只含5个极小项，课件原始不是重言式，因此推理不正确3.11.填充下面推理证明中没有写出的推理规则。

*第三章消解原理3・1斯柯伦标准形内容提要我们约泄，本章只讨论不含自由变元的谓词公式(也称语句,sentences),所说前束范式均指前束合取范式。

全称量词的消去是简单的。

因为约左只讨论语句，所以可将全称量词全部省去，把由此出现于公式中的“自由变元”均约立为全称量化的变元。

例如A(x)实指VxA(x)0存在量词的消去要复杂得多。

考虑3xA(x)o(1)当A(x)中除x外没有其它自由变元，那么，我们可以像在自然推理系统中所做那样，可引入A(e/x),其中c为一新的个体常元,称c为斯柯伦(Skolem)常元，用A(c/x)代替3xA(x),但这次我们不把A(c/x)看作假设，详见下文。

(2)当A中除x外还有其它自由变元y】,…,yz那么3xA(x, y】,…,yj来自于Vyr- Vy n3xA(x,yi,…,y』，其中"存在的x”本依赖于yi/-\y n的取值。

因此简单地用A(e/x, yi/-\y n) 代替3xA(x, y h-j n)是不适当的，应当反映出x对九…,y n的依赖关系。

为此引入函数符号f,以A(f(yi,…,y』/x, yi,・・・,yn)代替3xA(x, yi/-\y n),它義示：对任意给立的yi,…,yn,均可依对应关系f确左相应的x ・使x,y“…,y n满足A’」这里f是一个未知的确左的函数，因而应当用一个推理中尚未使用过的新函数符号，称为斯柯伦函数」定理3.1 (斯柯伦定理)对任意只含自由变元x, yi,…,yn的公式A(x, yi,…,y) 3xA(x, yi/-\y n)可满足,当且仅当A(f(y h-\y n),儿…,yj可满足。

这里f为一新函数符号：当n = 0 时，f为新常元。

定义3.1设公式A的前束范式为Bo C是利用斯柯伦常元和斯柯伦函数消去B中量词 (称斯柯伦化)后所得的合取范式，那么称C为A的斯柯伦标准形(Skolem normal form)o 以下我们约定：斯柯伦标准形中，乞子句之间没有相同的变元。

离散数学试题带答案一、填空题1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝{3} ; ρ(A) - ρ(B)＝{3},{1,3},{2,3},{1,2,3}} .2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 22n.3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 .4. 已知命题公式G＝⌝(P→Q)∧R，则G的主析取范式是(P∧⌝Q∧R)5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3.6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A⋂B＝{4} ; A⋃B＝{1,2,3,4};A－B＝{1,2} .7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性, 对称性传递性.8. 设命题公式G＝⌝(P→(Q∧R))，则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0)9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则R1•R2 ={(1,3),(2,2),(3,1)} , R2•R1 = {(2,4),(3,3),(4,2)} _R12 ={(2,2),(3,3).10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A⨯B)| = .11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} ,A∩B ={x | 0≤x≤1, x∈R} , .13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} .14. 设一阶逻辑公式G = ∀xP(x)→∃xQ(x)，则G的前束范式是∃x(⌝P(x)∨Q(x)) .15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。