离散数学习题2.doc

《离散数学》习题2 一、单项选择题 1．下列各式中判断自由变元和约束变元不正确的是（ ）。 A.,其中x是约束出现 B.,其中x是约束出现，而y是自由出现 C., 其中x和y都是约束出现 D., 其中x和y都是约束出现 2．设,则（ ）。 A. B. C. D. 3．设,则A上不同的等价关系总共有（ ）。 A.3个 B.4个 C.5个 D.6个 4．在自然数集N上，下列（ ）运算是可结合的，对于任意。A. B. C. D. 5．集合｛a,b,c｝到集合｛0,1｝可定义的特征函数的个数为（ ）。 A.3 B.6 C.8 D.9 6．整数集合Z上的关系的传递闭包是关系（ ）。 A. B. C.全域关系 D. 7．数的加法在下列集合上封闭的是（ ）。 A. B. C. D. 8．设，其中R为实数集合，为正实数集合，+和*分别表示普通的加法和乘法，令，下面四个命题中为真的是（ ）。 A. B. C. D.，但A,B,C都不是 9．三阶群中不同构的有（ ）个。 A.1 B.2 C.3 D.4 10．设,*为普通乘法，则代数系统的幺元为（ ）。 A.不存在 B. C. D. 11．完全图K3的不同构的生成子图的个数为（ ）。 A.3 B.4 C.5 D.6 12．仅有孤立点组成的图是（ ）。 A.零图 B.平凡图 C.完全图 D.子图 13．任意具有多个等幂元的半群，它（ ）。 A.不能构成群 B.不一定能构成群 C.不能构成交换群 D.能构成交换群 14．整数集合Z上的关系的传递闭包是关系（ ）。 A. B. C.全域关系 D. 15．设,则A上不同的等价关系总共有（ ）。 A.3个 B.4个 C.5个 D.6个 16．数的加法在下列集合上封闭的是（ ）。 A. B. C. D. 17．设,*为普通乘法，则代数系统的幺元为（ ）。 A.不存在 B. C. D. 18．完全图K3的不同构的生成子图的个数为（ ）。 A.3 B.4 C.5 D.6 19．设是一个有界格，它也是有补格，只要满足（ ）。 A.每个元素都有一个补元 B.每个元素都至少有一个补元 C.每个元素都无补元 D.每个元素都有多个补元 20．具有如下定义的代数系统，（ ）不构成群。 A.G={1，10},*是模11乘 B.G={1，3，4，5，9},*同是模11乘 C.G=Q(有理数),*是普通加法 D.G=Q(有理数),*是普通乘法 二、判断题 1．联结词集合是功能完备集。（ ） 2．设A为任意一个集合，则。（ ） 3．设是不同的命题变元，关于的极大项是简单析取式，但简单析取式不一定是极大项。（ ） 4．设个体域是自然数集合，p 代表 xy彐z F（x－y = z），则 p 是真命题。( ) 5．自然数 N 与其上的普通加法 + 构成的代数系统 〈N，+〉 是群。 ( ) 6．命题公式 A =﹁（p→q）∧q 的主析取范式为 A〈=〉∑（0）。 ( ) 7．边数 m 等于 n-1 的 n 阶无向图都是树。 ( ) 8．非平凡无向树 T 至少两片树叶。 ( ) 三、填空题 1．设*为集合A上二元运算，若A中一个元素e，它既是___，又是___，则称e是A中关于*的幺元。 2．谓词公式是___，是___。（填逻辑有效式或矛盾式） 3．原子Q既可说成是___范式，也可说成是___范式。 4．设是群，若运算*在G上满足交换律，则称G为______群或______群。 5．若连通平面图有4个结点，3个面，则有______条边。 四、综合题 1．在一阶逻辑中，将下面命题符号化，并且要求