上海電力學(xué)院離散數(shù)學(xué)教程1/932023/9/161

序言一、為何要學(xué)習(xí)離散數(shù)學(xué)?

2、離散數(shù)學(xué):是許多數(shù)學(xué)分支總稱.主要括： 數(shù)理邏輯,集合論,代數(shù)系統(tǒng),圖論.

1、專業(yè)需要:

2、對本身素質(zhì)訓(xùn)練

二、連續(xù)數(shù)學(xué)與離散數(shù)學(xué)

1、連續(xù)數(shù)學(xué):微積分,微分方程,復(fù)變函數(shù)等.

三.教學(xué)方法

1)引路2)預(yù)習(xí)3)作業(yè)4)章后總結(jié)2/932023/9/162序言四、參考書五、作業(yè)

1)《離散數(shù)學(xué)》耿素云等編著，高教出版社

2)《離散數(shù)學(xué)》何自強(qiáng)等編著，科學(xué)出版社怎樣使用參考書？

每章每節(jié)后看參考書，然后總結(jié)，壓縮即：薄厚薄3/932023/9/163序言離散數(shù)學(xué)是當(dāng)代數(shù)學(xué)一個主要分支，是學(xué)習(xí)計算機(jī)科學(xué)與術(shù)主要第一篇集合論（集合基本概念、關(guān)系、無限集）第二篇代數(shù)結(jié)構(gòu)（代數(shù)系統(tǒng)、群、環(huán)、域、格）第三篇圖論（圖基本概念以及不一樣類型圖）第四篇數(shù)理邏輯（命題邏輯和謂詞邏輯）基礎(chǔ)課之一。本課程以集合論、代數(shù)結(jié)構(gòu)、數(shù)理邏輯、圖論四大部分為主干教學(xué)內(nèi)容,并輔以組合論、數(shù)論基礎(chǔ)、形式語言與自動機(jī)初步等內(nèi)容。本教案選取課程主干內(nèi)容進(jìn)行組織,包含：4/932023/9/164第1章命題邏輯數(shù)理邏輯是計算機(jī)科學(xué)基礎(chǔ)理論之一?？煞譃槲宕蟛糠郑旱谝黄獢?shù)理邏輯第一章命題邏輯邏輯演算、集合論、證實(shí)論、模型論、遞歸論。數(shù)理邏輯既是數(shù)學(xué)又是邏輯學(xué)：它研究數(shù)學(xué)中邏輯問題，用數(shù)學(xué)方法研究形式邏輯。計算機(jī)硬件，軟件，算法及語言都含有數(shù)理邏輯性質(zhì)。我們在此僅講授數(shù)理邏輯基礎(chǔ)部分——邏輯演算部分。它包括命題演算和（一階）謂詞演算兩部分。5/932023/9/165第1章命題邏輯第一篇數(shù)理邏輯第一章命題邏輯1.2聯(lián)結(jié)詞1.3命題公式與翻譯1.4~1.5

命題邏輯等值演算1.6其它聯(lián)結(jié)詞及聯(lián)結(jié)詞完備集1.1 命題及表示法1.7對偶與析取范式和合取范式(范式)1.8命題邏輯推理理論6/932023/9/166第2章謂詞邏輯2.1謂詞概念與表示第一篇數(shù)理邏輯第二章謂詞邏輯2.2命題函數(shù)與量詞2.3~2.4一階謂詞公式2.5一階謂詞演算等價式與蘊(yùn)含式2.6一階謂詞前束范式2.7一階邏輯推理理論7/932023/9/1671.1命題及表示法命題邏輯研究中心問題是推理，即研究推理中前題和結(jié)論之

第一篇數(shù)理邏輯第一章命題邏輯定義1：命題是能判斷真假陳說句。定義2：真值是陳說句為真或假這種性質(zhì)。

間形式關(guān)系，而不包括前題和結(jié)論詳細(xì)內(nèi)容。推理基本單

位為命題。

注1：上命題必須是陳說句。而疑問句、祈使句和感嘆句等不是命題。

注2：命題真值是唯一，但與我們是否知道它真值無關(guān)。假命題：凡與事實(shí)不相符命題，其真值為假。符號化：用“0”或“F”表示。真命題：凡與事實(shí)相符命題，其真值為真。符號化：用“1”或“T”表示。8/932023/9/1681.1命題及表示法（1）三角形三個內(nèi)角和為180度。

第一篇數(shù)理邏輯第一章命題邏輯（2）4為素數(shù)。

例：判斷以下語句是否為命題

（3）1+101=110

（4）你喜歡離散數(shù)學(xué)嗎？（5）這朵花真美啊?。?）x>y（7）我正在說謊。9/932023/9/1691.1命題及表示第一篇數(shù)理邏輯第一章命題邏輯例：(1)P：“雪是黑”命題符號化：普通用大寫字母A，B，…，P，Q，…或帶下標(biāo)大命題常元與命題變元寫字母或數(shù)字表示。

(2)Q2：“上海是個漂亮城市”

(3)：“X+2>8”命題常元：表示詳細(xì)確定內(nèi)容命題。命題變元：表示任意，沒有賦予詳細(xì)內(nèi)容抽象命題。注1：命題變元與命題常元區(qū)分注2：命題變元與命題常元在邏輯演算中處理標(biāo)準(zhǔn)相同。10/932023/9/16101.2命題聯(lián)結(jié)詞第一篇數(shù)理邏輯第一章命題邏輯若干個簡單命題經(jīng)過命題聯(lián)結(jié)詞而組成新命題。

定義：簡單命題（原子命題）不能再分解為更簡單命題。

1、否定詞“”注：“”為一元運(yùn)算，否定全部而非部分。2、合取詞“”

定義：復(fù)合命題定義：設(shè)P為一個命題，利用“”與P組成復(fù)合命題稱為P否命題，記為“P”。讀作“非P”，其真值表見表1-1定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”

成復(fù)合命題，記為“PQ”。讀作“P且Q”

