离散填空题和答案解析

《离散填空题和答案解析》由会员分享，可在线阅读，更多相关《离散填空题和答案解析（13页珍藏版）》请在装配图网上搜索。

1、填空 1、p :你努力，q :你失败。“除非你努力，否则你将失败”的翻译为; “虽然你努力了，但还是失败了”的翻译为2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式 x yP(y, X)真值为 。3、设A=2，3，4，5，6上的二元关系R x, y |x y x是质数，贝U R=(列举法)。R的关系矩阵Mr=4、设代数系统A , *，其中A=a , b , c,则幺元是*abcaabcbbbccccb;是否有对称性5、n个结点的无向完全图 Kn的边数为7 (N :自然数集,6.设 A x|(x N)且(x 5), B x|x E 且x7 .

2、A , B, C表示三个集合，文图中阴影部分的集合表达式为xP(x) xP(x)在I下真值为11 .设 A=a , b , c, d，其上偏序关系R的哈斯图为c8 .设P, Q的真值为0, R, S的真值为1，贝U(P (Q (R P) (R S)的真值=9 若解释I的论域D仅包含一个元素，则10 .设A=1 , 2 , 3 , 4, A上关系图为则R2 =则R=12 .图的补图为13 .设A=a , b , c, d , A上二元运算如下:*abcdaabcdbbcdaccdabddabc那么代数系统的幺元是 _a，有逆元的元素为a,b c,d，它们的逆元分别为a,d,c,b。14 . n个

3、结点的树中有 n-1 条边。.15 .设 A 0,1,2,3 , A 上的关系为 R 0,1 , 0,2 , 0,3 , 1,2 , 1,3 ,2,3，若 Rm0,3 ，贝U m =3;若 Rn ,则 n 4。16 .设 A a, b,c , A 上的二元关系 R=,，贝U r(R)=va,a,vc,c,va,b,vb,c,vc,a; S(R),17 . I是整数集，如果(I, + )是群，那么(I, + )的幺兀是0; n是任意一个整数，则n的逆元是-n 。18 .若集合A=1,2, 3上的二元关系R1和R2的关系图如下所示，Df 一一贝U R10R2 = ,19 .设f, g是自然数集N上

4、的函数 x N, f (x) x 1, g(x) 2x ,则 f g(x) 2x+2。20 .设 A=a , b , c, A 上二元关系 R= , , ,贝 Us(R)=,。21 . A=1 , 2, 3 , 4 , 5 , 6, A上二元关系T x, y | x y是素数，则用列举法T= , ；T的关系图为 ；T具有反自反，反对称，反传递 性质。A22 .集合 A , 2, 2的幕集 2 = 州2 , /, 2, 为,2,2 。23 . P, Q 真值为 0 ; R, S 真值为 1。则 wff (P (R S)(P Q)(R S)的真值为 J。24 .求一个公式的主析取或主合取范式的方法

5、，有_真值表 和 _等值演算_ 法。25 .给定谓词合式公式 A，其中一部分公式形式为(x)B(x)或(x)B(x)，则量词 ， 后面所跟的 x称为指导变元,而称 B为相应量词的辖域。26 .集合 X=a , b , c, d上二元关系 R= , , , , , 贝U R 的 自 反 闭 包 r(R)=_, ,对称闭包 s(R)= , , , , , , 。27 .对代数系统 ,其中*是S上的二元运算，若 a , b S,且对任意的x S,都有a*x=x*a=x , b*x=x*b=b ,则称a为运算“ * ”的单位元 ，称b为运算“ * ”的_零元。28 .设是群，则满足结合律和_交换律，单

6、位元，逆元 29 .一个连通且一无回路的无向图称为树。30 .在简单无向图G=中，如果V中的每个结点都与其余的所有结点邻接，则该图称为J完全图_,如果V有n个结点，那么它还是度正则图。31 .任意两个不同的小项的合取为矛盾式，全体小项的析取式必为重言_式。32 .设集合 M=x|1 WxW12,x 被 2 整除，x Z,N=x|1 x12,x 被 3 整除，x Z，则M QN=_, M U N=_。33 .设 X=1 , 2 , 3, f: XtX, g : XtX, f=,g=,则 f g=_ ,g f=_ 。34 .设A=a,b,c , R是A上的二元关系，且给定R=, ，贝U R的自反闭

7、 包 r(R)=_,_ , 对 称闭包s(R)=, 。35 .设Q为有理数集，笛卡尔集S=Q XQ , *是S上的二元运算，, S,*=,贝 H * 运算的单位元是。 S, 若 a 丸，贝H 的逆元是。36 .设*是集合S上的二元运算，若运算*满足结合律 存在 单位元 ，则称为有么半群。37 .如下无向图割点是d,割边是e5。38 无向图G具有生成树，当且仅当 _连通且无回路 G的所有生成树中_权最小勺生成树称为最小生成树。39 所谓_简单命题是指不能再分解的命题，而复合命题是由一些_简单命题_经过联结词复合而成的命题。40 .在命题演算中，两个命题的合取、析取、条件、双条件均为复合命题。41

8、 使公式(x)( y)(A(x)B(y)( x)A(x) ( y)B(y)成立的条件是 _A_中不含 y,_B_中不含x。42 .设 A=1 , 2 , 3 , 4, R 是 A 上的二元关系， R=|x/y 是素数，贝U domR=2 ,3 , 4 ;ranR= 1,2。43 .设X=1 , 3 , 5 , 9, 15 , 45 , R是X上的整除关系，则 R是X上的偏序，其最大元是45 ，极小兀是 1。44 .树是不包含回路的_连通图。45. 设F(x):x是人，H(x,y):x与y 样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_ x y(F(x) F(y) H (x, y)。4

9、6. (p q) p q从公式分类角度来看，它为 重言式式。47. 设 R=,贝 UR 的对称 闭包是,。48. x(A(x) B(x)_ xA(x) (x)B(x)49. 设F(x):x是人，H(x):x呼吸，在一阶逻辑中，命题“凡人都呼吸”的符号化形式为=(x)(F(x)H(x)_。50. 一个3阶有向图的度序列是 2 , 2, 4，入度序列是2 , 0 , 2，出度序列是0,2,2 。51. 一无向图存在生成树的充分必要条件是无向图是连通图。52 . 量词否定等值式xA( x) x A(x)。53 .设 R 是 A=1 , 2 , 3, 4上的二元关系,R=,v1,2,v2,3,则R的对

10、称闭包是,。54 .已知n阶无向简单图G有m条边，则G的补图有(n(n-1)/2)-m条边。55 .已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m ,贝U m=9.56 .设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 _2个5度结点。57 .有向图中从vi到V2长度为 2的通路有 0条。n58 .任何(n,m)图G = (V,E),边与顶点数的关系是 d(v) 2m。i 159 .已知一棵无向树 T有三个3顶点，一个2度顶点，其余的都是1度顶点,则T中有 2个1度顶点。61右图62 .设为代数系统,运算如下:*abcaabcbbaccccc则它的幺元为a零元为

11、cb、c的逆元分别为c无逆元63 .设 A=1，2，3，4，A 上二元关系 R=1 ，2，2，1， , 画出R的关系图64 . 设 A=, , B=,则 A B=,。A B =, 。265 .设|A|=3，贝H A上有23 =512 个二元关系。66 . A=1 , 2, 3上关系 R= , 时，R 既是对称的又是反对称的。01010011的邻接矩阵A=0100011067 偏序集A, R贝H R = ,U IA。68 Q:我将去上海，R:我有时间，公式(Q R) (R Q)的自然语言为我在上海当且仅当我有空。69 .若P，Q为二命题，P Q真值为1，当且仅当P,Q 同为真命题或同为假命题70

12、 .对公式(yP(x,y) zQ(x,z)xR(x, y)中自由变元进行代入的公式为 _( yP(u, y) zQ(u,z) xR(x, v)。71 .若R是集合A上的偏序关系，则 R满足 自反性 反对称性 传递性。72 .设 M x1 x 12,x被2整除，x Z , N x1 x 12,x被3整除，x Z,贝H M N 6,12, M N 2,4, 8,10273 .在一个有 n个元素的集合上，可以有_22 种不同的关系，有nn种不同的函数。74 .若关系R是反对称的，当且仅当关系矩阵中以主对角线为对称的元素不能同时为1 ,在关系图上两个不同节点间的定向弧线，不可能成对出现。75 设g f

13、是一个复合函数，若g和f都是满射，则g f为 满射若 g禾廿f者E是单射，贝H g f 是 单:射 。76 .设A 2 , a ,3 , 4 , B a , 3,4,1，请在下列每对集合中填入适当的符号：(1) a戈B ,a,4,3 A。0 , x是奇数，77 设A 0,1 , N为自然数集，f(x)若f: AA，则f是1 , X是偶数。双射 射的，若f: na，贝y f是 满射的。78 .设图G = 中有7个结点，各结点的次数分别为2 , 4, 4, 6 , 5 , 5 , 2 ,则G中有 14条边，根据握手定理。79 两个重言式的析取是重言式，一个重言式和一个矛盾式的合取是矛盾式 。80 .设个体域为自然数集，命题“不存在最大自然数”符号化为x y(y x)。81、设 I 为整数集合，A xx230,x I ,B xx是素数，x 20,C1,3,5，则(AB)C123,5(BA)C135,7,11,13,17,19(BC)A82、设