高等數(shù)學數(shù)學

1、第二章第二章 謂詞邏輯謂詞邏輯 l在命題邏輯中，以原子命題為演算的最小單位，主要是研究命題之間的邏輯關(guān)系。命題是具有真 假意義的一句話，而對這句話的內(nèi)部結(jié)構(gòu)和成分是不作分析的，不能揭示原子命題內(nèi)部的特征。 因此，命題推理存在著不足，有些簡單的論斷也不能用命題邏輯進行推論，例如著名的蘇格拉底 三段論 l所有的人都是要死的； l蘇格拉底是人。 l所以，蘇格拉底是要死的。 l又如： l所有的無理數(shù)都是實數(shù)； l是無理數(shù)。 l 所以，是實數(shù)。 l按命題邏輯的方法，設(shè)P、Q、R分別表示上述三個命題，則R應該是P，Q的邏輯結(jié)果，即P,Q R， 命題公式PQR應為永真公式，但根據(jù)各種賦值情況不能保證PQR是

2、永真公式，即P,Q R 不能成立。所以用命題邏輯無法證明蘇格拉底三段論。 l原因就在于這類推理中，各命題內(nèi)部成分之間是有聯(lián)系的，需要分析命題結(jié)構(gòu)的更深層次。應該 將原子命題再細分，分析出個體詞，謂詞和量詞，以便可表達個體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系， 這就是一階邏輯所研究的基本內(nèi)容。一階邏輯也稱一階謂詞邏輯或謂詞邏輯。 l2.1 謂詞邏輯基本概念 l2.1.1 個體和謂詞 l一、一、個體和個體域 l命題是命題是具有真假意義的陳述句。從語法上分析，一個陳述句由主語和謂語兩部分組成。陳述句。從語法上分析，一個陳述句由主語和謂語兩部分組成。 l謂詞邏輯中把討論的對象稱為個體個體，它們可以是具體客體，也

3、可以是抽象的客體，諸如數(shù)字、符 號等。確定的個體常用a，b，c等小寫字母表示，它們被稱為個體常元常元。如：張三，蘋果，6等 都可以作為個體詞表示抽象的或泛指的個體詞稱為個體變量，常用字母x，y，z，u，v，w等來 表示，它們被稱為個體變元變元。 l個體變元的取值范圍稱為個體域(或稱論域)。個體域可以是有窮集合，例如，1，2，3，4，a， b，c，d，；也可以是無窮集合，例如，自然數(shù)集合N=0，1，2，。綜合各個個體域一起 作為論述范圍稱為全總域，用字母U表示。 l二、謂詞及其表示 l用以刻劃客體的性質(zhì)或客體之間的關(guān)系（通常是謂語）即是謂詞。謂詞也有常項和變項之分。表 示具體性質(zhì)或關(guān)系的謂詞稱為

4、謂詞常項，表示抽象的、泛指的性質(zhì)或關(guān)系的謂詞稱為謂詞變項謂詞變項。 l例如： l（1）“蘇格拉底是人” l“蘇格拉底” 是個體常量，“是人” 是謂詞 。 l（2）“5小于2” l“5”，“2” 是兩個個體常量，“小于” 是謂詞 。 l（3）“直線l1 位于直線l2和直線l3之間” l“直線l1”、“直線l2”和“直線l3” 是三個個體常量，“位于和之間” 是謂詞 。 l謂詞有可以放置個體的空位，如省略號表示的部分。當空位代之以個體后便為一個關(guān)于此個體的 語句。謂詞所具有的空位的數(shù)目稱為謂詞的元數(shù)謂詞的元數(shù)。上述例子中，（1）是一元謂詞，（2）是二元 謂詞，（3）是三元謂詞。謂詞也須符號化。謂詞

5、都用大寫英文字母F，G，H，表示，用變元 來代替空位，例如可用M（x），L（x,y），AT（x,y,z）表示上述三 個謂詞，它們被稱為謂詞。 這里，用什么變元是無關(guān)緊要的。 l我們說過，當謂詞的空位上填入個體后，便產(chǎn)生一個關(guān)于該個體的語句，這時它被稱為謂詞填式。 例如：用M(a)表示個體常項a具有性質(zhì)M ，用M(x)表示個體變項x具有性質(zhì)M.而用M(a，b)表示個 體常項a，b具有關(guān)系M，用M(x,y)表示個體變項x，y具有關(guān)系M.一般的，用P(x1,x2,xn)表示含 n(n1)個命題變項的n元謂詞。n=1時，P(x1)表示x1具有性質(zhì)P；n2時，P(x1,x2,xn)表示 x1,x2,xn

