離散數學第十五章

1、離離 散散 數數 學學 1第十五章一 階 邏 輯離離 散散 數數 學學 2邏輯學中的三段論1 凡有理數都是實數2 1/3是有理數3 1/3是實數在命題邏輯中無法表示其推理過程因為如果我們用P,Q,R分別表示命題1，2，3則, 按照三段論法，PQ R 可表示上述推理這就是命題邏輯的局限性三段論的論斷顯然正確，但在命題邏輯中PQR并不是重言式。取P=1，Q=1，R=0，就可弄假PQR故其不能正確反映三段論的推理過程離離 散散 數數 學學 3原 因q 在命題邏輯中無法將所有命題之間的內在聯系反映出來。命題邏輯中描述的三段論，即PQR，使R是與命題P、Q無關的獨立命題。但實際上R是與命題P、Q有關的，

2、只是這種關系在命題邏輯中得不到反映。q 要反映這種內在聯系,就要對簡單命題作進一步分析,分析出其中的個體詞,謂詞,量詞,研究它們的形式結構及邏輯關系,總結出正確的推理形式和規(guī)則,這就是一階邏輯所研究的內容.一階邏輯也稱謂詞邏輯.離離 散散 數數 學學 415.1 謂詞與量詞研究對象的全體所構成的集合.又稱個體域。一階邏輯中論域中的元素.又稱個體詞。定義定義15.1.1 設D是非空個體集合。定義在Dn上取值于 0,1 上的n元函數稱為n元命題函數或n元謂詞。其中Dn表示D的n次笛卡爾積.1.論域：2.個體： 令P(x)表示x為質數，則P(x)為一元謂詞。 令H(x，y)表示“x高于y”。則H(x

3、，y)為二元謂詞。 將x代以個體“張三”，y代以個體“李四”， 則H(張三,李四)就是命題“張三高于李四”。 注意：注意： P(x.y)與H(x,y)為命題函數.而P(2)與H(張三,李四)才是命題。例子：例子：3.量詞:在命題中表示數量的詞.分兩類.即存在與全稱量詞.離離 散散 數數 學學 5概念的討論 謂詞是用來刻劃個體的性質或個體之間的關系的。v謂詞如有n個變元則稱為n元謂詞. n元謂詞反映了n元關系.v變元在謂詞中的次序直接影響了謂詞的取值.如:謂詞P(x,y)為“x比y高”.而張三為170cm,李四為180cm.則:P(李四,張三)為真命題. P(張三,李四)為假命題.v個體是可以獨

