离散数学习题集十五套

1、离散数学试题与试卷一20% （每小题 2 分）一、填空A = x | (x Î N )且(x < 5), B = x | x Î E +且x < 7 （N：自然数集，E+1设正偶A È B = 。数） 则2A，B，C 表示三个集合，阴影部分的集合表为 。3设 P，Q 的为 0，R，S 的为 1，则Ø(P Ú (Q ® (R Ù ØP) ® (R Ú ØS) 的4公式(P Ù R) Ú (S Ù R) Ú ØP 的主合取范式为

2、 。=。$xP(x) ® "xP(x)5若解释 I 的论域 D 仅包含一个元素，则在I 下为 。6设 A=1，2，3，4，A图为则 R2 = 。7设 A=a，b，c，d，其上偏序R 的为则 R= 。8图的补图为。9设 A=a，b，c，d ，A 上二元运算如下：1A BC那么代数系统<A，*>的 元是，有逆元的元素为，它们的逆元分别为。10下图所示的偏序集中，是格的为。二、选择 20% （每小题 2 分）1、下列是真命题的有（）a Í a；F ÎF, F；BFÎF,F；AFÎF。CD2、下列集合中相等的有（）A4，3 

3、00; F ；B F ，3，4；C4， F ，3，3；D3，4。3、设 A=1，2，3，则A 上的二元有（）个。32´2 。23´3 ；A 23 ；32B； CD4、设 R，S 是集合 A 上的，则下列说法正确的是（A. 若 R，S 是自反的， 则 R o S 是自反的；B. 若 R，S 是反自反的， 则 R o S 是反自反的；C. 若 R，S 是对称的， 则 R o S 是对称的；D. 若 R，S 是传递的， 则 R o S 是传递的。5、设 A=1，2，3，4，P（A）（A 的幂集）上规定二元系如下）R = < s, t >| s, t Î p(

4、 A) Ù (| s |=| t | 则 P（A）/ R=（）2*abcda b cda bcdb cdac dabd abcAA ；BP(A) ；C1，1，2，1，2，3，1，2，3，4；D F ，2，2，3，2，3，4，A6、设 A= F ，1，1，3，1，2，3则 A 上包含“ Í ”的为（）7、下列函数是Af : I ®E ,Cf : R ®I ,的为（）Bf : N ®N´ N,f (n) = <n , n+1> ；Df :I ®N, f (x)=| x | 。f (x) = 2x ；f (x) = x

5、 ；（注：I整数集，E偶数集， N自然数集，R实数集）8、图 中 从v1 到v3 长度为 3 的通路有（）条。A 0； B1；C 2；D 3。9、下图中既不是 Eular 图，也不是 Hamilton 图的图是（）10、在一棵树中有 7 片树叶，3 个 3 度结点，其余都是 4 度结点则该度结点。）个 4（A1； B2； C3； D4 。三、证明 26%、R 是集合 X 上的一个自反，求证：R 是对称和传递的，当且仅当< a, b> 和<a , c>在R 中有<.b , c>在 R 中。（8 分）3、f 和 g 都是群<G1 ,>到< G2

6、, *>的同态，证明<C , >是<G1, >的一个子群。其中 C=x | x Î G1且f (x) = g(x)(8 分)、G=<V, E>(|V| = v，|E|=e ) 是每一个面至少由 k（k ³ 3）条边围成的连通平面e £ k(v - 2)k - 2图，则， 由此证明（Peterson）图是非平面图。（11 分）四、逻辑推演 16%用 CP 规则证明下题（每小题 8 分）1、 A Ú B ® C Ù D, D Ú E ® F Þ A ® F2

7、、"x(P(x) ® Q(x) Þ "xP(x) ® "xQ(x)五、计算 18%1、设集合 A=a，b，c，d上的R=<a , b > ,< b , a > ,< b, c > , < c , d >用矩阵运算求出 R 的传递闭包 t (R)。（9 分）2、如下图所示的赋表示某七个城市v1 , v2 ,L, v7 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分）试卷一：一、填空 20% （每小题 2 分）1、0，1，2，3，4，

8、6； 2、(B Å C) - A ；3、1； 4、(ØP Ú S Ú R) Ù (ØP Ú ØS Ú R) ；5、1；6、<1,1>, <1,3>, <2,2>, <2,4> ；7、<a.b>,<a,c>,<a,d>,<b,d>,<c,d>IA ；8、U9、a ；a , b , c ,d ；a , d , c , d ；10、c;4二、选择 20% （每小题 2 分）三、证明 26%1、 证：&qu

9、ot;a, b, c Î X< a, b >, < a, c > ÎRÞ“”若由 R对 称 性 知< b, a >, < c, a > ÎR ，由 R 传递性得< b, c >ÎR若 < a, b > ÎR ， < a, c > ÎR< b, c >ÎRa, b Î X“ Ü ”有任意 ，因 < a, a > ÎR 若< a, b > ÎR 若 < a

10、, b > ÎR ， < b, c > ÎR即 R 是传递的。< b, a > ÎR所以 R 是对称的。< b, a > ÎR Ù < b, c >Î R < a, c > ÎR则"a, b Î Cf (a) = g(a), f (b) = g(b)2、 证，有，又f (b-1 ) = f -1 (b) ,g(b-1 ) = g -1 (b) f (b-1 ) = f -1 (b) = g -1 (b) = g(b-1 ) f (a b-1

11、 ) = f (a) * f -1 (b) = g(a) * g(b-1 ) = g(a b -1 )a b -1 Î C3、 证：< C , >是 < G1 , >的子群。r2ekåi2e =d (F ) ³ rki=1r £v - e + r = 2 故设 G 有 r 个面，则，即。而e £ k(v - 2)2 = v - e + r £ v - e + 2ekk - 2。（8 分）即得e £ k(v - 2)为 k = 5, e = 15, v = 10 ，这样k - 2不成立，所以平面图。（3

12、 分）二、 逻辑推演 16%1、 证明：5题目12345678910CDB、CCADCADBA A A Ú B A Ú B ® C Ù D C Ù D D D Ú E D Ú E ® F F A ® F2、证明 "xP(x) P(c) "x(P(x) ® Q(x) P(c) ® Q(c) Q(c) "xQ(x) "xP(x) ® "xQ(x)P（附加前提）TIPTITITIPTICPP（附加前提）USPUSTIUGCP三、 计

13、算18%1、 解：æ 0100001000öæ 1010010000öç÷0÷ç÷1÷= ç 1= ç 0= MMMo Mç 01÷ç 00÷RR2RRç0÷0ç0÷0èøèø，æ 0100001001öç÷0÷= ç 1M= Mo Mç 00÷RR3R2ç0÷

14、;0èø，æ 10ö01001000ç÷1÷= ç 0M= Mo Mç 00÷R4R3Rç0÷0èø6æ1110011öç÷= ç111÷M= M+ M+ M+ Mç 01÷t ( R)RR2R3R400ç0÷0èøt (R)=<a , a> , <a , b> , < a , c> , <a ,

15、 d > , <b , a > , < b ,b > , < b , c . > ,< b , d > , < c , d > 2、 解： 用（Kruskal）算法求产生的最优树。算法略。结果如图：树权 C(T)=23+1+4+9+3+17=57 即为总造价。试卷二试题与一、填空 20% （每小题 2 分）1、 P：你努力，Q：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。2、论域 D=1，2，指定谓词 P则公式"x$yP( y, x)为。2、 设 S=a1 ，a2 ，a8，

16、Bi 是 S 的子集，则由 B31 所表达的子集是 。R = < x, y >| x < y Ú x是质数 ，则3、 设 A=2 ， 3 ， 4 ， 5 ， 6 上的二元R= （列举法）。R 的矩阵 MR= 。5 、设 A=1 ， 2 ， 3 ，则 A 上 既 不 是 对 称 的 又 不 是称 的R= R= 。； A 上既是对称的又是称的7P (1,1)P (1,2)P (2,1)P (2,2)TTFF6、设代数系统<A，*>，其中 A=a，b，c,则元是； 是 否 有 幂 等性；是否有对称性。7、4 阶群必是群或群。8、下面偏序格是分配格的是。9、n

17、个结点的无向完全图 Kn 的为，的充要条件是 。10、公式(P Ú (ØP Ù Q) Ù (ØP Ú Q) Ù ØR 的根树表示为 。二、选择 20% （每小题 2 分）1、在下述公式中是重言式为（）A (P Ù Q) ® (P Ú Q) ；B (P « Q) « (P ® Q) Ù (Q ® P) ；C Ø(P ® Q) Ù Q ；D P ® (P Ú Q)。(ØP 

18、4; Q) ® (ØQ Ú P)2、命题公式为（中极小项的个数为（），赋值的个数）。A0；B1；C2；D3 。3、设 S = F,1,1,2 ，则2 S有（）个元素。A3；4、 设 S = 1,B6；C7；D8 。2, 3 ，定义 S ´ S 上的等价R = << a,b >, < c, d >| < a, b >Î S ´ S, < c, d >Î S ´ S, a + d = b + c 则由R 产 生的 S ´ S 上一个划分共有（）个分块。8*

19、abca bca bcb bcc cbA4；5、设 S = 1,B5；2, 3 ，SC6；D9 。R 的图为则 R 具有（）性质。A自反性、对称性、传递性；B反自反性、D自反性 。称性；C反自反性、称性、传递性；+,o） < S, +, o > 是域。B S = x | x = 2n ,a, b Î Z6、设为普通加法和乘法，则（A S = x | x = a + b 3 ,a,b Î QC S = x | x = 2n + 1,n Î ZD S = x | x Î Z Ù x ³ 0= N。7、下面偏序集（）能格。8、在

20、如下的有中，从 V1 到 V4 长度为 3 的道路有（）条。A1；B2；C3；。D4 。9、在如下各图中（）10、设 R 是实数集合，“ ´ ”为普通乘法，则代数系统<R ，×> 是（）。A群；B独异点；C半群 。9三、证明 46%1、 设 R 是 A 上一个二元，S = < a,b >| (a,b Î A) Ù (对于某一个c Î A, 有< a, c >Î R且< c,b >Î R)试证 明若 R 是 A 上一个等价，则 S 也是 A 上的一个等价。（9 分）2、 用逻辑推

21、理证明：所有的舞蹈者都很有风度，是个学生且是个舞蹈者。因此有些学生很有风度。（11 分）f : A ® B 是从A 到 B 的函数，定义一个函数 g : B ® 2 A 对任意 b Î B 有3、 若g(b) = x | (x Î A) Ù ( f (x) = b)，证明：若 f 是 A 到 B 的的。（10 分）2 A，则 g 是从 B 到4、 若无G 中只有两个奇数度结点，则这两个结点一定连通。（8 分）m = 1 (n -1)(n - 2) + 225、 设 G 是具有 n 个结点的无向简单图，其Hamilton 图（8 分），则 G 是

22、四、计算 14%1、 设<Z6,+6>是一个群，这里+6 是模 6 加法，Z6=0 ，1，2，3，4，5，试求出<Z6,+6>的所有子群及其相应。（7 分）2、 权数 1，4，9，16，25，36，49，64，81，100 构造一棵最优二试卷二：一、 填空 20%（每小题 2 分）。（7 分）B31 = B00011111 = a4 , a5 , a6 , a7 , a8 ØP ® QP Ù Q1 、；2 、 T3 、4 、R=<2,2>,<2,3>,<2,4>,<2,5>,<2,6&g

23、t;,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,æ 11 ö110101101011110çç 1÷1 ÷ç 01 ÷çç 1÷1 ÷ç 00÷èø3>,<5,4>,<5,5>,<5,6> ；R=<1,1>,<2,2&

24、gt;,<3,3>5、四R=<1,2>,<1,3>,<2,1> ；循环群 8、 B9、6、a ；否；有7、Klein101 n(n -1)2；图中无奇度结点且连通 10 、二、选择 20%（每小题 2 分）三、1、（证明 46%9 分）（1） S 自反的"a Î A ，由 R 自反，(< a, a >Î R) Ù (< a, a >Î R) ，< a, a >Î S（2） S 对称的"a, b Î A< a, b >&#

25、206; S Þ (< a, c >Î R) Ù (< c, b >Î R)Þ (< a, c >Î R) Ù (< c, b >Î R)Þ< b, a >Î S（3） S 传递的"a, b, c Î A< a, b >Î S Ù < b, c >Î SLS 定义LR 对称LR 传递Þ (< a, d >Î R) Ù (&

26、lt; d , b >Î R) Ù (< b, e >Î R) Ù (< e, c >Î R)Þ (< a, b >Î R) Ù (< b, c >Î R)Þ< a, c >Î S由（1）、（2）、（3）得；S 是等价2、11 分LR 传递LS 定义。证明：设 P(x)：x 是个舞蹈者； Q(x) ：x 很有风度； S(x)：x 是个学生； 上述句子符号化为：a：前提： "x(P(x) ® Q(x)

27、、 S(a) Ù P(a)结论： $x(S (x) Ù Q(x)3 分 S(a) Ù P(a) "x(P(x) ® Q(x) P(a) ® Q(a) P(a) Q(a). S(a) S(a) Ù Q(a) $x(S(x) Ù Q(x)、0 分P PUSTI TI TI TIEG11 分11题目12345678910B、DD；DDBDABBBB、C： "b1 ,b2 Î B ,(b1 ¹ b2 ) Q f$a1 , a2 Î Af (a2 ),由于f是函数, a1 ¹

28、 a2证明使f (a1 ) = b1 , f (a2 ) = b2 , 且 f (a1 ) ¹又 g(b1 ) = x | (x Î A) Ù ( f (x) =b1 ),g(b2 ) = x | (x Î A) Ù ( f (x) = b2 ) a1 Î g(b1 ), a2 Î g(b2 )但 a1 Ï g(b2 ), a2 Ï g(b1 ) g(b1 ) ¹ g(b2 )由b1,b2任意性知 ,g为4、8 分证明：设 G 中两奇数度结点分别为 u 和 v，若 u，v 不连通，则 G 至少有

29、两个连通分支 G1、G2 ，使得 u 和 v 分别属于 G1 和 G2，于是 G1 和 G2 中各含有 1 个奇数度结。点，这与图论基本定理5、8 分，因而 u，v 一定连通。证明： 证 G 中任何两结点之和不小于 n。不相邻且d (u) + d (v) £ n -1,令V1 = u, v，则反证法：若两结点 u，vG-V1³ 1 (n -1)(n - 2) + 2 - (n -1) 2m'是具有 n-2 个结点的简单图， 它的, 可得³ 1 (n - 2)(n - 3) + 1m'2，这与 G1=G-V1 为 n-2 个结点为简单图的题设，因而

30、G中任何两个相邻的结点度数和不少于 n。所以 G 为 Hamilton 图.四、计算 14%1、 7 分解：子群有<0,+6>；<0,3,+6>；<0,2,4,+6>；<Z6,+6>0的0，3的：0，1；2，3；4，5：0，3；1，4；2，50，2，4的：0，2，4；1，3，5Z6 的：Z6 。2、 7 分试卷三试题与12一、填空 20% （每空 2 分）1、 设 f，g 是自然数集 N 上的函数"x Î N,f (x) = x + 1 ,g(x) = 2x ，f o g(x) =。则2、 设 A=a，b，c，A 上二元R=&

31、lt; a, a > , < a, b >,< a, c >, < c, c>,则 s（R）=。T = < x, y >| x ¸ y 是，则用列举3、 A=1，2，3，4，5，6，A 上二元法T=；T 的图为 ； 性质。T 具有A = F, 2,2 4、 集合的幂集2 A =。(P Ù (R Ú S) ® (P Ú Q) Ù (R Ù S) 的5、 P，Q为 0 ；R，S为 1。则 wff为 。wff Ø(P Ù Q) Ú R) ®

32、; R6、的主合取范式为。7、 设 P（x）：x 是， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数 y。则谓词 wff"x(P(x) ® $y(O( y) Ù N ( y, x) 的自然语言是 。"x"y($z(P(x, z) Ù P( y, z) ® $uQ(x, y, u) 的前束范式为8、 谓词 wff。二、选择 20% （每小题 2 分）1、 下述命题公式中，是重言式的为（）。A、( p Ù q) ® ( p Ú q) ； B、( p « q) &

33、#171; ( p ® q) Ù (q ® p) ；C、Ø( p ® q) Ù q ；D、( p Ù Øp) « q 。Ø( p Ù q) ® r 的主析取范式中含极小项的个数为（wff2、）。A 、2；B、 3；3、 给定推理C、5；D、0；E、 8 。13 "x(F (x) ® G(x) F ( y) ® G( y) $xF (x) F ( y) G( y) "xG(x) "x(F (x) ® G(x) 

34、2; "xG(x)PUSPESTIUG推理过程中错在（）。A、-> B、-> C、-> D、-> E、->4、 设 S1=1，2，8，9，S2=2，4，6，8，S3=1，3，5，7，9，S4=3，4，5，Í S1 且 XË S3 下 X 与（S5=3，5，在条件 XA、 X=S2 或 S5 ；C、X=S1，S2 或 S4；）集合相等。B、X=S4 或 S5；D、X 与 S1，S5 中任何集合都不等。5、 设R和 SP， P是上 的是 所 有 人 的 集 合 ，R = < x, y >| x, y Î P 

35、7; x是y的父亲， S = < x, y >| x, y Î P Ù x是y的母亲则 S -1 o R 表示（）。A、< x, y >| x, y Î P Ù x是y的丈夫；B、< x, y >| x, y Î P Ù x是y的孙子或孙女；D、< x, y >| x, y Î P Ù x是y的祖父或祖母。F ；C、6、 下面函数（）是而非。f : R ® R,-1；f (A、f : Z + ® R,f : R ® Z,f : R

36、74; R,f (x) = ln x ；f (x) = f (x) = 2x + 1。B、的最大整数；C、D、其中 R 为实数集，Z 为整数集，R+，Z+分别表示正实数与正整数集。7、 设 S=1，2，3，R 为S 上的，其图为则 R 具有（）的性质。14A、 自C、反自反、称、传递；B、什么性质也没有；D、自） Í S 。称、传递；称、称、传递。8、 设 S = F,1,1, 2，则有（A、1,2 ；B、1,2 ； C、1 ； D、2 。9、 设 A=1 ,2 ,3 ，则 A 上有（）个二元。32； C、22 ； D、 23 。）。A、23； B、32 10、全体小项合取式为（A、

37、可满足式； B、式； C、式； D、A，B，C可能。三、用 CP 规则证明 16% （每小题 8 分）1、 A Ú B ® C Ù D , D Ú E ® FÞA ® F2、"x(P(x) Ú Q(x)Þ"xP(x) Ú $xQ(x)四、（14%）集合 X=<1,2>, <3,4>, <5,6>, ，R=<<x1,y1>,<x2,y2>>|x1+y2 = x2+y1。1、 证明 R 是 X 上的等价2、

38、求出 X 关于 R 的。 （10 分）。（4 分）五、（10%）设集合 A= a ,b , c , d 要求 1、写出 R 的R=< a, b > , < b , a > , < b , c > , < c , d >矩阵和图。（4 分）2、用矩阵运算求出 R 的传递闭包。（6 分）六、（20%）1、（10 分）设 f 和 g 是函数，证明 Ç g 也是函数。f分）设函数 g : S ® T® S ，证明® S 有一左逆函数当且仅当 f 是f : Tf : T2、（10入射函数。：五、 填空 20%（每空

39、2 分）>a>a<>a<, ； 3 、1 、 2(x+1) ； 2 、< 2,1 >, < 3,1 >, < 5,1 >, < 4,2 >, < 6,2 >, < 6,3 > ；4、称性、反自反性；4、F,F,2,2,F,2,2；5、1；6、(P Ú ØQ Ú R) Ù (ØP Ú Q Ú R) Ù (P Ú Q Ú R) ；7、任意 x，如果 x 是则；8、"x"y&quo

40、t;z$u(ØP(x, z) Ú ØP( y, z) Ú Q(x, y,u) 。一个 y，y 是奇数且y 整除 x六、 选择20%（每小题 2 分）七、 证明16%(每小题 8 分)1、 A A Ú B A Ú B ® C Ù D C Ù D D D Ú E D Ú E ® F F A ® FP（附加前提）TIPTITITIPTICP2、Q "xP(x) Ú $)P(x) ® $xQ(x)本题可证 "x(P(x) Ú

41、 Q(x) Þ Ø("xP(x) ® $xQ(x)Ø("xP(x)P（附加前提） $x(ØP(x) ØP(a) "x(P(x) Ú Q(x) P(a) Ú Q(a) Q(a) $xQ(x)TEESPUSTIEG16题目12345678910CCCCABDADC Ø("xP(x) ® $xQ(x)八、 14%（1）证明：CP自反性： " < x, y >Î X , 由于x + y = x + y1、 << x, y

42、 >, < x, y >>Î RLR自反对称性： " < x1 , y1 >Î X , " < x2 , y2 >Î X2、当<< x1 , y1 >, < x2 , y2 >>Î R时 即x1 + y2 = x2 + y1 也即x2 + y1 = x1 + y2故<< x2 , y2 >, < x1 , y1 >>Î RLR有对称性传递性： " < x1 , y1 >Î X

43、 , " < x2 , y2 >Î X" < x3 , y3 >Î X3、当<< x1 , y1 >, < x2 , y2 >>Î R 且 << x2 , y2 >, < x3 , y3 >>Î R 时ì x1 + y2= x2 + y1(1)(2)即íx+ y = x + yî 2332(1) + (2)x1 + y2 + x2 + y3 = x2 + y1 + x3 + y2即 x1 + y3 = x3 +

44、 y1故 << x1 , y1 >, < x3 , y3 >>Î RLR有传递性由（1）（2）（3）知：R 是 X 上的先等价2、X/R=< 1 ,2 >R 九、 10%。æ 00ö10000ç÷= ç 110÷Mç 01÷R00ç0÷0èø ；1、图æ 10ö01001ç÷= ç 001÷M= Mo Mç 00÷R2RR00ç0

45、÷0èø2、æ 01ö10000100ç÷0÷= ç 1M= Mo Mç 00÷R3R2Rç0÷0èø17æ 1010010öç÷= ç 001÷ = Moç 00÷R3RR00ç0÷0M= M, M= M,LèøR5R3R6R4= M R + M R2 + M R3 + MMt ( R)t (R)=<a , a>

46、, <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c ,d > 。六、 20%f Ç g = < x, y >| x Î= < x, y >| x Î1、（1）令h = f Ç g domf Ç g = domh = （2） h = < x, y >| x Î domf Ç对x

47、Î domh若有y1, y2使得y1 = h(x) = f (x) = g(x) ,由于f (或g)是函数,有y1 = y2 即"x Î domh 有唯一y使得 f Ç g也是函数。2、证明："Þ"若f 有一左逆g ,则对"t Î故 g o f是入射,所以 f 是入射。"Ü" f" Î:® S定Tf是入射,( ),由 fT入fs 射,$ | t Î此时令=若 Ï (T,)g)fsts则对" Î则ogS(,s

48、)s只有一个值=(),) 故fgggtts即若f入射,必能构造函数g,。试卷四试题与一、 填空 10% （每小题2 分）1、 若 P，Q，为二命题， P ® Q为 0 当且仅当。2、 命题“ 对于任意给定的正实数， 都比它大的实数” 令 F(x)： x为实数， L(x, y) : x > y则命题的逻辑谓词公式为 。"xP(x) ® $xQ(x)3、 谓为词合式公式的前束范式 。4、 将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种称为换名规则。5、 设 x 是谓词合式公式 A 的一个客体变元，A 的论域为 D，A(x)关于 y 是的

49、，则 被称为量词消去规则，记为ES。二、 选择 25% （每小题 2.5 分）1、 下列语句是命题的有（）。B、 x + y > 0 ；A、 明年中秋节的晚上是晴天；C、 xy > 0 当且仅当 x 和y 都大于 0； D、我正在说谎。2、 下列各命题中为真题有（）。A、 2+2=4 当且仅当 3 是奇数；B、2+2=4 当且仅当 3 不是奇数；C、2+24 当且仅当 3 是奇数； D、2+24 当且仅当 3 不是奇数；3、 下列符号串是合式公式的有（ ）A、 P Û Q ；B、 P Þ P Ú Q ；C、(ØP Ú Q) 

50、7; (P Ú ØQ) ；D、Ø(P « Q) 。4、 下列等价式成立的有（）。A、 P ® Q Û ØQ ® ØP ；B、 P Ú (P Ù R) Û R ；P Ù (P ® Q) Û Q ；D、 P ® (Q ® R) Û (P Ù Q) ® R 。C、5、 若 A1 , A2 L An 和 B 为 wff，且 A1 Ù A2 ÙLÙ An Þ B 则（

51、）。A、称 A1 Ù A2 ÙLÙ An 为 B 的前件；B、称 B 为 A1 , A2 L An 的有效结论A1 Ù A2 ÙLÙ An Ù B Û FC 、 当 且 仅 当； D 、 当 且 仅 当A1 Ù A2 ÙLÙ An Ù ØB Û F 。6、 A，B 为二合式公式，且 A Û B ，则（）。A、 A ® B 为重言式；C、 A Þ B ；B、 A*D、 A*Þ B* ；Û B* ；E、 A &

52、#171; B 为重言式。197、 “人总是要死的”谓词公式表示为（）。（论域为全总域）M(x)：x 是人；Mortal(x)：x 是要死的。A、 M (x) ® Mortal (x) ；B、 M (x) Ù Mortal(x)C、"x(M (x) ® Mortal(x) ；D、$x(M (x) Ù Mortal(x)8、 公式 A = $x(P(x) ® Q(x) 的解释 I 为：域 D=2，P(x)：x>3, Q(x)：x=4 则 A的为（）。A、1； B、0；C、可满足式； D、无法判定。9、 下列等价正确的是（）。A、&

53、quot;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、 下列推理步骤错在（ "x(F (x) ® G(x) F ( y) ® G( y) $xF (x) F ( y) G( y) $xG(x)）

54、。PUSPESTIEGA、；B、；C、；D、30%三、 逻辑公式 A = (P ® Q) Ù (Q ® P) « (P « Q) 的类1、 用等值演算法和型。（10 分）表法2、 下列，若成立请证明，若不成立请举出反例：（10 分）已知 A Ú C Û B Ú C ，问 A Û B 成立吗？已知ØA Û ØB ，问 A Û B 成立吗？（1）（2）3、 如果厂方拒绝增资，那么就停止，除非超过一年并且工厂撤换了厂长。问：若厂方拒绝增资，面刚开始，是否能够停止。（10

55、分）20四、计算 10%1、 设命题 A1，A2 的为 1，A3，A4为 0，求命题( A1 Ú ( A2 ® ( A3 Ù ØA1 ) « ( A2 Ú ØA4 ) 的。（5 分）2、 利用主析取范式，求公式Ø(P ® Q) Ù Q Ù R 的类型。（5 分）五、谓词逻辑推理 15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草”。并推证其结论。六、证明：（10%）设论域 D=a , b , c，求证： "xA(x) Ú "：十、

56、填空 10%（每小题 2 分）( A(x) Ú B(x) 。0；2、"x(F (x) Ù L(x,0) ® $y(F ( y) Ù L( y, x) ；3、1、P为 1，Q 的为$x(ØP(x) Ú Q(x) ；4、约束变元；5、$xA(x) Þ A( y) ，y 为 D 的某些元素。十一、选择 25%（每小题 2.5 分）十二、逻辑30%1、（1）等值演算法A = (P ® Q) Ù (Q ® P) « (P « Q) Û (P « Q) &#

57、171; (P « Q) Û T（2）表法所以 A 为重言式。2、（1）不成立。21PQP ® QQ ® P(P ® Q) Ù (Q ® P)P « QA1111111100100101100010011111题目12345678910A,CA,DC,DA,DB,CA,B,C,D,ECAB(4)若取C = T则A Ú T Û TB Ú T Û T 有 A Ú C Û B Ú C Û T但 A 与 B 不一定等价，可为任意不等价的公式。（

58、2）成立。证明： ØA Û ØB充要条件 ØA « ØB Û TT Û (ØA ® ØB) Ù (ØB ® ØA) Û ( A Ú ØB) Ù (B Ú ØA)即： Û (ØB Ú A) Ù (ØA Ú B) Û ( A ® B) Ù (B ® A) Û A « B所以

59、 A « B Û T 故A Û B 。3、解：设 P：厂方拒绝增资；Q：停止；R超壶过一年；R：撤换厂长前提： P ® (Ø(R Ù S) ® ØQ) , P ® (Ø(R Ù S) ® ØQ) P Ø(R Ù S ) ® ØQ ØR ØR Ú ØS Ø(R Ù S ) ØQ停止是有效结论。ØR结论： ØQP,PPTIPTITETI四、计

60、算 10%(1 Ú (1 ® 0 Ù 0) « (1 Ú 1) = (1 Ú (1 ® 0) « 1解： = (1 Ú 0) « 1= 1 « 1= 1Ø(P ® Q) Ù Q Ù R Û Ø(ØP Ú Q) Ù (Q Ù R)Û (P Ù ØQ) Ù (Q Ù R) Û P Ù ØQ Ù Q &#

61、217; R Û F（1）（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(F (x) ® ØG(x)证明："x(M (x) ® "y(G( y) ® ØH (x, y) $x(M (x) Ù "y(F ( y) ® H (x, y)P22 M (a) 

62、7; "y(F ( y) ® H (a, y) M (a) "y(F ( y) ® H (a, y) "x(M (x) ® "y(G( y) ® ØH (x, y) M (a) ® "y(G( y) ® ØH (a, y) "y(G( y) ® ØH (a, y) "y(H (a, y) ® ØG( y) F (z) ® H (a, z) H (a, z) ® ØG(z) F (z) ® ØG(z) "x(F (x) ® ØG(x)ESTITIPUSTITEUSUSTIUG十三、证明 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)