6、具有關(guān)系P。 注意：本書約定命題可以看成0元謂詞, 將命題看成特殊的謂詞。 l定義定義2.1 n元謂詞P(x1,x2,xn)定義為：個體變量x1,x2,xn的定義域分別為D1，D2，Dn， 值域為0,1的n元命題函數(shù)（簡單命題函數(shù)）。 ln元謂詞P(x1,x2,xn)不是命題。但當用謂詞常項取代P，用個體常項a1,a2,an取代 x1,x2,xn，才能確定P(x1,x2,xn)的真假值，P(a1,a2,an)成為命題。 l2.1.2 量詞 l一、量詞 l有了個體詞和謂詞之后，還需要表示個體常項或變項之間數(shù)量關(guān)系的詞，即量詞。量詞可分兩種: 全稱量詞和存在量詞。全稱量詞全稱量詞和存在量詞。全稱量

7、詞用符號 表示，如：“一切的”，“任意的”，“所有的”， “每一個”，“凡”，“都”等詞可將它們都符號化為。存在量詞存在量詞用符號 表示，如“存在”， “至少有一個”“有一個”，“有的”等詞可將它們都符號化為。 l我們用 P(x) 表示“x滿足P(x)”，則xP(x) 表示：“所有（任意,每一個）x滿足P(x)”，即個體域 中所有的個體具有性質(zhì)P。而x P(x) 表示：“有（存在,至少有一個）x滿足P(x)”，即個體域中至 少有一個體具有性質(zhì)P。其中的x稱為作用變量（指導變元）。此時，P(x)稱為全稱量詞和存在量 詞的轄域。量詞的轄域或者是緊鄰其右側(cè)的那個謂詞;或者是其右側(cè)第一對括號內(nèi)的表達式

8、。 l二、約束變元和約束變元和自由變元。 l量詞轄域內(nèi)與該量詞指導變元同一的變元都是約束變元約束變元。 l例如 lx(A(x)B(x) x C(x) l中x的轄域是A(x)B(x)，其中的x是約束變元； x轄域是C(x)，x是約束變元。 x C(x)不在x 轄域內(nèi)。 l在x A(x)B(x) 中x的轄域是A(x)，其中x是約束變元，而B(x)中x不是約束變元稱為自由變元自由變元。 l在x和x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)約束出現(xiàn)。不是約束出現(xiàn)的其他變項均稱為是自由出現(xiàn)自由出現(xiàn) 的。 l三、變元改名與代入 l在一公式中，有的個體變元既是約束出現(xiàn)，又是自由出現(xiàn)，這就容易產(chǎn)生混淆。為了避免混淆

9、， 可對約束變元換名或自由變元代入。 l對于xF(x) ，zH(z)，我們可以對指導變元改名，比如改為yF(y) ，xH(x)。其含義不變。 l（1）改名規(guī)則，即將量詞某個指導變元及相應轄域中約束出現(xiàn)的個體變元，改成本轄域中未曾 出現(xiàn)過的個體變元，其余不變。 l2.1.3 謂詞公式及語句的符號化 l一、謂詞公式 l當限定量詞的指導變元為個體變元（不用命題變元、謂詞、函數(shù)變元 - 分別以命題、謂詞、 函數(shù)為值的變元）時，謂詞演算又稱為一階謂詞演算一階謂詞演算。我們只討論一階謂詞演算。 l一階謂詞演算使用如下符號： l（1）個體常量符號：a,b,c,a1,b1,c1,。是個體域D中的某個元素。 l

