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

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

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

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

4、叫做一個(gè)最大理想，假如除了R同I自己外沒(méi)有包含A的理想。二、（12分）R，S是集合A上的兩個(gè)關(guān)系。試證明下列等式：（1）(RS)-1= S-1R-1證明：先證(RS)-1 S-1R-1，對(duì)任意(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，對(duì)任意(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，對(duì)任意(x，y) (R-1)-1，則(y，x) R-1，則(x，y) R，所以(R-1)-1 R；再證R (R-1)-1，對(duì)任意(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分）指出下列表達(dá)式中的自由變量和約束變量，并指明量詞的作用域：（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個(gè)x都是約束變量，y為自由變量第一個(gè)x的作用域是第一個(gè)P(x)第2個(gè)x的作用域是第2個(gè)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分）一公司在六個(gè)城市c1，c2，c6中的每一個(gè)都有分公司。從ci到cj的班機(jī)旅費(fèi)由下列矩陣中的第i行第j列元素給出(表示沒(mé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公司所關(guān)心的是計(jì)算兩城市間的最便宜路線的表格。請(qǐng)準(zhǔn)備一張這樣的表格。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