離散數(shù)學(xué)數(shù)理邏輯初步

離散數(shù)學(xué)數(shù)理邏輯初步第一頁，共六十頁，2022年，8月28日前言計算機科學(xué)基礎(chǔ)理論的核心課程研究離散量的結(jié)構(gòu)和相互之間的關(guān)系數(shù)學(xué)與計算機科學(xué)的結(jié)合點第二頁，共六十頁，2022年，8月28日主要內(nèi)容數(shù)理邏輯初步集合論代數(shù)結(jié)構(gòu)圖論上述內(nèi)容之間有密切聯(lián)系,但是看起來又是非常離散的!第三頁，共六十頁，2022年，8月28日數(shù)理邏輯初步內(nèi)容提要用數(shù)學(xué)方法來研究推理的規(guī)律引進一套符號體系基本內(nèi)容：命題邏輯和謂詞邏輯第四頁，共六十頁，2022年，8月28日數(shù)理邏輯初步命題邏輯什么是命題？具有真假值判斷的陳述句

注意感嘆句、疑問句、祈使句等都不是命題；悖論也不是命題。真假值的表示真值=True=T;假值=False=F第五頁，共六十頁，2022年，8月28日數(shù)理邏輯初步命題種類與表示1.原子命題不能分解為更為簡單的陳述句；通常用大寫字母表示，A，B，P，Q2.復(fù)合命題有限個原子命題由若干個聯(lián)結(jié)詞按一定規(guī)則復(fù)合構(gòu)成的;

注意:復(fù)合命題的真假值將由它所包含的原子命題的真假值和聯(lián)結(jié)詞的邏輯意義所決定.第六頁，共六十頁，2022年，8月28日數(shù)理邏輯初步聯(lián)結(jié)詞(1)否定

P是一命題,?P為P的否定;?P的邏輯意義為當(dāng)P為真時?P為假；當(dāng)P為假時，?P為真。P?PTFFT第七頁，共六十頁，2022年，8月28日數(shù)理邏輯初步聯(lián)結(jié)詞(2)合取

P、Q是兩個命題,P∧Q是合取復(fù)合命題;P∧Q的邏輯意義為當(dāng)且僅當(dāng)P、Q同時為真時，P∧Q為真。PQP∧QTTTTFFFTFFFF第八頁，共六十頁，2022年，8月28日數(shù)理邏輯初步聯(lián)結(jié)詞(3)析取

P、Q是兩個命題,P∨Q是析取復(fù)合命題;P∨Q的邏輯意義為當(dāng)且僅當(dāng)P、Q同時為假時，P∨Q為假。PQP∨QTTTTFTFTTFFF第九頁，共六十頁，2022年，8月28日數(shù)理邏輯初步聯(lián)結(jié)詞(4)條件（蘊涵）

P、Q是兩個命題,P→Q是一個條件復(fù)合命題;P→Q的邏輯意義為當(dāng)且僅當(dāng)P為真、Q為假時，P→Q為假。PQP→QTTTTFFFTTFFT第十頁，共六十頁，2022年，8月28日數(shù)理邏輯初步聯(lián)結(jié)詞(5)雙條件（等價）

P、Q是兩個命題,P?Q是一個等價復(fù)合命題;P?Q的邏輯意義為當(dāng)且僅當(dāng)P和Q的真值相同時，P?Q為真。PQP?QTTTTFFFTFFFT第十一頁，共六十頁，2022年，8月28日數(shù)理邏輯初步最小聯(lián)結(jié)詞集能夠表達其它聯(lián)結(jié)詞的邏輯意義，但不能互相表達?？梢宰C明：最小聯(lián)結(jié)詞集為｛?，∧}（或{?，∨}）***因為（涉及下面講的等值公式）：

P∨Q=?（?P∧?Q）；

P→Q=?P∨Q；

P?Q=（P→Q）∧（Q→P）。第十二頁，共六十頁，2022年，8月28日數(shù)理邏輯初步命題公式（合式公式）回憶：聯(lián)結(jié)詞需要有一定規(guī)則構(gòu)成復(fù)合命題。遞歸定義（1）原子命題是一個命題公式；（2）如果A是命題公式，那么?A也是命題公式；（3）如果A和B是命題公式，那么A∧B、A∨B、A→B和

