总复习提纲：
1．判断一个数a 是否为素数的算法，最多、一般情况下、至少要作多少次除法运算？要达到最少的次数应该附加什么？依据是什么（素数定义、性质(Th9.2.2)）P184、P185
观察一正整数a 是否素数，要用小于a 大于1的整数一一来试除吗？不要。 定理9.2.2 若a 是大于1的整数，而所有小于或等于a 的素数都不能整除a ，则a 是素数。
令π(x )表示不超过x 的素数个数，可以证明
0)(lim =+∞→x
x x π 它表明了:尽管素数个数无穷多，但它比起正整数的个数来少得很多。 2．欧几里德算法思想及时间复杂度问题？P201
本质上是用辗转相除把求两个正整数最大公因数的问题化为求两个较小整数的最大公因数，直到两个整数中的一个为0。
现将定理9.3.2欧几里德算法以伪码形式给出如下： Euclid (a ，b ：整数) if b =0 then return a while b >0
{ r ←a (mod b ) a ←b b ←r } return a
算法中过程的每一步都是a 用b 代替，而b 用a (mod b )代替。只要b >0，这个过程就重复下去，当b =0时算法终止，此时a 的值也就是这一过程的非零余数，即为a 和b 的最大公因数。
在欧几里德算法中基本操作是除法，为研究欧几里德算法的时间复杂性，需要求出算法中所使用的除法次数，下面拉梅定理给出解答。 证明：如下定理
定理10.2.1 设a 和b 是满足a ≥b 的正整数，则欧几里德算法求得(a ，b )而使用除法的次数小于或等于b 的十进制位数的5倍。 3．两个n 位的二进制整数a 和b 的乘法算法 P204
可按下面等式进行计算：
ab =a ∑-=1
2n i i i b =∑-=1
2)(n i i i ab
计算过程：如下(核心思想：将ab i 当作一个整体，做平移，再做加法，而不是直接做乘法运算)
首先注意在b i =1时ab i =a ，而b i =0时ab i =0。每当用2乘一项时，结果都是把该项的二进制展开向左移一位并在尾部加上一个0，因此，可把ab i 的二进制展开向左移i 位，再在尾部加上i 个0来计算(ab i )2i 。最后，将n 个整数(ab i )2i ，
i =0，1，…，n -1，相加得到ab 。
两个正整数a 和b 二进制展开的乘法算法： mul (a ，b )
for i← 0 to n-1
if b i=1 then c i← a左移i位
else c i← 0 //c0c1…c n-1是部分积
p ← 0
for i← 0 to n-1
p ← p+c i//p是ab的值
读者不难得出：移位个数是O(n2)，位加法个数是O(n2)，这是因为，所有n个整数(ab i)2i，i=0，1，…，n-1，需要0+1+2+…+n-1次移位，故移位数是O(n2)，而将(ab i)2i从i=0到i = n+1加起来，需要做一次n位整数、(n+1)位整数、…以及2n位整数的加法，这些加法都需要O(n)次位相加，因此完成所有n个数加法需要O(n2)次位加法。
4．最常用的产生伪随机数的方法是线性同余法。P220
它是递归定义的：
x n+1=(ax n+c)(mod m) （1）
U i=x n/m （2）
其中，m称为模数，a为乘数，c为增量，x0为种数，且2≤a 分析此算法的特点： 5．RSA公钥系统 P222 RSA公钥系统是由MIT的三名研究人员：瑞弗斯特(Ron Rivest)、沙米尔(Adi Sharmir)和阿德莱门(Len Adleman)于1978年联合提出的，它的安全性是基于大整数因数分解困难问题，至今没有有效的算法。 RSA加密算法的过程： ①选取两素数p和q(保密) ②计算n = pq(公开)，φ(n)=(p-1)(q-1)(保密) ③选取加密公钥e，满足(e，φ(n))=1 ④计算解密私钥d，满足de≡1(modφ(n)) 使用RSA加密之前，应将明文数字化，并取长度小于log n位的数字作为明文块。 加密算法c=E(m)=m e(mod n) 解密算法D(c)=c d(mod n) 6．最短路径算法 P325 1959年，荷兰数学家E.W.Dijkstra给出了求某结点到其他各结点的最短链的一个标记算法。 Dijkstra标记算法： (1)令w(v i，v j)←∞，(v i，v j)?E(G) l(u0)←0 l(v)←∞，v≠u0 S←{u0} i←0 //初始化标记 (2)W hile v?S if l(u i)+w(u i，v) then l(v)←l(u i)+w(u i，v)//更新不在S中结点的标记 u i +1←min l (v ) 取最小值的且不属于S 中结点u i +1 S ← S ∪{u i +1} //给S 中添加带最小标记的结点 若i =n -1，算法结束；否则i ←i +1，转至(2) 由上述算法知： ① S 中各结点的标记l (u )即是从u 0到u 的距离。又因n <∞，经有限步后，每个结点都标记了，从而得到了从u 0到各结点的最短链。 ② 算法和时间复杂性是O (n 2)，所以是有效算法。 说明： 1． 算法中的标记设计l (u )问题。在算法的运行过程中，依次为各点作标记， 当经历到此点时为它作一个标记，未经历到时，标记为∞。标记的论据为 min{ l (u i )+w (u i ，v ),l (v )}. 当没有直接的边相连时，不作标记。 2． 提供了一个图的搜索算法，并且是对图的遍历算法，经过了图的所有点。 集合S 作为搜索结果的表示，其形成过程标记了下次的搜索方向的起点， u i +1←min l (v ) S ← S ∪{u i +1} 搜索方向的边为(u i ，v )且v ?S ，随着搜索过程的进行，S 中的元素渐渐增多，当然不属于S 的元素渐渐减少。当所有的点都加入到其中时算法结束。 3． S 中的元素是有序的，唯一么？什么情况下不唯一？ 形成了一棵树。对图的点进行了排列(其结果为一个偏序)。 v 5 v 3 v 4 v 2 v 1 v 0 1 2 10 8 5 42 3 6 7．关键路算法 P326 关键路是通过求事件的最早期望完成时间和事件的最迟必须完成时间来实现的，为此定义： π+(v )={x |x ∈V ∧ 分别称π+(v )和π-(v )为结点v 的后继结点集合和v 的先驱结点集合。 ① 最早期望完成时间 从始点开始沿着最长路到达v i 所需时间，称为v i 的最早期望完成时间，记为TE (v i )， i =1.2，…，n 。于是 TE (v 1)=0 TE (v i )=) (max i j v v - ∈π{TE (v j )+w ji } i =2，3，…，n ②最迟必须完成时间 在保证终点v n 的最早期望完成时间TE (v n )不增加前提下，自始点v 1最迟到达v i 的时间，称为v i 的最迟必须完成时间，记为TL (v i )。 TL (v n )=TE (v n ) TL (v i )= ) (m in i j v v + ∈π {TL (v j )-w ij } i =1，2，…，n -1 ③松驰时间 TS (v i )=TL (v i )-TE (v i ) i =1，2，…，n 显然，TS (v i )≥0，i =1，2，…，n 关键路上的各结点的松驰时间均为0，即由松驰时间为0的结点构成关键路，因为任何工序延误了时间，整个工程项目就延误了时间。 算法的复杂性是O (n )。 4 v v 6 8．已知简单有向图G = A =??????? ?????????01000 1000000010 001010001 试求A 1，A 2， A 3 ，A 4，A 5。并说明A 4中各非0元素的含义。 3 v 5 图16.4.3 9．设图G 的邻接矩阵A 是 P335 A =? ? ??? ???? ???0001 101111000010 试求G 的可达矩阵P 。 10． 请描述：什么是代数结构？什么是半群、独异点、群？ 11． 请描述什么是代数结构之间的同态？对于代数结构V1 = y=(x ＋y)mod n, 这里Zn={0,1,…,n-1}．假设给定映射? :Z →Zn, ? (x)= (x)mod n, V2是否是V1的同态象？（验证? (x ＋y)= ?(x) ⊕ ? (y)） 12． 给定独异点 ， 请问，该独异点是否是循环独异点？ 13．请描述什么是一个群的子群？ 设 分析使用定理13.6.3来证明。 证明：显然S非空。对?x, y∈S，则存在n, m∈Z， x = a n，y = a m，则 x*y-1 = a n* (a m)-1 = a n-m， 且n-m∈Z，所以x*y-1 = a n-m∈S， 故由定理13.6.3可得， 14．对于三次对称群 证明： （使用定理13.6.4证明子群，参考课件上此陪集的计算结果，同余关系的证明可以利用定理证明aH=Ha，进而得到该子群是正规子群，正规子群的陪集关系是同余关系得到）。 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 《离散数学J》考试试卷（期中） 课程代码143140320命题单位学院：计算机学院信息教研室 学院:_______________班级:_____________姓名:_______________学号:____________ 1．将下列命题将其符号化。（4分） ①.李平不是不聪明，而是不用功。 假设p:李平聪明，q:李平用功 ②.如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。 假设p：我懂得希腊文，q：我了解柏拉图 2．在一阶逻辑中将下列命题符号化。（9分） ①.整数都是有理数，并不是每个有理数一定是整数，有些有理数不是整数。 假设I(x)：x是整数，Q(x)：x是有理数。 ②.某些汽车比所有的火车慢。 假设F(x)：x是火车。G(x)：y是汽车。H(x,y)：x比y快 ③.谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。 假设：M(x)表示“x是人”，K(x)表示“x游戏人生”，L(x)表示“x 一事无成”，H(x,y)表示“x主宰y”，N(x)表示“x是奴隶”。 3．试证明： (┐P∧(┐Q∧R))∨((Q∧R)∨(P∧R))=R(10分) 4．求公式G＝(P→Q)∧R的主析取范式和主合取范式。(12分) 5．先将些列论断符号化，再证明论断的正确性。（15分） 所有的大一学生都要学习英语；并非所有的大一学生都要学习离散数学；故有些学习英语的不学习离散数学。 假设谓词如下：P(x)：x是大一学生；Q(x)：x要学习英语； R(x)：x要学习离散数学。 6．某班学生50人，会排球的有40人，会篮球的35人，会足球的10人，以上三种运动都会的5人，都不会的没有，问只会两种运动的有几人？ 最新离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式，若，则 （0） （3）设是集合上的等价关系，是由诱导的上的等价关系，则. （1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价. （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）. (２) 写出的对偶式（）. （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）. （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的. （） (5)写出命题公式的两种等价公式( ）. 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）.（12分） （１）（１）仅当今晚有时间，我去看电影. （２）（２）假如上午不下雨，我去看电影，否则就在家里读书. （3）你能通你能通过考试，除非你不复习. （４）（４）并非发光的都是金子. （５）（５）有些男同志，既是教练员，又是国家选手. （６）（６）有一个数比任何数都大. 四、设，给定上的两个关系和分别是 （１）（１）写出和的关系矩阵.（２）求及（1２分） 五、求的主析取范式和主合取范式.（１０分） 六、设是到的关系，是到的关系，证明：（8分） 七、设是一个等价关系，设对某一个，有 ，证明： 也是一个等价关系.（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败.所以，如果丙获胜，则丁不失败. 九、（１０分） 用谓词推理理论来论证下述推证. 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）.有的人不爱骑自行车，因而有的人不爱步行 (论 域是人). 十、(8分) 利用命题公式求解下列问题. 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我.” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,， 若 C B C A ∧?∧， 则B A ? ( ? ) （3）设R 是集合A 上的等价关系， L 是由R A 诱导的A 上的等价关系，则 L R =. ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价. （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为 ( }},{{φφ). (２) 写出)()(R P Q P →∧∨的对偶式（ )()(R P Q P ∧?∨∧ ）. （３）设A 是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（我校本科生的班级数 ），同学小王所在 的等价类为（小王所在的班的集合）. （４）设},,,{},,,{><><==3121321R A 是A 上的关系，则R 满足下列性质的哪 几条：自反的，对称的，传递的，反自反的，反对称的. （ 传递的，反自反的，反对称的 ） (5)写出命题公式Q P ?的两种等价公式 ( )()()()(P Q Q P P Q Q P ∨?∧∨?→∧→）. 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题 （４）（５）（６）.（12分） （３）（１）仅当今晚有时间，我去看电影. 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷 题 序 一 二 三 四 五 总分 成 绩 签 名 一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}P(A) B ．{a}P(A) C ．{{a}}P(A) D ．{{a}}P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．01 B ．0011100000 C ．00 D ．00 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨q D ．r →p ∨q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ C ） A ．┐(x)A(x)┐A B ．(x)(B →A(x))B →(x)A(x) C ．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D ．(x)(y)(A(x)→B(y))( x)A(x)→(y)B(y) 7、若s={1,2,3,4}，S 上关系R 的关系图为： 则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={ 《离散数学》期末考试题(B) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )，)(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为 ( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 2010-2011学年第一学期离散数学期中考试试卷答案 一、（本题满分12分）在命题逻辑中将下列命题符号化。 （1）小王边走路边听音乐。（2）除非a能被2整除，a才能被4整除。 （3）派小张、小李中的一人去开会。（4）小张和小李是同学。 （5）今天是星期一仅当明天是星期二。（6）若2+2≠4，则3+3≠6；反之亦然。 解：（1）令p：小王走路；q：小王听音乐。符号化为p∧q （2）令p：a能被2整除；q：a能被4。符号化为q→p （3）令p：派小张去开会；q：派小李去开会。符号化为（p∧┐q）∨（┐p∧q） （4）令p：小张和小李是同学。符号化为p （5）令p：今天是星期一；q：明天是星期二。符号化为p→q （6）令p：2+2=4；q：3+3=6。符号化为┐p?┐q 二、（本题满分12分）在一阶逻辑中将下列命题符号化。 （1）有的有理数能被2整除。（2）没有不犯错误的人。 （3）人都不一样高。（4）说火车比汽车跑的快是不对的。 （5）4>2与3≥1互为充要条件。（6）除非李键是东北人，否则他一定怕冷。解：（1）令F(x)：x为有理数；G(x)：x能被2整除。符号化为?x(F(x)∧G(x)) （2）令F(x)：x是人，G(x)：x犯错误，则命题符号化为：?x（F（x）→G(x)） （3）令F(x)：x是人；H(x,y)：x与y一样高。符号化为?x?y（F（x）∧F（y）→┐H（x，y））（4）令F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快，┐?x?y（F（x）∧G（y）→H（x，y））（5）令F(x,y)：x>y，G(x,y):x≥y，a:4，b:2，c:3，d:1。符号化为F(a,b)?G(c,d) （6）令F(x)：x是东北人，G(x)：x怕冷，a：李键，符号化为┐G（a）→F（a） 三、（本题满分8分）给出公式(q →r) ∧ ( p→p)的真值表并求出成真赋值和成假赋值。解：真值表如下 成真赋值：000、001、011、100、101、111；成假赋值：010、110 四、（本题满分10分）设p:2能整除5，q:太阳从西方升起，r:一年分四季。求下列复合命题的真值： （1）((p ∨q) → r)∧(r→ (p ∧q)) （2）((┐q ?p) → (r ∨p)) ∨ ((┐p ∧┐q) ∧r) 解：由题意，p、q、r的真值分别为0、0、1。（1）的真值为0；（2）的真值为1。 五、（本题满分12分）使用等值演算法判断公式下列公式的类型。 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷 一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}∈P(A) B ．{a}?P(A) C ．{{a}}∈P(A) D ．{{a}}?P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．1000000001 B ．0011100000 C ．0111001110 D ．0111101110 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ： 你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨?q D ．r →p ∨?q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ C ） A ．┐(?x)A ?(?x)┐A B ．(?x)(B →A(x))?B →(?x)A(x) C ．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D ．(?x)(?y)(A(x)→B(y))?( ?x)A(x)→(?y)B(y) 7、若s={1,2,3,4}，S 上关系R 的关系图为： 则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={ 离散数学-期末考试卷-A卷 东莞理工学院城市学院（本科）试卷（A卷） 2013-2014学年第一学期 开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场 科目：离散数学，班级：软工本2012-1、2、3 姓名：学号： 题序一二三四总分 得分 A评 卷人 一、单项选择题（每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. 下述不是命题的是( ) A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( ) A. 永假的 B. 永真的 C. 可满足的 D. 析取范式 3. 命题公式﹁B→﹁A等价于( ) A. ﹁A∨﹁ B B. ﹁(A∨B) C. ﹁A∧﹁ B D. A→B 4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．?P∧Q B．P∧?Q C．P→?Q D．P∨?Q 5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．?x(A(x))∧B(x) B．??x( A(x)→?B(x) ) C．??x( A(x)∧B(X)) D．??x( A(x)∧?B(x) ) 6. 设有A={a,b,c}上的关系R={ 7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>} B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 8．设简单图G所有结点的度数之和为10，则G一定有（） A．3条边B．4条边C．5条边 D．6条边 9．下列不．一定是树的是（） A．每对结点之间都有通路的图 B．有n个结点，n-1条边的连通图 C．无回路的连通图D．连通但删去一条边则不连通的图 10．下列各图中既是欧拉图，又是哈密顿图的是（） 离散数学期中考试试卷 班级————姓名————学号———— 一、单项选择题（每题４分，共３２分。） 1、前提┐P∨Q, ┐Q∨R, ┐R的结论是（）。 A. Q B. ┐P C. P∨Q D. ┐P→R 2、下列语句为命题的是（）。 Ａ．暮春三月，江南草长。 Ｂ．这是多么可爱的风景啊！ Ｃ．大家想做什么，就做什么，行吗？ Ｄ．请勿践踏草坪！ 3、下列复合命题为真命题的是（）。 A．如果３＋３≠６，则３是奇数。 B．３是有理数当且仅当加拿大在亚洲。 C．只要乌鸦是黑色的，就有中国是世界上面积最大的国家。 D．２是偶素数是不对的。 ４、下列关于谓词公式的论述不正确的是（）。 A．闭式在任何解释下都是命题。 B．可满足式是指存在一个解释使得在该解释下对任一赋值公式都为真。 C．命题公式中的重言式的代换实例是永真式。 D．命题公式中的矛盾式的代换实例是矛盾式。 ，Ｂ＝P(P(A))，以下不正确的是（）。 Ａ．｛｝∈Ｂ Ｂ．｛｝∈Ｂ Ｃ．｛｝包含于Ｂ Ｄ．｛｛｛｝｝｝包含于Ｂ ６、设集合｛１，２，３｝，下列关系Ｒ中不是等价关系的是（）。 Ａ．Ｒ＝｛（１,１），（２,２），（３,３）｝ Ｂ．Ｒ＝｛（１,１），（２,２），（３,３）,（３,２），（２,３）｝ Ｃ．Ｒ＝｛（１,１），（２,２），（３,３）, （1, 4）｝ Ｄ．Ｒ＝｛（１,１），（２,２），（１,２）,（２,１），（１,３），（３,１）,（３,３），（３,２）,（２,３）｝ ７、对于如下某个偏序集的哈斯图，其中集合{a,b,c,e}的最大元是（）。 A．c B．d C．e D．无 ８、命题公式A和B是等值的，是指（）。 A．A和B有相同的命题变项。 B．A和B都是可满足的。 C．当A对某一赋值为真时，B对该赋值也为真。 D．A和B有相同的真值表。 二、填空题（每题３分，共15 分。） 1、设R为非空集合A上的二元关系，如果R满足（）、（）、（），则称R为A上的一个偏序关系。 ２、若集合A={1, 2, 3}上的二元关系R1和R2的关系图如下所示， 则R1o R2 =（），R2o R1=（）。 ３、用P和P∧Q同时代入合式公式P→┐(P∨Q)中的P和Q,所得代换实例为（）。 4、设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。 ５、P({Φ,1}) = _____________________________________。 三、计算题（每题8分，共16分） 1．求下面公式的主析取范式和主合取范式。 ( →) r p→ q 2．求集合A={a，b，c}的所有划分和他们相应的等价关系。 安徽大学2006-2007学年第1学期 《离散数学》期末考试试卷（A卷） （时间120分钟） 开课院（系、部）姓名学号. 一、选择题（每小题2分，共20分）1．下列语句中，哪个是真命题（）A、 4 2= + x； B、我们要努力学习； C、如果ab为奇数，那么a是奇数，或b是偶数； D、如果时间流逝不止，你就可以长生不老。 2．下列命题公式中，永真式的是（） A、P Q P→ →) (； B、P P Q∧ → ?) (； C、Q P P? ? ∧) (； D、) (Q P P∨ →。3．在谓词逻辑中，令) (x F表示x是火车；) (y G表示y是汽车；) , (y x L表示x比y快。 命题“并不是所有的火车比所有的汽车快”的符号表示中哪些是正确的（） I.)),()()((y x L y G x F y x →∧??? II.)),()()((y x L y G x F y x ?∧∧?? III. )),()()((y x L y G x F y x ?→∧?? A 、仅I ； B 、仅III ； C 、I 和II ； D 、都不对。 4．下列结论正确的是：（ ） A 、若C A B A =，则 C B =； B 、若B A B A ?，则B A =； C 、若C A B A =，则C B =； D 、若B A ?且D C ?，则D B C A ?。 5．设φ=1A ，}{2φ=A ，})({3φρ=A ，)(4φρ=A ，以下命题为假的是（ ） A 、42A A ∈； B 、31A A ?； C 、24A A ?； D 、34A A ∈。 6．设R 是集合},,,{d c b a A =上的二元关系， },,,,,,,,,,,{><><><><><><=b d d b a c c a a d d a R 。下列哪些命题为真（ ） I.R R ?是对称的 II. R R ?是自反的 III. R R ?不是传递的 A 、仅I ； B 、仅II ； C 、I 和II ； D 、全真。 离散数学考试题详细答案 离散数学考试题(后附详细答案) 一、命题符号化（共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）).离散数学期末试题
《 离散数学》期中考试试卷(2006—2007学年第2学期)
最新离散数学期末考试试卷(A卷)
离散数学期末试题及答案完整版
08计算机《离散数学》期中试卷答案
【浙江工商大学】《离散数学》期末考试题(B)
河海大学文天学院09级离散数学期中考试试卷答案
离散数学期末考试试题及答案
离散数学期末试卷A卷及答案
离散数学期末考试试题及答案
离散数学期末试卷及答案
《离散数学》期末考试试题
08计算机《离散数学》期中试卷答案
离散数学-期末考试卷-A卷
离散数学期中考试
大学《离散数学》期末考试试卷及答案-(1)
离散数学考试题详细答案
相关主题
文本预览