离散数学试题 D.doc

离散数学试题 D 题号 一 二 三 四 五 六 七 八 九 十 总分 分数 一、单项选择（每题3分，共15分） 1. 设A＝{a，b，c}，B＝{a，b}，则下列命题不正确的是（ ）A．B－A＝ΦB．BA； C．A－B＝{c}D．AB＝{a，b} 2. 设A={1，2，3，4}，下列关系中 为等价关系。 （a）R={（1，1），（1，2），（2，1），（2，2），（3，3）} （b）R={（1，1），（1，3），（2，2），（3，3），（4，4）} （c）R={（1，1），（1，3），（2，2），（3，1），（3，3），（4，4）} （d）R={（1，1），（1，3），（2，2），（3，2），（4，4）} 3.下列图中是Euler图的是 。 4．设f是实数集R到R的函数，则f是双射函数的是（）。 (a), (b), (c), (d) 5. 利用谓词的约束变元改名规则和自由变元代入规则，可将如下公式：（x）（P（x）→Q（x，y））R（x，y）改写成（ ） A．（x）（P（y）→Q（x，y））R（z，s） B．（z）（P（z）→Q（z，s））R（x，s） C．（x）（P（s）→Q（x，s））R（x，y） D．（x）（P（s）→Q（z，s））R（z，s），求2。 2． 设G是具有21条边的无向简单图，其中有3个4度结点，其它结点都是3度。问G有几个结点。 3.将下列命题符号化(分析到个体词、谓词和量词)： “如果一个人怕困难，就不会获得成功。而爱迪生获得了成功，所以爱迪生不怕困难”。 4. =3，，则① A到B上的不同关系有多少个? ② A到B上的不同函数有多少个? ③ A到B上的不同单射函数有多少个? ④ B到A的不同满射函数有多少个? 5．求图2的最小生成树。 三、如图3，⑴求图的邻接矩阵A; （6分） ⑵求从C到D的长为3的所有通路； ⑶通过计算来验证⑵中的结论。 四、设，试给出A上的等价关系R，使得 。 （6分） 五、设 X={a，b，c，d}上的关系R={（a，b），（b，a），(b,c),(c,d)}。 求R的传递闭包t（R）。 （9分） 六、求公式的主取范式分）的次序图(Hass图)； (2) 问 S={2，3，5，7}是否有最大元，最小元，极大（小）元，上（下）界，上（下）确界？若有请求出。 八、设是群，则是交换群都有。（5分） 九、设是模4的加法。（9分） ⑴给出群的运算表。 ⑵求各元素的周期，并指出生成元； ⑶求其非平凡子群及其陪集。 十、符号化下列命题,并用演绎法证明其结论。（6分） “若乙不到，则甲不到”；“若乙到，则甲和丙就到”。因此，“若甲到，则丙就到” (d) (c) (b) (a) 图1 图3 C D B 9 10 8 7 6 5 4 4 3 2 F E D C B A A 图2