離散數(shù)學(xué)高等里離散數(shù)學(xué)-課件-chapt15

1、1,第十五章,一 階 邏 輯,2,邏輯學(xué)中的三段論,1 凡有理數(shù)都是實(shí)數(shù)2 1/3是有理數(shù)3 1/3是實(shí)數(shù),在命題邏輯中無法表示其推理過程因?yàn)槿绻覀冇肞,Q,R分別表示命題1，2，3則,,按照三段論法，P∧Q? R 可表示上述推理,這就是命題邏輯的局限性,三段論的論斷顯然正確，但在命題邏輯中P∧Q?R并不是重言式。取P=1，Q=1，R=0，就可弄假P∧Q?R,故其不能正確反映三段論的推理過程,3,原 因,在命題

2、邏輯中無法將所有命題之間的內(nèi)在聯(lián)系反映出來。命題邏輯中描述的三段論，即P∧Q→R，使R是與命題P、Q無關(guān)的獨(dú)立命題。但實(shí)際上R是與命題P、Q有關(guān)的，只是這種關(guān)系在命題邏輯中得不到反映。,要反映這種內(nèi)在聯(lián)系,就要對簡單命題作進(jìn)一步分析,分析出其中的個(gè)體詞,謂詞,量詞,研究它們的形式結(jié)構(gòu)及邏輯關(guān)系,總結(jié)出正確的推理形式和規(guī)則,這就是一階邏輯所研究的內(nèi)容.一階邏輯也稱謂詞邏輯.,4,§15.1 謂詞與量詞,,研究對象的全體所構(gòu)成的

3、集合.又稱個(gè)體域。,一階邏輯中論域中的元素.又稱個(gè)體詞。,定義15.1.1,設(shè)D是非空個(gè)體集合。定義在Dn上取值于 {0,1 }上的n元函數(shù)稱為n元命題函數(shù)或n元謂詞。其中Dn表示D的n次笛卡爾積.,1.論域：,2.個(gè)體：,令P(x)表示x為質(zhì)數(shù)，則P(x)為一元謂詞。 令H(x，y)表示“x高于y”。則H(x，y)為二元謂詞。 將x代以個(gè)體“張三”，y代以個(gè)體“李四”

4、， 則H(張三,李四)就是命題“張三高于李四”。,注意： P(x.y)與H(x,y)為命題函數(shù).而P(2)與H(張三,李四)才是命題。,例子：,3.量詞:,在命題中表示數(shù)量的詞.分兩類.即存在與全稱量詞.,5,概念的討論,謂詞是用來刻劃個(gè)體的性質(zhì)或個(gè)體之間的關(guān)系的。,謂詞如有n個(gè)變元則稱為n元謂詞. n元謂詞反映了n元關(guān)系.,變元在謂詞中的次序直接影響了謂詞的取值.,如:謂詞P(x,y)為“x

5、比y高”.,而張三為170cm,李四為180cm.,則:P(李四,張三)為真命題. P(張三,李四)為假命題.,個(gè)體是可以獨(dú)立存在的實(shí)體,它既可以是一個(gè)具體的事物,也可以是一個(gè)抽象的概念,用個(gè)體,謂詞表示命題的例子:,6,例子:,1,武漢位于重慶與上海之間.,解:個(gè)體a,b,c分別表示武漢,重慶和上海,,謂詞P(x,y,z)表示x位于y與z之間,,則命題表示為P(a,b,c).,2,如果王英坐在李洪的后面,則王英比李紅高.,

6、令a:王英;b:李紅;P(x,y):x坐在y的后面;G(x,y):x比y高.,則命題表示為P(a,b)?G(a,b).,,7,三段論基于謂詞的符號化：,A(x):x是有理數(shù)，B(x):x是實(shí)數(shù)，則三段論可表示為：P：A(x) ?B(x) Q：A(1/3) R：B(1/3).,﹁P?﹁(A(x)?B(x)) ? ﹁(﹁A(x) ∨B(x)) ?A(x) ∧ ﹁B(x),這樣，