11/932023/9/16111.2命題聯(lián)結(jié)詞第一篇數(shù)理邏輯第一章命題邏輯PQ：例1：P：“李軍聰明”，Q：“李軍用功”注：內(nèi)容上無聯(lián)絡(luò)兩個命題也能夠組成含有確定真值命題。 3：析取詞“”定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”組成例1：P：“開關(guān)壞了”，Q：“燈炮壞了”：PQ：注：“”表示可兼或。不可兼或不能用“”表示。PQ：“李軍聰明且用功”復(fù)合命題，記為“PQ”。讀作“P或Q”

例2：P：“1+11=100”，Q：“熊貓為稀有動物”12/932023/9/16121.2命題聯(lián)結(jié)詞

第一篇數(shù)理邏輯第一章命題邏輯4、條件“”例2：小李下午去打藍(lán)球或在宿舍玩電腦。

定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”組成復(fù)合命例1：有位父親對兒子說：“假如我去書店，我一給你買光盤。”解：P：父親去書店，Q：給兒子買光盤題，記為“PQ”。讀作“假如P，則Q”，其中P為前件，Q為后件。只有當(dāng)前件為真，后件為假時，PQ為假。試問：在何種情況下，這位父親算失信？1)P=1，Q=13)P=0，Q=12)P=1，Q=04)P=0，Q=0注：善意推論。13/932023/9/16131.2命題聯(lián)結(jié)詞第一篇數(shù)理邏輯第一章命題邏輯5、等價詞（雙條件）“”例2：雪是黑，僅當(dāng)太陽從西方出來。等價于定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”組成復(fù)合命例：將以下命題符號化，并討論它們真值1)if：3+3=6，則雪是白。假如雪是黑，則太陽從西方出來。題，稱為等價復(fù)合命題記為“PQ”。讀作“P當(dāng)且僅當(dāng)Q”，當(dāng)且僅P和Q真值相同時，PQ為真。不然為假。2)if：3+3不等于6，則雪是白。3)if：3+3=6，則雪不是白。4)if：3+3不等于6，則雪不是白。5)3為有理數(shù)當(dāng)且僅當(dāng)美國在亞洲。14/932023/9/16141.2命題聯(lián)結(jié)詞第一篇數(shù)理邏輯第一章命題邏輯解：P：3+3=6，Q：雪是白

1)邏輯詞優(yōu)先級別分別為：，，，，二、語句形式化1)P

Q，真值為1(P(1)Q(1))2)

P

Q，真值為1(

P(0)Q(1))3)P

Q，真值為0(P(1)

Q(0))5)P

Q，真值為0(P(1)Q(0))4)

P

Q，真值為1(

P(1)

Q(1))

P：3為有理數(shù)，Q：美國在亞洲推理問題：自然語言描述邏輯語言邏輯演算規(guī)律推理運(yùn)算在命題形式化時，若命題包含多個聯(lián)結(jié)詞時，應(yīng)注意聯(lián)結(jié)詞運(yùn)算規(guī)律。括號中運(yùn)算為最優(yōu)先級。15/932023/9/16151.2命題聯(lián)結(jié)詞第一篇數(shù)理邏輯第一章命題邏輯2)同級聯(lián)結(jié)詞，按從左到右次序運(yùn)算。

例2：假如你和他不都是傻子，那么你們不會去自討沒趣。

例1：狗急跳墻例3：假如你走路看書，那么你一定會成為近視眼。

例4：假如明天天氣好，我們?nèi)ソ加?；不然不去郊游?6/932023/9/16161.3命題公式及其賦值第一篇數(shù)理邏輯第一章命題邏輯一、命題公式(合式公式)：由命題常元、命題變元、命題聯(lián)結(jié)詞及定義：命題公式遞歸定義（簡稱公式）是否任何字符串都是命題呢？AB，A，B(RP)，P(R)，(P(R）定義：設(shè)A為含有命題變元P1，P2，…，Pn命題公式，給P1，圓括號等組成字符串。1)單個命題變元為命題公式。2)if：P，Q為命題公式，則

P，PQ，PQ，PQ，PQ也為命題公式。3)僅有有限次地利用上述1)、2)產(chǎn)生字符串才是命題公式。例：PQ(QR)，(PQ)R(QR)Q)P2，…，Pn一組確定真值，稱為對A一個賦值或解釋或真值指派。17/932023/9/16171.3命題公式及其賦值

第一篇數(shù)理邏輯第一章命題邏輯成真賦值：若指定一組值使A真值為1，則這組值為成真賦值。要求：

1)若A中出現(xiàn)命題變項為P1，P2，…，Pn，給定A賦值為

1，

成假賦值：若指定一組值使A真值為0，則這組值為成假賦值。

2)若A中出現(xiàn)命題變項為P，Q，R，…，給定A賦值為

1，

2，…，二、定義：真值表2，…，

n，則指P1=

1，P2=

2，…，Pn=

n

n，則指P=

1，Q=

2，…，最終字母賦值

n。上述

i，取值為0或1。將命題公式A在全部賦值情況列表，稱為A真值表。18/932023/9/16181.3命題公式及其賦值

第一篇數(shù)理邏輯第一章命題邏輯命題公式真值表結(jié)構(gòu)步驟以下：2)按從低到高次序?qū)懗龉礁鱾€層次。1)找出命題公式中全部命題變元，按下標(biāo)或字母次序排列，按二3)計算各個層次真值，直到最終計算出公式真值。注：兩個公式有相同真值表或不一樣真值表是指真值表最終例：求以下公式真值表，并求成真賦值和成假賦值。1)(PP)(QQ)三、命題公式類型進(jìn)制依次寫出賦值。一列是否相同。2)(QP)R19/932023/9/16191.3命題公式及其賦值第一篇數(shù)理邏輯第一章命題邏輯定義：重言式或永真式定義：矛盾式或永假式定義：可滿足式1)、3)同，2)、4)同。例：以下各公式中均含有兩個變元P，Q，它們中哪些有相同真值表？1)PQ，2)PQ，3)(PQ)

4)(PQ)(QP)，5)PQ一個命題公式，假如對它含命題變元任一組賦值，取值恒為真。一個命題公式，假如對它含命題變元一組賦值，取值恒為假。一個命題公式，假如對它含命題變元最少有一組賦值，取值為真。20/932023/9/16201.4~1.5

