第一篇：離散數學第一章命題邏輯知識點總結
數理邏輯部分
第1章
命題邏輯 1.1 命題符號化及聯結詞
命題: 判斷結果惟一的陳述句
命題的真值: 判斷的結果
真值的取值: 真與假 真命題: 真值為真的命題 假命題: 真值為假的命題
注意: 感嘆句、祈使句、疑問句都不是命題，陳述句中的悖論以及判斷結果不惟一確定的也不是命題。
簡單命題(原子命題)：簡單陳述句構成的命題
復合命題：由簡單命題與聯結詞按一定規(guī)則復合而成的命題
簡單命題符號化
用小寫英文字母 p, q, r, … ,pi,qi,ri(i≥1）表示 簡單命題
用“1”表示真，用“0”表示假
例如，令 p：
是有理數，則 p 的真值為 0 q：2 + 5 = 7，則 q 的真值為 1
聯結詞與復合命題 1.否定式與否定聯結詞“?”
定義 設p為命題，復合命題 “非p”（或 “p的否定”）稱
為p的否定式，記作?p.符號?稱作否定聯結詞，并規(guī)定?p 為真當且僅當p為假.2.合取式與合取聯結詞“∧”
定義 設p,q為二命題,復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q.∧稱作合取聯結詞，并規(guī)定 p∧q為真當且僅當p與q同時為真
注意：描述合取式的靈活性與多樣性
分清簡單命題與復合命題
例 將下列命題符號化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學.解 令
p：王曉用功，q：王曉聰明，則
(1)p∧q
(2)p∧q
(3)p∧?q.令 r : 張輝是三好學生，s :王麗是三好學生
(4)r∧s.(5)令 t : 張輝與王麗是同學，t 是簡單命題.說明:
(1)~(4)說明描述合取式的靈活性與多樣性.(5)中“與”聯結的是兩個名詞，整個句子是一個簡單命題.3.析取式與析取聯結詞“∨”
定義 設 p,q為二命題，復合命題“p或q”稱作p與q的析取式，記作p∨q.∨稱作析取聯結詞，并規(guī)定p∨q為假當且僅當p與q同時為假.例
將下列命題符號化
(1)2或4是素數.(2)2或3是素數.(3)4或6是素數.(4)小元元只能拿一個蘋果或一個梨.(5)王曉紅生于1975年或1976年.解 令 p:2是素數, q:3是素數, r:4是素數, s:6是素數，則(1),(2),(3)均為相容或.分別符號化為: p∨r , p∨q, r∨s，它們的真值分別為 1, 1, 0.而(4),(5)為排斥或.令 t :小元元拿一個蘋果，u:小元元拿一個梨，則(4)符號化為
(t∧?u)∨(?t∧u).令v :王曉紅生于1975年,w:王曉紅生于1976年,則(5)既可符號化為(v∧?w)∨(?v∧w), 又可符號化為 v∨w , 為什么? 4.蘊涵式與蘊涵聯結詞“?” 定義 設 p,q為二命題，復合命題 “如果p,則q” 稱作p與q的蘊涵式，記作p?q，并稱p是蘊涵式的前件，q為蘊涵式的后件.?稱作蘊涵聯結詞，并規(guī)定，p?q為假當且僅當 p 為真 q 為假.p?q 的邏輯關系：q 為 p 的必要條件
“如果 p，則 q ” 的不同表述法很多：
若 p，就 q
只要 p，就 q
p 僅當 q
只有 q 才 p
除非 q, 才 p 或
除非 q, 否則非 p.當 p 為假時，p?q 為真
常出現的錯誤：不分充分與必要條件
5.等價式與等價聯結詞“?”
定義 設p，q為二命題，復合命題 “p當且僅當q”稱作p與q的等價式，記作p?q.?稱作等價聯結詞.并規(guī)定p?q為真當且僅當p與q同時為真或同時為假.說明:
(1)p?q 的邏輯關系:p與q互為充分必要條件
(2)p?q為真當且僅當p與q同真或同假
聯結詞優(yōu)先級:(),?, ?, ?, ?, ?
同級按從左到右的順序進行
以上給出了5個聯結詞：?, ?, ?, ?, ?，組成 一個聯結詞集合{?, ?, ?, ?, ?}，聯結詞的優(yōu)先順序為：?, ?, ?, ?, ?;如果出 現的聯結詞同級，又無括號時，則按從左到右 的順序運算;若遇有括號時，應該先進行括號 中的運算.注意: 本書中使用的 括號全為園括號.? 命題常項
? 命題變項
1.2 命題公式及分類
? 命題變項與合式公式 ? 命題常項：簡單命題
? 命題變項：真值不確定的陳述句
? 定義 合式公式(命題公式, 公式)遞歸定義如下： ?(1)單個命題常項或變項 p,q,r,…,pi ,qi ,ri ,…,0,1 ?
是合式公式
?(2)若A是合式公式，則(?A)也是合式公式
?(3)若A, B是合式公式，則(A?B),(A?B),(A?B),(A?B)也是合式公式 ?(4)只有有限次地應用(1)~(3)形成的符號串才是合式公式 ? 說明: 元語言與對象語言，外層括號可以省去
合式公式的層次 定義
(1)若公式A是單個的命題變項, 則稱A為0層公式.(2)稱A是n+1(n≥0)層公式是指下面情況之一：
(a)A=?B, B是n層公式；
(b)A=B?C, 其中B,C分別為i層和j層公式，且
n=max(i, j)；
(c)A=B?C, 其中B,C的層次及n同(b)；
(d)A=B?C, 其中B,C的層次及n同(b)；
(e)A=B?C, 其中B,C的層次及n同(b).例如
公式
p ?p
?p?q
?(p?q)?r
((?p?q)?r)?(?r?s)
公式的賦值
定義 給公式A中的命題變項 p1, p2, … , pn指定
一組真值稱為對A的一個賦值或解釋
成真賦值: 使公式為真的賦值
成假賦值: 使公式為假的賦值
說明：
0層
1層
2層
3層
4層
???????
賦值?=?1?2…?n之間不加標點符號，?i=0或1.?
A中僅出現 p1, p2, …, pn，給A賦值?1?2…?n是 ? 指 p1=?1, p2=?2, …, pn=?n
?
A中僅出現 p, q, r, …, 給A賦值?1?2?3…是指 ? p=?1,q=?2 , r=?3 …
?
含n個變項的公式有2n個賦值.? 真值表
真值表: 公式A在所有賦值下的取值情況列成的表
例 給出公式的真值表
A=(q?p)?q?p 的真值表
例
B = ?(?p?q)?q 的真值表
例
C=(p?q)??r 的真值表
命題的分類
重言式
矛盾式
可滿足式
定義 設A為一個命題公式
(1)若A無成假賦值，則稱A為重言式(也稱永真式)
(2)若A無成真賦值，則稱A為矛盾式(也稱永假式)
(3)若A不是矛盾式，則稱A為可滿足式
注意：重言式是可滿足式，但反之不真.上例中A為重言式，B為矛盾式，C為可滿足式
A=(q?p)?q?p，B =?(?p?q)?q，C=(p?q)??r
1.3 等值演算
? 等值式 定義 若等價式A?B是重言式，則稱A與B等值，記作A?B，并稱A?B是等值式
說明：定義中，A,B,?均為元語言符號, A或B中 可能有啞元出現.例如，在(p?q)?((?p?q)?(?r?r))中，r為左邊 公式的啞元.用真值表可驗證兩個公式是否等值 請驗證：p?(q?r)?(p?q)?r
p?(q?r)
(p?q)?r
? 基本等值式
雙重否定律 : ??A?A
等冪律：
A?A?A, A?A?A
交換律:
A?B?B?A, A?B?B?A
結合律:
(A?B)?C?A?(B?C)
(A?B)?C?A?(B?C)分配律:
A?(B?C)?(A?B)?(A?C)
A?(B?C)?(A?B)?(A?C)德·摩根律:
?(A?B)??A??B
?(A?B)??A??B
吸收律:
A?(A?B)?A，A?(A?B)?A
零律:
A?1?1，A?0?0 同一律:
A?0?A，A?1?A
排中律:
A??A?1 矛盾律:
A??A?0
? 等值演算:
由已知的等值式推演出新的等值式的過程
置換規(guī)則：若A?B, 則?(B)??(A)等值演算的基礎：
(1)等值關系的性質：自反、對稱、傳遞
(2)基本的等值式
(3)置換規(guī)則
應用舉例——證明兩個公式等值 例1 證明 p?(q?r)?(p?q)?r
證
p?(q?r)
??p?(?q?r)
（蘊涵等值式，置換規(guī)則）
?(?p??q)?r
（結合律，置換規(guī)則）
??(p?q)?r
（德?摩根律，置換規(guī)則）
?(p?q)?r
（蘊涵等值式，置換規(guī)則）說明:也可以從右邊開始演算（請做一遍）
因為每一步都用置換規(guī)則，故可不寫出
熟練后，基本等值式也可以不寫出
應用舉例——證明兩個公式不等值 例2 證明: p?(q?r)
(p?q)?r
用等值演算不能直接證明兩個公式不等值,證明兩 個公式不等值的基本思想是找到一個賦值使一個成 真,另一個成假.方法一
真值表法（自己證）
方法二
觀察賦值法.容易看出000, 010等是左邊的 的成真賦值，是右邊的成假賦值.方法三
用等值演算先化簡兩個公式，再觀察.應用舉例——判斷公式類型
例3 用等值演算法判斷下列公式的類型
(1)q??(p?q)解
q??(p?q)
? q??(?p?q)
（蘊涵等值式）
? q?(p??q)
（德?摩根律）
? p?(q??q)
（交換律，結合律）
? p?0
（矛盾律）
? 0
（零律）
由最后一步可知，該式為矛盾式.(2)(p?q)?(?q??p)解
(p?q)?(?q??p)
?(?p?q)?(q??p)
（蘊涵等值式）
?(?p?q)?(?p?q)
（交換律）
? 1 由最后一步可知，該式為重言式.問：最后一步為什么等值于1？
(3)((p?q)?(p??q))?r)
解
((p?q)?(p??q))?r)
?(p?(q??q))?r
（分配律）
? p?1?r
（排中律）
? p?r
（同一律）
這不是矛盾式，也不是重言式，而是非重言式的可 滿足式.如101是它的成真賦值,000是它的成假賦值.總結：A為矛盾式當且僅當A?0 A為重言式當且僅當A?1 說明：演算步驟不惟一,應盡量使演算短些
1.5 對偶與范式 對偶式與對偶原理
定義 在僅含有聯結詞?, ∧,∨的命題公式A中，將 ∨換成∧, ∧換成∨，若A中含有0或1，就將0換成 1，1換成0，所得命題公式稱為A的對偶式，記為A*.從定義不難看出，(A*)* 還原成A
定理 設A和A*互為對偶式，p1,p2,…,pn是出現在A和
A*中的全部命題變項，將A和A*寫成n元函數形式，則(1)? A(p1,p2,…,pn)? A*(? p1, ? p2,…, ? pn)
(2)A(? p1, ? p2,…, ? pn)? ? A*(p1,p2,…,pn)定理（對偶原理）設A，B為兩個命題公式，若A ? B，則A* ? B*.析取范式與合取范式
文字:命題變項及其否定的總稱
簡單析取式:有限個文字構成的析取式
如 p, ?q, p??q, p?q?r, …
簡單合取式:有限個文字構成的合取式
如 p, ?q, p??q, p?q?r, …
析取范式:由有限個簡單合取式組成的析取式
A1?A2???Ar, 其中A1,A2,?,Ar是簡單合取式
合取范式:由有限個簡單析取式組成的合取式
A1?A2???Ar , 其中A1,A2,?,Ar是簡單析取式 范式:析取范式與合取范式的總稱
公式A的析取范式: 與A等值的析取范式
公式A的合取范式: 與A等值的合取范式 說明：
單個文字既是簡單析取式，又是簡單合取式
p??q?r, ?p?q??r既是析取范式，又是合取范式(為什么?)
命題公式的范式
定理
任何命題公式都存在著與之等值的析取范式 與合取范式.求公式A的范式的步驟：
(1)消去A中的?, ?（若存在）
(2)否定聯結詞?的內移或消去
(3)使用分配律
?對?分配（析取范式）
?對?分配（合取范式）
公式的范式存在，但不惟一
求公式的范式舉例
例 求下列公式的析取范式與合取范式
(1)A=(p??q)??r
解
(p??q)??r
?(?p??q)??r
（消去?）
? ?p??q??r
（結合律）
這既是A的析取范式（由3個簡單合取式組成的析 取式），又是A的合取范式（由一個簡單析取式 組成的合取式）
(2)B=(p??q)?r
解
(p??q)?r
?(?p??q)?r
（消去第一個?）
? ?(?p??q)?r
（消去第二個?）
?(p?q)?r
（否定號內移——德?摩根律）
這一步已為析取范式（兩個簡單合取式構成）
繼續(xù)：
(p?q)?r
?(p?r)?(q?r)
（?對?分配律）
這一步得到合取范式（由兩個簡單析取式構成）
極小項與極大項
定義 在含有n個命題變項的簡單合取式(簡單析取式)中，若每個命題變項均以文字的形式在其中出現且僅出現一 次，而且第i（1?i?n）個文字出現在左起第i位上，稱這樣 的簡單合取式（簡單析取式）為極小項（極大項）.說明：n個命題變項產生2n個極小項和2n個極大項
2n個極小項（極大項）均互不等值
用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示.用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示, mi(Mi)稱為極小項(極大項)的名稱.mi與Mi的關系:
?mi ? Mi ，?Mi ? mi
主析取范式與主合取范式
主析取范式: 由極小項構成的析取范式
主合取范式: 由極大項構成的合取范式
例如，n=3, 命題變項為p, q, r時，(?p??q?r)?(?p?q?r)? m1?m3 是主析取范式
(p?q??r)?(?p?q??r)? M1?M5 是主合取范式
A的主析取范式: 與A等值的主析取范式 A的主合取范式: 與A等值的主合取范式.定理
任何命題公式都存在著與之等值的主析取范 式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步驟：
(1)先求析取范式（合取范式）
(2)將不是極小項（極大項）的簡單合取式（簡
單析取式）化成與之等值的若干個極小項的析
?。O大項的合?。枰猛宦桑?/p>
律）、排中律（矛盾律）、分配律、冪等律等.(3)極小項（極大項）用名稱mi（Mi）表示，并 按角標從小到大順序排序.求公式的主范式
例 求公式 A=(p??q)?r的主析取范式與主合取范式.(1)求主析取范式
(p??q)?r
?(p?q)?r ，（析取范式）
①
(p?q)
?(p?q)?(?r?r)
?(p?q??r)?(p?q?r)
? m6?m7 ，r
?(?p?p)?(?q?q)?r
?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r)
? m1?m3?m5?m7
③
②, ③代入①并排序，得
(p??q)?r ? m1?m3?m5? m6?m7（主析取范式）
(2)求A的主合取范式
(p??q)?r
?(p?r)?(q?r)，（合取范式）
①
p?r
? p?(q??q)?r
?(p?q?r)?(p??q?r)
? M0?M2, q?r
?(p??p)?q?r
?(p?q?r)?(?p?q?r)
? M0?M4
②, ③代入①并排序，得
(p??q)?r ? M0?M2?M4
（主合取范式）主范式的用途——與真值表相同(1)求公式的成真賦值和成假賦值
例如
(p??q)?r ? m1?m3?m5? m6?m7，其成真賦值為001, 011, 101, 110, 111，其余的賦值 000, 010, 100為成假賦值.類似地，由主合取范式也可立即求出成
②③
假賦值和成真賦值.(2)判斷公式的類型
設A含n個命題變項，則
A為重言式?A的主析取范式含2n個極小項
?A的主合取范式為1.A為矛盾式? A的主析取范式為0
? A的主合取范式含2n個極大項
A為非重言式的可滿足式
?A的主析取范式中至少含一個且不含全部極小項
?A的主合取范式中至少含一個且不含全部極大項
例 某公司要從趙、錢、孫、李、周五名新畢 業(yè)的大學生中選派一些人出國學習.選派必須 滿足以下條件：
(1)若趙去，錢也去；
(2)李、周兩人中至少有一人去；
(3)錢、孫兩人中有一人去且僅去一人；
(4)孫、李兩人同去或同不去；
(5)若周去，則趙、錢也去.試用主析取范式法分析該公司如何選派他們出 國？
解此類問題的步驟為：
① 將簡單命題符號化
② 寫出各復合命題
③ 寫出由②中復合命題組成的合取式
④ 求③中所得公式的主析取范式
解 ① 設p：派趙去，q：派錢去，r：派孫去，s：派李去，u：派周去.②(1)(p?q)
(2)(s?u)
(3)((q??r)?(?q?r))
(4)((r?s)?(?r??s))
(5)(u?(p?q))
③(1)~(5)構成的合取式為
A=(p?q)?(s?u)?((q??r)?(?q?r))?
((r?s)?(?r??s))?(u?(p?q))④
A ?(?p??q?r?s??u)?(p?q??r??s?u)結論：由④可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去）或派趙、錢、周去（孫、李不去）.A的演算過程如下:
A ?(?p?q)?((q??r)?(?q?r))?(s?u)?(?u?(p?q))?
((r?s)?(?r??s))
（交換律)B1=(?p?q)?((q??r)?(?q?r))
?((?p?q??r)?(?p??q?r)?(q??r))（分配律）
B2=(s?u)?(?u?(p?q))
?((s??u)?(p?q?s)?(p?q?u))
（分配律）
B1?B2 ?(?p?q??r?s??u)?(?p??q?r?s??u)
?(q??r?s??u)?(p?q??r?s)?(p?q??r?u)再令 B3 =((r?s)?(?r??s))得 A ? B1?B2?B3
?(?p??q?r?s??u)?(p?q??r??s?u)注意：在以上演算中多次用矛盾律
要求：自己演算一遍
1.6 推理理論 推理的形式結構
推理的形式結構—問題的引入
推理舉例:
(1)正項級數收斂當且僅當部分和有上界.(2)若
推理: 從前提出發(fā)推出結論的思維過程 上面(1)是正確的推理，而(2)是錯誤的推理.證明: 描述推理正確的過程.判斷推理是否正確的方法 ? 真值表法
? 等值演算法
判斷推理是否正確 ? 主析取范式法
? 構造證明法
證明推理正確
說明：當命題變項比較少時，用前3個方法比較方 便, 此時采用形式結構“造證明時，采用“前提:
”.而在構 , 結論: B”.推理定律與推理規(guī)則 推理定律——重言蘊涵式
構造證明——直接證明法 例 構造下面推理的證明：
若明天是星期一或星期三，我就有課.若有課，今天必備課.我今天下午沒備課.所以，明天不是星期一和星期三.解 設 p：明天是星期一，q：明天是星期三，r：我有課，s：我備課 推理的形式結構為
例 構造下面推理的證明:
2是素數或合數.若2是素數，則
是無理數.若
是無理數，則4不是素數.所以，如果4是
素數，則2是合數.用附加前提證明法構造證明 解 設 p：2是素數，q：2是合數，r：
是無理數，s：4是素數 推理的形式結構
前提：p∨q, p?r, r??s
結論：s?q 證明
① s
附加前提引入
②p?r
前提引入
③r??s
前提引入
④p??s
②③假言三段論
⑤?p
①④拒取式
⑥p∨q
前提引入
⑦q
⑤⑥析取三段論 請用直接證明法證明之
第二篇：離散數學總結
一、課程內容介紹：
1．集合論部分： 離散數學學習總結
集合論是離散數學中第一個抽象難關，在老師的生動講解下，深入淺出，使得集合論成了相當有趣的知識。只是對于以后的應用還不是很了解，感覺學好它很重要。直觀地說，把一些事物匯集到一起組成一個整體就叫集合，而這些事物就是這個集合的元素或成員。例如： 方程x2－1＝0的實數解集合；
26個英文字母的集合；
坐標平面上所有點的集合；
集合通常用大寫的英文字母來標記，例如自然數集合N(在離散數學中認為0也是自然數)，整數集合Z，有理數集合Q，實數集合R，復數集合C等。
表示一個集合的方法有兩種：列元素法和謂詞表示法，如果兩個集合的交集為，則稱這兩個集合是不相交的。例如B和C是不相交的。
兩個集合的并和交運算可以推廣成n個集合的并和交： A1∪A2∪…∪An＝{x|x∈A1∨x∈A2∨…∨x∈An} A1∩A2∩…∩An＝{x|x∈A1∧x∈A2∧…∧x∈An}
2．關系
二元關系也可簡稱為關系。對于二元關系R，如果
例如R1={<1,2>,
給出一個關系的方法有三種:集合表達式，關系矩陣和關系圖。設R是A上的關系，我們希望R具有某些有用的性質，比如說自反性。如果R不具有自反性，我們通過在R中添加一部分有序對來改造R，得到新的關系R'，使得R'具有自反性。但又不希望R'與R相差太多，換句話說，添加的有序對要盡可能的少。滿足這些要求的R'就稱為R的自反閉包。通過添加有序對來構造的閉包除自反閉保外還有對稱閉包和傳遞閉包。
3．代數系統(tǒng)
代數結構也叫做抽象代數，主要研究抽象的代數系統(tǒng)。抽象的代數系統(tǒng)也是一種數學模型，可以用它表示實際世界中的離散結構。例如在形式語言中常將有窮字符表記為∑，由∑上的有限個字符（包括0個字符）可以構成一個字符串，稱為∑上的字。∑上的全體字符串構成集合∑*。設α,β是∑*上的兩個字，將β連接在α后面得到∑*上的字αβ。如果將這種連接看作∑*上的一種運算，那么這種運算不可交換，但是可結合。集合∑*關于連接運算就構成了一個代數系統(tǒng)，它恰好是抽象代數系統(tǒng)--半群的一個實例。抽象代數在計算機中有著廣泛的應用，例如自動機理論、編碼理論、形式語義學、代數規(guī)范、密碼學等等都要用到抽象代數的知識。代數結構的主要研究對象就是各種典型的抽象代數系統(tǒng)。
構成一個抽象代數系統(tǒng)有三方面的要素：集合、集合上的運算以及說明運算性質或運算之間關系的公理。請看下面的例子。
整數集合Z和普通加法＋構成了代數系統(tǒng)〈Z,＋〉，n階實矩陣的集合Mn(R)與矩陣加法＋構成代數系統(tǒng)〈Mn(R),＋〉。冪集P(B)與集合的對稱差運算也構成了代數系統(tǒng)
。類似這樣的代數系統(tǒng)可以列舉出許多許多，他們都是具體的代數系統(tǒng)。考察他們的共性，不難發(fā)現他們都含有一個集合，一個二元運算，并且這些運算都具有交換性和結合性等性質。為了概括這類代數系統(tǒng)的共性，我們可以定義一個抽象的代數系統(tǒng)
為了研究抽象的代數系統(tǒng)，我們需要先定義一元和二元代數運算以及二元運算的性質，并通過選擇不同的運算性質來規(guī)定各種抽象代數系統(tǒng)的定義。在此基礎上再深入研究這些抽象代數系統(tǒng)的內在特性和應用。
4．圖論部分
圖論是作為我們計算機專業(yè)的一門很有用處的知識，也是新興的一個數學分支，在計算機迅速發(fā)展的同時，圖論也迅速發(fā)展。因此，圖論給我們以一種神奇的感覺，在學習圖論中，老師總是把圖論分析得很透徹，學起來很有趣，同時也很簡單。圖論在數據結構方面的應用極其廣泛，對我們學計算機專業(yè)的人來說，是一門必須要學好的知識。
一個圖可以用一個圖形表示，定義中的結點對可以是有序的，也可以是無序的，若邊所對誤碼的結點對（a,b）是有序的，剛稱L是有向邊，a稱為L的起點，b稱為L的終點，若邊L所對應的結點對（a,b）是無序的，則稱L是無向邊。
5．數理邏輯部分
數理邏輯作為離散數學的最后一部分，充滿著對邏輯思維的挑戰(zhàn)，同時鍛煉了我們思考問題的嚴密性，當然最重要的是學會如何用數學方法去分析邏輯問題。
數理邏輯又稱符號邏輯，它是用數學方法支研究抽象思維的規(guī)律的應用學科，1.命題：把能判斷真假的陳述句稱為命題，作為命題的陳述句表達的判斷結果稱為命題的真值。命題公式、對偶與范式、命題演算的推理等等。
二、學習總結與體會
在本學期一開始學習這門課程時，老師就明確的告訴我們這門課程很重要，是我們大學中專業(yè)課程的核心課程，同時由于難度系數較高，故本門課程較為難學。總的來說，一個學期下來，自認為比較好地掌握了離散數學的基礎知識，并在平時的各方面得到了很好的應用。
對于離散數學，在剛開始學習的不知道他的重要性，以為他與高等數學一樣，或者學習的時候的時候，一定要有高等數學的知道，其實不然，當我開始學習之后才知道，只有掌握了高等數學以及線性代數等相關知道才能更好的學習離散數學。而且，作為計算機科學專業(yè)的學生，離散數學當中所涉及到相關知道，對于我們是至關重要的。比如，關系、群、路徑、圖的矩陣表示、樹等內容，都是在計算機程序設計以及相關
信息當中要用到的內容。
所以學習了離散數學課之后，我的收獲是很多的。對于一些數學相關的知識有了不同的理解，學會了用不同的方法去解決程序設計方法以及將計算機和數學有機聯系起來，不過在學習的過程中也遇到了一些難題，最為突出的，就是書本上的和老師講解的都還是比較的簡單，自己在課堂上也能聽懂，但是到具體的應用就很困難了。
特別是不看書，就很多的東西都還給了老師，所以，我會嚴格的要求自己，學過的東西，都要下來練習，盡量的多做一些習題，盡量的把學過的數學基礎知識練熟悉，這樣才能夠提高自己專業(yè)知識，提高自己解決問題的能力。
有一點讓我遺憾的是沒有學完這門課程，但在這門課程快要結束的時候，我總結了學習中遇到的一些問題，最為突出的是，書本上的知識與老師講的都比較容易懂，可是在真正運到實際生活中時，就不能將老師所講的知識點與書上所羅列的。因此，針對這一情況，在以后的學習中我會嚴格要求自己，多參加實踐，只有這樣，才能夠提高運用知識，解決問題的能力。
三、教學建議
1.在課程開設方面，對于離散數學等相關基礎、重要的課程，應當在大一或大二開設，不應放在大三下期，這樣對于我們學習時也有一定的幫助。我希望這一本書上能多一些練習題，以便我們學過了，下課了也有很多的練習題做，來鞏固課堂上的新內容。同時，我也希望在有些程序部分，能給出詳細的注釋語句。
2.相互學習，教師應當努力使現代教學手段與傳統(tǒng)教學手段有機結合，相互取長補短。在教學實施中既能發(fā)揮教學手段的優(yōu)勢，又能善于運用傳統(tǒng)方式，使教學效果達到最佳。建議能給一些學生練習的時間，這樣我們才能對學過的新內容有一個鞏固的時間，其實這樣更有助于以后的教學，前面的基礎知識打牢了，后面的學習更愉快。
3.提升技能：教師應重新認識離散數學與計算機聯系。同時，要始終把學生放在講課對象的中心位置，特別是在課余時間，建議由老師組
織學生進行分組，大家共同學習，由于現今的大學學習較為分散，很多時候同學們都不同在課堂上完成任務，只能下來之后繼續(xù)完成，所以組建學習小組后，通過完成任務等方式，讓學生學習到更多的知識點。學會更多的內容。
4.任務引領：充分調動學習學習積極性讓學習在完成任務的過程當中，充分學習到多媒體課件的制作以及多媒體信息的處理等等。
第三篇：《離散數學》課程總結
《離散數學》學期總結
轉眼之間，這學期要結束了。我們的離散數學，這門課程的學習也即將接近尾聲。下面就是我對這門課一些認識及自己的學習心得。
首先我們這門課程離散數學到底包含了哪幾大部分？每部分具體又有什么內？這門課程在計算機科學中有什么地位？這門課程在我們以后的學習生活中，以及在將來的工作中有什么幫助？下面我將以上幾個方面具體談一談并將總結一下自己本人在這門課程學習過程中遇到的一些問題和心得體會。
這門課程有數理邏輯，集合論，代數系統(tǒng)和圖論四部分。這四大部分通常被稱為離散數學的四大體系。其中每一部分都是一個獨立的學科，內容豐富。而我們離散數學中的內容是其中最基本，最重要且和計算機科學最密切相關的內容吸收到離散數學中來，并使它們前后貫通，形成一個有機整體。這門課的主要內容有命題邏輯、謂詞邏輯，屬于數理邏輯部分，集合論中有集合、二元關系、函數，代數系統(tǒng)包含代數系統(tǒng)基礎、群、環(huán)、域以及格和布爾代數的知識（這部分我們沒有涉及）。
那么這門課程在計算機科學中有著什么樣的地位呢，這門課程是計算機科學專業(yè)中重要的專業(yè)基礎課程，核心課程，可以這么說，離散數學，既是一門專業(yè)基礎課，是一門工具性學科。這門課講授的內容，與后續(xù)專學習業(yè)密切相關。在這門課里我們講授了大量的計算機學科專業(yè)必要的基本概念，基本理論和基本方法。為我們以后的學習，工作打下良好基礎。在算法設計，人工智能，計算機網絡，神經網絡，智能計算等學科中有著重要的作用。在計算機科學中有著廣泛的應用。通過這門課可以對我們計算機算法的理解和邏輯思維得到提高。
那么我們具體學了什么內容呢？
（一）首先集合論是整個數學的基礎，（不管是離散數學還是連續(xù)數學）如果沒有專門學過，那么出現在離散數學中還是很合適的。至于由集合論引出的二元關系，函數的內容，也是理所應當的。
數理邏輯是一個讓人眼前一亮的東西。我第一次發(fā)現，原來有些復雜的推理問題是可以通過“計算”的方法解決的。
數理邏輯，又叫符號邏輯。就是依靠專門的數學符號去推導過程對的科學。在推導過程中，我們探索出一套完整的規(guī)則。這個規(guī)格就是我們的推理規(guī)則。竟然為了確保這套規(guī)則的，準確性。防止二義性，以至于可以將公理理論公式化，依據各項規(guī)則，證得論證的有效性。
這一章里，我們首先學習了，命題邏輯的基本概念。并和一些邏輯連接詞。包括真值連接詞的否定，真值連接詞合取，析取。我們可以用，符號形式寫出各種命題，并利用真值表來判斷命題的真假。用真值表來判斷，命題是十分有效方便的。所以，對于真值表的記憶是十分重要的。命題公式的表示，也是用符號話的需要來給出的。隨后我們學習了永真式和永假式，對于永真式和永假式的證明，用制表技術可以方便的給出。對于永真式，因為原子命題變元，不論表示什么命題，是真的還是假的，它總是真的。所以它反映的是命題邏輯的邏輯規(guī)律。所以我們著重研究永真式。下面，在一個公式中，如果用另外的是替換其中某個或某些原子命題變元，就會得到全新的公式，這個全新的公式，和原公式什么關系呢？進而引出了我們的代入規(guī)則和替換規(guī)則。為了更方便的證明各種命題，我們學習了，等價和蘊涵的各種定理，還有范式和范式的判定問題，其中主要是主析取范式和合取范式的概念，定理，證明。證明過程我們在課上都已經證明過了。在這一章還學習了三段式的證明，此證明方法在以后的學習過程中經常使用。
謂詞邏輯就是對命題和推理做深一步的研究的學習。在謂詞演算中，原子命題分為謂詞和個體兩部分。謂詞邏輯就是將命題的內涵，通過個體和謂詞中的表現出來，把同一類命題，用命題函數表示，增強其表達能力。在這里要注意的是，命題還是不是命題，因為其沒有確定的真假異議，但是可以將一個命題函數轉化為問題，方法有二，（1）用個體域中的特定個體去替換個體變元；（2）這個體域上，將命題函數量化。所謂量化，就是用量詞的命題函數中的個體變元進行約束，由此引入了量詞的概念。量詞分為全稱，量詞與存在量詞，量詞反映了個體域與量詞間的真假關系。此外，在謂詞邏輯中，個體的個體域也是很重要的。將一個命題用謂詞，邏輯符號化時，通常經以下步驟（1）確定特性謂詞及其他謂詞。（2）確定量詞。（3）量詞與邏輯連接詞的搭配。有了量詞的概念后，謂詞邏輯表達能力就讓廣泛了，它所刻畫的語句也也更為普遍，更為深刻。
代數系統(tǒng)，在計算機科學中也非常重要。在計算機科學中帶出系統(tǒng)科，用作研究，抽象數據結構的性能及操作，也是程序設計語言的理論基礎。
圖論這一章里，我們學習的圖并不是幾何學中的圖形。而是客觀世界中某些事物具體聯系的一個數學抽象。用點代表事物，用邊表示各事物間的二元關系。這一章剛開始學的概念很多，讓我感覺有些亂。所以在課后要自己多下功夫了。
然后就是我在學習中出現的一些問題及解決方法了，今天，在學習數理邏輯的時候，覺得離散數學這門課程很簡單。但是隨著學習的進一步深入，我發(fā)現我的想法是錯誤的。對于后面的一些推理論證，自己缺乏思路。雖然，老師在課上也教給了我們推理的方法，但是，還是忍不住去看書上的證明。這一點在隨后的學習中，我一般盡量克服，也是在老師的幫助下，在證明時盡量自己想，憋自己一下，讓自己的思維得到訓練，自己的推理論證能力得到提高。進而使綜合素質，都要提高。
再說一下李勇老師的講課吧，講的非常棒。首先它會對每一部分的內容，及，基本概念給大家進行講解。然后就是強調自己的推理能力。每節(jié)課都會讓我們自己推理，驗證定理。從基礎出發(fā)，從小定理驗證到大定理，由特殊推廣到一般。一般都會讓我們從兩三個開始驗證，逐步得到結論，發(fā)現規(guī)律。一次，李勇老師對，課堂教學有著自己深刻的理解，對這門課的教學方法，教學模式有著獨特的看法。還有就是李勇老師，朋輩式的教學方法，在教學過程中，我們共同進步，教學相長，這樣是非常好的。
對于老師每節(jié)課讓我們自己推理的使用模式，我表示非常贊同。我認為，最好的學習辦法就是找到合適自己解決問題的方法。學習任何課程都是為了解決實際問題。離散數學也是如此，有了對概念的理解，有了正確的思考問題的方式，解決問題的時候就不會走彎路了，也就是說，基本的解決問題的方法就自然而然的掌握了。對于我們從小缺乏鍛煉的推理能力，在這里得到了非常高的提升。
第四篇：學習離散數學總結范文
學習離散數學的心得體會
姓名：
學號：1
班級：計算機
離散數學，對絕大多數學生來說應該都會是一門十分困難的課程，當然也包括我在內。通過這一學期的學習，我對這門課程有一些初步的了解，現在的心情和當初也很不相同。
在還沒有接觸的時候，看見課本就想退縮，心想：這是什么課程啊，這叫數學嗎，這些符號都是之前沒有見過的呢！但是既然都說是挑戰(zhàn)就沒有退縮的道理。雖然不能說是抱著“視死如歸”的精神，至少能說是忐忑不安。在聽老師講課的時候有些定義性的東西總會混淆，我自認為是個越挫越勇的人，并沒有因此退縮。超乎想象的是，老師講課好仔細，好詳細，因為前面的知識是為后面做鋪墊，所以在后面老師經常強調。
而且老師每兩次課都會布置作業(yè)，這讓我們在完成作業(yè)的時候對上過的內容進行了加深，有利于我們更好的學習離散數學。而且每次作業(yè)老師都很認真批改，錯誤的地方都會給你圈出來，以便于我們自己更好的完成訂正。錯誤的地方，經過老師認真仔細的講解，更讓我們對知識點及解題技巧有了一定的認知。當一題題目本來不會做錯了但是經過老師講解聽講到會做這題題目的時候，這種成就感還是相當不錯的呢。難得有這么認真又負責的老師，讓我本來對數學沒什么興趣的人居然也會漸漸地對數學產生了興趣。有了這些認知，我覺得這門課的難點在于課程比較枯燥，好多理論的知識需要我們去理解。
前三章主要是認識邏輯語言符號，了解了數理邏輯的特點，并做一些簡單的邏輯推理和運算。這些知識都是以前所學的進一步轉換，只要將數學的函數符號邏輯化就行。也就是說，那些符號知識形式上的不同，實質上是一樣的。不同的是，之前的數學只需要運用結論證明其他的案例等。但是邏輯數學不僅要知其然還要知其所以然，運用結論正結論。即使如此，我還是覺得這幾章學著很輕松，只要熟練掌握公式定理就會覺得離散數學并不像之前想象的那么困難。
第四章講的是關系。這一章，進一步認識、運用數理邏輯語言，熟練強化練習，深入理解。這一章的難度相較于前幾章要繁瑣些，有很多的符號轉換，運算，運算過程很復雜。對于計算能力不強的我來說，這一章或許是最吃力的，即使知道原理也需要通過大量的練習強化鞏固，而這其中用到的還有線性代數里面的矩陣。
第五章學的是函數，定義和高中所學一樣，只不過是把它轉換運用于數理邏輯，并用邏輯符號進行運算。雖說如此，但是這其中仍然有更深層次的概念和邏輯公式，如果單純的用原有的思維是很難想透徹的。
第六章“圖”和第七章“樹及其應用”可以歸為“圖論”。在剛接觸到“圖”這一章的時候我是抱著好奇之心去學習的，因為這章都是關于“圖”，想了解一下和幾何圖形的差別，所以覺得善長幾何的我應該能夠把它學好。但是不可否認，隨著知識的深入，這一章一定會比前面的更難理解，更難學。因此，上課的時候聽得格外認真，課后還找了一些相關書籍閱覽。在看過這些書籍以后，我才真正了解到它并不是枯燥乏味的，它的用途非常廣泛，并且應用于我們整個日常生活中。比如：怎樣布線才能使每一部電話互相連通，并且花費最小？從首府到每州州府的最短路線是什么？n項任務怎樣才能最有效地由n個人完成？管道網絡中從源點到集匯點的單位時間最大流是多少？一個計算機芯片需要多少層才能使得同一層的路線互不相交？怎樣安排一個體育聯盟季度賽的日程表使其在最少的周數內完成？一位流動推銷員要以怎樣的順序到達每一個城市才能使得旅行時間最短？我們能用4種顏色來為每張地圖的各個區(qū)域著色并使得相鄰的區(qū)域具有不同的顏色嗎？這些問題以及其他一些實際問題都涉及“圖論”。
這里所說的圖并不是幾何學中的圖形，而是客觀世界中某些具體事物間聯系的一個數學抽象，用頂點代表事物，用邊表示各式物間的二元關系，如果所討論的事物之間有某種二元關系，我們就把相應的頂點練成一條邊。這種由頂點及連接這些頂點的邊所組成的圖就是圖論中所研究的圖。由于它關系著客觀世界的事物，所以對于解決實際問題是相當有效的。哥尼斯堡橋問題（七橋問題），這個著名的數學難題，在經過如此漫長的時間最終還是瑞士數學家歐拉利用圖論解決了它，并得出沒有一種方法使得從這塊陸地中的任意一塊開始，通過每一座橋恰好一次再回到原點。
樹是指沒有回路的連通圖。它是連通圖中最簡單的一類圖，許多問題對一般連通圖未能解決或者沒有簡單的方法，而對于樹，則已圓滿解決，且方法較為簡單。而且在許多不同領域中有著廣泛的應用。例如家譜圖就是其中之一。如果將每個人用一個頂點來表示，并且在父子之間連一條邊，便得到一個樹狀圖。
圖論中最著名的應該就是圖的染色問題。這個問題的研究來源于著名的四色問題。四色問題是圖論中也許是全部數學中最出名、最難得一個問題之一。所謂四色猜想就是在平面上任何一張地圖，總可以用至多四種顏色給每一個國家染色，使得任何相鄰國家的顏色是不同的。四色問題粗看起來似乎與我們所討論的圖沒有什么聯系。其實也是可以轉化為圖論中的問題來討論。首先從地圖出發(fā)來構作一個圖，讓每一個頂點代表地圖的一個區(qū)域，如果兩個區(qū)域有一段公共邊界線，就在相應的頂點之間連上一條邊。由于地圖中每一塊區(qū)域對應圖的一個頂點，兩個相鄰頂點對應兩個相鄰的區(qū)域。所以對地圖染色使相鄰的區(qū)域染以不同的顏色相當于對圖的每個頂點染以相應的一種顏色，使得相鄰的頂點有不同的顏色?？傊?，圖論是數學科學的一個分支，而四色問題是典型的圖論課題。
通過對圖論的初步理解和認識，我深深地認識到，圖論的概念雖然有其直觀、通俗的方面，但是這許多日常生活用語被引入圖論后就都有了其嚴格、確切的含義。我們既要學會通過術語的通俗含義更快、更好地理解圖論概念，又要注意保持術語起碼的嚴格。
本以為枯燥乏味的離散數學竟然會是貼近生活，這些歷史難題等等，都讓我對它產生了一定的興趣，雖然不可否認的是，對我來說它確實是一門很難很深奧很抽象的課程，但是仍然不減我對圖論產生的興趣，或許這也就是我選擇這門課程最大的收獲吧。
第五篇：離散數學學期總結
200820174036何志伍計算機科學與技術
離散數學學期總結
離散數學是描繪一些離散量與量之間的相互邏輯結構及關系的學科。它的思想方法及內容滲透到計算機學科的各個領域中。因此它成為計算機及相關專業(yè)的一門重要專業(yè)基礎課。主要內容包括：集合論、關系、代數系統(tǒng)、圖論和數理邏輯五個部分。結構上，從集合論入手，后介紹數理邏輯，便于學生學習。為了能很好的消化理解內容，列舉了大量的較為典型、易于接受、說明問題的例題，配備了相當數量的習題，也列舉了部分實際應用問題。
一． 知識點
第一章.集合論
集合論或集論是研究集合（由一堆抽象物件構成的整體）的數學理論，包含集合、元素和成員關系等最基本數學概念。在大多數現代數學的公式化中，集合論提供了要如何描述數學物件的語言。
本章主要介紹集合的基本概念、運算及冪集合和笛卡爾乘積。這章是本書的基礎部分，要學好離散數學就必須很好的掌握集合的內容。集合論的概念和方法已經滲透到所有的數學分支，因而各數學分支的完整體系，都是在所取集合上。
第二章．關系
關系在我們日常生活中經常會遇到關系這一概念。但在數學中關系表示集合中元素間的聯系。本章主要學習關系的基本概念、關系的性質、閉包運算、次序關系、等價關系，本章學習的重點：關系的性質、閉包運算、次序關系。
關系這一章是集合論這一章的延伸，對集合論的理解程度對學習關系這一章是非常有影響的。而關系又是學習下一章代數系統(tǒng)必不可少的，所以本章是非常重要的章節(jié)。
第三章．代數系統(tǒng)
代數結構也叫做抽象代數，主要研究抽象的代數系統(tǒng)。抽象代數研究的中
心問題就是一種很重要的數學結構--代數系統(tǒng)：半群、群等等。
本章主要學習了運算與半群、群。學習本章需要學會判斷是否是代數系統(tǒng)、群和半群，以及判斷代數系統(tǒng)具有哪些運算規(guī)律，如：結合、交換律等及單位元、逆元。這些都在我們計算機編碼中體現出重要的作用。
第四章．圖論
圖論〔Graph Theory〕起源于著名的柯尼斯堡七橋問題，以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構成的圖形，這種圖形通常用來描述某些事物之間的某種特定關系，用點代表事物，用連接兩點的線表示相應兩個事物間具有這種關系。
本章主要學習圖的基本概念、路徑與回路、圖的矩陣表示、平面圖和二部圖、以及樹。學習的重點：圖的矩陣表示、平面圖和二部圖、以及樹。
第五章．數理邏輯
數理邏輯又稱符號邏輯、理論邏輯。它既是數學的一個分支，也是邏輯學的一個分支。是用數學方法研究邏輯或形式邏輯。數理邏輯是數學基礎的一個不可缺少的組成部分。雖然名稱中有邏輯兩字，但并不屬于單純邏輯學范疇。數理邏輯與計算機科學有著密切的關系，它已成為計算機科學的基礎理論。
本章學習的重點：命題及聯結詞、命題公式及公式的等值和蘊含關系、對偶與范式、命題演算的推理規(guī)則、謂詞邏輯簡介。
二．學習情況
離散數學作為一門必修課，其地位是非常重要的。學習好這門課對于我們也是頗有益處。而且離散數學還是一門有很深內涵的學科。
集合論是本書的這一章節(jié)，我們在以前已經學習過集合，為什么現在還要學習呢，這就足見集合在離散數學這門課程中的重要，把集合的知識作為一個基礎的知識點，來作鋪墊。所以說要想學習好離散數學就必須先將集合的知識掌握好。
關系是集合知識點的延伸，關系是相對于集合而言的。關系也是一個重要的知識點，對后續(xù)知識的學習也有重要的作用。后面的代數系統(tǒng)就必須依賴關系才存在的。如果一個系統(tǒng)里不存在關系，那么這個系統(tǒng)也是不存在的。系統(tǒng)里必然存在某種關系，這才使系統(tǒng)存在有意義。
代數系統(tǒng)的學習是對前面的集合論與關系的以個總結。學習了集合論與關系有什么用，在這一章節(jié)我們就可以看出來。通過學習這一章，對前面兩章有了更深的理解，也對前面所學知識有了一個總結。但同時本章也是本書中比較難以了理解的章節(jié)，在本章的學習中遇到一些問題，但是在同學的幫助下都一一解決了。
圖論的學習對于我們計算機專業(yè)的學生來說是非常的重要的，因為它與我們
計算機專業(yè)的關系最密切。在學習中，圖不再是我們以前接觸的圖，而是學習的事如何在點與點之間連結的問題。這對于發(fā)散我們的思維有很大的幫助。
數理邏輯是本書最重要的章節(jié)，它是培養(yǎng)我們的抽象思維，讓我們能在其他學科能夠運用一定的思維方式來解決問題。對于計算機專業(yè)來說，數理邏輯提高了計算機的工作效率。數理邏輯在計算機專業(yè)方面起到了重要的作用。
三．學習體會
學習了離散數學這門課程，對于一個愛好數學的人來說，我是非常受益的。同時，離散數學作為一門與計算機學科相關的專業(yè)基礎課，對我學專業(yè)知識也有很大的幫助。
學習離散數學，可以培養(yǎng)我們的邏輯思維方式，對于我們學習計算機方向的學生來說是非常有用的。尤其是在計算機編程方面對邏輯思維就有一定的要求。離散數學這門課程，是一門比較難學的課程，它有太多的概念、定義，需要我們有很好的記憶力，但是要完全記住這么多的概念、定義是非常困難的。所以說我們在有好的記憶力之外，還要運用理解記憶的方法來解決，這樣我們就不必花費過多的時間和精力去記憶這么多的概念和定義了。離散數學作為一門理科學科，在我看來最好的學習方法就是多動手、多做題，在做題得過程中，慢慢積累做題得經驗，同時也可以對概念和定義有一個更深層次的理解。
學習各個學科都有其各自的學習方法與思維方式，只有運用對了學習方法才能更好的學習這門課程。學習一門課程都是為了解決實際問題，學習離散數學也不例外。學通了一門課程才能在解決問題的時候不會走彎路。
上面說到了離散數學是一門比較難學的課程，在學習的過程中，也肯定會遇到許多的問題，比如在第三章學習的代數系統(tǒng)中的半群與運算，關于單位元與逆元素這兩個知識點遇到一些問題。但是通過反復的理解概念及做練習題和與同學交流，最后還是解決了這些問題。當解決問題的時候心中有一種成就感。
學習離散數學的過程中，也有許多的樂趣。但在輕松學習的過程中，還得從中學到東西，學到道理。我在學習這門課程之后，對我的專業(yè)知識方面有了很大的幫助，讓我的思維有了進一步的發(fā)散，使我在其他的學科中受益匪淺。
點擊咨詢 