離散數(shù)學課程教學的理性思考

1、離散數(shù)學教學的理性思考,,主要內容,基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎,基本問題,離散數(shù)學數(shù)理邏輯集合論圖論代數(shù)系統(tǒng)常識問：學習離散數(shù)學有什么有？答：離散數(shù)學是計算機專業(yè)基礎基本問題“離散數(shù)學是計算機專業(yè)基礎”是什么意思？“離散數(shù)學如何是計算機專業(yè)基礎”是什么意思？,離散數(shù)學與計算機專業(yè)課程關系問題,《高等學校計算機科學與技術專業(yè)發(fā)展戰(zhàn)略報告暨專業(yè)規(guī)范》,為什么離散數(shù)學的前導課程是數(shù)學？為什么數(shù)字邏

2、輯課程前導課程是計算機導論？如何體現(xiàn)離散數(shù)學課程的基礎性？,計算機專業(yè)的基礎問題,邏輯是所有數(shù)學推理及其所有自動推理的基礎。對于計算機的設計、系統(tǒng)規(guī)范說明、人工智能、計算機程序設計、程序設計語言以及計算機科學的其它許多領域，邏輯都有實際的應用。 ————Kenneth H. Rosen,ACM Computer Science Curricula 2013,集合、基本邏輯和證明方法的知識點,集合維恩圖并集、交集、補集笛

3、卡爾積、冪集、有限集合的基數(shù)關系自反性、對稱性、傳遞性等價關系、偏序關系函數(shù)滿射、單射、雙射反函數(shù)函數(shù)的復合,命題邏輯（參考：命題邏輯同時出現(xiàn)在智能系統(tǒng)/知識推理）邏輯聯(lián)結詞真值表范式（合取范式、析取范式）合式公式的有效性命題推理定律（肯定前件式和否定后件式的概念）謂詞邏輯全稱量詞與存在量詞命題邏輯和謂詞邏輯的局限,蘊含、等價、逆命題、否命題、逆否命題、否定和矛盾等概念數(shù)學證明架構直接證明反例證偽反

4、證法數(shù)學歸納法結構歸納法弱歸納法與強歸納法（即，第一類數(shù)學歸納法和第二類數(shù)學歸納法）數(shù)學上的遞歸定義,主要內容,基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎,最簡單的論域—邏輯域,邏輯對象：{0,1}邏輯運算：{? ,?, ?, ?, ?, ?}邏輯關系：{=, ╞}真值表一組邏輯自變量與一個邏輯因變量的對應表真值表定義邏輯運算和關系,命題邏輯公式與語言,定義：(1).常量0和1是邏輯公式；(2).命題變量是