命題邏輯等值演算第一篇數(shù)理邏輯第一章命題邏輯一、等值式(等價公式)定義：命題公式等價關(guān)系注1：A與B為等價公式可定義為AB為重言式。例2：判斷以下公式是否等價？注2：AB不表示公式（命題），僅代表A與B之間邏輯等價公式。例1：證實(shí)設(shè)A與B為兩個命題公式，若A與B有相同真值表時稱公式A與B為等價公式。記為：ABAB表示命題公式（命題）。

(PQ)(QP)

(QP)PQ1)P(QR)與(PQ)R2)(PQ)R與(PQ)R21/932023/9/16211.4~1.5命題邏輯等值演算第一篇數(shù)理邏輯第一章命題邏輯“”公式之間等價關(guān)系滿足：2)冪等律：AAA，AAA等價式基本定律：1)雙重否定定律：A

A3)交換律：A

BBA，A

BBA4)結(jié)合律：

(A

B)CA(BC) (A

B)CA(BC)5)分配律：

A(BC)(AB)(AC)

A(BC)(AB)(AC)

1)自反性：A，AA2)對稱性：A，B，if：AB，則BA3)可傳遞性：

A，B，R，if：AB，BR，則：AR22/932023/9/16221.4~1.5命題邏輯等值演算

第一篇數(shù)理邏輯第一章命題邏輯8)零律：A

11，A006)德摩根律：

(A

B)BA

(A

B)BA7)吸收律：

A(AB)A

A(AB)A

9)同一律：A

0A，A1A

10)排中律：AA1

11)矛盾律：AA012)條件等價式：ABAB13)雙等價等值式：

(AB)(AB)(BA)23/932023/9/16231.4~1.5命題邏輯等值演算

第一篇數(shù)理邏輯第一章命題邏輯定義:等值演算16)歸謬論:(AB)(AB)A14)假言易位：ABBA15)等價否定等價式：ABAB二、等值演算置換規(guī)律則設(shè)F(A)為包含公式A命題公式，F(xiàn)(B)是用公式B置換了F(A)中所由一些等值式推算另一些等值式過程。有A后得到命題公式，若BA，則F(B)F(A)24/932023/9/16241.4~1.5命題邏輯等值演算

第一篇數(shù)理邏輯第一章命題邏輯1)解：(PQ)R(PQ)R例2：用等值演算證實(shí)等值式例1：(PQ)R(PQ)R

1)(PQ)R(PR)(QR)2)(PQ)(PQ)(QP)例3：用等值演算判斷以下公式類型 (PQ)R(PQ)R(RP)(RQ) (PQ)R(PR)(QR) (PR)(QR)3)P(PQ)PQ25/932023/9/16251.4~1.5命題邏輯等值演算第一篇數(shù)理邏輯第一章命題邏輯三、蘊(yùn)含式2)解：(P(PQ))R(P(PQ))R 1)(PQ)(PQ)定義：當(dāng)且僅當(dāng)PQ是一個重言式時，我們稱“P蘊(yùn)含Q”，并記作PQ。對于PQ來說，除P真值取T，Q真值取F這么一個指派時，PQ2)(P(PQ))R(PPQ)R(TQ)RTRF 證實(shí)P

Q，即是證實(shí)PQ是重言式。真值為F外，其余情況，PQ真值為T。故要證P

Q，只需對條件命題PQ前件P，指定真值為T，若由此推出Q真值亦為T，則PQ是重言式，即P

Q成立；同理，如對條件命題PQ中，假定后件Q真值取F，若由此推出P真值亦為F，即推證了QP故P

Q成立。26/932023/9/16261.4~1.5命題邏輯等值演算第一篇數(shù)理邏輯第一章命題邏輯例：推證

Q(PQ)P對PQ來說，QP稱作它逆換式；PQ稱作它反換式；定義：逆換式、反換式、逆反式證法1：證法2：

假定P為F，則P為T。

QP稱作它逆反式。假定Q(PQ)為T，則Q為T。且(PQ)為T。由Q為F，PQ為T，則必須P為F，故P為T。(a)：若Q為F，則PQ為F，Q(PQ)為F。(b)：若Q為T，則Q為F，Q(PQ)為F。所以Q(PQ)P成立。慣用蘊(yùn)含式如表1-5.2。27/932023/9/16271.6其它聯(lián)結(jié)詞及聯(lián)結(jié)詞完備集

第一篇數(shù)理邏輯第一章命題邏輯1：不可兼析取“”一、其它聯(lián)結(jié)詞2：條件否定“”二、聯(lián)結(jié)詞完備集（最小聯(lián)結(jié)詞組）合命題，記為PQ。當(dāng)且僅當(dāng)P和Q有不一樣真值時，P不可定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”組成復(fù)析取Q為1；不然為零。其真值表見表定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”組成復(fù)合命題，記為PQ。當(dāng)且僅當(dāng)P為真，Q為假時，其真值為1。28/932023/9/16281.6其它聯(lián)結(jié)詞及聯(lián)結(jié)詞完備集

