离散数学考试题（十八） 一、选择：（满分20分，每小题2分） 1.下列语句中不是命题的有( (1)9+5≤12： (2)x+3=5: (3)我用的计算机CPU主频是1G吗？：(4)我要努力学习。 2.命题“我不能一边听课，一边看小说”的符号化为( )P→0；(2)P→0： 3)0A-P;(④-(PΛQ) 3.下列表达式正确的有( I0(P→Q)→Q:②)Pv0→P: 3)(PAQ)(PA-Q)=P:④P→(P→Q)=T。 4.n个命题变元可产生( )个互不等价的小项。 ()n:(2n2:(3)2n: (④)2。 5.若公式(PQ)v(-PAR)的主析取范式为 mo1Vm1Vm10Vm,则它的主合取范式为( ()）ma1Amo1Am10AmI:(②)M0AMo0 MM1o1: (3)Mo1AMo1 MIoM:()④m0 mmo入mot。 6.命题“尽管有人聪明，但未必一切人都聪明”的符号化 (P(x:x是聪明的，M(x):x是人)（ (①)3x(M(x)-→Px》A-x(M(x)→Px)》 (2)x(M(x)P(x)((M(x)P(x)) (3)3x(Mx)AP(x》A-x(Mx)→P(x)m (④)3x(M()AP(x)V-(x(M(x)→P(x)) 7.设A={④}，B=P(P(A)下列( )表达式成立。 I)ΦcB；(②)Φ}=B:(③)》eB:(W{他}=B。 8.A是素数集合，B是奇数集合，则A-B=( ()素数集合：（②）奇数集合：(3)①：（④{2；。 9.集合A={2,3,6,12,24,36}上偏序关系R的Has图为 则集合B=2,3,6,12)的上确界 117
离散数学考试题(十八) 117 一、 选择：（满分 20 分，每小题 2 分） 1．下列语句中不是命题的有（ ） ⑴ 9+5 12 ； ⑵ x+3=5； ⑶我用的计算机 CPU 主频是 1G 吗？； ⑷ 我要努力学习。 2．命题“我不能一边听课，一边看小说”的符号化为（ ） ⑴ P → Q ； ⑵ P → Q ； ⑶ Q P ； ⑷ (P Q) 。 3．下列表达式正确的有（ ） ⑴ (P → Q) Q ； ⑵ P Q P ； ⑶ (P Q) (P Q) P ； ⑷ P → (P → Q) T 。 4．n 个命题变元可产生（ ）个互不等价的小项。 ⑴ n ； ⑵ n 2 ； ⑶ 2n ； ⑷ 2 n。 5．若公式 (P Q) (P R) 的主析取范式为 m001 m011 m110 m111 则它的主合取范式为（ ） ⑴ m001 m011 m110 m111 ； ⑵ M000 M010 M100 M101 ； ⑶ M001 M011 M110 M111 ； ⑷ m000 m010 m100 m101 。 6．命题“尽管有人聪明，但未必一切人都聪明”的符号化 （P(x)：x 是聪明的，M(x)：x 是人） （ ） ⑴ x(M (x) → P(x)) (x(M (x) → P(x))) ⑵ x(M (x) P(x)) (x(M (x) P(x))) ⑶ x(M (x) P(x)) (x(M (x) → P(x))) ⑷ x(M (x) P(x)) (x(M (x) → P(x))) 7．设 A={ } ，B=Р(Р(A)) 下列（ ）表达式成立。 ⑴ B ； ⑵ B ； ⑶ B ； ⑷ B。 8．A 是素数集合，B 是奇数集合，则 A-B=（ ） ⑴ 素数集合； ⑵ 奇数集合； ⑶ ； ⑷ {2}。 9．集合 A={2，3，6，12，24，36}上偏序关系 R 的 Hass 图为 则集合 B={2，3，6，12}的上确界
离散数学考试题（十八） B={2,3,6,12)的下界 B={6,12,24,36}的下确界 B={6,12,24,36}的上界 (1)2:(2)3:(3)6:(4)12:(⑤)无. 10.若函数g和f的复合函数gf是双射，则( )一定是正确的。 (①)g是入射；（②）f是入射：（③）g是满射：（④Wf是满射。 二、填空：（满分20，每小题2分） 1.设P:它占据空间，Q:它有质量，R:它不断运动， S:它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质” 的符号化为 2.设A,B是两命题公式，A一B当且仅当 3.要证R→C为前提H,H2,Hm的有效结论，运用CP规则 是 4·对谓词公式(P(x,y)AzO(x,vxx,y)的自由变元代入 得 5.设S={a1.a2,as},Bi是S的子集，则 B31= 6.设I为整数集合，R={Xy>|x=y(mod3)则 ]F 7.偏序集(P({a,b}),c)的Hass图为 8.对集合X和Y,设X=m,IY=n,则从X到Y的函数有 个 9.设R为实数集，S={x0<x<1},f:R→S,则 f(x)=_ 为双射。 18
离散数学考试题(十八) 118 B={2，3，6，12}的下界 。 B={6，12，24，36}的下确界 。 B={6，12，24，36}的上界 。 ⑴ 2； ⑵ 3； ⑶ 6； ⑷ 12； ⑸ 无。 10．若函数 g 和 f 的复合函数 g f 是双射，则（ ）一定是正确的。 ⑴ g 是入射； ⑵ f 是入射； ⑶ g 是满射； ⑷ f 是满射。 二、 填空：（满分 20，每小题 2 分） 1．设 P：它占据空间，Q：它有质量，R：它不断运动， S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质” 的符号化为 。 2．设 A，B 是两命题公式， A B 当且仅当 。 3 ．要证 R →C 为前提 H H Hm , , , 1 2 的 有 效 结 论 ， 运 用 CP 规 则 是 。 4 ．对谓词公式 (yP(x, y) zQ(x,z)) xR(x, y) 的自由变元代入 得 。 5．设 S={a1,a2,.,a8},Bi 是 S 的子集，则 B31= 。 6．设 I 为整数集合，R={<x,y>∣x y(mod3) 则 [1]= 。 7．偏序集〈Ρ（{a,b}）， 〉的 Hass 图为 。 8．对集合 X 和 Y，设|X|=m ，|Y|=n ，则从 X 到 Y 的函数有 个。 9．设 R 为实数集，S={x|0<x<1}，f：R → S，则 f(x)= 为双射
离散数学考试题（十八） 10.设KN=o,K[(0,1)=,则 KN×(0,1)F」 三、 证明：(48分) 1.不构造真值表证明蕴涵式 (Q→(PAP》→(R→(R→(PAP》→R→Q(7分) 2.用逻辑推演下式 (AAB)→C,D,CVD→AV-B(7分) 3.用CP规则证明 x(P(x)VQ(X)→xPx)v3xOx)(7分) 4.符号化并证明其结论：“所有有理数是实数，某些有理数是整数，因此某些实 数是整数”（设Rx):X是实数，Qx):X是有理数，Ix):X是整数）(7 分) 5.设R是集合X上的一个自反关系，求证：R是对称的和传递的当且仅当<a,b >和<a,c>在R中，则有<b,c>在R中(8分)。 6.设f和g是函数，则fng也是函数。(6分) 7.证明0,1]~(0,1) (6分) 四、(6分)集合S={1,2,3,4,5,找出S上的等价关系， 此关系能产生划分{1,2}，{3}，{4,5，并画出关系图。 五、(6分)求(Q→P)A(一PAQ)的主合取范式
离散数学考试题(十八) 119 10．设 K[N]= 0 ，K[(0,1)]= ，则 K[N×(0,1)]= 。 三、 证明：（48 分） 1．不构造真值表证明蕴涵式 (Q → (P P)) → (R → (R → (P P))) R → Q （7 分） 2．用逻辑推演下式 (A B) → C ，D ，C D A B （7 分） 3．用 CP 规则证明 x(P(x) Q(X )) x P(x) x Q(x) （7 分） 4．符号化并证明其结论：“所有有理数是实数，某些有理数是整数，因此某些实 数是整数”（设 R(x)：x 是实数，Q(x)：x 是有理数，I(x)：x 是整数） （7 分） 5． 设 R 是集合 X 上的一个自反关系，求证：R 是对称的和传递的当且仅当＜a,b ＞和＜a,c＞在 R 中，则有＜b,c＞在 R 中 (8 分)。 6． 设 f 和 g 是函数，则 f∩g 也是函数。 （6 分） 7． 证明 [0，1]～（0，1） （6 分） 四、（6 分）集合 S={1，2，3，4，5}，找出 S 上的等价关系， 此关系能产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 五、（6 分）求 (Q → P) (P Q) 的主合取范式