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

離散數(shù)學(xué)教學(xué)的理性思考主要內(nèi)容基本問(wèn)題數(shù)理邏輯數(shù)理邏輯是基礎(chǔ)離散數(shù)學(xué)是基礎(chǔ)基本問(wèn)題離散數(shù)學(xué)數(shù)理邏輯集合論圖論代數(shù)系統(tǒng)常識(shí)問(wèn)：學(xué)習(xí)離散數(shù)學(xué)有什么有？答：離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)基礎(chǔ)基本問(wèn)題“離散數(shù)學(xué)是計(jì)算機(jī)專業(yè)基礎(chǔ)”是什么意思？“離散數(shù)學(xué)如何是計(jì)算機(jī)專業(yè)基礎(chǔ)”是什么意思？離散數(shù)學(xué)與計(jì)算機(jī)專業(yè)課程關(guān)系問(wèn)題核心課程先修課程計(jì)算機(jī)導(dǎo)論程序設(shè)計(jì)基礎(chǔ)計(jì)算機(jī)導(dǎo)論離散結(jié)構(gòu)數(shù)學(xué)分析或高等數(shù)學(xué)算法與數(shù)據(jù)結(jié)構(gòu)高級(jí)語(yǔ)言程序設(shè)計(jì)、離散結(jié)構(gòu)計(jì)算機(jī)組成基礎(chǔ)計(jì)算機(jī)導(dǎo)論、數(shù)字邏輯計(jì)算機(jī)體系結(jié)構(gòu)計(jì)算機(jī)組成基礎(chǔ)操作系統(tǒng)算法與數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)庫(kù)系統(tǒng)原理算法與數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)編譯原理程序設(shè)計(jì)、離散結(jié)構(gòu)、算法與數(shù)據(jù)結(jié)構(gòu)軟件工程程序設(shè)計(jì)、算法與數(shù)據(jù)結(jié)構(gòu)計(jì)算機(jī)圖形學(xué)程序設(shè)計(jì)、離散數(shù)學(xué)計(jì)算機(jī)網(wǎng)絡(luò)計(jì)算機(jī)導(dǎo)論、計(jì)算機(jī)組成、操作系統(tǒng)、算法與數(shù)據(jù)結(jié)構(gòu)人工智能高級(jí)語(yǔ)言程序設(shè)計(jì)、離散結(jié)構(gòu)數(shù)字邏輯計(jì)算機(jī)導(dǎo)論《高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略報(bào)告暨專業(yè)規(guī)范》為什么離散數(shù)學(xué)的前導(dǎo)課程是數(shù)學(xué)？為什么數(shù)字邏輯課程前導(dǎo)課程是計(jì)算機(jī)導(dǎo)論？如何體現(xiàn)離散數(shù)學(xué)課程的基礎(chǔ)性？計(jì)算機(jī)專業(yè)的基礎(chǔ)問(wèn)題邏輯是所有數(shù)學(xué)推理及其所有自動(dòng)推理的基礎(chǔ)。對(duì)于計(jì)算機(jī)的設(shè)計(jì)、系統(tǒng)規(guī)范說(shuō)明、人工智能、計(jì)算機(jī)程序設(shè)計(jì)、程序設(shè)計(jì)語(yǔ)言以及計(jì)算機(jī)科學(xué)的其它許多領(lǐng)域，邏輯都有實(shí)際的應(yīng)用?！狵ennethH.RosenACMComputerScienceCurricula2013DS.離散結(jié)構(gòu)（37個(gè)核心一級(jí)學(xué)時(shí)，4個(gè)核心二級(jí)學(xué)時(shí)）核心一級(jí)學(xué)時(shí)核心二級(jí)學(xué)時(shí)比例DS/集合、關(guān)系與函數(shù)49%DS/基礎(chǔ)邏輯922%DS/證明方法10127%DS/計(jì)數(shù)基礎(chǔ)512%DS/樹和圖3110%DS/離散概率6220%集合、基本邏輯和證明方法的知識(shí)點(diǎn)集合維恩圖并集、交集、補(bǔ)集笛卡爾積、冪集、有限集合的基數(shù)關(guān)系自反性、對(duì)稱性、傳遞性等價(jià)關(guān)系、偏序關(guān)系函數(shù)滿射、單射、雙射反函數(shù)函數(shù)的復(fù)合命題邏輯（參考：命題邏輯同時(shí)出現(xiàn)在智能系統(tǒng)/知識(shí)推理）邏輯聯(lián)結(jié)詞真值表范式（合取范式、析取范式）合式公式的有效性命題推理定律（肯定前件式和否定后件式的概念）謂詞邏輯全稱量詞與存在量詞命題邏輯和謂詞邏輯的局限蘊(yùn)含、等價(jià)、逆命題、否命題、逆否命題、否定和矛盾等概念數(shù)學(xué)證明架構(gòu)直接證明反例證偽反證法數(shù)學(xué)歸納法結(jié)構(gòu)歸納法弱歸納法與強(qiáng)歸納法（即，第一類數(shù)學(xué)歸納法和第二類數(shù)學(xué)歸納法）數(shù)學(xué)上的遞歸定義主要內(nèi)容基本問(wèn)題數(shù)理邏輯數(shù)理邏輯是基礎(chǔ)離散數(shù)學(xué)是基礎(chǔ)最簡(jiǎn)單的論域—邏輯域邏輯對(duì)象：{0,1}邏輯運(yùn)算：{,,,,,}邏輯關(guān)系：{=,╞}真值表一組邏輯自變量與一個(gè)邏輯因變量的對(duì)應(yīng)表真值表定義邏輯運(yùn)算和關(guān)系命題邏輯公式與語(yǔ)言定義：(1).常量0和1是邏輯公式；(2).命題變量是邏輯公式；(3).若Q,R是邏輯公式，則(Q)、(QR)、(QR)、(QR)、(QR)、(QR)是邏輯公式；(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)(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邏輯表達(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)算。x0…xk…xm-1y000000……………………k100101…………………2m-11…111…邏輯哲學(xué)世界是由事實(shí)構(gòu)成的《邏輯哲學(xué)論》事實(shí)是事物的性質(zhì)，以及事物之間的關(guān)系《我們關(guān)于外間世界的知識(shí)-哲學(xué)上科學(xué)方法應(yīng)用的一個(gè)領(lǐng)域》維特根斯坦羅素根據(jù)維特根斯坦和羅素的哲學(xué)思想，事實(shí)是表達(dá)事物的性質(zhì)或表達(dá)一些事物之間的關(guān)系。世界由事實(shí)構(gòu)成，而命題與事實(shí)對(duì)應(yīng)，事實(shí)使一個(gè)命題為真或?yàn)榧?。最?jiǎn)單的事實(shí)稱為原子事實(shí)，與原子事實(shí)對(duì)應(yīng)的是原子命題。原子命題的真或假取決于它與相應(yīng)的原子事實(shí)是否符合。謂詞定義：研究對(duì)象統(tǒng)稱為客體。定義：事物的性質(zhì)詞和事物的關(guān)系詞統(tǒng)稱為謂詞。謂詞可以表示為Q(x1,...,xn)，其中，Q是謂詞，x1,...,xn是客體Q(x)是一元謂詞，Q(x,y)二元謂詞，Q(x1,...,xn)是n元謂詞。謂詞對(duì)于任意客體都有真值。謂詞形式如果謂詞形式是Q(x)表示客體x有Q性質(zhì)；如果謂詞形式是Q(x1,...,xn)表示客體x1,...,xn之間有Q關(guān)系。量詞表示所有客體具有某性質(zhì)或關(guān)系的詞稱為全稱量詞，記為x(Q(x)R(x))表示至少有一個(gè)客體具有某性質(zhì)或關(guān)系的詞稱為存在量詞，記為

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

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