A?B都是命題公式；（4）一個命題公式只能有限次地應(yīng)用（1）、（2）、（3）得到。第十三頁，共六十頁，2022年，8月28日數(shù)理邏輯初步思考給定任意一串字符，如何判定它是否為一個命題公式？第十四頁，共六十頁，2022年，8月28日數(shù)理邏輯初步表達與翻譯目標(biāo)：知識表達（推理的第一步）過程：原子命題+聯(lián)結(jié)詞+邏輯意義例子Q：上海到北京的火車是下午五點半或六點開。A：P=上海到北京的火車是下午五點半開；

Q=上海到北京的火車是下午六點開。原句為（P∧?Q）∨（?P∧Q）第十五頁，共六十頁，2022年，8月28日數(shù)理邏輯初步指派與真值表指派：命題公式中所含的原子命題的真值的一種組合；真值表：所有指派列成的表。請看書中例題第十六頁，共六十頁，2022年，8月28日數(shù)理邏輯初步命題公式等值（等價公式）兩個命題公式在所有不同指派下所對應(yīng)的真值相同，即它們的真值表相同，那么這兩個命題公式等值?；貞洠罕磉_的例子（上海到北京的火車）?（P?Q）=（P∧?Q）∨（?P∧Q）第十七頁，共六十頁，2022年，8月28日數(shù)理邏輯初步命題等值基本定律對合律??P=P1冪等律P∨P=P,P∧P=P2結(jié)合律(P∨Q)∨R=P∨(Q∨R)(P∧Q)∧R=P∧(Q∧R)3交換律P∨Q=Q∨P,P∧Q=Q∧P4分配律P∨(Q∧R)=(P∨Q)∧(P∨R)P∧(Q∨R)=(P∧Q)∨(P∧R)5吸收律P∨(P∧Q)=P,P∧(P∨Q)=P6DeMorgan律?(P∨Q)=?P∧?Q?(P∧Q)=?P∨?Q7同一律P∨F=P,P∧T=P8零律P∨T=T,P∧F=F9否定律P∨?P=T,P∧?P=F10第十八頁，共六十頁，2022年，8月28日數(shù)理邏輯初步等值置換與證明等值置換：如果Ｘ是Ａ的子命題公式，Ｘ＝Ｙ，那么將Ａ中的Ｘ用Ｙ來置換所得到的公式Ｂ與Ａ等值，即Ａ＝Ｂ。等值公式的證明（１）真值表相同；（２）經(jīng)過等值置換后得到。第十九頁，共六十頁，2022年，8月28日數(shù)理邏輯初步重言式（永真式）永真公式：所有指派下都取真值；永假公式：所有指派下都取假值。幾個結(jié)論：（１）任何兩個永真式的合?。ɑ蛭鋈。┒加勒?；（２）永真式經(jīng)等值置換后仍永真；（３）Ａ＝Ｂ當(dāng)且僅當(dāng)Ａ?Ｂ永真。第二十頁，共六十頁，2022年，8月28日數(shù)理邏輯初步對偶注意：傳統(tǒng)上，命題公式通常包含{?，∧，∨}，而不是最小聯(lián)結(jié)詞集{?，∧}或{?，∨}對偶式：在命題公式A中將聯(lián)結(jié)詞∨換成∧，將∧換成∨，T換成F，F(xiàn)換成T，所得公式A*與A互為對偶。第二十一頁，共六十頁，2022年，8月28日數(shù)理邏輯初步關(guān)于對偶的幾個結(jié)論設(shè)A和A*是對偶式，P1，P2，…，Pn是出現(xiàn)在命題公式中的原子命題，則

