1離散數(shù)學21世紀高職高專新概念教材2第1章

命題邏輯

1.1命題及其表示法1.2命題聯(lián)結(jié)詞

1.3命題公式、翻譯與解釋

1.4真值表與等價公式

1.5對偶與范式

1.6公式的蘊涵

1.7其它聯(lián)結(jié)詞與最小聯(lián)結(jié)詞組

1.8命題邏輯推理理論

31.1命題及其表示法1.1.1命題的概念

數(shù)理邏輯將能夠判斷真假的陳述句稱作命題。

1.1.2命題的表示

命題通常使用大寫字母A，B，…，Z或帶下標的大寫字母或數(shù)字表示，如Ai，[10]，R等，例如A1：我是一名大學生。A1:我是一名大學生.[10]：我是一名大學生。R：我是一名大學生。41.2命題聯(lián)結(jié)詞1.2.1否定聯(lián)結(jié)詞1.2.2合取聯(lián)結(jié)詞1.2.3析取聯(lián)結(jié)詞1.2.4條件聯(lián)結(jié)詞1.2.5雙條件聯(lián)結(jié)詞1.2.6與非聯(lián)結(jié)詞1.2.7或非聯(lián)結(jié)詞51.2聯(lián)結(jié)詞1.2.1否定聯(lián)結(jié)詞﹁P

P﹁P0110PQP∧Q0000101001111.2.3析取聯(lián)結(jié)詞∨PQP∨Q0000111011111.2.2合取聯(lián)結(jié)詞∧61.2聯(lián)結(jié)詞PQP→Q0010111001111.2.4條件聯(lián)結(jié)詞→

1.2.5雙條件聯(lián)結(jié)詞

PQP

Q00101010011171.2聯(lián)結(jié)詞1.2.6與非聯(lián)結(jié)詞↑

PQP↑Q001011101110性質(zhì)：（1）P↑P

﹁（P∧P）

﹁P；（2）（P↑Q）↑（P↑Q）

﹁（P↑Q）

P∧Q；（3）（P↑P）↑（Q↑Q）

﹁P↑﹁Q

P∨Q。81.2聯(lián)結(jié)詞1.2.7或非聯(lián)結(jié)詞↓

PQP↓Q001010100110性質(zhì)：（1）P↓P

﹁（P∨Q）

﹁P；（2）（P↓Q）↓（P↓Q）

﹁（P↓Q）

P∨Q；（3）（P↓P）↓（Q↓Q）

﹁P↓﹁Q﹁（﹁P∨﹁Q）

P∧Q。91.3命題公式、翻譯與解釋1.3.1命題公式1.3.2命題的翻譯1.3.3命題公式的解釋

101.3命題公式、翻譯與解釋1.3.1命題公式定義命題公式，簡稱公式，定義為：（1）單個命題變元是公式；（2）如果P是公式，則﹁P是公式；（3）如果P、Q是公式，則P∧Q、P∨Q、P

Q、

P

Q都是公式；（4）當且僅當能夠有限次的應用(1)、(2)、(3)

所得到的包括命題變元、聯(lián)結(jié)詞和括號的符號串是公式。111.3命題公式、翻譯與解釋1.3.1命題公式例如，下面的符號串都是公式： （（（（﹁P）∧Q）

R）∨S） （（P

﹁Q）

（﹁R∧S）） （﹁P∨Q）∧R以下符號串都不是公式： （（P∨Q）

（∧Q）） （∧Q）121.3命題公式、翻譯與解釋1.3.2命題的翻譯

可以把自然語言中的有些語句，轉(zhuǎn)變成數(shù)理邏輯中的符號形式，稱為命題的翻譯。命題翻譯時應注意下列事項：（1）確定所給句子是否為命題。（2）句子中聯(lián)結(jié)詞是否為命題聯(lián)結(jié)詞。（3）要正確的選擇原子命題和合適的命題聯(lián)結(jié)詞。

131.3命題公式、翻譯與解釋1.3.2命題的翻譯

解：設(shè)P：上午下雨；Q：我去看電影；R：我在家里讀書；S：我在家里看報。本例可表示為：（

P

Q）∧（P

（R∨S））。

例：假如上午不下雨，我去看電影，否則就在家里讀書或看報。

141.3命題公式、翻譯與解釋1.3.3命題公式的解釋定義設(shè)P1，P2，…，Pn是出現(xiàn)在命題公式G中的全部命題變元，指定P1，P2，…，Pn的一組真值，稱這組真值為G的一個解釋或賦值，記作I，公式G在I下的真值記作TI（G）。例如，G=（

P∧Q）

R，則I：

PQR110是G的一個解釋，在這個解釋下G的真值為1，即TI（G）=1。151.4真值表與等價公式

1.4.1真值表1.4.2命題公式的分類1.4.3等價公式1.4.4置換規(guī)則

161.4真值表與等價公式

1.4.1真值表

定義將公式G在其所有解釋下所取得的真值列成一個表，稱為G的真值表。

構(gòu)造真值表的方法如下：（1）找出公式G中的全部命題變元，并按一定的順序排列成P1，P2，…，Pn。（2）列出G的2n個解釋，賦值從00…0（n個）開始，按二進制遞加順序依次寫出各賦值，直到11…1為止（或從11…1開始，按二進制遞減順序?qū)懗龈髻x值，直到00…0為止），然后從低到高的順序列出G的層次。（3）根據(jù)賦值依次計算各層次的真值并最終計算出G的真值。171.4真值表與等價公式

1.4.1真值表例：G=

（P→Q