7、﹁P譯為“所有有理數(shù)都不是實(shí)數(shù)”,矛 盾,原 因,僅引進(jìn)謂詞還不足以確切地刻畫命題，例如:,日常生活中，上述命題P為: “凡有理數(shù)都是實(shí)數(shù)”。而命題P的否定﹁P,應(yīng)理解成，“有些有理數(shù)不是實(shí)數(shù)”但是,8,原因：,命題P的確切意思為：“對任意x，如果x是有理數(shù)，則x是實(shí)數(shù)”。但是，A(x)?B(x)中并沒有確切表達(dá)出“對任意x”這個(gè)意思。這說明， A(x)?B(x)還不是一個(gè)命題。因此，在一階邏輯中，除了引進(jìn)謂詞外，還需要引

8、進(jìn)語句“對任意x”，以及與之對偶的語句“存在一個(gè)x”。,9,定義 15.1.2：,當(dāng)且僅當(dāng)對任意x∈D，G(x)均為真。,當(dāng)且僅當(dāng)存在一個(gè) x0∈D,使G(x0)為假。,當(dāng)且僅當(dāng)存在一個(gè)x0 ∈ D ，使G(x0) 為真；,當(dāng)且僅當(dāng)對任意x ∈ D ， G(x)均為假。,語句“對任意x”稱為全稱量詞，記為:,語句“存在一個(gè)x”稱為存在量詞，記為 :,設(shè)G（x）是一個(gè)一元謂詞，D是論域。,其真值規(guī)定為:,,其真值規(guī)定如下：,10,兩個(gè)重

