東北農業大學網路教育學院
離散數學複習題
複習題一
一、證明
1、對任意兩個集合，證明
2、構造下面命題推理的證明
如果今天是星期三，那麼我有一次英語或數學測驗；如果數學老師有事，那麼沒有數學測驗；今天是星期三且數學老師有事，所以我有一次英語測驗。
二 、計算
1、(1)畫乙個有一條尤拉迴路和一條漢密頓迴路的圖。
(2)畫乙個有一條尤拉迴路但沒有漢密頓迴路的圖
(3)畫乙個沒有尤拉迴路但有一條漢密頓迴路的圖
2、設，求公式：
的真值。
3、一棵樹有個結點度數為2 ，個結點度數為3，… ，個結點度數為k ，問它有幾個度數為1的結點。
4、設集合上的關係，求出它的自反閉包，對稱閉包和傳遞閉包。
三、設上的整除關係，
是否為上的偏序關係？若是，
則：1、畫出的哈斯圖；
2、求。
四、用推導法求公式的主析取正規化和主合取正規化。
五、設實數集上的關係，
證明：是上的等價關係。
六、設分別是實數集和正實數集，＋和×分別是普通加法和乘法，定義函式為，證明的同構對映。
七、設是實數集合，，在上定義二元運算為：，試證明是乙個群。是否阿貝爾群？
複習題二
一、設上的整除關係
完成下列各小題。
1、 證明是上的偏序關係。
2、 畫出偏序集的哈斯圖。
3、 在上定義兩個二元運算和：對任意，，。請填空（在橫線上填是或不是）：
代數系統格。 代數系統有界格。
代數系統有補格。 代數系統分配格。
二、求布林函式的析取正規化和合取正規化
設是布林代數上的乙個布林表示式。試寫出的析取正規化和合取正規化（用推導法或列函式表的方法均可）。
三、畫出滿足下列要求的圖
有一條尤拉迴路和一條漢密爾頓迴路。
有一條尤拉迴路但沒有漢密爾頓迴路。
沒有尤拉迴路但有漢密爾頓迴路。
既沒有尤拉迴路也沒有漢密爾頓迴路。
四、證明在完全二叉樹中，邊的總數等於2(n-1)，這裡n是葉子數。
五、計算
求帶權2、3、5、7、11、13的最優二叉樹。
六、證明
在乙個連通平面圖中，若它有n個結點，m條邊，且每個面由k條邊圍成。
試證七、證明
設是有限字母表，給定代數系統，其中是串的連線運算。對於任一串，建立到的對映，。證明是到的乙個滿同態，且當時，是同構對映。
八、應用
給定有限狀態機，它的狀態圖如附圖所示。
1、 求狀態的011010的後繼以及可接受狀態序列。
2、 求對於激勵010110的響應。
3、構造一台與相似的轉換賦值機，畫出的狀態圖。
九、證明
考察乙個（8，4）碼c，它的校驗位a5，a6，a7，a8滿足下列方程
a5=a1+ a2+ a4
a6=a1+ a3+ a4
a7=a1+ a2+ a3
a8=a2+ a3+ a4
其中a1，a2，a3，a4為資訊位。
求出這個碼的一致校驗矩陣。證明。
複習題三
一、設集合
完成下列各小題。
1求的冪集。
2證明是偏序集。
3畫出偏序集的哈斯圖。
4在上定義兩個二元運算和：對任意，，。請填空（在橫線上填是或不是並回答為什麼）：
代數系統格，因為
代數系統有界格，因為
代數系統有補格，因為
代數系統分配格，因為
代數系統布林代數，因為
二、計算
設是布林代數上的乙個布林表示式。試寫出的析取正規化和合取正規化（用列函式表的方法）。
三、回答問題
完全圖是否是尤拉圖？是否是哈密爾頓圖？為什麼？
四、畫圖
對於下圖，利用克魯斯克爾演算法求一棵最小生成樹。
五、計算
一棵樹有兩個結點度數為2 ，1個結點度數為3，3個結點度數為4 ，其餘結點度數為1。問該樹有幾個度數為1的結點。
六、證明
是無向簡單圖，其中，證明：。
證明因為是簡單圖，所以圖中沒有環和平行邊，任意兩結點間最多有一條邊，故。
七、證明
已知求證
八、設計
設計一台有限狀態機，它的輸出是已經輸入符號數的模3數（即設計模3計數器）。
九、計算
給定碼c=，求碼c中任兩個碼字的海明距和。
複習題四
一、填空
1、設a和b為有限集，|a|=m，|b|=n，則有個從a到b的關係，有個從a到b的函式，其中當mn時有個入射，當m=n時，有個雙射。
2、集合 （是/不是）可數的。
二、計算
1、用推導法求下列公式的主合取正規化和主析取正規化：
2設上二元關係，求其自反閉包、對稱閉包、傳遞閉包。
三、證明
1、設是三個集合，證明：
2證明等價式：
四、將下列命題推理符號化並給出形式證明：
已知張三或李四的彩票中獎了；如果張三的彩票中獎了，那麼你是知道的；如果李四的彩票中獎了，那麼王五的彩票也中獎了；現在你不知道張三的彩票中獎。所以李四和王五的彩票都中獎了。
五、設複數集合，定義：當且僅當，證明：為等價關係。
六、證明：若。
七、設集合，是普通乘法，證明：是乙個群。
八、設實數集合r，+和x是普通加法和乘法，定義對映，，證明的單一同態。
複習題五
一、填空
1、實數集合r （是/不是）可數的。
2、設a和b為有限集，|a|=m，|b|=n，則有個從a到b的關係，有個從a到b的函式，其中當mn時有個入射，當m=n時，有個雙射。
二、計算
1、用推導法求下列公式的主合取正規化和主析取正規化：
2設上二元關係，求其自反閉包、對稱閉包、傳遞閉包。
三、證明
1、設是三個集合，證明：
2證明等價式：
四、將下列命題推理符號化並給出形式證明：
已知今天下雨或颳風；如果今天下雨，那麼我在家看書；如果今天颳風，那麼我去放風箏；今天我沒有在家看書。所以今天颳風並且我去放風箏了。
五、設正整數集合上的二元關係，證明：為等價關係。
六、證明：若。
七、設集合，是普通乘法，證明：是乙個群。
八、設正實數集合r+和實數集合r，+和x是普通加法和乘法，定義對映，，證明的同構。
複習題六
一、 求公式q∧(p∨┐q)的析取正規化、合取正規化及主析取正規化、主合取正規化。
二、用推理規則證明：
前提 (x)(f(x)∧s(x))→(y)(m(y) →w(y))，(y)(m(y)∧┐w(y))
結論 (x)(f(x)→┐s(x))
三、計算題
1.證明邏輯等價式a→(a→b)a→b成立。
2.對任意集合a，b，c，證明：（a - b） b = a b
3.設二元關係r=,b>,, }求：
(1) dom r
(2) ran r
(3) rοr
4.求集合a=的勢。
5. 在20名青年中有10名是公司職員，12名是學生，其中5名既是職員又是學生，問有幾名既不是職員，又不是學生。
四、假設給定了正整數的序偶集合a，在a上定義二元關係r如下：<,>r,當且僅當xv=yu，證明r為等價關係。
五、給出偏序集上偏序關係r的關係圖（如下圖所示）。
（1）求偏序集的哈斯圖。
（2）指出a的最大、最小元（如果有的話），極大、極小元。
六、設為群。若在g上定義二元運算о,使得對任何元素x，yg，有
xоy = yx。
證明也是群
七、設為群,a為g中給定元素。定義函式f：g→g，使得對每一xg有f(x)=axa-1
證明：f是到的自同構。
複習題七
一、證明
1、對任意兩個集合，證明
2、構造下面命題推理的證明
如果我學習，那麼我數學不會不及格；如果我不熱衷於玩遊戲機，那麼我將學習；但我數學不及格，因此我熱衷與玩遊戲機。
二 、計算
1、 畫乙個有一條尤拉迴路和一條漢密頓迴路的圖。
2、設，求公式：
的真值。
3一棵樹有個結點度數為2 ，個結點度數為3，… ，個結點度數為k ，問它有幾個度數為1的結點。
4設集合上的關係，求出它的自反閉包，對稱閉包和傳遞閉包。
三、設上的整除關係，是否為上的偏序關係？若是，則：
1、畫出的哈斯圖；2、求的極大值和的極小值。
四、用推導法求公式的主析取正規化和主合取正規化。
五、設自然數集上的關係定義為：，
證明：是上的等價關係。
六、設分別是實數集和正實數集，＋和×分別是普通加法和乘法，定義函式為，證明的同構對映。
七、設是整數集合，＋是普通加法，試證明是乙個群。是否迴圈群？
複習題八
一、 求公式(┐p∨┐q)→(p┐q)的析取正規化、合取正規化及主析取正規化、主合取正規化。
二、用推理規則證明：
前提 (x)p(x)→(x)((p(x)∨q(x))→r(x))，(x)p(x)，(x)q(x)
結論 (x)(y)(r(x)∧r(y))
三、計算題
1.證明邏輯等價式ab (a∧b)∨(┐a∧┐b)成立。
2.設ab，求證a∩cb∩c。
3.設集合a=，a上的關係r=，求r的自反閉包、對稱閉包。
4.求下列集合的基數。
（1）t=
（2）b=
（3）c=，a=
5. 求從1到500的整數中，能被3或5除盡的數的個數。
四、設r，s為a上的兩個等價關係，且r s。定義a/r上的關係r/s：
<[x],[y]>r/s當且僅當s
證明：r/s為a/r上的等價關係。
五、設上的整除關係
，是否為上的偏序關係？若是，
則：1、畫出的哈斯圖；
2、 求。
六、設為一群。證明：
（1）若對任意ag有a2 =e，e為么元，則g為阿貝爾群。
（2）若對任意a，bg有(ab)2 =a2b2 ，則g為阿貝爾群。
七、設n4 =｛0，1，2, 3｝，f：n4→n4定義如下：
令f = ，其中f0為n4上恒等函式。給定一代數結構，且（這裡ο為函式合成運算，+4為模4加運算）。
離散數學作業
離散數學集合論部分形成性考核書面作業 本課程形成性考核書面作業共3次，內容主要分別是集合論部分 圖論部分 數理邏輯部分的綜合練習，基本上是按照考試的題型 除單項選擇題外 安排練習題目，目的是通過綜合性書面作業，使同學自己檢驗學習成果，找出掌握的薄弱知識點，重點複習，爭取盡快掌握 本次形考書面作業是第...
離散數學證明題
證明題1.用等值演演算法證明下列等值式 1 pq p q p q 2 p q p q p q p q 證明 1 pq p q q p p q q p p q q p p q p p q q p q p q p q 2 p q p q p p p q q p q q p q p q 2 構造下列推理的...
flash網上作業題彙總
東北農業大學網路教育學院 flash應用網上作業題 第一章 flash cs5入門基礎 一 填空題 1 flashcs5預設的是每秒 24 幀。2 在flash cs5中提供多種工作區面板集的布局方式，選擇 視窗 工作區 命令，在子選單中可以選擇 動畫 傳統 或 除錯 等命令，可以在多種布局模式中切...