東 北 大 學 繼 續(xù) 教 育 學 院

離散數學（一）X 試 卷（作業(yè)考核 線上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)) T $xA(x)

四．(12分)令集合A={1,{1}},B={1}，P(A)表示A的冪集。分別計算：

  （注意：要求有計算過程，不能直接寫出結果?。?/p>

(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) 是漢密爾頓圖但不是歐拉圖 。