其中，項(xiàng)t對(duì)于Q中的x是可代入的。

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

其中x不是Q中自由變?cè)?3).推理規(guī)則1).分離規(guī)則（簡(jiǎn)稱MP規(guī)則）：從Q和QR推出R。2).全稱概括（簡(jiǎn)稱UG規(guī)則）：從Q(x)推出(xQ)。演繹與證明Γ├Q的證明，就是要構(gòu)造一個(gè)合式公式的變換序列，其中每一步產(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)論域、解釋、賦值與模型在指定論域上，對(duì)于一階邏輯語(yǔ)言L解釋將常元指稱為論域中某客體；將謂詞指稱為論域上的關(guān)系；將函詞指稱為論域上的函數(shù)。賦值將客體變?cè)阜Q為論域中的客體。一階邏輯語(yǔ)言的解釋，是確定該種語(yǔ)言里的符號(hào)表達(dá)式同某個(gè)論域之間的聯(lián)系。論域和解釋構(gòu)成了結(jié)構(gòu)。結(jié)構(gòu)和賦值構(gòu)成了模型。一階邏輯語(yǔ)言的語(yǔ)義就是在模型上的邏輯真值。合式公式、合式公式集合與模型研究合式公式或合式公式集合QΓ={Q1,...,Qn}在一個(gè)模型上具有的性質(zhì)；在所有模型上具有的性質(zhì)真值性永真性相等性推論性存在模型可滿足性模型永真模型等值模型推論所有模型有效性邏輯永真邏輯等值邏輯推論等式關(guān)系和推論關(guān)系定義：給定一階語(yǔ)言L及它的兩個(gè)公式Q,R，如果存在模型M=<D,σ>，使得σ(Q)=σ(R),則稱Q與R是在模型M等值，記為QMR。定義：給定一個(gè)語(yǔ)言L,Γ是一個(gè)公式集合,Q是一個(gè)公式。

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

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

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

