第二章1一階邏輯基本概念.ppt

1、1,在命題邏輯中，把命題分解到原子命題為止，認(rèn)為原子命題是不能再分解的，僅僅研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理。這樣，有些推理用命題邏輯就難以確切地表示出來。例如，著名的亞里士多德三段論蘇格拉底推理：,退出,2,所有的人都是要死的， 蘇格拉底是人， 所以蘇格拉底是要死的。 根據(jù)常識，認(rèn)為這個推理是正確的。但是，若用命題邏輯來表示，設(shè)P、Q和R分別表示這三個原子命題，則有 P，QR,3,然而，(PQ)R并不是永真式，故上述推理形式又是錯誤的。一個推理，得出矛盾的結(jié)論，問題在哪里呢? 問題就在于這類推理中，各命題之間的邏輯關(guān)系不是體現(xiàn)在原子命題之間，而是體現(xiàn)在構(gòu)成原子命題的內(nèi)部

2、成分之間，即體現(xiàn)在命題結(jié)構(gòu)的更深層次上。對此，命題邏輯是無能為力的。,4,命題邏輯的局限性,單用一個字母表示一個命題，描述不深刻，揭示不出原子命題內(nèi)部的含義； 命題演算對命題中量的概念無法表示。 有些簡單的推理問題，在命題邏輯中無法解決；問題出在各命題之間的邏輯關(guān)系不是體現(xiàn)在簡單命題之間，而是體現(xiàn)在構(gòu)成簡單命題的內(nèi)部成分之間，所以在必要對簡單命題作進(jìn)一步細(xì)分。 在研究某些推理時(shí)，對原子命題進(jìn)一步分析出其中的個體詞，謂詞和量詞，研究它們的形式結(jié)構(gòu)的邏輯關(guān)系、正確的推理形式和規(guī)則，這些正是謂詞邏輯（或稱為一階邏輯）的基本內(nèi)容。,5,2.1一階邏輯基本概念 2.2一階邏輯合式公式及解釋 2.3一階邏

3、輯等值式,第二章 一階(謂詞)邏輯,6,2.1一階邏輯基本概念 （個體詞、謂詞和量詞）,在命題邏輯中，命題是具有真假意義的陳述句。從語法上分析，一個陳述句由主語和謂語兩部分組成。在一階邏輯中，為揭示命題內(nèi)部結(jié)構(gòu)及其不同命題的內(nèi)部結(jié)構(gòu)關(guān)系，就按照這兩部分對命題進(jìn)行分析，并且把主語稱為個體詞或客體，把謂語稱為謂詞。,7,例如：吳華是大學(xué)生，用P表示， 李明是大學(xué)生，用Q表示。 “是大學(xué)生”用A（x）表示：x是大學(xué)生，命題符號含有個體詞變量。 a表示吳華，A（a）表示吳華是大學(xué)生。 b表示李明，A（b）表示李明是大學(xué)生。 相當(dāng)于“是大學(xué)生”，用A（）來表示，這就是謂詞。,8,例：張三比李四高， 用H

4、（x,y）表示x比y高。 a:張三b:李四 H（a,b）：張三比李四高 H（b,a）：李四比張三高 x,y,a,b表示個體，H（ ,）是謂詞，這個謂詞涉及了兩個個體，是二元謂詞。,9,.個體詞、謂詞和命題的謂詞形式 定義2.1.1 在原子命題中，所描述的對象稱為個體詞；用以描述個體詞的性質(zhì)或個體詞間關(guān)系的部分，稱為謂詞。 個體詞，是指可以獨(dú)立存在的事物，它可以是具體的，也可以是抽象的，如張明，計(jì)算機(jī)，精神等。表示具體或特定的客體的個體詞，稱為個體常元，以a，b，c或帶下標(biāo)的ai，bi，ci表示；表示抽象或泛指的個體詞，稱為個體變元，以x，y，z或xi，yi，zi表示。,10,個體域：個體變項(xiàng)的

5、取值范圍。 （分有限集合和無限集合） 全總個體域：由宇宙間的一切事物組成。,11,謂詞，當(dāng)與一個個體相聯(lián)系時(shí)，它刻劃了個體性質(zhì)；當(dāng)與兩個或兩個以上個體相聯(lián)系時(shí)，它刻劃了個體之間的關(guān)系。 表示具體性質(zhì)或關(guān)系的謂詞 ，稱為謂詞常元；表示抽象或泛指的性質(zhì)或關(guān)系的謂詞 ，稱為謂詞變元，都用大寫英文字母，如P，Q，R，或其帶上、下標(biāo)來表示。,12,例如，在命題“張明是位大學(xué)生”中，“張明”是個體，“是位大學(xué)生”是謂詞，它刻劃了“張明”的性質(zhì)。 設(shè)S(x)：x是位大學(xué)生，c：張明，則“張明是位大學(xué)生”可表示為S(c)，或者寫成S(c)：張明是位大學(xué)生。 又如，在命題“武漢位于北京和廣州之間”中，武漢、北京

