东大21秋学期学期《离散数学》在线平时作业3[答案]

东大21秋学期学期《离散数学》在线平时作业3[答案]答案

《离散数学》在线平时作业3

试卷总分:100  得分:100

一、单选题 (共 10 道试题,共 50 分)

1.单选题。结点是树的叶结点，当且仅当 该结点（          ）。

A.度数不为0；

B.度数大于1；

C.度是等于1。

 

2.{图}

A.{图}

B.{图}

C.{图}

D.{图}

正确答案:-----

 

3.{图}

A.矛盾式

B.重言式

C.无法确定

D.不知道

正确答案:-----

 

4.下面是

"xC(x),  $x(A(x)ÚB(x)),   "x(B(x)?ØC(x))  Þ $xA(x)

的谓词推理过程。在这个过程中每一步中的（  ）处是此步所用的推理规则。请写出这些推理规则。

⑴ $x(A(x)ÚB(x)),      (    )

⑵ A(a)ÚB(a)              (    )  ⑴

⑶ "xC(x)                   (    )    

⑷ C(a)                        (     )  ⑶  

⑸ "x(B(x)→ØC(x))    (    ) 

⑹ B(a)→ØC(a)          (    )  ⑸

⑺ ØB(a)                      (    )  ⑷ ⑹ I12

⑻ A(a)                        (    )  ⑵ ⑺ I10

⑼ $xA(x))                   (    )   ⑻

A.⑴ P；⑵ T； ⑶ T；⑷ UG；⑸ P；⑹ US；⑺ P；⑻ T；⑼ ES。

B.⑴ P；⑵ EG；⑶ T；⑷ UG；⑸ P；⑹ UG；⑺ P；⑻ T；⑼ EG。

C.⑴ P；⑵ ES；⑶  P；⑷ US；⑸ P；⑹ US；⑺ T；⑻ T；⑼ EG。

D.⑴ P；⑵ US；⑶ T；⑷ UG；⑸ P；⑹ UG；⑺ P；⑻ T；⑼ UG。

正确答案:-----

 

5.下面的命题公式中不是永真式的是（      ）。

A.(P∧Q)→Q

正确答案:-----

B.(P∧(P→Q))→Q

正确答案:-----

C.P→(P∨Q)

D.(P∨Q)→P

正确答案:-----

 

6.选择填空。如果集合X满足  XÍD 且 XÇB＝Ф，则X可能与下面给定的集合(       )

正确答案:-----

相等。

A.A＝{1,2,3,4,5,6,7,8,9}，

B.B＝{2,4,6,8}，

C.C＝{1,3,5,7,9}，

D.D＝{3,4,5}，

正确答案:-----

E.E＝{3,5}，

 

7.{图}

A.自然数集合

B.整数集合

C.有理数集合

D.实数集合

正确答案:-----

 

8.单选题。 无向图G=<V,E>，所有结点度数的总和等于（      ）。

A.边数；

B.边数的2倍；

C.不能确定。

 

9.单选题。无向图中，度数是奇数的结点有（       ）个？

A.奇数；

B.非负整数

C.偶数。

 

10.{图}

A.B:①：⑵⑶⑺⑻

B.B:②：⑶⑷⑻

C.B:③：⑶⑹⑺⑻

D.B:④：⑶⑺

正确答案:-----

 

东大21秋学期学期《离散数学》在线平时作业3[答案]多选题答案

二、判断题 (共 5 道试题,共 25 分)

11.判断下面命题的真值。{图}

 

12.设A={&Phi;}，B=P(P(A))。判断下面命题的真值。{图}

 

13.R是A上关系，判断下面命题的真值。{图}

 

14.判断下面命题的真值。{图}

 

15.判断题 。判断下面的说法是否正确。

R和S是A上任何自反关系，则R&cap;S 也自反。

 

三、多选题 (共 5 道试题,共 25 分)

16.下面的命题公式中哪些是永真式，只写出题号即可{图}

A.1

B.2

C.3

D.4

正确答案:-----

 

17.多选题。写出群定义中满足下面哪些性质。

A.封闭性；

B.可结合性；

C.可交换性；

D.有么元；

正确答案:-----

E.有零元。

F.每个元素有逆元；

 

21.多选填空题。给定集合A={1,2,3}，定义A上的等价关系如下：

T=A×A(完全关系（全域关系）)

等价关系T中含有等价类  (         )。

A.{1}

B.{2}

C.{3}

D.{1,2}

正确答案:-----

E.{1,3}

F.{2,3}

G.{1,2,3}

 

19.试题见图片{图}

A.a图

B.b图

C.c图

D.d图

正确答案:-----

E.e图

F.f图

G.g图

H.h图

I.i图

J.j图

 

20.多选题。 令I是整数集合；N是自然数集合，R是实数集合。＋是加法运算，×是乘法运算。下面所列代数系统哪些是独异点？

A.<I,+>,

B.<R,+>,

C.<I,×>,

D.<N,×>,

正确答案:-----

E.<R,×>。

 

东大21秋学期学期《离散数学》在线平时作业3[答案]历年参考题目如下：

东 北 大 学 继 续 教 育 学 院
     离散数学X  试 卷（作业考核 线上2）  A  卷（共 4  页）         
总分 题号 一 二 三 四 五 六 七 八 九 十
得分         
一.  (13分)有两个小题
1．分别说明联结词Ø、∧、∨、→和«在自然语言中表示什么含义。




2．分别列出PÚQ、PÙQ、P«Q、P®Q的真值表(填下表)。
P Q PÚQ PÙQ P«Q P®Q
    
    
    
    
二. (10分)写出命题公式 (Q→ØP)→Q 的主合取范式。（要求有解题过程）







三. (14分) 用谓词逻辑推理的方法证明下面推理的有效性。要求按照推理的格式书写推理过程。  
  "xC(x), $x(A(x)ÚB(x)), "x(B(x)®ØC(x)) Þ $xA(x)






四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的幂集。分别计算：
  （注意：要求有计算过程，不能直接写出结果！）
(1)  A×P(B)
 

(2)  A⊕B


(3)  P(A)－P(B)






五. (25分)给定集合A={1,2,3},定义A上的关系如下：
R={<1,2>,<2,3>,<3,1>}
S=A×A(完全关系（全域关系）)
T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}
M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

   
   
1.写出关系R的矩阵；再画出上述各个关系的有向图。







2.判断各个关系性质。用“√”表示“是”，用“×”表示“否”，填下表：
自反的 反自反的 对称的 反对称的 传递的
R    
S    
T    
M    
3.上述四个关系中，哪些是等价关系？哪些是偏序关系？对等价关系，写出此等价关系的各个等价类。





4.求复合关系RoT




六. (12分) R是实数集合，给出R上的运算如下：×、+、|x-y|、min、max,分别表示乘法、加法、x-y的绝对值、两个数中取最小的、两个数中取最大的运算。







1. 判断各个运算性质。用“√”表示“是”，用“×”表示“否”，
填下表：
|x-y| max  × min +
有交换性    
有结合性    
有幂等性    
有幺元    
有零元    
2.指出R对上面哪些运算构成群？.



七. (14分) 有三个小题
   1. 指出下面各个图中哪些是彼此同构的.






2.上面图b与c显然是不同构的，请说明不同构的理由（说明一个即可。）





3.请画出五个具有五个结点的无向图，使之分别满足：
    (1) 是欧拉图但不是汉密尔顿图。
    (2) 既是欧拉图也是汉密尔顿图。
    (3) 是完全图K5。
(4) 是棵树。
(5) 是汉密尔顿图但不是欧拉图 。