?A(P1，P2，…，Pn)=A*(?P1，?P2，…，?Pn)(注：用數(shù)學(xué)歸納法可證）P1，P2，…，Pn是出現(xiàn)在命題公式中的原子命題，如果A=B，則A*=B*。第二十二頁，共六十頁，2022年，8月28日數(shù)理邏輯初步范式文字：原子命題與它的非；簡單合取式：有限個文字組成的合取式；簡單析取式：有限個文字組成的析取式；合取范式：有限個簡單析取式的合取；析取范式：有限個簡單合取式的析取。第二十三頁，共六十頁，2022年，8月28日數(shù)理邏輯初步思考任何一個命題公式都可以等值轉(zhuǎn)化為合取范式或析取范式嗎？如果可以轉(zhuǎn)換，那么合取范式或析取范式是唯一的嗎？第二十四頁，共六十頁，2022年，8月28日數(shù)理邏輯初步主范式：范式的唯一性小項：所有原子命題或它的非都在簡單合取式中出現(xiàn)，但不同時出現(xiàn)。每一個小項唯一地對應(yīng)一個簡單合取式，任意兩個不同小項的合取永假，全體小項的析取永真。大項：所有原子命題或它的非都在簡單析取式中出現(xiàn)，但不同時出現(xiàn)。每一個大項唯一地對應(yīng)一個簡單析取式，任意兩個不同的大項的析取永真，全體大項的合取永假。第二十五頁，共六十頁，2022年，8月28日數(shù)理邏輯初步主合取范式和主析取范式主合取范式：僅由大項所組成的合取范式；主析取范式：僅由小項所組成的析取范式。從命題公式的真值表中可得到主合取范式和主析取范式：成真指派所對應(yīng)的小項的析取即為主析取范式；成假指派所對應(yīng)的大項的合取即為主合取范式。為什么？第二十六頁，共六十頁，2022年，8月28日數(shù)理邏輯初步基本推理設(shè)H1，H2，…，Hn，C是一組命題公式，C是前提H1，H2，…，Hn的邏輯結(jié)論的充分必要條件是（H1∧

H2∧

…∧Hn）→C永真。通常記為：（H1∧

H2∧

…∧Hn）╞C（即在使前提為真的所有指派下結(jié)論也為真）重要性：在符號世界和現(xiàn)實世界中建立了一條道路！第二十七頁，共六十頁，2022年，8月28日數(shù)理邏輯初步推理方法真值表法直接證明法間接證明法欲證明（H1∧

H2∧

…∧Hn）→C永真，即證明H1∧

H2∧

…∧Hn

∧

?

C永假！第二十八頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞邏輯知識表達的粒度問題原子命題：命題層次不可分解刻畫命題內(nèi)部的邏輯結(jié)構(gòu)的需要命題邏輯的局限性例子：三段論所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。第二十九頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞的概念對命題概念的擴充與分解把命題分成兩個結(jié)構(gòu)：主語和謂語主語：描述具體或抽象的客體（個體）；謂語：刻劃客體的性質(zhì)或關(guān)系。第三十頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞的表示主語：小寫字母，a,b,x,y謂語：大寫字母，A，B，P，Q謂詞：P（a）（注：一元原子謂詞）推廣到n元原子謂詞

P（a1,a2,……,an）具有真假值原子命題即為0元原子謂詞第三十一頁，共六十頁，2022年，8月28日數(shù)理邏輯初步常元與變元常元：個體作為常量，表示具體的客體；通常用a,b,c表示。變元：個體作為變量，表示抽象的客體；通常用x,y,z表示。第三十二頁，共六十頁，2022年，8月28日數(shù)理邏輯初步個體域個體的定義域：客體的論述范圍有限或無限全總個體域：所有個體所組成的集合第三十三頁，共六十頁，2022年，8月28日數(shù)理邏輯初步函詞個體的函數(shù)：值域還是個體域

f(x1,x2,…,xn)=y,

x1,x2,…,xn為

n個常元或變元，y是一個常元或變元，f是n元函詞。注意：函詞與謂詞的區(qū)別！第三十四頁，共六十頁，2022年，8月28日數(shù)理邏輯初步項遞歸定義：（1）常元是項；（2）變元是項；（3）如果f是n元函詞，x1,x2,…,xn為

n個項，那么f(x1,x2,…,xn)也是項；（4）項只能有限次應(yīng)用上述（1）、（2）、（3）得到。第三十五頁，共六十頁，2022年，8月28日數(shù)理邏輯初步自由變元與約束變元自由變元：變元在個體域中自由取值；約束變元：變元在個體域中的取值是受到一定約束的。約束的定性化與定量化：自由變元=》量詞約束=》常元第三十六頁，共六十頁，2022年，8月28日數(shù)理邏輯初步量詞表示變元在個體域中的定性約束全稱量詞：表示個體域中的所有個體；記作存在量詞：表示個體域中的某幾個個體；記作

第三十七頁，共六十頁，2022年，8月28日數(shù)理邏輯初步量詞的作用域?qū)τ趚P(x)或xP(x)，x是約束變元，謂詞P(x)即為量詞的轄域（作用域）。

注意：量詞的約束只在它的作用域內(nèi)，也就是說，量詞作用域之外的變元是自由變元。第三十八頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞公式（合式公式）遞歸定義（1）原子謂詞公式是謂詞公式；（2）若A（x1,x2,…,xn)是n元原子謂詞公式，t1,t2,…,tn是項，則A（t1,t2,…,tn

）也是謂詞公式；（3）若A是謂詞公式，則?A也是謂詞公式；（4）若A和B都是謂詞公式，則A∧B、A∨B、A→B和