）∧QpQP→Q

（P→Q

）

（P→Q

）∧Q00100011001001011100181.4真值表與等價公式1.4.2命題公式的分類

定義設(shè)G為公式：（1）如果G在所有解釋下取值均為真，則稱G是永真式或重言式；（2）如果G在所有解釋下取值均為假，則稱G是永假式或矛盾式；（3）如果至少存在一種解釋使公式G取值為真，則稱G是可滿足式。

191.4真值表與等價公式1.4.3等價公式

定義設(shè)A和B是兩個命題公式，如果A和B在任意賦值情況下都具有相同的真值，則稱A和B是等價公式。記為A

B。

性質(zhì)：定理設(shè)A、B、C是公式，則（1）A

A（2）若A

B則B

A（3）若A

B且B

C則A

C201.4真值表與等價公式1.4.3等價公式定理1.2設(shè)A、B、C是公式，則下述等價公式成立：（1）雙重否定律

A

A（2）等冪律 A∧A

A；A∨A

A（3）交換律 A∧B

B∧A；A∨B

B∨A（4）結(jié)合律 （A∧B）∧C

A∧（B∧C） （A∨B）∨C

A∨（B∨C）（5）分配律 （A∧B）∨C

（A∨C）∧（B∨C） （A∨B）∧C

（A∧C）∨（B∧C）（6）德·摩根律

（A∨B）

A∧

B

（A∧B）

A∨

B211.4真值表與等價公式1.4.3等價公式（7）吸收律 A∨（A∧B）

A；A∧（A∨B）

A（8）零一律 A∨1

1；A∧0

0（9）同一律 A∨0

A；A∧1

A（10）排中律 A∨

A

1（11）矛盾律 A∧

A

0（12）蘊涵等值式 A→B

A∨B（13）假言易位 A→B

B→

A（14）等價等值式 A

B

（A→B）∧（B→A）（15）等價否定等值式 A

B

A

B

B

A（16）歸繆式 （A→B）∧（A→

B）

A221.4真值表與等價公式1.4.4置換規(guī)則

定理（置換規(guī)則）

設(shè)

（A）是一個含有子公式A的命題公式，

（B）是用公式B置換了

（A）中的子公式A后得到的公式，如果A

B，那么

（A）

（B）。

231.5對偶與范式

1.5.1對偶1.5.2范式1.5.3主范式

241.5對偶與范式

1.5.1對偶定義在僅含有聯(lián)結(jié)詞

、∧、∨的命題公式A中，將聯(lián)結(jié)詞∧換成∨，將∨換成∧，如果A中含有特殊變元0或1，就將0換成1，1換成0，所得的命題公式A*稱為A的對偶式。例：公式（

P∨Q）∧（P∨

Q）的對偶式為：（

P∧Q）∨（P∧

Q）251.5對偶與范式

1.5.1對偶定理設(shè)A和A*互為對偶式，P1，P2，…，Pn是出現(xiàn)在A和A*中的所有原子變元，若將A和A*寫成n元函數(shù)形式，則（1）

A（P1，P2，…，Pn）

A*（

P1，

P2，…，

Pn）（2）A（

P1，

P2，…，

Pn）

A*（P1，P2，…，Pn）定理（對偶原理）設(shè)A、B是兩個命題公式，若A

B，則A*

B*，其中A*、B*分別為A、B的對偶式。

261.5對偶與范式

1.5.2范式定義僅由有限個命題變元及其否定構(gòu)成的析取式稱為簡單析取式，僅由有限個命題變元及其否定構(gòu)成的合取式稱為簡單合取式。定義僅由有限個簡單合取式構(gòu)成的析取式稱為析取范式。僅由有限個簡單析取式構(gòu)成的合取式稱為合取范式。定理（范式存在定理）任何命題公式都存在著與之等價的析取范式和合取范式。

271.5對偶與范式

1.5.3主范式

定義在含有n個命題變元P1，P2，…，Pn的簡單合取范式中，若每個命題變元或其否定不同時存在，但二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變元或其否定出現(xiàn)在從左起的第i個位置上（若命題變元無腳標，則按字典順序排列），這樣的簡單合取式稱為極小項。相應的，滿足上述條件的簡單析取式稱為極大項。n個命題變元P1，P2，…，Pn的極小項用公式可表示為Pi*，極大項可表示為Pi*，其中，Pi*為Pi或

Pi（i=1，2，…，n）。281.5對偶與范式

1.5.3主范式定義設(shè)G為公式，P1，P2，…，Pn為G中的所有命題變元，若G的析取范式中每一個合取項都是P1，P2，…，Pn的一個極小項，則稱該析取范式為G的主析取范式。矛盾式的主析取范式為0。定理任意的命題公式都存在一個唯一的與之等價的主析取范式。291.5對偶與范式

1.5.3主范式用等值演算求主析取范式步驟如下：（1）求G的析取范式G'；（2）若G中某個簡單合取式m中沒有出現(xiàn)某個命題變元Pi或其否定

Pi，則將m作如下等價變換：m

m∧（Pi∨

Pi）

（m∧Pi）∨（m∧

Pi）（3）將重復出現(xiàn)的命題變元、矛盾式和重復出現(xiàn)的極小項都消去；（4）重復步驟（2）、（3），直到每一個簡單合取式都為極小項；（5）將極小項按腳標由小到大的順序排列，并用∑表示。如m0∨m1∨m7可表示為∑（0，1，7）。301.5對偶與范式

