數理邏輯部分以判定推理為主：包括對給定合式公式屬性的判定及熟練使用８條規則進行有效推理。這一部分佔20分。
代數系統部分：掌握代數系統的基本概念，包括子代數，代數系統的同態、同構，積代數和商代數的求法等，特殊代數系統掌握群相關的內容，如何求子群等。這部分佔20分。
圖論部分掌握圖的基本概念，圖的矩陣表示及矩陣攜帶的資訊，重點掌握樹相關的概念。這部分佔２0分。
平時成績佔２０分。
針對各部分所做的練習。
１、求下列公式的主正規化，並判定公式的屬性。
例1 1(pqr)(pqr)(pq)
解：上式=(pqr)(pqr)(pq)(r r)=(pqr)(pqr)(pqr) (pqr)
=m7, m3, m1,m0其中表示析取。
該公式含三個變元，與其等價的主析取正規化四項，所以它是可滿足的。
例1 2 (p(qr))(p (q r))
解：上式＝ (p(qr)) (p(qr))
= (pq)(pr)(pq)(pr)
= (pqr)(pqr)
(pqr)(pqr)
(pqr)(pqr)
(pqr)(pqr)
=m4,m5, m6,m2, m3,m1其中表示合取。
該公式是可滿足的。
例1 3剛進入大學的小張與寢室裡的其他三人聊天，這三個人根據小張的口音分別作出下述判斷：
甲說：小張不是蘇州人，是上海人。
乙說：小張不是上海人，是蘇州人。
丙說：小張既不是上海人，也不是杭州人。
小張聽後，笑曰：你們三人有一人全說對了，有一人全說錯了，還有一人對錯各半。
試用命題邏輯推斷小張究竟是**人。
解：首先符號化：
設：ｐ：小張是蘇州人
ｑ：小張是上海人
ｒ：小張是杭州人
根據題意有：
甲：pq,
乙： q p,
丙： q r
分析小張只可能是其中乙個城市的人或者不是這三個城市的人。
根據甲乙丙三人的說話內容可以判斷：丙至少說對了一半，因此甲或乙必有一人全錯了。若甲全錯了，則有q p即乙全對了。若乙全錯了，則甲全對。所以丙必是一對一錯。
將小張的話符號化為：
((pq) ((qr)(qr)))
((qp)((qr) (qr)))t
化簡得： (pqr) ( pqr)
小張不可能既是蘇州人又是杭洲人，所以只能是上海人。
例1 4甲乙丙丁４人中僅有兩個人代表單位參加了市裡的橋牌比賽，關於誰參加比賽，下列４種說法都是正確的：
１甲和乙兩人中有一人參加；
２若丙參加，則丁必參加；
３乙和丁兩人中至多參加一人；
４若丁不參加，則甲也不參加。
試判斷哪兩個人參加了比賽。
解：符號化命題如下：
設ａ：甲參加了比賽；
ｂ：乙參加了比賽
ｃ：丙參加了比賽
ｄ：丁參加了比賽
依題意將1,2,3,4分別符號化為：
((ab)(ab))
(cd)(bd)(da) t
將上式化為主析取正規化應有24=16個極小項
即m0000, m0001, m0010, m0011,
m0100, m0101,m0110, m0111,
m1000, m1001, m1010, m1011,
m1100,m1101, m1110, m1111
根據題意去掉不合法的
得到的結論是甲和丁參加了比賽。
例1 5當p，q，r，s四個人考試成績出來後，有人問四個人中誰的成績最好，p說「不是我」，q說「是s」，r說是「q」，s說「不是我」。四個人的回答只有乙個人符合實際，問哪一位的成績最好。若有兩人成績並列最好，是誰？
解：令p: p的成績最好；q：q的成績最好；r：r的成績最好；s：s的成績最好。
若只有p回答正確： p s q s
若只有q回答正確： p s q s
若只有r回答正確： p s q s
若只有s回答正確： p s q s
由於 (p s q s) ( p s q s) ( p s q s) ( p s q s)
= (p q s) (p q s)
=(p q r s) (p q r s) (p q r s) (p q r s)
若只有乙個人成績最好，必是p q r s為真，即p成績最好；若有兩個人成績並列最好，可能是p,s或者p,r
練習：利用主正規化判斷下式的型別
(p→q) (q→r) →((p q) →r)
結果 = m4,m6,m2
該公式是可滿足的
２、對下面的問題首先符號化，然後使用８條規則進行有效推理證明。
2 1每乙個自然數不是奇數就是偶數，自然數是偶數當且僅當它能被2整除，並不是所有的自然數都能被2整除。因此，有的自然數是奇數。
解法1：首先定義如下謂詞：
n(x):x是自然數
q(x):x是奇數
e(x):x是偶數
i(x):x能被2整除
於是問題可用符號表述為：
(x)(n(x)(q(x)e(x))),
(x)((n(x) e(x)) i(x)),
(x)(n(x) i(x)) ，(x)(n(x) q(x))
推理證明過程如下：
1 (x)(n(x) i(x)) p規則
2 (x)(n(x) i(x)) t規則和1
3 n(a) i(aes規則和2
4 n(at規則和3
5 i(at規則和3
6 (x)(n(x)(q(x)e(x))) p規則
7 n(a)(q(a)e(a)) us規則和６
8 q(a)e(a) t規則３和７
9 (x)((n(x) e(x)) i(x)) p規則
10 (n(a) e(a)) i(a) us規則和11 (n(a) e(at規則5和10
12 n(a)e(at規則和11
13 e(at規則4和12
14 q(at規則8和13
15 n(a)q(at規則4和14
16(x)(n(x) q(xeg規則和15
問題得證。
解法2：採用反證法。證明過程如下
1(x)(n(x) i(x)) p規則
2(x)(n(x) i(x)) t規則和1
3 n(a) i(aes規則和2
4 n(at規則和3
5 i(at規則和3
6 (x)(n(x) q(x)) p規則(假設前提)
7 (x)( n(x) q(x)) t規則和6
8 n(a) q(aus規則和７
9 q(at規則４和8
10 (x)(n(x)(q(x)e(x))) p規則
11 n(a)(q(a)e(a)) t規則和10
12 q(a)e(at規則4和11
13 e(at規則9和12
14 (x)((n(x) e(x)) i(x)) p規則
15 (n(a) e(a)) i(a) us規則和1416 n(a) e(at規則4和13
17 i(at規則15和16
18 i(a) i(at規則5和17
19(x)(n(x) q(xf規則6和18
問題得證．
例2 2天鵝都會飛，而癩**不會飛；
所以癩**不是天鵝。
解：令te(x):x是天鵝
l(x):x是癩**
f(x):x會飛
於是問題可符號化為：
(x)(te(x) f(x)), (x)(l(x) f(x))
(x)(l(x) te(x))
證明過程如下：
1(x)(l(x) te(x)) p規則(假設前提)
2(x)(l(x) te(xt規則和１
3 l(a) te(aes規則2
4 l(at規則3
5 te(at規則3
6 (x)(te(x) f(x)) p規則
7 te(a) f(aus規則和6
8 f(at規則5和7
9 (x)(l(x) f(xp規則
10 l(a) f(aus規則和9
11 f(a) l(at規則和10
12 l(at規則8和11
13 l(a) l(at規則4和12
14 (x)(l(x) te(x)) f規則１和13
問題得證。
例2 3 所有牛都有角，有些動物是牛，所以有些動物有角
解：設ｎ(x):x是牛
ｊ(x):x有角
a(x):x是動物
於是問題可描述成：
(x)(ｎ(x) →ｊ(x)),(x)(a(x)∧ｎ(x))
(x)(a(x)∧ｊ(x))
證明：１、(x)(a(x)∧ｎ(x)) p規則
２、a(a)∧ｎ(aes規則和１
３、 a(a) t規則和２
４、ｎ(a) t規則和２
５、(x)(ｎ(x) →ｊ(x)) p規則
６、ｎ(a) →ｊ(a) us規則和５
７、ｊ(a) t規則４和６
離散期末練習試卷
上海應用技術學院2008 2009學年第一學期 離散數學 期末試卷 a 課程 b204216學分 4 考試時間 100 分鐘 課程序號 3404 班級學號姓名 我已閱讀了有關的考試規定和紀律要求，願意在考試中遵守 考場規則 如有違反將願接受相應的處理。試卷共 6 頁，請先檢視試卷有無缺頁，然後答題。...
離散最後總結
主要內容 1.命題符號化 命題邏輯和謂詞邏輯都有考察。否定式與否定聯結詞 非p 合取式與合取聯結詞 p並且q 析取式與析取聯結詞 p或q 蘊涵式與蘊涵聯結詞 如果p,則q 相同的表達為 若p，就q 只要p，就q p僅當q 只有q 才p 除非q,才p 除非q，否則非p 練習 如果交通不阻塞，他就不會遲...
離散數學期末試題個人總結
這個是第一章最有可能出的題型，且老師也曾多次強調過 老師說第二章會弄點中文的話讓我們用符號翻譯，因找不到好的題目，就用下面的代替，不過我相信，要是把上面的這 這幾行意思弄懂了，文字轉字元，就絕對沒什麼問題了 老師強調關係是很關鍵的一章，甚至有可能出2道題，因為第四章考試範圍是4.1 4.4以及4.7...