2006年7月全国自考离散数学试题试卷真题及答案.docVIP

2006年7月全国自考离散数学试题试卷真题 一、单项选择题（本大题共15小题，每小题1分，共15分） 1．下列语句中不是命题的只有（　　　） A．鸡毛也能飞上天？ B．或重于泰山，或轻于鸿毛。 C．不经一事，不长一智。 D．牙好，胃口就好。 2．从真值角度看，命题公式的全部类型是（　　　） A．永真式 B．永假式 C．永真式，永假式 D．永真式，永假式，可满足式 3．设M（x）：x是人；F（x）：x要吃饭。用谓词公式表达下述命题：所有的人都要吃饭，其中错误的表达式是（　　　） A． B． C． D． 4．下列公式是前束范式的是（　　　） A． B． C． D． 5．设论域为整数集，下列真值为真的公式是（　　　） A． B． C． D． 6．下列是谓词演算中的合式公式的是（　　　） A． B． C． D． ．（　　　） A．B． C．D． ．（　　　） 8．下列式子正确的是（　　　） A．（A－B）-C=A-（B∪C） B．A－（B∪C）=（A－B）∪C C．~（A－B）=~（B－A） D．~（A∩B）A 9．下列集合对所给的运算是封闭的只有（　　　） A．非零整数集合Z*上的除法运算 B．全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算 C．全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算 D．A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍数 10．设A，，*是环，则下列说法不正确的是（　　　） A．A，是交换群 B．A， *是半群 C．*对是可分配的 D．对*是可分配的 11．下列四个格，是分配格的是（　　　） 12．下列各图是无向完全图的是（　　　） 13．下列各有向图是强连通图的是（　　　） 14．设Ｇ是具有n个结点的无向简单图，若在Ｇ中存在一条汉密尔顿路，则Ｇ中每一对结点的度数之和与n-1的关系为（　　　） A．大于 B．大于等于 C．等于 D．小于 15．设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（　　　） A．e-n+r=2 B．n+r-e=2 C．n-r+e=2 D．n-e-r=2 二、填空题（本大题共10小题，每小题2分，共20分） 请在每小题的空格中填上正确答案。错填、不填均无分。 16．所谓___是指不能再分解的命题，而复合命题是由一些____经过联结词复合而成的命题。 17．在命题演算中，两个____的合取、析取、条件、双条件均为____。 18．使公式成立的条件是____中不含y，____中不含x。 19．设A={1，2，3，4}，R是A上的二元关系，R={x,y|x/y是素数}，则domR=_____; ranR=____。 20．设无向图Ｇ有n个结点m条边，每个结点的度数为k或k+1，记Nk为度数等于k的结点数，则Nk=_____。如果无向简单图C的结点的度数均为相同的偶数，且m=7，则n=____。 21．设X={1，3，5，9，15，45}，R是X上的整除关系，则R是X上的偏序，其最大元是___，极小元是____。 22．设是有界格，a,bL,若ab=0,则a=b=_____；若ab=1,则a=b=____。 23．设e是群G上的幺元，若aG且a2=e,则a-1=____ ,a-2=__________。 24．代数系统A,。，其中A为命题公式集合，。为析取运算，则A，。中零元素是____，幺元是____。 25．树是不包含_____的___图。 三、计算题（本大题共6小题，第26、27题各4分，第28、29题各5分，第30、31题各6分，共30分） 26．如果论域是集合{a,b,c}，试消去下面公式中的量词： 27．求公式（的主析取范式。 28．设A={a,b,c},A上二元关系R={a,a,a,c,b,a},用关系矩阵法求最小的自然数m,n,mn使Rm=Rn。 29．根据下列条件如果能画则请画出一个欧拉图，如果不能画则请说明理由。 （1）偶数个顶点，偶数条边 （2）奇数个顶点，奇数条边 （3）偶数个顶点，奇数条边 （4）奇数个顶点，偶数条边 30．下列各整数集合对于整除关系“|”都构成偏序集，判断哪些偏序集能构成格？并说明理由。 1)L={1,2,3,4,5} 2) L={1,2,3,6,12} 3)L={1,2,3,4,6,9,12,18,36} 4)L={1,2,22,23,…,2n} 31．设A={2，3，5，12，19}，等价关系R={x,y|x, (mod 3)},写出各元素的等价类，并求A/R。