1.5.3主范式定義1.18設(shè)G為公式，P1，P2，…，Pn為G中的所有命題變元，若G的合取范式中每一個析取項都是P1，P2，…，Pn的一個極大項，則稱該合取范式為G的主合取范式。通常，主合取范式用∏表示。重言式的主合取范式中不含任何極大項，用1表示。定理1.8任意的命題公式都存在一個唯一的與之等價的主合取范式。

311.6公式的蘊涵1.6.1蘊涵的概念1.6.2基本蘊涵式

321.6公式的蘊涵1.6.1蘊涵的概念定義設(shè)G、H是兩個公式，若G→H是永真式，則稱G蘊涵H，記作G

H。蘊涵關(guān)系有如下性質(zhì)：（1）對于任意公式G，有G

G；（2）對任意公式G、H，若G

H且H

G，則G

H；（3）若G

H且H

L，則G

L。廣義的蘊涵概念。定義設(shè)G1，G2，…，Gn，H是公式，如果（G1∧G2∧…∧Gn）→H是永真式，則稱G1，G2，…，Gn蘊涵H，又稱H是G1，G2，…，Gn的邏輯結(jié)果，記作（G1∧G2∧…∧Gn）

H或（G1，G2，…，Gn）

H。331.6公式的蘊涵1.6.2基本蘊涵式（1）P∧Q

P；（2）P∧Q

Q；（3）P

P∨Q；（4）Q

P∨Q；（5）

P

（P→Q）；（6）Q

（P→Q）；（7）

（P→Q）

P；（8）

（P→Q）

Q；（9）P，P→Q

Q；（10）

Q，P→Q

P；（11）

P，P∨Q

Q；（12）P→Q，Q→R

P→R；（13）P∨Q，P→R，Q→R

R；（14）P→Q，R→S

（P∧R）→（Q∧S）；（15）P，Q

P∧Q。341.7其它聯(lián)結(jié)詞與最小聯(lián)結(jié)詞組1.7.1其它聯(lián)結(jié)詞1.7.2最小聯(lián)結(jié)詞組

351.7其它聯(lián)結(jié)詞與最小聯(lián)結(jié)詞組1.7.1其它聯(lián)結(jié)詞定義設(shè)P、Q為命題公式，則復合命題PQ稱為P和Q的不可兼析取，當且僅當P與Q的真值不相同時，PQ的真值為1，否則PQ的真值為假。定義設(shè)P、Q是兩個命題公式，復合命題PcQ稱為命題P、Q的條件否定，當且僅當P的真值為1，Q的真值為0時，PcQ的真值為1，否則

PcQ的真值為0。

361.7其它聯(lián)結(jié)詞與最小聯(lián)結(jié)詞組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é)詞的全功能集。定理

{

，∧，∨}是聯(lián)結(jié)詞的全功能集。

定理{

，∧}，{

、∨}，{

，→}是最小聯(lián)結(jié)詞組。定理{↑}，{↓}是最小聯(lián)結(jié)詞組。371.8命題邏輯推理理論

1.8.1命題邏輯推理理論1.8.2推理規(guī)則1.8.3推理常用方法

381.8命題邏輯推理理論1.8.1命題邏輯推理理論定義如果G1，G2，…，Gn蘊涵H，則稱H能夠由G1，G2，…，Gn有效推出，G1，G2，…，Gn稱為H的前提，H稱為G1，G2，…，Gn的有效結(jié)論。稱（G1∧G2∧…∧Gn）→H是由前提G1，G2，…，Gn推結(jié)論H的推理的形式結(jié)構(gòu)。

391.8命題邏輯推理理論1.8.2推理規(guī)則下面給出推理中常用的推理規(guī)則。1．前提引入規(guī)則：可以在證明的任何時候引入前提；2．結(jié)論引入規(guī)則：在證明的任何時候，已證明的結(jié)論都可以作為后續(xù)證明的前提；3．置換規(guī)則：在證明的任何時候，命題公式中的任何子命題公式都可以用與之等價的命題公式置換。4．假言推理規(guī)則：P，P→Q

Q5．附加規(guī)則：P

P∨Q；6．化簡規(guī)則：P，Q

P；401.8命題邏輯推理理論1.8.2推理規(guī)則7．拒取式規(guī)則：

Q，P→Q

P；8．假言三段論規(guī)則：P→Q，Q→R

P→R；9．析取三段論規(guī)則：

P，P∨Q

Q；10．構(gòu)造性二難規(guī)則：P∨Q，P→R，Q→R

R；11．合取引入規(guī)則：P，Q

P∧Q411.8命題邏輯推理理論1.8.3推理常用方法

1、直接證法直接證法就是根據(jù)一組前提，利用前面提供的一些推理規(guī)則，根據(jù)已知的等價公式和蘊涵式，推演得到有效的結(jié)論的方法，即有前提直接推導出結(jié)論。

421.8命題邏輯推理理論1、直接證法例構(gòu)造下列推理的證明。前提：P∨Q，P→R，Q→S結(jié)論：S∨R證明（1）P∨Q 前提引入規(guī)則（2）P→R 前提引入規(guī)則（3）Q→S 前提引入規(guī)則（4）S∨R （1）（2）（3）構(gòu)造性二難規(guī)則

431.8命題邏輯推理理論2．間接證法間接證法主要有如下兩種情況。（1）附加前提證明法有時要證明的結(jié)論以蘊涵式的形式出現(xiàn)，即推理的形式結(jié)構(gòu)為：（G1∧G2∧…∧Gn）

（R→C）設(shè)（G1∧G2∧…∧Gn）為S，則上述推理可表示為證明S

