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

離散數(shù)學(xué)（一）X 試 卷（作業(yè)考核 線上2）  A  卷（共    4    頁(yè)）

總分 題號(hào) 一 二 三 四 五 六 七 八 九 十

得分         

一、 (13分)有兩個(gè)小題

1．分別說(shuō)明聯(lián)結(jié)詞?、∧、∨、→和?在自然語(yǔ)言中表示什么含義。

2．分別列出PúQ、PùQ、P?Q、P?Q的真值表(填下表)。

P Q PúQ PùQ P?Q P?Q

二. (10分)寫(xiě)出命題公式 (Q→?P)→Q 的主合取范式。（要求有解題過(guò)程）

三、(14分) 用謂詞邏輯推理的方法證明下面推理的有效性。要求按照推理的格式書(shū)寫(xiě)推理過(guò)程。  

  ?"xC(x), $x(A(x)úB(x)), "x(B(x)??C(x)) T $xA(x)

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

  （注意：要求有計(jì)算過(guò)程，不能直接寫(xiě)出結(jié)果?。?/p>

(1)  A×P(B)

(2)  A⊕B

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

五. (25分)給定集合A={1,2,3},定義A上的關(guān)系如下：

R={<1,2>,<2,3>,<3,1>}

S=A×A(完全關(guān)系（全域關(guān)系）)

T={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>}

M={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

1.寫(xiě)出關(guān)系R的矩陣；再畫(huà)出上述各個(gè)關(guān)系的有向圖。

2.判斷各個(gè)關(guān)系性質(zhì)。用“√”表示“是”，用“×”表示“否”，填下表：

自反的 反自反的 對(duì)稱(chēng)的 反對(duì)稱(chēng)的 傳遞的

R    

S    

T    

M    

3.上述四個(gè)關(guān)系中，哪些是等價(jià)關(guān)系？哪些是偏序關(guān)系？

對(duì)等價(jià)關(guān)系，寫(xiě)出此等價(jià)關(guān)系的各個(gè)等價(jià)類(lèi)。

4.求復(fù)合關(guān)系RoT

六. (12分) R是實(shí)數(shù)集合，給出R上的運(yùn)算如下：×、+、|x-y|、min、max,分別表示乘法、加法、x-y的絕對(duì)值、兩個(gè)數(shù)中取最小的、兩個(gè)數(shù)中取最大的運(yùn)算。

1. 判斷各個(gè)運(yùn)算性質(zhì)。用“√”表示“是”，用“×”表示“否”，

填下表：

|x-y| max  × min +

有交換性    

有結(jié)合性    

有冪等性    

有幺元    

有零元    

2.指出R對(duì)上面哪些運(yùn)算構(gòu)成群？.

七. (14分) 有三個(gè)小題

   1. 指出下面各個(gè)圖中哪些是彼此同構(gòu)的.

2.上面圖b與c顯然是不同構(gòu)的，請(qǐng)說(shuō)明不同構(gòu)的理由（說(shuō)明一個(gè)即可。）

3.請(qǐng)畫(huà)出五個(gè)具有五個(gè)結(jié)點(diǎn)的無(wú)向圖，使之分別滿足：

    (1) 是歐拉圖但不是漢密爾頓圖。

    (2) 既是歐拉圖也是漢密爾頓圖。

    (3) 是完全圖K5。

(4) 是棵樹(shù)。

(5) 是漢密爾頓圖但不是歐拉圖 。