第一篇數(shù)理邏輯第一章命題邏輯定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”組成3：與非“”4：或非“”題，記為PQ。當(dāng)且僅當(dāng)P與Q同時為假時,PQ為1；不然為0。定義：n元真值函數(shù)復(fù)合命題，記為“PQ”。當(dāng)且僅當(dāng)P與Q同時為真時,pq為零,不然為1。其真值表見表1-6.3(左圖定義：設(shè)P和Q為兩個命題，由P與Q用二元聯(lián)結(jié)詞“”組成復(fù)合命真值表見表1-6.4(右圖)。稱F：{0，1}n{0，1}為n元真值函數(shù)。F：自變量為n個命題變元{0，1}組成長度為n符號串。值域：{0，1}29/932023/9/16291.6其它聯(lián)結(jié)詞及聯(lián)結(jié)詞完備集

第一篇數(shù)理邏輯第一章命題邏輯n=1時，1元真值函數(shù)為22個n個命題變元共組成22n次冪個不一樣真值函數(shù)。定義：（聯(lián)結(jié)詞完備集）設(shè)S是一個聯(lián)結(jié)詞完備集合，假如任何n(n1)元真值函數(shù)都能夠僅定理：S={，，}是聯(lián)結(jié)詞完備集。推論：以下聯(lián)結(jié)詞集都是完備集n=2時，1元真值函數(shù)為24個由S中聯(lián)結(jié)詞組成公式表示。30/932023/9/16301.6其它聯(lián)結(jié)詞及聯(lián)結(jié)詞完備集

第一篇數(shù)理邏輯第一章命題邏輯1）S1={，，，}4）S4={，}5）S5={，}6）S6={}2）S2={，，，，}3）S3={，}7）S7={}例1：僅用，表示（pq）p。例2：用表示p。定理：S={，}或S={，}是最小聯(lián)結(jié)詞完備集。31/932023/9/16311.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯在給定命題公式中，將聯(lián)結(jié)詞“”換成“”，將聯(lián)結(jié)詞“”換成注：A也為A*對偶式。例：寫出以下各式對偶式一、對偶式定義：A對偶式定理：設(shè)A與A*是對偶式,P1,P2，…,Pn是出現(xiàn)在A與A*中原子A(P1,P2,…,Pn)

A*(P1,P2,…,Pn)定理：設(shè)P1,P2,…,Pn是出現(xiàn)在A與B中原子變元，假如AB，則A*

B*?！啊?，若有特殊元“0”或“1”亦相互取代，所得公式A*稱為A對偶式。(PQ)R，(PQ)1，PQ，PQ則:A(P1,P2,…,Pn)

A*(P1,P2,…,Pn)32/932023/9/16321.7對偶與析取范式和合取范式(范式)

第一篇數(shù)理邏輯第一章命題邏輯簡單析取式：僅由有限個文字組成析取式。簡單合取式：僅由有限個文字組成合取式。二、析取范式和合取范式定義：例：P，PQ，PQQ為簡單析取式注：單個文字既可為簡單析取式又為簡單合取式。定理：文字：命題變元或命題變元否定。P，PQ，PQQ為簡單合取式1）一個簡單析取式為重言式充要條件是它同時含有命題變元和命題變元否定。33/932023/9/16331.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯析取范式：由有限個簡單合取式組成析取式。合取范式：由有限個簡單析取式組成合取式。

2）一個簡單合取式為矛盾式充要條件是它同時含有命題變元和定義：注1：析取范式與合取范式僅含有，，注2：單個文字，簡單析取范式與簡單合取范式既為析取范式又是合取范式。定理：2)一個合取范式為重言式充要條件是它每個簡單析取式都是重言式。命題變元否定。1)一個析取范式為矛盾式充要條件是它每個簡單合取式都是矛盾式。

34/932023/9/16341.7對偶與析取范式和合取范式(范式)

第一篇數(shù)理邏輯第一章命題邏輯求給定公式范式步驟：1)消去聯(lián)結(jié)詞“”，“”定理（范式存在定理）對任意公式A，都存在等價于它析取范式和合取范式。PQPQ(PQ)(PQ)(PQ)(求合取范式)2)消去否定號“”3)利用分配律和結(jié)合律例1：求公式(PQ)R合取范式(PQ)(PQ)(PQ)(求析取范式)解：(PQ)R(PQ)R35/932023/9/16351.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯3)全體小項析取式為永真。三命題變元P，Q和R，其極小項為：普通n個命題變元有2n個極小項。一個極小項對一組賦值使其真值m7=PQR，m6=PQR，m5=PQR，m4=PQR,m3=PQR,極小項有以下性質(zhì)：1)每個小項當(dāng)其真值指派與編碼相同時，其真值為1，其余指派為0。2)任意兩個不一樣小項合取式為永假。定義：布爾析取或極大項n個變元析取式，稱作布爾析取或極大項，其中每個變元為1，此時所對應(yīng)二進(jìn)制數(shù)為i，引入記號mi表示。m2=PQR,

m1=PQR，m0=PQR它否定不能同時存在，但二者必須出現(xiàn)且僅出現(xiàn)一次。36/932023/9/16361.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯1)每個大項當(dāng)其真值指派與編碼相同時，其真值為0，其余指派為1。例：兩命題變元P和Q，其極大項為：三命題變元P，Q和R，其極大項為：普通說，n個命題變元共有2n個極大項。一個極大項對一組賦值使極大項有以下性質(zhì)：2)任意兩個不一樣大項析取式為永真。3)全體大項合取式為永假。M0=PQ,M1=PQ,M2=PQ,M3=PQM0=PQR，M1=PQR，M2=PQR，M4=PQR,M3=PQR,M6=PQR,M5=PQR，M7=PQR其真值為0，此時所對應(yīng)二進(jìn)制數(shù)為i，引入記號Mi表示。37/932023/9/16371.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯定理：在真值表中，一個公式真值為0指派所對應(yīng)大項合定義：主析取范式、主合取范式對于一個給定命題公式，假如有一個等價公式，它僅由小項組對于一個給定命題公式，假如有一個等價公式，它僅由大項組定理：在真值表中，一個公式真值為1指派所對應(yīng)小項求主范式方法：方法1：已知公式真值表求。例：求PQ，PQ，

PQ主析取范式和主合取范式。成析取范式，則該等價公式稱為原式主析取范式。成合取范式，則該等價公式稱為原式主合取范式。析取，即為此公式主析取范式。取，即為此公式主合取范式。38/932023/9/16381.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯求主析取范式步驟：P

Q主析取范式為：m3m1m0(4)對合取項補(bǔ)入沒有出現(xiàn)命題變元，即添加(

PP)，再用分配律展開。方法2：用求范式方法來求(1)化歸為析取范式。(2)除去析取范式中全部永假析取項。(3)將析取式中重復(fù)出現(xiàn)合取項和相同變元合并。P

Q主合取范式為：M2P

Q主析取范式為：m3m2m1

P

Q主合取范式為：M0PQ主析取范式為：m1PQ主合取范式為：M3

M2

M039/932023/9/16391.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯求主合取范式步驟：例：求以下公式主析取范式(4)對合取項補(bǔ)入沒有出現(xiàn)命題變元,即添加(

PP),再用分配律展開.1)(PQ)

(PR)(QR)(1)化歸為合取范式

(2)除去合取范式中全部永真合取項。(3)將合取式中重復(fù)出現(xiàn)析取項和相同變元合并。例：求(PQ)R主合取范式.

