離散數(shù)學(xué)筆記

1、離散數(shù)學(xué) 第一章 命題邏輯內(nèi)容：命題及命題聯(lián)結(jié)詞、命題公式的基本概念，真值表、基本等價(jià)式及永真蘊(yùn)涵式，命題演算的推理理論中常用的直接證明、條件證明、反證法證明等方法教學(xué)目的：1 熟練掌握命題、聯(lián)結(jié)詞、復(fù)合命題、命題公式及其解釋的概念。2 熟練掌握常用的基本等價(jià)式及其應(yīng)用。3 熟練掌握（主）析/合取范式的求法及其應(yīng)用。4 熟練掌握常用的永真蘊(yùn)涵式及其在邏輯推理中的應(yīng)用。5 熟練掌握形式演繹的方法。教學(xué)重點(diǎn)：1命題的概念及判斷2聯(lián)結(jié)詞，命題的翻譯3主析（合）取范式的求法4邏輯推理教學(xué)難點(diǎn)：1主析（合）取范式的求法2邏輯推理1.1命題及其表示法1.1.1 命題的概念 數(shù)理邏輯將能夠判斷真假的陳述句稱

2、作命題。1.1.2 命題的表示命題通常使用大寫字母A，B，Z或帶下標(biāo)的大寫字母或數(shù)字表示，如Ai，10，R等，例如A1：我是一名大學(xué)生。A1:我是一名大學(xué)生.10：我是一名大學(xué)生。R：我是一名大學(xué)生。1.2命題聯(lián)結(jié)詞1.2.1 否定聯(lián)結(jié)詞P01101.2.2 合取聯(lián)結(jié)詞0000101001111.2.3 析取聯(lián)結(jié)詞0000111011111.2.4 條件聯(lián)結(jié)詞0010111001111.2.5 雙條件聯(lián)結(jié)詞0010101001111.2.6 與非聯(lián)結(jié)詞001011101110性質(zhì)：（1） PP（PP）P；（2）（2）（PQ）（PQ）（PQ） PQ；（3）（PP）（QQ）PQ PQ。1.2.7

3、或非聯(lián)結(jié)詞001010100110性質(zhì)：（1）PP（PQ）P；（2）（PQ）（PQ）（PQ）PQ；（3）（PP）（QQ）PQ（PQ）PQ。1.3 命題公式、翻譯與解釋1.3.1 命題公式定義 命題公式，簡稱公式，定義為：（1）單個(gè)命題變?cè)枪?；?）如果P是公式，則P是公式；（3）如果P、Q是公式，則PQ、PQ、PQ、 PQ都是公式；（4）當(dāng)且僅當(dāng)能夠有限次的應(yīng)用(1) 、(2)、(3) 所得到的包括命題變?cè)?、?lián)結(jié)詞和括號(hào)的符號(hào)串是公式。例如，下面的符號(hào)串都是公式：（P）Q）R）S）（PQ）（RS） （PQ）R以下符號(hào)串都不是公式：（PQ）（Q） （Q）1.3.2 命題的翻譯 可以把自然語言

4、中的有些語句，轉(zhuǎn)變成數(shù)理邏輯中的符號(hào)形式，稱為命題的翻譯。 命題翻譯時(shí)應(yīng)注意下列事項(xiàng)：（1）確定所給句子是否為命題。（2）句子中聯(lián)結(jié)詞是否為命題聯(lián)結(jié)詞。（3）要正確的選擇原子命題和合適的命題聯(lián)結(jié)詞。例：假如上午不下雨，我去看電影，否則就在家里讀書或看報(bào)。解：設(shè)P：上午下雨；Q：我去看電影；R：我在家里讀書；S：我在家里看報(bào)。本例可表示為： （PQ）（P（RS）。1.3.3 命題公式的解釋定義 設(shè)P1，P2，Pn是出現(xiàn)在命題公式G中的全部命題變?cè)付≒1，P2，Pn的一組真值，稱這組真值為G的一個(gè)解釋或賦值，記作I，公式G在I下的真值記作TI（G）。例如，G=（PQ）R，則I：110是G的一個(gè)

5、解釋，在這個(gè)解釋下G的真值為1，即TI（G）=1。1.4 真值表與等價(jià)公式1.4.1 真值表定義 將公式G在其所有解釋下所取得的真值列成一個(gè)表，稱為G的真值表。構(gòu)造真值表的方法如下：（1）找出公式G中的全部命題變?cè)?，并按一定的順序排列成P1，P2，Pn。 （2）列出G的2n個(gè)解釋，賦值從000（n個(gè)）開始，按二進(jìn)制遞加順序依次寫出各賦值，直到111為止（或從111開始，按二進(jìn)制遞減順序?qū)懗龈髻x值，直到000為止），然后從低到高的順序列出G的層次。（3）根據(jù)賦值依次計(jì)算各層次的真值并最終計(jì)算出G的真值。例：G=（ PQ ）Q 001000110010010111001.4.2 命題公式的分類 定

