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

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

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

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

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

5、邏輯公式；(3).若Q,R是邏輯公式，則(?Q)、(Q?R) 、(Q?R) 、(Q?R) 、(Q?R) 、(Q?R)是邏輯公式；(4).只有有限次應(yīng)用(1)—(3)構(gòu)成的公式是邏輯公式。,真值表驗(yàn)證運(yùn)算性質(zhì),結(jié)合律(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,邏輯表達(dá)式一般方法,若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功能可以用真值表表達(dá)所有邏輯運(yùn)算都可以表達(dá)為?, ? ,?,的運(yùn)算。,邏輯哲

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

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

9、 ?x(Q(x)?R(x))表示至少有一個客體具有某性質(zhì)或關(guān)系的詞稱為存在量詞，記為? ?x(Q(x)?R(x)),合式公式與一階謂詞語言,定義：合式公式是按如下規(guī)則構(gòu)成的有窮長符號串。(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).只有有限次應(yīng)用(1)—(4)構(gòu)成的公式是合式公式。,思想理論與邏輯語言,弗雷格思想理論思想是陳述句的含義思想有真假思想有結(jié)構(gòu)思想通過語言來表達(dá)和傳遞存在判定思想同一性的標(biāo)準(zhǔn)思想影響人的意志自然語言符合邏輯語言在保持思想的情況下，自然語言變換為邏輯語言,Gottlob Frege 1848-1925,自然（科學(xué)）

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

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

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

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

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

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

17、0，對于所有n，當(dāng)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)),歐幾里德幾何學(xué),

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

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

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

21、示的公理和前提集開始，一步步推理到結(jié)論。因?yàn)橥评磉^程沒有領(lǐng)域概念及其涵義，僅有抽象的符號，按照推理規(guī)則一步一步進(jìn)行推理，所以，推理具有統(tǒng)一方法。,邏輯公理系統(tǒng),公理系統(tǒng)從一些公理出發(fā)，根據(jù)演繹法，推導(dǎo)出一系列定理，形成的演繹體系叫作公理系統(tǒng)。公理系統(tǒng)的組成：語言集公理集公理是用于表達(dá)推理由之出發(fā)的初始肯定命題；推理規(guī)則集推理規(guī)則是由公理及已證定理得出新定理的規(guī)則；定理集表達(dá)了肯定的所有命題。,謂詞邏輯公理系統(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] 其中，項(xiàng)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的證明，就是要構(gòu)造一個合式公式的變換序列，其中每一步產(chǎn)生的合式公式，并且或者是公理模式或者是前提模式或者是由分離規(guī)

24、或者是全稱概括（謂詞邏輯）,├ ?xQ(x)??yQ(y) (y不在Q中出現(xiàn)),證明： 證據(jù)：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,證明： 證據(jù)：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解釋將常元指稱為論域中某客體；將謂詞指稱為論域上的關(guān)系；將函詞指稱為論域上的函數(shù)。賦值將客體變元指稱為論域中的客體。一階邏輯語言的解釋，是確定該種語言里的符號表達(dá)式同某個論域之間的聯(lián)系。論域和解釋構(gòu)成了結(jié)構(gòu)。結(jié)構(gòu)和賦值構(gòu)成了模型。一階邏輯語言的語義就是在模型上的邏輯真值。,合式公式、合式公式集合與模型,研究合式公式或合式公式集合QΓ= {Q1,...,Qn}在一個模型上具有的性質(zhì)；在所有

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

35、定義：給定一個語言L , Γ是一個公式集合, Q 是一個公式。 若對于任意模型M=，使得當(dāng)σ(Γ)=1時有σ(Q)=1，則稱Q 是Γ邏輯推論，或稱Γ語義推出Q，記為Γ╞Q。,前束范式,定義：設(shè)δk為?,?量詞，x1…xn為不同變元，Q為開公式，形式為δ1x1…δn xnQ的公式稱為前束范式， 稱δ1x1…δn xn為前束詞，稱Q為母式。定理：設(shè)δ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進(jìn)行等值變換，產(chǎn)生的公式僅有聯(lián)結(jié)詞?、?、?以及量詞?、?。(2). 用等值公

