離散數(shù)學(xué)期末復(fù)習(xí)題

PAGE19-離散數(shù)學(xué)期末復(fù)習(xí)題一、選擇題1、永真式的否定是（2）(1)永真式(2)永假式(3)可滿足式(4)(1)--(3)均有可能2、設(shè)P：2×2=5，Q：雪是黑的，R：2×4=8，S：太陽從東方升起，則下列真命題為(1)(1)(2)(3)(4)。3、設(shè)P：我聽課，Q：我看小說，則命題R“我不能一邊聽課，一邊看小說”的符號化為=2\*GB2⑵=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷提示：4、下列表達式錯誤的有=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵=3\*GB2⑶=4\*GB2⑷5、下列表達式正確的有=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵=3\*GB2⑶=4\*GB2⑷6、下列聯(lián)接詞運算不可交換的是(3)=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷6、設(shè)D：全總個體域，F(xiàn)（x）：x是花，M(x)：x是人，H(x,y)：x喜歡y，則命題“有的人喜歡所有的花”的邏輯符號化為=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷7、設(shè)L(x)：x是演員，J(x)：x是老師，A(x,y)：x欽佩y，命題“所有演員都欽佩某些老師”的邏輯符號化為=2\*GB2⑵=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷8、謂詞公式中的x是=3\*GB2⑶=1\*GB2⑴自由變元=2\*GB2⑵約束變元=3\*GB2⑶既是自由變元又是約束變元=4\*GB2⑷既不是自由變元又不是約束變元9、下列表達式錯誤的有=1\*GB2⑴=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷10、下列推導(dǎo)錯在=3\*GB2⑶① P② US①③ ES②④ UG③=1\*GB2⑴②=2\*GB2⑵③=3\*GB2⑶④=4\*GB2⑷無11、下列推理步驟錯在=3\*GB2⑶① P② US①③ ES②④ UG③⑤ EG④=1\*GB2⑴①→②=2\*GB2⑵②→③=3\*GB2⑶③→④=4\*GB2⑷④→⑤12、設(shè)個體域為{a,b}，則去掉量詞后，可表示為=4\*GB2⑷=1\*GB2⑴=2\*GB2⑵(3)=4\*GB2⑷提示：原式二、填充題1、一個命題含有n個原子命題，則對其所有可能賦值有種。2、n個命題變元可產(chǎn)生個互不等價的極小項，其中，任意兩個不同極小項的合取式為矛盾式（永假式），而全體極小項的析取式為重言式（永真式），n個命題變元可構(gòu)造包括F的不同的主析取范式類別為。3、n個命題變元可產(chǎn)生個互不等價的極大項，其中，任意兩個不同極大項的析取式為重言式（永真式），而全體極小項的合取式為矛盾式（永假式），n個命題變元可構(gòu)造包括T的不同的主合取范式類別為。5、公式的對偶公式為。6、設(shè)P：它占據(jù)空間，Q：它有質(zhì)量，R：它不斷運動，S：它叫做物質(zhì)。命題“占據(jù)空間的，有質(zhì)量的而且不斷運動的叫做物質(zhì)”的邏輯符號可化為。7、P：你努力，Q：你失敗。“除非你努力，否則你將失敗”的翻譯為；“雖然你努力了，但還是失敗了”的翻譯為。8、令：x會叫，：x是狗，：x會咬人，則命題“會叫的狗未必會咬人”的符號化為。9、設(shè)P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，則命題“大象比老鼠重”的符號化為。10、令A(yù)（x）:x是自然數(shù)，B（x,y）：x小于y，則命題“存在最小的自然數(shù)”的符號化為。三、計算題1、用真值表方法判斷下列公式的類型，并求（3）的主析取范式與主合取范式（1）（PQ）（P∨Q）；（2）（PQ）∧Q；（3）（PQ）∧R；解（1）、（2）和（3）的真值表如表1、表2和表3所示：表1PQPQP∨Q（PQ）（P∨Q）00011011110111011111表2PQPQ（PQ）（PQ）∧Q00011011110100100000表3PQRPQR（PQ）∧R000001010011100101110111111100111010101010100010由上述真值表可知，（1）為永真式，（2）為永假式，（3）為可滿足式。（3）的主析取范式為：；其主合取范式為。2、給定解釋I：D={2，3}，L（x,y）為L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0,求謂詞合式公式的真值。解：。3、個體域為{1，2}，求xy（x+y=4）的真值。解：xy（x+y=4）x（（x+1=4）∨（x+2=4））（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+2=4））（0∨0）∧（0∨1）0∧10。四、證明題1、證明下列邏輯恒等式：（1）ＰＱ(ＰＱ)(ＱＰ)證明、用真值表法證明PQPQ（PQ）（QP）FFFTTFTTTTFFFFTT由定義可知，這兩個公式是等價的。（2）P(QP)P(PQ)證明、P(QP)P(QP)P(PQ)P(PQ)P(PQ)P(PQ)（3）證明：左右（4）求證：x(A(x)B(x))xA(x)xB(x)（5）求證：x(P(x)Q(x))∧xP(x)x(P(x)∧Q(x))證明：左x((P(x)Q(x)∧P(x))x((P(x)∨Q(x))∧P(x))x(P(x)∧Q(x))右（6）求證：xy(P(x)Q(y))xP(x)yQ(y)證明：xy(P(x)Q(y))xy(P(x)∨Q(y))x(P(x)∨yQ(y))xP(x)∨yQ(y)xP(x)∨yQ(y)xP(x)yQ(y)（7）求證：證明：左右2、用推理規(guī)則證明下列各結(jié)論是各前提的有效結(jié)論：（1）P→Q，QR，R，SP=>S證明：(1)RP(2)QRPQT（1），（2）(析取三段論)P→QPPT（3），（4）(拒取式)SPP(7)ST（5），（6）(析取三段論)（2）A→(B→C)，C→(DE)，F(xiàn)→(DE),A=>B→F證明：(1)AP(2)A→(B→C)P(3)B→CT（1），（2）(假言推理)(4)BP（附加前提）CT（3），（4）(假言推理)C→(DE)前提DET（5），（6）(假言推理)F→(DE)前提FT（7），（8）(拒取式)B→FCP（3）(P→Q)(R→S)，(Q→W)(S→X)，(WX)，P→R=>P證明：（1）PP（假設(shè)前提）（2）P→RP（3）RT（1），（2）(假言推理)（4）(P→Q)(R→S)P（5）P→QT（4）(化簡律)（6）R→ST（4）(化簡律)（7）QT（1），（5）(假言推理)（8）ST（3），（6）(假言推理)（9）(Q→W)(S→X)P（10）Q→WT（9）(化簡律)（11）S→XT（9）(化簡律)（12）WT（7），（10）(假言推理)（13）XT（8），（11）(假言推理)（14）WXT（12），（13）(合取引入)（15）(WX)P（16）(WX)(WX)T（14），（15）(合取引入)由（16）得出矛盾式，故P為原前提的有效結(jié)論（4）x(P(x)Q(y)∧R(x))，xP(x)Q(y)∧x(P(x)∧R(x))證明(1)xP(x)P(2)P(a)T(1)，ES(3)x(P(x)Q(y)∧R(x))P(4)P(a)Q(y)∧R(a)T(3)，US(5)Q(y)∧R(a)T(2)(4)(假言推理)(6)Q(y)T(5)(化簡律)(7)R(a)T(5)(化簡律)(8)P(a)∧R(a)T(2)(7)(合取引入)(9)x(P(x)∧R(x))T(8)，EG(10)Q(y)∧x(P(x)∧R(x))T(6)(9)(合取引入)（5）證明：①xP(x)P（ 附加前提）②P(e) T①ES③ P④ T③US⑤Q(e) T②④(假言推理)⑥ T⑤EG⑦ CP（6）證明：⑴ P⑵ P⑶ T⑴⑵(假言推理)⑷ T⑵ES⑸ P⑹ T⑸ES⑺ T⑶US⑻ T⑹（附加律）⑼ T⑺⑻(假言推理)⑽ T⑷⑼(合取引入)⑾ T⑽EG⑿ T⑾EG（7）證明：（1）P（假設(shè)前提）（2）T（1）（3）T（2）(化簡律)（4）T（3）ES（5）P（6）T（5）（7）T（6）US（8）T(4).(7)(假言推理)(9)T(2)(化簡律)(10)T(9)US(11)T(8)(10)(合取引入)由（11）得出矛盾式，故為原前提的有效結(jié)論五、將下列命題形式化，并證明結(jié)論的有效性：1、為慶祝九七香港回歸祖國，四支足球隊進行比賽，已知情況如下，問結(jié)論是否有效?前提:(1)若A隊得第一，則B隊或C隊獲亞軍;若C隊獲亞軍，則A隊不能獲冠軍;若D隊獲亞軍，則B隊不能獲亞軍;A隊獲第一;結(jié)論:(5)D隊不是亞軍。證明、設(shè)A：A隊得第一;B:B隊獲亞軍;C:C隊獲亞軍;D:D隊獲亞軍;則前提符號化為A（BC），CA，DB，A；結(jié)論符號化為D。本題即證明A（BC），CA，DB，AD。（1）AP（2）A（BC）P（3）BCT（1），（2）(假言推理)（4）CAP（5）CT（1），（4）(拒取式)（6）BT（3），（5）(析取三段論)（7）DBP（8）DT（6），（7）(拒取式)故該結(jié)論有效2、只要今天天氣不好，就一定有考生不能提前進入考場，當(dāng)且僅當(dāng)所有考生提前進入考場，考試才能準(zhǔn)時進行。所以，如果考試準(zhǔn)時進行，那么天氣就好。解設(shè)P：今天天氣好，Q：考試準(zhǔn)時進行，A(e)：e提前進入考場，個體域：考生的集合，則命題可符號化為：PxA(x)，xA(x)QQP。(1)PxA(x)P(2)PxA(x)T(1)(3)xA(x)PT(2)(4)xA(x)QP(5)(xA(x)Q)∧(QxA(x))T(4)(6)QxA(x)T(5)(化簡律)(7)QPT(6)(3)（假言三段論）3、所有有理數(shù)都是實數(shù)，某些有理數(shù)是整數(shù)。因此，某些實數(shù)是整數(shù)。解：設(shè)Q(x)：x是有理數(shù)，R(x)：x是實數(shù)，Z(x)：x是整數(shù)。命題形式化：。證明：（1）P(2)T(1)ES(3)T(2)(化簡律)(4)P(5)T(4)US(6)T(3)(5)(假言推理)(7)T(2)(化簡律)(8)T(6)(7)(合取引入)(9)T(8)EG集合、關(guān)系、函數(shù)的重要知識一、關(guān)系的集合運算法則設(shè)，則有1.，，，，2.，，3.4.，二、關(guān)系特性的判斷方法自反性非（反）自反性對稱性非（反）對稱性傳遞性定義若則若且則若且則集合運算關(guān)系矩陣主對角線元素全為1主對角線元素全為0對稱矩陣若，且，則若，則關(guān)系圖圖中各頂點都有環(huán)圖中各頂點都無環(huán)若兩頂點間有邊，必為雙向邊若兩頂點間有邊，必為單向邊若兩頂點通過中間點相聯(lián)，則兩頂點間必有直達邊三、關(guān)系特性在各種運算下的遺傳變異問題設(shè)，則有四、函數(shù)的性質(zhì)設(shè)函數(shù)，，若是單射，則也是單射；若是滿射，則也是滿射；若是雙射，則也是雙射；若是單射，則是單射；若是滿射，則是滿射；若是雙射，則是滿射，是單射集合、關(guān)系、函數(shù)的重要習(xí)題一、選擇題1、下列為真命題的是（B）A、B、C、D、2、下列結(jié)果錯誤的是（B）A、B、C、D、3、非空集合上的空關(guān)系不具備的性質(zhì)是（A）A、自反性B、反自反性C、對稱性；D、傳遞性4、設(shè)R為S={1，2，3}上的關(guān)系，其關(guān)系圖如下，則下列為真命題的是（C）A、R對稱，但不反對稱B、R反對稱，但不對稱C、R對稱，又反對稱D、R不對稱，也不反對稱5、設(shè)R為S={1，2，3，4}上的關(guān)系，其關(guān)系圖如下，則下列為假命題的是（C）A、R不自反，也不反自反B、R不對稱，也不反對稱C、R傳遞D、R不傳遞6、設(shè)R，S是集合A上的關(guān)系，則下列斷言正確的是（A）A、若自反，則自反B、若對稱，則對稱；C、若反自反，則反自反D、若反對稱，則反對稱7、設(shè)Z為整數(shù)集，下面哪個序偶不夠成偏序集（A）A、B、C、D、8、設(shè)A={，{1}，{1，3}，{1，2，3}}則A上包含關(guān)系“”的哈斯圖為（C）9、集合A={1，2，3，4}上的偏序關(guān)系圖為則它的哈斯圖為（A）10、下列關(guān)系中能構(gòu)成函數(shù)的是（B）A、；B、；C、；D、11、下列函數(shù)是雙射的為（A）A、f:ZE,f(x)=2xB、f:NNN,f(n)=<n,n+1>C、f:RZ,f(x)=1D、f:ZN,f(x)=|x|（注：Z—整數(shù)集，E—偶數(shù)集，N—自然數(shù)集，R—實數(shù)集）12、下面函數(shù)為單射而非滿射的是（B）A、B、；C、D、13、下列命題正確的有（C）A、若是雙射，則都是單射B、若是雙射，則都是滿射C、若是雙射，則是單射,是滿射D、若是雙射，則是滿射,是單射二、填充題1、設(shè)，，則{6，12}，{2，4，8，10}，{2，3，4，8，9，10}2、集合的冪集=3、，4、設(shè)，則5、設(shè)關(guān)系A(chǔ)={<1,2>,<2,4>,<3,3>}與B={<1,3>,<2,4>,<4,2>},則={<1,4>,<2,2>}，{<4,2>}6、設(shè)集合A={1，2，3，4，5}上偏序關(guān)系的Hass圖為則集合A上的最大元為1，最小元為無，極大元為1，極小元為4,5，lub為1，glb為無；其子集B={2，3，4}上的最大元為無，最小元為4，；極大元為2,3，極小元為4，lub為1，glb為47、偏序集的哈斯圖為則={<a,b>,<a,d>,<a,e>,<a,c>,<a,f>,<a,g>,<b,d>,<b,e>,<c,f>,<c,g>}設(shè)A={1，2，3，4}，S={{1}，{2，3}，{4}}，為A的一個分劃，則由S導(dǎo)出的等價關(guān)系R={<1,1>,<2,2>,<2,3>,<3,2>,<3,3><4,4>}9、設(shè)|X|=m，|Y|=n，則從X到Y(jié)有種不同的關(guān)系，有種不同的函數(shù)10、在一個有n個元素的集合上，可以有種不同的關(guān)系，有種不同的函數(shù)，有種不同的雙射11、設(shè)f，g是自然數(shù)集N上的函數(shù)，則，三、問答、計算、證明題1、設(shè)R是X＝{1，2，3，4}上的二元關(guān)系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}(1)畫出R的關(guān)系圖．(2)寫出R的關(guān)系矩陣．(3)說明R是否是自反、反自反、對稱、傳遞的？解(1)R的關(guān)系圖如圖所示：(2)R的關(guān)系矩陣為：(3)對于R的關(guān)系矩陣，由于對角線上不全為1，R不是自反的；由于對角線上存在非0元，R不是反自反的；由于矩陣不對稱，R不是對稱的；從關(guān)系圖看出，若兩頂點通過中間點相聯(lián)，則兩頂點間必有直達邊，所以R是傳遞的．2、設(shè)X為集合，A＝－{}－{X}，且A≠，若|X|＝n，問(1)偏序集<A，>是否有最大元？(2)偏序集<A，>是否有最小元？(3)偏序集<A，>中極大元和極小元的一般形式是什么？并說明理由。解：考察的哈斯圖，最底層的頂點是空集，記作第0層，由底向上，第一層是單元集，第二層是二元集，…，由|X|＝n，則第n－1層是X的n－1元子集，第n層是X．偏序集<A，>與偏序集<，>相比，恰好缺少第0層和第n層．A≠，則偏序集<A，>不存在最大元和最小元因此<A，>的極小元就是X的所有單元集，即{x}，x∈X；而極大元恰好是比X少一個元素，即X－{x}，x∈X．3、是集合上的關(guān)系，寫出關(guān)系矩陣，畫出關(guān)系圖，問R是上的等價關(guān)系嗎？解：R的關(guān)系圖為R是自反、對稱的，但不傳遞，故不是等價關(guān)系．4、求S={1，2，3，4，5}上的等價關(guān)系R，使其誘導(dǎo)劃分{{1，2}，{3}，{4，5}}，畫出關(guān)系圖．解：R1={1,2}×{1,2}={<1,1>,<1,2>,<2,1>,<2,2>}R2={3}×{3}={<3,3>}R3={4,5}×{4,5}={<4,4>,<4,5>,<5,4>,<5,5>}R=R1R2R3={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5>}．5、設(shè)，，從A到B的關(guān)系，試給出R的關(guān)系圖和關(guān)系矩陣，并說明此關(guān)系及其逆關(guān)系是否為函數(shù)？為什么？A234B2A234B2471012R的關(guān)系矩陣為關(guān)系不是A到B的函數(shù)，因為元素2，4的象不唯一逆關(guān)系也不是B到A的函數(shù)因為元素7的象不存在．6、設(shè)，R是A的等價關(guān)系且由R誘導(dǎo)的A的劃分塊數(shù)為4，則不同的R有多少種？解：我們知道一個集合上的等價關(guān)系數(shù)目與該集合的劃分?jǐn)?shù)目是一致的，因而，該題只需求出將8個元素的集合分成4份的劃分種數(shù)即可。如果4份中元素個數(shù)分別為5，1，1，1，則共有種，如果4份中元素個數(shù)分別為4，2，1，1，則共有種，如果4份中元素個數(shù)分別為3，3，1，1，則共有種，如果4份中元素個數(shù)分別為3，2，2，1，則共有種，如果4份中元素個數(shù)分別為2，2，2，2，則共有種，因此，A上秩為4的等價關(guān)系共有++++．7、設(shè)，在上定義關(guān)系，證明：是上的等價關(guān)系，并求出．證明：1）即R自反．2）從而，即R對稱．3）則，從而即R傳遞．綜上得出，R是等價關(guān)系．，．8、設(shè)A={1，2，3，4}，在上規(guī)定二元關(guān)系，證明：R是上的等價關(guān)系，并寫出，商集．證明：⑴，由于，所以，即R自反的．⑵，若，則，，R是對稱的．⑶，若：，即：所以R是傳遞的．由⑴⑵⑶知，R是等價關(guān)系．，．9、若R和S都是非空集A上的等價關(guān)系，則RS是A上的等價關(guān)系．證明：a∈A，因為R和S都是A上的等價關(guān)系，所以xRx且xSx。故xRSx。從而RS是自反的．a(chǎn),b∈A，aRSb，即aRb且aSb。因為R和S都是A上的等價關(guān)系，所以bRa且bSa。故bRSa。從而RS是對稱的．a(chǎn),b,c∈A，aRSb且bRSc，即aRb，aSb,bRc且bSc。因為R和S都是A上的等價關(guān)系，所以aRc且aSc。故aRSc。從而RS是傳遞的．故RS是A上的等價關(guān)系．10、設(shè)R是A上一個二元關(guān)系，，試證明：若R是A上一個等價關(guān)系，則S也是A上的一個等價關(guān)系．證明：（1），由R自反，則，，即自反．（2）則，且由R對稱，知，于是，即對稱．（3），則，且由R傳遞，知，于是，即S傳遞的．由（1）、（2）、（3）得，S是等價關(guān)系．11、設(shè)A={1，2}，A上所有函數(shù)的集合記為AA,是函數(shù)的復(fù)合運算，試給出AA上運算的運算表，并指出AA中是否有幺元，哪些元素有逆元？解：因為|A|=2，所以A上共有22=4個不同函數(shù)。令，其中：為AA中的幺元，和有逆元．設(shè)函數(shù)f：R×RR×R，f定義為：f(<x，y>)＝<x＋y，x－y>。(1)證明f是雙射；(2)求逆函數(shù)f－1；(3)求fof．證明：(1)x，y，x1，y1∈R，若f(<x，y>)＝f(<x1，y1>)，則<x＋y，x－y>＝<x1＋y1，x1－y1>，x＋y＝x1＋y1，x－y＝x1－y1，從而x＝x1，y＝y(tǒng)1，故f是單射；<u，w>∈R×R，令x＝，y＝，則<x，y>∈R×R且f(<x，y>)＝<＋，－>＝<u，w>，所以f是滿射，故為雙射(2)f－1(<u，w>)＝<，>。(3)fof(<x，y>)＝f(<x＋y，x－y>)＝<x＋y＋x－y，x＋y－(x－y)>＝<2x，2y>．12、設(shè)f是A到A的滿射，且，證明．證明：因為f是滿射，所以，存在使得，又因為f是函數(shù)，所以即由，知，則，由a的任意性知．代數(shù)系統(tǒng)一、選擇題：1、下列正整數(shù)集的子集在普通加法運算下封閉的是（D）A、{}B、{與互質(zhì)}C、{是的因子}D、{是的倍數(shù)}2、設(shè)S={1，2，…，10}，則下面定義的運算*關(guān)于S非封閉的有（D）A、x*y=max(x,y)B、x*y=min(x,y)C、x*y=取其最大公約數(shù)D、x*y=取其最小公倍數(shù)3、設(shè)集合的冪集為，為集合的交、并、差、笛卡爾乘積運算，則下列系統(tǒng)中是代數(shù)系統(tǒng)的為（D）A、B、C、D、4、在自然數(shù)集上定義的下列四種運算，其中滿足結(jié)合律的是（C）A、B、C、D、5、設(shè)為正整數(shù)集，*表示求兩數(shù)的最小公倍數(shù)，對代數(shù)系統(tǒng)，有（A）A、是么元，無零元B、是零元，無么元C、無零元，無么元D、無等冪元6、設(shè)非空有限集的冪集為，對代數(shù)系統(tǒng)，有（B）A、是么元，是零元B、是零元，是么元C、唯一等冪元D、無等冪元7、在有理數(shù)集Q上定義的二元運算*：，則Q中元素滿足（C）A、都有逆元B、只有唯一逆元C、時，有逆元D、都無逆元8、設(shè)R是實數(shù)集合，“”為普通乘法，則代數(shù)系統(tǒng)<R，×>一定不是（D）A、半群B、獨異點C、可交換的獨異點D、循環(huán)獨異點9、設(shè)S={0，1}，*為普通乘法，則<S,*>（B）A、是半群，但非獨異點B、是獨異點，但非群C、是群，但非阿貝爾群D、是阿貝爾群10、任意具有多個等冪元的半群，它（A）A、不能構(gòu)成群B、不一定能構(gòu)成群C、能構(gòu)成群D、能構(gòu)成阿貝爾群二、填充題：1、下表中的運算均定義在實數(shù)集上，請在相應(yīng)的空格中打“√”或填上具體實數(shù)（不滿足或無該項者不填）×結(jié)合律√×√交換律√×√么元（含左、右么元）00（右幺元）1零元（含左、右零元）××02、設(shè)A={2,4,6}，A上*為：a*b=max{a,b}，則在獨異點<A,*>中，么元是(2)，零元為(6)。3、設(shè)A={3,6,9}，A上*為：a*b=min{a,b}，則在獨異點<A,*>中，么元是(9)，零元為(3)。4、代數(shù)系統(tǒng)<A,*>中，|A|>1，若分別為<A,*>的么元和零元，則的關(guān)系為。*abcaabcbbaccccc5、設(shè)<{a,b,c},*>為代數(shù)系統(tǒng)，*運算如下：則它的么元為a；零元為c；a、b、c的逆元分別為a、b、無。6、設(shè)〈G,*〉是一個群，則(1)若a,b,x∈G，ax=b，則x=(ab)；(2)若a,b,x∈G，ax=ab，則x=(b)。7、群<G,*>的等冪元是(么元)，有(1)個，零元有(0)個。8、設(shè)是12階群的生成元，則是(6)階元素，是(4)階元素。9、設(shè)是10階群的生成元，則是(5)階元素，是(10)階元素。10、在一個群〈G,*〉中，若G中的元素的階是k，則的階是(k)。三、簡答題：1、設(shè)A={1，2}，A上所有函數(shù)的集合記為AA,是函數(shù)的復(fù)合運算，試給出AA上運算的運算表，并指出AA中是否有么元，哪些元素有逆元？答：因為|A|=2，所以A上共有22=4個不同函數(shù)。令，其中：為AA中的么元，和有逆元。2、已知定義在集合上的運算*如下表：*abcdaabcdbbadcccdbaddcab試問：1）是否為代數(shù)系統(tǒng)？2）是否為子群？3）是否為群？4）是否有單位元？5）是否滿足交換律？題號12345答案√√√√√3、設(shè)I是整數(shù)集合，Z3是由模3的同余類組成的同余類集，在Z3上定義+3如下：，試給出+3的運算表，并指出<Z+,+3>是否構(gòu)成群？+3[0][1][2][0][0][1][2][1][1][2][0][2][2][0][1]答：<Z+,+3>構(gòu)成群。四、計算題：1、設(shè)S=QQ，Q為有理數(shù)集合，*為S上的二元運算：對任意(a,b)，(c,d)S,有(a,b)*(c,d)=(ac,ad+b),求出S關(guān)于二元運算*的么元，以及當(dāng)a0時，(a,b)關(guān)于*的逆元。解：設(shè)S關(guān)于*的么元為(a,b)。根據(jù)*和么元的定義，對(x,y)S,有(a,b)*(x,y)=(ax,ay+b)=(x,y),(x,y)*(a,b)=(ax,xb+y)=(x,y)。即ax=x,ay+b=y,xb+y=y對x,yQ都成立。解得a=1,b=0，則S關(guān)于*的么元為(1,0)。當(dāng)a0時，設(shè)(a,b)關(guān)于*的逆元為(c,d)。根據(jù)逆元的定義，有(a,b)*(c,d)=(ac,ad+b)=(1,0)，(c,d)*(a,b)=(ac,cb+d)=(1,0)即ac=1,ad+b=0,cb+d=0。解得c=1/a,d=-b/a。所以(a,b)關(guān)于*的逆元為(1/a,-b/a)。2、試求<N6,+6>中每個元素的階。解：0是<N6,+6>中關(guān)于+6的么元。則|0|=1；|1|=|5|=6，|2|=|4|=3，|3|=2。五、證明題：設(shè)<R,*>是一個代數(shù)系統(tǒng)，*是R上二元運算，，則0是么元且<R,*>是獨異點。證明：（1）即，0是么元（2）由于+，·在R封閉，則*在R上封閉。（3）因此，〈R，*〉是獨異點。2、I上的二元運算*定義為：a,bI，a*b=a+b-2。試證：<I,*>為群。證明：（1）a,b,cI，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4,a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c=a*(b*c)，從而*滿足結(jié)合律。（2）記e=2。對aI，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I關(guān)于運算*的單位元。（3）對aI，因為a*（4-a）=a+4-a-2=2=e=4-a+a-2=(4-a)*a。故4-a是a關(guān)于運算*的逆元。綜上所述，<I,*>為群。3、設(shè)*是集合A上可結(jié)合的二元運算，且a,bA,若a*b=b*a，則a=b。試證明：（1）aA,a*a=a，即a是等冪元；（2）a,bA,a*b*a=a。證明：（1）aA,記b=a*a。因為*是可結(jié)合的，故有b*a=(a*a)*a=a*(a*a)=a*b。由已知條件可得a=a*a。（2）a,bA,因為由（1），a*(a*b*a)=(a*a)*(b*a)=a*(b*a),(a*b*a)*a=(a*b)*(a*a)=(a*b)*a=a*(b*a)。故a*(a*b*a)=(a*b*a)*a，從而a*b*a=a。4、設(shè)半群<S,·>中消去律成立，則<S,·>是可交換半群當(dāng)且僅當(dāng)a,bS，（a·b）2=a2·b2。證明：a,bS，（a·b）2=(a·b)·(a·b)=((a·b)·a)·b=(a·(b·a))·b=(a·(a·b))·b=((a·a)·b)·b=(a·a)·(b·b)=a2·b2; a,bS，因為（a·b）2=a2·b2，所以(a·b)·(a·b)=(a·a)·(b·b)。故a·((b·a)·b)=a·(a·(b·b))。由于·滿足消去律，所以(b·a)·b=a·(b·b)，即(b·a)·b=(a·b)·b。從而a·b=b·a。故·滿足交換律。5、若<S,>是可交換獨異點，T為S中所有等冪元的集合，則<T,>是<S,>的子獨異點。證明： ee=e，eT，即T是S的非空子集。 a,bT,<S，>是可交換獨異點,(ab)(ab)=((ab)a)b=(a(ba))b=（a(ab)）b=((aa)b)b=(aa)(bb)=ab,即abT。故<T,>是<S,>的子獨異點。有么元且滿足消去律的有限半群一定是群。證明設(shè)<G，*>是一個有么元且滿足消去律的有限半群，要證<G，*>是群，只需證明G的任一元素a可逆。，則，對a，a2，…，ak，…，因G只有有限個元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是么元。由消去律得am＝e。于是，當(dāng)m＝1時，a＝e，而e是可逆的；當(dāng)m＞1時，a*am-1＝am-1*a＝e。從而a是可逆的，其逆元是am-1。總之，a是可逆的。6、對獨異點<A,*>，若A中每個元素都有右逆元，則<A,*>必為群。證明：設(shè)為<A,*>的么元，，記b是a的右逆元，c是b的右逆元，則，則b是a的左逆元。故，a有唯一逆元b，于是，<A,*>必為群。7、設(shè)群<G,＊>除單位元外每個元素的階均為2，則<G,＊>是交換群。證明：對任一aG，由已知可得a*a=e，即a-1=a。對任一a,bG，因a*b=(a*b)-1=b-1*a-1=b*a，所以*滿足交換律。從而＜G,*＞是交換群。8、證明：（1）有限群中階大于2的元素的個數(shù)一定是偶數(shù)。（2）偶數(shù)階群中階為2的元素的個數(shù)一定是奇數(shù)。證明：（1）設(shè)<G,·>是有限群，則aG，有|a|=|a-1|。且當(dāng)a階大于2時，a-1。故階數(shù)大于2的元素成對出現(xiàn)，從而其個數(shù)必為偶數(shù)。證明：（2）設(shè)<G,·>是偶數(shù)階群，則由于群的元素中階為1的只有一個單位元，階大于2的元素是偶數(shù)個，剩下元素中都是階為2的元素。故偶數(shù)階群中階為2的元素一定是奇數(shù)個。9、設(shè)<G，*>是由g生成的循環(huán)群，則若G為無限循環(huán)群，則G只有兩個生成元g和g－1。證明：因為g是群<G，*>的生成元，所以對任意的a∈G，存在i∈Z使得a＝gi。又a＝，所以g－1也是群<G，*>的生成元。再證G只有g(shù)和g－1這兩個生成元。假設(shè)h也是G的生成元，對G的元素g，存在整數(shù)s，使得g＝hs。對于h來說，由g是G的生成元，存在整數(shù)t，使得h＝gt。于是，g＝hs＝gst。由G中的消去律得＝e。因為G是無限群，必有st－1＝0。從而有s＝t＝1或s＝t＝－1，即h＝g或h＝g－1。10、<G，*>是個群，u∈G，定義G中的運算“”為ab=a*u-1*b，對任意a，b∈G，求證：<G，>也是個群。證明：1）a，b∈G，ab=a*u-1*b∈G，運算是封閉的。2）a，b，c∈G，（ab）c=（a*u-1*b）*u-1*c=a*u-1*（b*u-1*c）=a（bc），運算是可結(jié)合的。3）a∈G，設(shè)E為的單位元，則aE=a*u-1*E=a，得E=u，存在單位元u。4）a∈G，ax=a*u-1*x=E，x=u*a-1*u，則xa=u*a-1*u*u-1*a=u=E，各元素都有逆元。所以<G，>也是個群。11、設(shè)<G,·>是群，作f:GG,aa-1。證明：f是G的自同構(gòu)G是交換群。證明： 設(shè)f是G的自同構(gòu)。對a，bG，a·b=(b-1·a-1)-1=(f(b)·f(a))-1=(f(b·a))-1=((b·a)-1)-1=b·a。故運算·滿足交換律，即G是可交換群。因為當(dāng)ab時，a-1b-1，即f(a)f(b)，故f是G到G中的一個單射。又對aG，有f(a-1)=(a-1)-1=a。故f是G到G上的滿射。從而f是G到G上的雙射。對a，bG，因為G是可交換群，則f(a·b)=(a·b)-1=(b·a)-1=a-1·b-1=f(a)·f(b)。故f是G的自同構(gòu)。圖論部分一、選擇題：1．歐拉回路是（B）A.路徑B.簡單回路C.既是基本回路也是簡單回路D.既非基本回路也非簡單回路2．哈密爾頓回路是（C）A.路徑B.簡單回路C.既是基本回路也是簡單回路D.既非基本回路也非簡單回路3．設(shè)G是簡單有向圖，可達矩陣P(G)刻劃下列關(guān)系中的是（C）A、點與邊B、邊與點C、點與點D、邊與邊4．下列哪一種圖不一定是樹（C）。A.無簡單回路的連通圖B.有n個頂點n-1條邊的連通圖C.每對頂