成都理工大学2014－2015学年第一学期
《离散数学》考试试卷
大题 一 得分 二 三 四 五 六 七 八 九 总分 得分一、填空题（本大题共10小题，每小题2分，共20分）
1. 解释（0，1）使命题公式A?(p?(p?q))?q的真值为 。 2. 两个重言式的析取是__________________ 式，一个重言式和一个永假式的合取式是_________________式。
3．设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为_____________________________________。
4. 设F(x):x是火车，G?y?:y是汽车，H(x,y):x比y快，则“火车都比汽车快”可符号化为 。 5. A上的等价关系R的定义是???????????????????????????????。
6. 设A={1，2，3}，R={<1，2>,<1，3>} 是A上的关系，则R满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。
???????????????????????????????????????。
7. 设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统
得分二、选择题（本大题共10小题，每小题1分，共10分）
1．下列语句中，不是命题的有（ ）。
A. 5能被2整除。 C. 现在开会吗？
B.太阳系以外的星球上有生物。
D.小李在宿舍里。
2．与谓词公式 ?P?Q等价的公式是（ ）。
A. ?P?Q
C. ?P??Q
B. P??Q D. P?Q
3．下述不是偏序集合的是（ ）。
A．〈I，?〉 B．〈R，?〉
C．〈{1，2，3，6} 整除〉 D．〈{2，4，8，16}，倍数〉
4．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ）。
A．满射函数 B．单射函数 C．双射函数 D．非单射非满
5. 设个体域为整数，下列公式中真值为1的是( )。
A．?x?y(x + y = 1); B．?x?y(x + y = 1); C．?x?y(x + y = 1); D．? ?x?y(x + y = 1)。
6．设集合X为人的全体，在X上定义关系R、S为R={|a，b?X∧a是b的父亲}，S={|a，b?X∧a是b的母亲}，那么关系{|a，b? X∧ a是b的祖母}的表达式为（ ）。
A．R?S B．R-1?S C．S?R D．R?S-1
7. 满足谓词P(x,y)：xy?0的整数集Z上的二元关系具有（ ）性质？
A．反自反、对称 B．反对称、传递 C．反对称 D．自反、对称、传递
8. I为整数集，下列系统中不是代数系统的有（ ）。
A. C.
B.
9．任何图中必定有偶数个（ ）：
A、度数为偶数的结点 B、入度为偶数的结点 C、度数为奇数的结点 D、出度为奇数的结点
10．下列图形中为欧拉图的是（ ）
得分三、（本大题共10分）
求(P∨Q)←→(P∧Q)的主析取范式和主合取范式。
得 分 四、（本大题共10分）
用谓词推理理论来论证下述推证：
每个有理数都是实数,有的有理数是整数.因此,有的实数是整数。
得分五、（本大题共10分）
设 为群，任意a,b,c?A, 证明 a*b=a*c，则 b=c。
得分六、（本大题共10分）
设R＝{<1,2>,<3,4>,<2,2>}， S＝{<4,2>,<2,3>,<3,1>}，分别是定义为从A→B和从B→C的关系，其中A＝B＝C＝{1,2,3,4}。
求R?S，S?R，R?R，S?S。
得分七、（本大题共10分）
设A＝｛1，2，3，4，6，8，12，24｝，R为A上整除关系，试画 的哈斯图，并求A中的最大元，最小元，极大元，极小元。
得分八、（本大题共10分）
设无向图G=
（1） 画出G的图形；（2） 求出G中各顶点的度及奇数度顶点的个数。