2)P((PQ)(QP))40/932023/9/16401.7對偶與析取范式和合取范式(范式)第一篇數(shù)理邏輯第一章命題邏輯A：有三個變元，if：Am1m2m3， 則方法3：由主析取范式求主合取范式A：有兩個變元，if：Am1m2， 則AM0M3AM0M4M5M6M741/932023/9/16411.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯一、推理形式結(jié)構(gòu)推理是由已知命題得到新命題思維過程。前題：已知命題定義：設(shè)A1,A2,…,An，B都是命題公式，假如A1

A2

…

AnB注：由前提推出結(jié)論是否正確與諸前題排列次序無關(guān)。判斷一個推理是否正確方法有四種：(1)真值演出算(2)直接證實(shí)(3)間接證實(shí)推理=前提+結(jié)論結(jié)論：新命題為重言式，則稱從前提A1,A2,…,An推出B。A1

A2

…

An

B，稱{A1,A2,…,An}為前提集合。42/932023/9/16421.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯1)真值演出算判斷A1

A2

…

AnB是否為重言式。if：B亦有真值1，則推理正確。Or看真值為0行，if：在每2)直接演算法判斷以下推理是否正確？例1：若a能被4整除，則a能被2整除。a能被4整除，故a能被2整除。在真值表中找出全部A1,A2,…,An真值為行，對這么行，一個這么行中，A1,A2,…,An為真值中最少有一個為0，則推理正確?？磿鴓41例143/932023/9/16431.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯解：P：a能被4整除，Q：a能被2整除判斷A1

A2

…

AnB是否為重言式。前提：PQ，P， 結(jié)論：Q推理形式：(PQ)PQ例2：下午馬芳或者去看電影，或去游泳。她沒去看電影，所以她去游泳了。解：P：馬芳去看電影，Q：馬芳去游泳前提：PQ，P結(jié)論：Q推理形式：(PQ)PQ44/932023/9/16441.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯例3：若下午溫度超出30度，則王小燕必去游泳；若她去游泳，她解：P：下午溫度超出30度Q：王小燕必去游泳，R：王小燕去看電影前提：PQ，QR定義：自然推理系統(tǒng)由三部份組成1)字母表 2)合式公式 3)推理規(guī)則其中字母表為：a)命題變元符號：P,Q,R,…不去看電影。所以若王小燕去看電影，下午氣溫必不超出30度。結(jié)論：RP45/932023/9/16451.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯b)聯(lián)結(jié)詞符號:,,,,c)括號與逗號:(),推理規(guī)則:1o：前提引入規(guī)則2o：結(jié)論引入規(guī)則3o：置換規(guī)則4o：假言推理規(guī)則：AB,AB5o：化簡規(guī)則：ABB6o：附加規(guī)則：AAB7o：拒取式規(guī)則：AB,BA9o：析取三段論規(guī)則：AB,BA8o：假言三段論規(guī)則：AB,BCAC10o：結(jié)構(gòu)性二難規(guī)則：AB,CD,ACBD46/932023/9/16461.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯在自然推理系統(tǒng)中結(jié)構(gòu)以下推理證實(shí)例4： 前提：PQ，QR，PS，

S

結(jié)論：R(PQ)證實(shí)

P

S

前提引入

S前提引入

P拒取式

PQ前提引入

Q析取三段論

QR前提引入

R假言推理規(guī)則

R(PQ)

47/932023/9/16471.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯例5：前提：PQ，PR，QS

結(jié)論：SR證實(shí)

PR

前提引入

PQRQ附加規(guī)則

QS

前提引入

RQRS附加規(guī)則

PQRS假言三段論

PQ前提引入

RS

48/932023/9/16481.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯二、運(yùn)算和推理1、A蘊(yùn)含B證實(shí)A

B為重言式，可用前件或后件方法2、A、B兩公式等價(1)比較真值表；(2)A

B為重言式4、推理3、求主析(合)取范式(1)真值表；(2)步驟法；(3)交換法(1)真值表；(2)直接法；(3)間接法49/932023/9/16491.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯PC規(guī)則：if:證實(shí)A1,A2,…,An

B

C，可引入附加前提B，去推出C。例：證實(shí)A(BC)，DA，B

D

C證實(shí)

D附加前提引入

DA前提引入

A析取三段論

B前提引入

A(BC)前提引入

BC假言推理

C假言推理

D

C則推理正確。50/932023/9/16501.8命題邏輯推理理論

第一篇數(shù)理邏輯第一章命題邏輯3)間接證實(shí)(歸謬法)A1,A2,…,An

B，若

B可推出矛盾，如AA則說明推理正確。例1：PQ，

(PQ)P

證實(shí)

PQ前提引入

Q假言推理規(guī)則

P附加前提

(PQ)前提引入

PQ徳摩根律

Q

QQ(矛盾)

不然錯誤。51/932023/9/16511.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯例2：證實(shí)CB，ABAC證實(shí)

(AC) 附加前提引入

A I7

C I8

AB 前提引入

CB

前提引入

B 析取三段論

B

假言推理

BB

矛盾例3：設(shè)有以下情況，結(jié)論是否有效？

52/932023/9/16521.8命題邏輯推理理論