9、要的式子：,則，三段論法中的命題P 及﹁P可符號化如下：,此時(shí)，﹁P確實(shí)是命題“凡有理數(shù)都是實(shí)數(shù)”的否定。,當(dāng)論域D為有限集時(shí)，如D=｛a1,a2 ,…,an｝，對于任意一元謂詞G(X)，都有,即消去了量詞，化成了命題邏輯中等值的命題公式。,注意：,??x(?(A(x) →B(x)),至P24,11,將命題符號化時(shí)，必須明確所涉及到的個(gè)體集合，即論域。,例子：,而我們約定，除非特別說明，所有論域均為由一切對象組成的個(gè)體集合。,論域的討

10、論：,令：M (x) : x 是人。D (x) : x 要死。對命題“人是要死的”,如果論域是全人類，可符號化為,如果論域是世界上一切生物，可符號化為,12,命題符號化的例子：,例1：沒有不犯錯(cuò)誤的人,令H（x）： x是人,,M（x）： x犯錯(cuò)誤,例2：閃光的未必都是金子,令L（x）： x是閃光的,,G（x）： x是金子,例3：存在著偶質(zhì)數(shù),令E(x)：x是偶數(shù),,P(x)：x是質(zhì)數(shù),則有：?x(E(x)∧P(x)),13,例4

11、：每個(gè)自然數(shù)都有后繼數(shù),令N（x）：x 是自然數(shù),,H（x,y）：y是x的后繼數(shù),例5：對平面上的任意兩點(diǎn)，有且僅有一條直線通過這兩點(diǎn),令P（x）： x是一個(gè)點(diǎn),,L（x）：x是一條直線,,T（x,y,z）：z通過x,y,,E（x,y）：x等于y,命題符號化的例子：,例6：所有的人指紋都不一樣,令M(x)：x是人,,D(x,y)：x與y相同,,S(x,y)：x與y指紋相同,14,習(xí) 題,(1)任何金屬都可以溶解在某種液體中.

12、(2)每一個(gè)人的祖母都是他父親的母親.,解(1):,令J(x):x是金屬;,E(x):x是液體;,S(x,y):x可以溶解在y中,,(2):,令P(x):x是人;,F(x,y):y是x的父親;,M(x,y):y是x的母親;,G(x,y)x是y的祖母;,15,習(xí) 題:,令P(x)為“x是質(zhì)數(shù)”,E(x)為“x是偶數(shù)”,O(x)為“x是奇數(shù)”,D(x,y)為“x除盡y”.把下列各式譯成漢語.,解:,(a) 對所有x,若x是偶數(shù),則對所

13、有y,若x除盡y,則y是偶數(shù).,(b)對所有x,若x是質(zhì)數(shù),則存在y,y是偶數(shù)且x除盡y,(c)對所有x,若x是奇數(shù),則對所有y,y是質(zhì)數(shù),則x不能除盡y.,(即所有質(zhì)數(shù)能除盡某些偶數(shù)),(即任何奇數(shù)不能除盡任何質(zhì)數(shù)).,y,16,§15.2 合式公式及解釋,當(dāng)論域D給出時(shí)，它可以是D中的某個(gè)元素。,當(dāng)論域D給出時(shí)，它可以是D中的任何一個(gè)元素。,引進(jìn)合式公式的概念，在形式化中使用的四種符號：,第一，常量符號：,a,b,c,a

14、i,bi,ci …i≥1,第二，變量符號：,x,y,z ,xi,yi,zi …i ≥ 1,第三，函數(shù)符號：,f,g,h ,fi,gi,hi …i ≥ 1,第四，謂詞符號：,P,Q,R ,Pi,Qi,Ri …i ≥ 1,當(dāng)論域D給出時(shí)，n元函數(shù)符號f(x1，…xn)可以是D n到D的任意一個(gè)映射。,當(dāng)論域D給出時(shí)，n元謂詞符號P(x1，…xn)可以是Dn到{0,1}的任意一個(gè) 謂詞。,17,項(xiàng)的定義（定義15.2.1）：,,,,,,,(

15、1) 常量符號是項(xiàng)；,(3) 若f(x1,…,xn)是n元函數(shù)符號，t1,…,tn是項(xiàng)，則f(t1,…,tn)是項(xiàng)；,(2) 變量符號是項(xiàng)；,(4) 只有有限次地使用(1),(2),(3)所生成的符號串才是項(xiàng)。,例如：a,b,x,y是項(xiàng)，f(x,y)=x+y,g(x,y)=x·y是項(xiàng)，f(a,g(x,y))=a+x·y也是項(xiàng)。,18,原子與公式(定義15.2.2，15.2.3)：,2.2. 設(shè)P(x1,…

16、xn)是n元謂詞，t1,…,tn是項(xiàng)， 則稱P(t1,…tn)為原子公式，或簡稱原子。,2.3. 一階邏輯中的合式公式，也稱為謂詞公式，簡稱為公式，其遞歸定義為：,（1）原子是合式公式；,（2）若A是合式公式，則(﹁A)也是合式公式；,（3）若A,B是合式公式，則(A∧B), (A∨B), (A→B), (A?B)也是合式公式；,（4）若A是合式公式，x是A中的變量符號，,（5）只有有限次地使用（1）—（4）所生成的符號串才是合

17、式公式。,19,,§15.1中各命題符號化的結(jié)果都是合式公式。對于一個(gè)謂詞，如果其中每一個(gè)變量都在一個(gè)量詞的作用之下，則它就不再是命題函數(shù)而是一個(gè)命題了。但是，這種命題和命題邏輯中的命題還是有區(qū)別的。因?yàn)檫@種命題中畢竟還有變量，盡管這種變量和命題函數(shù)中的變量有所不同。因此，有必要區(qū)分這些變量。,20,約束變量與自由變量(定義15.2.4)：,1 在一個(gè)謂詞公式中變量的出現(xiàn)說是約束的，當(dāng)且僅當(dāng)它出現(xiàn)在使用這個(gè)變量的量詞

18、作用域之內(nèi)。,3 至少有一次約束出現(xiàn)的變量，稱為約束變量。至少有一次自由出現(xiàn)的變量，稱為自由變量。,2 變量的出現(xiàn)說是自由的，當(dāng)且僅當(dāng)它的出現(xiàn)不是約束的。,上例中的R(x)中x的出現(xiàn)是自由的，y和z出現(xiàn)也是自由的。,例子：,例子：,例子：,上例中的x既是自由變量，又是約束變量，而y和z則是自由變量。,,21,有關(guān)公式中變量的兩條規(guī)則：,改名規(guī)則： 將謂詞公式中出現(xiàn)的約束變量改為另一個(gè)約束變量。此改名必須在量詞作用域內(nèi)各處以及