QR進(jìn)行等值變換，產(chǎn)生的公式僅有聯(lián)結(jié)詞、、以及量詞、。(2).用等值公式QQ進(jìn)行變換化簡(jiǎn)公式。(3).根據(jù)以上等值公式，以及如下量詞變換等值公式Q(x)xQ(x)Q(x)xQ(x)(4).用德摩根律(QR)QR，(QR)QR進(jìn)行化簡(jiǎn)。重復(fù)應(yīng)用(2)、(3)、(4)步驟，逐次將所有聯(lián)結(jié)詞置于原子謂詞。前束范式步驟（續(xù)）(5).用換名等值公式xQ(x)yQ(y)和xQ(x)yQ(y)將所有不同量詞轄域的變?cè)獡Q名為互不同的變?cè)?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))重復(fù)應(yīng)用(6)步驟，逐次將量詞前置，使得公式變換為前束范式。(7).用等值變換交換量詞次序xyQ(x,y)yxQ(x,y)xyQ(x,y)yxQ(x,y)等式演算一般方法命題公式:Q的范式是Q'，R的范式是R'，因?yàn)镼Q'，

Q'R'，R'R。所以QR謂詞公式:Q的前束合取范式是Q'，R的前束合取范式是R'，因?yàn)镼Q'，

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

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

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