第一篇數(shù)理邏輯第一章命題邏輯(1）或者天晴，或者下雨。（2）假如是晴天，我去看電影。（3）假如我去看電影，我就不看書。結(jié)論：假如我在看書則天在下雨。

53/932023/9/16531.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯第一章：小結(jié)

一、基本概念和術(shù)語

命題，原子命題，復(fù)合命題，命題常元，命題變元，公合式公式否定詞、析取詞、合取詞、條件詞，雙條件，優(yōu)先次序 對偶式，簡單析取式，簡單合取式，析取范式，合取范式，真值表，重言式，矛盾式，可滿足式，蘊(yùn)含式，等價式，逆反式小項，大項，主析取范式，主合取范式54/932023/9/16541.8命題邏輯推理理論第一篇數(shù)理邏輯第一章命題邏輯二、運(yùn)算和推理1、A蘊(yùn)含B證實(shí)A

B為重言式，可用前件或后件方法2、A、B兩公式等價(1)比較真值表；(2)A

B為重言式3、求主析(合)取范式(1)真值表；(2)步驟法；(3)交換法4、推理

(1)真值表；(2)直接法；(3)間接法55/932023/9/16552.1謂詞概念與表示第一篇數(shù)理邏輯第二章謂詞邏輯在命題演算中，把簡單命題作為基本研究單位而不在進(jìn)行分解，例1： 全部些人總是要死。P：全部些人總是要死PQR顯然此不是命題邏輯重言式。這使得命題邏輯有很大不足。有些很簡單推理形式，如典型邏輯三段論，用命題演算推理理論無法論證。蘇格拉底是人。所以蘇格拉底是要死。Q：蘇格拉底是人R：蘇格拉底是要死56/932023/9/16562.1謂詞概念與表示第一篇數(shù)理邏輯第二章謂詞邏輯造成上述原因在于我們沒有對簡單命題本身內(nèi)部特征作進(jìn)一例2： 熊貓是動物。P：熊貓是動物P和Q不能揭示這兩個命題共性對簡單命題成份、結(jié)構(gòu)和簡單命題間共性等作深入步分析，無法揭示前提和結(jié)論在形式結(jié)構(gòu)方面聯(lián)絡(luò)，所以不能認(rèn)識到這種推理形式和規(guī)律。 狗是動物。Q：狗是動物分析，這正是一階邏輯所要研究問題。一階邏輯又稱一謂詞邏輯或謂詞邏輯。57/932023/9/16572.1謂詞概念與表示第一篇數(shù)理邏輯第二章謂詞邏輯一、個體詞和個體域定義：個體常元：表示詳細(xì)、特指個體詞。慣用小寫字a，b，c等表示。個體變元：表示抽象、泛指或一定范圍個體詞。慣用小寫字個體域：個體變元取值范圍。慣用D表示。注1：個體域能夠是有限或無限。個體：能夠獨(dú)立存在事物。母x，y，z等表示。注2：全總個體域：最大個體域包含整個宇宙全體事物。注3：假如無尤其申明個體域均為全總個體域。58/932023/9/16582.1謂詞概念與表示

第一篇數(shù)理邏輯第二章謂詞邏輯普通句子是有主語和謂語兩部份組成。個體通常是主語，能夠是抽象或詳細(xì)。如：小張，小王，熊貓，計算機(jī)等。謂詞：用來刻劃一個個體性質(zhì)或多個個體之間關(guān)系詞。元數(shù)：謂詞中包含個體數(shù)目。謂詞常元：表示有詳細(xì)意義性質(zhì)或關(guān)系謂詞。謂詞變元：表示有抽象或泛指性質(zhì)或關(guān)系謂詞。從數(shù)學(xué)角度來講：謂詞是一個以D為定義域，以{0，1}為值域函數(shù)。0元謂詞：將不帶個體變元謂詞。59/932023/9/16592.1謂詞概念與表示

第一篇數(shù)理邏輯第二章謂詞邏輯一元謂詞：表示一個個體性質(zhì)。二元謂詞：表示兩個個體之間關(guān)系。n元謂詞：表示n個個體之間關(guān)系。用謂詞表示式寫出以下命題元數(shù)：謂詞中包含個體數(shù)目。例1：只有2為素數(shù)，4才是素數(shù)。解：一元謂詞F(x):x為素數(shù)

a=2，b=4F(a)F(b)例2：假如5大于4，則4大于6解：二元謂詞G(x,y)：x>y60/932023/9/16602.2命題函數(shù)與量詞

第一篇數(shù)理邏輯第二章謂詞邏輯定義：簡單命題函數(shù)：由一個謂詞，一些個體變元組成表示式。復(fù)合命題函數(shù)：由一個或n個簡單命題函數(shù)以及邏輯聯(lián)結(jié)詞組成表示式。僅在命題中分析出個體或謂詞后，還不足以表示邏輯三段論和日定義:量詞：表示數(shù)量詞。分為全稱量詞和存在量詞。

全稱量詞：表示“全部”，“任意”，“每一個”，“凡”等詞。記為：

xA(x)or(x)A(x)：表示個體域中全部個體都有性質(zhì)A。存在量詞：表示“存在著”，“有一些”，“最少存在一個”等詞。記常生活中各種問題。因為還缺乏表示個體常元與變元之間數(shù)量關(guān)系?！啊?，x表示個體域中全部個體，x稱為全稱變元。為：“”，x表示存在個體域中個體，x為存在性變元。61/932023/9/16612.2命題函數(shù)與量詞

第一篇數(shù)理邏輯第二章謂詞邏輯

xA(x)or(x)A(x)：表示存在個體域中某個體都含有性質(zhì)A。量詞也稱為對個體所附加約束詞。例1：設(shè)F(x)：表示x會飛，D為鳥集合例2：設(shè)G(x)：x為白，D：為菊花集合注：帶有量詞命題函數(shù)必須確定其個體域；不然無法準(zhǔn)確表示命題含義。

xA(x)or(x)A(x)：表示個體域中全部個體都有性質(zhì)A。定義：特定謂詞

xF(x)：

xF(x)：

xG(x)：

xG(x)：

If：全部命題函數(shù)個體域為全總個體域，對每個個體性質(zhì)要特別指明。為了討論個體域中某部分個體性質(zhì)，引入刻劃這部分個體謂詞。62/932023/9/16622.2命題函數(shù)與量詞

第一篇數(shù)理邏輯第二章謂詞邏輯普通對全稱量詞，此特征謂詞常作蘊(yùn)涵前件。如

xA(x)可寫成

x(M(x)

A(x))，M(x)為A(x)特征謂詞。普通對存在量詞，此特征謂詞常作合取項。如

xH(x)可寫成

x(M(x)

H(x))，M(x)限制H(x)改變。三、一階邏輯命題中符號化問題1、一元謂詞符號化例1：凡人都有呼吸。解：F(x)：x為人，H(x)：x呼吸

x(F(x)

H(x))例2：有些人用左手寫字。63/932023/9/16632.2命題函數(shù)與量詞

第一篇數(shù)理邏輯第二章謂詞邏輯解：F(x)：x為人，G(x)：x用左手寫字

x(F(x)

G(x))例3：小李是大學(xué)生和運(yùn)動員。解：L(x)：x是大學(xué)生，P(x)：x是運(yùn)動員

a：小李L(a)

P(a)注：在命題符號化時，假如沒有尤其指明個體域，則采取全總體域。將以下命題符號化，并指明其真值。例1：全部些人都長黑頭發(fā)。解：M(x)：x為人，F(xiàn)(x)：x長黑頭發(fā)例2：每個學(xué)生都要參加考試。

x(M(x)

F(x))64/932023/9/16642.2命題函數(shù)與量詞

第一篇數(shù)理邏輯第二章謂詞邏輯解：M(x)：x為學(xué)生，F(xiàn)(x)：x要參加考試

x(M(x)

F(x))例3：任何整數(shù)或是正或是負(fù)。解：P(x)：x為整數(shù)，Q(x)：x是正數(shù)R(x)：x是負(fù)數(shù)

x(P(x)(Q(x)

R(x)))例4：在美國留學(xué)學(xué)生未必是亞州人。解：M(x)：x在美國留學(xué)學(xué)生F(x)：x是亞州人

x(M(x)

F(x))例5：沒有些人登上木星。解：M(x)：x為人，F(xiàn)(x)：x登上木星

x(M(x)

F(x))65/932023/9/16652.2命題函數(shù)與量詞

第一篇數(shù)理邏輯第二章謂詞邏輯注：量詞是否定詞關(guān)系，約定：出現(xiàn)在量詞之前否定詞是否定被量化整個命題。練習(xí)：勇敢者未必是成功者。2、n（n2）元命題符號化將以下命題符號化例1：兔子比烏龜跑快。解：F(x)：x是兔子，Q(y)：y是烏龜H(x，y)：x比y跑快(x)(y)(F(x)

Q(y)

H(x，y))例2：有兔子比全部烏龜跑快。66/932023/9/16662.2命題函數(shù)與量詞

第一篇數(shù)理邏輯第二章謂詞邏輯

(x)(y)(F(x)

Q(y)

H(x，y)例3：不是全部兔子比烏龜跑快。

(x)(y)(F(x)

Q(y)

H(x，y))例4：不存在跑一樣快兔子和烏龜。

L(x，y)：x與y跑一樣快

(x)(y)(F(x)

Q(y)

L(x，y))

67/932023/9/16672.3~2.4一階謂詞公式第一篇數(shù)理邏輯第二章謂詞邏輯定義：一階語言字母表以下：1)個體常元：a，b，c，…2)個體變元：x，y，z，…3)函數(shù)符號：f，g，h，…4)謂詞符號：F，G，H，…5)量詞符號：，6)聯(lián)結(jié)詞符號：，，，，7)括號與逗號：（），定義：中項定義1)個體常元和個體變元是項。68/932023/9/16682.3~2.4一階謂詞公式