5、邏輯公式；(3).若Q,R是邏輯公式，則(?Q)、(Q?R) 、(Q?R) 、(Q?R) 、(Q?R) 、(Q?R)是邏輯公式；(4).只有有限次應用(1)—(3)構成的公式是邏輯公式。,真值表驗證運算性質,結合律(P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=P∧(Q∧R)(P?Q)?R=P?(Q?R) 分配律P∨(Q∧R)=(P∨Q)∧(P∨R) P∧(Q∨R)=(P∧Q)∨(P∧R)P∧(Q?R)=(P∧Q)?(

6、P∧R),交換律Q∨R=R∨QQ∧R=R∧QQ?R=R?Q德?摩根律?(Q∨R)=?Q∧?R?(Q∧R)=?Q∨?R,邏輯表達式一般方法,若xi,j =1，則x'i,j=xk，若xi,j =0，則x'i,j= ?xi,j若yk=1，k=0,…,n，則yk=x'm-1,k?… ? x'0,ky= y0?…? yn功能可以用真值表表達所有邏輯運算都可以表達為?, ? ,?,的運算。,邏輯哲

7、學,世界是由事實構成的《邏輯哲學論》事實是事物的性質，以及事物之間的關系《我們關于外間世界的知識-哲學上科學方法應用的一個領域》,維特根斯坦,羅素,根據維特根斯坦和羅素的哲學思想，事實是表達事物的性質或表達一些事物之間的關系。世界由事實構成，而命題與事實對應，事實使一個命題為真或為假。最簡單的事實稱為原子事實，與原子事實對應的是原子命題。原子命題的真或假取決于它與相應的原子事實是否符合。,謂詞,定義：研究對象統(tǒng)稱為客體。定義

8、：事物的性質詞和事物的關系詞統(tǒng)稱為謂詞。謂詞可以表示為Q(x1,...,xn)，其中，Q是謂詞，x1,...,xn是客體Q(x)是一元謂詞，Q(x,y)二元謂詞，Q(x1,...,xn)是n元謂詞。謂詞對于任意客體都有真值。謂詞形式如果謂詞形式是Q(x)表示客體x有Q性質；如果謂詞形式是Q(x1,...,xn)表示客體x1,...,xn之間有Q關系。量詞表示所有客體具有某性質或關系的詞稱為全稱量詞，記為?

9、 ?x(Q(x)?R(x))表示至少有一個客體具有某性質或關系的詞稱為存在量詞，記為? ?x(Q(x)?R(x)),合式公式與一階謂詞語言,定義：合式公式是按如下規(guī)則構成的有窮長符號串。(1).若是x1,…,xn是變元，Qin是n元謂詞，則Qin(x1,…,xn)是合式公式。(2).若Q是合式公式，則(?Q)是合式公式；(3).若Q和R是合式公式，則(Q?R)、(Q?R)、(Q?R) 、(Q

10、?R)及(Q?R)是合式公式；(4).若Q是合式公式，x是變元，則(?xQ)及(?xQ)是合式公式。(5).只有有限次應用(1)—(4)構成的公式是合式公式。,思想理論與邏輯語言,弗雷格思想理論思想是陳述句的含義思想有真假思想有結構思想通過語言來表達和傳遞存在判定思想同一性的標準思想影響人的意志自然語言符合邏輯語言在保持思想的情況下，自然語言變換為邏輯語言,Gottlob Frege 1848-1925,自然（科學）

11、語言命題符合邏輯語言,定義：具有確定真或假含義的陳述句稱為原子命題，或簡單命題。在自然語言中，'并且'、'或'、'并非'、'如果...，則...。'、'當且僅當'等詞也稱為聯(lián)接詞。復合語句是一些陳述句用'并且'、'或'、'并非'、'如果...，則...。'、'當且僅當'等聯(lián)接

12、為一條語句。量化語句是用'所有'、'存在'等量詞約束陳述句或復合語句。定義：原子命題用'并且'、'或'、'并非'、'如果...，則...。'、'當且僅當'等聯(lián)接詞聯(lián)接的語句稱為復合命題。定義：用'所有'和'存在'量詞約束的原子命題或復合命題稱為量化命題。定義：原子命題、復合命題和量化命題

13、統(tǒng)稱為命題。,符號化機械過程,自然語言的命題符號化方法是機械式過程，無需理解具體概念的含義，僅僅將相同的客體、函數(shù)、性質或關系分別用相同符號表示。復合語句由簡單語句、聯(lián)接詞及量詞構成。首先，識別出簡單語句，而后，簡單語句符號化。復合語句由符號化的簡單命題形式和聯(lián)接詞及量詞構成。復合語句就可以根據聯(lián)接詞及量詞的含義，形成符號化的命題。,符號化機械過程（續(xù)）,自然知識可以表示為命題，所有的自然律也可以表達為命題。自然語言的命題符號

14、化方法：(1).在復合語句中識別出陳述句，并用下劃線標出(2).陳述語句符號化相同（不同）的客體用相同(不同)符號表示相同（不同）函數(shù)用相同（不同）符號表示相同（不同）性質或關系用相同（不同）符號表示(3).聯(lián)接詞及量詞符號化'并且'表示為'?'，'或'表示為'?'，'并非'表示為'?'，'如果...，則...。'

15、;表示為'?'，'當且僅當'表示為'?‘'所有'表示為'?'，'存在'表示為'?'，形成符號化的命題。,數(shù)學分析概念,在研究過程中，首先用定義的方式給出概念，而后研究概念的性質以及概念之間的關系，形成定理。概念的定義是復合語句，也能夠用機械方式符號化。自然語言表達序列極限、函數(shù)極限、連續(xù)、一致連續(xù)、導數(shù)等概念，人們可能有二義性

16、理解，即人們對這些概念含義會有不同的理解。如果這些概念符號化，那么，人們對這些概念的理解就會相同。,定義（極限）是命題,定義：設{xn}是序列，對于任意ε>0，存在N>0，對于任何n，當n>N時，都有|xn-b|<ε，則稱序列{xn}的極限是b，記為 。,(1) 陳述句識別：對于所有ε，ε>0，存在N，N>0，對于任何n，當n>N時，都有|xn-b|0，存在N，N>

17、0，對于所有n，當n>N時，都有|xn-b|0??N(N>0??n(n>N?|xn-b|<ε))),定理是命題,定理 ：若序列的極限存在，則極限值唯一。?ε(ε>0??N1(N1>0??n(n>N1?|xn-a|0??N2(N2>0??n(n>N2?|xn-b|0??N(N>0??n(n>N?|xn-a|0??n(n>0?|xn |<M)),歐幾里德幾何學,

18、歐幾里德（325 BC -265 BC ），古希臘數(shù)學家；《幾何原本》是一個實質公理系統(tǒng)把點、線、面、角等分為原始定義概念（23）和可定義概念；命題分為公理（5）、公設（5）；由公理公設出發(fā)加以證明的定理（467）從簡單到復雜，證明相當嚴格。從而建立了歐幾里得幾何學的第一個公理化數(shù)學體系。,,公設1.由任意一點到另外任意一點可以畫直線。2.一條有限直線可以繼續(xù)延長。3.以任意點為心及任意的距離可以畫圓。4.凡直角都彼此

19、相等。5．(平行公設)若一直線與兩直線相交，且若同側所交兩內角之和小于兩直角，則兩直線無限延長后必相交于該側的一點。,公理1．等于同量的量彼此相等。2．等最加等量，其和仍相等。3，等量減等量，其差仍相等。4．彼此能重合的物體是全等的。5．整體大于部分。,希爾伯特證明論,通過形式化第一次使證明本身成為數(shù)學研究對象。給出初始符號集合構造合式公式規(guī)則Γ├Q的證明，構造出1~m個合式公式序列，其中，第m個合式公式是Q，并且1~

20、m合式公式或者是前提或者是公理或者是推導規(guī)則形式證明正確性的驗證。,David Hilbert 1826-1943,邏輯證明有何不同？,領域知識是提出概念，形成定理，對定理進行證明。通過思想概念的涵義以及關系，形成一個個推理步驟，最后完成證明。領域知識不同，證明方法也不同。在邏輯公理系統(tǒng)中，已知語言、公理、推理規(guī)則Γ是前提集, Q是結論Γ是語句集合，Q是語句在邏輯公理系統(tǒng)中，各個領域知識都抽象為形式語言。從形式語言表

21、示的公理和前提集開始，一步步推理到結論。因為推理過程沒有領域概念及其涵義，僅有抽象的符號，按照推理規(guī)則一步一步進行推理，所以，推理具有統(tǒng)一方法。,邏輯公理系統(tǒng),公理系統(tǒng)從一些公理出發(fā)，根據演繹法，推導出一系列定理，形成的演繹體系叫作公理系統(tǒng)。公理系統(tǒng)的組成：語言集公理集公理是用于表達推理由之出發(fā)的初始肯定命題；推理規(guī)則集推理規(guī)則是由公理及已證定理得出新定理的規(guī)則；定理集表達了肯定的所有命題。,謂詞邏輯公理系統(tǒng),(1)

22、謂詞邏輯語言：L=(2).公理集合：1).公理模式A 1：Q? (R?Q)2).公理模式A 2：(P? (Q?R)) ? ((P?Q) ? (P?R))3).公理模式A 3：(?Q??R) ? (R?Q) 4).公理模式A 4：?xQ(x)?Q(x)[x/t] 其中，項t對于Q中的x

23、是可代入的。 5).公理模式A 5：?x(Q?R(x)) ? (Q??xR(x)) 其中x不是Q中自由變元。(3).推理規(guī)則1).分離規(guī)則（簡稱MP規(guī)則）：從Q和Q?R推出R。2).全稱概括（簡稱UG規(guī)則）：從Q(x)推出(?xQ)。,演繹與證明,Γ├Q的證明，就是要構造一個合式公式的變換序列，其中每一步產生的合式公式，并且或者是公理模式或者是前提模式或者是由分離規(guī)