6、義 設(shè)G為公式：（1）如果G在所有解釋下取值均為真，則稱G是永真式或重言式；（2）如果G在所有解釋下取值均為假，則稱G是永假式或矛盾式；（3）如果至少存在一種解釋使公式G取值為真，則稱G是可滿足式。1.4.3 等價(jià)公式 定義 設(shè)A和B是兩個(gè)命題公式，如果A和B在任意賦值情況下都具有相同的真值，則稱A和B是等價(jià)公式。記為AB。性質(zhì)定理設(shè)A、B、C是公式，則（1）AA（2）若AB則BA（3）若AB且BC則AC定理 設(shè)A、B、C是公式，則下述等價(jià)公式成立：（1）雙重否定律 AA（2）等冪律 AAA ； AAA（3）交換律 ABBA ； ABBA（4）結(jié)合律 （AB）CA（BC）（AB）CA（BC）（

7、5）分配律 （AB）C（AC）（BC）（AB）C（AC）（BC）（6）德·摩根律 （AB）AB（AB）AB（7）吸收律 A（AB）A；A（AB）A（8）零一律 A11 ； A00（9）同一律 A0A ； A1A（10）排中律 AA1（11）矛盾律 AA0（12）蘊(yùn)涵等值式 ABAB（13）假言易位 ABBA（14）等價(jià)等值式 AB（AB）（BA）（15）等價(jià)否定等值式 ABABBA（16）歸繆式 （AB）（AB）A1.4.4 置換規(guī)則 定理（置換規(guī)則） 設(shè)（A）是一個(gè)含有子公式A的命題公式，（B）是用公式B置換了（A）中的子公式A后得到的公式，如果AB，那么（A）（B）。1.5 對(duì)偶

8、與范式1.5.1 對(duì)偶定義 在僅含有聯(lián)結(jié)詞Ø、的命題公式A中，將聯(lián)結(jié)詞換成，將換成，如果A中含有特殊變?cè)?或1，就將0換成1，1換成0，所得的命題公式A*稱為A的對(duì)偶式。例：公式（PQ）（PQ） 的對(duì)偶式為：（PQ）（PQ）定理 設(shè)A和A*互為對(duì)偶式，P1，P2，Pn是出現(xiàn)在A和A*中的所有原子變?cè)魧和A*寫成n元函數(shù)形式，則（1）A（P1，P2，Pn）A*（P1，P2，Pn）（2）A（P1，P2，Pn）A*（P1，P2，Pn） 定理（對(duì)偶原理）設(shè)A、B是兩個(gè)命題公式，若AÛB，則A*B*，其中A*、B*分別為A、B的對(duì)偶式。1.5.2 范式定義 僅由有限個(gè)命題變?cè)?/p>

9、其否定構(gòu)成的析取式稱為簡單析取式，僅由有限個(gè)命題變?cè)捌浞穸?gòu)成的合取式稱為簡單合取式。定義 僅由有限個(gè)簡單合取式構(gòu)成的析取式稱為析取范式。僅由有限個(gè)簡單析取式構(gòu)成的合取式稱為合取范式。定理（范式存在定理）任何命題公式都存在著與之等價(jià)的析取范式和合取范式。1.5.3 主范式定義 在含有n個(gè)命題變?cè)狿1，P2，Pn的簡單合取范式中，若每個(gè)命題變?cè)蚱浞穸ú煌瑫r(shí)存在，但二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變?cè)蚱浞穸ǔ霈F(xiàn)在從左起的第i個(gè)位置上（若命題變?cè)獰o腳標(biāo)，則按字典順序排列），這樣的簡單合取式稱為極小項(xiàng)。相應(yīng)的，滿足上述條件的簡單析取式稱為極大項(xiàng)。n個(gè)命題變?cè)狿1，P2，Pn的極小項(xiàng)用公式

10、可表示為 Pi* ，極大項(xiàng)可表示為Pi*，其中，Pi*為Pi或Pi（i=1，2，n）。定義 設(shè)G為公式，P1，P2，Pn為G中的所有命題變?cè)?，若G的析取范式中每一個(gè)合取項(xiàng)都是P1，P2，Pn的一個(gè)極小項(xiàng)，則稱該析取范式為G的主析取范式。矛盾式的主析取范式為0。定理 任意的命題公式都存在一個(gè)唯一的與之等價(jià)的主析取范式。 用等值演算求主析取范式步驟如下：（1） 求G的析取范式G'；（2）（2）若G中某個(gè)簡單合取式m中沒有出現(xiàn)某個(gè)命題變?cè)狿i或其否定Pi，則將m作如下等價(jià)變換：mm（PiPi）（ mPi）（mPi）（3）將重復(fù)出現(xiàn)的命題變?cè)?、矛盾式和重?fù)出現(xiàn)的極小項(xiàng)都消去；（4）重復(fù)步驟（2