19、該量詞符號中進(jìn)行，且改成的新約束變量要與改名區(qū)域中的其它變量有別。,代替規(guī)則：對公式中某變量的所有自由出現(xiàn)，用另一個(gè)與原公式中其它變量符號均不同的變量符號來代替。,例子：,例子：,因此，通過使用改名規(guī)則和代替規(guī)則，可使一階邏輯中的公式不出現(xiàn)某變量既是約束變量又是自由變量的情況。,22,解釋(定義15.2.4)：,在一階邏輯中,公式G的一個(gè)解釋I,是由非空論域D和對G中常量符號、函數(shù)符號、謂詞符號按下列規(guī)則進(jìn)行的一組指定所組成。,1)

20、 對每個(gè)常量符號，指定D中一個(gè)元素；,對每個(gè)n元函數(shù)符號，指定一個(gè)函數(shù)，即指定一個(gè)Dn到D的映射；,對每個(gè)n元謂詞符號，指定一個(gè)謂詞，即指定一個(gè)Dn到{0,1}上的映射。,注意：為統(tǒng)一起見，對以上定義中的公式規(guī)定：公式中無自由變量，或?qū)⒆杂勺兞靠醋鞒Ａ?。于是，每個(gè)公式在任何具體解釋下總表示一個(gè)命題。,23,例 子:,顯然此公式在解釋I下，取1值（為真）。因?yàn)椋?,給出論域,對公式中的常量符號a指定為2,指定函數(shù)f,另外x=

21、3時(shí)，P(f(3))∧Q(3,f(2))為假，注意到對x的約束是存在量詞?x，故此公式在該解釋下為真。,24,習(xí)題,給定解釋I如下: (1) Di:={2,3}； (2) a?=2； (3) 函數(shù)f(x)為f(2)=3，f(3)=2； (4) 謂詞：F(x)為F(2):=0,F(3):=1; G(x,y)為G(i,j):=1,i,j=2,3; L(x,y)為L(2,2)=L(3,3):

22、=1, L(2,3)=L(3,2)=:0.,在解釋I下,求下列各式的真值.,解：?(F(2) ∧G(2,2))∧(F(3) ∧G(3,2)) ?(0 ∧1) ∧(1 ∧1)?0.,解：?(F(f(2)) ∧G(2,f(2))) ∨ (F(f(3)) ∧G(3,f(3))) ?(F(3) ∧G(2,3)) ∨(F(2) ∧G(3,2)) ?(1 ∧1)

23、∨(0 ∧1)?1.,解：?(L(2,2) ∨L(2,3)) ∧(L(3,2) ∨L(3,3)) ?1 ∧1?1.,注意,25,謂詞公式的分類：,定義15.2.5：設(shè)G是一個(gè)謂詞公式如果存在解釋I,使G在I 下為真（I 滿足G），則稱G是可滿足的。如果所有解釋I均不滿足G（弄假），則稱G是恒假的，或不可滿足的。如果G的所有解釋I都滿足G，則稱G是恒真的。,定理：一階邏輯的判定問題是不可解的，即不存在一個(gè)統(tǒng)一的算法

24、，對一階邏輯中的任何謂詞公式G，A能夠在有限步內(nèi)判定公式G的類型。,但，一階邏輯是半可判定的，即如果謂詞公式G是恒真的，那么，存在算法在有限步內(nèi)能檢驗(yàn)出G的恒真性。,解釋I依賴于非空個(gè)體集合D，而D可以是無窮集合，D的數(shù)目也可是無窮的。故要考慮公式的所有解釋是很難的。,26,判斷下列公式的類型:,,27,解答:,(1)無論對Q指派何種命題常元,Q∨﹁Q的真值總是1.而在I中對任意的x,總存在y=1使x-1<x+1成立,(2)

