离散填空题和答案(8页).doc

《离散填空题和答案(8页).doc》由会员分享，可在线阅读，更多相关《离散填空题和答案(8页).doc（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-离散填空题和答案-第 8 页填空1、：你努力，：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为2、论域D=1，2，指定谓词PP (1,1)P (1,2)P (2,1)P (2,2)TTFF则公式真值为 。3、设A=2，3，4，5，6上的二元关系，则R= （列举法）。R的关系矩阵MR= 0 1 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 10 0 0 0 0 。*a b cabca b cb b cc c b4、设代数系统，其中A=a，b，c,则幺元是 ；是否有对称性 。5、n个结点的无向完全图Kn的边数为 。6设 （N：自然数集

2、，E+ 正偶数） 则 。7A，B，C表示三个集合，文图中阴影部分的集合表达式为 A B C。8设P，Q 的真值为0，R，S的真值为1，则的真值= 。9若解释I的论域D仅包含一个元素，则 在I下真值为 （T，F）。10设A=1，2，3，4，A上关系图为则 R2 = 。11设A=a，b，c，d，其上偏序关系R的哈斯图为则 R= 。12图的补图为 。13设A=a，b，c，d ，A上二元运算如下：*a b c dabcda b c db c d ac d a bd a b c那么代数系统的幺元是 a ，有逆元的元素为 a,b c,d ，它们的逆元分别为 a,d,c,b 。14n个结点的树中有 n-1

3、条边。.15设，A上的关系为,若，则m3;若4。16设，A上的二元关系R=,，则 ,; , .17I是整数集，如果（I，+）是群，那么（I，+）的幺元是 0 ；n是任意一个整数，则n的逆元是 -n 。18若集合A=1, 2, 3上的二元关系R1和R2的关系图如下所示，则R1oR2 = , 19设 f，g是自然数集N上的函数，则 2x+2 。20设A=a，b，c，A上二元关系R= , , , 则s（R）= , 。21A=1，2，3，4，5，6，A上二元关系，则用列举法 T= , ；T的关系图为T具有 反自反，反对称，反传递 性质。22集合的幂集= ,2，2, ,2,2 。23P，Q真值为0 ；R

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

5、无回路_的无向图称为树。30在简单无向图G=中，如果V中的每个结点都与其余的所有结点邻接，则该图称为_ _完全图_，如果V有n个结点，那么它还是_ n _度正则图。31任意两个不同的小项的合取为_矛盾_式，全体小项的析取式必为_重言_式。32设集合M=x|1x12,x被2整除，xZ,N=x|1x12,x被3整除，xZ，则 MN=_6,12_，MN=_2,3,4,6,8,9,10,12_。33设X=1，2，3，f：XX，g：XX，f=,g=,，则fg=_,_，gf=_,_。34设A=a,b,c，R是A上的二元关系，且给定R=,，则R的自反闭包r(R)= _,_，对称闭包s(R)= _,_。35设

6、Q为有理数集，笛卡尔集S=QQ，*是S上的二元运算，,S, *=, 则*运算的单位元是_。S, 若a0，则的逆元是_。36设*是集合S上的二元运算，若运算*满足_结合律_且存在_单位元_，则称为有么半群。37如下无向图割点是_d_，割边是_e5_。38无向图G具有生成树，当且仅当_连通且无回路_。G的所有生成树中_权最小_的生成树称为最小生成树。39所谓_简单命题_是指不能再分解的命题，而复合命题是由一些_简单命题_经过联结词复合而成的命题。40在命题演算中，两个_命题_的合取、析取、条件、双条件均为_复合命题_。41使公式成立的条件是_A_中不含y，_B_中不含x。42设A=1，2，3，4，

7、R是A上的二元关系，R=|x/y是素数，则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一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_ _。 46.从公式分类角度来看，它为_重言式_式。 47.设R=,，则R的对称闭包是, 。 48 _。49.设F(x):x是人，H(x):x呼吸，在一阶逻辑中，命题“凡人都呼吸”的符号化形式为_ _。 50.一个3阶有向图的度序列是2，2，4，入度序列是2，

8、0，2，出度序列是 0,2,2 。51.一无向图存在生成树的充分必要条件是 无向图是连通图 。52量词否定等值式 _。53设R是A=1，2，3，4上的二元关系,R=,则R的对称闭包是 , 。54已知n阶无向简单图G有m条边，则G的补图有 (n(n-1)/2)-m 条边。55已知n阶无向图G中有m条边，各顶点的度数均为3。又已知2n-3=m，则m= 9 .56设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 2 个5度结点。57有向图 中从v1到v2长度为2的通路有 0 条。58任何(n,m) 图G = (V,E) , 边与顶点数的关系是 。59已知一棵无向树T有三个3顶点,一个2度顶点

9、,其余的都是1度顶点,则T中有 2 个1度顶点。60n阶完全图Kn的边数为 n(n-1)/2 。61右图 的邻接矩阵A=62设为代数系统，* 运算如下：*abcaabcbbaccccc则它的幺元为 a ；零元为 c ； a、b、c的逆元分别为 a b c无逆元 。63设A=1，2，3，4，A上二元关系R=，画出R的关系图 。64 设A=, , B=,则= , 。= , 。65设|A|=3，则A上有 232 =512 个二元关系。66A=1，2，3上关系R= , 时，R既是对称的又是反对称的。67偏序集的哈斯图为，则= ,IA 。68Q：我将去上海，R：我有时间，公式的自然语言为我在上海当且仅当

10、我有空 。69若P，Q为二命题，真值为1，当且仅当 P,Q 同为真命题或同为假命题 。70对公式中自由变元进行代入的公式为 。71若R 是集合A上的偏序关系，则R满足 自反性 反对称性 传递性 。72设， 则 6，12 ， 2，4，8，10 。73在一个有n个元素的集合上，可以有 2n2 种不同的关系，有 nn种不同的函数。74若关系R是反对称的，当且仅当关系矩阵中 以主对角线为对称的元素不能同时为1，在关系图上 两个不同节点间的定向弧线，不可能成对出现 。75设是一个复合函数，若和都是满射，则为 满射 ，若和都是单射，则是 单射 。76设，请在下列每对集合中填入适当的符号：。 （1） , (2) 。77设，N为自然数集， 若，则是 双射 射的，若，则是 满 射的。78设图G = 中有7个结点，各结点的次数分别为2，4，4，6，5，5，2，则G中有 14 条边，根据 握手定理 。79两个重言式的析取是 重言式 ，一个重言式和一个矛盾式的合取是 矛盾式 。80设个体域为自然数集，命题“不存在最大自然数”符号化为 。81、设I为整数集合，则1,2,3,51,3,5,7,11,13,17,1982、设