37、式??Q?Q進(jìn)行變換化簡公式。(3).根據(jù)以上等值公式，以及如下量詞變換等值公式??Q(x) ??x?Q(x)??Q(x) ??x?Q(x)(4).用德?摩根律?(Q?R) ??Q??R，?(Q?R) ??Q??R進(jìn)行化簡。重復(fù)應(yīng)用(2)、(3)、(4)步驟，逐次將所有聯(lián)結(jié)詞?置于原子謂詞。,前束范式步驟（續(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))重復(fù)應(yīng)用(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 '，因?yàn)?Q?Q '， Q '?R '，R' ?R 。所以Q?R謂詞公式:Q的前束合取范式是Q ' ，R的前束合取范式是R '，因?yàn)?Q?Q '， Q '?R

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

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

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

43、x ?X?y ?Y}若R 是從X到Y(jié)的關(guān)系，就是集合X中元素與集合Y中元素之間的對應(yīng)。,函數(shù),定義：設(shè) f 是從集合 X 到 Y 的關(guān)系若對每個 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è)函數(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為雙射，也稱為一一對應(yīng)。,單調(diào)性函數(shù),定義：設(shè)X，Y為集合，≤是全序關(guān)系，f: X?Y，(1).如果對于任意x1f(x2)，則稱f是嚴(yán)格單調(diào)遞減的? x1? x2(x1f(x2)),集合運(yùn)算,定義：設(shè)A,B為二集合，稱由A和B的所有元素組成的集合為A與B的并集，記作A ? B，稱?為并運(yùn)算符。A ? B ={ x | x?A ? x?B}A ?B ={ x | x?A ?x?B}

46、 交運(yùn)算A-B ={ x | x?A ?x?B} 差運(yùn)算A+B ={ x | x?A ?x?B} 對稱差運(yùn)算?A ={ x | x?A } 補(bǔ)運(yùn)算集合運(yùn)算也是由集合及“?”這兩個基本概念的導(dǎo)出概念。,關(guān)系運(yùn)算,定義：設(shè)關(guān)系R和S是從X到Y(jié)的兩個關(guān)系，則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}復(fù)合運(yùn)算、指數(shù)運(yùn)算及逆運(yùn)算R°S = { | ?y(?R??S}Rn+1 = Rn ° R（ R0 = IX ）R?1 = { | ?R},集合相等關(guān)系,定義(外延性公理）： 如果集合A 和B 含有相同的元素，則稱A 和B相等，記為A = B。 A = B ??x (x?A? x?B)??

48、x (x?A? x?B)??x (x?B? x?A)其中?表示當(dāng)且僅當(dāng)關(guān)系。在數(shù)理邏輯證明中，用“符號?”代替集合符號“?”。集合的“=”是集合之間的一種關(guān)系，即相等關(guān)系；這個等關(guān)系也可以是表示相等謂詞。謂詞“=”概念是由集合及“?”這兩個基本概念的導(dǎo)出概念。,集合包含關(guān)系（子集）,定義 若集合 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)關(guān)系“?”和“?”概念也是由集合及“?”這兩個基本概念的導(dǎo)出概念。在數(shù)理邏輯證明中，“?”和“?”也可以看作是包含謂詞。,集合運(yùn)算性質(zhì),結(jié)合律 (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 互補(bǔ)律A ? ? A = ? A ? ? A = U 對合律 ? ? A = A ? ? = U ? U = ?,關(guān)系運(yùn)算性質(zhì),(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ù)運(yùn)算性質(zhì),定理：設(shè)f : X ? Y，則f ° IX = IY ° f = f。定理 設(shè) f : X ? Y， g : Y ? Z， h : Z ? W，則h ° ( g ° f ) = (h ° g ) ° f 定理：設(shè) f 是從 X 到 Y 的函數(shù)，g 是從 Y 到 Z 的函數(shù)。若 f 和 g 都是滿射，則

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

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

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

57、{|x?V?y?V}圖的基本結(jié)構(gòu)是指圖的頂點(diǎn)之間，邊之間及邊與頂點(diǎn)之間的連接關(guān)系。頂點(diǎn)之間是鄰接關(guān)系頂點(diǎn)與邊是關(guān)聯(lián)關(guān)系邊與邊是相鄰關(guān)系,圖包含關(guān)系（子圖）,定義（子圖）：設(shè)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)定義（導(dǎo)出子圖）：設(shè)

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

59、面圖,群的基本概念,定義：設(shè)G是一個非空集合，°是二元代數(shù)運(yùn)算，如果滿足以下條件：(1).代數(shù)運(yùn)算°滿足結(jié)合律，即對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ù)運(yùn)算°作成一個群。群是用運(yùn)算定義概念,群（公理）,群理論可以采用數(shù)理邏輯方法表示，它有3條

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