25、因?yàn)閤-y<x+y在I中的真值不確定,當(dāng)指派x=1,y=1時(shí),x-y<x+y取值為真.當(dāng)指派x=4,y=-1時(shí),x-y<x+y取值為假.故(2)為可滿足式.,,28,§15.3 等值式與范式：,定義15.3.1：設(shè)A、B是謂詞公式。若A?B是恒真公式，則稱A與B是等值的，記為A?B，否則記為A?B，稱A?B為等值式。 顯然， A?B當(dāng)且僅當(dāng)對任何解釋I，I同時(shí)滿足A與B，或I同時(shí)弄假A與

26、B。,一階邏輯中等值式的分類：,1 命題公式的推廣,2 量詞否定等值式,3 量詞作用域的收縮與擴(kuò)張等值式,4 量詞分配等值式,,29,1 命題公式的推廣,由于命題邏輯中的公式都可看作特殊的謂詞公式，因此，§14.2(P189) 給出的19個(gè)基本等值式，以及對其中每個(gè)等值中的同一命題變元用同一謂詞公式代入，所得的關(guān)系式都是一階邏輯中的等值式。例1：由P?Q?﹁P∨Q可得,例2：,可得,,,,,30,2 量詞否定等值

27、式,,,,定理：設(shè)G(x)是恰含一個(gè)自由變元x的謂詞公式，于是有：,證明：設(shè)D是論域,（1）,同理可證（2）.,,若I滿足?(?xG(x)),G,31,3 量詞作用域的收縮與擴(kuò)張等值式,定理: 設(shè)G(x)是恰含一個(gè)自由變元x的謂詞公式, H是不含變量x的謂詞公式.,于是有:,證明,,32,證明：設(shè)D是論域，I是G(x)和H的一個(gè)解釋.,,33,4 量詞分配等值式,定理: 設(shè)G(x),H(x)是恰含一個(gè)自由變

28、元x的謂詞公式,則有:,對不對？,證明,（×）,（×）,原因,,,34,原因,取解釋I如下：D：=自然數(shù)集；G(x)：=“x是奇數(shù)”；H(x)：=“x是偶數(shù)”.,,同理可證B.,,35,證明,（改名規(guī)則）,（定理15.3.2）,(析取詞交換律),（定理15.3.2）,(析取詞交換律),,36,前束范式,定義：設(shè)G為一個(gè)謂詞公式，如果G具有如下形式： Q1x1…QnxnM則稱G為前束范式，,例：,F

29、(x,y)，?x?y?zP(x,y,z) 是前束范式,?x?y(P(x,y)→Q(x,y)) 是前束范式,Q1x1…Qnxn稱為首標(biāo),M稱為母式。,37,定理15.3.4：,對任意謂詞公式G，都存在一個(gè)與其等值的前束范式。,證明：,對于公式G，可通過如下步驟得到等值于G的前束范式。,（1）使用基本等值式：,(3)必要的話，將約束變量改名。,（4）使用定理15.3.1～定理15.3.3將所有量詞都提到 公式的最左邊。,注意: 一個(gè)公

30、式的前束范式是不唯一的.,例子,38,例子:,對公式,推導(dǎo)如下:,y,39,習(xí) 題：將下式化成前束范式,解（1）：,40,解（2）：,前束范式對首標(biāo)中量詞的次序沒有要求，對母式中公式的形式也沒作何種規(guī)定。下面對前束范式作進(jìn)一步規(guī)范，即保留前束范式中的全稱量詞而消去存在量詞。,41,一種特殊的前束范式: Skolem范式,定義：設(shè)G是一個(gè)謂詞公式，Q1x1,…,QnxnM是與G等值的前束范式。其中M為合取范式。（1）若Qr是存

31、在量詞（1≤r≤n），并且它左邊沒有全稱量詞，則取異于出現(xiàn)在M中所有常量符號的常量符號c，并用c代替M中所有的xr，然后在首標(biāo)中消除Qrxr。,（2）若Qr1,…,Qrm是所有出現(xiàn)在Qrxr左邊的全稱量詞，m≥1, 則取異于出現(xiàn)在M中所有函數(shù)符號的m元函數(shù)符號 f(xr1,…,xrm)，用f(xr1,…,xrm)代替出現(xiàn)在M中的所有xr， 然后在首標(biāo)中刪除Qrxr。,（3）重復(fù)以上過程，直到該前束范式的首標(biāo)