（R→C），即證明S→（R→C）為永真式。441.8命題邏輯推理理論例1.25用附加前提證明法證明下面推理。前提：P→（Q→R），

S∨P，Q結(jié)論：S→R證明：（1）

S∨P 前提引入規(guī)則（2）S 附加前提引入規(guī)則（3）P （1）（2）析取三段論規(guī)則（4）P→（Q→R） 前提引入規(guī)則（5）Q→R （3）（4）假言推理規(guī)則（6）Q 前提引入規(guī)則（7）R （5）（6）假言推理規(guī)則451.8命題邏輯推理理論（2）歸繆法定義1.25設(shè)G1，G2，…，Gn是n個命題公式，如果G1∧G2∧…∧Gn是可滿足式，則稱G1，G2，…，Gn是相容的。否則（即G1∧G2∧…∧Gn是矛盾式）稱G1，G2，…，Gn是不相容的。461.8命題邏輯推理理論（2）歸繆法例用歸繆法證明。前提：P∨Q，P→R，Q→S結(jié)論：S∨R證明（1）

（S∨R） 附加前提引入規(guī)則（2）

S∧

R （1）置換規(guī)則（3）

S （2）化簡規(guī)則（4）

R （2）化簡規(guī)則（5）Q→S 前提引入規(guī)則（6）

Q∨S （5）置換規(guī)則（7）

Q （3）（6）析取三段論規(guī)則47（8）P∨Q 前提引入規(guī)則（9）P （7）（8）析取三段論規(guī)則（10）P→R 前提引入規(guī)則（11）

P∨R （10）置換規(guī)則（12）R （9）（11）析取三段論規(guī)則（13）

R∧R （4）（12）合取引入規(guī)則1.8命題邏輯推理理論48本章小結(jié)

本章首先引入命題、簡單命題、復合命題和邏輯聯(lián)結(jié)詞，并在此基礎(chǔ)上定義了公式、公式的翻譯和解釋、真值表與等價公式、對偶與范式、蘊涵等概念，然后介紹了用等價式、蘊涵式等進行命題演算和推理的方法。本章初步體現(xiàn)了數(shù)理邏輯的基本觀點和基本方法，為本課程后續(xù)的學習和將來從事計算機工作打下良好的邏輯基礎(chǔ)。

49第二章謂詞邏輯本章學習目標命題邏輯中原子命題是最小的單位，不能夠再進行分解，這給推理帶來了很大局限性，本章引入謂詞邏輯。學習關(guān)于謂詞邏輯的相關(guān)概念和定理，解決實際問題。50第二章謂詞邏輯

2.1謂詞邏輯命題的符號化

2.2謂詞邏輯公式與解釋2.3謂詞邏輯約束公式的等價與蘊涵2.4前束范式2.5謂詞演算的推理理論51第二章謂詞邏輯2．謂詞：用來刻畫個體詞的性質(zhì)或個體詞之間關(guān)系的詞

一般來說，“x是A”類型的命題可以用A（x）表達。對于

“x大于y”這種兩個個體之間關(guān)系的命題，可表達為B（x，y），這里B表示“…大于…”謂詞。我們把A（x）稱為一元謂詞，

B（x，y）稱為二元謂詞，M（a，b，c）稱為三元謂詞，依次類推，通常把二元以上謂詞稱作多元謂詞。

2.1謂詞邏輯命題的符號化

1．個體詞：個體詞是指研究對象中不依賴于人的主觀而獨立存在的具體的或抽象的客觀實體

個體常項或個體常元：個體變項或個體變元：個體域或論域：52第二章謂詞邏輯2.1謂詞邏輯命題的符號化

解（1）設(shè)謂詞G（x）：x是素數(shù)，a：4，b：8；（1）中的題符號化為謂詞的蘊涵式：G（a）→G（b）由于此蘊涵式的前件為假，所以（1）中的命題為真。（2）設(shè)謂詞H（x，y）：x小于y，a：2，b：3，c：8，d：7（2）中的命題符號化為謂詞的蘊涵式：H（a，b）→H（c，d）由于此蘊涵式的前件為真，后件為假，所以（2）中的命題為假。例2.1將下列命題在謂詞邏輯中符號化，并討論它們的真值：（1）只有4是素數(shù)，8才是素數(shù)。（2）如果2小于3，則8小于7。53第二章謂詞邏輯2.1謂詞邏輯命題的符號化

解（a）令F（x）：x要死的；G（x）：x天生就近視。（1）在個體域D1中除人外，沒有其他的事物，因而（1）可符號化為：

xF（x）（2）在個體域D1中有些人是天生就近視，因而（2）可符號化為例2.2在個體域分別限制為（a）和（b）條件時，將下面的命題符號化：（1）所有人都是要死的。（2）有的人天生就近視。其中：（a）個體域D1為人類集合。（b）個體域D2為全總個體域。54第二章謂詞邏輯2.1謂詞邏輯命題的符號化

謂詞的蘊涵式：

xG（x）（b）在個體域D2中除人外，還有其他的事物，因而在將（1）、（2）符號化時，必須考慮先將人分離出來，令M（x）：x是人。在D2中，（1）、（2）可分別描述如下：（1）對于宇宙間的一切事物，如果事物是人，則他是要死的。（2）在宇宙間存在著天生就近視的人。將（1）、（2）分別符號化為：（1）

x（M（x）

F（x））（2）

x（M（x）

G（x））在個體域D1、D2中命題（1）、（2）都是真命題。55第二章謂詞邏輯2.1謂詞邏輯命題的符號化