第一篇數(shù)理邏輯第二章謂詞邏輯2)若(x1,x2,…,xn)是任意n元函數(shù)，t1,t2,…,tn是任意n個項，則(t1,t2,…,tn)是項。3)全部項都是有限次使用1)、2)得到。定義：原子公式設(shè)R(x1,x2,…,xn)是n元謂詞，t1,t2,…,tn是任意n個項，則稱R(t1,t2,…,tn)是原子公式定義：謂詞合式公式1)原子公式是謂詞合式公式。2)若A為謂詞合式公式，則

A為謂詞合式公式3)若A和B為謂詞合式公式，則AB，AB，AB，AB也是謂詞合式公式。4)若A為謂詞合式公式，則

xA(x)，

xA(x)也是謂詞合式公式。69/932023/9/16692.3~2.4一階謂詞公式

第一篇數(shù)理邏輯第二章謂詞邏輯5)僅由有限次使用1)—4)組成符號串才是謂詞合式公式。合式公式也稱謂詞公式，簡稱公式。定義：轄域，指導(dǎo)變元約束出現(xiàn)，自由出現(xiàn)在

xA(x)，

x

A(x)中，x指導(dǎo)變元，A為對應(yīng)量詞轄域。x，例：指出以下公式中轄域，指導(dǎo)變元，約束出現(xiàn)，自由出現(xiàn)。1)x(F(x，y)G(x，z))1)解：x：約束出現(xiàn)，指導(dǎo)變元

x轄域中，x全部出現(xiàn)為約束出現(xiàn)；A中不是約束出現(xiàn)那些項為自由出現(xiàn)

x轄域為：F(x，y)G(x，z)

y：自由出現(xiàn)70/932023/9/16702.3~2.4一階謂詞公式第一篇數(shù)理邏輯第二章謂詞邏輯2)x(F(x)G(y))y(H(x)L(x,y,z))定義：約束變元換名對公式中約束變元更更名稱符號，這種恪守一定規(guī)則更改稱為約束變元換名。規(guī)則：1)更改變元名稱符號是量詞中指導(dǎo)(約束)變元，以及該轄域中所2）換名時一定要改為轄域中沒有出現(xiàn)變元名稱。例：x(P(x)R(x，y))L(x,y)定義：閉式出現(xiàn)變元，在公式中其余部分不變?？蓪憺閦(P(z)R(z，y))L(x,y)71/932023/9/16712.3~2.4一階謂詞公式第一篇數(shù)理邏輯第二章謂詞邏輯設(shè)A為任意公式,若A中不含自由出現(xiàn)個體變元,則稱A為封閉公式。簡稱閉式。72/932023/9/16722.5一階謂詞演算等價式與蘊(yùn)含式第一篇數(shù)理邏輯第二章謂詞邏輯一、等值公式定義：設(shè)A，B為一階邏輯中任意兩個公式，若AB為永真式，一階邏輯等值演算主要內(nèi)容：給出一些主要等值式，有這些下面給出一些主要等值式：第一組：在命題邏輯中重言式代換實(shí)例均為一階邏輯永真式。例1：(PQ)(PQ)例2：HHF (x)H(x)(x)H(x)F第二組：則稱A，與B等值。記為AB。等值式能夠推出更多等值式。 (x)(P(x)Q(x))(x)(P(x)Q(x))1、消去量詞等值式73/932023/9/16732.5一階謂詞演算等價式與蘊(yùn)含式第一篇數(shù)理邏輯第二章謂詞邏輯設(shè)個體域為有限值，D={a1,a2,…,an}，則有(1)xA(x)

