离散填空题和答案

1、填空1、p :你努力，q-.你失败。“除非你努力，否则你将失败"的翻译为 ;“虽然你努力了，但还是失败了”的翻译为2、论域D=1, 2,指定谓词PP(l,l)P(l,2)P(2,l)P(2,2)TTFF则公式Vx3yP(y,x)真值为 。3、设 A=2, 3 , 4, 5,6上的二元关系7? = < x,y >1 x < y AX 是质数,则 R=_(列举法)。R的关系矩阵MR= 0 111100111000000000 1000004、设代数系统<A, *>,其中A=a, b, c,*abcaabcbbbc则幺元是;是否有对称性occcb5、 n个结点

2、的无向完全图心的边数为 6. 设 4 = xl(xwN)且(x<5),B = xlxwE+ 且 x<7 (N :自然数集，E+ 正偶数)贝 ij A< JB= o7. A, B, C表示三个集合，文图中阴影部分的集合表达式为&设P, Q的真值为0, R, S的真值为1,则（Pv （0 T （R 人P） -（7?vS）的真值=9.若解释I的论域D仅包含一个元 BxP（x） VxP（x）在I下真值为11.设 A=a, b,c, d,其上偏dR的哈斯图b则帶=则R= a人Al VJ2. Wcd的补图.13.设A=a, b,A上二元运算如c, d*abcdaabcdbbcda

3、ccdabddabc那么代数系统v人，* 的幺元是厘 ,有逆元的元素为a,b c,d ,它们的逆元分别为a,d,c,b°.15.设 A = 0,1,2,3, A 上的关系为 7? = <0,1>,<0,2>,<0,3>,<1,2>,<1,3>,<2,3>，若艮"=< 0,3,贝U m= 3;若 7?" = 0,则 n= 416. 设 4 = a,b,c, A 上的二元关系R=<a,b>,<b,c>,<c,a>,则/"(7?)S(R)=<

4、a,a>,vb,b>,vc,c>,<a,b>,vb,c>,vc,a><a,b>,vb,a>,vb.,c>,<c,b>,vc,a>,va,c>.17. I是整数集，如果(I, +)是群，那么(I, +)的幺兀是0； n是任意-个整数，则n的逆元是-n o18. 若集合A=1,2,3±二元关系R1和R2的关系图如下所示， - R,R?贝 H RioR? = <1,1>,<3,1>,v1,3>,v3, 3>19. 设f, g是自然数集N上的函数Vx e N, f (

5、x) = x + 1, g(x) = 2x ,贝 U / °(x) = o20. 设 A=a, b, c, A 上二元关系 R=< a, a > , < a, b >,< a, c >, < c, c>,贝 U s (R) =<a,a>,va,b>,va,c>,<c,c>,vb,a>,vc,a> 。21. A=1,2, 3, 4, 5, 6, A 上二元关系T = < x, yl x* y是素数,则用列举法T= <2,1>,<3,1>,<5,1>,

6、<4,2>,<6,2>,<6,3>T的关系图为T 具有 反自反，反对称，反传递性质。22. 集合 A = ,2,2的幕集 2? 丄,，2, 少，2, 223. P, Q 真值为 0 ; R, S 真值为 1。贝U wff (PA (7?vS)%Pve ) A( 7?AS)的真值为口 等值演算24. 求一个公式的主析取或主合取范式的方法，有真值表-法和法。25.给定谓词合式公式A,其中一部分公式形式为(Vx)B(x)或(mx)B(x),则量词0,日后面所跟的x称为指导变元，而称B为相应量词的辖域26.集合X=a, b, c, d上二元关系R=<a, b&

7、gt;, <a, c>, <a, d>, <b, c>, <b, d>,<e,d>贝0 R的自反闭包r(R)=va, b>, va, c>, va, d>, vb, c>, vb, d>, ve, d>,vb,a>,vc,a>,vd,a>,vc,b>vd,bxd,e> 。27. 对代数系统<S, *>,其中*是S上的二元运算，若 a, bGS,且对任意的xGS,都有a*x=x*a=x,b*x=x*b=b,则称a为运算"* ”的单位元，称b为运算&q

