离散数学练习题1

1、1、下列句子是简单命题的是（ ）A) 3是素数。 B) 2x+35 C) 张三跟李四是同学吗？ D) 我在说谎。2、下列公式不是永真式的是（ ）A) (pq)p)r B) p(pqr) C) (qr) r D) (pq)(qp)3、设命题公式G(pq)，Hp(q p)，则G与H的关系是( ) 。 A) GH B) HG C) H = G D) G = H4、下列命题不为真的是（ ）A) B) C) a,ba,b,c,a,b D) a,ba,b,c,a,b5、1到300之间（包含1 和1000）不能被3、5和7整除的数有（ ）个。A) 138 B) 120 C) 68 D) 1246、设A, C

2、, B, D为任意集合，以下命题一定为真的是（ ）A) AB= AC =B=CB) AC= AB =B= CC) A(BC) = (AB)(AC) D) 存在集合A,使得A A A7、设A=1,2,3,4，R=, 是A上的关系，则R的性质是（ ）A) 既是对称的也是反对称的B) 既不是对称的也不是反对称的C) 是对称的但不是反对称的 D) 不是对称的但是反对称的8、设R是A上的关系，则R在A上是传递的当且仅当（ ）A) IA R B) R=R-1 C) RIA D) R。RR9、设A=1,2,3,4,5,6,7,8,R为A上的等价关系R=|x,y A x=y(mod 3)其中， x=y(mod

3、 3)叫做x与y模3相等，即x除以3的余数与y除以3的余数相等。则1的等价类，即1，为（ ）A) 1,4,7 B) 2,5,8 C) 3,6 D) 1,2,3,4,5,6,7,8 10、当集合A=且B时，则BA结果为（ ）A) B) C) , D) 错误运算11、函数f:RR,f(x)= x2-2x+1,则f(x)是（）函数。A) 单射 B) 满射 C) 双射 D) 不是单射，也不是满射12、设X=a,b,c,d,Y=1,2,3，f=,，则以下命题正确的是( )A) f是从X到Y的二元关系，但不是从X到Y的函数B) f是从X到Y的函数，但不是满射的，也不是单射的C) f是从X到Y的满射，但不是

4、单射D) f是从X到Y的双射13、下列运算在指定集合上不符合交换律的是（）。A) 复数C集合上的普通加法 B) n阶实矩阵上的乘法B)C) 集合S的幂集上的 D) 集合S的幂集上的14、下列集合对所给的二元运算封闭的是（）A) 正实数集合R+和。运算，其中。运算定义如下：a,bR+，a。b=ab-a-bB) nZ+，nZ=nZ|zZ，nZ关于普通的加法运算C) S=2x-1|xZ+关于普通的加法运算D) S=x|x=2n, nZ+，S关于普通的加法运算15、设V=,其中*定义如下： a，bZ, a*b=a+b-2 ,则能构成的代数系统是（）。A) 半群、独异点、群 B) 半群、独异点C) C)

5、 半群 D) 二元运算16、令S=a,b，S上有4个二元运算：*， ， 和，分别由下列四个表确定：* a b a b a b a b a a a a a b a b a a a bb a a b b a b a a b a bA) B) C) D)则这4个运算中满足幂等律的是（ ）17、在上述四个运算中有单位元的是（ ）18、在上述四个运算中有零元的是（ ）19、与命题公式P（QR）等值的公式是( )A) (PQ)R B) (PQ)R C) (PQ)R D) P(QR)20、下列集合都是N的子集，能够构成代数系统V=的子代数的是（ ）A)x| xNx与5互为素数 B) x| xNx是30的因子

6、C) x| xNx是30的倍数 D) x|x=2k+1, kN 二、填空题(1分/空，共20分。请将正确答案填在相应的横线上。)1、公式(pq) p的成假赋值为 00_,公式(qp) p的成真赋值为_无_。2、设，为任意命题公式，为重言式，若，那么是 重言式 （重言式、矛盾式或可满足式）。3、f：N-NN，f(x)=,A=5,B=,则f(x)是_单 射_（单射，满射，双射）函数，A在f下的像f(A)_，B在f下的完全原像f-1(B)=_2,7_。4、已知公式A中含有3个命题变项p,q,r，并且它的成真赋值为000，011，110，则A的主合取范式为（用极大项表示）_M1_M2_M4_M5_M7