A(a1)

A(a2)…A(an)(2)xA(x)

A(a1)

A(a2)…A(an)2、量詞否定等值式(1)

(xA(x))x(

A(x))(2)(xA(x))x(

A(x))約定：出現(xiàn)在量詞之前否定，不是否定該量詞，而是否定被量化例1：A(x)表示x(人)今天來校上課

xA(x)表示任何人今天都來上課。了整個命題。74/932023/9/16742.5一階謂詞演算等價式與蘊(yùn)含式第一篇數(shù)理邏輯第二章謂詞邏輯

(xA(x))表示任何人今天都不來上課。

(xA(x))表示不是任何人今天都來上課。3、量詞轄域收縮與擴(kuò)張等值式設(shè)A(x)是任意含自由出現(xiàn)個體變元x公式，B中不含x出現(xiàn)，則：(1)x(A(x)B)xA(x)B(xA(x))x(

A(x))xA(x)Bx(A(x)B)x(BA(x))BxA(x)(2)x(A(x)B)xA(x)Bx(A(x)B)xA(x)B75/932023/9/16752.5一階謂詞演算等價式與蘊(yùn)含式第一篇數(shù)理邏輯第二章謂詞邏輯xA(x)Bx(A(x)B)x(BA(x))BxA(x)例：證實(shí)

xA(x)Bx(A(x)B)xA(x)B(x)A(x)B (x)(A(x))B(x)(A(x)B)x(A(x)B)說明：A(x)：x(人)為張村人，B：姓張左：對全部些人，為張村人或姓張

x(A(x)B)xA(x)B

x(A(x)B)xA(x)B右：全部些人為張村人，或姓張76/932023/9/16762.5一階謂詞演算等價式與蘊(yùn)含式第一篇數(shù)理邏輯第二章謂詞邏輯左：對全部些人，既為張村人又姓張右：全部些人為張村人且姓張

xA(x)Bx(A(x)B)左：若每個人是張村人，則姓張

右：有些人，若是張村人則姓張

x(BA(x))BxA(x)左：對全部些人，若姓張則是張村人右：若姓張，則全部些人都是張村人4、量詞分配等值式77/932023/9/16772.5一階謂詞演算等價式與蘊(yùn)含式第一篇數(shù)理邏輯第二章謂詞邏輯(1)x(A(x)B(x))xA(x)xB(x)(2)x(A(x)B(x))xA(x)xB(x)說明：A(x)：x(人)很努力 B(x)：x(人)很聰明

x(A(x)B(x))xA(x)xB(x)左：全部些人，既努力又聰明右：全部些人很努力同時全部些人很聰明

x(A(x)B(x))xA(x)xB(x)左：有些人，很努力或者很聰明右：有些人很努力或者有些人很聰明78/932023/9/16782.5一階謂詞演算等價式與蘊(yùn)含式第一篇數(shù)理邏輯第二章謂詞邏輯5、量詞與命題聯(lián)結(jié)詞之間一些蘊(yùn)含式(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)x

B(x)(4)x(A(x)B(x))xA(x)x

B(x)僅對二元謂詞，且不考慮自由變元，有以下八種形式：xy(A(x,y))， yx(A(x,y))xy(A(x,y))， yx(A(x,y))xy(A(x,y))， yx(A(x,y))xy(A(x,y))， yx(A(x,y))79/932023/9/16792.6一階謂詞前束范式第一篇數(shù)理邏輯第二章謂詞邏輯在命題邏輯中，析取范式與合取范式是兩種不一樣等值形式，在一階定義：前束范式設(shè)A為一階邏輯公式，若A含有以下形式：例1：(x)(y)(z)(P(x)Q(x)R(x,z))例2：(x)(y)(F(x)H(y)G(x,y))例3：(x)(F(x)(y)(G(y)H(x,y))定理：（前束范式存在定理）一階邏輯公式中任何公式都存在與之等值前束范式?；癁榍笆妒讲襟E：謂詞也有范式。

Q1x1Q2x2…QkxkB則稱A為前束范式，其中QI為或，B為不含量詞公式。80/932023/9/16802.6一階謂詞前束范式第一篇數(shù)理邏輯第二章謂詞邏輯1)將“”移至命題變元or謂詞之前。2)約束元換名3)將量詞移到全式最前面

x(A(x)B)xA(x)B注：普通前束范式不唯一。求以下公式前束范式例1：xF(x)xG(x)解：

xF(x)xG(x)xF(x)x(G(x))xF(x)y(G(y))x(A(x)B)xA(x)Bxy(F(x)(G(y)))81/932023/9/16812.6一階謂詞前束范式第一篇數(shù)理邏輯第二章謂詞邏輯例3：

xP(x)xQ(x)

解：

xP(x)xQ(x)xP(x)xQ(x)x(P(x))xQ(x)x((P(x))Q(x))定義：前束合取范式和前束析取范式設(shè)A為前束范式，且含有Q1x1Q2x2…QkxkB形式，假如B為合取范式，則A為前束合取范式。假如B為析取范式，則A為前束析取范式。怎樣求前束合取范式和前束析取范式?82/932023/9/16822.6一階謂詞前束范式第一篇數(shù)理邏輯第二章謂詞邏輯定理：每一個前束范式都能夠轉(zhuǎn)化為與其等價前束合取范式或前束析取范式。步驟 1：取消多出量詞；2：換名；3：消去條件聯(lián)結(jié)詞；4：例：將A=x[(yP(x)zQ(z，y))yR(x,y)]化為與其等價前束合取范式。

解：第一步：消去多出量詞Ax[(P(x)zQ(z，y))yR(x，y)]Ax[(P(x)zQ(z，y))wR(x，w)]第三步：消去條件聯(lián)結(jié)詞Ax[(P(x)zQ(z，y))wR(x，w)]將深入；5：將量詞推到左邊第二步：換名83/932023/9/16832.6一階謂詞前束范式第一篇數(shù)理邏輯第二章謂詞邏輯第四步：將

深入Ax[(

P(x)