61、 (左逆元),群運(yùn)算,定義：設(shè)A，B是群G的任二非空子集，稱AB為A與B的乘運(yùn)算AB={a°b|a?A?b?B}定義：設(shè)A，B是群G的任二非空子集，稱A-1為A的逆運(yùn)算A-1={a-1|a?A},群包含關(guān)系（子群）,定義：設(shè)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。,群的性質(zhì),群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,設(shè)G為群，對于任意a?G，b?G，有(1). ├(a-1)-1=a(2). ├(a°b)-1=b-1°a-

63、1(1).├(a-1)-1=a群中運(yùn)算滿足消去律。(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,定理證明方法,集合和邏輯表征概念、運(yùn)算、關(guān)系及其定理等式形式的定理有一般的證明方法演繹形式定理有公理方法公理：邏輯公理、專用公理正確證明驗(yàn)證：或者是公理或者是前

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

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

66、D觸發(fā)器存貯單元：SRAM、DRAM,命題邏輯是數(shù)字邏輯基礎(chǔ),概念與邏輯表達(dá)式數(shù)字邏輯部件功能用真值表表達(dá)功能：輸入與輸出之間的關(guān)系。結(jié)構(gòu)：實(shí)現(xiàn)功能的邏輯表達(dá)式。邏輯結(jié)構(gòu)的一般構(gòu)建方法：給定功能真值表命題邏輯方法求出（?、?、?）邏輯范式構(gòu)建邏輯部件（非門、與門、或門、寄存器）Verilog等軟件實(shí)現(xiàn),3線—8線譯碼器功能表,譯碼是的輸入是一個二進(jìn)制數(shù)X，用Xn-1,…,X1,X0表示，輸出是二進(jìn)制數(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,一般性方法求邏輯表達(dá)式32位譯碼器Verilog程序,多路選擇器,多

68、路選擇器是一種多路數(shù)據(jù)輸入并且一路數(shù)據(jù)輸出的邏輯部件,Z0= ?C1??C0Z1= ?C1?C0Z2= C1??C0Z3= C1?C0,Yk = Z0?X0k?Z1?X1k? Z2?X2k? Z3?X3k,一般性方法求邏輯表達(dá)式,多路選擇器Verilog程序,按位邏輯運(yùn)算,設(shè)a31-1~0, b31~0是32位二進(jìn)制數(shù)，二進(jìn)制數(shù)邏輯運(yùn)算是按位做非、與、或以及異或運(yùn)算，運(yùn)算記為~、&、|、^，即~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;,二進(jìn)制加法運(yùn)算,S'0= A'0+B'0，被加數(shù)位A'0，加數(shù)位B'0以及進(jìn)位位C'-1，輸出有和數(shù)位S'0和進(jìn)位位C'0。A'0，B'0和C'-1按二進(jìn)制數(shù)相加，產(chǎn)生的二進(jìn)制數(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'