24、或者是全稱概括（謂詞邏輯）,├ ?xQ(x)??yQ(y) (y不在Q中出現(xiàn)),證明： 證據：A1=?xQ(x) ?Q(y) A4 A2=?y(?xQ(x) ?Q(y))

25、 UG A3=?y(?xQ(x) ?Q(y))?(?xQ(x) ??y Q(y)) A5 A4=?xQ(x) ??y Q(y) A3=A2? A4證畢,定理(傳遞律)：P?Q,Q?R├P?R,證明： 證據：A

26、1=(Q?R) ?(P? (Q?R)) A1A2=Q?R A2? Γ A3=P? (Q?R) A1=A2 ? A3 A4=(P? (Q?R)) ?((P?Q) ?(P?R))

27、 A2A5=(P?Q) ?(P?R) A4=A3 ? A5 A6=(P?Q) A6? Γ A7=(P?R) A5=A6→A7證畢,定律與規(guī)則,思維直覺、

28、思維定律與定理。充分理由律（三段論）：Q, Q?R ├R傳遞律：P?Q,Q?R├P?R 反證律：如果Γ, ?Q├ R, Γ, ?Q├?R,則Γ├ Q歸謬律：如果Γ, Q├ R, Γ, Q├ ?R，則Γ├ ?Q 排中律：├(Q??Q)矛盾律：├?(Q??Q)引入規(guī)則： ├ P(c) ??xP(x) 選擇規(guī)則： ├ ?xP(x)?P(c),命題邏輯定理,├ (P?(Q?R)) ?(Q?(P?R))├(Q?R)?((P?Q

29、)?(P?R))├(P? Q)?((Q?R)?(P?R))├((P? Q)?(P?R))?(P?(Q ?R)├Q?Q├??Q?Q├ Q???Q├Q?((Q?R)? R) ├ Q?(Q?R)?R├ Q?Q ?Q ├ Q?Q ?Q├(Q?R) ? (R?Q)├(Q? R)?(Q ??R),├ (??Q???R)?(Q?R) ├ (Q?R)?(??Q???R)├(Q?R)?(?R??Q)├(?Q?R)?(?R?Q)

30、├(Q??R )?(R??Q) ├ ?Q?(Q? R)├(?Q?Q)?(R?Q)├(?Q?Q)?Q ├(?Q?R??R)?Q├(?Q?R) ?((?Q??R) ?Q)├(Q?R) ?((Q??R)??Q),一階謂詞邏輯定理,├ ?xR(x) ? ?y R(y)├ ?xR(x) ? ?y R(y)├ Q(c) ??xQ(x)├ ?Q(c) ???xQ(x)├ ?xR(x) ? ?xR(x)  

31、├ ?x?y R(x,y) ? ?y?xR(x,y) ├ ?x?y R(x,y) ? ?y?xR(x,y) ├ ?x?yR(x,y) ? ?y?x R(x,y)├ ?x?yR(x,y) ? ?xR(x,x)├ ?xR(x,x) ? ?x?yR(x,y),├ ?x(P(x)?Q(x)) ?(?xP(x) ??x Q(x))├ ?x(P(x) ?Q(x)) ?(?xP(x) ? ?x Q(x))├ ?x(P(x)?Q(x))?

32、(?xP(x)??xQ(x)) ├ ?xP(x) ? ?xQ(x))??x(P(x) ? Q(x)) ├ ?x(P(x)?Q(x)) ?(?xP(x) ??xQ(x))├ ?x(P(x)?Q(x)) ?(?xP(x) ??xQ(x)) ├ ?xP(x) ???x?P(x) ├ ?xP(x) ???x?P(x) ├ ?x?P(x) ???xP(x) ├ ? ?x?P(x) ??xP(x),論域、解釋、賦值與模型,在指定論域