11、）、（3），直到每一個(gè)簡單合取式都為極小項(xiàng)；（5）將極小項(xiàng)按腳標(biāo)由小到大的順序排列，并用表示。如m0m1m7可表示為（0，1，7）。 定義 設(shè)G為公式，P1，P2，Pn為G中的所有命題變?cè)?，若G的合取范式中每一個(gè)析取項(xiàng)都是P1，P2，Pn的一個(gè)極大項(xiàng)，則稱該合取范式為G的主合取范式。通常，主合取范式用表示。重言式的主合取范式中不含任何極大項(xiàng)，用1表示。 定理 任意的命題公式都存在一個(gè)唯一的與之等價(jià)的主合取范式。1.6 公式的蘊(yùn)涵1.6.1 蘊(yùn)涵的概念定義 設(shè)G、H是兩個(gè)公式，若GH是永真式，則稱G蘊(yùn)涵H，記作GH。蘊(yùn)涵關(guān)系有如下性質(zhì)：（1） 對(duì)于任意公式G，有GG；（2）（2）對(duì)任意公式G、H

12、，若GH且HG，則GH；（3） 若GH且HL，則GL。 廣義的蘊(yùn)涵概念 定義 設(shè)G1，G2，Gn，H是公式，如果（G1G2Gn）H是永真式，則稱G1，G2，Gn蘊(yùn)涵H，又稱H是G1，G2，Gn的邏輯結(jié)果，記作（G1G2Gn）H或（G1，G2，Gn）H。1.6.2 基本蘊(yùn)涵式（1）PQP； （2）PQQ；（3）PPQ； (4) QPQ；（5）P（PQ）； （6）Q（PQ）；（7）（PQ）P； （8）（PQ）Q；（9）P，PQQ； （10）Q，PQP；（11）P，PQQ； （12）PQ，QRPR；（13）PQ，PR，QRR； （14）PQ，RS（PR）（QS）；（15）P，QPQ。1.7 其它聯(lián)結(jié)

13、詞與最小聯(lián)結(jié)詞組1.7.1 其它聯(lián)結(jié)詞定義 設(shè)P、Q為命題公式，則復(fù)合命題P Q稱為P和Q的不可兼析取，當(dāng)且僅當(dāng)P與Q的真值不相同時(shí)，PQ的真值為1，否則PQ的真值為假。定義 設(shè)P、Q是兩個(gè)命題公式，復(fù)合命題P Q稱為命題P、Q的條件否定，當(dāng)且僅當(dāng)P的真值為1，Q的真值為0時(shí)，P Q的真值為1，否則 PQ的真值為0。1.7.2 最小聯(lián)結(jié)詞組定義 設(shè)S是一些聯(lián)結(jié)詞組成的非空集合，如果任何的命題公式都可以用僅包含S中的聯(lián)結(jié)詞的公式表示，則稱S是聯(lián)結(jié)詞的全功能集。特別的，若S是聯(lián)結(jié)詞的全功能集且S的任何真子集都不是全功能集，則稱S是最小全功能集，又稱最小聯(lián)結(jié)詞組。 定理 ，是聯(lián)結(jié)詞的全功能集。 定理

14、 ，是聯(lián)結(jié)詞的全功能集。定理 ，、，是最小聯(lián)結(jié)詞組。 定理 ，是最小聯(lián)結(jié)詞組。1.8 命題邏輯推理理論1.8.1 命題邏輯推理理論定義 如果G1，G2，Gn蘊(yùn)涵H，則稱H能夠由G1，G2，Gn有效推出，G1，G2，Gn稱為H的前提，H稱為G1，G2，Gn的有效結(jié)論。稱（G1G2Gn）H是由前提G1，G2，Gn推結(jié)論H的推理的形式結(jié)構(gòu)。1.8.2 推理規(guī)則下面給出推理中常用的推理規(guī)則。1 前提引入規(guī)則：可以在證明的任何時(shí)候引入前提；2 結(jié)論引入規(guī)則：在證明的任何時(shí)候，已證明的結(jié)論都可以作為后續(xù)證明的前提；3 置換規(guī)則：在證明的任何時(shí)候，命題公式中的任何子命題公式都可以用與之等價(jià)的命題公式置換。4

15、 言推理規(guī)則：P，PQQ5 附加規(guī)則：PPQ；6 化簡規(guī)則：P，QP；7 拒取式規(guī)則： Q，PQP；8 假言三段論規(guī)則：PQ，QRPR；9 析取三段論規(guī)則：P，PQQ；10.構(gòu)造性二難規(guī)則：PQ，PR，QRR；11.合取引入規(guī)則：P，QPQ1.8.3 推理常用方法1.直接證法 直接證法就是根據(jù)一組前提，利用前面提供的一些推理規(guī)則，根據(jù)已知的等價(jià)公式和蘊(yùn)涵式，推演得到有效的結(jié)論的方法，即有前提直接推導(dǎo)出結(jié)論。 例 構(gòu)造下列推理的證明。前提：PQ，PR，QS 結(jié)論：SR證明（1）PQ 前提引入規(guī)則 （2）PR 前提引入規(guī)則 （3）QS 前提引入規(guī)則 （4）SR （1）（2）（3）構(gòu)造性二難規(guī)則2間

