掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
闖進數學世界――探秘歷史名題
-
>
中醫(yī)基礎理論
-
>
當代中國政府與政治(新編21世紀公共管理系列教材)
-
>
高校軍事課教程
-
>
思想道德與法治(2021年版)
-
>
毛澤東思想和中國特色社會主義理論體系概論(2021年版)
-
>
中醫(yī)內科學·全國中醫(yī)藥行業(yè)高等教育“十四五”規(guī)劃教材
離散數學/吳秀蘭 版權信息
- ISBN：9787302514541
- 條形碼：9787302514541 ; 978-7-302-51454-1
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>>
離散數學/吳秀蘭 內容簡介
本書共分8章，分別為命題邏輯、一階邏輯、集合、二元關系和函數、代數系統(tǒng)、格與布爾代數、圖論和樹.在結構體系上，本書首先介紹數理邏輯及集合相關內容；其次介紹關系及代數系統(tǒng)；很后介紹圖論與樹的相關知識及應用.每一章的內容介紹之后都選配了適量的習題，做到少而精，注意突出重點.便于學生理解和掌握抽象理論和方法. 本書不僅可作為高等院校數學、計算機科學與技術及相關專業(yè)的教材，也可作為從事計算機工作的相關人員的參考書.
離散數學/吳秀蘭 目錄
1.1命題與聯結詞1
1.1.1命題與真值1
1.1.2命題聯結詞2
1.2命題公式及其解釋6
1.2.1命題公式6
1.2.2命題的符號化7
1.2.3公式的賦值及真值表8
1.3命題公式的等值演算10
1.3.1命題公式的等值式10
1.3.2代入規(guī)則與替換規(guī)則11
1.4范式13
1.4.1合取范式與析取范式13
1.4.2主范式15
1.5聯結詞完備集18
1.6命題演算的推理理論20
1.7自然推理系統(tǒng)N中的形式證明22
習題127
第2章一階邏輯30
2.1一階邏輯基本概念30
2.2一階邏輯公式及解釋33
2.3一階邏輯等值式與置換規(guī)則36
2.4一階邏輯前束范式39
2.5一階邏輯的推理理論40
習題246
第3章集合49
3.1集合的基本概念49
3.2集合的基本運算50[3]目錄[3][1]目錄[3]3.3集合中元素的計數51
習題353
第4章二元關系和函數54
4.1集合的笛卡兒積與二元關系54
4.2關系的運算57
4.3關系的性質63
4.4關系的閉包68
4.5等價關系與偏序關系74
4.6函數的定義和性質79
4.7函數的復合與反函數82
習題485
第5章代數系統(tǒng)88
5.1二元運算及其性質88
5.2代數系統(tǒng)94
5.3代數系統(tǒng)的同態(tài)與同構96
習題598
第6章格與布爾代數100
6.1格的定義與性質100
6.2分配格與有補格105
6.3布爾代數111
習題6114
第7章圖論116
7.1圖的基本概念116
7.2通路、回路和圖的連通性123
7.3圖的矩陣表示128
7.4歐拉圖131
7.5哈密頓圖135
7.6應用舉例139
習題7142
第8章樹144
8.1無向樹及生成樹144
8.2根樹及其應用148
習題8153
1.1.1命題與真值1
1.1.2命題聯結詞2
1.2命題公式及其解釋6
1.2.1命題公式6
1.2.2命題的符號化7
1.2.3公式的賦值及真值表8
1.3命題公式的等值演算10
1.3.1命題公式的等值式10
1.3.2代入規(guī)則與替換規(guī)則11
1.4范式13
1.4.1合取范式與析取范式13
1.4.2主范式15
1.5聯結詞完備集18
1.6命題演算的推理理論20
1.7自然推理系統(tǒng)N中的形式證明22
習題127
第2章一階邏輯30
2.1一階邏輯基本概念30
2.2一階邏輯公式及解釋33
2.3一階邏輯等值式與置換規(guī)則36
2.4一階邏輯前束范式39
2.5一階邏輯的推理理論40
習題246
第3章集合49
3.1集合的基本概念49
3.2集合的基本運算50[3]目錄[3][1]目錄[3]3.3集合中元素的計數51
習題353
第4章二元關系和函數54
4.1集合的笛卡兒積與二元關系54
4.2關系的運算57
4.3關系的性質63
4.4關系的閉包68
4.5等價關系與偏序關系74
4.6函數的定義和性質79
4.7函數的復合與反函數82
習題485
第5章代數系統(tǒng)88
5.1二元運算及其性質88
5.2代數系統(tǒng)94
5.3代數系統(tǒng)的同態(tài)與同構96
習題598
第6章格與布爾代數100
6.1格的定義與性質100
6.2分配格與有補格105
6.3布爾代數111
習題6114
第7章圖論116
7.1圖的基本概念116
7.2通路、回路和圖的連通性123
7.3圖的矩陣表示128
7.4歐拉圖131
7.5哈密頓圖135
7.6應用舉例139
習題7142
第8章樹144
8.1無向樹及生成樹144
8.2根樹及其應用148
習題8153
展開全部
離散數學/吳秀蘭 節(jié)選
第3章集合集合論是現代數學的基礎，它的起源可以追溯到16世紀末期.為了追尋微積分的堅實的基礎，人們只進行了有關數集的研究.直到1876—1883年，康托發(fā)表了一系列有關集合論的文章，對任意元素的集合進行了深入的探討，提出了關于基數、序數和良序集等理論，奠定了集合論的深厚基礎.但是，隨著集合論的發(fā)展，以及它與數學哲學密切聯系所作的討論，在1900年前后出現了各種悖論，使集合論的發(fā)展一度陷入僵滯的局面.1904—1908年，策墨羅列出了**個集合論的公理系統(tǒng)，他的公理，使數學哲學中產生的一些矛盾基本上得到統(tǒng)一，在此基礎上逐步形成了公理化集合論和抽象集合論，使該學科成為數學中發(fā)展*為迅速的一個分支.本章介紹集合的一些基本知識. 3.1集合的基本概念 在研究問題時，通常把具有某種性質的事物作為一個整體來研究，這個整體稱為集合，其中的每個事物稱為集合的元素.常用英文大寫字母A,B,C等表示集合，以英文小寫字母a,b,c等表示集合的元素.a∈A表示a是A的元素，aA表示a不是A的元素. 定義3.1.1一個集合若由有限個元素組成，則稱為有限集，否則稱為無限集.特別地，元素個數為零的集合稱為空集，記作“”.用符號“|A|”表示有限集A的元素個數. 常見的集合表示法分為枚舉法和特性描述法.枚舉法是將集合的元素一一列出.如集合A由元素a,b,c,d組成，可記為A={a,b,c,d}.特性描述法是用集合的元素所具有的共同性質來刻畫集合.如A={x|x是正偶數}.一般集合可用A={x|P(x)}表示，其中P(x)表示事物x滿足性質P，集合A由滿足性質P的所有元素組成. 注（1） 集合的元素具有確定性，即元素a∈A或aA二者必居且僅居其一. （2） 集合的確定不應引起悖論.如A={x|xA}不能定義成為一個集合. （3） 集合中的元素具有無序性.如{a,b}={b,a}. 定義3.1.2集合間的關系有如下定義： （1） 設A，B為集合，AB表示A是B的子集，即如果a∈A，則a∈B. （2） 設A，B為集合，AB表示A是B的真子集，即AB且存在b∈B使bA. （3） 設A，B為集合，A=B表示AB且BA，即A和B元素相同，稱作A與B相等. （4） 稱P(X)={A|AX}為X的冪集，即X的所有子集組成的集合，有時也記為2X. 根據討論問題的需要，常設一個充分大的集合為全集，也稱為基本集，所討論的集合均為這個集合的子集.[3]第3章集合[3][1]3.2集合的基本運算[3]注（1） X含有n個元素，則X有2n個子集，即P(X)含有2n個元素. （2） 空集是任一集合的子集. （3） 包含關系滿足以下性質： ① AA；（自反性） ② 若AB,BA，則A=B； （反對稱性） ③ 若AB,BC，則AC. （傳遞性） 例3.1.1設A={a,b},求P(A). 解P(A)={,{a},,{a,b}}. 注2={}，要區(qū)分與{}，其中表示空集，其中沒有任何元素，而{}則表示以空集為元素的一個集族，即∈{}. 一般用N,Z,Q,R,C分別表示自然數集、整數集、有理數集、實數集、復數集，它們滿足NZQRC. 3.2集合的基本運算 集合有并、交、差、補、對稱差等運算. 定義3.2.1設A,B為集合，A與B的并集記作A∪B，其定義式為 A∪B={x|x∈A或x∈B}. 定義3.2.2設A,B為集合，A與B的交集記作A∩B，其定義式為 A∩B={x|x∈A且x∈B}. 定義3.2.3設A,B為集合，A與B的差集記作A－B或A\\B，其定義式為 A－B={x|x∈A且xB}. 定義3.2.4設X為基本集，集合A的補集記作Ac或，其定義式為 Ac=X－A={x|xA且x∈X}. 定義3.2.5設A，B為集合，A與B的對稱差記作AB，其定義式為 AB=(A－B)∪(B－A). 對稱差也稱為布爾和. 以上定義的并和交運算稱為初級并和初級交.下面考慮推廣的并和交運算，即廣義并和廣義交. 定義3.2.6設A為集合，A的元素的元素構成的集合稱作A的廣義并，記作∪A，符號化表示為 ∪A=x|zz∈A∧x∈z. 例3.2.1設A=a,b,c,a,c,d,a,e,f，B=a，C=a,c,d.則 ∪A={a,b,c,d,e,f}，∪B=a， ∪C=a∪c,d，∪= 根據廣義并定義，我們有，若A=A1,A2,…,An，則∪A=A1∪A2∪…∪An. 定義3.2.7設A為集合，A的元素的元素構成的集合稱作A的廣義交,記作∩A，符號化表示為 ∩A=x|zz∈A→x∈z. 考慮例3.2.1中的集合，有 ∩A=a,∩B=a,∩C=a∩c,d. 但空集不可以進行廣義交，因為∩不是集合，在集合論中是沒有意義的.和廣義并類似，若A=A1,A2,…,An，則∩A=A1∩A2∩…∩An. 例3.2.2設A={{a},a,b},計算∪∪A,∩∩A和∩∪A∪∪∪A－∪∩A. 解∪A={a,b},∩A=a,∪∪A=a∪b, ∩∪A∪∪∪A－∪∩A=a∩b∪a∪b－a =a∩b∪b－a =b. 所以∪∪A=a∪b，∩∩A=a, ∩∪A∪∪∪A－∪∩A=b. [3][1]3.3集合中元素的計數[3]3.3集合中元素的計數 集合的運算可以用文氏圖表示.文氏圖的構造方法如下： E是全集，圓A,B的內部為集合A,B，如果沒有關于集合不交的說明，任何兩圓應彼此相交.圖中的陰影區(qū)域表示集合A,B在相應運算下組成的集合.具體見圖3.3.1. 圖3.3.1 X為集合，A,B,C為X的子集，∪,∩,c為集合的并、交、補運算，有以下性質： （1） A∪B=B∪A,A∩B=B∩A；（交換律） （2） (A∪B)∪C=A∪(B∪C), (A∩B)∩C=A∩(B∩C)； （結合律） （3） A∪=A,A∩X=A； （同一律） （4） A∪Ac=X,A∩Ac=； （互補律） （5） A∪(A∩B)=A,A∩(A∪B)=A； （吸收律） （6） A∪(B∩C)=(A∪B)∩(A∪C)， A∩(B∪C)=(A∩B)∪(A∩C)； （分配律） （7） A∪A=A,A∩A=A； （冪等律） （8） A∪X=X,A∩=； （零律） （9） (Ac)c=A； （雙重否定律） （10） A∪Bc=Ac∩Bc,(A∩B)c=Ac∪Bc. （德摩根律） 由以上性質知，在任何集合運算的公式中，將∪與∩互換，公式仍然成立.這就是集合論的對偶原則. 定理3.3.1（包含排斥原理）設S為有限集合，P1,P2,…,Pm是m個性質. S中的任何元素x或者具有性質Pi或者不具有性質Pi(i=1,2,…,m)兩種情況必居其一.令Ai表示具有性質Pi的元素構成的子集，則S中不具有性質P1,P2,…,Pm的元素個數為 |A1∩A2∩…∩Am|=|S|－∑mi=1|Ai|+∑1≤i－∑1≤i+…+(－1)m|A1∩A2∩…∩Am|. 推論S中至少具有一條性質的元素數為 |A1∪A2∪…∪Am| =∑mi=1|Ai|－∑1≤i－…+(－1)m－1|A1∩A2∩…∩Am|. 當m=2時，有 |A1∪A2|=|A1|+|A2|－|A1∩A2|. 當m=3時，有 |A1∪A2∪A3|=|A1|+|A2|+|A3|－|A1∩A2|－|A1∩A3| －|A2∩A3|+|A1∩A2∩A3|. 一般包含排斥原理又稱為容斥原理. 例3.3.1有120個學生參加考試，這次考試有3道題A,B,C，考試結果如下： 12個學生3道題都做對了，20個學生做對A,B兩道題，16個學生做對A,C兩道題，28個學生做對B,C兩道題，做對A題的有48個學生，做對B題的有56個學生，還有16個學生一道題也沒做對.求做對C題的學生有多少個？ 解設做對A題的學生為P1,做對B題的學生為P2,做對C題的學生為P3,由題意，根據容斥原理可知 |P1∩P2∩P3|=12,|P1∩P2|=20,|P1∩P3|=16,|P2∩P3|=28， |P1|=48,|P2|=56,|P1∪P2∪P3|=16,所以|P1∪P2∪P3|=120－16=104， 而 |P1∪P2∪P3|=|P1|+|P2|+|P3|－|P1∩P2|－|P1∩P3| －|P2∩P3|+|P1∩P2∩P3|， 因此|P3|=52，所以做對了C題的學生有52人. [3][1]習題3[3]習題3 1. 設A,B為集合，試確定下列各式成立的充分必要條件： (直接寫結論就可以) (1) A－B=B; (2) A－B=B－A; (3) A∩B=B∪A; (4) AB=A. 2. 證明(A∪B=A∪C)∧(A∩B=A∩C)B=C. 3. 求下列集合的冪集: (1) A={a,b,c}，則P(A)=; (2) B={1,{2,3}}，則P(B)=; (3) C={}，則P(C)=; (4) D={,{}}，則P(D)=. 4. 設E=1,2,3,4,5,6,A=1,4,B=1,2,5,C=2,4，求下列集合(用枚舉法寫出集合的具體元素): （1） A∩BC； （2） (A∩B)∪CC； （3） (A∩B)C； （4） P(A)∩P(B)； （5） P(A)－P(B). 5. 用枚舉法表示下面的集合： （1） S1=x|x=2∨x=5； （2） S2=x|x∈Z∧3（3） S3=x|x∈R∧x2－1=0∧x>3; （4） S4=〈x,y〉|x,y∈Z∧0≤x≤2∧－1≤y≤0. 6.設A=2,a,3,4,B=,4,a,3,C=1,2,1.求:(1) AB=; (2) P(C)=. 7. 設S={2,a,{3},4}，R={{a},3,4,1},指出下面的寫法哪些是對的，哪些是錯的. （1） {a}∈S;（2） {a}∈R;（3） {a,4{3}}S; （4） {{a},1,3,4}R;（5） S=R;（6） {a}S; （7） {a}R;（8） R;（9） {{a}}R; （10） {}S;（11） ∈R;（12） {{3},4}.第4章二元關系和函數第3章討論了集合及集合的運算，本章研究集合內元素的關系以及集合間元素的關系，這就是關系和函數.關系和函數是很重要的數學概念，它在計算機科學技術中的許多方面有著重要的應用，如數據結構、數據庫、情報檢索、算法分析等.本章主要討論二元關系理論. 4.1集合的笛卡兒積與二元關系 定義4.1.1由兩個元素x和y(允許x=y)按一定順序排列成的二元組，稱為一個有序對或序偶，記作〈x,y〉，其中x是它的**元素，y是它的第二元素. 有序對〈x,y〉具有如下性質： 1. 當x≠y時，〈x,y〉≠〈y,x〉. 2. 〈x1,y1〉=〈x2,y2〉 的充要條件是x1=x2 且 y1=y2. 上述兩條性質是二元集x,y所不具備的.例如，當x≠y時，有x,y=y,x.原因在于集合中的元素是無序的，而有序對中的元素是有序的. 例4.1.1已知〈x+2,3〉=〈3,2x+y〉，求x和y. 解由有序對相等的充要條件，有x+2=3, 2x+y=3.解得x=1，y=1. 定義4.1.2設A，B為兩個集合，所有**元素屬于A,第二元素屬于B的序偶所組成的集合,稱為集合A和集合B的笛卡兒乘積.記作A×B,即 A×B={〈x,y〉|x∈A∧y∈B}. 例4.1.2設A={a,b},B=0,1,C=,試求A×B,B×A,A×A,B×B,C×C,A×B×C和A×B×C. 解A×B=〈a,0〉,〈a,1〉,〈b,0〉,〈b,1〉,B×A=〈0,a〉,〈1,a〉,〈0,b〉,〈1,b〉, A×A=〈a,a〉,〈a,b〉,〈b,b〉,〈b,a〉, B×B=〈0,0〉,〈0,1〉,〈1,0〉,〈1,1〉, C×C=〈,〉, A×B×C=〈〈a,0〉,〉,〈〈a,1〉,〉,〈〈b,0〉,〉,〈〈b,1〉,〉, B×C=〈0,〉,〈1,〉, A×(B×C)={〈a,〈0,〉〉,〈a,〈1,〉〉,〈b,〈0,〉〉,〈b,〈1,〉〉}.[3]第4章二元關系和函數[3][1]4.1集合的笛卡兒積與二元關系[3]如果A=m，B=n，則A×B=mn.從例4.1.2不難看出笛卡兒積具有如下性質: 性質1對任意集合A，根據定義有 A×=，×A=. 性質2一般地說，笛卡兒積元素不滿足交換律，即 A×B≠B×A(當A≠∧B≠∧A≠B時). 性質3笛卡兒積運算不滿足結合律，即 A×B×C≠A×B×C(當A≠∧B≠∧C≠時). 性質4笛卡兒積運算對并和交運算滿足分配律，即 A×(B∪C)=A×B∪A×C， (B∪C)×A=B×A∪C×A， A×(B∩C)=A×B∩A×C， (B∩C)×A=B×A∩C×A. 證明我們只證明**個等式.任取〈x,y〉∈A×B∪C，則有 〈x,y〉∈A×B∪Cx∈A∧y∈B∪C x∈A∧(y∈B∨y∈C) (x∈A∧y∈B)∨(x∈A∧y∈C) 〈x,y〉∈A×B∨〈x,y〉∈A×C 〈x,y〉∈A×B∪A×C, 所以有A×(B∪C)=A×B∪A×C. 類似地可以證明其他情形. 性質5AC∧BDA×BC×D. 采用命題演算的方法，可以證明性質5.該證明留給讀者考慮. 值得注意的是,性質5的逆命題不成立,分以下幾種情況討論: (1) 當A=B=時,顯然有AC且BD成立. (2) 當A≠且B≠時,也有AC且BD成立.具體證明如下: 任取x∈A,由于B≠,則存在y∈B.所以有〈x,y〉∈A×BC×D.由笛卡兒積的定義有x∈C且y∈D. (3) 當A=但B≠時,有AC成立,但不一定有BD成立.例如,取A=,B={1},C={2},D={3}. (4) 當A≠但B=時，有BD成立，不一定有AC成立.例如，A={1}，B=，C={2}，D={3}. 例4.1.3設A=1,2，求PA×A. 解P(A)={,1,{2},{1,2}},P(A)×A={〈,1〉,〈,2〉,〈{1},1〉,〈{1},2〉,〈{2},1〉,〈{2},2〉,〈{1,2},1〉,〈{1,2},2〉}. 例4.1.4設A，B，C，D為任意集合，判斷以下命題是否為真，并說明理由. (1) A×B=A×CB=C; (2) A－B×C=(A－B)×(A－C); (3) A=B∧C=DA×C=B×D; (4) 存在集合A，使得AA×A. 解(1) 不一定為真，當A=,B={1},C={2}時,有A×B==A×C，但是B≠C. (2) 不一定為真，當A=B={2}，C={3}時,有 A－(B×C)=2－〈2,3〉={2}， A－B×(A－C)=×{2}=. (3) 為真. (4) 為真.取集合A=時，有AA×A. 定義4.1.3如果一個集合滿足下列條件之一：
書友推薦
- >
企鵝口袋書系列·偉大的思想20:論自然選擇(英漢雙語)
- >
小考拉的故事-套裝共3冊
- >
我與地壇
- >
月亮與六便士
- >
中國人在烏蘇里邊疆區(qū):歷史與人類學概述
- >
二體千字文
- >
唐代進士錄
- >
朝聞道
本類暢銷