33、上，對于一階邏輯語言L解釋將常元指稱為論域中某客體；將謂詞指稱為論域上的關系；將函詞指稱為論域上的函數(shù)。賦值將客體變元指稱為論域中的客體。一階邏輯語言的解釋，是確定該種語言里的符號表達式同某個論域之間的聯(lián)系。論域和解釋構成了結構。結構和賦值構成了模型。一階邏輯語言的語義就是在模型上的邏輯真值。,合式公式、合式公式集合與模型,研究合式公式或合式公式集合QΓ= {Q1,...,Qn}在一個模型上具有的性質；在所有

34、模型上具有的性質,等式關系和推論關系,定義：給定一階語言L及它的兩個公式Q,R，如果存在模型M=，使得σ(Q) = σ(R), 則稱Q與R是在模型M等值，記為Q?MR。定義：給定一個語言L , Γ是一個公式集合, Q 是一個公式。 若存在模型M=，使得當σ(Γ)=1時，有σ(Q)=1，則稱Q 是Γ關于模型邏輯推論，記為Γ╞MQ。定義：如果對于任意模型M=，都有 σ(Q) = σ(R), 則稱Q與R是邏輯等價，記為Q?R。

35、定義：給定一個語言L , Γ是一個公式集合, Q 是一個公式。 若對于任意模型M=，使得當σ(Γ)=1時有σ(Q)=1，則稱Q 是Γ邏輯推論，或稱Γ語義推出Q，記為Γ╞Q。,前束范式,定義：設δk為?,?量詞，x1…xn為不同變元，Q為開公式，形式為δ1x1…δn xnQ的公式稱為前束范式， 稱δ1x1…δn xn為前束詞，稱Q為母式。定理：設δk為?,?量詞，x1…xn為不同變元，對于任意

36、合式公式Q，存在前束范式δ1x1…δn xnR， 使得Q?δ1x1…δn xnR。定義：若δ1x1…δn xnQ的是前束范式，并且Q是合取范式，則稱δ1x1…δn xnQ是前束合取范式。,前束范式步驟,(1).依次用等值公式Q?R?? (Q?R)Q?R? (Q?R)?(R?Q)Q?R? ?Q?R進行等值變換，產生的公式僅有聯(lián)結詞?、?、?以及量詞?、?。(2). 用等值公