若集合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)關(guān)系“”和“”概念也是由集合及“”這兩個(gè)基本概念的導(dǎo)出概念。在數(shù)理邏輯證明中，“”和“”也可以看作是包含謂詞。集合運(yùn)算性質(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互補(bǔ)律A

A=A

A=U 對(duì)合律

A=A

=U U=關(guān)系運(yùn)算性質(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ù)運(yùn)算性質(zhì)定理：設(shè)f:XY，則f°

IX=IY

°

f=f。定理

設(shè)f:XY，g:YZ，h:ZW，則 h°

(g°

f)=(h°

g)°

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

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

f是滿射。

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

f是單射。

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

f是雙射。定理：設(shè)f是從X到Y(jié)的函數(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)f1滿足唯一性性質(zhì)：f滿足唯一性當(dāng)且僅當(dāng)f1滿足單值性定理：設(shè)f:XY是雙射函數(shù)，則存在逆函數(shù)f1:YX，并且f1是雙射函數(shù)。定理

若f:XY是可逆的，則 f1

°

f=IX且f°f1=IY定理：設(shè)雙射f:XY及雙射g:YX，g=f1，當(dāng)且僅當(dāng)g°f=IX

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

°g1

。定理：設(shè)f是從X到Y(jié)的函數(shù)，g是從Y到Z的函數(shù)，若f和g是單調(diào)增加的，則g°f是單調(diào)增加的。用集合和邏輯定義圖概念定義：設(shè)V是一個(gè)非空頂點(diǎn)集合，E是無(wú)向邊集合，V和E的有序偶稱為無(wú)向圖G，記為G=<V,E>，其中 E={(x,y)|xVyV}定義：設(shè)V是一個(gè)非空頂點(diǎn)集合，E是有向邊集合，V和E的有序偶稱為有向圖D，記為D=<V,E>，其中E={<x,y>|xVyV}圖的基本結(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=<V,E>和GS=<VS,ES>是兩個(gè)圖。若VSV并且ESE則稱GS是G的子圖。

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

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

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

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

若H是G的真子群，則簡(jiǎn)記為HG。 HGx(xHxG) {e}G，GG。群的性質(zhì)群G的元素a的左逆元a-1也是a的一個(gè)右逆元。├a°a-1=e群G的左單位元e也是G的一個(gè)右單位元。├a°e=a群G的每個(gè)元素的逆元都是唯一的。a'°a=e├a-1=a'群G的單位元是唯一的。x(e'°x=x)├e'=e設(shè)G為群，對(duì)于任意aG，bG，有(1).├(a-1)-1=a(2).├(a°b)-1=b-1°a-1(1).├(a-1)-1=a群中運(yùn)算滿足消去律。(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定理證明方法集合和邏輯表征概念、運(yùn)算、關(guān)系及其定理等式形式的定理有一般的證明方法演繹形式定理有公理方法公理：邏輯公理、專用公理正確證明驗(yàn)證：或者是公理或者是前提或者是推導(dǎo)規(guī)則主要內(nèi)容基本問(wèn)題數(shù)理邏輯數(shù)理邏輯是基礎(chǔ)離散數(shù)學(xué)是基礎(chǔ)計(jì)算機(jī)專業(yè)基礎(chǔ)指令集、操作系統(tǒng)和語(yǔ)言文法都有規(guī)范，需求明確基于需求，設(shè)計(jì)出系統(tǒng)模型判定系統(tǒng)模型正確的準(zhǔn)則是什么？軟件測(cè)試邏輯定義功能，形式建模，定理證明用集合和邏輯進(jìn)行系統(tǒng)的形式建模數(shù)字邏輯（邏輯模型）計(jì)算機(jī)組成（結(jié)構(gòu)模型）操作系統(tǒng)（操作模型）編譯系統(tǒng)（語(yǔ)言模型）用公理系統(tǒng)方法進(jìn)行形式證明證明之驗(yàn)證數(shù)字邏輯數(shù)字邏輯是關(guān)于數(shù)字（二進(jìn)制數(shù)）的邏輯運(yùn)算、關(guān)系判斷及操作的邏輯表示方法，以及物理實(shí)現(xiàn)。數(shù)字邏輯主要有組合邏輯和時(shí)序邏輯。數(shù)字邏輯部件組合邏輯設(shè)計(jì)，包括編碼器、譯碼器、比較器、數(shù)據(jù)選擇器、數(shù)據(jù)分配器、奇偶校驗(yàn)器、算術(shù)邏輯單元、乘法器、數(shù)據(jù)擴(kuò)展器等。時(shí)序邏輯設(shè)計(jì)，包括計(jì)數(shù)器、寄存器、移位器等基本問(wèn)題數(shù)字邏輯的理論基礎(chǔ)是什么？布爾代數(shù)？數(shù)字邏輯與離散數(shù)學(xué)有什么關(guān)系？設(shè)計(jì)數(shù)字邏輯部件的一般方法是什么？物理基礎(chǔ)組合邏輯：與門、或門、非門時(shí)序邏輯：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線譯碼器功能表譯碼是的輸入是一個(gè)二進(jìn)制數(shù)X，用Xn-1,…,X1,X0表示，輸出是二進(jìn)制數(shù)2n-1，用Y2**n-1,…,Y1,Y0表示。輸入輸出X2X1X0Y7Y6Y5Y4Y3Y2Y1Y00000000000100100000010010000001000110000100010000010000101001000001100100000011110000000Y0=

X2

X1X0Y1=

X2

X1X0Y2=

X2X1X0Y3=

X2

X1X0Y4=

X2

X1X0Y5=

X2

X1X0Y6=

X2X1X0Y7=

X2

X1X0一般性方法求邏輯表達(dá)式32位譯碼器Verilog程序多路選擇器多路選擇器是一種多路數(shù)據(jù)輸入并且一路數(shù)據(jù)輸出的邏輯部件輸入輸出C1C0X0kX1kX2kX3kYk00D0k×××D0k01×D1k××D1k10××D2k×D2k11×××D3kD3kZ0=C1C0Z1=C1C0Z2=C1C0Z3=C1C0Yk=Z0X0kZ1X1kZ2X2kZ3X3k一般性方法求邏輯表達(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)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;二進(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。輸入輸出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=~