集合論
世界上各門學(xué)科與各個(gè)領(lǐng)域的研究與應(yīng)用中,都有特定的研究的對象與目標(biāo)。這些研究對象與目標(biāo)呈群體形式出現(xiàn),為研究它的一般性規(guī)則與特點(diǎn),就出現(xiàn)了集合論。
集合論是一門最基礎(chǔ)的學(xué)科,它對人類社會(huì)中的所有學(xué)科具有指導(dǎo)性作用。
集合論的基本內(nèi)容包括三個(gè)方面,它們是:
集合論基礎(chǔ)檐迟。
關(guān)系:關(guān)系是建立在集合論基礎(chǔ)上的一種特殊集合,它研究客觀世界中事物間關(guān)聯(lián)的規(guī)則垫言。
函數(shù):函數(shù)是一種特殊的規(guī)范化的關(guān)系。
集合之間的關(guān)系：相離垢啼，相交，相等张肾。
集合概念的基本性質(zhì)：
1.集合元素的確定性
2.集合元素的相異性:集合中每個(gè)元素均是不相同的芭析。如有S={a,b},則a,b必不相同的。
3.集合元素的不重復(fù)性:集合中不出現(xiàn)有相重復(fù)的元素,如{a,b,b,c}與{a,b,c}是一樣的吞瞪。
4.集合元素的無序性:集合中元素與其排列無關(guān)馁启。如{a,b,c}與{ b,a,c}及{ c,a,b }均是一樣的。
5.集合與元素的相異性:集合與元素是兩個(gè)不同概念,集合不等同于元素芍秆。
定義三個(gè)最基本的運(yùn)算:并運(yùn)算惯疙、交運(yùn)算以及補(bǔ)。
給出三個(gè)運(yùn)算的21個(gè)規(guī)則:
1.交換律:
A∪B=B∪A
A∩B=B∩A
2.結(jié)合律:
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.互補(bǔ)律:
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
集合冪運(yùn)算:由集合S的所有子集(包括空集及S自身)所組成元素的運(yùn)算稱S冪運(yùn)算,可記為p(S),也可記為2 S ,而其所得到的集合S’則稱為S的冪集,即:p(S)= S’妖啥。
序偶:兩個(gè)按一定次序排列的元素a與b組成一個(gè)有序序列,稱為序偶,并可記為:(a,b),其中a與b分別可稱為(a,b)的第一分量與第二分量霉颠。
笛卡爾乘:集合A與B中將A中元素作為第一分量,B中元素作為第二分量構(gòu)作的所有序偶所形成序偶集的過程,稱笛卡爾乘〖Ｋǎ可記為A×B掉分。其所形成的結(jié)果集C是一個(gè)序偶集,叫A與B的笛卡爾乘積,也可簡稱笛卡爾積】艘粒可表示如下:C=A×B={(a,b)| a屬于A,b屬于B}酥郭。
數(shù)理邏輯
數(shù)理邏輯是用數(shù)學(xué)方法(即形式化方法)研究形式邏輯演繹推理規(guī)則的科學(xué),是一門研究演繹推理規(guī)則的數(shù)學(xué)。
思維形式化：學(xué)習(xí)數(shù)理邏輯首先要學(xué)會(huì)將一個(gè)形式邏輯問題轉(zhuǎn)換成命題邏輯或謂詞邏輯中的公式,即思維的形式化愿吹。在思維形式化中用若干基本形式化符號:
(1)個(gè)體常量:a,b,c,…;
(2)個(gè)體變量:x,y,z,…;
(3)函數(shù)符:f,g,h,…;
(4)謂詞符:P,Q,R,…;
(5)聯(lián)結(jié)詞:?,∧,∨,?,?;
(6)量詞符:?,?;
(7)括號:(,)不从。
原子公式：
設(shè)P是n元謂詞符,t 1 ,t 2 ,…,t n 為項(xiàng),則P(t 1 ,t 2 ,…,t n )是原子公式。
命題公式：
(1)命題是公式;
(2)如果P是公式則(非P)是公式;
( 3 ) 如 果 P , Q 是 公 式 則 ( P∨Q ) ,
(P∧Q),(P->Q)及(P<->Q)是公式;
(4)公式由且僅由有限次應(yīng)用(1)(2)(3)而得犁跪。
謂詞邏輯公式:
(1)原子公式是公式;
(2)如A,B是公式,則(非A),(A∨B),
(A∧B),(A->B)及(A<->B)是公式;
(3)如A是公式,x是個(gè)體變元,則(??任意xA),(存在?xA)為公式;
(4)公式由且僅由有限次使用(1)-(3)而得椿息。
推理形式化
(1)初級形式化推理
包括等式推理與蘊(yùn)含推理,由兩部分組成:
推理規(guī)則
推理過程
應(yīng)用命題邏輯歹袁、謂詞邏輯中的基本等式、基本蘊(yùn)含式與相應(yīng)的推理規(guī)則
圖論
圖論用“結(jié)點(diǎn)”表示事物,用“邊”表示事物間的聯(lián)系,并用“結(jié)點(diǎn)”與“邊”所構(gòu)成的圖研究客觀事物寝优。
為便于計(jì)算,建立了圖的矩陣表示条舔。這樣可以將圖論研究與計(jì)算相結(jié)合。
圖的形式很多,重點(diǎn)對樹進(jìn)行研究乏矾。
圖論應(yīng)掌握的:
1孟抗、圖論的基本概念
2、基本定理
3钻心、圖的矩陣運(yùn)算
4凄硼、樹
圖論中的基本概念
1、圖的概念
2捷沸、有向圖與無向圖
3摊沉、幾種特殊的圖(零圖、平凡圖痒给、完全圖说墨、補(bǔ)圖、簡單圖與多重圖苍柏、有權(quán)圖婉刀、同構(gòu)圖)
4、通路序仙、回路(簡單、基本)
5鲁豪、圖的連通性(可達(dá)性潘悼、連通圖、歐拉爬橡、哈密爾頓)
圖論中的的基本定理
1治唤、結(jié)點(diǎn)與邊的關(guān)系
2、基本通路(回路)長度的定理:(n,m)圖基本通路(回路)長度小于等于n-1(n)
3糙申、歐拉圖宾添、歐拉通路
4、哈密爾頓圖柜裸、哈密爾頓通路
圖的矩陣計(jì)算
1缕陕、圖的鄰接矩陣
2、通路計(jì)算
3疙挺、連通性計(jì)算
樹
1扛邑、樹的定義
2、樹的性質(zhì)
3铐然、外向樹與內(nèi)向樹
4蔬崩、二元樹與多元樹
5恶座、生成樹
6、生成樹尋找算法