例2.3在個體域分別限制為（a）和（b）條件時，將下面的命題符號化：（1）對任意的x，都有x2-5x+6

=（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）個體域D1為自然數(shù)集合。（b）個體域D2為實數(shù)集合。56第二章謂詞邏輯2.1謂詞邏輯命題的符號化

解（a）令F（x）：x2-5x+6

=（x-2）（x-3）；G（x）：x+1=0。（1）可符號化為：

xF(x)（2）可符號化為：

xG（x）在個體域D1中命題（1）為真命題，命題（2）為假命題。（b）在個體域D2中（1）、（2）符號化分別為（1）

xF（x）（2）

xG（x）在個體域D2中命題（1）、（2）都是真命題。57第二章謂詞邏輯2.1謂詞邏輯命題的符號化

例2.4將下列命題符號化，并指出真值情況。（1）沒有人登上過月球。（2）所有人的頭發(fā)未必都是黑色的。解個體域為全總個體域，令M（x）：x是人。（1）令F（x）：x登上過月球。命題（1）符號化為：

x（M（x）∧F（x））設(shè)a是1969年登上月球完成阿波羅計劃的一名美國人，則M（a）∧F（a）為真，故命題（1）為假。（2）令H（x）：x的頭發(fā)是黑色的。命題（2）可符號化為：

x（M（x）

H（x））我們知道有的人頭發(fā)是褐色的，所以

x（M（x）

H（x））為假，故命題（2）為真。

58第二章謂詞邏輯2.1謂詞邏輯命題的符號化

例2.5將下列命題符號化。（1）貓比老鼠跑得快。（2）有的貓比所有老鼠跑得快。（3）并不是所有的貓比老鼠跑得快。（4）不存在跑得同樣快的兩只貓。解設(shè)個體域為全總個體域。令C（x）：x是貓；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同樣快。這4個命題分別符號化為：（1）

x

y（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）））。59第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

定義2.1設(shè)P（x1，x2，…，xn）是n元謂詞公式，其中，x1x2，…，xn是個體變項，則稱P（x1，x2，…，xn）為謂詞演算的原子公式。定義2.2謂詞演算的合式公式定義如下：（1）原子公式是合式公式；（2）若A是合式公式，則（﹁A）也是合式公式；（3）若A，B是合式公式，則（A∧B）、（A∨B）、（A→B）、（A?B）是合式公式；（4）若A是合式公式，則

xA、

xA是合式公式；（5）只有有限次地應用（1）~（4）構(gòu)成的符號串才是合式公式。60第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

例2.5在謂詞邏輯中將下列命題符號化。（1）不存在最大的數(shù)。（2）計算機系的學生都要學離散數(shù)學。解取個體域為全總個體域。（1）令F（x）：x是數(shù)，L（x，y）：x大于y；則命題（1）符號化為﹁

x（F（x）∧

y（F（y）→L（x，y）））（2）令C（x）：x是計算機系的學生，G（x）：x要學離散數(shù)學;則命題（2）可符號化為：

x（C（x）→G（x））61第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.1謂詞邏輯的合式公式

例2.6將下列命題符號化。（1）盡管有人聰明，但并非所有人都聰明。（2）這只大紅書柜擺滿了那些古書。解（1）令C（x）：x聰明；M（x）：x是人。則命題（1）可符號化為

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）可符號化為R（a）∧Q（b）∧F（a，b）62第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.2約束變元與自由變元1．約束變元與自由變元的概念定義2.3在公式

xF（x）和

xF（x）中，稱x為指導變元，F(xiàn)（x）為相應量詞的轄域或作用域。在

x和

x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，F(xiàn)（x）中不是約束出現(xiàn)的其他變元均稱為自由出現(xiàn)。63第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.2約束變元與自由變元例2.7指出下列各式量詞的轄域及變元的約束情況：（1）

x（F（x，y）→G（x，z））（2）

x（P（x）→

yR（x，y））（3）

x（F（x）→G（y））→

y（H（x）∧M（x，y，z））64第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.2約束變元與自由變元解（1）對于

x的轄域是A=（F（x，y）→G（x，z）），在A中，x是約束出現(xiàn)的，而且約束出現(xiàn)兩次，y，z均為自由出現(xiàn)，而且各自由出現(xiàn)一次。（2）對于

x的轄域是（P（x）→

yR（x，y）），

y的轄域是R（x，y），x，y均是約束出現(xiàn)的。（3）對于

x的轄域是（F（x）→G（y）），其中x是約束出現(xiàn)的，而y是自由出現(xiàn)的。對

y的轄域是（H（x）∧M（x，y，z）），其中y是約束出現(xiàn)的，而x，z是自由出現(xiàn)的。在整個公式中，x約束出現(xiàn)一次，自由出現(xiàn)兩次，y約束出現(xiàn)一次，自由出現(xiàn)一次，z僅自由出現(xiàn)一次。65第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.2約束變元與自由變元2．約束變元的換名與自由變元的代入例2.8對公式

x（P（x）→R（x，y））∧Q（x，y）進行換名。解對約束變元x換名為t后為

t（P（t）→R（t，y））∧Q（x，y）同理，對公式中的自由變元也可以更改，這種更改稱作代入。自由變元的代入規(guī)則是：（1）對于謂詞公式中的自由變元，可以代入，此時需要對公式中出現(xiàn)該自由變元的每一處進行代入。（2）用以代入的變元與原公式中所有變元的名稱都不能相同。66第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.2約束變元與自由變元2．約束變元的換名與自由變元的代入例2.9對公式