4、立存在的實體,它既可以是一個具體的事物,也可以是一個抽象的概念用個體,謂詞表示命題的例子:離離 散散 數數 學學 6例子: 1,武漢位于重慶與上海之間.解:個體a,b,c分別表示武漢,重慶和上海,謂詞P(x,y,z)表示x位于y與z之間,則命題表示為P(a,b,c).2,如果王英坐在李洪的后面,則王英比李紅高.令a:王英;b:李紅;P(x,y):x坐在y的后面;G(x,y):x比y高.則命題表示為P(a,b)G(a,b).離離 散散 數數 學學 7三段論基于謂詞的符號化：A(x):x是有理數，B(x):x是實數，則三段論可表示為：P：A(x) B(x) Q：A(1/3) R：B(1/3).P(

5、A(x)B(x) (A(x) B(x) A(x) B(x)這樣， P譯為“所有有理數都不是實數”矛矛 盾盾原原 因因僅引進謂詞還不足以確切地刻畫命題，例如僅引進謂詞還不足以確切地刻畫命題，例如:日常生活中，上述命題P為: “凡有理數都是實數”。而命題P的否定P,應理解成，“有些有理數不是實數”但是離離 散散 數數 學學 8原因： 命題P的確切意思為：“對任意x，如果x是有理數，則x是實數”。但是，A(x)B(x)中并沒有確切表達出“對任意x”這個意思。這說明， A(x)B(x)還不是一個命題。因此，在一階邏輯中，除了引進謂詞外，還需要引進語句“對任意x”，以及與之對偶的語句“存在一個x”。離離

6、 散散 數數 學學 9定義 15.1.2：當且僅當對任意xD，G(x)均為真。當且僅當存在一個 x0D,使G(x0)為假。當且僅當存在一個x0 D ，使G(x0) 為真；當且僅當對任意x D ， G(x)均為假。語句語句“對任意對任意x”稱為全稱量詞，記為稱為全稱量詞，記為:xx語句語句“存在一個存在一個x”稱為存在量詞，記為稱為存在量詞，記為 :設G（x）是一個一元謂詞，D是論域。其真值規(guī)定為:,)(. 1為真xxG.)(,)(均為真對任意表示命題則xGDxxxG.)(,)(為真使存在一個表示命題xGDxxxG其真值規(guī)定如下：,)(. 1為真xxG為假，)(. 2xxG為假，)(. 2xxG

7、離離 散散 數數 學學 10兩個重要的式子：則，三段論法中的命題P 及P可符號化如下：此時，P確實是命題“凡有理數都是實數”的否定。 )()(xGxxxG)()(xGxxxG)()(:xBxAxP)()(xBxAxP)()(xBxAx當論域D為有限集時，如D=a1,a2 ,an，對于任意一元謂詞G(X)，都有即消去了量詞，化成了命題邏輯中等值的命題公式。注意：注意：)(.)()()(21naGaGaGxxG)(.)()()(21naGaGaGxxGx(A(x) B(x)至P24離離 散散 數數 學學 11將命題符號化時，必須明確所涉及到的個體集合，即論域。例子：而我們約定，除非特別說明，所有論

8、域均為由一切對象組成的個體集合。論域的討論：令：M (x) : x 是人。D (x) : x 要死。對命題“人是要死的”如果論域是全人類，可符號化為)(xxD如果論域是世界上一切生物，可符號化為)()(xDxMx離離 散散 數數 學學 12命題符號化的例子：命題符號化的例子：例例1：沒有不犯錯誤的人令H（x）： x是人,M（x）： x犯錯誤例例2：閃光的未必都是金子令L（x）： x是閃光的, G（x）： x是金子例例3：存在著偶質數令E(x)：x是偶數,P(x)：x是質數).()()()(:xMxHxxMxHx則有).()()()(:xGxLxxGxLx則有則有：x(E(x)P(x)離離 散散

9、 數數 學學 13例例4：每個自然數都有后繼數令N（x）：x 是自然數, H（x,y）：y是x的后繼數例例5：對平面上的任意兩點，有且僅有一條直線通過這兩點令P（x）： x是一個點, 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指紋相同).,()()(:yxHyNyxNx則有).,(),()(),()()()(:zuEuyxTuLuzyxTzLzyPxPyx則有).,(),()()(:yxSyxDyMxMyx則有離離 散散 數數

10、學學 14習 題 (1)任何金屬都可以溶解在某種液體中. (2)每一個人的祖母都是他父親的母親.解(1):令J(x):x是金屬; E(x):x是液體;S(x,y):x可以溶解在y中,);,()()(:yxSyEyxJx則可以表示為(2):令P(x):x是人;F(x,y):y是x的父親;M(x,y):y是x的母親;:()( ( )( )( , )( ( )( , )( , ).xyzyzx y P xP yG x yz P zF x zM z y 則可以表示為是人， 是祖母， 是父親， 是 的母親G(x,y) ：y是x的祖母;離離 散散 數數 學學 15習 題: 令P(x)為“x是質數”,E(x

11、)為“x是偶數”,O(x)為“x是奇數”,D(x,y)為“x除盡y”.把下列各式譯成漢語.).,()()()()(.();,()()()()(.();(),()()()(.(yxDyPyxOxcyxDyEyxPxbxEyxDyxExa解: (a) 對所有x,若x是偶數,則對所有y,若x除盡y,則y是偶數.(b)對所有x,若x是質數,則存在y,y是偶數且x除盡y(c)對所有x,若x是奇數,則對所有y,y是質數,則x不能除盡y.(即所有質數能除盡某些偶數)(即任何奇數不能除盡任何質數).y離離 散散 數數 學學 1615.2 合式公式及解釋合式公式及解釋當論域D給出時，它可以是D中的某個元素。當論

12、域D給出時，它可以是D中的任何一個元素。引進合式公式的概念，在形式化中使用的四種符號：第一，常量符號：a,b,c,ai,bi,ci i1第二，變量符號： x,y,z ,xi,yi,zi i 1第三，函數符號： f,g,h ,fi,gi,hi i 1第四，謂詞符號：P,Q,R ,Pi,Qi,Ri i 1當論域D給出時，n元函數符號f(x1，xn)可以是D n到D的任意一個映射。當論域D給出時，n元謂詞符號P(x1，xn)可以是Dn到0,1的任意一個 謂詞。離離 散散 數數 學學 17項的定義（定義項的定義（定義15.2.1）：）：(1) 常量符號是項；(3) 若f(x1,xn)是n元函數符號，t

13、1,tn是項，則f(t1,tn)是項；(2) 變量符號是項；(4) 只有有限次地使用(1),(2),(3)所生成的符號串才是項。例如：a,b,x,y是項，f(x,y)=x+y,g(x,y)=xy是項，f(a,g(x,y)=a+xy也是項。離離 散散 數數 學學 18原子與公式原子與公式(定義定義15.2.2，15.2.3)：2.2. 設P(x1,xn)是n元謂詞，t1,tn是項， 則稱P(t1,tn)為原子公式，或簡稱原子。2.3. 一階邏輯中的合式公式，也稱為謂詞公式，簡稱為公式，其遞歸定義為：（1）原子是合式公式；（2）若A是合式公式，則(A)也是合式公式；（3）若A,B是合式公式，則(A

14、B), (AB), (AB), (AB)也是合式公式；（4）若A是合式公式，x是A中的變量符號，（5）只有有限次地使用（1）（4）所生成的符號串才是合式公式。.,也是合式公式則xAxA 離離 散散 數數 學學 19 15.1中各命題符號化的結果都是合式公式。 對于一個謂詞，如果其中每一個變量都在一個量詞的作用之下，則它就不再是命題函數而是一個命題了。但是，這種命題和命題邏輯中的命題還是有區(qū)別的。因為這種命題中畢竟還有變量，盡管這種變量和命題函數中的變量有所不同。因此，有必要區(qū)分這些變量。離離 散散 數數 學學 20約束變量與自由變量約束變量與自由變量(定義定義15.2.4)：1 在一個謂詞公式

15、中變量的出現說是約束的，當且僅當它出現在使用這個變量的量詞作用域之內。.),(),(,)(),(),(的出現是約束的中和謂詞中公式xzxQyxPxRzxQyxPx3 至少有一次約束出現的變量，稱為約束變量。至少有一次自由出現的變量，稱為自由變量。2 變量的出現說是自由的，當且僅當它的出現不是約束的。 上例中的R(x)中x的出現是自由的，y和z出現也是自由的。例子：例子：例子：上例中的x既是自由變量，又是約束變量，而y和z則是自由變量。)()(),()(yyGxxGyyGxxG顯然有離離 散散 數數 學學 21有關公式中變量的兩條規(guī)則：改名規(guī)則： 將謂詞公式中出現的約束變量改為另一個約束變量。此

16、改名必須在量詞作用域內各處以及該量詞符號中進行，且改成的新約束變量要與改名區(qū)域中的其它變量有別。代替規(guī)則：對公式中某變量的所有自由出現，用另一個與原公式中其它變量符號均不同的變量符號來代替。例子：),(),(,),(),(zxQyuuPuxzxQyxxP得改成將公式例子：),(),(,zuQyxxPux得代替用的對上例，可將自由出現因此，通過使用改名規(guī)則和代替規(guī)則，可使一階邏輯中的公式不出現某變量既是約束變量又是自由變量的情況。離離 散散 數數 學學 22解釋(定義15.2.4)： 在一階邏輯中,公式G的一個解釋I,是由非空論域D和對G中常量符號、函數符號、謂詞符號按下列規(guī)則進行的一組指定所組

17、成。1) 對每個常量符號，指定D中一個元素；2) 對每個n元函數符號，指定一個函數，即指定一個Dn到D的映射；3) 對每個n元謂詞符號，指定一個謂詞，即指定一個Dn到0,1上的映射。注意：為統(tǒng)一起見，對以上定義中的公式規(guī)定：公式中無自由變量，或將自由變量看作常量。于是，每個公式在任何具體解釋下總表示一個命題。離離 散散 數數 學學 23例 子:.1:)3,3(;0:)2,3(;1:)3,2(;1:)2,2(;1:)3(;0:)2(;2)3(;3)2(;2:;3,2:)(,()(QQQQPPffaDIafxQxfPx并給出解釋給出公式顯然此公式在解釋I下，取1值（為真）。因為：為真時取當)2(,

18、2()2(,2fQfPx給出論域給出論域對公式中的常量對公式中的常量符號符號a指定為指定為2指定函數f另外x=3時，P(f(3)Q(3,f(2)為假，注意到對x的約束是存在量詞x，故此公式在該解釋下為真。離離 散散 數數 學學 24習題 給定解釋I如下: (1) Di:=2,3； (2) a=2； (3) 函數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):=1, L(2,3)=L(3,2)=:0.在解釋I下,求下列各式的真值.).,() 3();(,

19、()()2();,()() 1 (yxyLxxfxGxfFxaxGxFx解：(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) (0 1)1.解：(L(2,2) L(2,3) (L(3,2) L(3,3) 1 11.注意離離 散散 數數 學學 25謂詞公式的分類：定義定義15.2.5：設G是一個謂詞公式1如果存在解釋I,使G在I 下為真（I 滿足G），則稱G是可滿足的。2如果所有解釋I均不滿足G（弄假），則稱G是恒假的，或不可滿足的。3

20、如果G的所有解釋I都滿足G，則稱G是恒真的。定理：定理：一階邏輯的判定問題是不可解的，即不存在一個統(tǒng)一的算法，對一階邏輯中的任何謂詞公式G，A能夠在有限步內判定公式G的類型。但，一階邏輯是半可判定的，即如果謂詞公式G是恒真的，那么，存在算法在有限步內能檢驗出G的恒真性。 解釋I依賴于非空個體集合D，而D可以是無窮集合，D的數目也可是無窮的。故要考慮公式的所有解釋是很難的。離離 散散 數數 學學 26判斷下列公式的類型:.),(,.),(),()3();,()2();(),() 1 (yxyxGQIyxQyxGyxGyxyxyxGQQyxyxyGx表示為命題變元的個體域為整數集其中離離 散散 數

21、數 學學 27解答: (1)無論對Q指派何種命題常元,QQ的真值總是1.而在I中對任意的x,總存在y=1使x-1x+1成立(2)因為x-yx+y在I中的真值不確定,當指派x=1,y=1時,x-yx+y取值為真.當指派x=4,y=-1時,x-yy.),()(yxxFyA令則A(y)是真命題,),(是假命題規(guī)則后的式子：但使用xxxFxUG是錯誤的。故)()(xxAyA原因是條件2)不滿足。)()(:)(xxAcAEG規(guī)則成立條件：1) c是特定的常量符號.2) 取代c的x在A(c)中沒有出現過.離離 散散 數數 學學 52錯誤使用EG規(guī)則的例子.)2(,)2(),2 ,()2(.: ),(,中出

22、現過已在且為真命題則取令在實數集合中AxAxxFAyxyxF),()2(, 2,xxxFxAxEG則得到代替若用規(guī)則時在使用.)()2(,.),(,),(),(是錯誤的推理因此是一個假命題顯然而xxAAxxxFxxxFxxxFx其原因是使用EG規(guī)則的條件2)不滿足。離離 散散 數數 學學 53存在指定規(guī)則存在指定規(guī)則(ES規(guī)則規(guī)則):)()(cAxxA成立條件：成立條件：1) c是使A(c)為真的常量符號;),()(,)2acaBxxB則比如則在此之前也使用過該規(guī)若推理過程中3)A(x)中的自由變元只有x.例如：例如：設D為自然數集, F(x)表示“x是奇數”，G(x)表示“x是偶數”.)()

23、(是真命題則xxGxxF離離 散散 數數 學學 54但，若不注意使用條件，則有：)()()1 (xxGxxF前提引入)()2(xxF化簡，根據（1）)() 3(cFES規(guī)則，根據（2）)()4(xxG化簡，根據（1）)()5(cGES規(guī)則，根據（4）)()()6(cGcF合取，根據（3），（5）)()()7(xGxFxEG規(guī)則，根據（6）于是得出：)()()()(xGxFxxxGxxF（）違反了條件2）離離 散散 數數 學學 55例 1 證明：)()()()()()(xCxBxxAxcxxBxAx推理過程如下：)()() 1 (xBxAx前提引入)()()2(yByAUS規(guī)則，根據（1）)()

24、() 3(xAxcx前提引入)()()4(aAaCES規(guī)則，根據（3）)()5(aC化簡，根據（4）)()6(aA化簡，根據（4）)()7(aB假言推理，根據（2），（6）)()()8(aCaB合取，根據（5），（7）)()()9(xCxBxEG規(guī)則，根據（8）在推理過程中，y被指定為論域中的任一個體，a被指定為論域中的某一個體。對于(2)和(6)，在使用假言推理時，由于y是任一個體，因此，可以選為某一個體a，故得(7)。 離離 散散 數數 學學 56本例也可作如下推理：)()()1(xAxCx前提引入ES規(guī)則，根據（1）)()3(aA化簡，根據（2）)()()4(xBxAx前提引入)()()

25、5(aBaAUS規(guī)則，根據（4）)()6(aB假言推理，根據(3)，(5)()7(aC化簡，根據（2）)()()8(aCaB合取，根據（6），（7）)()()9(xCxBxEG規(guī)則，根據（8）)()()2(aAaC離離 散散 數數 學學 57例例 2 證明： 蘇格拉底三段論“凡人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的”。證明證明:結論: D(a)首先將命題符號化：M(x):x是人. D(x):x是要死的. a:蘇格拉底.)(),()(aMxDxMx前提:證明:)()() 1 (xDxMx)()()2(aDaM)() 3(aM)()4(aD前提引入US規(guī)則，（1）前提引入假言推理，（2）

26、，（3）離離 散散 數數 學學 58例例 3 有些病人相信所有的醫(yī)生，但是病人都不相信騙子。證明：醫(yī)生都不是騙子。 證明：v命題符號化： P(x):x是病人；D(x):x是醫(yī)生；Q(x):x是騙子；R(x,y):x相信y。v前提：x(P(x)y(D(y)R(x,y)， xy(P(x)Q(y)R(x,y)v結論：x(D(x)Q(x)v推理：離離 散散 數數 學學 591)x(P(x)y(D(y)R(x,y) 前提引入2)P(c)y(D(y)R(c,y) ES，(1)3)xy(P(x)Q(y)R(x,y) 前提引入4)y(P(c)Q(y)R(c,y) US，(3)5)P(c)Q(z)R(c,z)

27、US，(4)6)(P(c)Q(z)R(c,z) 蘊涵等值式，(5)7)P(c)Q(z)R(c,z) De Morgan律,(6)8)P(c)(Q(z)R(c,z) 蘊涵等值式，(7)9)P(c) 化簡，(2)10) Q(z)R(c,z) 析取三段論，(8)，(9)11) R(c,z)Q(z) 等值演算，(10)12) y(D(y)R(c,y) 化簡，(2)13) D(z)R(c,z) US，(12)14) D(z)Q(z) 假言三段論，(11)，(13)15) x(D(x)Q(x) UG，(14) 離離 散散 數數 學學 60例例 4：指出下面推理的錯誤：指出下面推理的錯誤1) x(F(x)G(x) 前提引入2) F(y)G(y) US，(1)3) xF(x) 前提引入4) F(y) ES，(3)5) G(y) 假言推理，(2),(4)6