離散數(shù)學大作業(yè)

1、一、簡要回答下列問題：（每小題3分，共30分）1請給出集合的結合率。答：結合律(AUB)UC=AU(BUC)x(AUB)UC，即 xAUB 或 xC即 xA 或 xB 或 xC即 xA 或 xBC即 xAU(BUC)說明 (AUB)UC包含于AU(BUC)同理可證AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC)2請給出一個集合A，并給出A上既不具有自反性，又不具有反自反性的關系。3設A=1，2，問A上共有多少個不同的對稱關系？答：不同的對稱關系有：8種R = R = R = R = ,R = ,R = ,R = ,R = ,4設A=1，2，3，4，5，6，R是A上的整除關系

2、，M=2,3，求M的上界，下界。R = ,M=2,3 其上界為6，下界為15關于P，Q，R請給出使極小項m0，m4為真的解釋。答：m0= pqr m4 = pqr6什么是圖中的簡單路？請舉一例。答：圖的通路中，所有邊e1,e2,ek互不相同，稱為簡單通路。7什么是交換群，請舉一例。答：如果群G，*中的運算*是可以交換的，則稱該群為可交換群，或稱阿貝爾群。如I，+是交換群。8什么是群中右模H合同關系？答：設G是群，H是G的子群，a,bG，若有hH， 使得a =bh，則稱a合同于b（右模H），記為ab（右mod H）9什么是有壹環(huán)？請舉一例。答：幺元：如果A中的一個元素e，它既是左幺元又是右幺元，

3、則稱e為A中關于運算的幺元。 顯然，對任一x A，有 e x = x e = x環(huán)設是具有兩個二元運算 和*的代數(shù)系統(tǒng)，如果適合: 是交換群(阿貝爾群)； 是半群； 運算對運算是可分配的，即： a (b c) = (a b) (a c) (b c) a = (b a) (c a) 則稱是環(huán)。含幺環(huán)：如果是獨異點(或含幺半群)，則稱是含幺環(huán)。設 V=是半群，如果V中有幺元存在，則稱V為含幺半群，也稱為獨異點。設V=是代數(shù)系統(tǒng)，是非空集合A上的二元運算，如果是可結合的，即對任意的x,y,zA,有 (xy)z = x(yz)則稱V為半群。10什么是極大理想？請舉一例。答：一個環(huán)R的一個不等于的理想I

4、叫做一個最大理想，假如除了R同I自己外沒有包含A的理想。二、（12分）R，S是集合A上的兩個關系。試證明下列等式：（1）(RS)-1= S-1R-1證明：先證(RS)-1 S-1R-1，對任意(x，y) (RS)-1，則(y，x) (RS)，則存在aA，滿足(y，a) R且(a，x) S，那么(x，a) S-1且(a，y) R-1，所以(x，y) S-1R-1，因此(RS)-1 S-1R-1；再證S-1R-1 (RS)-1，對任意(x，y) S-1R-1，則存在aA，滿足(x，a) S-1且(a，y) R-1，所以(y，a) R且(a，x) S，所以(y，x) (RS)，所以(x，y) (RS

5、)-1，因此S-1R-1 (RS)-1。（2）(R-1)-1= R證明：先證(R-1)-1 R，對任意(x，y) (R-1)-1，則(y，x) R-1，則(x，y) R，所以(R-1)-1 R；再證R (R-1)-1，對任意(x，y) R，則(y，x) R-1，則(x，y) (R-1)-1，所以R (R-1)-1。故(R-1)-1= R得證。三、（20分）指出下列公式哪些是恒真的哪些是恒假的：(1)P（P Q）Q(2)（P Q）（PQ）(3)（P Q） （QR）（P R ）(4)（P Q）（P QP Q）解：(1)P（P Q）Q是恒真的Q），(2)（P Q）（P是恒真的，(3)（P Q） （Q

6、R）（P R ）是恒真的，(4)（P Q）（P QP Q）是可滿足的。四、（18分）指出下列表達式中的自由變量和約束變量，并指明量詞的作用域：（1）(xP(x)$xQ(x)(xP(x)Q(y)（2）$xy(P(x)Q(y)zR(z)（3）A(z)(xyB(x，y，a)（4）x A(x)yB(x，y)（5）($xF(x)yG(x，y，z)$zH(x，y，z)答：（1）(xP(x)xQ(x)(xP(x)Q(y)3個x都是約束變量，y為自由變量第一個x的作用域是第一個P(x)第2個x的作用域是第2個P(x)x的作用域是Q(x)（2）x,y,z都是約束變量（3）x,y是約束變量，z為自由變量（4）A(

7、x)中的x是約束變量，B(x,y)中的x是自由變量，y是約束變量（5）F(x)中的x是約束變量 G(x,y,z)中的y是約束變量，x,z是自由變量 H(x,y,z)中的z是約束變量，x,y是自由變量。五、（20分）一公司在六個城市c1，c2，c6中的每一個都有分公司。從ci到cj的班機旅費由下列矩陣中的第i行第j列元素給出(表示沒有直接班機)： 0 50 40 25 10 50 0 15 20 25 15 0 10 20 40 20 10 0 10 25 25 20 10 0 55 10 25 25 55 0公司所關心的是計算兩城市間的最便宜路線的表格。請準備一張這樣的表格。C1C2C3C4C5C6C035C1C6 C245C1C5 C3或C1C6 C4C3或C1C5 C4C335C1C5 C4或C1C6 C425C1C5 10C1C6 C235C2C6 C1015C2 C320C2C4 30C2C4 C525C2C6C345C3C4 C6 C1或C3C5 C1或C3C4 C5C115C3C2 010C3C4 20C3C4 C5或C3C535C3C4 C6C435C4C5 C1或C4C6 C125C4C2 10C4C3 010C4C525C4C6 C525C5 C130C5C4 C220C5C4 C