x（F（x）→G（x，y））∧

yH（y）代入。解對y實施代入，經(jīng)過代入后原公式為

x（F（x）→G（x，t））∧

yH（y）另外，量詞作用域中的約束變元，當論域的元素是有限時，個體變元的所有可能的取代是可以枚舉的。設(shè)論域元素為a1，a2，…，an，則

xA（x）

A（a1）∧A（a2）∧…∧A（an）

xA（x）

A（a1）∨A（a2）∨…∨A（an）。67第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.3謂詞邏輯公式的解釋定義2.4謂詞邏輯公式的一個解釋I，是由非空區(qū)域D和對G中常項符號、函數(shù)符號、謂詞符號以下列規(guī)則進行的一組指定組成：（1）對每一個常項符號指定D中一個元素。（2）對每一個n元函數(shù)符號，指定一個函數(shù)。（3）對每一個n元謂詞符號，指定一個謂詞。顯然，對任意公式G，如果給定G的一個解釋I，則G在I的解釋下有一個真值，記作TI（G）。68第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.3謂詞邏輯公式的解釋例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；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；69第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.3謂詞邏輯公式的解釋解（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））

=（1∧1）∨（0∧1）

=1（2）TI（H）=TI（P（2）∧Q（2，2）∧P（3）∧Q（3，2））

=0∧1∧1∧0=070第二章謂詞邏輯2.2謂詞邏輯公式與解釋2.2.3謂詞邏輯公式的解釋定義2.5若存在解釋I，使得G在解釋I下取值為真，則稱公式G為可滿足的，簡稱I滿足G。定義2.6若不存在解釋I，使得I滿足G，則稱公式G為永假式（或矛盾式）。若G的所有解釋I都滿足G，則稱公式G為永真式（或重言式）。71第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式定義2.7設(shè)A、B是命題邏輯中的任意兩個公式，設(shè)它們有共同的個體域E，若對任意的解釋I都有TI（A）=TI（B），則稱公式A、B在E上是等價的，記作A

B。72第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式定理1設(shè)A（x）是謂詞公式，有關(guān)量詞否定的兩個等價公式：（1）﹁

xA（x）

x﹁A（x）（2）﹁

xA（x）

x﹁A（x）證明（1）設(shè)個體域是有限的為：D={a1，a2，…，an}，則有﹁

xA（x）

﹁（A（a1）∧A（a2）∧…∧A（an））

﹁A（a1）∨﹁A（a2）∨…∨﹁A（an））

x﹁A（x）的轉(zhuǎn)換73第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式定理1設(shè)A（x）是謂詞公式，有關(guān)量詞否定的兩個等價公式：（1）﹁

xA（x）

x﹁A（x）（2）﹁

xA（x）

x﹁A（x）證明（2）設(shè)個體域是有限的為：D={a1，a2，…，an}，則有

﹁

xA（x）

﹁（A（a1）∨A（a2）∨…∨A（an））

﹁A（a1）∧﹁A（a2）∧…∧﹁A（an）

x﹁A（x）74第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式定理2設(shè)A（x）是任意的含自由出現(xiàn)個體變項x的公式，B是不含x出現(xiàn)的公式，則有（1）

x（A（x）∨B）

xA（x）∨B（2）

x（A（x）∧B）

xA（x）∧B（3）

x（A（x）→B）

xA（x）→B（4）

x（B→A（x））

B→

xA（x）（5）

x（A（x）∨B）

xA（x）∨B（6）

x（A（x）∧B）

xA（x）∧B（7）

x（A（x）→B）

xA（x）→B（8）

x（B→A（x））

B→

xA（x）75第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式證明（1）設(shè)D是個體域，I為任意解釋，即用確定的命題及確定的個體代替出現(xiàn)在

x（A（x）∨B）和

xA（x）∨B中的命題變元和個體變元，于是得到兩個命題，若對

x（A（x）∨B）代替之后所得命題的真值為真，此時必有A（x）∨B的真值為真；因而A（x）真值為真或B的真值為真，若B的真值為真，則

xA（x）∨B的真值為真；若B的真值為假，則必有對D中任意x都使得A（x）的真值為真，所以

x（A（x）∨B）為真，從而

xA（x）∨B為真。76第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式證明若對

x（A（x）∨B）代替之后所得命題的真值為假，則A（x）和B的真值必為假，因此

xA（x）∨B的真值為假；所以

x（A（x）∨B）為假，有

xA（x）∨B為假。（2）、（5）和（6）證明與（1）類似，證明過程略。（3）

x（A（x）→B）

x（

A（x）∨B）

x

A（x）∨B

xA（x）∨B

xA（x）→B（4）、（7）、（8）證明與（3）類似，證明過程略。77第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式定理3設(shè)A（x）、B（x）是任意包含自由出現(xiàn)個體變元x的公式,則有：（1）

x（A（x）∧B（x））

xA（x）∧

xB（x）（2）

x（A（x）∨B（x））

xA（x）∨

xB（x）78第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式證明（1）設(shè)D是任一個體域，若

x（A（x）∧B（x））的真值為真，則對任意a

D，有A（a）和B（a）同時為真，即

xA（x）為真、

xB（x）為真，從而

xA（x）∧

xB（x）為真。若

x（A（x）∧B（x））的真值為假，則對任意a

D，有A（a）和B（a）不能同時為真，即

xA（x）和

xB（x）的真值不能同時為真，從而

xA（x）∧

xB（x）的真值為假。綜上所述

x（A（x）∧B（x））

xA（x）∧