A?B也是謂詞公式；（5）若A是謂詞公式，x是A中出現(xiàn)的任意變元，則VxA和xA也是謂詞公式；（6）一個謂詞公式只能有限次地應(yīng)用上述規(guī)則得到。第三十九頁，共六十頁，2022年，8月28日數(shù)理邏輯初步思考給定任意一個字符串，如何判斷它是否為一個謂詞公式？第四十頁，共六十頁，2022年，8月28日數(shù)理邏輯初步約束變元的改名避免變元名稱的混淆約束變元的邏輯意義與使用名稱無關(guān)則有VxA(x)=VyA(y)xA(x)=yA(y)第四十一頁，共六十頁，2022年，8月28日數(shù)理邏輯初步自由變元的代入自由變元作為參數(shù)自由變元的改名需要保持一致代入后不能與約束變元相沖突

改名與代入的意義在于：使得謂詞公式中的變元名稱各不相同，邏輯意義更加清楚。第四十二頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞公式的真值與哪些因素有關(guān)？謂詞個體域函詞量詞聯(lián)結(jié)詞第四十三頁，共六十頁，2022年，8月28日數(shù)理邏輯初步思考給定一個謂詞公式，如何判斷它的真假值？******首先，謂詞公式的真假值能夠判定嗎？？？（注意：個體域的不可確定性）第四十四頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞公式的指派謂詞（包括命題）、函詞、量詞和個體域組成指派的成分通常把個體域單獨考慮由于個體域有無限多個，通常假定為全總個體域作為缺省個體域注：謂詞公式的真值表能列出嗎？第四十五頁，共六十頁，2022年，8月28日數(shù)理邏輯初步表達與翻譯符號世界與現(xiàn)實世界的轉(zhuǎn)換知識表達的更細(xì)粒度過程：原子謂詞的表示確定常元與變元存在函詞、量詞嗎？聯(lián)結(jié)詞的選擇第四十六頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞公式表達舉例極限的定義P(x,y)：x大于y;Q(x,y)：x小于y;(Vε)(δ)(Vx)(((P(ε,0)→P(δ,0))∧

Q(|x-a|,δ)∧P(|x-a|,0))→Q(|f(x)-b|,ε))

第四十七頁，共六十頁，2022年，8月28日數(shù)理邏輯初步謂詞公式的等值回憶：無法判斷謂詞公式的真假值！但是：在確定的個體域中，可以判斷謂詞公式的真假值?。τ趦蓚€謂詞公式A和B，在相同的個體域E下，所有的指派都有相同的真值，那么A和B在個體域E下等值。第四十八頁，共六十頁，2022年，8月28日數(shù)理邏輯初步等值謂詞公式（舉例）命題公式的推廣量詞與否定的關(guān)系

?(Vx)P(x)=(x)?P(x)?(x)P(x)=(Vx)?P(x)量詞作用域的變化量詞與聯(lián)結(jié)詞的關(guān)系（請看書中例子）第四十九頁，共六十頁，2022年，8月28日數(shù)理邏輯初步永真的、可滿足的和不可滿足的永真的：一個謂詞公式在一個確定的個體域下的所有指派都為真；可滿足的：一個謂詞公式在一個確定的個體域下的有某些指派為真；不可滿足的：一個謂詞公式在一個確定的個體域下的所有指派都為假。第五十頁，共六十頁，2022年，8月28日數(shù)理邏輯初步思考謂詞公式有標(biāo)準(zhǔn)形式嗎？第五十一頁，共六十頁，2022年，8月28日數(shù)理邏輯初步前束范式前束范式：所有量詞都在公式的前面，即如形式θ1x1θ2x2…θmxmP，其中θi

取V或，P是母式，x為變元。第五十二頁，共六十頁，2022年，8月28日數(shù)理邏輯初步結(jié)論：謂詞公式可以轉(zhuǎn)化成前束范式關(guān)鍵：？如何轉(zhuǎn)化？注意：為了變元清晰，需要使用改名！第五十三頁，共六十頁，2022年，8月28日數(shù)理邏輯初步進一步：前束合取范式前束合取范式：母式為合取范式的前束范式結(jié)論：任意一個謂詞公式都可以等值轉(zhuǎn)化為一個前束合取范式。

為什么？第五十四頁，共六十頁，2022年，8月28日數(shù)理邏輯初步進一步：前束析取范式前束析取范式：母式為析取范式的前束范式與前束合取范式類似