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

離散數(shù)學教學的理性思考主要內(nèi)容基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎基本問題離散數(shù)學數(shù)理邏輯集合論圖論代數(shù)系統(tǒng)常識問：學習離散數(shù)學有什么有？答：離散數(shù)學是計算機專業(yè)基礎基本問題“離散數(shù)學是計算機專業(yè)基礎”是什么意思？“離散數(shù)學如何是計算機專業(yè)基礎”是什么意思？離散數(shù)學與計算機專業(yè)課程關系問題核心課程先修課程計算機導論程序設計基礎計算機導論離散結(jié)構(gòu)數(shù)學分析或高等數(shù)學算法與數(shù)據(jù)結(jié)構(gòu)高級語言程序設計、離散結(jié)構(gòu)計算機組成基礎計算機導論、數(shù)字邏輯計算機體系結(jié)構(gòu)計算機組成基礎操作系統(tǒng)算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫系統(tǒng)原理算法與數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學編譯原理程序設計、離散結(jié)構(gòu)、算法與數(shù)據(jù)結(jié)構(gòu)軟件工程程序設計、算法與數(shù)據(jù)結(jié)構(gòu)計算機圖形學程序設計、離散數(shù)學計算機網(wǎng)絡計算機導論、計算機組成、操作系統(tǒng)、算法與數(shù)據(jù)結(jié)構(gòu)人工智能高級語言程序設計、離散結(jié)構(gòu)數(shù)字邏輯計算機導論《高等學校計算機科學與技術專業(yè)發(fā)展戰(zhàn)略報告暨專業(yè)規(guī)范》為什么離散數(shù)學的前導課程是數(shù)學？為什么數(shù)字邏輯課程前導課程是計算機導論？如何體現(xiàn)離散數(shù)學課程的基礎性？計算機專業(yè)的基礎問題邏輯是所有數(shù)學推理及其所有自動推理的基礎。對于計算機的設計、系統(tǒng)規(guī)范說明、人工智能、計算機程序設計、程序設計語言以及計算機科學的其它許多領域，邏輯都有實際的應用。————KennethH.RosenACMComputerScienceCurricula2013DS.離散結(jié)構(gòu)（37個核心一級學時，4個核心二級學時）核心一級學時核心二級學時比例DS/集合、關系與函數(shù)49%DS/基礎邏輯922%DS/證明方法10127%DS/計數(shù)基礎512%DS/樹和圖3110%DS/離散概率6220%集合、基本邏輯和證明方法的知識點集合維恩圖并集、交集、補集笛卡爾積、冪集、有限集合的基數(shù)關系自反性、對稱性、傳遞性等價關系、偏序關系函數(shù)滿射、單射、雙射反函數(shù)函數(shù)的復合命題邏輯（參考：命題邏輯同時出現(xiàn)在智能系統(tǒng)/知識推理）邏輯聯(lián)結(jié)詞真值表范式（合取范式、析取范式）合式公式的有效性命題推理定律（肯定前件式和否定后件式的概念）謂詞邏輯全稱量詞與存在量詞命題邏輯和謂詞邏輯的局限蘊含、等價、逆命題、否命題、逆否命題、否定和矛盾等概念數(shù)學證明架構(gòu)直接證明反例證偽反證法數(shù)學歸納法結(jié)構(gòu)歸納法弱歸納法與強歸納法（即，第一類數(shù)學歸納法和第二類數(shù)學歸納法）數(shù)學上的遞歸定義主要內(nèi)容基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎最簡單的論域—邏輯域邏輯對象：{0,1}邏輯運算：{,,,,,}邏輯關系：{=,╞}真值表一組邏輯自變量與一個邏輯因變量的對應表真值表定義邏輯運算和關系命題邏輯公式與語言定義：(1).常量0和1是邏輯公式；(2).命題變量是邏輯公式；(3).若Q,R是邏輯公式，則(Q)、(QR)、(QR)、(QR)、(QR)、(QR)是邏輯公式；(4).只有有限次應用(1)—(3)構(gòu)成的公式是邏輯公式。真值表驗證運算性質(zhì)結(jié)合律(P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=P∧(Q∧R)(PQ)R=P(QR)分配律P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)P∧(QR)=(P∧Q)(P∧R)交換律Q∨R=R∨QQ∧R=R∧QQR=RQ德摩根律(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功能可以用真值表表達所有邏輯運算都可以表達為,

,,的運算。x0…xk…xm-1y000000……………………k100101…………………2m-11…111…邏輯哲學世界是由事實構(gòu)成的《邏輯哲學論》事實是事物的性質(zhì)，以及事物之間的關系《我們關于外間世界的知識-哲學上科學方法應用的一個領域》維特根斯坦羅素根據(jù)維特根斯坦和羅素的哲學思想，事實是表達事物的性質(zhì)或表達一些事物之間的關系。世界由事實構(gòu)成，而命題與事實對應，事實使一個命題為真或為假。最簡單的事實稱為原子事實，與原子事實對應的是原子命題。原子命題的真或假取決于它與相應的原子事實是否符合。謂詞定義：研究對象統(tǒng)稱為客體。定義：事物的性質(zhì)詞和事物的關系詞統(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關系。量詞表示所有客體具有某性質(zhì)或關系的詞稱為全稱量詞，記為x(Q(x)R(x))表示至少有一個客體具有某性質(zhì)或關系的詞稱為存在量詞，記為

x(Q(x)R(x))合式公式與一階謂詞語言定義：合式公式是按如下規(guī)則構(gòu)成的有窮長符號串。(1).若是x1,…,xn是變元，Qin是n元謂詞，則Qin(x1,…,xn)是合式公式。(2).若Q是合式公式，則(Q)是合式公式；(3).若Q和R是合式公式，則(QR)、(QR)、(QR)、(QR)及(QR)是合式公式；(4).若Q是合式公式，x是變元，則(xQ)及(xQ)是合式公式。(5).只有有限次應用(1)—(4)構(gòu)成的公式是合式公式。思想理論與邏輯語言弗雷格思想理論思想是陳述句的含義思想有真假思想有結(jié)構(gòu)思想通過語言來表達和傳遞存在判定思想同一性的標準思想影響人的意志自然語言符合邏輯語言在保持思想的情況下，自然語言變換為邏輯語言GottlobFrege1848-1925自然（科學）語言命題符合邏輯語言定義：具有確定真或假含義的陳述句稱為原子命題，或簡單命題。在自然語言中，'并且'、'或'、'并非'、'如果...，則...。'、'當且僅當'等詞也稱為聯(lián)接詞。復合語句是一些陳述句用'并且'、'或'、'并非'、'如果...，則...。'、'當且僅當'等聯(lián)接為一條語句。量化語句是用'所有'、'存在'等量詞約束陳述句或復合語句。定義：原子命題用'并且'、'或'、'并非'、'如果...，則...。'、'當且僅當'等聯(lián)接詞聯(lián)接的語句稱為復合命題。定義：用'所有'和'存在'量詞約束的原子命題或復合命題稱為量化命題。定義：原子命題、復合命題和量化命題統(tǒng)稱為命題。符號化機械過程自然語言的命題符號化方法是機械式過程，無需理解具體概念的含義，僅僅將相同的客體、函數(shù)、性質(zhì)或關系分別用相同符號表示。復合語句由簡單語句、聯(lián)接詞及量詞構(gòu)成。首先，識別出簡單語句，而后，簡單語句符號化。復合語句由符號化的簡單命題形式和聯(lián)接詞及量詞構(gòu)成。復合語句就可以根據(jù)聯(lián)接詞及量詞的含義，形成符號化的命題。符號化機械過程（續(xù)）自然知識可以表示為命題，所有的自然律也可以表達為命題。自然語言的命題符號化方法：(1).在復合語句中識別出陳述句，并用下劃線標出(2).陳述語句符號化相同（不同）的客體用相同(不同)符號表示相同（不同）函數(shù)用相同（不同）符號表示相同（不同）性質(zhì)或關系用相同（不同）符號表示(3).聯(lián)接詞及量詞符號化'并且'表示為''，'或'表示為''，'并非'表示為''，'如果...，則...。'表示為''，'當且僅當'表示為'‘'所有'表示為''，'存在'表示為''，形成符號化的命題。數(shù)學分析概念在研究過程中，首先用定義的方式給出概念，而后研究概念的性質(zhì)以及概念之間的關系，形成定理。概念的定義是復合語句，也能夠用機械方式符號化。自然語言表達序列極限、函數(shù)極限、連續(xù)、一致連續(xù)、導數(shù)等概念，人們可能有二義性理解，即人們對這些概念含義會有不同的理解。如果這些概念符號化，那么，人們對這些概念的理解就會相同。定義（極限）是命題定義：設{xn}是序列，對于任意ε>0，存在N>0，對于任何n，當n>N時，都有|xn-b|<ε，則稱序列{xn}的極限是b，記為

。(1)陳述句識別：對于所有ε，ε>0，存在N，N>0，對于任何n，當n>N時，都有|xn-b|<ε。(2).陳述句符號化：所有ε，ε>0，存在N，N>0，對于所有n，當n>N時，都有|xn-b|<ε。(3).聯(lián)接詞和量詞符號化ε(ε>0N(N>0n(n>N|xn-b|<ε)))定理是命題定理

：若序列的極限存在，則極限值唯一。ε(ε>0N1(N1>0n(n>N1|xn-a|<ε)),ε(ε>0N2(N2>0n(n>N2|xn-b|<ε))├a=b定理

：若序列{xn}有極限，則{xn}有界。ε(ε>0N(N>0n(n>N|xn-a|<ε)))├M(M>0n(n>0|xn|<M))歐幾里德幾何學歐幾里德（325BC-265BC），古希臘數(shù)學家；《幾何原本》是一個實質(zhì)公理系統(tǒng)把點、線、面、角等分為原始定義概念（23）和可定義概念；命題分為公理（5）、公設（5）；由公理公設出發(fā)加以證明的定理（467）從簡單到復雜，證明相當嚴格。從而建立了歐幾里得幾何學的第一個公理化數(shù)學體系。公設1.由任意一點到另外任意一點可以畫直線。2.一條有限直線可以繼續(xù)延長。3.以任意點為心及任意的距離可以畫圓。4.凡直角都彼此相等。5．(平行公設)若一直線與兩直線相交，且若同側(cè)所交兩內(nèi)角之和小于兩直角，則兩直線無限延長后必相交于該側(cè)的一點。公理1．等于同量的量彼此相等。2．等最加等量，其和仍相等。3，等量減等量，其差仍相等。4．彼此能重合的物體是全等的。5．整體大于部分。希爾伯特證明論通過形式化第一次使證明本身成為數(shù)學研究對象。給出初始符號集合構(gòu)造合式公式規(guī)則Γ├Q的證明，構(gòu)造出1~m個合式公式序列，其中，第m個合式公式是Q，并且1~m合式公式或者是前提或者是公理或者是推導規(guī)則形式證明正確性的驗證。DavidHilbert1826-1943邏輯證明有何不同？領域知識是提出概念，形成定理，對定理進行證明。通過思想概念的涵義以及關系，形成一個個推理步驟，最后完成證明。領域知識不同，證明方法也不同。在邏輯公理系統(tǒng)中，已知語言、公理、推理規(guī)則Γ是前提集,Q是結(jié)論Γ是語句集合，Q是語句在邏輯公理系統(tǒng)中，各個領域知識都抽象為形式語言。從形式語言表示的公理和前提集開始，一步步推理到結(jié)論。因為推理過程沒有領域概念及其涵義，僅有抽象的符號，按照推理規(guī)則一步一步進行推理，所以，推理具有統(tǒng)一方法。邏輯公理系統(tǒng)公理系統(tǒng)從一些公理出發(fā)，根據(jù)演繹法，推導出一系列定理，形成的演繹體系叫作公理系統(tǒng)。公理系統(tǒng)的組成：語言集公理集公理是用于表達推理由之出發(fā)的初始肯定命題；推理規(guī)則集推理規(guī)則是由公理及已證定理得出新定理的規(guī)則；定理集表達了肯定的所有命題。謂詞邏輯公理系統(tǒng)(1)謂詞邏輯語言：L=<{,},{},P,F,C>(2).公理集合：1).公理模式A

1：Q(RQ)2).公理模式A

2：(P(QR))((PQ)(PR))3).公理模式A3：(QR)(RQ)4).公理模式A4：xQ(x)Q(x)[x/t]