32、中無存在量詞。,由此得到的前束范式稱為Skolem范式，其中用來代替xr的那些常數(shù)符號和函數(shù)符號稱為公式G的Skolem函數(shù)。,例子,42,例子：,1）用a代替x；2）用f(y,z)代替u；3）用g(y,z,v)代替w。,于是，得Skolem范式：,注意：公式與其Skolem范式兩者不一定等值。,例子：,令解釋I為： D={1,2};P(1,1):=0;P(1,2):=1;P(2,1):=0;P(2,2):=1f(1):=1;f(2

33、):=2,,43,定理15.3.5：,設(shè)S是謂詞公式G的Skolem范式。于是，G是恒假的當(dāng)且僅當(dāng)S是恒假的。證明：由定理15.3.4，不妨設(shè)G是前束范式：G=Q1x1…QnxnM(x1,…,xn)，并且首標(biāo)中至少有一個(gè)存在量詞。 設(shè)Qr是首標(biāo)中下標(biāo)最小的存在量詞，1≦r ≦n，令 G1=?x1…?xr-1Qr+1xr+1…QnxnM(x1,…xr-1, f(x1,…,xr-1),xr+1,…,xn)其中f(x1,…,xr-1)

34、是代替xr的Skolem函數(shù)。,44,,下面證明，G恒假當(dāng)且僅當(dāng)G1恒假，如果G1可滿足，則存在一個(gè)解釋I滿足G1，于是，對任意值組(x01,…,x0r-1)∈Dr-1，都有f(x01,…,x0r-1)∈D，使得Qr+1xr+1…QnxnM(x01,…,x0r-1,f(x01,…,x0r-1),xr+1…xn) 在I下為真。但此時(shí)滿足G1的解釋I也是滿足G的解釋。此與G恒假矛盾，故G1也恒假。反之，設(shè)G1恒假，若G可滿足，則存在

35、一個(gè)解釋I滿足G。于是，對任意值組(x01,…,x0r-1)∈Dr-1，都存在x0r∈D，使得 Qr+1xr+1…QnxnM(x01,…,x0r-1,x0r ,xr+1…xn)在I下為真。,45,,今擴(kuò)充解釋I為I’，使其包含對函數(shù)符號f(x01,…,x0r-1)的如下指定：f(x01,…,x0r-1)=x0r，對任意值組(x01,…,x0r-1)∈Dr-1。于是，I’滿足G1，矛盾，故G也恒假。設(shè)G0=G；Gk=(

36、將Gk-1中下標(biāo)最小的存在量詞用Skolem函數(shù)代替所得的公式），k=1,…,m。易知，Gm就是公式G的Skolem范式，即S=Gm 與上類似可證：G1恒假當(dāng)且僅當(dāng)G2恒假，…,Gk-1恒假當(dāng)且僅當(dāng)Gk恒假，…,Gm恒假。 因此，G0恒假當(dāng)且僅當(dāng)Gm恒假，即，G恒假當(dāng)且僅當(dāng)S恒假。,46,推論15.3.1：,設(shè)公式S是公式G的Skolem范式，于是，滿足S的解釋必滿足G,但反之不然。一階邏輯中公式G的Skolem范式

37、，在定理的機(jī)器證明中非常有用。機(jī)器定理證明中著名的歸結(jié)原理就是建立在Skolem范式基礎(chǔ)上的。,47,定義15.4.1 設(shè)G、H是兩個(gè)謂詞公式。如果G?H是恒真的,則稱G蘊(yùn)含H，或稱H是G的邏輯結(jié)果,記為G?H。 顯然，任意公式G，H，G?H的充分必要條件是：對任意解釋I，若I滿足G，則I必滿足H。,§15.4 一階邏輯的推理理論,定義15.4.2 設(shè)G1, … ,Gn, H是謂詞公式，n≥1.

38、 如果,因命題公式是謂詞公式的特殊情形，由上述定義知，謂詞演算的推理方法可看作是命題演算的推理方法的擴(kuò)張。故在推理過程中，命題演算中的前提引入規(guī)則、結(jié)論引入規(guī)則、置換規(guī)則，8個(gè)基本蘊(yùn)涵式以及對其中每個(gè)蘊(yùn)涵式中的同一命題變元用同一謂詞公式代入所得蘊(yùn)涵式，都可使用。但由于量詞的引入，某些前題與結(jié)論可能受量詞的限制。因此，還需給出一些謂詞演算中特有的蘊(yùn)涵式和推理規(guī)則。,則稱G1, … ,Gn共同蘊(yùn)含H，,或稱H是G1, …

39、,Gn的邏輯結(jié)果，記為,48,謂詞演算中的三個(gè)蘊(yùn)涵式,定理：設(shè)G(x),H(x)是恰含一個(gè)自由變元x的謂詞公式，于是，證明: (1),(3)(?xG(x)→?xH(x))??x(G(x)→H(x)),則存在x0∈D，使得G(x0) ∨H(x0)為假命題。此時(shí)，,G(x0)與 H(x0)均為假命題，從而，,在解釋I下為假。,矛盾！故,49,證明：,,因?yàn)?xG(x)→?xH(x)??(?xG(x))∨?xH(x)

