一階邏輯基本概念謂詞邏輯(離散數(shù)學(xué))課件(PPT 49頁(yè))

1、 第四章一階邏輯基本概念（謂詞邏輯）1第1頁(yè)，共49頁(yè)。本章主要內(nèi)容4.1 一階邏輯命題符號(hào)化4.2 一階邏輯公式及解釋2第2頁(yè)，共49頁(yè)。4.1 一階邏輯命題符號(hào)化個(gè)體詞、謂詞、量詞的概念一階邏輯命題的符號(hào)化3第3頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念 定義：個(gè)體詞（個(gè)體）: 可以獨(dú)立存在的具體或抽象的客體。個(gè)體詞的基本概念例：我是老師。其中“我”就是個(gè)體詞。 張三比李四高。其中“張三”、“李四”都是個(gè)體詞。4第4頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念個(gè)體常項(xiàng)：具體的客體，用a, b, c表示。個(gè)體變項(xiàng)：抽象或泛指的事物，用x, y, z表示。 個(gè)體域（論域）: 個(gè)體變項(xiàng)的取值范圍。

2、例：x高于y。x，y都是個(gè)體變項(xiàng)。有限個(gè)體域即個(gè)體域是有限集合無(wú)限個(gè)體域即個(gè)體域是無(wú)窮集合全總個(gè)體域 宇宙間一切事物組成。5第5頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念謂詞的基本概念定義: 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞。例：張華是大學(xué)生。 李凱是大學(xué)生。是大學(xué)生例：張三比李四高。比高6第6頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念謂詞常項(xiàng)：表示具體性質(zhì)或關(guān)系 例：是大學(xué)生，記為F，F(xiàn)(張華)表示“張華是大學(xué)生”。謂詞變項(xiàng)：表示抽象及泛指的性質(zhì)或關(guān)系 例：具有性質(zhì)F，記為F， F(張華)：張華具有性質(zhì)F謂詞常項(xiàng)和變項(xiàng)都用大寫(xiě)字母表示。7第7頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念n元謂詞

3、(n2): 含有n個(gè)個(gè)體變項(xiàng)的謂詞。如：L(x,y)：xy，L是一個(gè)二元謂詞。一元謂詞: 只含有一個(gè)個(gè)體變項(xiàng)的謂詞。 如：F(x)：x是女孩。0元謂詞: 不含個(gè)體變項(xiàng)的謂詞。8第8頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念 如：上例二元謂詞L中的x,y代以個(gè)體“2”和“1”,則L(2,1)就是命題“21”。此時(shí)二元謂詞變成0元謂詞。 同理：一元謂詞F(x)中的x代以個(gè)體“小王”，則F(小王)就是命題“小王是女孩”。也是0元謂詞。謂詞邏輯包括命題邏輯。9第9頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念例1：用0元謂詞將下述命題符號(hào)化。 (1) 墨西哥位于南美洲在命題邏輯中, 設(shè) p: 墨西哥位于南