7、_，主析取范式为（用极小项表示）_m0m3_ m6_。5、公式x(F(x,y)$yG(x,y,z)的前束范式为_x$y(F(x,u)G(x,y,z)_或_x$t(F(x,y) G(x,t,z)_。6、列出从集合A=1,2到B=1的所有二元关系 ，, 。7、设A为集合且A=n，则A共有 2n 个子集，P(A)有22n 个子集。8、设 f，g，h RR 且f(x)=x+3, g(x)=2x+1, h(x)=x/2, 则复合函数f。g(x)= 2x+7 ，g。h(x)=_( 2x+1)/2_ ，f。g。h (x)=_(2x+7)/2_。9、含有n个命题变项的公式共有_2n _个不同的赋值，最多可以生

8、成_22n _个不同的真值表；n个命题变项共可产生_2n _个极小项（极大项）；含n个命题变项的所有有穷多个合式公式中，与它们等值的主析取范式（主合取范式）共有_22n _种不同的情况。10、已知集合A=,，则A的幂集P(A)_，,_。三、利用公式的主合取范式判断下列公式是否等值。（5分） p(qr)与 (pq) rp(qr)p(qr)pqrM6(pq)r(pq) rpq)rM6四、符号化命题，并推理证明(给出每个符号的准确含义，及每一步推理的根据)。（5分）每个科学工作者都是刻苦钻研的。每个刻苦钻研而又聪明的人在他的事业中都将获得成功。华有为是科学工作者并且是聪明的，所以华有为在他的事业中将

9、获得成功。解: 首先符号化：M(x)：x是科学工作者；F(x)：x是刻苦钻研的；G(x)：x是聪明的；H(x)：x在事业中获得成功；a：华有为。前提： x(M(x)F(x)）， x (F(x)G(x)H(x),M(a) G(a)结论：H(a)证明： M(a) G(a) 前提引入 M(a) T 化简规则 G(a) T 化简规则 x(M(x)F(x)） 前提引入 M(a)F(a) T F(a) T 假言推理 x (F(x)G(x)H(x) 前提引入 F(a)G(a)H(a) T UI F(a)G(a) T 合取(10)H(a) T 假言推理五、设A=1,2,3,4，在AA上定义二元关系R，AA，R

10、u+y=x+v(1) 证明R是AA上的等价关系(2) 确定由R引起的对AA的划分。(5分)(1)证明: AA = x+y=y+x = R R是自反的 AA , R = x+v=y+u = R R是对称的 , AA , R R = x+v=y+u u+n=v+m = x+v+u+n=y+u+v+m = x+n=y+m = R R是传递的(2)解:,12346812222六、A= 1,2,3,4,6,8,12，R是A上的整除关系，请作出偏序集的哈斯图，给出关系矩阵，并求出A的极大元、极小元、最大元和最小元。若B=2,3,4，求出B的上界，下界，最小上界，最大下界。（5分）解:A的极大元为8、12,

11、极小元为1，无最大元，最小元为1。B的上界为12，下界为1，最小上界为12，最大下界为1。七、在自然推理系统P中构造下面推理的证明。（5分）(1) 前提：(pq) (rs), (st) u结论：pu(2) 前提：x(F(x) (G(a) R(x)， $x F(x).结论： $x (F(x) R(x).(1)证明： p 附加前提引入规则 p q 附加规则 (p q) ( r s) 前提引入 r s 假言推理 s 化简规则 s t 附加规则 (s t) u 前提引入 u 假言推理(2)证明： $x F(x) 前提引入 F(b) EI x(F(x) (G(a) R(x) 前提引入 F(b) (G(a

12、) R(b) UI G(a) R(b) 假言推理 R(b) 化简 F(b) R(b) 合取 $x (F(x) R(x) EG八、设有理数集合Q上的 * 运算定义如下： a，bQ, a*b=a+b-ab 。请指出该运算的性质，并求出其单位元、零元及所有可能的逆元。（5分）解：(1)因为a*b=a+b-ab =b+a-ba=b*a，所以运算满足交换律。 (2)因为(a*b)*c=( a+b-ab)*c= a+b-ab+c-( a+b-ab)c=a+b+c-ab-bc-ac+abc a*(b*c)=a*(b+c-bc)=a+b+c-bc- a(b+c-bc)= a+b+c-ab-bc-ac+abc 故运算满足结合律。 (3)任意xQ，因为x*x=x+x-xx=2x+x2x，故不满足幂等律 (4)因为对aQ，有a*0=a+0-a0=a，所以0是单位元。 (5) 因为对aQ，有a*1=a+1-a=1，所以1是零元。 (6) 对aQ，令a*x=a+x-ax=0，则有x=a/(a-1)。所以当a1时，其逆元为a-1=a/(a