xB（x）79第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式證明（2）設(shè)D是任一個體域，若

x（A（x）∨B（x））的真值為真,則存在a

D，使得A（a）∨B（a）為真，即A（a）為真或B（a）為真，即

xA（x）為真或

xB（x）為真，從而

xA（x）∨

xB（x）為真。若

x（A（x）∨B（x））的真值為假，則存在a

D，使得A（a）∨B（a）為假，此時，A（a）為假，B（a）為假，從而

xA（x）∨

xB（x）的真值為假。綜上所述

x（A（x）∨B（x））

xA（x）∨

xB（x）80第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式例2.11證明下列各等價式（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））81第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.1謂詞邏輯的等價公式例2.11證明下列各等價式（1）﹁

x（A（x）∧B（x））

x（A（x）→﹁B（x））（2）﹁

x（A（x）→B（x））

x（A（x）∧﹁B（x））證明（2）﹁

x（A（x）→B（x））

x﹁（A（x）→B（x））

x﹁（﹁A（x）∨B（x））

x（A（x）∧﹁B（x））82第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.2謂詞邏輯的蘊涵公式定義2.8設(shè)A、B是命題邏輯中的任意兩個公式，若A→B是永真式，則稱公式A蘊涵公式B，記作A

B。定理4下列蘊涵式成立（1）

xA（x）∨

xB（x）

x（A（x）∨B（x））（2）

x（A（x）∧B（x））

xA（x）∧

xB（x）（3）

x（A（x）→B（x））

xA（x）→

xB（x）（4）

x（A（x）→B（x））

xA（x）→

xB（x）（5）

xA（x）→

xB（x）

x（A（x）→B（x））83第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.2謂詞邏輯的蘊涵公式證明

（1）設(shè)

xA（x）

xB（x）在任意解釋下的真值為真，即對個體域中的每一個x。都能使A（x）的真值為真或者對個體域中的每一個x都能使B（x）的真值為真，無論哪種情況，對于個體域中的每一個x都能使A（x）∨B（x）的真值為真。因此，蘊涵式

xA（x）∨

xB（x）

x（A（x）∨B（x））成立。

（2）設(shè)個體域為D，在解釋I下

x（A（x）∧B（x））的真值為真，即存在a

D使得A（a）

B（a）為真，從而A（a）為真，B（a）為真，故有

xA（x）、

xB（x）均為真，所以，蘊涵式

x（A（x）∧B（x））

xA（x）∧

xB（x）成立。84第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.2謂詞邏輯的蘊涵公式（3）設(shè)個體域為D，在解釋I下

xA（x）→

xB（x）的真值為假,即存在a

D使得A（a）→B（a）為假，所以蘊涵式

x（A（x）→B（x））

xA（x）→

xB（x）成立。（4）

x（A（x）→B（x））→（

xA（x）→

xB（x））

﹁

x（A（x）→B（x））∨（

xA（x）→

xB（x））

﹁

x（A（x）→B（x））∨（﹁

xA（x）∨

xB（x））

﹁

x（A（x）→B（x））∨﹁

xA（x）∨

xB（x）

﹁（

x（A（x）→B（x））∧

xA（x））∨

xB（x）

（

x（A（x）→B（x））∧

xA（x））→

xB（x）85第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.2謂詞邏輯的蘊涵公式（5）

xA（x）→

xB（x）

xA（x）∨

xB（x）

x

A（x）∨

xB（x）

x（

A（x）∨B（x））

x（A（x）→B（x））86第二章謂詞邏輯2.3謂詞邏輯約束公式的等價與蘊涵2.3.3多個量詞的使用定義2.9設(shè)謂詞公式G，不包含聯(lián)結(jié)詞→，?。把G中出現(xiàn)的聯(lián)結(jié)詞

，

互換；命題常量T，F(xiàn)互換；量詞

，

互換之后得到的公式稱為G的對偶公式，記作G*。定理5（對偶定理）設(shè)A、B是任意兩個公式并且不包含聯(lián)結(jié)詞→，?。若A

B，則A*

B*。87第二章謂詞邏輯2.4前束范式定義2.10一個謂詞公式，如果量詞均在全式的開頭，且轄域延伸到公式的末尾，則該公式稱為前束范式。定理6對任意一個謂詞公式都可以化為與它等價的前束范式。證明首先利用等價公式將謂詞公式中的聯(lián)結(jié)詞→，?去掉。其次利用量詞的轉(zhuǎn)化律將量詞前面的否定深入到謂詞前面，在利用改名和代入規(guī)則以及量詞轄域擴張的公式將量詞移到全式的最前面，這樣便得到前束范式。88第二章謂詞邏輯2.4前束范式例2.12求下列謂詞公式的前束范式。（1）

x

y（

zA（x，z）∧A（x，z））→

tB（x，y，t）解（1）

x

y（

zA（x，z）∧A（x，z））→

tB（x，y，t）

﹁

x

y（

zA（x，z）∧A（x，z））∨

tB（x，y，t）

x

y（

z﹁A（x，z）∨﹁A（x，z））∨

tB（x，y，t）（量詞轉(zhuǎn)化）

x

y（

w﹁A（x，w）∨﹁A（x，z））∨

tB（u，v，t）（改名及代入規(guī)則）

x

y

w

t（﹁A（x，w）∨﹁A（x，z）∨B（u，v，t））（量詞轄域擴張）

89第二章謂詞邏輯2.4前束范式例2.12求下列謂詞公式的前束范式。（2）﹁

x（

yP（x，y）→

x

y（Q（x，y）∧

y（P（y，x）

