【文章內(nèi)容簡(jiǎn)介】 前提引入F(a)174。G(a)2UI G(a)3假言推論H(a)前提引入 x(G(x)217。H(x)174。I(x))前提引入G(a)217。H(a)174。I(a)6UI G(a)217。H(a)5合取I(a)8假言推論第二篇：離散數(shù)學(xué)習(xí)題集合論={198。,1}，B={{a}}求A的冪集、AB、A∪B、A+B。={1,2,3,4,5}, R={(x,y)|x={a,b,c},R= IA ∪{(a,b),(b,a)}，求a和b關(guān)于R的等價(jià)類。，A/R={{1,2}，{3}},求A，R。，如果一定成立請(qǐng)證明，否則請(qǐng)舉出反例。①如果A∪B205。C，則A205。C或者B205。C。②如果AB=AC且A185。198。，則B=C。，R,r(R)是否一定是A上的等價(jià)關(guān)系？證明或舉例。∩C205。B∩C,AC205。BC,證明：A205。B。：AX(B∩C)=(AXB)∩(AXC)：P(A)∪P(B)205。P(A∪B)：R[sym] iff R=R：r(R)=R∪IA,S(R)=R∪R,t(R)=R∪R∪...：s(R∪S)=s(R)∪s(S)，證明：如果R是對(duì)稱的，則r(R)也是對(duì)稱的。，R={(x,y)|xy是3的倍數(shù)}，證明：R是I上的等價(jià)關(guān)系。，則A/R一定是A的劃分。，S是A上的自反和對(duì)稱關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。，R是II上的二元關(guān)系，R={,|xv=yu},證明：R是等價(jià)關(guān)系。:A174。B，R是B上的等價(jià)關(guān)系，令S={|x206。A且y206。A且206。R}，證明：S是A上的等價(jià)關(guān)系。，S是A上的自反和對(duì)稱關(guān)系，證明t(R∪S)是A上的等價(jià)關(guān)系。，請(qǐng)問P∪Q，PQ是否是A上的劃分，,R[irref]且R[tra],證明：r(R)是A上的偏序關(guān)系。{1,2,3,4,6}上整除關(guān)系的哈斯圖，求{2,3,6}的4種元素。={a,b,c,d,e,f,g},R={(a,c),(a,e),(b,d),(b,f),(d,e),(d,f)},S=tr(R),畫出S的哈斯圖并求{b,c,d,f}的極大元等8種元素。:A→B,g:B→C都是單（滿）射，證明：復(fù)合映射gof一定是單（滿）射。:A→B,g:B→C，gof是單射，請(qǐng)問f和g是否一定是單射？請(qǐng)證明或舉出反例。，f:RR174。RR,f()=,請(qǐng)問f是否為單射？是否為滿射？分別證明或舉反例。∩C=198。,令f：P(B∪C)174。P(B)P(C)，對(duì)X206。P(B∪C),令f(X)=(B∩X,C∩X),證明：f是雙射。代數(shù)系統(tǒng)，Z8={0,1,2,3,4,5,6,7},+8是模8加法，求出的單位元、每個(gè)元素的逆元、所有的生成元和所有的子群。，零元，每個(gè)元素的逆元，每個(gè)元素的階，它是循環(huán)群?jiǎn)幔壳蟪鏊械淖尤?。，在R上定義運(yùn)算*為x*y=x+y+xy,問：是代數(shù)系統(tǒng)嗎？有單位元嗎？每個(gè)元素都有逆元嗎？ ***，是代數(shù)系統(tǒng)，對(duì)于R中元素*x,y，令xoy=2x+2y2。請(qǐng)問中是否存在單位元、零元、哪些元素有逆元？運(yùn)算o是否滿足交換律和結(jié)合律。分別說明理由。，R上的6運(yùn)算定義如下：對(duì)R中元素x,y，f1()=x+y；f2()=xy；f3()=xy；f4()=x/y；f5()=max{x,y}；f6()=|xy|。問：哪些滿足交換律、結(jié)合律、有單位元、有零元？說明理由。，證明：G是交換群當(dāng)且僅當(dāng)對(duì)任意G中222元素x,y,都有等式(xy)=xy成立。：如果群G中每個(gè)元素的逆元素都是它自已，則G是交換群。：階為素?cái)?shù)的群一定是循環(huán)群。，u206。G,定義運(yùn)算*：x*y=xouoy, 證明：是一個(gè)群。*：對(duì)任意整數(shù)x和y,x*y=x+y4,其中+，為普通加減法。證明：是一個(gè)群。：如果群G中至少有兩個(gè)元素，則群中沒有零元。，證明：{x|x是S的左陪集}是G的一個(gè)劃分,a206。G,n是a的階(周期)，證明：k是的一個(gè)子群。，K都是群G的子群，請(qǐng)問H∩K,H∪K,HK是否一定是G的子群？ ，K是G的兩個(gè)子群，a206。G, 試證：aH205。aK當(dāng)且僅當(dāng)H205。K。={1,3,4,5,9},*是模11的乘法(即x*y=xy mod 11)，請(qǐng)問(G,*)是否構(gòu)成群？，e是單位元，a206。G,a的階為k,證明：a=e當(dāng)且僅當(dāng) n是k的倍數(shù)。，證明：{x|x是S的左陪集}是G的一個(gè)劃分，證明：S={a206。G|x206。G(ax=xa)},則S是G的子群。，則G中必存在2階元素。：6個(gè)元素的群在同構(gòu)意義下只有兩個(gè)。++，R為正實(shí)數(shù)集，與是否同構(gòu)？ ，證明：G不可能表示成兩個(gè)真子群的并。？完全圖、完全二部圖的邊數(shù)。？。？哪些完全圖是E圖？ ？ 。：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。：如果G是歐拉圖，則其邊圖L(G)也是歐拉圖。：奇數(shù)個(gè)頂點(diǎn)的二部圖（兩步圖）不是哈密爾頓圖。，G有m條邊，n個(gè)頂點(diǎn)，證明：m163。3n6。并由此證明K5不是平面圖。：有6個(gè)頂點(diǎn)的簡(jiǎn)單無向圖G和它的補(bǔ)圖中至少有一個(gè)三角形。：在至少有兩個(gè)頂點(diǎn)的無向樹中，至少有2個(gè)一度頂點(diǎn)。，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？：簡(jiǎn)單無向圖G和它的補(bǔ)圖中至少有一個(gè)是連通圖。：無向圖中奇度點(diǎn)（度數(shù)為奇數(shù)的點(diǎn)）有偶數(shù)個(gè)。：n個(gè)頂點(diǎn)的無向連通圖至少有n1條邊。，V是G的頂點(diǎn)集，證明：對(duì)任意頂點(diǎn)集S，198。185。S204。V，都有ω（GS）≤|S|。其中ω（GS）表示GS的分圖數(shù)目。，1個(gè)頂點(diǎn)次數(shù)為2，其余頂點(diǎn)次數(shù)為1，問它有幾個(gè)次數(shù)為1的頂點(diǎn)？寫出求解過程。：每個(gè)簡(jiǎn)單平面圖都包含一個(gè)次至多為5的頂點(diǎn)。，m條邊和f個(gè)面，證明：nm+f=2?！堞?，證明：G是ρ+1可點(diǎn)著色的。，G有n個(gè)頂點(diǎn)，則G最少有幾條邊，最多有幾條邊？，則稱G是自補(bǔ)圖，求所有4個(gè)頂點(diǎn)自補(bǔ)圖。，G有m條邊，n個(gè)頂點(diǎn)，證明：m163。3n6。如果G中無三角形，則m163。2n4。數(shù)理邏輯，則要進(jìn)行英語或數(shù)理邏輯考試。沒有不犯錯(cuò)誤的人。整數(shù)都是有理數(shù)。有的有理數(shù)不是整數(shù)。不存在最大的整數(shù)。有且只有一個(gè)偶數(shù)是素?cái)?shù)。：P174。(┓Q174。R)、(┓Q174。R)174。(P171。R)：p174。(q174。r)，┓s∨p，q ├ s174。r p174。r，q174。s，p∨q ├ r∨s p∨q，p174。┓r，s174。t，┓s174。r，┓t ├ q p174。(┓(r∧s)174。┓q),p,┓s ├ ┓q ，他一定會(huì)學(xué)好數(shù)學(xué)。如果小王不是文科學(xué)生，他一定是理科學(xué)生。小王沒學(xué)好數(shù)學(xué)。所以小王是文科學(xué)生。，并且改變論域使該公式在新的解釋下取值相反。論域：D={2,3,6}, F(x):x≤3, G(x):x5, R(x,y):x+y第三篇：離散數(shù)學(xué)習(xí)題及答案離散數(shù)學(xué)考試試題（A卷及答案）一、（10分）某項(xiàng)工作需要派A、B、C和D 4個(gè)人中的2個(gè)人去完成，按下面3個(gè)條件，有幾種派法？如何派？(1)若A去，則C和D中要去1個(gè)人；(2)B和C不能都去；(3)若C去，則D留下。解設(shè)A：A去工作；B：B去工作；C：C去工作；D：D去工作。則根據(jù)題意應(yīng)有：A174。C197。D，216。(B∧C)，C174。216。D必須同時(shí)成立。因此(A174。C197。D)∧216。(B∧C)∧(C174。216。D)219。(216。A∨(C∧216。 D)∨(216。C∧D))∧(216。B∨216。C)∧(216。C∨216。D)219。(216。A∨(C∧216。 D)∨(216。C∧D))∧((216。B∧216。C)∨(216。B∧216。D)∨216。C∨(216。C∧216。D))219。(216。A∧216。B∧216。C)∨(216。A∧216。B∧216。D)∨(216。A∧216。C)∨(216。A∧216。C∧216。D)∨(C∧216。 D∧216。B∧216。C)∨(C∧216。 D∧216。B∧216。D)∨(C∧216。 D∧216。C)∨(C∧216。 D∧216。C∧216。D)∨(216。C∧D∧216。B∧216。C)∨(216。C∧D∧216。B∧216。D)∨(216。C∧D∧216。C)∨(216。C∧D∧216。C∧216。D)219。F∨F∨(216。A∧216。C)∨F∨F∨(C∧216。 D∧216。B)∨F∨F∨(216。C∧D∧216。B)∨F∨(216。C∧D)∨F 219。(216。A∧216。C)∨(216。B∧C∧216。 D)∨(216。C∧D∧216。B)∨(216。C∧D)219。(216。A∧216。C)∨(216。B∧C∧216。 D)∨(216。C∧D)219。T故有三種派法：B∧D，A∧C，A∧D。二、（15分）在謂詞邏輯中構(gòu)造下面推理的證明：某學(xué)術(shù)會(huì)議的每個(gè)成員都是專家并且是工人，有些成員是青年人，所以，有些成員是青年專家。解：論域：所有人的集合。S(x)：x是專家；W(x)：x是工人；Y(x)：x是青年人；則推理化形式為：x(S(x)∧W(x))，$xY(x)$x(S(x)∧Y(x))下面給出證明：(1)$xY(x)P(2)Y(c)T(1)，ES(3)x(S(x)∧W(x))P(4)S(c)∧W(c)T(3)，US(5)S(c)T(4)，I(6)S(c)∧Y(c)T(2)(5)，I(7)$x(S(x)∧Y(x))T(6)，EG三、（10分）設(shè)A、B和C是三