16、接證法 間接證法主要有如下兩種情況。 （1）附加前提證明法 有時(shí)要證明的結(jié)論以蘊(yùn)涵式的形式出現(xiàn)，即推理的形式結(jié)構(gòu)為：（G1G2Gn）（RC）設(shè)（G1G2Gn）為S，則上述推理可表示為證明S（RC），即證明S（RC）為永真式。 用附加前提證明法證明下面推理。前提：P（QR），SP，Q 結(jié)論：SR證明：（1）SP 前提引入規(guī)則 （2）S 附加前提引入規(guī)則 （3）P （1）（2）析取三段論規(guī)則 （4）P（QR） 前提引入規(guī)則 （5）QR （3）（4）假言推理規(guī)則 （6）Q 前提引入規(guī)則 （7）R （5）（6）假言推理規(guī)則2）歸繆法定義 設(shè)G1，G2，Gn是n個(gè)命題公式，如果G1G2Gn是可滿足式，則

17、稱G1，G2，Gn是相容的。否則（即G1G2Gn是矛盾式）稱G1，G2，Gn是不相容的。例 用歸繆法證明。前提：PQ，PR，QS 結(jié)論：SR證明（1）（SR） 附加前提引入規(guī)則 （2）SR （1）置換規(guī)則 （3）S （2）化簡規(guī)則 （4）R （2）化簡規(guī)則 （5）QS 前提引入規(guī)則 （6）QS （5）置換規(guī)則 （7）Q （3）（6）析取三段論 （8）PQ 前提引入規(guī)則 （9）P （7）（8）析取三段論規(guī)則 （10）PR 前提引入規(guī)則 （11）PR （10）置換規(guī)則 （12）R （9）（11）析取三段論規(guī)則 （13）RR （4）（12）合取引入規(guī)則第二章 謂詞邏輯第三章本章學(xué)習(xí)目標(biāo) 命題邏輯中原

18、子命題是最小的單位，不能夠再進(jìn)行分解，這給推理帶來了很大局限性，本章引入謂詞邏輯。學(xué)習(xí)關(guān)于謂詞邏輯的相關(guān)概念和定理，解決實(shí)際問題。內(nèi)容：謂詞、量詞及謂詞公式等概念，基本等價(jià)式、永真蘊(yùn)涵式及謂詞演算的形式推理方法，謂詞范式的概念教學(xué)目的：1 深刻理解個(gè)體、謂詞、量詞的概念。2 深刻理解原子、公式、解釋的概念。3 掌握用解釋的方法證明等價(jià)式和蘊(yùn)涵式。4 熟練掌握謂詞演算的形式推理方法。 教學(xué)重點(diǎn)： 1個(gè)體、謂詞、量詞的概念 2用解釋的方法證明等價(jià)式和蘊(yùn)涵式 3謂詞演算的形式推理方法 教學(xué)難點(diǎn)： 1解釋的方法證明等價(jià)式和蘊(yùn)涵式 2謂詞演算的形式推理方法2.1 謂詞邏輯命題的符號(hào)化 1個(gè)體詞 ：個(gè)體詞

19、是指研究對(duì)象中不依賴于人的主觀而獨(dú)立存在的具體的或抽象的客觀實(shí)體 個(gè)體常項(xiàng)或個(gè)體常元 ： 個(gè)體變項(xiàng)或個(gè)體變?cè)?： 個(gè)體域或論域 ： 2謂詞：用來刻畫個(gè)體詞的性質(zhì)或個(gè)體詞之間關(guān)系的詞 一般來說，“x是A”類型的命題可以用A（x）表達(dá)。對(duì)于“x大于y”這種兩個(gè)個(gè)體之間關(guān)系的命題，可表達(dá)為B（x，y），這里B表示“大于”謂詞。我們把A（x）稱為一元謂詞,B（x，y）稱為二元謂詞，M（a，b，c）稱為三元謂詞，依次類推，通常把二元以上謂詞稱作多元謂詞。 例2.1 將下列命題在謂詞邏輯中符號(hào)化，并討論它們的真值：（1）只有4是素?cái)?shù)，8才是素?cái)?shù)。（2）如果2小于3，則8小于7。 解（1）設(shè)謂詞G（x）：x

20、是素?cái)?shù)，a：4，b：8；（1）中的題符號(hào)化為謂詞的蘊(yùn)涵式：G（a）G（b）由于此蘊(yùn)涵式的前件為假，所以（1）中的命題為真。（2）設(shè)謂詞H（x，y）：x小于y，a：2，b：3，c：8，d：7（2）中的命題符號(hào)化為謂詞的蘊(yùn)涵式：H（a，b）H（c，d）由于此蘊(yùn)涵式的前件為真，后件為假，所以（2）中的命題為假。 例 2.2 在個(gè)體域分別限制為（a）和（b）條件時(shí)，將下面的命題符號(hào)化：（1）所有人都是要死的。（2）有的人天生就近視。其中：（a）個(gè)體域D1為人類集合。 （b）個(gè)體域D2為全總個(gè)體域。 解（a）令F（x）：x要死的；G（x）：x天生就近視。（1）在個(gè)體域D1中除人外，沒有其他的事物，因而（

