别吵吵吻我
范文一：四川大学离散数学试题
离散数学模拟试题1
一. 单项选择题 (每小题1.5分, 共30分)
1. 永真命题公式( )
① 只存在主析取范式; ②只存在主合取范式;
③既存在主析取范式也存在主合取范式; ④都不对.
2. 下列代数系统中消去侓不成立的是( )
①. 群; ②含幺半群; ③整环; ④分配格.
3. 在4个元素的集合上可定义的满射有( ) 个
①4; ②12; ③16 ④24
4. 在整环和格的定义中对运算都要求满足的性质是( )
① 及收律; ②幂等律; ③交换律; ④分配律.
5. 下面说法中正确的是( )
① 半群都有幂等元; ②. 剩余类环 ③. 整数加法群 6.Z 5为模5剩余类集, 定义f: Z5→Z 5如下:f(x)=2x+1,则f0f( ). ①不是函数; ②不是单射; ③是置换; ④不是满射(0:1;1:3;2:0;3:2;4:4) 7. 下面图中可以具有边数最多的是( ) (114=38*3, 100=10*10,120=16*15/2,100=10*10,114=38*3,110=44*5/2 ) ① 40阶的简单连通平面图; ②K 10,10; ③K 16; ④44阶的5度正则图 8. 下面关于集合基数正确的说法是( ) ① 没有最大的基数集; ②. 任何集合都存在与它等势的真子集; 确③没有最小的基数; ④有理数集合与实数集合等势 9. 下面图中, 可以割边的图是( ) ①K 10,10; ②欧拉图; ③平面图; ④哈密顿图. 10. 在4个元素的集合上可定义的等价关系有( ) 个 ①4; ②8; ③12 ④15. 11. 群 ① 没有平凡子群; ②是循环群; ③是置换群; ④不存在. 12. 设R 是A 上的二元关系, 且R0RUR=R,则( ) ①r?=R;②S( R )=R;③t( R )=R;④R=IA . 13. ①a ∨b=b∧c; ②a ∧c=a∨b; ③b ∧a=a∨c; ④a ∨b=c∧b 14. 谓词合适公式同时又是命题合适公式时, 公式中必无( ) ①自由变量; ②约束变量; ③个体常量; ④函数. 15. 设T 是G 的生成树, 则( ) ①G 的回路必含T 的边; ②G 的回路必不含T 的边; ③G 的割边必含T 的边; ④G 的割边必不含T 的边. 16. 设18阶简单连通平面图G 有35条边, 则最多能为它增加( ) 条边 使其仍能保持是简单平面图. ① 13; ②..18; ③.20; ④.25. 17. 下式中( ) 是永真的. ①(P∧Q) →(P∨Q) ；②(P→Q) ∧(P∨Q) ； ③(P→Q) →(P?Q) ；④(P∨Q) →(P→Q). 18. 下面在集合论和逻辑学中正确的公式有( , ) ① P ∨～P ?P ∧～P; ②2A U2B =2AUB ; ③?x(A(x) →B(x)) ?～?xA(x)∨?x B(x); ④A ⊕B=A⊕C ?B=C; 19. 下面可由拉格朗日定理推出的结论是( ) ①每个群都有循环子群; ②素数阶的群是循环群; ③群中方程有解; ④群的同态核是群的正规子群. 20. 下面能够符合既无割点也无割边的图类是( ) ①. 树; ②欧拉图; ③哈密顿图; ④二部图. 二. 计算题(每题6分, 共36分) 1. 求剩余类环 2. 如果一个n 阶简单平面图又是自补图时, 求n 的可能值。 3. 写出(～P ?R) ∧(Q→～R) 的主析取范式。 4. 设A={a,b,c,d,e},求该集合元素a 和b 在同一个等价类中的等价关系数目。 5. 设G 是n 阶3度正则平面图, 求要给它新加多少边才可能使它成为自对偶图。 6. 写出置换群 四．推理与证明题（共34分） 1设R 是集A 上的等价关系，证明对任何正整数n,R n 也是等价关系。（8分） 2. 证明连通图G 其对偶图是平面二部图当且仅当G 是平面欧拉图。（9分） 3证明：Q →(P→R) ，(R∨S) →B,A ∨ (S∧～B) ?～Q ∨～P ∨A 。（8分） 4. 证明<2a ,="" ⊕="">是交换群, 并判它的元素周期分布情况。（9分） 离散数学实验报告（1） 实验名称：构造任意合式公式的真值表 姓名：卢松 指导老师：冯伟森 年级：11级2班 学号：1143041172 学院：计算机 1、 功能 给出任意变元的合式公式，构造该合式公式的真值表。 1、 基本思想 仍然以用数值变量表示命题变元为前提规范，合式表示的表示。程序计算前将转换后的合式公式输入到本程序首个sign ：语句后的条件位置上。另外使用a[N]来表示合式公式中所出现的n 个命题变元。 一位数组a[N]除了表示n 个命题变元外，它还是一个二进制加法的模拟器，每当在这个模拟器中产生一个二进制数时，就相当于给各命题变元产生了一组真值指派。其中数值一表示真值为1，数值0表示真值为0. 2、 算法逻辑 （1） 将二进制加法模拟器a[N]赋初值，a i =0(i=1,2,…,n) 。 （2） 计算模拟器中所对应于模拟器所给出的一组真值指派 下合式公式的真值。（条件语句） （3） 输出真值表中对应于模拟器所给出的一组真值指派及 这组真值指派所对应的一行真值。 （4） 在模拟器a[N]中，模拟产生下一个二进制数值。 （5） 若a[N]中的数值等于2n ，则结束，否则转（2）。 3、 源程序 #include #define N 4 main() { int a[N]; int i,z; printf("构造任意公式的真值表"); printf("\n"); for(i=1;i<> { } sign: if(!(a[1]==1||a[2]==1)&&((a[1]==1||a[3]==1)||a[4]==1)) z=1; a[i]=0; printf("a[%d]=0 ",i); else z=0; for(i=N;i>=1;i--) printf("%4d",a[i]); printf(" |%4d\n",z); i=1; sing: } a[i]=a[i]+1; if(a[i]<2) goto="" sign;="" else="" a[i]="0;" i++;=""><=4) goto=""> 备注：本题是以~（P νQ ）Λ((PνR) νS) 为例子进行实验的。 4、 实验总结： 由于自己的技术问题只是验证了一组数据，因为时间紧迫所以来不及修改，课后会继续修改。从这次实验中学习到了很多，尤其是对真值表的判断条件，同时感觉到想像和实际操作之间的距离。 四川大学离散数学往年考试试题二 2 A {xx是整数且x 16}，下面哪个命题为假( )1(设。 A、{0,1,2,4} A; B、{,3,,2,,1} A; C、 A; D、{xx是整数且x 4} A。 2(设A , B { ,{ }}，则B,A是( )。 A、{{ }}; B、{ }; C、{ ,{ }}; D、 。 3(右图描述的偏序集中，子集{b,e,f}的上界为 ( )。 A、b,c; B、a,b; C、b; D、a,b,c。 4(设f和g都是X上的双射函数，则(f g)为( )。 A、f ,1 ,1 g,1; B、(g f),1; C、g,1 f,1; D、g f ,1 。 5(下面集合( )关于减法运算是封闭的。 }。 A、N ; B、{2xx I}; C、{2x,1x I}; D、{xx是质数 6(具有如下定义的代数系统 G,, ，( )不构成群。 A、G {1,10}，*是模11乘 ; B、G {1,3,4,5,9}，*是模11乘 ; C、G Q(有理数集)，*是普通加法 ; D、G Q(有理数集)，*是普通乘法。 7(设 G {2m 3nm,n I} ，*为普通乘法。则代数系统 G,, 的幺元为( )。 00,1,1 A、不存在 ; B、e 2 3; C、e 2 3; D、e 2 3。 8(下面集合( )关于整除关系构成格。 A、{2，3，6，12，24，36} ; B、{1，2，3，4，6，8，12} ; C、{1，2，3，5，6，15，30} ; D、{3，6，9，12}。 9(设V {a,b,c,d,e,f}， E { a,b , b,c , c,a , a,d , d,e , f,e }，则有向图 G V,E 是( )。 注:试题字迹务必清晰，书写工整。 本题6页，本页为第1页 教务处试题编号: 课程名称: 任课教师: 学号: A、强连通的 ; B、单向连通的 ; C、弱连通的 ; D、不连通的。 10(下面那一个图是欧拉图( )。 姓名: 11(在任何图中必定有偶数个( )。 A、度数为偶数的结点 ; B、入度为奇数的结点 ; C、度数为奇数的结点 ; D、出度为奇数的结点 。 12(含有3个命题变元的具有不同真值的命题公式的个数为( )。 A、2; B、3; C、22; D、232332。 13(下列集合中哪个是最小联结词集( )。 A、{ , }; B、{ , }; C、{ , }; D、{ , , }。 14(下面哪个命题公式是重言式( )。 A、(P Q) (Q R); B、(P Q) P; C、( P Q) (P Q); D、 (P Q) P。 15(在谓词演算中，下列各式哪个是正确的( )。 A、,x,yA(x,y) ,y,xA(x,y); B、,x,yA(x,y) ,y,xA(x,y); C、,x,yA(x,y) ,y,xA(x,y); D、A(a) ,xA(x)。 二、多项选择题(本大题共5小题，每题2分，共10分 )在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。 评阅教师 得分 1、设A,{1,2,3}，则右图所示A上的关系具有( )。 1).自反性 2).反自反性 4).反对称性 5).传递性 3).对称性 3 2、下列语句是命题的有( )。 1). 明年中秋节的晚上是晴天; 2).x,y 0; 本题8页，本页为第2页 课程名称: 任课教师: 学号: 姓名: 3). xy 0当且仅当x和y都大于0; 4).我正在说谎。 3、A，B为二合式公式，且A B，则( )。 **1).A B为重言式; 2).A B; **3).A B; 4).A B; 5).A B为重言式。 4、右图所示的图一定不是( )。 1).平面图 2).二部图 3).欧拉图 4).哈密而顿图 5).树 5、设R和S是集合A上的任意关系，下列命题不成立( )。 1).若R和S是自反的，则R0S也是自反的。 2).若R和S是反自反的，则R0S也是反自反的。 3).若R和S是对称的，则R0S也是对称的。 4).若R和S是传递的，则R0S也是传递的。 评阅教师 得分 三、填空题(本大题共5小题，每题2分，共10分) 1、P:你努力，Q:你失败。“除非你努力，否则你将失败”的翻译为 “虽然你努力了，但还是失败了”的翻译为 。 }，则 2、设A={2，3，4，5，6}上的二元关系R { x,y |x y x是 质数 (枚举法)。 R的关系矩阵MR= 本题8页，本页为第3页 。 3、设A={1，2，3}，则A上既不是对称的又不是反对称的关系R= ;A上既是对称的又是反对称的关系R= 。 4、设代数系统，其中A={a，b，c}, 则幺元是 ;是否有幂等性 。 5、n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是 。 评阅教师 得分 四、演算题(本大题共4小题，每题10分，共40分 ) }, , ,1、设E(x1,x2,x3) (x1 x2) (x2 x3) (x1 x3)是布尔代 数 {0,1 试写出其主析取范式和主合取范式。 上的一个布尔表达式， 2、如下图所示的赋权图表示某七个城市 v1,v2, ,v7及预先算出它们之间的一些直接通信线路造价 (单位:万元)， 试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。 3、已知有如图的偏序关系，求出其子集A={b,c,d,e}的极大元、极小元、最大元、最小元、最小上界和最大下界。 4、设A {a,b,c}，A上的关系 { a,a , a,b , b,c , c,b }，求出 cb d r( ),s( )和t( )。 评阅教师 得分 五、证明题(本大题共2小题，共25分 ) 1、(12分)证明:(P (Q S))?( R?P)?Q R S 2、(13分) 如果集合A上的关系R和S是反自反的、对称的和传递的， 证明:R S是A上的等价关系。 7. 给定解释 I 和 I 中赋值 v 如下: }2, 1{=I D , 1=I a , 2=I b , 2) 1(=I f , 1) 2(=I f 1) 2, 1() 1, 1(==I I P P , 0) 2, 2() 1, 2(==I I P P , 1) (=x v , 1) (=y v 计算下列公式在解释 I 和赋值 I 中 v 下的真值。 解 (1) ) ))(), (()) (, ()) (, ((v x y f P b f x P x f a P I ∧∧ )) ()), ((()) (), (())) ((, (x v y v f P b f x v P x v f a P I I I I I I I I ∧∧= ) 1), 1(()) 2(, 1()) 1(, 1(I I I I I I f P f P f P ∧∧= 0011) 1, 2() 1, 1() 2, 1(=∧∧=∧∧=I I I P P P (2) ) ))(, ((v x y yP x I ?? ])2/[))(, ((])1/[))(, ((x v x y yP I x v x y yP I ?∧?= ]))2/][1/[))(, ((])1/][1/[))(, (((y x v x y P I y x v x y P I ∨= ]))2/][2/[))(, ((])1/][2/[))(, (((y x v x y P I y x v x y P I ∨∧ )) 2, 2() 2, 1(()) 1, 2() 1, 1((I I I I P P P P ∨∧∨= 1) 01() 01(=∨∧∨= (3)) ))))((), (() , (((v y f x f P y x P y x I →?? ))) 2(, ) 1(() 2, 1(())) 1(, ) 1(() 1, 1((I I I I I I I I f f P P f f P P →∧→= ))) 2(, ) 2(() 2, 2(())) 1(, ) 2(() 1, 2((I I I I I I I I f f P P f f P P →∧→∧ )) 1, 1() 2, 2(()) 2, 1() 1, 2(()) 1, 2() 2, 1(()) 2, 2() 1, 1((I I I I I I I I P P P P P P P P →∧→∧→∧→=01100) 10() 10() 01() 01(=∧∧∧=→∧→∧→∧→= 7. 给定解释 I 如下: }, {b a D I =, 1) , () , (==b b P a a P I I , 0) , () , (==a b P b a P I I 判断 I 是不是以下语句的模型。 解 (1))) , ((y x yP x I ?? 1) 10() 01()) , () , (()) , () , ((=∨∧∨=∨∧∨=b b P a b P b a P a a P I I I I (2))) , ((y x yP x I ?? 01001) , () , () , () , (=∧∧∧=∧∧∧=b b P a b P b a P a a P I I I I (3))) , ((y x yP x I ?? 0) 10() 01()) , () , (()) , () , ((=∧∨∧=∧∨∧=b b P a b P b a P a a P I I I I (4))) , ((y x P y x I ??? 10110) , () , () , () , (=∨∨∨=?∨?∨?∨?=b b P a b P b a P a a P I I I I (5)))) , () , (((x y P y x P y x I →?? )) , () , (()) , () , ((a b P b a P a a P a a P I I I I →∧→= )) , () , (()) , () , ((b b P b b P b a P a b P I I I I →∧→∧ 1) 11() 00() 00() 11(=→∧→∧→∧→= (6)111) , () , ()) , ((=∧=∧=?b b P a a P x x xP I I I 9. 用归结法证明: (1)?y (P (y ) → Q(y ))|=?x (?y (P (y ) ∧R (x , y ) →?z (Q (z ) ∧R (x , z ))) (2)?x (?y (S (x , y ) ∧ P(y )) →?y (Q (y ) ∧R (x , y ))), ??xQ (x ) |=?x ?y (S (x , y ) →?P (y )) (3)))) () , (() () ((y C y x S y x R x Q x ∧?→?∧?, ))) () , (() () ((y P y x S y x Q x P x →?∧∧?, )) () ((x R x P x ?→?=|)) () ((x C x P x ∧? (4))) () ((x Q x P x ∨?/|=) () (x xQ x xP ?∨? (5)) , (y x yP x ??/|=) , (y x xP y ?? 解 (1)?y (P (y ) → Q(y ))|=?x (?y (P (y ) ∧R (x , y ) →?z (Q (z ) ∧R (x , z ))) 由语句 ?y (P (y ) → Q(y )) 得到子句 ?P (y ) ∨ Q(y ) , ??x (?y (P (y ) ∧R (x , y ) →?z (Q (z ) ∧R (x , z ))) ???x (??y (P (y ) ∧R (x , y )) ∨?z (Q (z ) ∧R (x , z ))) ??x (?y (P (y ) ∧R (x , y )) ∧??z (Q (z ) ∧R (x , z ))) ??x (?y (P (y ) ∧R (x , y )) ∧?z (?Q (z ) ∨?R (x , z ))) ??x ?y ?z (P (y ) ∧R (x , y ) ∧(?Q (z ) ∨?R (x , z ))) 得到子句 P (b ) , R (a , b ) , ?Q (z ) ∨?R (a , z ) 。 构造子句集 {?P (y ) ∨ Q(y ) , P (b ) , R (a , b ) , ?Q (z ) ∨?R (a , z )}的一个反驳如下: ① ?P (y ) ∨ Q(y ) ② P (b ) ③ R (a , b ) ④ ?Q (z ) ∨?R (a , z ) ⑤ Q (b ) 由 ① {y /b } 和 ② ⑥ ?Q (b ) 由 ③ 和 ④ {z /b } ⑦ □ 由 ⑤ 和 ⑥ 因此, ?y (P (y ) → Q(y ))|=?x (?y (P (y ) ∧R (x , y ) →?z (Q (z ) ∧R (x , z ))) (2) ?x (?y (S (x , y ) ∧ P(y )) →?y (Q (y ) ∧R (x , y ))), ??xQ (x )|=?x ?y (S (x , y ) →?P (y )) ?x (?y (S (x , y ) ∧ P(y )) →?y (Q (y ) ∧R (x , y ))) ??x (?y (S (x , y ) ∧ P(y )) →?z (Q (z ) ∧R (x , z ))) ??x ?z ?y (S (x , y ) ∧ P(y ) →Q (z ) ∧R (x , z )) ??x ?z ?y (?(S (x , y ) ∧ P(y )) ∨(Q (z ) ∧R (x , z ))) ??x ?z ?y ((?S (x , y ) ∨?P (y )) ∨(Q (z ) ∧R (x , z ))) ??x ?z ?y ((?S (x , y ) ∨?P (y ) ∨Q (z )) ∧ (?S (x , y ) ∨?P (y ) ∨ R(x , z ))) 得到子句 ?S (x , y ) ∨?P (y ) ∨Q (f (x )) 和 ?S (x , y ) ∨?P (y ) ∨ R(x , f (x )) 。 由语句 ??xQ (x ) 得到子句 ?Q (x ) 。 ??x ?y (S (x , y ) →?P (y )) ???x ?y (?S (x , y ) ∨?P (y )) ??x ?y (S (x , y ) ∧ P(y )) 得到子句 S (a , b ) 和 P (b ) 。 构造子句集 {?S (x , y ) ∨?P (y ) ∨Q (f (x )) , ?S (x , y ) ∨?P (y ) ∨ R(x , f (x )) , ?Q (x ) , S (a , b ) , P (b )} 的一个反驳如下: ① ?S (x , y ) ∨?P (y ) ∨Q (f (x )) ② ?S (x , y ) ∨?P (y ) ∨ R(x , f (x )) ③ ?Q (x ) ④ S (a , b ) ⑤ P (b ) ⑥ ?S (x , y ) ∨?P (y ) 由 ① 和 ③ {x /f (x )} ⑦ ?P (b ) 由 ④ 和 ⑥ {x /a , y /b } ⑧ □ 由 ⑤ 和 ⑦ 因此, ?x (?y (S (x , y ) ∧ P(y )) →?y (Q (y ) ∧R (x , y ))), ??xQ (x ) |=?x ?y (S (x , y ) →?P (y )) (3)由语句 ))) () , (() () ((y C y x S y x R x Q x ∧?→?∧?得到子句 )) (, () () (x f x S x R x Q ∨∨?, )) (() () (x f C x R x Q ∨∨? 由语句 ))) () , (() () ((y P y x S y x Q x P x →?∧∧?得到子句 ) (a P , ) (a Q , ) () , (y P y a S ∨?; 由语句 )) () ((x R x P x ?→?得到子句 ) () (x R x P ?∨?; 由语句 )) () ((x C x P x ∧??得到子句 ) () (x C x P ?∨?。 构造子句集 {)) (, () () (x f x S x R x Q ∨∨?, )) (() () (x f C x R x Q ∨∨?, ) (a P , ) (a Q , ) () , (y P y a S ∨?, ) () (x R x P ?∨?, ) () (x C x P ?∨?}的一个反驳如下: ⑴ )) (, () () (x f x S x R x Q ∨∨? ⑵ )) (() () (x f C x R x Q ∨∨? ⑶ ) (a P ⑷ ) (a Q ⑸ ) () , (y P y a S ∨? ⑹ ) () (x R x P ?∨? ⑺ ) () (x C x P ?∨? ⑻ )) (() () (a f P a R a Q ∨∨? 由 ⑴ {x /a }和 ⑸ {y /f (a )} ⑼ ) (a R ? 由 ⑶ 和 ⑹ {x /a } ⑽ )) (() (a f P a R ∨ 由 ⑷ 和 ⑻ ⑾ )) ((a f P 由 ⑼ 和 ⑽ ⑿ )) (() (a f C a R ∨ 由 ⑵ {x /a }和 ⑷ ⒀ )) ((a f C 由 ⑼ 和 ⑿ ⒁ )) ((a f P ? 由 ⑺ {x /f (a )}和 ⒀ ⒂ □ 由 ⑾ 和 ⒁ 因此, ))) () , (() () ((y C y x S y x R x Q x ∧?→?∧?, ))) () , (() () ((y P y x S y x Q x P x →?∧∧?, )) () ((x R x P x ?→?=|)) () ((x C x P x ∧?。 (4))) () ((x Q x P x ∨?/|=) () (x xQ x xP ?∨? 由语句 )) () ((x Q x P x ∨?得到子句 ) () (x Q x P ∨,由语句 )) () ((x xQ x xP ?∨??得到子句 ) (a P ?和 ) (b Q ?。 显 然 , 由 这 三 个 子 句 只 能 归 结 出 子 句 ) (a Q 和 ) (b P 。 因 此 , )) () ((x Q x P x ∨?/|=) () (x xQ x xP ?∨? (5)?x ?yP (x , y ) |=/?y ?xP (x , y ) 由语句 ?x ?yP (x , y ) 得到子句 P (x , f (x )) 。 ??y ?xP (x , y ) ??y ?x ?P (x , y ) ,得到子句 ?P (g (y ), y ) 。 我们证明这两个子句没有归结子句。 若有代换 {x /t 1}和代换 {y /t 2}使得 t 1=g (t 2) f (t 1)= t2 可得出 t 1= g(f (t 1)) ,这是不可能的,因为这里的 =表示作为符号串的相同, g (f (t 1)) 的长度 =t 1的长度 + 6。 因此, ?x ?yP (x , y ) |=/?y ?xP (x , y ) 。 10. 每个一年级学生至少有一个高年级学生作为他的辅导员。 凡理科学生的辅导员皆是理科 学生。小王是理科一年级学生。因此,至少有一个理科高年级学生。 解 首先将前提和结论符号化。取个体域为学生的集合。 F (x ) :x 是一年级学生。 H (x ) :x 是高年级学生。 L (x ) :x 是理科学生。 G (x , y) :x 是 y 的辅导员。 a :小王。 “每个一年级学生至少有一个高年级学生作为他的辅导员”符号化为 ?x (F (x ) →?y (H (y ) ∧ G(y , x))) “凡理科学生的辅导员皆是理科学生”符号化为 ?x (L (x ) →?y (G (y , x) → L(y ))) “小王是理科一年级学生”符号化为 L (a ) ∧F (a ) 。 “至少有一个理科高年级学生”符号化为 ?x (L (x ) ∧ H(x )) 。 需要证明 ?x (F (x ) →?y (H (y ) ∧ G(y , x))) , ?x (L (x ) →?y (G (y , x) → L(y ))) , L (a ) ∧F (a ) |=?x (L (x ) ∧ H(x )) ?x (F (x ) →?y (H (y ) ∧ G(y , x))) ??x ?y (F (x ) →H (y ) ∧ G(y , x)) ??x ?y (?F (x ) ∨ (H (y ) ∧ G(y , x))) ??x ?y ((?F (x ) ∨H (y )) ∧ (?F (x ) ∨G (y , x))) 得出子句 ?F (x ) ∨H (f (x )) 和 ?F (x ) ∨G (f (x ), x) 。 ?x (L (x ) →?y (G (y , x) → L(y ))) ??x ?y (?L (x ) ∨?G (y , x) ∨ L(y )) 得出子句 ?L (x ) ∨?G (y , x) ∨ L(y ) 。 L (a ) ∧F (a ) 本身即为斯科伦范式,得出子句 L (a ) 和 F (a ) 。 将 ??x (L (x ) ∧ H(x )) 化为斯科伦范式 ?x (?L (x ) ∨?H (x )) , 得出子句 ?L (x ) ∨?H (x ) 。 构造子句集 {?F (x ) ∨H (f (x )) , ?F (x ) ∨G (f (x ), x) , ?L (x ) ∨?G (y , x) ∨ L(y ) , L (a ) , F (a ) , ?L (x ) ∨?H (x ) } 的一个反驳如下: ⑴ ?F (x ) ∨H (f (x )) ⑵ ?F (x ) ∨G (f (x ), x) ⑶ ?L (x ) ∨?G (y , x) ∨ L(y ) ⑷ L (a ) ⑸ F (a ) ⑹ ?L (x ) ∨?H (x ) ⑺ H (f (a )) 由⑴ {x /a } 和⑸ ⑻ G (f (a ), a ) 由⑵ {x /a } 和⑸ ⑼ ?G (y , a ) ∨ L(y ) 由⑶ {x /a } 和⑷ ⑽ L (f (a )) 由⑻和⑼ {y /f (a )} ⑾ ?L (f (a )) 由⑹ {x /f (a )} 和⑺ ⑿ □ 由⑽和⑾ 11. 任何喜欢步行的人都不喜欢乘汽车。 每个人或者喜欢乘汽车或者喜欢骑自行车。 有的人 不喜欢骑自行车。因此,有的人不喜欢步行。 解 首先将前提和结论符号化。取个体域为人的集合。 W (x ) :x 喜欢步行。 C (x ) :x 喜欢乘汽车。 B (x ) :x 喜欢骑自行车。 “任何喜欢步行的人都不喜欢乘汽车”符号化为 ?x (W (x ) →?C (x )) “每个人或者喜欢乘汽车或者喜欢骑自行车”符号化为 ?x (C (x ) ∨ B(x )) “有的人不喜欢骑自行车”符号化为 ?x ?B (x ) 。 “有的人不喜欢步行”符号化为 ?x ?W (x ) 。 需要证明 ?x (W (x ) →?C (x )) , ?x (C (x ) ∨ B(x )) , ?x ?B (x )|=?x ?W (x ) 将 ?x (W (x ) →?C (x )) 化为斯科伦范式 ?x (?W (x ) ∨?C (x )) , 得出子句 ?W (x ) ∨?C (x ) 。 ?x (C (x ) ∨ B(x )) 本身即是斯科伦范式,得出子句 C (x ) ∨ B(x ) 。 将 ?x ?B (x ) 化为斯科伦范式 ?B (a ) ,得出子句 ?B (a ) 。 将 ??x ?W (x ) 化为斯科伦范式 ?xW (x ) ,得出子句 W (x ) 。 构造子句集 {?W (x ) ∨?C (x ) , C (x ) ∨ B(x ) , ?B (a ) , W (x )} 的一个反驳如下: ① ?W (x ) ∨?C (x ) ② C (x ) ∨ B(x ) ③ ?B (a ) ④ W (x ) ⑤ ?C (x ) 由①和④ ⑥ B (x ) 由②和⑤ ⑦ □ 由③和⑥ {x /a } 26. 设 A , B , C , D 是任意四个集合,证明下列等式成立。 (1) ( A ?B ) ?(C ?D ) = (A ?C ) ?(B ?D ) 27. 求下列公式的主范式,进而判断其是否永真式、永假式、可满足式。 解 (1) r q p →∧?r q p ∨∧???) (r q p ∨?∨? r q p →∧?的主合取范式是 r q p ∨?∨,包含一个极大项,因此它是非永真的可满 足式。 (2) r q p →→) (r q p ∨∨???) ( r q p ∨?∧???) () () (r q r p ∨?∧∨? ) ) (() ) ((r q p p r q q p ∨?∨?∧∧∨?∧∨? ) () () (r q p r q p r q p ∨?∨?∧∨?∨∧∨∨? r q p →→) (的主合取范式是 ) () () (r q p r q p r q p ∨?∨?∧∨?∨∧∨∨, 包含了 三个极大项,因此它是非永真的可满足式。 (3) ) (q p q p ??→?∨?)) () (() (q p q p q p ∨∧?∨?∨?∨??? ) () (q p q p ∨∨?∨???q p q p ∨∧∧?) (q p ∨? ) (q p q p ??→?∨?的主合取范式为 q p ∨, 包含了一个极大项, 因此它是非永真 的可满足式。 (4) )) ((r q q p p →?∨→∨)) ((r q q p p ∨??∨∨?∨?1? )) ((r q q p p →?∨→∨的主合取范式为 1, 不包含任何极大项, 因此它是永真式。 (5) ) () (r q p r q p ?∧?→?∧∧→ )) (()) ((r q p r q p ?∧?∨??∧∧∨?? ) () () () (r q r q p r q r q p p p ?∧?∧∧∨∧∧∨?∧?∧?∨∧?? ) () (r q p r q p ∧∧∨?∧?∧?? ) () (r q p r q p ?∧?→?∧∧→的主析取范式为 ) () (r q p r q p ∧∧∨?∧?∧?, 包含了两个极小项,因此它是非永真的可满足式。 (6) ) (q p q p ?∨?∧∧ ) () ) (()) ((q p q p p q q p ?∨?∧∨?∧∧?∧∨? ) () () () (q p q p q p q p ?∨?∧∨?∧?∨∧∨? ) (q p q p ?∨?∧∧的主合取范式为 ) () () () (q p q p q p q p ?∨?∧∨?∧?∨∧∨, 包含了所有的四个极大项,因此它是永假式。 离散数学考试试题（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 ) ?M 0∧M 1 ?m 2∨m 3∨m 4∨m 5∨m 6∨m 7 二、（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 。 综上可知，tsr (R ) 是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，， (1)写出R 的关系矩阵。 (2)判断R 是不是偏序关系，为什么？ 解 (1) R的关系矩阵为： ' ' ' ' ?1 M (R ) = 0 0 0?1111? ? 1101?0101? ? 0011?0001?? (2)由关系矩阵可知，对角线上所有元素全为1，故R 是自反的；r ij ＋r ji ≤1，故R 是反对称的；可计算对应的关系矩阵为： ?1 M (R 2) = 0 0 0? 由以上矩阵可知R 是传递的。 1111? ? 1101? 0101?=M (R ) ? 0011?0001?? 五、（10分）设A 、B 、C 和D 为任意集合，证明(A －B ) ×C ＝(A ×C ) －(B ×C ) 。 证明：因为 ?(x ∈A ∧x ?B ) ∧y ∈C ?(x ∈A ∧y ∈C ∧x ?B ) ∨(x ∈A ∧y ∈C ∧y ?C ) ?(x ∈A ∧y ∈C ) ∧(x ?B ∨y ?C ) ?(x ∈A ∧y ∈C ) ∧?(x ∈B ∧y ∈C ) ? 所以，(A －B ) ×C ＝(A ×C －B ×C ) 。 六、（10分）设f ：A →B ，g ：B →C ，h ：C →A ，证明：如果h g f ＝I A ，f h g ＝I B ，g f h ＝I C ，则f 、g 、h 均为双射，并求出f 、g 和h 。 解 因I A 恒等函数，由h g f ＝I A 可得f 是单射，h 是满射；因I B 恒等函数，由f h g ＝I B 可得g 是单射，f 是满射；因I C 恒等函数，由g f h ＝I C 可得h 是单射，g 是满射。从而f 、g 、h 均为双射。 由h g f ＝I A ，得f ＝h g ；由f h g ＝I B ，得g ＝f h ；由g f h ＝I C ，得h ＝g f 。 －1 －1 －1 －1 －1 －1 七、（15分）设 证明 因G 有限，不妨设G ＝{a 1，a 2，…，a n }。由a *x ＝a *y ?x ＝y 得，若x ≠y ，则a *x ≠a *y 。于是可证，对任意的a ∈G ，有aG ＝G 。又因为运算*满足交换律，所以aG ＝G ＝Ga 。令e ∈G 使得a *e ＝a 。对任意的b ∈G ，令c *a ＝b ，则b *e ＝(c *a )*e ＝c *(a *e ) ＝c *a ＝b ，再由运算*满足交换律得e *b ＝b ，所以e 是关于运算*的幺元。对任意a ∈G ，由aG ＝G 可知，存在b ∈G 使得a *b ＝e ，再由运算*满足交换律得b *a ＝e ，所以b 是a 的逆元。由a 的任意性知，G 中每个元素都存在逆元。故G 是一群。 八、（20分）（1）证明在n 个结点的连通图G 中，至少有n －1条边。 证明 不妨设G 是无向连通图（若G 为有向图，可略去边的方向讨论对应的无向图）。 设G 中结点为v 1、v 2、…、v n 。由连通性，必存在与v 1相邻的结点，不妨设它为v 2（否则可重新编号），连接v 1和v 2，得边e 1，还是由连通性，在v 3、v 4、…、v n 中必存在与v 1或v 2相邻的结点，不妨设为v 3，将其连接得边e 2，续行此法，v n 必与v 1、v 2、…、v n -1中的某个结点相邻，得新边e n -1，由此可见G 中至少有n －1条边。 2（2）给定简单无向图G ＝ 图。 2证明 若n ≥C m 。 -1＋2，则2n ≥m －3m ＋6 （1） 2 若存在两个不相邻结点u 、v 使得d(u ) ＋d(v ) ＜m ，则有2n ＝ w ∈V ∑d (w ) ＜m ＋(m －2)(m －3) ＋m ＝m － 2 3m ＋6，与（1）矛盾。所以，对于G 中任意两个不相邻结点u 、v 都有d(u ) ＋d(v ) ≥m 。由定理10.26可知，G 是哈密尔顿图。 离散数考试试题（B 卷及答案） 一、（10分）使用将命题公式化为主范式的方法，证明(P →Q ) →(P ∧Q ) ?(Q →P ) ∧(P ∨Q ) 。 证明：因为(P →Q ) →(P ∧Q ) ??(?P ∨Q ) ∨(P ∧Q ) ?(P ∧?Q ) ∨(P ∧Q ) (Q →P ) ∧(P ∨Q ) ?(?Q ∨P ) ∧(P ∨Q ) ?(P ∧?Q ) ∨(?Q ∧Q ) ∨(P ∧P ) ∨(P ∧Q ) ?(P ∧?Q ) ∨P ?(P ∧?Q ) ∨(P ∧(Q ∨?Q )) ?(P ∧?Q ) ∨(P ∧Q ) ∨(P ∧?Q ) ?(P ∧?Q ) ∨(P ∧Q ) 所以，(P →Q ) →(P ∧Q ) ?(Q →P ) ∧(P ∨Q ) 。 二、（10分）证明下述推理： 如果A 努力工作，那么B 或C 感到愉快；如果B 愉快，那么A 不努力工作；如果D 愉快那么C 不愉快。所以，如果A 努力工作，则D 不愉快。 解 设A ：A 努力工作；B 、C 、D 分别表示B 、C 、D 愉快；则推理化形式为： A →B ∨C ，B →?A ，D →?C A →?D (1)A 附加前提 (2)A →B ∨C P (3)B ∨C T(1)(2)，I (4)B →?A P (5)A →?B T(4)，E (6)?B T(1)(5)，I (7)C T(3)(6)，I (8)D →?C P (9)?D T(7)(8)，I (10)A →?D CP 三、（10分）证明?x ?y (P (x ) →Q (y )) ?(?xP (x ) →?yQ (y )) 。 ?x ?y (P (x ) →Q (y )) ??x ?y (?P (x ) ∨Q (y )) ??x (?P (x ) ∨?yQ (y )) ??x ?P (x ) ∨?yQ (y ) ???xP (x ) ∨?yQ (y ) ?(?xP (x ) →?yQ (y )) 四、（10分）设A ＝{?，1，{1}}，B ＝{0，{0}}，求P (A ) 、P (B ) －{0}、P (B ) ⊕B 。 解 P (A ) ＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P (B ) －{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P (B ) ⊕B ＝{?，{0}，{{0}}，{0，{0}}⊕{0，{0}}＝{?，0，{{0}}，{0，{0}} 五、（15分）设X ＝{1，2，3，4}，R 是X 上的二元关系，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 是否是自反、反自反、对称、传递的。 解 (1)R 的关系图如图所示： (2) R的关系矩阵为： ?1 M (R ) = 1 1? 反自反的；由于矩阵不对称，R 不是对称的； 经过计算可得 10111011 0??0? 0??0?? (3)对于R 的关系矩阵，由于对角线上不全为1，R 不是自反的；由于对角线上存在非0元，R 不是 ?1 M (R 2) = 1 1? 10111011 0??0? =M (R ) ，所以R 是传递的。 ?0?0?? 六、（15分）设函数f ：R ×R →R ×R ，f 定义为：f ( (4)求复合函数f f 和f f 。 证明 (1)对任意的x ，y ，x 1，y 1∈R ，若f ( (2)对任意的∈R ×R ，令x ＝ －1－1 u +w u -w u +w u -w u +w ，y ＝，则f ( u -w >＝，所以f 是满射。 2 (3)f ()＝ －1－1 u +w u -w ，>。 22 －1 －1 (4)f f ( x +y +x -y x +y -(x -y ) ，>＝ 22 3 3 4 4 4 5 5 5 f f ( 七、（15分）给定群 3 试证 证明 对G 中任意元a 和b 。 因为a *b ＝(a *b ) ，所以a *a *b *b ＝a *(a *b ) *b ，即得a *b ＝(b *a ) 。同理，由a *b ＝(a *b ) 可得，a *b ＝(b *a ) 。由a *b ＝(a *b ) 可得，a *b ＝(b *a ) 。 于是(a *b )*(b *a ) ＝(b *a ) ＝a *b ，即b *a ＝a *b 。同理可得，(a *b )*(b *a ) ＝(b *a ) ＝a *b ，即b *a ＝a *b 。 由于(a *b )*b ＝a *b ＝b *a ＝b *(b *a ) ＝b *(a *b ) ＝(b *a ) *b ，故a *b ＝b *a 。 八、（15分）（1）证明在n 个结点的连通图G 中，至少有n －1条边。 证明 不妨设G 是无向连通图（若G 为有向图，可略去边的方向讨论对应的无向图）。 设G 中结点为v 1、v 2、…、v n 。由连通性，必存在与v 1相邻的结点，不妨设它为v 2（否则可重新编号），连接v 1和v 2，得边e 1，还是由连通性，在v 3、v 4、…、v n 中必存在与v 1或v 2相邻的结点，不妨设为v 3，将其连接得边e 2，续行此法，v n 必与v 1、v 2、…、v n -1中的某个结点相邻，得新边e n -1，由此可见G 中至少有n －1条边。 （2）试给出|V |＝n ，|E |＝(n －1)(n －2) 的简单无向图G ＝ 1 2 3 4 4 3 3 3 3 33 3 4 4 4 4 4 2 2 3 3 3 4 3 3 3 5 5 5 4 4 4 3 3 3 -1 33 -1-1 3 -1 22244 转载请注明出处范文大全网 » 四川大学离散数学试题范文二：四川大学离散数学实验报告(1)
范文三：DOC-四川大学离散数学往年考试试题二
范文四：离散数学期末真题
范文五：离散数学期末试题
