一、 填空題
1． （（（p→q）∨￢q）→rq合式公式。
2． 「我正在說謊」 命題。
3． 公式（r∧（r→q））→q 重言式。
4．（（（￢p∨r）→q）∧r）∨q合式公式。
5．公式（x）（p（x）→q(y)）∧r(x)中的自由未知量為
6.「如果雪是黑的，太陽從西邊出」是命題。
7．a，b為集合，則a-b b-a。
8．a，b為集合，則a∩（b∪a） a。
9．設y=,,則p(y) 中有個元素。
10．a，b為集合，則a∩b b∪a。
11．a，b為集合，則b∪（a-b） b。
12．設x=,,則x 上不同的關係有種。
13．a，b為集合，ba , 則(b-a)∪b b。
14．r，s都是a上的自反，傳遞，對稱關係，則s（r∩s
15. r，s都是a上的自反，傳遞，對稱關係，則t（r∩s
16．a是乙個集合，則p（a）上集合的包含關係是關係。
17．a=上的小於關係函式。
18．a，b，c為集合，則（a－b）∩c a∩c－b∩c。
19．乙個二元運算函式。
20．設x=,y=,從x 到y上有個不同的函式。
21．函式二元關係。
22．i是乙個整數集，*是加法運算，代數系統中的么元是 。
23．a是整數集，*是乘法運算，代數系統中的么元是 。
24．獨異點半群。
25．群中的元素逆元。
26． 群一定是交換群。
27．n個結點的樹中有邊數為 。
28．5個結點的無向完全圖平面圖。
29．根樹中有乙個結點的入度為 。
30．有n個結點的無向完全圖的邊數結點數。
31．尤拉圖漢密爾頓圖。
32．根樹中有個結點的入度為0。
33. 無迴路的連通圖是 。
34．尤拉圖連通圖。
35．圖中所有結點的度數之和為
二．判斷題
1．a，b，c為命題公式，如果a ∨c b∨c，則有ab。 ( )
2．p→（q→r）q→（p→r）。（ ）
3．所有重言式都是等價的。（ ）
4．任一命題公式既可化為析取正規化，又可化為合取正規化。（ ）
5．命題「有理數都是實數」謂詞符號化時不用量詞。（ ）
6．空集是每個集合的子集。 （ ）
7. φ∈p（a），其中p（a）為集合a的冪集。（ ）
8．空集是p（a）中的乙個元素，其中a為任一集合，p（a）為a的冪。（ ）
9．實數集上的整除關係是反對稱關係。 （ ）
10．序偶做成的集合一定是關係。（ ）
11．笛卡爾積運算滿**換律。（ ）
12．集合的包含關係是傳遞關係。（ ）
13. 集合a上的相容關係具有傳遞性。 ( )
14. 等價關係具有傳遞性。（ ）
15. 偏序集的任一非空子集一定有極大元。（ ）
16．函式不一定是關係。（ ）
17．雙射函式一定是入射函式。 ( )
18．任意乙個函式f的逆函式都存在。（ ）
19. 恒等函式一定是雙射函式。（ ）
20．實數集上的除法運算一定是封閉的。 （ ）
21．自然數集上的加法運算一定是封閉的。（ ）
22．有零元的代數系統一定不是群。（ ）
23．r為實數集，*為r上的普通乘法運算，代數系統是群。 （ ）
24．群中不一定有零元。（ ）
25．s為集合，代數系統〈p（s），∩〉是群。（ ）
26．a為正數集，·是普通乘法運算，代數系統是群。（ ）
27．代數系統是群,其中r為實數集。（ ）
28．群中的運算滿足消去律。（ ）
29．根樹中所有結點的入度為1。（ ）
30．完全圖ｋ５是尤拉圖。（ ）
31．有n個結點的無向完全圖是漢密爾頓圖。（ ）
32．平面圖一定是連通圖。（ ）
33．兩個結點相同，邊數相同的圖一定同構。（ ）
34．漢密爾頓圖一定不是尤拉圖。（ ）
35．漢密爾頓圖是連通圖。（ ）
三．計算題
1． 將「我留下，僅當你走」命題符號化。
2．將「除非天不下雨，否則我乘車上班」命題符號化。
3．將「我去鎮上，僅當我有時間」命題符號化。
4．將「我將去看電影，當我有時間」命題符號化。
5．將復合命題「我既不去看電影，也不去看電視，我準備做作業。」分解成
原子命題。
6．做命題公式(p→q)→￢r的真值表。
7．做命題公式(q∧g)∨￢r的真值表。
8．求出命題公式￢（p→q）∧r的合取正規化。
9．求（p→q）→r的析取正規化。
10．求￢（p→q）的合取正規化。
11．求出命題公式￢（p→q）→r的合取正規化。
12．將「不是所有運動員都是教練員」謂詞符號化。
13．求空集ф的冪集的冪集。
14．求空集ф的冪集。
15．已知集合a=上的關係r=，求r的對稱閉包s(r)。
16．a=上的小於等於關係是偏序關係，a的子集b=，求b的極大元，極小元，最大元，最小元。
17．整數集i上的同餘模5的關係r是等價關係，試求出由r所確定的所有等價類。
18．設a=上的二元關係r=，求r（r）。
19．設a=上的二元關係r=，求s(r)-r．
20．設a=上的二元關係r=，求t（r）。
21．設a=上的二元關係r=和
s=,求sοr。
22．設a=上的二元關係s=,求s的逆關係。
23．設a=上的關係r=，
s=，求r∪s。
24．設a=上的關係r=，
s=，求r∩s。
25．設a=上的關係r=，
s=，求s-r。
26．設a=上的關係r=，
s=，求～r∪s。
27．設a=，b=，求ab。
28．設a=，b=，求～（ab）。
29．已知集合a=上的關係r=，求r的傳遞閉包t(r)。
30．集合a=上的大於等於關係是偏序關係，a的子集
b=，求b的極大元，極小元，最大元，最小元。
31．集合t=上的關係r=是等價關係，試求出由r所確定的所有等價類。
35．設a=, b=，求出從a到b的一切可能的函式。
36．已知函式f=, g=，求fоg。
37．給出兩個是群的代數系統。
38．舉出兩個不是群的代數系統。
39．集合s=上的二元運算*的運算表如下，求出它的么元，零元，及逆元。
* a b c d e
a b a c c c
b a b c d e
c c c c c c
d e d c b a
e d e c d b
40．設a=，a的冪集p（a）上的交運算∩，給出它的運算表。
41．設a=，a的冪集p（a）上的交運算∪，給出它的運算表。
42．求出帶權為1，3，4，5，6的最優二叉樹，並求其權。
43．一棵樹中，度數為2的結點有a個，度數為3的結點有b個，度數為4的結點有c個，剩下的結點度數都為1，求出度數為1的結點有多少個。
四．證明題
7．設fоg是復合函式，如果是fоg入射，證明g也是入射。
8．已知r是實數集，＊是普通乘法運算，判斷代數系統是否是
乙個群，並證明你的結論。
9. 設i是整數集，h=，+是普通的加法運算，證明代數系統與代數系統是同構的。
10.問有1個結點的度數為1，2個結點的度數為2，3個結點的度數為3，
4個結點的度數為4的樹嗎？並證明你的理由。
（0004）《離散數學》複習思考題答案
一．1． 不是；2 不是； 3是； 4 是；5 x,y；6 真；7 ≠；8 =；9 8；
10 ；11；12 2 9；13 =；14 r∩s；15 r∩s；16 偏序關係；17不是；18 ≠； 19．是；20 8；21 是；22 0；23 1；24 是；25 有；
26 迴圈群；27 n-1；28 不是；29 0；30 大於；31 不一定是；32 1；
33 樹；34 一定是；35 邊數的兩倍。
二．1． 叉；2勾；3勾；4勾；5叉；6勾；7勾；8勾；9叉；10勾。
離散數學考題總結
第1章主要介紹集合論的基本概念和結論，集合的運算及其性質，以及利用運算性質進行集合表示式的化簡和集合恒等式的證明等內容 考試經常涉及到的題型有以下4個 集合與集合之間的包含 元素與集合之間的屬於關係 冪集的計算 集合之間的運算 利用集合運算性質證明集合恒等式 大家對於集合與集合 元素和集合之間的關係...
離散數學 複習
第1章命題邏輯 本章重點 命題與聯結詞，公式與解釋，真值表，公式的型別及判定,主 析取 合取 正規化，命題邏輯的推理理論.一 重點內容 1.命題 命題表述為具有確定真假意義的陳述句。命題必須具備二個條件 其一，語句是陳述句 其二，語句有唯一確定的真假意義.2.六個聯結詞及真值表 否定聯結詞，p是命題...
離散數學複習
例題1 設是群，是的子群，在g上定義關係r r 證明 r是集合g上的等價關係。證明 即證明r為自反 對稱和傳遞關係。1 證自反 是子群，則h中必然存在么元，設為e。則ag，eh，a a e，所以 r，所以，r為自反關係。2 證對稱 a,bg,若r，則hh，a b h，因為是子群，則h必然具有逆元h ...