1. 掌握離散數學中涉及的相關概念。
2. 培養學生的邏輯思維能力和演算法設計的思想。
3. 熟練掌握c/c++語言程式設計的基本方法和各種除錯手段。
4. 熟練掌握包括陣列、鍊錶以及鄰接表或鄰接矩陣等資料結構的建立和運用。
1. 求有限集上給定關係的自反、對稱和傳遞閉包。（有兩種求解方法，只做一種為a，兩種都做為b）
2. 求有限集上等價關係的數目。（有兩種求解方法，只做一種為a，兩種都做為b）
3. 求解商集，輸入集合和等價關係，求相應的商集。（c）
注意：題目型別分為a，b，c三類，其中a為基本題，完成a類題目可達到設計的基本要求，其他均為加分題，並按字母順序分數增加越高。
c或c＋＋語言程式設計環境實現。
關係採用關係矩陣的形式表示會比較容易處理。自反閉包和對稱閉包的求法比較簡單，傳遞閉包有兩種方法求解。一種直接通過定義，另一種稱為warshall演算法。
warshall演算法：
設r的關係矩陣為m
(1)令矩陣a=m
(2)置i=1
(3)對所有的j，若a[j，i]=1，則
對於 k=1，2，…，n，令a[j，k]=a[j，k]+a[i，k]
(4)i=i+l．
(5)若i≤n，則轉到(3)，否則結束。
集合上的等價關係與該集合的劃分之間存在一一對應關係。乙個等價關係對應乙個劃分，乙個劃分也對應乙個等價關係。我們把n個元素的集合劃分成k塊的方法數叫第二類stirling數，表示為s(n,k)。
例如有甲、乙、丙、丁四人，若所有人分成1組，只有所有人在同一組這個方法，因此s(4,1) = 1；若所有人分成4組，只可以人人獨立一組，因此s(4,4) = 1；若分成2組，可以是甲乙一組、丙丁一組，或甲丙一組、乙丁一組，或甲丁一組、乙丙一組，或其中三人同一組另一人獨立一組，即是：
1. ,
2. ,
3. ,
4. ,
5. ,
6. ,
7. ,
因此s(4,2) = 7。
給定s(n,n) = s(n,1) = 1，有遞迴關係s(n,k) = s(n 1,k 1) + ks(n 1,k)
上面的遞推式可以用組合證明：一方面，如果將元素1單獨拿出來劃分成1個集合，那麼方法數是s(n-1,k-1)；另一方面，如果元素1所在的集合不止乙個元素，那麼可以先將剩下的n-1個元素劃分好了以後再選乙個集合把1放進去，方法數是k*s(n-1,k)；有加法原理得證。
第二類stirling數可用遞推和遞迴兩種方法求解。
集合上所有等價類的個數即為k從1到n，所有s(n,k)之和。
商集即等價類構成的集合，要求商集，首先需要判斷輸入的關係是否為等價關係，否則沒有商集。確定集合a=關於r的等價類的演算法如下：
(1) 令a中每乙個元素自成乙個子集，如a1=,a2=,…,an=
(2) 對r中每個二元組< x,y >，判定x和y所屬子集。假設x屬於ai，y屬於aj，若ai<>aj，則將ai併入aj，並置ai為空；或將aj併入ai，並置aj為空。一般將元素少的集合合併到元素多的集合。
(3) a1 ,a2,…,an中所有非空子集構成的集合即為所求商集。
要實現集合的並運算，採用並查集(union-find sets)是一種不錯的方法。並查集是一種樹型的資料結構，多棵樹構成乙個森林，每棵樹構成乙個集合，樹中的每個節點就是該集合的元素，找乙個代表元素作為該樹(集合)的祖先。並查集可用於快速實現處理一些不相交集合（disjoint sets）的並。
一般用途就是用來維護某種等價類。並查集支援以下三種操作：
(1) make_set(x) 把每乙個元素初始化為乙個集合
初始化後每乙個元素的父親節點是它本身，每乙個元素的祖先節點也是它本身。
(2) find_set(x) 查詢乙個元素所在的集合
查詢乙個元素所在的集合，只要找到這個元素所在集合的祖先即可。判斷兩個元素是否屬於同一集合，只要看他們所在集合的祖先是否相同即可。
(3) union(x,y) 合併x,y所在的兩個集合
合併兩個不相交集合操作很簡單：首先設定乙個陣列father[x]，表示x的"父親"的編號。那麼，合併兩個不相交集合的方法就是，找到其中乙個集合的祖先，將另外乙個集合的祖先指向它。
關於並查集的具體操作實現請參考有關資料。
本程式的一大特色就是開發者靈活使用了c語言中的陣列概念來進行開發，用陣列來模擬關係矩陣的運算，通過相應的演算法實現了全部的功能。
在關係元素的提取中，開發者熟練地運用陣列和指標，先將使用者輸入的字元儲存在陣列中，然後利用指標指向輸入的第乙個字元，對它進行判斷。如果是a到z之間的字母，說明是集合中的元素，將其儲存到另乙個陣列中，然後修改指標，使它指向原陣列中的另乙個元素。如果不屬於a到z之間，說明不是集合中的元素，直接修改指標，使它指向原陣列中的另乙個元素。
就這樣依次對使用者輸入的關係表示式進行提取，最後就得到了我們的集合元素。
在提取元素的賦值中，依次將儲存了提取的關係元素陣列中的每兩個元素和集合元素陣列中的元素進行比較，發現匹配的之後，將表徵初始關係矩陣的二維陣列的相應元素賦值為1，其它的賦值為0。這樣就建立了初始關係矩陣。
在求取自反閉包的關係矩陣中，只需將初始關係矩陣主對角線上的所有元素賦值為1即可。
在求取對稱閉包的關係矩陣中，根據「對稱關係的關係矩陣關於主對角線對稱」的原理，將初始關係矩陣中除對角線之外的其他數值進行判斷，若發現值為1的元素，就將此元素關於主對角線對稱的相應元素賦值為1，這樣就實現的了對稱閉包關係矩陣的求取。
在求取對稱閉包的關係矩陣中，有兩種演算法——
1) 直接通過定義演算法
根據「傳遞關係的關係矩陣的特徵——如果aij=1,且ajk=1,則aik=1」的
原理，將初始關係矩陣中的所有元素進行對應的規則判斷，如果滿足條件的話，按照定義將相對應的元素賦值為1，這樣就得到的了對稱閉包關係矩陣。
2) warshall演算法
設r的關係矩陣為m
(1)令矩陣a=m
(2)置i=1
(3)對所有的j，若a[j，i]=1，則
對於 k=1，2，…，n，令a[j，k]=a[j，k]+a[i，k]
(4)i=i+l．
(5)若i≤n，則轉到(3)，否則結束。
所得的矩陣a即為傳遞閉包的關係矩陣。
在實現「求有限集上等價關係的數目」的功能時，有兩種演算法——
1) 遞推演算法
該演算法先將初始矩陣中第一列和主對角線上的元素都賦值為1，然後依次將上一行的兩個元素按照s(n,k) = s(n 1,k 1) + ks(n 1,k)的思路進行相加，結果儲存在相應的單元中，最終所得的矩陣即為滿足輸出條件的矩陣
2) 遞迴演算法
該演算法遵循求等價關係中s(n,k) = s(n 1,k 1) + ks(n 1,k)的原則，利用了c語言中遞迴的思想，在遞迴呼叫子函式的內部，間接地呼叫自身，把問題轉化為規模縮小了的同類問題的子問題，然後遞迴呼叫函式來表示問題的解。
商集即等價類構成的集合，要求商集，首先需要判斷輸入的關係是否為等價關係，否則沒有商集。實現的演算法比較簡單，根據「等價關係是自反的、對稱的和傳遞的」的性質，將求得的自反閉包、對稱閉包以及傳遞閉包的關係矩陣依次和初始關係矩陣進行比較，如果他們完全相同，就說明是等價關係，否則不是。
離散數學實驗報告
南京工程學院 實驗報告 課程名稱離散數學 實驗專案名稱命題邏輯 實驗學生班級 k多 111 實驗學生姓名朱在吉 學號 240111338 同組學生姓名 實驗時間 2012.10.25 實驗地點 實驗成績評定 指導教師簽字年月日 一 實驗目的和要求 真值表是命題邏輯中的乙個十分重要的概念，利用它幾乎可...
離散數學實驗1報告
實驗abc 專業 自動化 班級 學號 姓名 日期 2011年12月05日 1.掌握離散數學中涉及的相關概念。2.培養學生的邏輯思維能力和演算法設計的思想。3.熟練掌握c c 語言程式設計的基本方法和各種除錯手段。4.熟練掌握包括陣列 鍊錶以及鄰接表或鄰接矩陣等資料結構的建立和運用。1.從鍵盤輸入兩個...
離散數學實驗指導書
通常人們對離散數學教學的認識就是概念 定理 公式和解題。但是，離散數學不僅僅是這些，還有實驗。在理論教學過程中，學生的活動只是 智力活動 或更為直接地說是解題活動，教師在上面講離散數學，而學生則每天在課堂上聽課並在紙上做題目。這樣，對多數學生而言，離散數學的發現探索活動沒有能夠真正開展起來。離散數學...