6、和廣州是三個個體，而“位于和之間”是謂詞，它刻劃了武漢、北京和廣州之間的關(guān)系。 設(shè)P(x,y,z)：x位于y和z之間，a：武漢，b：北京，c：廣州，則P(a，b，c)：武漢位于北京和廣州之間。,13,注：區(qū)分：謂詞與運(yùn)算。 雖都是自變量取自個體域上的函數(shù)，但函數(shù)值不同，運(yùn)算的函數(shù)值是個體，謂詞的函數(shù)值是真值。,14,定義2.1.2 一個原子命題用一個謂詞(如P)和n個有次序的個體常項(xiàng)(如a1，a2，an)表示成P(a1，a2，an)，稱它為該原子命題的謂詞形式或命題的謂詞形式。 應(yīng)注意的是，命題的謂詞形式中的個體出現(xiàn)的次序影響命題的真值，不是隨意變動，否則真值會有變化。如上述例子中，P(b,a

7、,c)是假。,15,.原子謂詞公式 原子命題的謂詞形式還可以進(jìn)一步加以抽象，比如在謂詞右側(cè)的圓括號內(nèi)的n個個體常項(xiàng)被替換成個體變項(xiàng)，如x1,x2,xn，這樣便得了一種關(guān)于命題結(jié)構(gòu)的新表達(dá)形式，稱之為n元原子謂詞。 定義2.1.3 由一個謂詞(如P)和n個體變項(xiàng)(如x1，x2，xn)組成的P(x1，x2，xn)，稱它為n元原子謂詞或n元命題函數(shù)，簡稱n元謂詞。而個體變項(xiàng)的論述范圍，稱為個體域或論域。,16,當(dāng)n=1時(shí)，稱一元謂詞；當(dāng)n=2時(shí)，稱為二元謂詞，。特別地，當(dāng)n=0，稱為零元謂詞。零元謂詞是命題，這樣命題與謂詞就得到了統(tǒng)一。,17,n元謂詞不是命題，只有其中的個體變項(xiàng)用特定個體或個體常項(xiàng)

8、替代時(shí)，才能成為一個命題。但個體變項(xiàng)在哪些論域取特定的值，對命題的真值極有影響。 例如，令S(x)：x是大學(xué)生。 若x的論域?yàn)槟炒髮W(xué)的計(jì)算機(jī)系中的全體同學(xué)，則S(x)是真的； 若x的論域是某中學(xué)的全體學(xué)生，則S(x)是假的； 若x的論域是某劇場中的觀眾，且觀眾中有大學(xué)生也有非大學(xué)生的其它觀眾，則S(x)是真值是不確定的。,18,通常，把一個n元謂詞中的每個個體的論域綜合在一起作為它的論域，稱為n元謂詞的全總論域。定義了全總論域，為深入研究命題提供了方便。當(dāng)一個命題沒有指明論域時(shí)，一般都從全總論域作為其論域。而這時(shí)又常常要采用一個謂詞如P(x)來限制個體變項(xiàng)x的取值范圍，并把P(x)稱為特性謂詞

9、。,19,.量詞 利用n元謂詞和它的論域概念，有時(shí)還是不能用符號來很準(zhǔn)確地表達(dá)某些命題，例如S(x)表示x是大學(xué)生，而x的個體域?yàn)槟硢挝坏穆毠ぃ敲碨(x)可表示某單位職工都是大學(xué)生，也可表示某單位有一些職工是大學(xué)生，為了避免理解上的歧義，在一階邏輯中，需要引入用以刻劃“所有的”、“存在一些”等表示不同數(shù)量的詞，即量詞，其定義如下：,20,定義2.1.4 符號稱為全稱量詞符，用來表達(dá)“對所有的”、“每一個”、“對任何一個”、“一切”等詞語；x稱為全稱量詞，稱x為指導(dǎo)變項(xiàng)。 符號稱為存在量詞符，用來表達(dá)“存在一些”、“至少有一個”、“對于一些”、“某個”等詞語；x稱為存在量詞，x稱為指導(dǎo)變項(xiàng)。,