→Q（x，y））））

解（2）﹁

x（

yP（x，y）→

x

y（Q（x，y）∧

y（P（y

，x）→Q（x，y））））

﹁

x（﹁

yP（x，y）∨

x

y（Q（x，y）∧

y（P（y，x）→Q（x，y））））

x（

yP（x，y）∧

x

y（﹁Q（x，y）∨

y（P（y，x）∧

﹁Q（x，y））））

（量詞轉(zhuǎn)化、德·摩根定律）

90第二章謂詞邏輯2.4前束范式例2.12求下列謂詞公式的前束范式。

x（

yP（x，y）∧

x

y（﹁Q（x，y）∨

z（P（z，x）∧

﹁Q（x，z））））（改名原則）

x（

yP（x，y）∧

x

y

z（﹁Q（x，y）∨（P（z，x）∧﹁Q（x，z））））（量詞轄域擴張）

x（

yP（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））））（量詞轄域擴張）

91第二章謂詞邏輯2.4前束范式定義2.11若一個謂詞公式，具有如下形式，則稱該公式為前束析取范式。定義2.12若一個謂詞公式，具有如下形式，則稱該公式為前束合取范式。定理7任意謂詞公式都可以化為與其等價的前束析取范式和前束合取范式。92第二章謂詞邏輯2.5謂詞演算的推理理論1．全稱指定規(guī)則（簡稱US規(guī)則）這條規(guī)有下面兩種形式：(1)

xP（x）

P（y）(2)

xP（x）

P（c）其中，P是謂詞，（1）中y為任意不在P（x）中約束出現(xiàn)的個體變元；（2）中c為個體域中的任意一個個體常元。93第二章謂詞邏輯2.5謂詞演算的推理理論2．存在指定規(guī)則（簡稱ES規(guī)則）

xP（x）

P（c）其中，c為個體域中使P成立的特定個體常元。必須注意，應用存在指定規(guī)則，其指定的個體c不是任意的。3．全稱推廣規(guī)則（簡稱UG規(guī)則）

P（y）

xP（x）4．存在推廣規(guī)則（簡稱EG規(guī)則）P（c）

xP（x）其中，c為個體域中的個體常元，這個規(guī)則比較明顯，對于某些個體c，若P（c）成立，則個體域中必有

xP（x）。94第二章謂詞邏輯2.5謂詞演算的推理理論例2.13證明

x（M（x）→D（x））∧M（s）

D（s）這是著名的蘇格拉底三段論的論證。其中M（x）：x是一個人。

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）I95第二章謂詞邏輯2.5謂詞演算的推理理論例2.14判斷下列的推理過程是否正確。（1）

x

yG（x，y）P

（2）

yG（z，y）US（1）（3）G（z，c）ES（2）（4）

xG（x，c）UG（3）（5）

y

xG（x，y）EG（4）96第二章謂詞邏輯2.5謂詞演算的推理理論解這個推理過程是錯誤的，因為從它可以得出結(jié)論：

x

yG（x，y）

y

xG（x，y）從前面的學習中我們知道這個式子不成立。它的推導錯誤出現(xiàn)在第（3）步。

x

yG（x，y）的含義是：對于任意的一個x，存在著與它對應的y，使得G（x，y）成立。但是，對

yG（z，y）利用ES規(guī)則消去存在變量后得到G（z，c）的含義卻是：對于任意個體z，有同一個體c，使得G（z，c）成立。顯然，G（z，c）不是

yG（z，y）的有效結(jié)論。因此，使用ES規(guī)則

xP（x）

P（c）消去存在量詞的條件是:P（x）中除x外沒有其他自由出現(xiàn)的個體變元。97第二章謂詞邏輯2.5謂詞演算的推理理論例2.15證明：

x（C（x）→（W（x）∧R（x）））∧

xC（x）∧Q（x）

xQ（x）∧

xQ（x）證明（1）

xC（x）P

（2）C（y）ES（1）（3）

x（C（x）→（W（x）

R（x）））P

（4）C（y）→（W（y）∧R（y））US（3）（5）W（y）∧R（y）T（2）（4）I

（6）R（y）T（5）I

（7）

xR（x）EG（6）（8）Q（x）P

（9）

xQ（x）EG（8）（10）

xQ（x）∧

xQ（x）T（7）（9）I98第二章謂詞邏輯2.5謂詞演算的推理理論例2.16證明：

x（A（x）∨B（x））

xA（x）∨

xB（x）證明方法1

（1）

x（A（x）∨B（x））P

（2）A（y）∨B（y）US（1）（3）

x（A（x）∨B（x））EG（2）（4）

xA（x）∨

xB（x）T（3）E99第二章謂詞邏輯2.5謂詞演算的推理理論例2.17給定前提：

x（P（x）∧

y（Q（y）→R（x，y）））

x（P（x）→

y（S（y）→﹁R（x，y）））證明下列結(jié)論：

x（Q（x）→﹁S（x））100第二章謂詞邏輯2.5謂詞演算的推理理論例2.17證明：（1）

x（P（x）∧

y（Q（y）→R（x，y）））P

（2）P（a）∧

y（Q（y）→R（a，y））ES（1）（3）P（a）T（2）（4）

x（P（x）→

y（S（y）→﹁R（x，y）））P

（5）P（a）→

y（S（y）→﹁R（a，y））US（4）（6）

y（S（y）→﹁R（a，y））T（3）（5）I101第二章謂詞邏輯2.5謂詞演算的推理理論例2.17證明：（7）

y（Q（y）→R（a，y））