⑴ 離散數學基本知識
總結 離散數學知識點 命題邏輯
→，前鍵為真，後鍵為假才為假；<—>，相同為真，不同為假；
主析取範式：極小項(m)之和；主合取範式：極大項(M)之積；
求極小項時，命題變元的肯定為1，否定為0，求極大項時相反；
求極大極小項時，每個變元或變元的否定只能出現一次，求極小項時變元不夠合取真，求極大項時變元不夠析取假；
求範式時，為保證編碼不錯，命題變元最好按P,Q,R的順序依次寫；
真值表中值為1的項為極小項，值為0的項為極大項；
n個變元共有個極小項或極大項，這為(0~-1)剛好為化簡完後的主析取加主合取；
永真式沒有主合取範式，永假式沒有主析取範式；
推證蘊含式的方法(=>)：真值表法；分析法(假定前鍵為真推出後鍵為真，假定前鍵為假推出後鍵也為假)
10.命題邏輯的推理演算方法：P規則，T規則 ①真值表法；②直接證法；③歸謬法；④附加前提法； 謂詞邏輯
一元謂詞：謂詞只有一個個體，一元謂詞描述命題的性質； 多元謂詞：謂詞有n個個體，多元謂詞描述個體之間的關系；
全稱量詞用蘊含→，存在量詞用合取^;
既有存在又有全稱量詞時，先消存在量詞，再消全稱量詞； 集合
N，表示自然數集，1,2,3……，不包括0；
基：集合A中不同元素的個數，|A|；
冪集：給定集合A，以集合A的所有子集為元素組成的集合，P(A)；
若集合A有n個元素，冪集P(A)有個元素，|P(A)|==；
集合的分劃：(等價關系) ①每一個分劃都是由集合A的幾個子集構成的集合； ②這幾個子集相交為空，相並為全(A)；
集合的分劃與覆蓋的比較： 分劃：每個元素均應出現且僅出現一次在子集中； 覆蓋：只要求每個元素都出現，沒有要求只出現一次； 關系
若集合A有m個元素，集合B有n個元素，則笛卡爾A×B的基數為mn，A到B上可以定義種不同的關系；
若集合A有n個元素，則|A×A|=，A上有個不同的關系；
⑵ 離散數學 第二章 集合
一個 集合 是一些對象的整體
序列 和集合的不同之處是要考慮次序數字系統包括眾所周知的十進制，二進制等等
關系 是序偶的集合
函數 是關系的一個特例
一個集合是一些對象的整體
可以用枚舉法描述它:A={1,2,3,4}
也可以列出其元素的性質來描述:B={x│x是正偶數}
如果X是一個有限集合，令| X |=X中元素的個數，
沒有元素的集合稱為空集(或零集)用符號∅表示,∅={}，
兩個集合X和Y有相同的元素,說兩個集合相等，記為X=Y。
子集
設 X 和 Y 是集合。如果X的所有元素都是Y的元素，我們說X是Y的子集,寫為X⊆Y。
真子集
如X是Y的子集但X不等於Y,則X是Y的一個真子集。記為：X⊊Y
空集是任何集合的子集。
集合X的所有子集的集合,稱為X的冪集，用P(×)表示。
並集、交集、差集
並集XUY={x|x∈X or y ∈Y}
交集X∩Y= {x|x∈X and y∈ Y}
差集X-Y= {x|x∈X or x ∉ Y}
不相交 X∩Y=∅；
U：全集 X：子集
則U-X為X的補集
一個由集合X的非空子集的整體組成的S，如X的每個元素都只屬於S的某一個元素，S就稱為X的一個劃分。
笛卡爾積
—個由兩個元素組成的有序對(或序偶)，寫為(a,b)
(a,b)=(c,d)當且僅當a=c,b=d. X,Y集合，X×Y稱為X和Y的笛卡兒積
一個序列(或有序組)是一個表,要計及其元素出現的次序。
如果s是一個序列，一般的，s.表示序列的第n項。我們把n稱為序列的下標。
序列3,5,5,7,8,8,13是增序列。對於所有的n, S n >S n+1 ,則稱S n 為增序列。
對於n=m,m+1,..,令{S n }是一個序列，且令n1，n2,...是一個增序列，值在{m,m+1,..}中,滿足n k <n k+1 ，稱序列{S nk }是{S n }的一個子序列
X 集合
X* X上所有串的集合
α串,| α |串的長度。
如果α和β是兩個串，由α後面跟著β所組成的串α β ,稱為α和β的連接。
①比特bit ②二進制系統,16進制系統,8進制系統 ③系統的基數
這個就不多闡述了，計組中已經學過了！
關系可以想成一張表，其中列出了一些元素和其他元素之間的關系。
X到Y的關系R,是笛卡兒積X*Y的一個子集。如果(x, y)∈R，我們寫為xRy且說x和y有關。當X=Y，我們稱R是X上的(二元)關系。
定義 ：
令S是集合X的一個劃分。 定義xRy:
對於S的某些集合干,x和y都屬於T。則R是自反，對稱和傳遞的。
X上的一個自反的，對稱的和傳遞的關系稱為X上的一個等價關系。
令R是集合×上的一個等價關系。對於每個a∈X，
令[a]={x∈X]xRa};則s={[a]la∈X}是X的一個劃分。
令R是集合x上的一個等價關系集合[a]，稱為由關系R確定的x的等價類。
令R表示一個有限集合x上的等價關系。如每個等價類有r個元素,則共有|X|/r個等價類。
一個表示從X到Y的關系的方法是使用矩陣。如果xRy，則×行y列的元素之值為1,否則，其值為0。這即是關系矩陣。
定理
R₁的關系(X到Y)矩陣A₁，R₂的關系(到Z)矩陣A₂。
R₁○R₂的關系矩陣:
在矩陣的積A₁A₂中，把非0項用1代替而得的矩陣。
函數是特殊的關系。
R的定義域=
{x∈X│|存在y ∈ Y,(×,y) ∈R}f 關系，f函數，f的定義域=X，且.(x,y')在f 中，y=y'。
⑶ 離散數學
集合論
世界上各門學科與各個領域的研究與應用中,都有特定的研究的對象與目標。這些研究對象與目標呈群體形式出現,為研究它的一般性規則與特點,就出現了集合論。
集合論是一門最基礎的學科,它對人類社會中的所有學科具有指導性作用。
集合論的基本內容包括三個方面,它們是:
集合論基礎。
關系:關系是建立在集合論基礎上的一種特殊集合,它研究客觀世界中事物間關聯的規則。
函數:函數是一種特殊的規范化的關系。
集合之間的關系：相離，相交，相等。
集合概念的基本性質：
1.集合元素的確定性
2.集合元素的相異性:集合中每個元素均是不相同的。如有S={a,b},則a,b必不相同的。
3.集合元素的不重復性:集合中不出現有相重復的元素,如{a,b,b,c}與{a,b,c}是一樣的。
4.集合元素的無序性:集合中元素與其排列無關。如{a,b,c}與{ b,a,c}及{ c,a,b }均是一樣的。
5.集合與元素的相異性:集合與元素是兩個不同概念,集合不等同於元素。
定義三個最基本的運算:並運算、交運算以及補。
給出三個運算的21個規則:
1.交換律:
A∪B=B∪A
A∩B=B∩A
2.結合律:
A∪(B∪C)=(A∪B)∪C
A∩(B∩C)=(A∩B)∩C
3.分配律:
A∪(B∩C)=(A∪B)∩(A∪C)
A∩(B∪C)=(A∩B)∪(A∩C)
4.等幕律:
A∪A=A
A∩A=A
5.雙否定律:
~(~A)=A
6.互補律:
A∪~A=E
A∩~A=空集
~E=空集
~空集=E
7.同一律:
A∩E=A
A∪空=A
A∩空=空
A∪E=E
8.吸收律:
A∪(A∩B)=A
(1-18)
A∩(A∪B)=A
(1-19)
9.德.摩根(De Morgan)律:
~(A∪B)=~A∩~B
~(A∩B)=~A∪~B
集合冪運算:由集合S的所有子集(包括空集及S自身)所組成元素的運算稱S冪運算,可記為p(S),也可記為2 S ,而其所得到的集合S』則稱為S的冪集,即:p(S)= S』。
序偶:兩個按一定次序排列的元素a與b組成一個有序序列,稱為序偶,並可記為:(a,b),其中a與b分別可稱為(a,b)的第一分量與第二分量。
笛卡爾乘:集合A與B中將A中元素作為第一分量,B中元素作為第二分量構作的所有序偶所形成序偶集的過程,稱笛卡爾乘。可記為A×B。其所形成的結果集C是一個序偶集,叫A與B的笛卡爾乘積,也可簡稱笛卡爾積。可表示如下:C=A×B={(a,b)| a屬於A,b屬於B}。
數理邏輯
數理邏輯是用數學方法(即形式化方法)研究形式邏輯演繹推理規則的科學,是一門研究演繹推理規則的數學。
思維形式化：學習數理邏輯首先要學會將一個形式邏輯問題轉換成命題邏輯或謂詞邏輯中的公式,即思維的形式化。在思維形式化中用若干基本形式化符號:
(1)個體常量:a,b,c,…;
(2)個體變數:x,y,z,…;
(3)函數符:f,g,h,…;
(4)謂詞符:P,Q,R,…;
(5)聯結詞:,∧,∨,,;
(6)量詞符:,;
(7)括弧:(,)。
原子公式：
設P是n元謂詞符,t 1 ,t 2 ,…,t n 為項,則P(t 1 ,t 2 ,…,t n )是原子公式。
命題公式：
(1)命題是公式;
(2)如果P是公式則(非P)是公式;
( 3 ) 如 果 P , Q 是 公 式 則 ( P∨Q ) ,
(P∧Q),(P->Q)及(P<->Q)是公式;
(4)公式由且僅由有限次應用(1)(2)(3)而得。
謂詞邏輯公式:
(1)原子公式是公式;
(2)如A,B是公式,則(非A),(A∨B),
(A∧B),(A->B)及(A<->B)是公式;
(3)如A是公式,x是個體變元,則(任意xA),(存在xA)為公式;
(4)公式由且僅由有限次使用(1)-(3)而得。
推理形式化
(1)初級形式化推理
包括等式推理與蘊含推理,由兩部分組成:
推理規則
推理過程
應用命題邏輯、謂詞邏輯中的基本等式、基本蘊含式與相應的推理規則
圖論
圖論用「結點」表示事物,用「邊」表示事物間的聯系,並用「結點」與「邊」所構成的圖研究客觀事物。
為便於計算,建立了圖的矩陣表示。這樣可以將圖論研究與計算相結合。
圖的形式很多,重點對樹進行研究。
圖論應掌握的:
1、圖論的基本概念
2、基本定理
3、圖的矩陣運算
4、樹
圖論中的基本概念
1、圖的概念
2、有向圖與無向圖
3、幾種特殊的圖(零圖、平凡圖、完全圖、補圖、簡單圖與多重圖、有權圖、同構圖)
4、通路、迴路(簡單、基本)
5、圖的連通性(可達性、連通圖、歐拉、哈密爾頓)
圖論中的的基本定理
1、結點與邊的關系
2、基本通路(迴路)長度的定理:(n,m)圖基本通路(迴路)長度小於等於n-1(n)
3、歐拉圖、歐拉通路
4、哈密爾頓圖、哈密爾頓通路
圖的矩陣計算
1、圖的鄰接矩陣
2、通路計算
3、連通性計算
樹
1、樹的定義
2、樹的性質
3、外向樹與內向樹
4、二元樹與多元樹
5、生成樹
6、生成樹尋找演算法