10、（2）個體變量符號：x,y,z,x1,y1,z1, 。是個體域D中的任意元素。 l（3）函數(shù)符號：f,g,h,f1,g1,h1,。當個體域為D，n元函數(shù)符號f(x1,x2,xn)可以是DnD的 任意一個函數(shù)。 l（4）謂詞符號： P,Q,R,P1,Q1,R1。當個體域為D，n元謂詞符號P(x1,x2,xn)可以是 Dn0,1的任意一個謂詞。 l定義定義2.2 謂詞邏輯中的項 ，被遞歸地定義為： l（1）任意的個體常量符號或任意的個體變量符號是項； l（2）若f（x1,x2,xn）是n 元函數(shù)符號，t1,t2, ,tn是項，則f(t1,t2, tn）是項； l（3）僅僅由有限次使用（1），（2）

11、產(chǎn)生的表達式才是項。 l定義定義2. 3 若P(x1,x2,xn)是n元謂詞，t1,t2,tn是項，則稱P(t1,t2,tn)為原子謂詞公式，簡 稱原子公式。 l由原子公式及邏輯符號出發(fā)，可給出謂詞邏輯中的謂詞的合適公式的遞歸定義。 l定義定義2.4 滿足下列條件的表達式，稱為合適公式（Well-Formed Formulae/Wff）,簡稱公式。 l(1)原子公式是合式公式。 l(2)若A是合式公式，則(A)也是合式公式。 l(3)若A，B是合式公式，則(AB)，(AB)，(AB)，(AB)也是合式公式。 l (4)若A是合式公式，則xA，xA也是合式公式。 l (5)只有有限次的應用(1)

12、(4)構(gòu)成的符號串才是合式公式。 l由上述定義可知，合適公式是按上述規(guī)則由原子公式、聯(lián)結(jié)詞、量詞、圓括號和逗號所組成的 符號串。括號省略方式如同命題公式。但量詞轄域中僅出現(xiàn)一個原子公式，則此轄域的括號可 省略，否則不能省略其括號。 l定義定義2.5 設(shè)A是任意的公式，若A中不含有自由出現(xiàn)的個體變元，則稱A為封閉的公式封閉的公式，簡稱閉閉 公式公式。 l由閉式定義可知，閉式中所有個體變元均為約束出現(xiàn)。 l例如x (P(x) R(x)是閉公式。 l二、語句的符號化 l把一個文字敘述的命題，用謂詞公式表示出來，稱為謂詞邏輯的翻譯或符號化或形式化；反之 亦然。 l例2.7 在個體域分別為(a) 個體域

13、D1為人類集合；(b) 個體域D2為全總個體域時， l將下面兩個命題符號化: l(1) 每一個人都會犯錯誤。 l(2) 有的人會打籃球。 l解：(a)令A(x):x會犯錯誤；B(x):x會打籃球。 l由于所有 x D1，有A(x)，(1)符號化為 xA(x) l由于存在 x D1，有B(x) (2)符號化為 xB(x) l(b) D2為全總個體域,人類是其子集，如果（1）翻譯為 xA(x)，(2) 翻譯為 xB(x)，意義就 不一樣了。 l在D2情況下，需限定范圍 ，即指D2 中的人類子集。所以，引入謂詞M(x) ：x是人。這時 l(1) 符號化為 x(M(x)A(x) l(2) 符號化為 x

14、(M(x)B(x) l謂詞M(x)稱為特性謂詞。一般情況，總是使用全總個體域。所以，要用特性謂詞限定范圍。 l特性謂詞在加入到公式中時遵循如下原則： l（1）對于全稱量詞x， 特性謂詞作為前件加入條件式。 l（2）對于存在量詞x， 特性謂詞作為合取項加入合取式。 l2.2 謂詞邏輯永真式 l2.2.1公式的解釋 l謂詞公式是由一些抽象的符號構(gòu)成的，是由原子謂詞公式 、邏輯聯(lián)結(jié)詞、量詞、括號連接起來的 抽象表達式。給定一個謂詞公式，它的實際意義是什么？這涉及到謂詞邏輯的語義問題。若對它 們（常量符號、變量符號、函數(shù)符號、謂詞符號）給以具體的解釋，則公式就有實際的意義，才 可能有真或假。 l由此，

15、謂詞邏輯中公式G的每一個解釋I 由如下四部分組成： l（1）非空的個體域集合D； l（2）對G 中的每個常量符號，指定D中的某個特定的元素； l（3）對G 中的每個n元函數(shù)符號，指定Dn到D中的某個特定的函數(shù)； l（4）對G 中的每個n元謂詞符號，指定Dn到0,1中的某個特定的謂詞。 lx G(x)是這樣的一個命題：“對任意屬于個體域D中的x，G(x)都為真”。故對命題的真值如下規(guī) 定： lx G(x)= lxG(x)是命題“存在一個個體域D中的a，使得G(a)為真”，其真值為 lxG(x)= l按照上述定義，給定有限個體域集D=a1,a2,an時， lxA(x)=A(a1)A(a2)A(an

16、)； lxA(x)=A(a1)A(a2)A(an)。 l2.2.2謂詞演算永真式 l一、謂詞公式分類 l從上述例題可以看到，同一個公式在不同解釋下真值可能不同。 l定義定義2.6 設(shè)A為一個公式，若A在任何解釋下均為真，則稱A為永真式永真式(或稱邏輯有效式或稱邏輯有效式)。若A在任 何解釋下均為假，則稱A為矛盾式矛盾式(或永假式或永假式)。若至少存在一個解釋使A為真，則稱A為可滿足式可滿足式。 l從上述定義可知： l（1）永真式的否定為矛盾式；矛盾公式的否定為有效公式。 l（2）永真式一定為可滿足式。 l謂詞演算中允許使用命題常元，謂詞公式中仍包含命題公式，其中的重言式在謂詞演算中仍然 是永真

17、式。當把命題演算中的重言式中的命題變元，代入任意的謂詞公式，都不會影響原式的 永真性，從而它們也是謂詞公式中的重言式，是永真式。這種通過代入得到的公式稱為原公式 的代入實例代入實例。永真公式的任意一個代入實例必為永真式。 l如 PP 是重言式，用A(x)代入P得到代入實例A(x) A(x)也是重言式；用x A(x) 代入P得 到代入實例x A(x) x A(x)也是重言式。 l需要指出的是：謂詞邏輯是不可判定的。即對任一謂詞公式而言，沒有能行的方法判明它是否 是有普遍有效性的。但是，類似命題邏輯可用真值表法判明任一命題公式的永真性，個體域有 窮時的謂詞公式是可判定的。 l 二、謂詞演算的等價式

18、和蘊含式 l定義定義2.7 設(shè)A，B是謂詞邏輯中任意兩個公式，若AB是永真式，則稱A與B是等價的等價的。記做 AB，稱AB是等價式等價式； 若 AB是永真式，則稱A 蘊含蘊含B。記做AB，稱AB是蘊含式蘊含式。 l定義定義2. 8 設(shè)謂詞公式A中含自由變元x，設(shè)t為一個項，稱t關(guān)于A對x可代入，如果t中無自由變元 為A中的約束變元。 l關(guān)于謂詞邏輯的替換原理，同命題邏輯。 l定義定義2.9 設(shè)A為僅含聯(lián)結(jié)詞 ，的謂詞公式，A*為將A中符號，T，F(xiàn)， , 分別換 為，F(xiàn)，T, ， 后所得的公式，那么稱A*為A的對偶式。 l第一章中關(guān)于對偶式的一切討論，現(xiàn)在對于謂詞演算都仍然成立。 l 下面討論謂

19、詞邏輯等價式。 l(1)命題永真式代入實例 l由于命題邏輯中的重言式的代換實例都是謂詞邏輯中的重言式，因而第一章的等值式給出的 代換實例都是謂詞邏輯中的等價式。例如： l xA(x) xA(x) l A(x)B(y) A(x)B(y) l(2) 量詞否定等價式 lx A(x) xA(x)； lx A(x) xA(x)； l這表明兩個量詞可相互表示。 l當個體域為有限集a1,an時,可以簡單證明： l x A(x) (A(a1)A(an) A(a1)A(an) xA(x); l（3）量詞轄域的擴張與收縮 lA(x)是任意的含自由出現(xiàn)個體變項x的公式，B中不含x的出現(xiàn),則 lx (A(x)B) x

20、 A(x)B； lx (A(x)B) x A(x)B； lx (A(x)B) x A(x)B； l x (A(x)B) x A(x)B； l由上經(jīng)證明可得到： lx (A(x)B) xA(x)B x (BA(x) Bx A(x) lx(A(x)B) x A(x)B x(BA(x) BxA(x) lx A(x) x B(x) x y(A(x)B(y)； l x A(x) x B(x) x y(A(x)B(y)； l（4）量詞分配律 l A(x)，B(x)是任意的含自由出現(xiàn)個體變元x的公式， l x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) l（5） 量詞

21、與命題聯(lián)結(jié)詞之間的一些蘊含式 l x A(x) x A(x)； l x A(x)x B(x) x (A(x)B(x)； l x (A(x)B(x) x A(x)x B(x)； l x (A(x)B(x) x A(x)x B(x)； l x (A(x)B(x) x A(x)x B(x)。 l（6）多個量詞的基本等價公式和蘊涵公式,設(shè)A(x,y)是含有自由變元x,y的謂詞公式，則有 l ( x ) ( y )A(x,y) ( y ) ( x )A(x,y)； l (x) (y)A(x,y) (y) (x)A(x,y)； l (x) ( y )A(x,y) ( y ) (x)A(x,y)； l (

22、x ) ( y )A(x,y) (y) ( x )A(x,y)； l ( y ) ( x )A(x,y) (x) ( y )A(x,y)； l (y) ( x )A(x,y) ( x ) (y)A(x,y)； l ( x ) (y)A(x,y) (y) (x)A(x,y)； l ( y ) (x)A(x,y) (x) (y)A(x,y)。 l全稱量詞與存在量詞在公式中出現(xiàn)的次序，不能隨意更換。 l2.3 謂詞公式的前束范式 l在命題邏輯里，每一公式都有與之等價的范式，在判定一個公式特性（如永真、永假）時，范式 起著重要作用，而對謂詞邏輯的公式來講，我們學習前束范式與原公式是等值的，而其他范式與

23、 原公式只有較弱的關(guān)系。 l定義定義2. 10 稱公式A是一個前束范式，如果A中的一切量詞都位于該公式的最前端（不含否定詞） 且這些量詞的轄域都延伸到公式的末端。其標準形式如下： l(Q1x1)(Q2x2)(Qnxn)B(x1,x2,xn) l其中，Qi為量詞或（i=1,n），M稱作公式B的母式（基式），B中不再有量詞。特別地，若 中無量詞，則也看作是前束范式。當B為合?。ㄎ鋈。┓妒綍r，稱為A的前束合?。ㄎ鋈。?范式。 l定理定理2.1 前束范式存在定理前束范式存在定理 l謂詞邏輯中的任一公式都可化為與之等價的前束范式，但其前束范式并不惟一。 l證明 設(shè)G是任一公式，可通過下述步驟將其轉(zhuǎn)化為與

24、之等價的前束范式： l（1）將謂詞謂詞公式等價轉(zhuǎn)換為僅含聯(lián)結(jié)詞為僅含聯(lián)結(jié)詞 ，的謂詞公式的謂詞公式； l（2）反復運用德摩根定律，直接將“”內(nèi)移到原子謂詞公式的前端； l（3）使用謂詞的等價公式（主要是量詞轄域的擴張與收縮）將所有量詞提到公式的 最前端。 l經(jīng)過這幾步，可求得任一公式的與原公式是等價的前束范式。 l定義定義2. 11 設(shè)公式A是一個前束范式，如消去A中所有的存在量詞和全稱量詞，所得 到的公式稱為Skolem標準形。 l定理定理2. 2 任意一個公式A都存在相應的Skolem標準形，但此Skolem標準形不一定與 原公式等價。 l證明 由定理2.3.1知公式A必有與之等價的前束范

25、式，設(shè)A的前束范式為 lA=(Q1x1)(Q2x2)(Qnxn)B(x1,x2,xn) l（1）如果Qi是存在量詞，且Qi的左邊沒有全稱量詞，則用一個不出現(xiàn)在B中的的常 量符號a來代替xi在B中一切出現(xiàn)。 l（2）如果Qi是存在量詞，且Qi的左邊有全稱量詞(xj),(xl),(xk)，則直接用一 個不出現(xiàn)在B中的函數(shù)f(xj,xl,xk)來取代xi在B中一切出現(xiàn)。 l（3）如果Qi是全稱量詞，則直接用一個新的變量符號x來取代xi在M中一切出現(xiàn)。 l反復使用上述（1）（3），消去前束范式中的所有存在量詞和全稱量詞，此時得 到的公式為該公式的Skolem標準形，該標準形顯然不與原公式等價。 l例如 例1的Skolem標準形為 A(v,a) (B(f(v,x)C(x) l2.4 謂詞演算推理理論 l命題邏輯的永真式在謂詞邏輯仍然成立，因此完全可以使用與命題演算時相同的術(shù)語和符號，也 可以使用命題演算系統(tǒng)中的證明方法和推理規(guī)則（規(guī)則P,規(guī)則T,規(guī)則CP）。在推導的過程中，還 可以引用