37、式??Q?Q進行變換化簡公式。(3).根據以上等值公式，以及如下量詞變換等值公式??Q(x) ??x?Q(x)??Q(x) ??x?Q(x)(4).用德?摩根律?(Q?R) ??Q??R，?(Q?R) ??Q??R進行化簡。重復應用(2)、(3)、(4)步驟，逐次將所有聯(lián)結詞?置于原子謂詞。,前束范式步驟（續(xù)）,(5).用換名等值公式?xQ(x)??yQ(y)和?xQ(x)??yQ(y)將所有不同量詞轄域的變元換名為互不同的變

38、元。(6). 若x不在Q中出現(xiàn)，則Q??xR(x) ??x(Q?R(x))Q??xR(x) ??x(Q?R(x))Q??xR(x) ??x(Q?R(x))Q??xR(x) ??x(Q?R(x))δ1x1Q(x1)?δ2 R(x2) ?δ1x1δ2 x2(Q(x1)?R(x2)) δ1x1Q(x1)?δ2 R(x2) ?δ1x1δ2 x2(Q(x1)?R(x2))重復應用(6)步驟，逐次將量詞前置，使得公式變換為前束范式。

39、(7).用等值變換交換量詞次序?x?y Q(x,y) ??y?xQ(x,y)?x?y Q(x,y) ??y?xQ(x,y),等式演算一般方法,命題公式:Q的范式是Q '，R的范式是R '，因為 Q?Q '， Q '?R '，R' ?R 。所以Q?R謂詞公式:Q的前束合取范式是Q ' ，R的前束合取范式是R '，因為 Q?Q '， Q '?R

40、'，R' ?R 。所以Q?R,主要內容,基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎,結構主義,在《結構主義》中，皮亞杰給出結構特征結構由對象集合S以及關系集合R、運算集合F和常元集合C組成，整體性、轉換、自身調整性結構主義是知識表征的重要方法,從結構主義觀點看,集合論性質定義概念外延與內涵圖論結構集合定義概念代數(shù)系統(tǒng)操作定義概念,定義運算保持封閉性定義關系洞察性質，形成定理,邏輯表達概念

41、、運算和關系一般方法證明等式演繹形式證明,命題的邏輯構造,基本概念與導出概念命題：概念定義是命題。運算定義是命題。關系定義是命題。定理是命題。邏輯命題能由自然語言描述機械式的變換為邏輯描述。聯(lián)接詞?,?,?,?,?量詞?,?謂詞、函詞和常元邏輯命題是形式的。,集合基本概念、概括性公理,集合是一些能夠明確區(qū)分的對象構成的整體。集合一般用大寫英文字母表示，構成集合的對象稱為元素，一般用小寫英文字母表示。元素與集合

42、有“屬于”基本關系， ?關系如果對象 a 在集合 A 中，則稱 a 是A 的元素，或者a 屬于A，記為 a?A，否則記為a?A。概括性公理謂詞ψ(x)是給定的一個性質，則ψ(x)確定唯一一個集合。設A = {x |ψ(x)}，滿足性質ψ(x)的對象都在A中，不滿足該性質的對象都不在A中。即?x (ψ(x) ? x?A),關系,定義 設X，Y是集合，若R ? X ? Y ，則稱 R 為從X到Y的關系，簡稱為關系R。R={ |

43、x ?X?y ?Y}若R 是從X到Y的關系，就是集合X中元素與集合Y中元素之間的對應。,函數(shù),定義：設 f 是從集合 X 到 Y 的關系若對每個 x? X 存在唯一 y? Y 使得 ? f，則稱 f 為從 X 到 Y 的函數(shù)(映射)，記為 f : X ? Y。從 X 到 Y 的函數(shù)指的是單值全函數(shù)，滿足f ? X ? Y?dom( f ) = X?ran( f ) ?Y?? f?? f?y = z,滿射、單射和雙射,定義

44、：設函數(shù)f : X ? Y，(1).若對于每個 y?Y ，都存在 x?X使得 f (x) = y，則稱 f 為滿射，即?y (y?Y ??x (x?X ? f (x) = y))(2).若對于任意 x?X, y?Y，只要 f (x) = f (y)，就有 x = y ，或只要 x ? y，就有 f (x) ? f (y) ，則稱 f 為單射，即?x?y(x?X ?y?X? f (x) = f (y) ? x = y)(3).若