4、美洲符號(hào)化為 p, 該命題為真命題。 在一階邏輯中, 設(shè) a：墨西哥；F(x)：x位于南美洲； 符號(hào)化為F(a)10第10頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念(2) 是無(wú)理數(shù)僅當(dāng) 是有理數(shù)在一階邏輯中，設(shè)F(x): x是無(wú)理數(shù)；G(x): x是有理數(shù)符號(hào)化為在命題邏輯中,設(shè) p: 是無(wú)理數(shù);q: 是有理數(shù). 符號(hào)化為 p q, 這是假命題。11第11頁(yè)，共49頁(yè)。一、個(gè)體詞、謂詞、量詞的概念（3） 如果23，則33，q：3y，G(x,y)：x10 。19第19頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化 令 F(x): x是無(wú)理數(shù), G(y): y是有理數(shù), L(x,y)：xy x (F(x)

5、 y(G(y)L(x,y) （2）有的無(wú)理數(shù)大于有的有理數(shù)20第20頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化（3）沒(méi)有不犯錯(cuò)的人。設(shè)：P(x)：x是人； Q(x)：x犯錯(cuò)誤。21第21頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化 令 F(x): x是金屬，G(x): x是液體， L(x,y): x溶解在y中（4）任何金屬都可以溶解在某種溶液中。22第22頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化（5）某些人對(duì)所有的花粉都過(guò)敏。 令 F(x): x是人, G(y): y是花粉, L(x,y)：x對(duì)y過(guò)敏。23第23頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化（6）所有的學(xué)生都上課了，這是錯(cuò)的。 令 F(x): x

6、是學(xué)生, G(x): x上課了。 這句話相當(dāng)于“有些學(xué)生沒(méi)有上課”。 24第24頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化（7）不存在最大的整數(shù)。 令 F(x): x是整數(shù), L(x,y)：x比y大。 這句話相當(dāng)于：“任意一個(gè)整數(shù)，都存在比它大的整數(shù)”。25第25頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化 例4：（教材例4.5）將下列命題符號(hào)化（1）兔子比烏龜跑得快。（2）有的兔子比所有的烏龜跑得快。（3）并不是所有的兔子都比烏龜跑得快。（4）不存在跑得同樣快的兩只兔子。26第26頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化例5:設(shè)A(x):x能被3整除； B(x):x能被6整除.個(gè)體域?yàn)椋?,2,6,7,

7、12分析如下情況的真值。真假真真27第27頁(yè)，共49頁(yè)。二、一階邏輯中命題符號(hào)化 例6：考慮個(gè)體域?yàn)閷?shí)數(shù)域，則命題“對(duì)于 任意的x，都存在y，使得xy”應(yīng)該符號(hào)化 為下面的哪一種形式？ 令：L(x,y): x2, G(x): x1個(gè)體域N, F(x): x1, G(x): x2成真解釋 代入得A = x(x2x1)真命題成假解釋代入得A= x(x1 x2)假命題40第40頁(yè)，共49頁(yè)。三、公式的解釋對(duì)公式中的各個(gè)抽象符號(hào)給出如下解釋：（1）個(gè)體域D=N；（2）a=0（3）f(x,y)=x+y，g(x,y)=xy（4）F(x,y)：x=y例： 由于公式是抽象的符號(hào)串，若不對(duì)它們給以具體解釋，則公

8、式是沒(méi)有實(shí)在意義的。41第41頁(yè)，共49頁(yè)。三、公式的解釋 定義：解釋I由下面4部分組成： (a)非空個(gè)體域DI (b)DI中一些特定元素的集合 (c)DI上特定函數(shù)集合 (d)DI上特定謂詞的集合 42第42頁(yè)，共49頁(yè)。三、公式的解釋 例3 給定解釋I 如下: (a) 個(gè)體域 D=N（包括0） (b) (c) (d) 謂詞 說(shuō)明下列公式在 I 下的涵義,并討論真值。 43第43頁(yè)，共49頁(yè)。三、公式的解釋(1) xF( g(x,a), x) x(2x=x)(2) xy(F(f (x,a), y)F(f(y,a), x)xy(x+2=yy+2=x)(3) xF(f(x,x),g(x,x)x(

9、2x=x2)假命題假命題真命題44第44頁(yè)，共49頁(yè)。三、公式的解釋(5) xyzF(f(y,z),x)xyz (y+z=x)(4) xyzF(f(x,y),z)xyz (x+y=z)真命題假命題(6) x F(g(x,y),z)xy=z不是命題45第45頁(yè)，共49頁(yè)。三、公式的解釋 小結(jié)： (1)(5)中的公式都是閉式,在I下全是命題。 (6)與(7)中的公式都不是閉式,但(6)在該解釋下沒(méi)有確定的真值，而(7)的真值為真 。(7) xF(g (x,a), x)F(x,y) x(2x= x)(x=y)真命題閉式: 不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式。例： 定理：閉式在任何解釋下都是命題。46第46頁(yè)，共49頁(yè)。四、公式的類型永真式（邏輯有效式）：無(wú)成假解釋矛盾式（永假式）：無(wú)成真解釋可滿足式：至少有一個(gè)成真解釋47第47頁(yè)，共49頁(yè)。 例5：證明下面公式不是永真式。只要找到一個(gè)使公式成假的解釋就可以證明該公式不是永真式。設(shè)論域?yàn)檎麛?shù)集合，F(xiàn)(x,y):xy前件為：對(duì)任意整數(shù)x，存在整數(shù)y，使得xy。其真值為真。后件為：存在整數(shù)x，對(duì)任意的整數(shù)y都有xy。其真值為假。 所以在這樣的解釋下，公式為假，即不是永真式。48第