21、1）可符號(hào)化為：x F（x）（2）在個(gè)體域D1中有些人是天生就近視，因而（2）可符號(hào)化為謂詞的蘊(yùn)涵式：x G（x） （b）在個(gè)體域D2中除人外，還有其他的事物，因而在將（1）、（2）符號(hào)化時(shí)，必須考慮先將人分離出來，令M（x）：x是人。在D2中，（1）、（2）可分別描述如下：（1） 對(duì)于宇宙間的一切事物，如果事物是人，則他是要死的。（2） 在宇宙間存在著天生就近視的人。將（1）、（2）分別符號(hào)化為： （1） x（M（x）F（x） （2） x（M（x）G（x）在個(gè)體域D1、D2中命題（1）、（2）都是真命題。 例2.3 在個(gè)體域分別限制為（a）和（b）條件時(shí)，將下面的命題符號(hào)化：（1）對(duì)任意的x

22、，都有x2-5x+6 =（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）個(gè)體域D1為自然數(shù)集合。 （b）個(gè)體域D2為實(shí)數(shù)集合。 解 （a）令F（x）：x2-5x+6 =（x-2）（x-3）；G（x）：x+1=0。（1）可符號(hào)化為：x F(x)（2）可符號(hào)化為：x G（x）在個(gè)體域D1中命題（1）為真命題，命題（2）為假命題。（b）在個(gè)體域D2中（1）、（2）符號(hào)化分別為（1） x F（x）（2） x G（x）在個(gè)體域D2中命題（1）、（2）都是真命題。 例2.4 將下列命題符號(hào)化，并指出真值情況。（1）沒有人登上過月球。（2）所有人的頭發(fā)未必都是黑色的。解 個(gè)體域?yàn)槿倐€(gè)體域，令

23、M（x）：x是人。（1）令F（x）：x登上過月球。命題（1）符號(hào)化為：x（M（x）F（x）設(shè)a是1969年登上月球完成阿波羅計(jì)劃的一名美國人，則M（a）F（a）為真，故命題（1）為假。（2）令H（x）：x的頭發(fā)是黑色的。命題（2）可符號(hào)化為：x（M（x）H（x）我們知道有的人頭發(fā)是褐色的，所以x（M（x）H（x）為假，故命題（2）為真。 例2.5 將下列命題符號(hào)化。（1）貓比老鼠跑得快。（2）有的貓比所有老鼠跑得快。（3）并不是所有的貓比老鼠跑得快。（4）不存在跑得同樣快的兩只貓。解 設(shè)個(gè)體域?yàn)槿倐€(gè)體域。令C（x）：x是貓；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y

24、跑得同樣快。這4個(gè)命題分別符號(hào)化為：（1）xy（C（x）M（y）Q（x，y）；（2）x（C（x）y（M（y）Q（x，y）；（3）x y（C（x）M（y）Q（x，y）；（4）x y（C（x）C（y）L（x，y）2.2 謂詞邏輯公式與解釋2.2.1 謂詞邏輯的合式公式 定義2.1 設(shè)P（x1，x2，xn）是n元謂詞公式，其中，x1x2，xn是個(gè)體變項(xiàng)，則稱P（x1，x2，xn）為謂詞演算的原子公式。 定義2.2 謂詞演算的合式公式定義如下：（1）原子公式是合式公式；（2）若A是合式公式，則（A）也是合式公式；（3）若A，B是合式公式，則（AB）、（AB）、（AB）、（AB）是合式公式；（4）若A是

25、合式公式，則x A、x A是合式公式；（5）只有有限次地應(yīng)用（1）（4）構(gòu)成的符號(hào)串才是合式公式。 例2.5 在謂詞邏輯中將下列命題符號(hào)化。（1）不存在最大的數(shù)。（2）計(jì)算機(jī)系的學(xué)生都要學(xué)離散數(shù)學(xué)。解 取個(gè)體域?yàn)槿倐€(gè)體域。（1）令F（x）：x是數(shù)，L（x，y）：x大于y；則命題（1）符號(hào)化為x（F（x） y（F（y） L（x，y）（2）令C（x）：x是計(jì)算機(jī)系的學(xué)生，G（x）：x要學(xué)離散數(shù)學(xué);則命題（2）可符號(hào)化為： x（C（x） G（x） 例2.6 將下列命題符號(hào)化。（1）盡管有人聰明，但并非所有人都聰明。（2）這只大紅書柜擺滿了那些古書。解 （1）令C（x）：x聰明；M（x）：x是人。則

26、命題（1）可符號(hào)化為x（M（x）C（x）x（M（x）C（x）（2）令F（x，y）：x擺滿了y；R（x）：x是大紅書柜；Q（x）:x是古書；a：這只；b：那些。則命題（2）可符號(hào)化為R（a）Q（b）F（a，b） 2.2.2 約束變?cè)c自由變?cè)?1約束變?cè)c自由變?cè)母拍疃x 2.3 在公式x F（x）和x F（x）中，稱x為指導(dǎo)變?cè)現(xiàn)（x ）為相應(yīng)量詞的轄域或作用域。在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，F(xiàn)（x）中不是約束出現(xiàn)的其他變?cè)Q為自由出現(xiàn)。 例2.7 指出下列各式量詞的轄域及變?cè)募s束情況：（1）x（F（x，y） G（x，z）（2）x（P（x）y R（x，y）（3）x（F（