10、21,*符號!稱為存在唯一量詞符，用來表達(dá)“恰有一個”、“存在唯一”等詞語；!x稱為存在唯一量詞，稱x為指導(dǎo)變項(xiàng)。 全稱量詞、存在量詞、存在唯一量詞統(tǒng)稱量詞。量詞記號是由邏輯學(xué)家Fray引入的，有了量詞之后，用邏輯符號表示命題的能力大大加強(qiáng)了。,22,例 試用量詞、謂詞表示下列命題： 所有大學(xué)生都熱愛祖國； 每個自然數(shù)都是實(shí)數(shù)； 一些大學(xué)生有遠(yuǎn)大理想； 有的自然數(shù)是素?cái)?shù)。,23,解 令S(x)：x是大學(xué)生，L(x)：x熱愛祖國，N(x)：x是自然數(shù)，R(x)：x是實(shí)數(shù)，I(x)：x有遠(yuǎn)大理想，P(x)：x是素?cái)?shù)。 則例中各命題分別表示為： (x)(S(x)L(x) (x)(N(x)R(x) (

11、x)(S(x)I(x) (x)(N(x)P(x),24,在該例的解答中，由于命題中沒有指明個體域，這便意味著各命題是在全總論域中討論，因而都使用了特性謂詞，如S(x)、N(x)。 注：量詞與特性謂詞的搭配還有一定規(guī)律，即全稱量詞后跟一個蘊(yùn)含式，而特性謂詞作為其前件出現(xiàn)；存在量詞后跟一個合取式，特性謂詞作為一個合取項(xiàng)出現(xiàn)。 說明：命題符號化之前，必須明確個體域的范圍。,25,如果在解答時(shí)，指明了個體域，便不用特性謂詞，例如在、中令個體域?yàn)槿w大學(xué)生，則可符號化為： (x)L(x) (x)I(x) 在和中的個體域?yàn)槿孔匀粩?shù)，則可符號化為： (x)R(x) (x)P(x),26,思考： 如何將“沒

12、有不吃飯的人.”在一階邏輯中符號化？ 解：M(x):x是人. F(x):x吃飯. (1)(x)(M(x)F(x) (2)(x)(M(x)F(x),27,（5）所有的正數(shù)均可開方。 解： 1.若個體域?yàn)槿w正實(shí)數(shù)R+，S（X）：X可以開方， 則命題符號化為：xS（x） 2.若個體域?yàn)槿w實(shí)數(shù)集R，G（x , y）：xy， 則命題符號化為：x(G(x , 0） S(x) 3.若個體域?yàn)槿倐€體域D, R(x): x是實(shí)數(shù)，則符號化為： x(R(x)G(x , 0) S(x),28,注： 1)使用時(shí)，特性謂詞后用 ，即(x)(A(x)B(x)表示對所有具有性質(zhì)A的x，都具有性質(zhì)B； 2)使用時(shí)，特性

13、謂詞后用, 即(x)(A(x)B(x)表示存在著x，具有性質(zhì)A且具有性質(zhì)B； 在全總個體域討論某類事物需引入特性謂詞； 全稱量詞和存在量詞的意義隨個體域的不同而不同。,29,謂詞前加上了量詞，稱為謂詞的量化。若一個謂詞中所有個體變項(xiàng)都量化了，則該謂詞就變成了命題。這是因?yàn)樵谥^詞被量化后，可以在整個個體域中考慮命題的真值了。,這如同數(shù)學(xué)中的函數(shù)f(x)， 的值是不確定的，但 可確定其值。,30,含量詞的謂詞的真值規(guī)定 說明：不含量詞的謂詞公式G（x），它不是命題，而是命題函數(shù)，其真值依賴于x從個體域中取的個體詞的不同而不同。 例：D表示某班全體學(xué)生，G（x）表示x是男生。 則G（李剛）是真，而G

14、（王芳）是假。 而 xG（x）與xG（x）是命題了，x僅是一個“指導(dǎo)變項(xiàng)” xG（x）與 yG（y）意義完全相同。 xG（x）：全班每個人均是男生。 xG（x）：全班存在一個人或（一部分人）是男生。 含量詞的謂詞公式的真值不再依賴于x的選取了。,31,（1） xG（x）的真值規(guī)定 xG（x）的命題是“對任意xD，均有G（x）” xG（x）的真值為1，當(dāng)且僅當(dāng)，對一切xD，G（x）真 值均為1； xG（x）的真值為0，當(dāng)且僅當(dāng)，存在x0D， G（x0）真 值為0。,32,（2） xG（x）的真值規(guī)定 xG（x）的命題是“存在一個x0D，使得G（x0）成立” xG（x）的真值為1，當(dāng)且僅當(dāng)存在x0D，G（x0）的真值為1。 xG（x）的真值為0，當(dāng)且僅當(dāng)，對一切xD，G（x）的真值為0。,33,注：對于一個謂詞，如其每個變量均在量詞的管轄下，則該謂詞不是命題函數(shù)，而是命題了，它有確定的真值了。（閉式） 量化命題的真假與論域有關(guān)，可借助循環(huán)與搜索來思考。 (1)如果D是有限集,謂詞公式中的量詞可以用邏輯聯(lián)結(jié)