8、uot;* ”的零元。28. 设<S, *>是群，贝U<S, *>满足结合律和.交换律，单位元,逆元。29. 个 连通且一无回路的无向图称为树。30. 在简单无向图G=<V, E>中，如果V中的每个结点都与其余的所有结点邻接，则该图称为 完全图，如果V有n个结点，那么它还是 度正则图。31. 任意两个不同的小项的合取为矛盾_ 式,全体小项的析取式必为.重言式。32. 设集合 M=xllvx<12,x 被 2 整除，xGZ,N=xll<x<12,x 被 3 整除，xAZ,贝0MPIN=, MUN= (2,3,4,6.8,9,10.12。33.

9、 设 X=1, 2, 3, f : X X, g : X X, f=vl,2>,<2,3>,<3,l>,g=vl,2>,<2,3>.<3,3>，贝 Uf o g=_,g o 仁vl,3>,v2,l>,v3,l>o34. 设A=abc, R是A上的二元关系，且给定R=<a,b>,<b,c>,<c,a>,则R的自反闭包r(R)=<a,a>,vb,b>,vc,c>,<a,b>,vb,c>,vc,a> ，对 称闭包 s(R)=<a,b&

10、gt;,<b,a>,<b,c>,<c,b>,<c,a>,<a,c>。35. 设Q为有理数集，笛卡尔集S=QXQ, *是S上的二元运算，V<a, b>,<x, y> S,£<a, b>*<x, y>=<ax, y+b>,贝 U* 运算的单位元是 。V <a, b>GS,若aHO,贝H <a, b>的逆元是o36. 设*是集合S上的二元运算，若运算*满足一 且存在 单位元,则称<S, *>为有么半群。37. 女口下无向图割点是 ,害g

11、边是 o38. 无向图G具有生成树，当且仅当.连通且无回路一o G的所有生成树中.权最小的生成树称为最小生成树。39. 所谓一简单命题一是指不能再分解的命题,而复合命题是由一些简单命题一经过联结词复合而成的命题。40. 在命题演算中，两个.命题-的合取、析取、条件、双条件均为复合命题一。41. 使公式(3x)(3y)(A(x) A B(y) o (3x)A(x) A (3y)B(y)成立的条件是 _ 中不含 y, B_ 中不含x。是素数,贝U domR=2, 3,42. 设 A=1,2, 3, 4, R 是 A 上的二元关系，R=<x,y>lx/y4 ;ranR= 1,243. 设

12、X=1,3, 5, 9,15, 45, R 是X上的整除关系，则R是X上的偏序，其最大元是45 ,极小元是 o44. 树是不包含回路的一连通_图。45. 设F(x):x是人，H(x,y):x与y 样高，在一阶逻辑中，命题"人都不一样 高“的符号化形式为 _VxVy(F(x)/F(y) T->H(x,y)46. 从公式分类角度来看，它为 式。47. 设 R= 1, 1>, 1,2>, 2,3>，贝U R 的对称闭包是 1, 1>, 1,2>, 2, 1>, 2, 3>, 3, 2> o4& Vx(A(x) A 5(x) o

13、_ VxA(x) A V( X)5(X) 。49. 设F(x) :x是人，H(x) :x呼吸，在一阶逻辑中，命题“凡人都呼吸”的符号化形式为 _V(x)(F(x) f H(x) 。50. 个3阶有向图的度序列是2, 2, 4,入度序列是2, 0, 2,岀度序列是0, 2, 2 o51. 一无向图存在生成树的充分必要条件是无向图是连通图。52. 量词否定等值式(x) O iA(x)。53. 设 R 是 A=1, 2, 3, 4上的二元关系，R= 1, 1， 1,2>，< 2, 3>，< 3, 4,贝U R的对称闭包是 1, 1>, 1,2>, 2, 1>

14、, 2, 3>, 3, 2>, 3, 4>, 4, 3>。54. 已知n阶无向简单图G有m条边，则G的补图有条边。55. 已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m,贝 H m= _9 .56. 设G为9阶无向图，每个结点度数不是5就是6,则G中至少有 个5度结点。n57.有向中从V1到V2长度为2的通路58. 任何(n,m)图0= (V, E),边与顶点数的关系是一工d(v) = 2力廿。i=59. 已知一棵无向树 T有三个3顶点，一个2度顶点，其余的都是 1度顶点，60.则T中有 个度顶点n阶完全图62. 设v a,b,c,* 为代数系统，*

15、运算如下*abcaabcbbaccccc则它的幺元为 _a ; 零元为 c ;a、b、c的逆元分别为abc无逆元63. 设 A=1, 2, 3, 4, A 上二元关系 R=<1,2>, <2, 1>, <2, 3>, <3, 4> 画岀 R 的关系图 O64. 设 A=<1,2>,<2,4 >,<3,3 > , B=<1,3>,<2,4>,<4,2>,则 Au5= <1,2>,<24<3,3>,<1,3>,<4,2>。A&

16、#176; B= <1,4>,<2,2> o2 一65. 设IAI=3,则A上有个二元关系。66. A=1,2, 3上关系R=时，R既是对称的又是反对称的。67.偏序集4,心的哈斯图为a贝 0 R= = <a,b>,<a,d>,<b,d>,<b,e>,<a,e>,<a,c>,<a,f>,<a,g>,<c,f>,<c,g> U lg68. Q:我将去上海，R :我有时间，公式(Q R)八(R Q)的69. 若P, Q为二命题，PAQ真值为1,当且仅当P,

17、Q同为真命题或同为假命题。70. 对公式(VyP(x, y)人±Q(x,z) v Vx7?(x, y)中自由变元进行代入的公式为 _(VyP(",y)人玉 QO,z)VVxR(x,v) 。71?若R是集合A上的偏序关系，则 R满足 自反性 反对称性传递性。72. 设 M =xl<x<12,x 被 2 整除，xeZ, 2V = x|l < x < 12,x 被 3 整除，xeZ,贝 0 M cN =6, 12, M-N =2, 4, 8, 10。273. 在 个有 n个元素的集合上，可以有 种不同的关系，有n11种不同的函数。74. 若关系R是反对称的，当且仅当关系矩阵中以主对角线为对称的元素不能同时为1,在关系图上两个不同节点间的定向弧线，不可能成对岀现。75. 设gof是一个复合函数，若g和/都是满射，则g。/?为满射,若g和/ 都是单射，则go / 是单射。76. 设A = 2, a, 3, 4, B = ?, 3,4,1，请在下列每对集合中填入适当的符号：(1) a B ,a,4,3 c A <>Q X是奇数77. 设A = 0,1, N 为自然数集，f (x)-'若/: A A ,则/?是1, x是偶数。双射射的，若f : N A，则/?是满射的。78. 设图G =