27、x） G（y） y（H（x）M（x，y，z） 解 （1）對(duì)于x的轄域是A=（F（x，y） G（x，z），在A中，x是約束出現(xiàn)的，而且約束出現(xiàn)兩次，y，z均為自由出現(xiàn)，而且各自由出現(xiàn)一次。（2）對(duì)于x的轄域是（P（x）y R（x，y），y的轄域是R（x，y），x，y均是約束出現(xiàn)的。（3）對(duì)于x的轄域是（F（x） G（y），其中x是約束出現(xiàn)的，而y是自由出現(xiàn)的。對(duì)y的轄域是（H（x）M（x，y，z），其中y是約束出現(xiàn)的，而x，z是自由出現(xiàn)的。在整個(gè)公式中，x約束出現(xiàn)一次，自由出現(xiàn)兩次，y約束出現(xiàn)一次，自由出現(xiàn)一次，z僅自由出現(xiàn)一次。 2約束變?cè)膿Q名與自由變?cè)拇?例2.8 對(duì)公式x（P（x）

28、R（x，y）Q（x，y）進(jìn)行換名。解 對(duì)約束變?cè)獂換名為t后為t（P（t） R（t，y）Q（x，y）同理，對(duì)公式中的自由變?cè)部梢愿?，這種更改稱作代入。自由變?cè)拇胍?guī)則是：（1）對(duì)于謂詞公式中的自由變?cè)?，可以代入，此時(shí)需要對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行代入。（2）用以代入的變?cè)c原公式中所有變?cè)拿Q都不能相同。 例2.9 對(duì)公式x（F（x） G（x，y）y H（y）代入。解 對(duì)y實(shí)施代入，經(jīng)過代入后原公式為x（F（x） G（x，t） y H（y）另外，量詞作用域中的約束變?cè)?dāng)論域的元素是有限時(shí)，個(gè)體變?cè)乃锌赡艿娜〈强梢悦杜e的。設(shè)論域元素為a1，a2，an，則 x A（x） A

29、（a1）A（a2）A（an） x A（x） A（a1）A（a2）A（an）。 2.2.3 謂詞邏輯公式的解釋 定義2.4 謂詞邏輯公式的一個(gè)解釋I，是由非空區(qū)域D和對(duì)G中常項(xiàng)符號(hào)、函數(shù)符號(hào)、謂詞符號(hào)以下列規(guī)則進(jìn)行的一組指定組成：（1）對(duì)每一個(gè)常項(xiàng)符號(hào)指定D中一個(gè)元素。（2）對(duì)每一個(gè)n元函數(shù)符號(hào)，指定一個(gè)函數(shù)。（3）對(duì)每一個(gè)n元謂詞符號(hào)，指定一個(gè)謂詞。顯然，對(duì)任意公式G，如果給定G的一個(gè)解釋I，則G在I的解釋下有一個(gè)真值，記作TI（G）。 例2.10 指出下面公式在解釋I下的真值。（1）G=x（P（f（x）Q（x，f（a）；（2）H=x（P（x）Q（x，a）。給出如下的解釋I：D=2，3；a：2

30、；f（2）：3、f（3）：2；P（2）：0、P（3）：1； Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1；解 （1）TI（G）= TI（P（f（2）Q（2，f（2）（P（f（3）Q（3，f（2） = TI（P（3）Q（2，3）（P（2）Q（3，3） = （11）（01） = 1（2）TI（H）= TI（P（2）Q（2，2）P（3）Q（3，2） =0110=0 定義2.5 若存在解釋I，使得G在解釋I下取值為真，則稱公式G為可滿足的，簡稱I滿足G。定義2.6 若不存在解釋I，使得I滿足G，則稱公式G為永假式（或矛盾式）。若G的所有解釋I都滿足G，則稱公式G為永真式（或重

31、言式）。2.3 謂詞邏輯約束公式的等價(jià)與蘊(yùn)涵2.3.1 謂詞邏輯的等價(jià)公式 定義2.7 設(shè)A、B是命題邏輯中的任意兩個(gè)公式，設(shè)它們有共同的個(gè)體域E，若對(duì)任意的解釋I都有TI（A）= TI（B），則稱公式A、B在E上是等價(jià)的，記作AB。 定理1 設(shè)A（x）是謂詞公式，有關(guān)量詞否定的兩個(gè)等價(jià)公式：（1）x A（x）xA（x）（2）x A（x）xA（x） 證明 （1）設(shè)個(gè)體域是有限的為：D= a1，a2，an，則有x A（x）（A（a1）A（a2）A（an）A（a1）A（a2）A（an） xA（x）（2）設(shè)個(gè)體域是有限的為：D= a1，a2，an，則有 x A（x）（A（a1） A（a2）A（an）

32、 A（a1） A（a2）A（an）xA（x）定理2 設(shè)A（x）是任意的含自由出現(xiàn)個(gè)體變項(xiàng)x的公式，B是不含x出現(xiàn)的公式，則有（1）x（A（x）B）x A（x）B（2）x（A（x）B）x A（x）B（3）x（A（x） B）x A（x） B（4）x（BA（x）B x A（x）（5）x（A（x）B） x A（x）B（6）x（A（x）B）x A（x）B（7）x（A（x） B）x A（x） B（8）x（BA（x）Bx A（x）證明 （1）設(shè)D是個(gè)體域，I為任意解釋，即用確定的命題及確定的個(gè)體代替出現(xiàn)在x（A（x）B）和x A（x）B中的命題變?cè)蛡€(gè)體變?cè)?，于是得到兩個(gè)命題，若對(duì)x（A（x）B）代替之后所