40、 ? ?x(?G(x))∨?xH(x)由(1)有:?x?G(x)∨?xH(x)??x(?G(x)∨H(x)) ??x(G(x)→H(x))故 (?xG(x)→?xH(x)) ? ?x(G(x)→H(x)),(3) ?xG(x)→?xH(x) ??x(G(x)→H(x)),(2) ?x(G(x) ∧

41、H(x))? ?xG(x)∧ ?xH(x)),50,謂詞演算中的推理規(guī)則(US.UG.EG.ES),全稱指定規(guī)則 (US規(guī)則),這兩種形式可根據(jù)需要選用，兩式成立的條件是：,1 x 是A(x)中的自由變元,2 在(1)式中，y是不在A(x)中約束出現(xiàn)的任何一個(gè)變量符號,3 在(2)式中，c為任意的常量符號,例子：,設(shè)論域D為實(shí)數(shù)集.謂詞F(x,y)表示x＞y,則,其原因在于，y在A(x)中是約束出現(xiàn)的.,51,全稱推廣與存在推廣

42、規(guī)則：(UG與EG),成立條件：,1) y在A(y)中自由出現(xiàn)。,2) x不能在A(y)中約束出現(xiàn)。,例子：,在實(shí)數(shù)域中仍取F(x,y)為x>y.,則A(y)是真命題,原因是條件2)不滿足。,成立條件：,1) c是特定的常量符號.,2) 取代c的x在A(c)中沒有出現(xiàn)過.,52,錯(cuò)誤使用EG規(guī)則的例子,其原因是使用EG規(guī)則的條件2)不滿足。,53,存在指定規(guī)則(ES規(guī)則):,成立條件：,1) c是使A(c)為真的常量符號,3

43、)A(x)中的自由變元只有x.,例如：,設(shè)D為自然數(shù)集, F(x)表示“x是奇數(shù)”，G(x)表示“x是偶數(shù)”.,54,但，若不注意使用條件，則有：,前提引入,化簡，根據(jù)（1）,ES規(guī)則，根據(jù)（2）,化簡，根據(jù)（1）,ES規(guī)則，根據(jù)（4）,合取，根據(jù)（3），（5）,EG規(guī)則，根據(jù)（6）,于是得出：,,（×）違反了條件2）,55,例 1 證明：,推理過程如下：,前提引入,US規(guī)則，根據(jù)（1）,前提引入,ES規(guī)則，根據(jù)（3）,

44、化簡，根據(jù)（4）,化簡，根據(jù)（4）,假言推理，根據(jù)（2），（6）,合取，根據(jù)（5），（7）,EG規(guī)則，根據(jù)（8）,在推理過程中，y被指定為論域中的任一個(gè)體，a被指定為論域中的某一個(gè)體。對于(2)和(6)，在使用假言推理時(shí)，由于y是任一個(gè)體，因此，可以選為某一個(gè)體a，故得(7)。,56,,本例也可作如下推理：,前提引入,ES規(guī)則，根據(jù)（1）,化簡，根據(jù)（2）,前提引入,US規(guī)則，根據(jù)（4）,假言推理，根據(jù)(3)，(5),化簡

