《离散数学》考试题库及答案
一、填空 20% （每小题2分）
1．设 （N：自然数集，E 正偶
A{x|(xN)且(x5)},B{x|xE且x7}
+
数） 则 。
AB
2．A，B，C表示三个集合，文图中阴影部分的集合表达式为
。
3．设P，Q 的真值为0，R，S的真值为1，则
A B
C
(P(Q(RP)))(RS)
的真值= 。
4．公式的主合取范式为
(PR)(SR)P
。
5．若解释I的论域D仅包含一个元素，则 在I下真值为
xP(x)xP(x)
。
6．设A={1，2，3，4}，A上关系图为
则 R = 。
2
7．设A={a，b，c，d}，其上偏序关系R的哈斯图为
则 R= 。
8．图的补图为 。
9．设A={a，b，c，d} ，A上二元运算如下：
* a b c d
a a b c d
b b c d a
c c d a b
d d a b c
那么代数系统 逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A． ； B．； {a}{{a}}{{}}{,{}} C． ； D． 。 {{},}{}{{}} 2、下列集合中相等的有（ ） A．{4，3}；B．{，3，4}；C．{4，，3，3}；D． {3，4}。 3、设A={1，2，3}，则A上的二元关系有（ ）个。 A． 2；B． 3；C． ； D． 。 3 2 2 33 22 3 4、设R，S是集合A上的关系，则下列说法正确的是（ ） A．若R，S 是自反的， 则是自反的； RS B．若R，S 是反自反的， 则是反自反的； RS C．若R，S 是对称的， 则是对称的； RS D．若R，S 是传递的， 则是传递的。 RS 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 R{s,t|s,tp(A)(|s||t|} 则P（A）/ R=（ ） A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； D．{{}，{2}，{2，3}，{{2，3，4}}，{A}}0 6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为（ ） 7、下列函数是双射的为（ ） A．f : IE , f (x) = 2x ； B．f : NNN, f (n) = C．f : RI , f (x) = [x] ； D．f :IN, f (x) = | x | 。 （注：I—整数集，E—偶数集， N—自然数集，R—实数集） 8、图 中 从v到v长度为3 的通路有（ ）条。 13 A． 0； B． 1； C． 2； D ． 3。 9、下图中既不是Eular图，也不是Hamilton图的图是（ ） 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4 度结点。 A．1； B．2； C．3； D．4 。 三、证明 26% １、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 ２、f和g都是群 12, 1 群。其中C= (8分) {x|xG且f(x)g(x)} 1 ３、G= 图，则， 由此证明彼得森图（Peterson）图是非平面图。（11分） e k(v2) k2 四、逻辑推演 16% 用CP规则证明下题（每小题 8分） 1、 ABCD,DEFAF 2、 x(P(x)Q(x))xP(x)xQ(x) 五、计算 18% 1、设集合A={a，b，c，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算 求出R的传递闭包t (R)。 （9分） 2、如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通 v,v,,v 127 信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分） 试卷一答案： 一、填空 20% （每小题2分） 1、{0，1，2，3，4，6}； 2、；3、1； 4、； (BC)A(PSR)(PSR) 5、1；6、{<1,1>, <1,.3>, <2,2>, <2,4> }；7、{ A 9、a ；a , b , c ,d ；a , d , c , d ；10、c; 二、选择 20% （每小题 2分） 题目 1 2 3 4 5 6 7 8 9 10 答案 C D B、C C A D C A D B A 三、证明 26% 1、 证： Ra,b,cX<a,b>,<a,c> 由“” 若R对称性知 <b,a>,<c,a R ，由R传递性得 <b,c> R R<a,c> R<b,c> R<a,b> ，有 任意 ，因“” 若 a,bX <a,a> R<a,b> R <b,a> R 若 所以R是对称的。 R<b,c> R<b,a> R b,cR <a,c> R<a,b> ， 则 若 即R是传递的。 2、 证，有 ，又 a,bCf(a)g(a),f(b)g(b) 11111111 f(b)f(b),g(b)g(b)f(b)f(b)g(b)g(b) 111 f(a ★★ b)f(a)*f(b)g(a)*g(b)g(a b) 1 a ★ < C , ★> 是 < G , ★>的子群。 bC 1 1 3、 证： ①设G有r个面，则，即 。而 故 2ed(F)rk i i1 r r 2e k ver2 2vervee 2ek(v2) kk2 即得 。（8分） e k(v2) k2 不成立， ②彼得森图为，这样 k5,e15,v10 所以彼得森图非平面图。（3分） 二、 逻辑推演 16% 1、 证明： ① P（附加前提） A ② T①I AB ③ P ABCD ④ T②③I CD ⑤ T④I D ⑥ T⑤I DE ⑦ P DEF ⑧ T⑥⑦I F ⑨ CP AF 2、证明 ① P（附加前提） xP(x) ② US① P(c) ③ P x(P(x)Q(x)) ④ US③ P(c)Q(c) ⑤ T②④I Q(c) ⑥ UG⑤ xQ(x) ⑦ CP xP(x)xQ(x) 三、 计算 18% 1、 解： 01001010 MMMM 10100101 RRR 00010000 R 2 00000000 ， MMM RR 32 0101 1010 R 0000 0000 1010 0101 MMM R 0000 0000 1111 1111 MMMMM 0001 0000 ， RR 43 t(R)R RRR 234 t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > } 2、 解： 用库斯克（Kruskal）算法求产生的最优树。算法略。结果如图： 树权C(T)=23+1+4+9+3+17=57即为总造价。 试卷二试题与答案 一、填空 20% （每小题2分） 1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻y译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式真值为 。 xyP(y,x) 2、 设S={a，a，…，a}，B是S的子集，则由B所表达的子集是 1 2 8i31 。 3、 设A={2，3，4，5，6}上的二元关系，则R= R{x,y|xyx是质数} （列举法）。 R的关系矩阵M= R 。 5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系 R= ；A上既是对称的又是反对称的关系 R= 。 6、设代数系统 * a b c a a b c b b b c c c c b 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n个结点的无向完全图K的边数为 ，欧拉图的充要条件是 n 。 10、公式的根树表示为 (P(PQ))((PQ)R 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A．；B．； (PQ)(PQ)(PQ)((PQ)(QP)) C．； D．。 (PQ)QP(PQ) 2、命题公式 中极小项的个数为（ ），成真赋值的个数 (PQ)(QP) 为（ ）。 A．0； B．1； C．2； D．3 。 S 3、设，则 有（ ）个元素。 S{,{1},{1,2}} 2 A．3； B．6； C．7； D．8 。 4、 设，定义上的等价关系 S{ 1, 2, 3 } SS R{a,b,c,d | a,bSS,c,dSS,adbc} 则由 R产 生 的上一个划分共有（ ）个分块。 SS A．4； B．5； C．6； D．9 。 5、设，S上关系R的关系图为 S{ 1, 2, 3 } 则R具有（ ）性质。 A．自反性、对称性、传递性； B．反自反性、反对称性； C．反自反性、反对称性、传递性； D．自反性 。 6、设 为普通加法和乘法，则（ ）是域。 , S,, A． B． S{x|xab3,a,bQ} C． D．= N 。 S{x|x2n1,nZ}S{x|xZx0} S{x|x2n,a,bZ} 7、下面偏序集（ ）能构成格。 8、在如下的有向图中，从V到V长度为3 的道路有（ ）条。 14 A．1； B．2； C．3； D．4 。 9、在如下各图中（ ）欧拉图。 10、 设R是实数集合，“”为普通乘法，则代数系统 A．群； B．独异点； C．半群 。 三、证明 46% 1、 设R是A上一个二元关系， S{a,b|(a,bA)(对于某一个cA,有a,cR且c,bR)} 试证 明若R是A上一个等价关系，则S也是A上的一个等价关系。（9分） 2、 用逻辑推理证明： 所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 （11分） A g:B2 f:AB 3、 若是从A到B的函数，定义一个函数对任意有 bB A g(b){x|(xA)(f(x)b)} ，证明：若f是A到B的满射，则g是从B到 2 的单射。（10分） 4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分） 5、 设G是具有n个结点的无向简单图，其边数，则G是 Hamilton图（8分） m(n1)(n2)2 1 2 四、计算 14% 1、 设 6666 试求出 66 2、 权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。（7分） 试卷二答案： 一、 填空 20%（每小题2分） 1、；2、T 3、4、 PQ PQ BB{a,a,a,a,a} 310001111145678 R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5, 11111 11111 00011 11111 00000 3>,<5,4>,<5,5>,<5,6>}； 5、R={<1,2>,<1,3>,<2,1>}； R={<1,1>,<2,2>,<3,3>} 6、a ；否；有 7、Klein四元群；循环群 8、 B 9、 1 n(n1) 2 ；图中无奇度结点且连通 10 、 二、 选择 20%（每小题 2分） 题目 1 2 3 4 5 6 7 8 9 10 答案 B、D D；D D B D A B B B B、C 三、 证明 46% 1、（9分） （1） S自反的 aA ，由R自反，， (a,aR)(a,aR)a,aS （2） S对称的 a,bA a,bS(a,cR)(c,bR)S定义 (a,cR)(c,bR)R对称 b,aSR传递 （3） S传递的 a,b,cA a,bSb,cS (a,dR)(d,bR)(b,eR)(e,cR) (a,bR)(b,cR)R传递 a,cSS定义 由（1）、（2）、（3）得；S是等价关系。 2、11分 证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华 上述句子符号化为： 前提：、 结论： ……3分 x(P(x)Q(x))S(a)P(a)x(S(x)Q(x)) ① P S(a)P(a) ② P x(P(x)Q(x)) ③ US② P(a)Q(a) ④ T①I P(a) ⑤ T③④I Q(a). ⑥ T①I S(a) ⑦ T⑤⑥I S(a)Q(a) ⑧ EG⑦ ……11分 x(S(x)Q(x) ３、１0分 证明 ： b,bB,(bb)f满射a,aA 121212 使f(a)b,f(a)b,且f(a)f(a),由于f是函数,aa 11221212 又g(b){x|(xA)(f(x)b)},g(b){x|(xA)(f(x)b)} 1122 ag(b),ag(b)但ag(b),ag(b)g(b)g(b) 1122122112 由b,b任意性知,g为单射 12 。 4、8分 证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连 通分支G、G，使得u和v分别属于G和G，于是G和G中各含有1个奇数度结 12 1212 点，这与图论基本定理矛盾，因而u，v一定连通。 5、8分 证明： 证G中任何两结点之和不小于n。 反证法：若存在两结点u，v 不相邻且,令，则G-V d(u)d(v)n1 V{u,v} 1 1 是具有n-2个结点的简单图，它的边数,可得 m(n1)(n2)2(n1) ' 1 2 m(n2)(n3)1 ' 1 2 ，这与G=G-V为n-2个结点为简单图的题设矛盾，因而G 11 四、 计算 14%d 中任何两个相邻的结点度数和不少于n。 所以G为Hamilton图. 1、 7分 解：子群有<{[0]},+>；<{[0],[3]},+>；<{[0],[2],[4]},+>；<{Z},+> 66666 {[0]}的左陪集：{[0]}，{[1]}；{[2]}，{[3]}；{[4]}，{[5]} {[0]，[3]}的左陪集：{[0]，[3]}；{[1]，[4]}；{[2]，[5]} {[0]，[2]，[4]}的左陪集：{[0]，[2]，[4]}；{[1]，[3]，[5]} Z的左陪集：Z。 66 2、 7分 试卷三试题与答案 一、 填空 20% （每空 2分） f(x)x1,g(x)2xxN, ， 1、 设 f，g是自然数集N上的函数 则 。 fg(x) 2、 设A={a，b，c}，A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} , 则s（R）= 。 3、 A={1，2，3，4，5，6}，A上二元关系，则用列举 T{x,y|xy是素数} 法 T= ； T的关系图为 ； T具有 性质。 4、 集合的幂集 A{{,2},{2}} 2 A = 。 5、 P，Q真值为0 ；R，S真值为1。则的 wff(P(RS))((PQ)(RS)) 真值为 。 6、 的主合取范式 wff((PQ)R)R 为 。 7、 设 P（x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。 则谓词的自然语言是 wffx(P(x)y(O(y)N(y,x))) 。 8、 谓词的前束范式为 wffxy(z(P(x,z)P(y,z))uQ(x,y,u)) 。 二、 选择 20% （每小题 2分） 1、 下述命题公式中，是重言式的为（ ）。 A、； B、； (pq)(pq)(pq)((pq))(qp)) C、； D、。 (pq)q(pp)q 2、 的主析取范式中含极小项的个数为（ ）。 wff(pq)r A 、2； B、 3； C、5； D、0； E、 8 。 3、 给定推理 ① P x(F(x)G(x)) ② US① F(y)G(y) ③ P xF(x) ④ ES③ F(y) ⑤ T②④I G(y) ⑥ UG⑤ xG(x) x(F(x)G(x))xG(x) 推理过程中错在（ ）。 A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥ 4、 设S={1，2，…，8，9}，S={2，4，6，8}，S={1，3，5，7，9}，S={3，4，5}， 1234 S={3，5}，在条件下X与（ ）集合相等。 5 XS且XS 13 A、 X=S或S； B、X=S或S； 25 45 C、X=S，S或S； D、X与S，…，S中任何集合都不等。 12415 5、 设R和S是P上的关系，P是所有人的集合， R{x,y|x,yPx是y的父亲}S{x,y|x,yPx是y的母亲} ， 则表示关系 （ ）。 SR 1 A、； {x,y|x,yPx是y的丈夫} B、； {x,y|x,yPx是y的孙子或孙女} C、 ； D、。 {x,y|x,yPx是y的祖父或祖母} 6、 下面函数（ ）是单射而非满射。 A、； f:RR,f(x)x2x1 f:ZR,f(x)lnx B、； 2 C、； f:RZ,f(x)[x],[x]表示不大于x的最大整数 D、。 f:RR,f(x)2x1 其中R为实数集，Z为整数集，R，Z分别表示正实数与正整数集。 ++ 7、 设S={1，2，3}，R为S上的关系，其关系图为 则R具有（ ）的性质。 A、 自反、对称、传递； B、什么性质也没有； C、反自反、反对称、传递； D、自反、对称、反对称、传递。 8、 设，则有（ ）。 S{,{1},{1,2}} S A、{{1,2}} ；B、{1,2 } ； C、{1} ； D、{2} 。 9、 设A={1 ,2 ,3 }，则A上有（ ）个二元关系。 A、2 ； B、3 ； C、； D、。 32 23 22 32 10、全体小项合取式为（ ）。 A、可满足式； B、矛盾式； C、永真式； D、A，B，C 都有可能。 三、 用CP规则证明 16% （每小题 8分） AFABCD,DEF 1、 2、 x(P(x)Q(x))xP(x)xQ(x) 四、（14%） 集合X={<1,2>, <3,4>, <5,6>,… }，R={< 112212 = 21 1、 证明R是X上的等价关系。 （10分） 2、 求出X关于R的商集。（4分） 五、（10%） 设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。（4分） 2、用矩阵运算求出R的传递闭包。（6分） 六、（20%） 1、（10分）设f和g是函数，证明也是函数。 fg 2、（10分）设函数，证明 有一左逆函数当且仅当f是 g:STf:TSf:TS 入射函数。 答案： 五、 填空 20%（每空2分） 1、2(x+1)；2、；3、 {a ,a,a ,b,a ,c,c ,c,b ,a,c ,a} {2,1,3,1,5,1,4,2,6,2,6,3 ； 4、 反对称性、反自反性；4、；5、1； {,{{,2}},{{2}},{{,2},{2}}} 6、；7、任意x，如果x是素数则 (PQR)(PQR)(PQR) 存在一个y，y是奇数且y整除x ；8、。 xyzu(P(x,z)P(y,z)Q(x,y,u)) 六、 选择 20%（每小题 2分） 题目 1 2 3 4 5 6 7 8 9 10 答案 C C C C A B D A D C 七、 证明 16%(每小题8分) 1、 ① P（附加前提） A ② T①I AB ③ P ABCD ④ T②③I CD ⑤ T④I D ⑥ T⑤I DE ⑦ P DEF ⑧ T⑥⑦I F ⑨ CP AF 2、 xP(x)xQ(x)(x)P(x)xQ(x) 本题可证x(P(x)Q(x))(xP(x)xQ(x) P（附加前提） ① T①E ② ES② ③ P ④ US④ ⑤ T③⑤I ⑥ EG⑥ ⑦ CP ⑧ (xP(x)) x(P(x)) P(a) x(P(x)Q(x)) P(a)Q(a) Q(a) xQ(x) (xP(x)xQ(x) 八、 14% （1） 证明： 1、 自反性： x,yX,由于xyxy x,y,x,yRR自反 2、 对称性： x,yX,x,yX 1122 当x,y,x,yR时即xyxy也即xyxy 112212212112 故x,y,x,yRR有对称性 2211 3、 传递性： x,yX,x,yXx,yX 112233 当x,y,x,yR且x,y,x,yR时 11222233 xyxy(1) 2211 即 xyxy(2) 2332 (1)(2)xyxyxyxy 12232132 即 xyxy 1331 故x,y,x,yRR有传递性 1133 由（1）（2）（3）知：R是X上的先等价关系。 2、X/R= {[1,2]} R 九、 10% 0100 1010 M R 0001 0000 1、； 关系图 0101 1010 0000 0000 2、 MMM R 2 RR 0101 1010 MMM R 0000 0000 1010 0101 MMMM R 0000 0000 RR 32 RRR 243 MMMM RRRR 5364 ,, 1111 1111 MMMMM 0001 0000 t(R)R RRR 234 t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > }。 六、 20% fg{x,y|xdomfxdomgyf(x)yg(x)} {x,y|xdomfdomgyf(x)g(x)} 1、（1） 令hfg domfgdomh{x|xdomfdomg,f(x)g(x)} （2） h{x,y|xdomfdomgyh(x)f(x)g(x)} 对xdomh若有y,y使得 12 yh(x)f(x)g(x),yh(x)f(x)g(x) 12 由于f(或g)是函数,有yy即xdomh有唯一y使得yh(x) 12 fg也是函数 。 2、证明： ""若f有一左逆g,则对tTgf(t)t 故gf是入射,所以f是入射 。 ""f是入射,f:TS定义如下: sf(T),由f入射,|tT,使f(t)s 此时令g(s)t,若sf(T)令g(s)cT 则对sS,g(s)只有一个值t或c且若f(t)s 则gf(t)g(s)t,故g是f的左逆元 即若f入射,必能构造函数g,使g为f左逆函数 。 试卷四试题与答案 一、 填空 10% （每小题 2分） 1、 若P，Q，为二命题，真值为0 当且仅当 。 PQ 2、 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x为实数， L(x,y):xy 则命题的逻辑谓词公式 为 。 3、 谓词合式公式的前束范式 xP(x)xQ(x) 为 。 4、 将量词辖域中出现的 和指导变元交换为另一变元符号，公式其余 的部分不变，这种方法称为换名规则。 5、 设x是谓词合式公式A的一个客体变元，A的论域为D，A(x)关于y是自由的，则 被称为存在量词消去规则，记为 ES。 二、 选择 25% （每小题 2.5分） 1、 下列语句是命题的有（ ）。 A、 明年中秋节的晚上是晴天； B、； xy0 C、当且仅当x和y都大于0； D、我正在说谎。 xy0 2、 下列各命题中真值为真的命题有（ ）。 A、 2+2=4当且仅当3是奇数；B、2+2=4当且仅当3不是奇数； C、2+2≠4当且仅当3是奇数； D、2+2≠4当且仅当3不是奇数； 3、 下列符号串是合式公式的有（ ） A、；B、；C、；D、。 PQ PPQ(PQ)(PQ)(PQ) 4、 下列等价式成立的有（ ）。 A、；B、； PQQPP(PR)R C、 ； D、。 P(PQ)QP(QR)(PQ)R 5、 若和B为wff，且则（ ）。 A,AAAAAB 12n12n A、称为B的前件； B、称B为的有效结论 AAA 12n A,AA 12n C、当且仅当；D、当且仅当 AAABF 12n AAABF 12n 。 6、 A，B为二合式公式，且，则（ ）。 AB ** A、为重言式； B、； AB AB ** C、； D、； E、为重言式。 ABAB AB 7、 “人总是要死的”谓词公式表示为（ ）。 （论域为全总个体域）M(x)：x是人；Mortal(x)：x是要死的。 A、； B、 M(x)Mortal(x)M(x)Mortal(x) C、；D、 x(M(x)Mortal(x))x(M(x)Mortal(x)) 8、 公式的解释I为：个体域D={2}，P(x)：x>3, Q(x)：x=4则A Ax(P(x)Q(x)) 的真值为（ ）。 A、1； B、0； C、可满足式； D、无法判定。 9、 下列等价关系正确的是（ ）。 A、； x(P(x)Q(x))xP(x)xQ(x) B、； x(P(x)Q(x))xP(x)xQ(x) C、； x(P(x)Q)xP(x)Q D、。 x(P(x)Q)xP(x)Q 10、 下列推理步骤错在（ ）。 ① P x(F(x)G(x)) ② US① F(y)G(y) ③ P xF(x) ④ ES③ F(y) ⑤ T②④I G(y) ⑥ EG⑤ xG(x) A、②；B、④；C、⑤；D、⑥ 三、 逻辑判断30% 1、 用等值演算法和真值表法判断公式的类 A((PQ)(QP))(PQ) 型。（10分） 2、 下列问题，若成立请证明，若不成立请举出反例：（10分） （1） 已知，问成立吗？ ACBCAB （2） 已知，问成立吗？ ABAB 3、 如果厂方拒绝增加工资，那么罢工就不会停止，除非罢工超过一年并且工厂撤换了 厂长。问：若厂方拒绝增加工资，面罢工刚开始，罢工是否能够停止。（10分） 四、计算10% 1、 设命题A，A的真值为1，A，A真值为0，求命题 1234 (A(A(AA)))(AA) 123124 的真值。（5分） 2、 利用主析取范式，求公式的类型。（5分） (PQ)QR 五、谓词逻辑推理 15% 符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证 其结论。 六、证明：（10%） 设论域D={a , b , c}，求证：。 xA(x)xB(x)x(A(x)B(x)) 答案： 十、 填空 10%（每小题2分） 1、P真值为1，Q的真值为0；2、；3、 x(F(x)L(x,0)y(F(y)L(y,x)) x(P(x)Q(x))xA(x)A(y) ；4、约束变元；5、，y为D的某些元素。 十一、 选择 25%（每小题2.5分） 题目 1 2 3 4 5 6 7 8 9 10 答案 A,C A,D C,D A,D B,C A,B,C,D,E C A B (4) 十二、 逻辑判断 30% 1、（1）等值演算法 A((PQ)(QP))(PQ)(PQ)(PQ)T （2）真值表法 P Q A 1 1 1 1 1 1 1 1 0 0 1 0 0 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 所以A为重言式。 2、（1）不成立。 若取 CT则ATTBTT有ACBCT PQQP(PQ)(QP) PQ 但A与B不一定等价，可为任意不等价的公式。 （2）成立。 证明： AB充要条件ABT T(AB)(BA)(AB)(BA) 即： (BA)(AB)(AB)(BA)AB 所以故 。 ABTAB 3、解：设P：厂方拒绝增加工资；Q：罢工停止；R罢工超壶过一年；R：撤换厂长 前提： 结论： P((RS)Q),P,R ① P P((RS)Q) ② P P ③ T①②I (RS)Q ④ P R ⑤ T④I RS ⑥ T⑤E (RS) ⑦ T③⑥I Q 罢工不会停止是有效结论。 四、计算 10% Q （1） 解： (1(100)))(11)(1(10)1 (10)1111 (PQ)QR(PQ)(QR) (PQ)(QR)PQQRF （2） 它无成真赋值，所以为矛盾式。 五、谓词逻辑推理 15% 解： M(x):x是人;F(x):x是花;G(x):x是杂草;H(x,y):x喜欢y x(M(x)y(F(y)H(x,y)))x(M(x)y(G(y)H(x,y))) x(F(x)G(x)) 证明： ⑴ P x(M(x)y(F(y)H(x,y))) ⑵ ES⑴ M(a)y(F(y)H(a,y)) ⑶ T⑵I M(a) ⑷ T⑵I y(F(y)H(a,y)) ⑸ P x(M(x)y(G(y)H(x,y))) ⑹ US⑸ M(a)y(G(y)H(a,y)) ⑺ T⑶⑹I y(G(y)H(a,y)) ⑻ T⑺E y(H(a,y)G(y)) ⑼ US⑷ F(z)H(a,z) ⑽ US⑻ H(a,z)G(z) ⑾ T⑼⑽I F(z)G(z) ⑿ UG⑾ x(F(x)G(x)) 十三、 证明10% xA(x)xB(x)(A(a)A(b)A(c)(B(a)B(b)B(c) (A(a)B(a))(A(a)B(b))(A(a)B(c)) (A(b)B(a))(A(b)B(b))(A(b)B(c)) (A(c)B(a))(A(c)B(b))(A(c)B(c)) (A(a)B(a))(A(b)B(b))(A(c)B(c) x(A(x)B(x))
本文发布于:2023-05-24 02:27:51，感谢您对本站的认可！
本文链接：https://www.wtabcd.cn/zhishi/a/168486647117411.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
本文word下载地址：《离散数学》考试题库及答案.doc
本文 PDF 下载地址：《离散数学》考试题库及答案.pdf
| 留言与评论（共有 0 条评论） |