33、得命題的真值為真，此時(shí)必有A（x）B的真值為真；因而A（x）真值為真或B的真值為真，若B的真值為真，則x A（x）B的真值為真；若B的真值為假，則必有對(duì)D中任意x都使得A（x）的真值為真，所以x（A（x）B）為真，從而x A（x）B為真。若對(duì)x（A（x）B）代替之后所得命題的真值為假，則A（x）和B的真值必為假，因此x A（x）B的真值為假；所以x（A（x）B）為假，有x A（x）B為假。（2）、（5）和（6）證明與（1）類似，證明過程略。（3）x（A（x） B）x（A（x）B） xA（x） B x A（x）B x A（x） B（4）、（7）、（8）證明與（3）類似，證明過程略。 定理3 設(shè)A

34、（x）、B（x）是任意包含自由出現(xiàn)個(gè)體變?cè)獂的公式,則有：（1）x（A（x）B（x）x A（x）x B（x）（2）x（A（x）B（x）x A（x）x B（x） 證明 （1）設(shè)D是任一個(gè)體域，若x（A（x）B（x）的真值為真，則對(duì)任意aD，有A（a）和B（a）同時(shí)為真，即x A（x）為真、x B（x）為真，從而x A（x）x B（x）為真。若x（A（x）B（x）的真值為假，則對(duì)任意aD，有A（a）和B（a）不能同時(shí)為真，即x A（x）和 x B（x）的真值不能同時(shí)為真，從而x A（x）x B（x）的真值為假。綜上所述 x（A（x）B（x）x A（x）x B（x） （2）設(shè)D是任一個(gè)體域，若x（A

35、（x）B（x）的真值為真,則存在aD，使得A（a）B（a）為真，即A（a）為真或B（a）為真，即x A（x）為真或x B（x）為真，從而x A（x）x B（x）為真。若x（A（x）B（x）的真值為假，則存在aD，使得A（a）B（a）為假，此時(shí)，A（a）為假，B（a）為假，從而x A（x）x B（x）的真值為假。綜上所述 x（A（x）B（x）x A（x）x B（x） 例2.11 證明下列各等價(jià)式（1）x（A（x）B（x）x（A（x）B（x）（2）x（A（x） B（x）x（A（x）B（x）證明 （1）x（A（x）B（x） x （A（x）B（x） x（A（x）B（x） x（A（x）B（x） （2）x

36、（A（x） B（x） x （A（x） B（x） x （A（x）B（x） x（A（x）B（x） 2.3.2 謂詞邏輯的蘊(yùn)涵公式 定義2.8 設(shè)A、B是命題邏輯中的任意兩個(gè)公式，若AB是永真式，則稱公式A蘊(yùn)涵公式B，記作AB。 定理4 下列蘊(yùn)涵式成立（1）x A（x）x B（x）x（A（x）B（x）（2）x（A（x）B（x）x A（x）x B（x）（3）x（A（x） B（x）x A（x） x B（x）（4）x（A（x） B（x）x A（x） x B（x）（5）x A（x） x B（x）x（A（x） B（x） 證明： （1）設(shè)x A（x）x B（x）在任意解釋下的真值為真，即對(duì)個(gè)體域中的每一個(gè)x。都

37、能使A（x）的真值為真或者對(duì)個(gè)體域中的每一個(gè)x都能使B（x）的真值為真，無論哪種情況，對(duì)于個(gè)體域中的每一個(gè)x都能使A（x）B（x）的真值為真。因此，蘊(yùn)涵式x A（x）x B（x）x（A（x）B（x）成立。 （2）設(shè)個(gè)體域?yàn)镈，在解釋I下x（A（x）B（x）的真值為真，即存在aD使得A（a）B（a）為真，從而A（a）為真，B（a）為真，故有x A（x）、x B（x）均為真，所以，蘊(yùn)涵式x（A（x）B（x）x A（x）x B（x）成立。（3）設(shè)個(gè)體域?yàn)镈，在解釋I下x A（x） x B（x）的真值為假,即存在aD使得A（a） B（a）為假，所以蘊(yùn)涵式x（A（x） B（x）x A（x） x B（x）

38、成立。（4）x（A（x） B（x）（x A（x） x B（x） x（A（x） B（x）（x A（x） x B（x） x（A（x） B（x）（x A（x）x B（x） x（A（x） B（x）x A（x）x B（x） （x（A（x） B（x）x A（x）x B（x） （x（A（x） B（x）x A（x）x B（x）（5）x A（x） x B（x）x A（x）x B（x） x A（x）x B（x） x（A（x）B（x） x（A（x） B（x） 2.3.3 多個(gè)量詞的使用 定義2.9 設(shè)謂詞公式G，不包含聯(lián)結(jié)詞，。把G中出現(xiàn)的聯(lián)結(jié)詞，互換；命題常量T，F(xiàn)互換；量詞，互換之后得到的公式稱為G的對(duì)偶公式，