45、，根據(jù)（2）,合取，根據(jù)（6），（7）,EG規(guī)則，根據(jù)（8）,57,例 2 證明：,蘇格拉底三段論“凡人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的”。,證明:,結(jié)論: D(a),首先將命題符號化：M(x):x是人. D(x):x是要死的. a:蘇格拉底.,前提:,證明:,前提引入,US規(guī)則，（1）,前提引入,假言推理，（2），（3）,58,例 3,有些病人相信所有的醫(yī)生，但是病人都不相信騙子。證明：醫(yī)

46、生都不是騙子。證明：命題符號化： P(x):x是病人；D(x):x是醫(yī)生；Q(x):x是騙子；R(x,y):x相信y。前提：?x(P(x)∧?y(D(y)→R(x,y)))， ?x?y(P(x)∧Q(y)→?R(x,y))結(jié)論：?x(D(x)→?Q(x))推理：,59,,?x(P(x)∧?y(D(y)→R(x,y))) 前提引入P(c)∧?y(D(y)→R(c,y)) ES，

47、(1)?x?y(P(x)∧Q(y)→?R(x,y)) 前提引入?y(P(c)∧Q(y)→?R(c,y)) US，(3)P(c)∧Q(z)→?R(c,z) US，(4)?(P(c)∧Q(z))∨R(c,z) 蘊(yùn)涵等值式，(5)?P(c)∨?Q(z)∨R(c,z) De Morgan律,(6)?P(c)∨(Q(z)→?R(c,z))

48、 蘊(yùn)涵等值式，(7)P(c) 化簡，(2)Q(z)→?R(c,z) 析取三段論，(8)，(9)R(c,z)→?Q(z) 等值演算，(10)?y(D(y)→R(c,y)) 化簡，(2)D(z)→R(c,z) US，(12)D

49、(z)→?Q(z) 假言三段論，(11)，(13)?x(D(x)→?Q(x)) UG，(14),60,例 4：指出下面推理的錯(cuò)誤,?x(F(x)→G(x)) 前提引入F(y)→G(y) US，(1)?xF(x) 前提引入F(y) ES，(3)G(y) 假言推理，(2),(4)

50、?xG(x) UG，(5),,×,沒有滿足ES規(guī)則的條件1即： ?xA(x)?A(c)c是使A(c)為真的常量符號。,F(c) ES，(3) G(c) 假言推理，(2),(4)?xG(x) EG，(5),61,習(xí)題：符號化下列命題，并論證其結(jié)論：,任何人如果他喜歡步行，他就不喜歡乘汽車，每一個(gè)人或 者喜歡乘汽車，或者喜歡騎自行車。有的人不愛

51、騎自行車，因而有的人不愛步行。命題符號化：設(shè)P(x):x喜歡步行。Q(x):x喜歡乘汽車. R(x):x喜歡騎自行車。推理的形式結(jié)構(gòu)：,62,結(jié)構(gòu)形式：,前提引入,ES，(1),前提引入,US ，(3),(5)Q(c) 析取三段論 (2),(4).,前提引入,(7) P(c)?﹁Q(c),US，(6),(8) Q(c) ?﹁P(c) 等

52、值演算，(7).,EG，(9).,證明：推理如下：,(9) ﹁P(c) 假言推理 (5)，(8).,10,63,習(xí)題：符號化下列命題，并論證其結(jié)論：,每個(gè)大學(xué)生，不是文科學(xué)生就是理工科學(xué)生，有的大學(xué)生是優(yōu)等生，小張不是理工科學(xué)生，但他是優(yōu)等生，因而如果小張是大學(xué)生，他就是文科生。命題符號化：設(shè)G(x):x是大學(xué)生。L(x):x是文科學(xué)生。P(x):x是理工科學(xué)生。S(x):x是優(yōu)秀生。c:小