『壹』 離散數學這門課程第四章關系的知識點有哪些
離散數學這門課第四章關系的知識點包含章節導引,第一節關系的概念,第二節關系運算,第三節關系的特殊性質及其閉包,第四節等價關系和劃分,第五節偏序關系,課後鞏固,。
『貳』 離散數學基本知識
總結 離散數學知識點 命題邏輯
→，前鍵為真，後鍵為假才為假；<—>，相同為真，不同為假；
主析取範式：極小項(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上有個不同的關系；
『叄』 離散數學這門課程第三章一階邏輯的知識點有哪些
離散數學這門課第三章一階邏輯的知識點包含章節導引,第一節謂詞和謂詞公式,第二節謂詞公式的等值演算和前束範式,第三節一階邏輯的推理理論,課後鞏固,。
『肆』 求 離散數學（第四版）知識框架
離散數學期末復習要點與重點 第1章 集合及其運算 復習要點 1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和冪集等概念，熟練掌握集合的表示方法．具有確定的，可以區分的若幹事物的全體稱為集合，其中的事物叫元素.．集合的表示方法：列舉法和描述法. 注意：集合的表示中元素不能重復出現，集合中的元素無順序之分． 掌握集合包含(子集)、真子集、集合相等等概念．注意：元素與集合，集合與子集，子集與冪集，�0�2與�0�0(�0�1),空集�0�4與所有集合等的關系.空集�0�4，是惟一的，它是任何集合的子集．集合A的冪集P(A)＝， A的所有子集構成的集合．若�0�5A�0�5＝n，則�0�5P(A)�0�5=2n．2．熟練掌握集合A和B的並A�0�6B，交A�0�5B，補集~A(~A補集總相對於一個全集).差集A－B，對稱差�0�3，A�0�3B＝(A－B)�0�6(B－A)，或A�0�3B＝(A�0�6B)－（A�0�5B）等運算，並會用文氏圖表示．掌握集合運算律(見教材第9～11頁)(運算的性質).3．掌握用集合運算基本規律證明集合恆等式的方法．集合的運算問題：其一是進行集合運算；其二是運算式的化簡；其三是恆等式證明．證明方法有二：(1)要證明A＝B，只需證明A�0�1B，又A�0�8B；(2)通過運算律進行等式推導．重點：集合概念，集合的運算，集合恆等式的證明． 第2章 關系與函數 復習要點1．了解有序對和笛卡兒積的概念，掌握笛卡兒積的運算． 有序對就是有順序二元組，如<x, y>，x, y的位置是確定的，不能隨意放置． 注意：有序對<a，b>�0�1<b,a>，以a, b為元素的集合{a, b}={b, a}；有序對(a, a)有意義，而集合{a, a}是單元素集合，應記作{a}． 集合A，B的笛卡兒積A×B是一個集合，規定A×B＝{<x,y>�0�5x�0�2A,y�0�2B}，是有序對的集合.笛卡兒積也可以多個集合合成，A1×A2×…×An． 2．理解關系的概念：二元關系、空關系、全關系、恆等關系.掌握關系的集合表示、關系矩陣和關系圖，掌握關系的集合運算和求復合關系、逆關系的方法． 二元關系是一個有序對集合，，記作xRy． 關系的表示方法有三種：集合表示法， 關系矩陣：R�0�1A×B，R的矩陣. 關系圖：R是集合上的二元關系，若<ai, bj>�0�2R，由結點ai畫有向弧到bj構成的圖形．空關系�0�4是唯一、是任何關系的子集的關系；全關系；恆等關系，恆等關系的矩陣MI是單位矩陣．關系的集合運算有並、交、補、差和對稱差．復合關系；復合關系矩陣：(按布爾運算)； 有結合律：(R·S)·T＝R·(S·T)，一般不可交換．逆關系；逆關系矩陣滿足：；復合關系與逆關系存在：(R·S)－1=S－1·R－1． 3．理解關系的性質(自反性和反自反性、對稱性和反對稱性、傳遞性的定義以及矩陣表示或關系圖表示)，掌握其判別方法(利用定義、矩陣或圖，充分條件)，知道關系閉包的定義和求法．註：(1)關系性質的充分必要條件：① R是自反的�0�4IA�0�1R；②R是反自反的�0�4IA�0�5R＝�0�4；③R是對稱的 �0�4R＝R－1；④R是反對稱的�0�4R�0�5R－1�0�1IA；⑤R是傳遞的�0�4R·R�0�1R. (2)IA具有自反性，對稱性、反對稱性和傳遞性．EA具有自反性，對稱性和傳遞性．故IA，EA是等價關系．�0�4具有反自反性、對稱性、反對稱性和傳遞性．IA也是偏序關系．4．理解等價關系和偏序關系概念，掌握等價類的求法和作偏序集哈斯圖的方法．知道極大(小)元，最大(小)元的概念，會求極大(小)元、最大(小)元、最小上界和最大下界． 等價關系和偏序關系是具有不同性質的兩個關系. 知道等價關系圖的特點和等價類定義，會求等價類． 一個子集的極大(小)元可以有多個，而最大(小)元若有，則惟一.且極元、最元只在該子集內；而上界與下界可以在子集之外．由哈斯圖便於確定任一子集的最大(小)元，極大(小)元．5．理解函數概念：函數(映射)，函數相等，復合函數和反函數．理解單射、滿射和雙射等概念，掌握其判別方法． 設f是集合A到B的二元關系，"a�0�2A，存在惟一b�0�2B，使得<a, b>�0�2f，且Dom(f)=A，f是一個函數(映射)．函數是一種特殊的關系．集合A×B的任何子集都是關系，但不一定是函數．函數要求對於定義域A中每一個元素a，B中有且僅有一個元素與a對應，而關系沒有這個限制． 二函數相等是指：定義域相同，對應關系相同，而且定義域內的每個元素的對應值都相同． 函數有：單射——若；滿射——f(A)=B或使得y=f(x)；雙射——單射且滿射． 復合函數 即．復合成立的條件是：．一般，但.反函數——若f：A�0�3B是雙射，則有反函數f－1：B�0�3A， ， 重點：關系概念與其性質，等價關系和偏序關系，函數. 第3章 圖的基本概念 復習要點 1．理解圖的概念：結點、邊、有向圖，無向圖、簡單圖、完全圖、結點的度數、邊的重數和平行邊等.理解握手定理． 圖是一個有序對<V，E>，V是結點集，E是聯結結點的邊的集合．掌握無向邊與無向圖，有向邊與有向圖，混合圖，零圖，平凡圖、自迴路(環)，無向平行邊，有向平行邊等概念．簡單圖，不含平行邊和環(自迴路)的圖、 在無向圖中，與結點v(�0�2V)關聯的邊數為結點度數(v)；在有向圖中，以v(�0�2V)為終點的邊的條數為入度－(v)，以v(�0�2V)為起點的邊的條數為出度＋(v)，deg(v)=deg+(v) +deg－(v)．無向完全圖Kn以其邊數；有向完全圖以其邊數．了解子圖、真子圖、補圖和生成子圖的概念．生成子圖——設圖G＝<V, E>，若E�0�4�0�1E，則圖<V, E�0�4>是<V, E>的生成子圖． 知道圖的同構概念，更應知道圖同構的必要條件，用其判斷圖不同構.重要定理：(1) 握手定理 設G=<V，E>，有；(2) 在有向圖D＝<V, E>中，；(3) 奇數度結點的個數為偶數個． 2．了解通路與迴路概念：通路(簡單通路、基本通路和復雜通路)，迴路(簡單迴路、基本迴路和復雜迴路)．會求通路和迴路的長度．基本通路(迴路)必是簡單通路(迴路)． 了解無向圖的連通性，會求無向圖的連通分支．了解點割集、邊割集、割點、割邊等概念．了解有向圖的強連通強性；會判別其類型．設圖G＝<V，E>，結點與邊的交替序列為通路．通路中邊的數目就是通路的長度．起點和終點重合的通路為迴路．邊不重復的通路(迴路)是簡單通路(迴路)；結點不重復的通路(迴路)是基本通路(迴路). 無向圖G中，結點u, v存在通路，u, v是連通的，G中任意結點u, v連通，G是連通圖．P(G)表示圖G連通分支的個數． 在無向圖中，結點集V�0�4�0�0V，使得P(G－V�0�4)>P(G)，而任意V�0�5�0�0V�0�4,有P（G－V�0�5）＝P(G)，V�0�4為點割集. 若V�0�4是單元集，該結點v叫割點；邊集E�0�4�0�0E，使得P(G－V�0�4)>P(G)，而任意E�0�5�0�0E�0�4，有P（G－E�0�5）＝P(G)，E�0�4為邊割集．若E�0�4是單元集，該邊e叫割邊(橋)．要知道：強連通單側連通弱連通，反之不成立．3．了解鄰接矩陣和可達矩陣的概念，掌握其構造方法及其應用．重點：圖的概念，握手定理，通路、迴路以及圖的矩陣表示． 第4章 幾種特殊圖 復習要點1．理解歐拉通路(迴路)、歐拉圖的概念，掌握歐拉圖的判別方法．通過連通圖G的每條邊一次且僅一次的通路(迴路)是歐拉通路(迴路)．存在歐拉迴路的圖是歐拉圖. 歐拉迴路要求邊不能重復，結點可以重復．筆不離開紙，不重復地走完所有的邊，走過所有結點，就是所謂的一筆畫．歐拉圖或通路的判定定理 (1)無向連通圖G是歐拉圖�0�4G不含奇數度結點(即G的所有結點為偶數度)； (2)非平凡連通圖G含有歐拉通路�0�4G最多有兩個奇數度的結點； (3)連通有向圖D含有有向歐拉迴路�0�4D中每個結點的入度＝出度．連通有向圖D含有有向歐拉通路�0�4D中除兩個結點外，其餘每個結點的入度＝出度，且此兩點滿足deg－(u)－deg＋(v)＝±1．2．理解漢密爾頓通路(迴路)、漢密爾頓圖的概念，會做簡單判斷．通過連通圖G的每個結點一次，且僅一次的通路(迴路)，是漢密爾頓通路(迴路)．存在漢密爾頓迴路的圖是漢密爾頓圖. 漢密爾頓圖的充分條件和必要條件 (1)在無向簡單圖G=<V，E>中，�0�5V�0�5�0�63，任意不同結點，則G是漢密爾頓圖．(充分條件) (2)有向完全圖D＝<V，E>, 若，則圖D是漢密爾頓圖. (充分條件)(3) 設無向圖G=<V，E>，任意V1�0�0V，則W(G－V1)�0�5�0�5V1�0�5(必要條件)若此條件不滿足，即存在V1�0�0V，使得P(G－V!)>�0�5V1�0�5,則G一定不是漢密爾頓圖(非漢密爾頓圖的充分條件)．3．了解平面圖概念，平面圖、面、邊界、面的次數和非平面圖．掌握歐拉公式的應用．平面圖是指一個圖能畫在平面上，除結點之外，再沒有邊與邊相交． 面、邊界和面的次數等概念．重要結論：(1)平面圖．(2)歐拉公式：平面圖 面數為r，則(結點數與面數之和＝邊數＋2)(3)平面圖． 會用定義判定一個圖是不是平面圖． 4．理解平面圖與對偶圖的關系、對偶圖在圖著色中的作用，掌握求對偶圖的方法．給定平面圖G＝〈V，E〉，它有面F1，F2，…，Fn，若有圖G*＝〈V*，E*〉滿足下述條件： ⑴對於圖G的任一個面Fi，內部有且僅有一個結點vi*∈V*；⑵對於圖G的面Fi，Fj的公共邊ek，存在且僅存在一條邊ek*∈E*，使ek*＝(vi*，vj*)，且ek*和ek相交； ⑶當且僅當ek只是一個面Fi的邊界時，vi*存在一個環ek*和ek相交；則圖G*是圖G的對偶圖．若G*是G的對偶圖，則G也是G*的對偶圖．一個連通平面圖的對偶圖也必是平面圖．5．掌握圖論中常用的證明方法．重點：歐拉圖和哈密頓圖、平面圖的基本概念及判別． 第5章 樹及其應用 復習要點1．了解樹、樹葉、分支點、平凡樹、生成樹和最小生成樹等概念，掌握求最小生成樹的方法．連通無迴路的無向圖是樹．樹的判別可以用圖T是樹的充要條件(等價定義)．注意：(1) 樹T是連通圖； (2)樹T滿足m＝n－1（即邊數=頂點數-1）．圖G的生成子圖是樹，該樹就是生成樹．每邊指定一正數，稱為權，每邊帶權的圖稱為帶權圖．G的生成樹T的所有邊的權之和是生成樹T的權，記作W(T)．最小生成樹是帶權最小的生成樹．2．了解有向樹、根樹、有序樹、二叉樹、二叉完全樹、正則二叉樹和最優二叉樹等概念．了解帶權二叉樹、最優二叉樹的概念，掌握用哈夫曼演算法求最優二叉樹的方法．有向圖刪去邊的方向為樹，該圖為有向樹． 對非平凡有向樹，恰有一個結點的入度為0(該結點為樹根)，其餘結點的入度為1，該樹為根樹． 每個結點的出度小於或等於2的根樹為二叉樹；每個結點的出度等於0或2的根樹為二叉完全樹；每個結點的出度等於2的根樹稱為正則二叉樹． 有關樹的求法：(1)生成樹的破圈法和避圈法求法；(2)最小生成樹的克魯斯克爾求法；(3) 最優二叉樹的哈夫曼求法重點：樹與根樹的基本概念，最小生成樹與最優二叉樹的求法. 第6章 命題邏輯 復習要點 1．理解命題概念，會判別語句是不是命題．理解五個聯結詞：否定�0�1P、析取�0�3、合取�0�2、條件�0�3、和雙條件�0�0及其真值表，會將簡單命題符號化．具有確定真假意義的陳述句稱為命題．命題必須具備：其一，語句是陳述句；其二，語句有唯一確定的真假意義. 2．了解公式的概念(公式、賦值、成真指派和成假指派)和公式真值表的構造方法．能熟練地作公式真值表．理解永真式和永假式概念，掌握其判別方法．判定命題公式類型的方法：其一是真值表法，其二是等價演演算法.3．了解公式等價概念，掌握公式的重要等價式和判斷兩個公式是否等價的有效方法：等價演演算法、列真值表法和主範式方法． 4．理解析取範式和合取範式、極大項和極小項、主析取範式和主合取範式的概念，熟練掌握它們的求法． 命題公式的範式不惟一，但主範式是惟一的． 命題公式A有n個命題變元，A的主析取範式有k個極小項，有m個極大項，則 於是有(1) A是永真式�0�4k=2n(m=0)； (2) A是永假式�0�4m＝2n(k=0)； 求命題公式A的析取(合取)範式的步驟：見教材第174頁．求命題公式A的主析取(合取)範式的步驟：見教材第177和178頁． 5．了解C是前提集合{A<sub>1</sub>,A<sub>2</sub>,…,A<sub>m</sub>}的有效結論或由A1, A2, …, Am 邏輯地推出C的概念．要理解並掌握推理理論的規則、重言蘊含式和等價式，掌握命題公式的證明方法：真值表法、直接證法、間接證法．重點：命題與聯結詞，公式與解釋，真值表，公式的類型及判定，主析取(合取)範式，命題演算的推理理論. 第7章 謂詞邏輯復習要點1．理解謂詞、量詞、個體詞、個體域，會將簡單命題符號化．原子命題分成個體詞和謂詞，個體詞可以是具體事物或抽象的概念，分個體常項和個體變項．謂詞用來刻劃個體詞的性質或之間的關系． 量詞分全稱量詞"，存在量詞$. 命題符號化注意：使用全稱量詞"，特性謂詞後用�0�3；使用存在量詞$，特性謂詞後用�0�2．2．了解原子公式、謂詞公式、變元(約束變元和自由變元)與轄域等概念．掌握在有限個體域下消去公式的量詞和求公式在給定解釋下真值的方法．由原子公式、聯結詞和量詞構成謂詞公式．謂詞公式具有真值時，才是命題． 在謂詞公式"xA或$xA中，x是指導變元，A是量詞的轄域．會區分約束變元和自由變元．在非空集合D(個體域)上謂詞公式A的一個解釋或賦值有3個條件． 在任何解釋下，謂詞公式A取真值1，A為邏輯有效式(永真式)；公式A取真值0，A為永假式；至少有一個解釋使公式A取真值1，A稱為可滿足式．在有限個體域下，消除量詞的規則為：設D＝{a<sub>1</sub>, a<sub>2</sub>,…, a<sub>n</sub>}，則會求謂詞公式的真值，量詞的轄域，自由變元、約束變元，以及換名規則、代入規則等．掌握謂詞演算的等價式和重言蘊含式．並進行謂詞公式的等價演算．3．了解前束範式的概念，會求公式的前束範式的方法. 若一個謂詞公式F等價地轉化成 ，那麼就是F的前束範式，其中Q1，Q2，…，Qk只能是"或$，而x1, x2,…, xk是個體變元，B是不含量詞的謂詞公式．前束範式仍然是謂詞公式． 4．了解謂詞邏輯推理的四個規則．會給出推理證明． 謂詞演算的推理是命題演算推理的推廣和擴充，命題演算中基本等價式，重言蘊含式以及P，T，CP規則在謂詞演算中仍然使用．謂詞邏輯的推理演算引入了US規則(全稱量詞指定規則)，UG規則(全稱量詞推廣規則)，ES規則(存在量詞指定規則)，EG規則(存在量詞推廣規則)等.重點：謂詞與量詞，公式與解釋，謂詞演算．
『伍』 離散數學這門課程第八章基本計數方法的知識點有哪些
離散數學這門課第八章基本計數方法的知識點包含章節導引,第一節鴿巢原理,第二節加法原理與乘法原理,第三節不可重復的排列和組合,第四節二項式系數,第五節可重復的排列和組合,第六節容斥原理,課後鞏固,。
『陸』 離散數學這門課程第六章圖論基礎的知識點有哪些
離散數學這門課第六章圖論基礎的知識點包含章節導引,第一節圖及其表示,第二節握手定理,第三節圖的連通性,第四節頂點著色,第五節圖同構,課後鞏固,。
『柒』 離散數學這門課程第五章函數的知識點有哪些
離散數學這門課第五章函數的知識點包含章節導引,第一節函數的概念和性質,第二節可數集、不可數集和不可解問題,課後鞏固,。
『捌』 離散數學包括哪些知識
邏輯和證明，集合與函數， 演算法，數論和密碼學，歸納與遞歸，計數， 離散概率，高級計數技術
， 關系，圖，樹， 布爾代數， 計算模型
『玖』 離散數學的簡單填空，幫幫忙
1、{a,c,e}
2、{{Ф}}
3、P(A)={∅,{2},{{∅,2}},{{∅,2},2}}
4、A×B={(0,2),(1,2)}
5、2^(3^2)=2^9=512
6、無圖無真相
7、{{1,3,5},{2，4}}
『拾』 離散數學，主要學習哪些知識
離散數學是數學的幾個分支的總稱,以研究離散量的結構和相互間的關系為主要目標,其研究對象一般地是有限個或可數無窮個元素;因此它充分描述了計算機科學離散性的特點.內容包含：數理邏輯、集合論、代數結構、圖論、組合學、數論等.《離散數學》課程簡介 離散數學是計算機專業的一門重要基礎課.它所研究的對象是離散數量關系和離散結構數學結構模型.由於數字電子計算機是一個離散結構,它只能處理離散的或離散化了的數量關系,因此,無論計算機科學本身,還是與計算機科學及其應用密切相關的現代科學研究領域,都面臨著如何對離散結構建立相應的數學模型；又如何將已用連續數量關系建立起來的數學模型離散化,從而可由計算機加以處理.離散數學課程主要介紹離散數學的各個分支的基本概念、基本理論和基本方法.這些概念、理論以及方法大量地應用在數字電路、編譯原理、數據結構、操作系統、資料庫系統、演算法的分析與設計、人工智慧、計算機網路等專業課程中；同時,該課程所提供的訓練十分有益於學生概括抽象能力、邏輯思維能力、歸納構造能力的提高,十分有益於學生嚴謹、完整、規范的科學態度的培養.
離散數學主要包括四個方面邏輯學集合論,代數結構,圖論,直接用來解決一些實際的問題的,比較少,因為它是一門計算機專業的理論基礎課,解決實際問題,你看哪些方面的問題了,
下面我舉一些例子：
1 數據結構,這是計算機專業的一門重量級課程,而離散數學里裡面的圖論,就是數據結構裡面圖和樹的理論基礎!像一些經典的演算法,在數據結構里會學到,其實,它們在圖論里就被研究得很透!
2.關系資料庫,不用說,它的理論基礎----關系代數,就是離散數學的一個分支!
3.在計算機網路原理裡面,有一些路由選擇演算法之類 的,像最短路徑演算法等,都是離散數學里圖論的應用,都是一些經典的演算法!
4.更深層次的,像人工智慧等學科,都是以離散數學做為理論基礎的,
所以,離散數學是計算機的一個理論基礎,
至於你在編程中解決的問題,那應該是數據結構和演算法的應用,因為這門課就是離散數學的理論,加上在計算機上的存儲以及操作實現的~~