39、記作G*。 定理5（對(duì)偶定理） 設(shè)A、B是任意兩個(gè)公式并且不包含聯(lián)結(jié)詞，。若AB，則A*B*。2.4 前束范式 定義2.10 一個(gè)謂詞公式，如果量詞均在全式的開頭，且轄域延伸到公式的末尾，則該公式稱為前束范式。 定理6 對(duì)任意一個(gè)謂詞公式都可以化為與它等價(jià)的前束范式。證明 首先利用等價(jià)公式將謂詞公式中的聯(lián)結(jié)詞，去掉。其次利用量詞的轉(zhuǎn)化律將量詞前面的否定深入到謂詞前面，在利用改名和代入規(guī)則以及量詞轄域擴(kuò)張的公式將量詞移到全式的最前面，這樣便得到前束范式。 例2.12 求下列謂詞公式的前束范式。（1）x y（z A（x，z）A（x，z）t B（x，y，t）解 （1）x y（z A（x，z）A（x，

40、z） t B（x，y，t） x y（z A（x，z）A（x，z）t B（x，y，t） x y（zA（x，z）A（x，z）t B（x，y，t） （量詞轉(zhuǎn)化） x y（wA（x，w）A（x，z）t B（u，v，t） （改名及代入規(guī)則） x y w t（A（x，w）A（x，z）B（u，v，t）（量詞轄域擴(kuò)張）（2）x（y P（x，y） x y（Q（x，y）y（P（y，x）Q（x，y） 解 （2）x（y P（x，y） x y（Q（x，y）y（P（y，x）Q（x，y） x（y P（x，y）x y（Q（x，y）y（P（y，x）Q（x，y） x（y P（x，y）xy（Q（x，y）y（P（y，x） Q（x，y

41、） （量詞轉(zhuǎn)化、德·摩根定律） x（y P（x，y）x y（Q（x，y）z（P（z，x）Q（x，z） （改名原則）x（y P（x，y）x y z（Q（x，y）（P（z，x）Q（x，z） （量詞轄域擴(kuò)張） x（y P（x，y）u v z（Q（u，v）（P（z，u）Q（u，z） （改名原則）x y u v z （P（x，y）（ Q（u，v）（P（z，u）Q（u，z） （量詞轄域擴(kuò)張） 定義2.11 若一個(gè)謂詞公式，具有如下形式，則稱該公式為前束析取范式。 定義2.12 若一個(gè)謂詞公式，具有如下形式，則稱該公式為前束合取范式。 定理7 任意謂詞公式都可以化為與其等價(jià)的前束析取范式和前束合取

42、范式。2.5 謂詞演算的推理理論 1全稱指定規(guī)則（簡稱US規(guī)則） 這條規(guī)則有下面兩種形式：(1)x P（x）P（y）(2)x P（x）P（c）其中，P是謂詞，（1）中y為任意不在P（x）中約束出現(xiàn)的個(gè)體變?cè)?；?）中c為個(gè)體域中的任意一個(gè)個(gè)體常元。 2存在指定規(guī)則（簡稱ES規(guī)則） x P（x）P（c）其中，c為個(gè)體域中使P成立的特定個(gè)體常元。必須注意，應(yīng)用存在指定規(guī)則，其指定的個(gè)體c不是任意的。 3全稱推廣規(guī)則（簡稱UG規(guī)則） P（y）x P（x） 4存在推廣規(guī)則（簡稱EG規(guī)則）P（c）x P（x）其中，c為個(gè)體域中的個(gè)體常元，這個(gè)規(guī)則比較明顯，對(duì)于某些個(gè)體c，若P（c）成立，則個(gè)體域中必有x

43、 P（x）。 例2.13 證明 x（M（x） D（x）M（s）D（s）這是著名的蘇格拉底三段論的論證。其中 M（x）：x是一個(gè)人。 D（x）：x是要死的。 s：蘇格拉底。證明 （1）x（M（x） D（x） P （2）M（s） D（s） US（1） （3）M（s） P （4）D（s） T（2）（3）I 例 2.14 判斷下列的推理過程是否正確。 （1）x y G（x，y） P （2）y G（z，y） US（1） （3）G（z，c） ES（2） （4）x G（x，c） UG（3） （5）y x G（x，y） EG（4） 解 這個(gè)推理過程是錯(cuò)誤的，因?yàn)閺乃梢缘贸鼋Y(jié)論： x y G（x，y）y x G（x，y）從前面的學(xué)習(xí)中我們知道這個(gè)式子不成立。它的推導(dǎo)錯(cuò)誤出現(xiàn)在第（3）步。x y G（x，y）的含義是：對(duì)于任意的一個(gè)x，存在著與它對(duì)應(yīng)的y，使得G（x，y）成立。但是，對(duì)y G（z，y）利用ES規(guī)則消去存在變量后得到G（z，c）的含義卻是：對(duì)于任意個(gè)體z，有同一個(gè)體c，使得G（z，c）成立。顯然，G（z，c）不是y G（z，y）的有效結(jié)論。因此，使用ES規(guī)則x P（x）P（c）消去存在量詞的條件是:P（x）中除x外沒有