45、函數(shù)f既是單射又是滿射，則稱 f為雙射，也稱為一一對應。,單調性函數(shù),定義：設X，Y為集合，≤是全序關系，f: X?Y，(1).如果對于任意x1f(x2)，則稱f是嚴格單調遞減的? x1? x2(x1f(x2)),集合運算,定義：設A,B為二集合，稱由A和B的所有元素組成的集合為A與B的并集，記作A ? B，稱?為并運算符。A ? B ={ x | x?A ? x?B}A ?B ={ x | x?A ?x?B}

46、 交運算A-B ={ x | x?A ?x?B} 差運算A+B ={ x | x?A ?x?B} 對稱差運算?A ={ x | x?A } 補運算集合運算也是由集合及“?”這兩個基本概念的導出概念。,關系運算,定義：設關系R和S是從X到Y的兩個關系，則R ? S, R ? S, R ? S, R + S, ? R為R ? S=

47、{|?R??S }R ? S={|?R??S }R ? S={|?R??S }R + S={|?R??S }? R={|?R}復合運算、指數(shù)運算及逆運算R°S = { | ?y(?R??S}Rn+1 = Rn ° R（ R0 = IX ）R?1 = { | ?R},集合相等關系,定義(外延性公理）： 如果集合A 和B 含有相同的元素，則稱A 和B相等，記為A = B。 A = B ??x (x?A? x?B)??

48、x (x?A? x?B)??x (x?B? x?A)其中?表示當且僅當關系。在數(shù)理邏輯證明中，用“符號?”代替集合符號“?”。集合的“=”是集合之間的一種關系，即相等關系；這個等關系也可以是表示相等謂詞。謂詞“=”概念是由集合及“?”這兩個基本概念的導出概念。,集合包含關系（子集）,定義 若集合 A 的元素都是集合B的元素，則稱A是B的子集，也稱 A包含于B，或者B包含 A ，記為 A ? B 或 B ? A 。A ? B

49、 ??x (x?A? x?B)定義 若A ? B且A ?B ，則稱A是B的真子集，也稱A真包含于B，或者B 真包含A ，記為A ? B 或 B ? A 。 A ? B ??x (x?A? x?B) ? ?x (x?B ? x?A)關系“?”和“?”概念也是由集合及“?”這兩個基本概念的導出概念。在數(shù)理邏輯證明中，“?”和“?”也可以看作是包含謂詞。,集合運算性質,結合律 (A ? B ) ? C = A ? ( B ? C

50、)(A ? B ) ? C = A ? (B ? C)交換律A ? B = B ? A A ? B = B ? A 分配律A ? ( B ? C ) = (A ? B) ? (A ? C)A ? ( B ? C ) = (A ? B) ? (A ? C)德?摩根律 ? (A ? B ) = ? A ? ? B ? (A ? B ) = ? A ? ? B,冪等律A ? A = A A ? A = A吸收律A

51、? (A ? B ) = A A ? (A ? B ) = A同一律A ? ? = A A ? U = A零 律A ? ? = ? A ? U = U 互補律A ? ? A = ? A ? ? A = U 對合律 ? ? A = A ? ? = U ? U = ?,關系運算性質,(R1°R2 )°R3 = R1°(R2°R3) (R1 ? R2 )°R3 = R1°

52、R3 ? R2°R3 R1°(R2 ? R3)= R1°R2 ? R1°R3 (R1 ? R2 ) ° R3 ? R1 ° R3 ? R2° R3 R1 ° (R2 ? R3) ? R1 ° R2 ? R1° R3(R1 ? R2 ) ° R3 ? R1 ° R3 ? R2° R3,RmRn = Rm+n(Rn)m = Rmn(R1?R2)-1= R1-1?R2-1(R1?R2)-1= R1-1?R2-1(R1-R2)-

53、1= R1-1-R2-1(~R1)-1= ~R1-1 (R ° S)?1 = S ?1 ° R?1,函數(shù)運算性質,定理：設f : X ? Y，則f ° IX = IY ° f = f。定理 設 f : X ? Y， g : Y ? Z， h : Z ? W，則h ° ( g ° f ) = (h ° g ) ° f 定理：設 f 是從 X 到 Y 的函數(shù)，g 是從 Y 到 Z 的函數(shù)。若 f 和 g 都是滿射，則

54、g ° f 是滿射。若 f 和 g 都是單射，則 g ° f 是單射。若 f 和 g 都是雙射，則 g° f 是雙射。定理：設 f 是從 X 到 Y 的函數(shù)，g 是從 Y 到 Z 的函數(shù)。若g ° f 是滿射，則g是滿射。若 g ° f 是單射，則f 是單射。若 g ° f 是雙射，則g 是滿射，f是單射。,函數(shù)運算性質（續(xù)）,性質：f滿足單值性當且僅當f?1 滿足唯一性性質：f 滿足唯一性當且僅當f?1滿足

55、單值性定理：設 f : X ? Y 是雙射函數(shù)，則存在逆函數(shù)f ?1: Y ? X，并且f ?1是雙射函數(shù)。定理 若 f : X ? Y 是可逆的，則 f ?1 ° f = IX且f ° f ?1 = IY定理：設雙射f : X ? Y 及雙射g : Y ? X ，g = f ?1，當且僅當 g ° f = IX 且 f ° g = IY。定理 若雙射f : X ? Y 及雙射g : Y ? Z ，則g ° f 也是雙射

56、，并且 (g ° f )?1 = f ?1 ° g?1 。定理：設 f 是從 X 到 Y 的函數(shù)，g 是從 Y 到 Z 的函數(shù)，若f和g是單調增加的，則g ° f是單調增加的。,用集合和邏輯定義圖概念,定義：設V是一個非空頂點集合，E是無向邊集合，V和E的有序偶稱為無向圖G，記為G= ，其中E={(x, y)|x?V?y?V}定義：設V是一個非空頂點集合，E是有向邊集合，V和E的有序偶稱為有向圖D，記為D=，其中 E=

57、{|x?V?y?V}圖的基本結構是指圖的頂點之間，邊之間及邊與頂點之間的連接關系。頂點之間是鄰接關系頂點與邊是關聯(lián)關系邊與邊是相鄰關系,圖包含關系（子圖）,定義（子圖）：設G=和GS=是兩個圖。若VS?V并且ES?E則稱GS是G的子圖。 記為GS?G。如果GS是子圖并且VS?V或ES?E，則稱GS是G的真子圖，記為GS?G。GS?G ?VS?V?ES?EGS?G?GS?G?(VS?V?ES?E)定義（導出子圖）：設

58、GS=是G=子圖。如果ES是E中所有只關聯(lián)于VS中的頂點的邊的集合，則稱GS為VS所導出的子圖，簡稱圖G的導出子圖，即ES={e| u?VS ?v?VS?e=(u, v) ?E}定義（生成子圖）：設圖GS=是圖G=的子圖。如果VS=V，則稱GS為G的生成子圖。GS ?G?VS=V,典型圖問題（集合和邏輯表征）,連通性穿程問題歐拉圖、哈密頓圖通路問題最短通路、關鍵通路樹二叉樹、生成樹二分圖及匹配問題圖著色問題平

59、面圖,群的基本概念,定義：設G是一個非空集合，°是二元代數(shù)運算，如果滿足以下條件：(1).代數(shù)運算°滿足結合律，即對G中任意元素a，b，c都有(a°b)°c=a°(b°c)(2).G中有元素e，稱為G的左單位元，對于G中每個元素a都有e°a= a(3).對G中每個元素a，都有元素a-1，稱為a的左逆元，使得a-1°a=e則稱G對代數(shù)運算°作成一個群。群是用運算定義概念,群（公理）,群理論可以采用數(shù)理邏輯方法表示，它有3條

60、公理。定義：設是一個代數(shù)系統(tǒng)，稱為一個群，如果滿足以下條件： (1).對于任意x?G，y?G，z?G，有?x?y?z ((x°y)°z = x°(y°z)) (結合律)(2).常元素e?G，對于任意x?G，有?x (e°x= x) (左單位元)(3).對于每一元素x?G，存在元素y，使得?x?y (y°x = e)

61、 (左逆元),群運算,定義：設A，B是群G的任二非空子集，稱AB為A與B的乘運算AB={a°b|a?A?b?B}定義：設A，B是群G的任二非空子集，稱A-1為A的逆運算A-1={a-1|a?A},群包含關系（子群）,定義：設G是一個群，H是G的一個非空子集。如果H本身對G的乘法也作成一個群，則稱H為G的一個子群，記為H?G。若H是G的真子群，則簡記為H?G。H?G??x(

62、x?H?x?G){e}?G，G?G。,群的性質,群G的元素a的左逆元a-1也是a的一個右逆元。├ a°a-1=e群G的左單位元e也是G的一個右單位元。├a°e=a群G的每個元素的逆元都是唯一的。a'°a=e├a-1=a '群G的單位元是唯一的。?x (e'°x= x)├e'=e,設G為群，對于任意a?G，b?G，有(1). ├(a-1)-1=a(2). ├(a°b)-1=b-1°a-

63、1(1).├(a-1)-1=a群中運算滿足消去律。(1).a°b= a°c? b= c(2).a°c= b°c? a= b,(1).A(BC)=(AB)C(2).A(B∪C)=AB∪AC(3).(A-1) -1=A(4).(AB) -1=B-1A-1,定理證明方法,集合和邏輯表征概念、運算、關系及其定理等式形式的定理有一般的證明方法演繹形式定理有公理方法公理：邏輯公理、專用公理正確證明驗證：或者是公理或者是前

64、提或者是推導規(guī)則,主要內容,基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎,計算機專業(yè)基礎,指令集、操作系統(tǒng)和語言文法都有規(guī)范，需求明確基于需求，設計出系統(tǒng)模型判定系統(tǒng)模型正確的準則是什么？軟件測試邏輯定義功能，形式建模，定理證明用集合和邏輯進行系統(tǒng)的形式建模數(shù)字邏輯（邏輯模型）計算機組成（結構模型）操作系統(tǒng)（操作模型）編譯系統(tǒng)（語言模型）用公理系統(tǒng)方法進行形式證明證明之驗證,數(shù)字邏輯,數(shù)字邏輯是關于數(shù)字（二

65、進制數(shù)）的邏輯運算、關系判斷及操作的邏輯表示方法，以及物理實現(xiàn)。數(shù)字邏輯主要有組合邏輯和時序邏輯。數(shù)字邏輯部件組合邏輯設計，包括編碼器、譯碼器、比較器、數(shù)據選擇器、數(shù)據分配器、奇偶校驗器、算術邏輯單元、乘法器、數(shù)據擴展器等。時序邏輯設計，包括計數(shù)器、寄存器、移位器等基本問題數(shù)字邏輯的理論基礎是什么？布爾代數(shù)？數(shù)字邏輯與離散數(shù)學有什么關系？設計數(shù)字邏輯部件的一般方法是什么？,物理基礎,組合邏輯：與門、或門、非門時序邏輯：

66、D觸發(fā)器存貯單元：SRAM、DRAM,命題邏輯是數(shù)字邏輯基礎,概念與邏輯表達式數(shù)字邏輯部件功能用真值表表達功能：輸入與輸出之間的關系。結構：實現(xiàn)功能的邏輯表達式。邏輯結構的一般構建方法：給定功能真值表命題邏輯方法求出（?、?、?）邏輯范式構建邏輯部件（非門、與門、或門、寄存器）Verilog等軟件實現(xiàn),3線—8線譯碼器功能表,譯碼是的輸入是一個二進制數(shù)X，用Xn-1,…,X1,X0表示，輸出是二進制數(shù)2n-1，用Y2*

67、*n-1,…,Y1,Y0表示。,Y0 = ? X2 ? ? X1 ? ? X0Y1 = ? X2 ? ? X1 ? X0Y2= ? X2 ? X1 ? ?X0Y3 = ? X2 ? X1 ? X0,Y4= X2 ? ? X1 ? ? X0Y5 = X2 ? ? X1 ? X0Y6= X2 ? X1 ? ?X0Y7 = X2 ? X1 ? X0,一般性方法求邏輯表達式32位譯碼器Verilog程序,多路選擇器,多

68、路選擇器是一種多路數(shù)據輸入并且一路數(shù)據輸出的邏輯部件,Z0= ?C1??C0Z1= ?C1?C0Z2= C1??C0Z3= C1?C0,Yk = Z0?X0k?Z1?X1k? Z2?X2k? Z3?X3k,一般性方法求邏輯表達式,多路選擇器Verilog程序,按位邏輯運算,設a31-1~0, b31~0是32位二進制數(shù)，二進制數(shù)邏輯運算是按位做非、與、或以及異或運算，運算記為~、&、|、^，即~a31~0=(~ak)3

69、1~0a31~0& b31~0=(ak&bk) 31~0a31~0| b31~0=(ak|bk) 31~0a31~0^ b31~0=(ak^bk) 31~0,module Andmodule(A,B,D);input [31:0]A;input [31:0]B;output [31:0]D;assign D=A&B;endmoduleassign D=A|B;assign D=A

70、&~B|~A&B;,二進制加法運算,S'0= A'0+B'0，被加數(shù)位A'0，加數(shù)位B'0以及進位位C'-1，輸出有和數(shù)位S'0和進位位C'0。A'0，B'0和C'-1按二進制數(shù)相加，產生的二進制數(shù)的位20為S'0，位21為C'0。,S'0=~A'0&~B'0&C'-1|

71、~A'0&B'0&~C'-1|A'0&~B'0&~C'-1|A'0&B'0&C'-1C'0 =~A'0&B'0&C'-1|A'0&~B'0&C'-1|A'0&B'0&~C'-1|A'