可做奧鵬院校所有作業(yè)，畢業(yè)論文，咨詢請?zhí)砑観Q：3230981406 微信：aopopenfd777
東 北 大 學(xué) 繼 續(xù) 教 育 學(xué) 院
離散數(shù)學(xué) X 試 卷（作業(yè)考核 線上2） A 卷（共 4 頁）
總分 題號 一 二 三 四 五 六 七 八 九 十
得分
一、 (13分)有兩個小題
1．分別說明聯(lián)結(jié)詞?、∧、∨、→和?在自然語言中表示什么含義。
2．分別列出P?Q、P?Q、P?Q、P?Q的真值表(填下表)。
P Q P?Q P?Q P?Q P?Q
二、 (10分)寫出命題公式 (Q→)→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的冪集。分別計(jì)算：
（注意：要求有計(jì)算過程，不能直接寫出結(jié)果！）
(1) A×P(B)
(2) AB
(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.寫出關(guān)系R的矩陣；再畫出上述各個關(guān)系的有向圖。
2.判斷各個關(guān)系性質(zhì)。用“√”表示“是”，用“×”表示“否”，填下表：
自反的 反自反的 對稱的 反對稱的 傳遞的
R
S
T
M
3.上述四個關(guān)系中，哪些是等價關(guān)系？哪些是偏序關(guān)系？
對等價關(guān)系，寫出此等價關(guān)系的各個等價類。
4.求復(fù)合關(guān)系RoT
六. (12分) R是實(shí)數(shù)集合，給出R上的運(yùn)算如下：×、+、|x-y|、min、max,分別表示乘法、加法、x-y的絕對值、兩個數(shù)中取最小的、兩個數(shù)中取最大的運(yùn)算。
1. 判斷各個運(yùn)算性質(zhì)。用“√”表示“是”，用“×”表示“否”，
填下表：
|x-y| max × min +
有交換性
有結(jié)合性
有冪等性
有幺元
有零元
2.指出R對上面哪些運(yùn)算構(gòu)成群？.
七. (14分) 有三個小題
1. 指出下面各個圖中哪些是彼此同構(gòu)的.
2.上面圖b與c顯然是不同構(gòu)的，請說明不同構(gòu)的理由（說明一個即可。）
3.請畫出五個具有五個結(jié)點(diǎn)的無向圖，使之分別滿足：
(1) 是歐拉圖但不是漢密爾頓圖。
(2) 既是歐拉圖也是漢密爾頓圖。
(3) 是完全圖K5。
(4) 是棵樹。
(5) 是漢密爾頓圖但不是歐拉圖 。