其中，項t對于Q中的x是可代入的。

5).公理模式A5：x(QR(x))(QxR(x))

其中x不是Q中自由變元。(3).推理規(guī)則1).分離規(guī)則（簡稱MP規(guī)則）：從Q和QR推出R。2).全稱概括（簡稱UG規(guī)則）：從Q(x)推出(xQ)。演繹與證明Γ├Q的證明，就是要構(gòu)造一個合式公式的變換序列，其中每一步產(chǎn)生的合式公式，并且或者是公理模式或者是前提模式或者是由分離規(guī)或者是全稱概括（謂詞邏輯）├xQ(x)yQ(y)(y不在Q中出現(xiàn))證明：

證據(jù)：A1=xQ(x)Q(y)A4

A2=y(xQ(x)Q(y))UGA3=y(xQ(x)Q(y))(xQ(x)yQ(y))A5

A4=xQ(x)yQ(y)A3=A2A4證畢定理(傳遞律)：PQ,QR├PR證明：

證據(jù)：A1=(QR)(P(QR))A1A2=QRA2

ΓA3=P(QR)A1=A2

A3

A4=(P(QR))((PQ)(PR))A2A5=(PQ)(PR)A4=A3

A5

A6=(PQ)A6

Γ

A7=(PR)A5=A6→A7證畢定律與規(guī)則思維直覺、思維定律與定理。充分理由律（三段論）：Q,QR├R傳遞律：PQ,QR├PR反證律：如果Γ,Q├R,Γ,Q├R,則Γ├Q歸謬律：如果Γ,Q├R,Γ,Q├R，則Γ├Q排中律：├(QQ)矛盾律：├(QQ)引入規(guī)則：├P(c)xP(x)選擇規(guī)則：├xP(x)P(c)命題邏輯定理├(P(QR))(Q(PR))├(QR)((PQ)(PR))├(PQ)((QR)(PR))├((PQ)(PR))(P(QR)├QQ├QQ├QQ├Q((QR)

R)

├Q(QR)R├QQQ├QQQ├(QR)(RQ)├(QR)(QR)├(QR)(QR)

├(QR)(QR)├(QR)(RQ)├(QR)(RQ)├(QR)(RQ)

├Q(QR)├(QQ)(RQ)├(QQ)Q├(QRR)Q├(QR)((QR)Q)├(QR)((QR)Q)

一階謂詞邏輯定理├xR(x)

yR(y)├xR(x)

yR(y)├Q(c)xQ(x)├Q(c)xQ(x)├xR(x)

xR(x)

├xyR(x,y)

yxR(x,y)├xyR(x,y)

yxR(x,y)├xyR(x,y)

yxR(x,y)├xyR(x,y)

xR(x,x)├xR(x,x)

xyR(x,y)├x(P(x)Q(x))(xP(x)xQ(x))├x(P(x)Q(x))(xP(x)

xQ(x))├x(P(x)Q(x))(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)xP(x)├xP(x)xP(x)├xP(x)xP(x)├

xP(x)xP(x)論域、解釋、賦值與模型在指定論域上，對于一階邏輯語言L解釋將常元指稱為論域中某客體；將謂詞指稱為論域上的關系；將函詞指稱為論域上的函數(shù)。賦值將客體變元指稱為論域中的客體。一階邏輯語言的解釋，是確定該種語言里的符號表達式同某個論域之間的聯(lián)系。論域和解釋構(gòu)成了結(jié)構(gòu)。結(jié)構(gòu)和賦值構(gòu)成了模型。一階邏輯語言的語義就是在模型上的邏輯真值。合式公式、合式公式集合與模型研究合式公式或合式公式集合QΓ={Q1,...,Qn}在一個模型上具有的性質(zhì)；在所有模型上具有的性質(zhì)真值性永真性相等性推論性存在模型可滿足性模型永真模型等值模型推論所有模型有效性邏輯永真邏輯等值邏輯推論等式關系和推論關系定義：給定一階語言L及它的兩個公式Q,R，如果存在模型M=<D,σ>，使得σ(Q)=σ(R),則稱Q與R是在模型M等值，記為QMR。定義：給定一個語言L,Γ是一個公式集合,Q是一個公式。

若存在模型M=<Dσ>，使得當σ(Γ)=1時，有σ(Q)=1，則稱Q是Γ關于模型邏輯推論，記為Γ╞MQ。定義：如果對于任意模型M=<D,σ>，都有

σ(Q)=σ(R),則稱Q與R是邏輯等價，記為QR。定義：給定一個語言L,Γ是一個公式集合,Q是一個公式。

若對于任意模型M=<D,σ>，使得當σ(Γ)=1時有σ(Q)=1，則稱Q是Γ邏輯推論，或稱Γ語義推出Q，記為Γ╞Q。前束范式定義：設δk為,量詞，x1…xn為不同變元，Q為開公式，形式為δ1x1…δnxnQ的公式稱為前束范式，稱δ1x1…δnxn為前束詞，稱Q為母式。定理：設δk為,量詞，x1…xn為不同變元，對于任意合式公式Q，存在前束范式δ1x1…δnxnR，使得Qδ1x1…δnxnR。定義：若δ1x1…δnxnQ的是前束范式，并且Q是合取范式，則稱δ1x1…δnxnQ是前束合取范式。前束范式步驟(1).依次用等值公式QR(QR)QR(QR)(RQ)QR

QR進行等值變換，產(chǎn)生的公式僅有聯(lián)結(jié)詞、、以及量詞、。(2).用等值公式QQ進行變換化簡公式。(3).根據(jù)以上等值公式，以及如下量詞變換等值公式Q(x)xQ(x)Q(x)xQ(x)(4).用德摩根律(QR)QR，(QR)QR進行化簡。重復應用(2)、(3)、(4)步驟，逐次將所有聯(lián)結(jié)詞置于原子謂詞。前束范式步驟（續(xù)）(5).用換名等值公式xQ(x)yQ(y)和xQ(x)yQ(y)將所有不同量詞轄域的變元換名為互不同的變元。(6).若x不在Q中出現(xiàn)，則QxR(x)x(QR(x))QxR(x)x(QR(x))QxR(x)x(QR(x))QxR(x)x(QR(x))δ1x1Q(x1)δ2R(x2)δ1x1δ2x2(Q(x1)R(x2))δ1x1Q(x1)δ2R(x2)δ1x1δ2x2(Q(x1)R(x2))重復應用(6)步驟，逐次將量詞前置，使得公式變換為前束范式。(7).用等值變換交換量詞次序xyQ(x,y)yxQ(x,y)xyQ(x,y)yxQ(x,y)等式演算一般方法命題公式:Q的范式是Q'，R的范式是R'，因為QQ'，

Q'R'，R'R。所以QR謂詞公式:Q的前束合取范式是Q'，R的前束合取范式是R'，因為QQ'，

Q'R'，R'R。所以QR主要內(nèi)容基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎結(jié)構(gòu)主義在《結(jié)構(gòu)主義》中，皮亞杰給出結(jié)構(gòu)特征結(jié)構(gòu)由對象集合S以及關系集合R、運算集合F和常元集合C組成，<S,R,F,C>整體性、轉(zhuǎn)換、自身調(diào)整性結(jié)構(gòu)主義是知識表征的重要方法從結(jié)構(gòu)主義觀點看集合論性質(zhì)定義概念外延與內(nèi)涵圖論結(jié)構(gòu)集合定義概念代數(shù)系統(tǒng)操作定義概念定義運算保持封閉性定義關系洞察性質(zhì)，形成定理邏輯表達概念、運算和關系一般方法證明等式演繹形式證明命題的邏輯構(gòu)造基本概念與導出概念命題：概念定義是命題。運算定義是命題。關系定義是命題。定理是命題。邏輯命題能由自然語言描述機械式的變換為邏輯描述。聯(lián)接詞,,,,量詞,謂詞、函詞和常元邏輯命題是形式的。集合基本概念、概括性公理集合是一些能夠明確區(qū)分的對象構(gòu)成的整體。集合一般用大寫英文字母表示，構(gòu)成集合的對象稱為元素，一般用小寫英文字母表示。元素與集合有“屬于”基本關系，關系如果對象a在集合A中，則稱a是A的元素，或者a屬于A，記為aA，否則記為aA。概括性公理謂詞ψ(x)是給定的一個性質(zhì)，則ψ(x)確定唯一一個集合。設A={x|ψ(x)}，滿足性質(zhì)ψ(x)的對象都在A中，不滿足該性質(zhì)的對象都不在A中。即x(ψ(x)xA)關系定義設X，Y是集合，若RXY，則稱R為從X到Y(jié)的關系，簡稱為關系R。 R={<x,y>|xXyY}若R是從X到Y(jié)的關系，就是集合X中元素與集合Y中元素之間的對應。函數(shù)定義：設f是從集合X到Y(jié)的關系若對每個xX存在唯一yY使得<x,y>f，則稱f為從X到Y(jié)的函數(shù)(映射)，記為f:XY。從X到Y(jié)的函數(shù)指的是單值全函數(shù)，滿足 fXYdom(f)=Xran(f)Y <x,y>f<x,z>fy=z滿射、單射和雙射定義：設函數(shù)f:XY，(1).若對于每個yY，都存在xX使得f(x)=y，則稱f為滿射，即y(yYx(xXf(x)=y))(2).若對于任意xX,yY，只要f(x)=f(y)，就有x=y，或只要xy，就有f(x)f(y)，則稱f為單射，即xy(xXyXf(x)=f(y)x=y)(3).若函數(shù)f既是單射又是滿射，則稱f為雙射，也稱為一一對應。單調(diào)性函數(shù)定義：設X，Y為集合，≤是全序關系，f:XY，(1).如果對于任意x1<x2，則f(x1)≤f(x2)，則稱f是單調(diào)遞增的x1x2(x1<x2f(x1)≤f(x2))(2).如果對于任意x1<x2，則f(x1)<f(x2)，則稱f是嚴格單調(diào)遞增的x1x2(x1<x2f(x1)<f(x2))(3).如果對于任意x1<x2，則f(x1)≥f(x2)，則稱f是單調(diào)遞減的x1x2(x1<x2f(x1)≥f(x2))(4).如果對于任意x1<x2，則f(x1)>f(x2)，則稱f是嚴格單調(diào)遞減的x1x2(x1<x2f(x1)>f(x2))集合運算定義：設A,B為二集合，稱由A和B的所有元素組成的集合為A與B的并集，記作AB，稱為并運算符。 AB={x|xAxB}AB={x|xAxB}交運算A-B={x|xAxB}差運算A+B={x|xAxB}對稱差運算A={x|xA}補運算集合運算也是由集合及“”這兩個基本概念的導出概念。關系運算定義：設關系R和S是從X到Y(jié)的兩個關系，則RS,RS,RS,R+S,R為RS={<x,y>|<x,y>R<x,y>S}RS={<x,y>|<x,y>R<x,y>S}RS={<x,y>|<x,y>R<x,y>S}R+S={<x,y>|<x,y>R<x,y>S}R={<x,y>|<x,y>R}復合運算、指數(shù)運算及逆運算R°S={<x,z>|y(<x,y>R<y,z>S}Rn+1=Rn

°R（R0=IX）R1={<y,x>|<x,y>R}集合相等關系定義(外延性公理）：如果集合A和B含有相同的元素，則稱A和B相等，記為A=B。A=Bx(xAxB)

x(xAxB)x(xBxA)其中表示當且僅當關系。在數(shù)理邏輯證明中，用“符號”代替集合符號“”。集合的“=”是集合之間的一種關系，即相等關系；這個等關系也可以是表示相等謂詞。謂詞“=”概念是由集合及“”這兩個基本概念的導出概念。集合包含關系（子集）定義

若集合A的元素都是集合B的元素，則稱A是B的子集，也稱A包含于B，或者B包含A，記為AB或BA。ABx(xAxB)定義

若AB且AB，則稱A是B的真子集，也稱A真包含于B，或者B真包含A，記為AB或BA。ABx(xAxB)

x(xBxA)關系“”和“”概念也是由集合及“”這兩個基本概念的導出概念。在數(shù)理邏輯證明中，“”和“”也可以看作是包含謂詞。集合運算性質(zhì)結(jié)合律

(AB)C=A(BC)(AB)C=A(BC)交換律AB=BAAB=BA分配律A(BC)=(AB)(AC)A(BC)=(AB)(AC)德摩根律(AB)=A

B(AB)=A

B冪等律AA=AAA=A吸收律A(AB)=AA(AB)=A同一律A

=AAU=A零

律A

=AU=U互補律A

A=A

A=U 對合律

A=A

=U U=關系運算性質(zhì)

(R1°R2)°R3=R1°(R2°R3)(R1

R2)°R3=R1°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°R3RmRn=Rm+n(Rn)m=Rmn(R1R2)-1=R1-1R2-1(R1R2)-1=R1-1R2-1(R1-R2)-1=R1-1-R2-1(~R1)-1=~R1-1

(R°S)1=S1

°R1函數(shù)運算性質(zhì)定理：設f:XY，則f°

IX=IY

°

f=f。定理

設f:XY，g:YZ，h:ZW，則 h°

(g°

f)=(h°

g)°

f定理：設f是從X到Y(jié)的函數(shù)，g是從Y到Z的函數(shù)。

若f和g都是滿射，則g°

f是滿射。

若f和g都是單射，則g°

f是單射。

若f和g都是雙射，則g°

f是雙射。定理：設f是從X到Y(jié)的函數(shù)，g是從Y到Z的函數(shù)。

若g°f是滿射，則g是滿射。

若g°f是單射，則f是單射。

若g°f是雙射，則g是滿射，f是單射。函數(shù)運算性質(zhì)（續(xù)）性質(zhì)：f滿足單值性當且僅當f1滿足唯一性性質(zhì)：f滿足唯一性當且僅當f1滿足單值性定理：設f:XY是雙射函數(shù)，則存在逆函數(shù)f1:YX，并且f1是雙射函數(shù)。定理

若f:XY是可逆的，則 f1

°

f=IX且f°f1=IY定理：設雙射f:XY及雙射g:YX，g=f1，當且僅當g°f=IX

且f°g=IY。定理若雙射f:XY及雙射g:YZ，則g°f也是雙射，并且(g°f)1=f1

°g1

。定理：設f是從X到Y(jié)的函數(shù)，g是從Y到Z的函數(shù)，若f和g是單調(diào)增加的，則g°f是單調(diào)增加的。用集合和邏輯定義圖概念定義：設V是一個非空頂點集合，E是無向邊集合，V和E的有序偶稱為無向圖G，記為G=<V,E>，其中 E={(x,y)|xVyV}定義：設V是一個非空頂點集合，E是有向邊集合，V和E的有序偶稱為有向圖D，記為D=<V,E>，其中E={<x,y>|xVyV}圖的基本結(jié)構(gòu)是指圖的頂點之間，邊之間及邊與頂點之間的連接關系。頂點之間是鄰接關系頂點與邊是關聯(lián)關系邊與邊是相鄰關系圖包含關系（子圖）定義（子圖）：設G=<V,E>和GS=<VS,ES>是兩個圖。若VSV并且ESE則稱GS是G的子圖。

記為GSG。如果GS是子圖并且VSV或ESE，則稱GS是G的真子圖，記為GSG。 GSGVSVESE GSGGSG(VSVESE)定義（導出子圖）：設GS=<VS,ES>是G=<V,E>子圖。如果ES是E中所有只關聯(lián)于VS中的頂點的邊的集合，則稱GS為VS所導出的子圖，簡稱圖G的導出子圖，即 ES={e|uVS

vVSe=(u,v)E}定義（生成子圖）：設圖GS=<VS,ES>是圖G=<V,E>的子圖。如果VS=V，則稱GS為G的生成子圖。 GS

GVS=V典型圖問題（集合和邏輯表征）連通性穿程問題歐拉圖、哈密頓圖通路問題最短通路、關鍵通路樹二叉樹、生成樹二分圖及匹配問題圖著色問題平面圖群的基本概念定義：設G是一個非空集合，°是二元代數(shù)運算，如果滿足以下條件：(1).代數(shù)運算°滿足結(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ù)運算°作成一個群。群是用運算定義概念群（公理）群理論可以采用數(shù)理邏輯方法表示，它有3條公理。定義：設<G,°>是一個代數(shù)系統(tǒng)，<G,°>稱為一個群，如果滿足以下條件：(1).對于任意xG，yG，zG，有xyz((x°y)°z=x°(y°z))(結(jié)合律)(2).常元素eG，對于任意xG，有x(e°x=x)(左單位元)(3).對于每一元素xG，存在元素y，使得xy(y°x=e)(左逆元)群運算定義：設A，B是群G的任二非空子集，稱AB為A與B的乘運算 AB={a°b|aAbB}定義：設A，B是群G的任二非空子集，稱A-1為A的逆運算 A-1={a-1|aA}群包含關系（子群）定義：設G是一個群，H是G的一個非空子集。

如果H本身對G的乘法也作成一個群，則稱H為G的一個子群，記為HG。

若H是G的真子群，則簡記為HG。 HGx(xHxG) {e}G，GG。群的性質(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設G為群，對于任意aG，bG，有(1).├(a-1)-1=a(2).├(a°b)-1=b-1°a-1(1).├(a-1)-1=a群中運算滿足消去律。(1).a°b=a°cb=c(2).a°c=b°ca=b(1).A(BC)=(AB)C(2).A(B∪C)=AB∪AC(3).(A-1)

-1=A(4).(AB)

-1=B-1A-1定理證明方法集合和邏輯表征概念、運算、關系及其定理等式形式的定理有一般的證明方法演繹形式定理有公理方法公理：邏輯公理、專用公理正確證明驗證：或者是公理或者是前提或者是推導規(guī)則主要內(nèi)容基本問題數(shù)理邏輯數(shù)理邏輯是基礎離散數(shù)學是基礎計算機專業(yè)基礎指令集、操作系統(tǒng)和語言文法都有規(guī)范，需求明確基于需求，設計出系統(tǒng)模型判定系統(tǒng)模型正確的準則是什么？軟件測試邏輯定義功能，形式建模，定理證明用集合和邏輯進行系統(tǒng)的形式建模數(shù)字邏輯（邏輯模型）計算機組成（結(jié)構(gòu)模型）操作系統(tǒng)（操作模型）編譯系統(tǒng)（語言模型）用公理系統(tǒng)方法進行形式證明證明之驗證數(shù)字邏輯數(shù)字邏輯是關于數(shù)字（二進制數(shù)）的邏輯運算、關系判斷及操作的邏輯表示方法，以及物理實現(xiàn)。數(shù)字邏輯主要有組合邏輯和時序邏輯。數(shù)字邏輯部件組合邏輯設計，包括編碼器、譯碼器、比較器、數(shù)據(jù)選擇器、數(shù)據(jù)分配器、奇偶校驗器、算術邏輯單元、乘法器、數(shù)據(jù)擴展器等。時序邏輯設計，包括計數(shù)器、寄存器、移位器等基本問題數(shù)字邏輯的理論基礎是什么？布爾代數(shù)？數(shù)字邏輯與離散數(shù)學有什么關系？設計數(shù)字邏輯部件的一般方法是什么？物理基礎組合邏輯：與門、或門、非門時序邏輯：D觸發(fā)器存貯單元：SRAM、DRAM命題邏輯是數(shù)字邏輯基礎概念與邏輯表達式數(shù)字邏輯部件功能用真值表表達功能：輸入與輸出之間的關系。結(jié)構(gòu)：實現(xiàn)功能的邏輯表達式。邏輯結(jié)構(gòu)的一般構(gòu)建方法：給定功能真值表命題邏輯方法求出（、、）邏輯范式構(gòu)建邏輯部件（非門、與門、或門、寄存器）Verilog等軟件實現(xiàn)3線—8線譯碼器功能表譯碼是的輸入是一個二進制數(shù)X，用Xn-1,…,X1,X0表示，輸出是二進制數(shù)2n-1，用Y2**n-1,…,Y1,Y0表示。輸入輸出X2X1X0Y7Y6Y5Y4Y3Y2Y1Y00000000000100100000010010000001000110000100010000010000101001000001100100000011110000000Y0=

X2

X1X0Y1=

X2

X1X0Y2=

X2X1X0Y3=

X2

X1X0Y4=

X2

X1X0Y5=

X2

X1X0Y6=

X2X1X0Y7=

X2

X1X0一般性方法求邏輯表達式32位譯碼器Verilog程序多路選擇器多路選擇器是一種多路數(shù)據(jù)輸入并且一路數(shù)據(jù)輸出的邏輯部件輸入輸出C1C0X0kX1kX2kX3kYk00D0k×××D0k01×D1k××D1k10××D2k×D2k11×××D3kD3kZ0=C1C0Z1=C1C0Z2=C1C0Z3=C1C0Yk=Z0X0kZ1X1kZ2X2kZ3X3k一般性方法求邏輯表達式多路選擇器Verilog程序按位邏輯運算設a31-1~0,b31~0是32位二進制數(shù)，二進制數(shù)邏輯運算是按位做非、與、或以及異或運算，運算記為~、&、|、^，即~a31~0=(~ak)31~0a31~0&b31~0=(ak&bk)31~0a31~0|b31~0=(ak|bk)31~0a31~0^b31~0=(ak^bk)31~0moduleAndmodule(A,B,D); input[31:0]A; input[31:0]B; output[31:0]D; assignD=A&B; endmoduleassignD=A|B;assignD=A&~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ù)相加，產(chǎn)生的二進制數(shù)的位20為S'0，位21為C'0。輸入輸出A'0B'0C'-1S'0C'00000000110010100110110010101011100111111S'0=~A'0&~B'0&C'-1|~A'0&B'0&~C'-1|A'0&~B'0&~C'-1|A'0&B'0&C'-1C'0=~