離散數(shù)學(xué)高教版第4章

1、1,主要內(nèi)容一階邏輯命題符號化 個(gè)體詞、謂詞、量詞 一階邏輯命題符號化一階邏輯公式及其解釋 一階語言 合式公式 合式公式的解釋 永真式、矛盾式、可滿足式,第四章 一階邏輯基本概念,2,4.1 一階邏輯命題符號化,個(gè)體詞——所研究對象中可以獨(dú)立存在的具體或抽象的客體 如 ：1、小王是程序猿。 3、x是有理數(shù)。 2、

2、 是無理數(shù)。 4、這輛汽車是那頭畫圖汪的。 個(gè)體常項(xiàng)：表示具體或特定的客體的個(gè)體詞，用a, b, c表示 個(gè)體變項(xiàng)：表示抽象或者泛指的個(gè)體詞，用x, y, z表示 個(gè)體域(論域)——個(gè)體變項(xiàng)的取值范圍 有限個(gè)體域，如 {a, b, c}, {1, 2} 無限個(gè)體域，如 N, Z, R, … 全總個(gè)體域——由宇宙間一切事物組成,3

3、,謂詞,謂詞——表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞，常用F,G，H等表示。 1） 是無理數(shù)。 “…是無理數(shù)“是謂詞，記為F， 整個(gè)陳述句表示為F( ). 2)x是有理數(shù)。 “…是有理數(shù)”是謂詞，記為G 整個(gè)陳述句表示為G(x) 3)小王與小李同歲。 “…與…有理數(shù)”是謂詞，記為H。 整

4、個(gè)陳述句表示為H(a,b).其中a表示小王,b表示小李 4）x與y具有關(guān)系L。,,4,謂詞常項(xiàng) 表示具體性質(zhì)或關(guān)系的謂詞。 如, F(a)：a是人 謂詞變項(xiàng) 表示抽象的或者泛指的性質(zhì)或關(guān)系。如, F(x)：x具有性質(zhì)F n（n?1）元謂詞 含有n(n?1)個(gè)個(gè)體變項(xiàng)x1, x2 ,…, xn 的謂詞P稱作n元謂詞，記為：P(x1, x2 ,…, xn ) 一元謂詞(n

5、=1)——表示性質(zhì), P(x1)表示x1具有性質(zhì)P 多元謂詞(n?2)——表示事物之間的關(guān)系，P(x1, x2 ,…, xn )表示x1, x2 ,…, xn 具有關(guān)系P。 如, L(x,y)：x與 y 有關(guān)系 L，L(x,y)：x?y，… 0元謂詞——不含個(gè)體變項(xiàng)的謂詞, 即命題常項(xiàng) 或命題變項(xiàng),5,實(shí)例1,,例1 將下列命題在一階邏輯中用0元謂詞將命題符號化，并討論他

6、們的真值。 (1) 只有2是素?cái)?shù)，4才是素?cái)?shù)。,在命題邏輯中符號化： p：4是素?cái)?shù), q:2是素?cái)?shù),符號化為： p→q,解：在一階邏輯中：設(shè)一元謂詞F(x)：x是素?cái)?shù)，命題可符號化為： F(4) →F(2) 命題為真。,,6,(2)如果5大于4，則4大于6.,在命題邏輯中符號化： p：5大于4, q:4大于6,命題符號化為： p→q,解：在一階邏輯中：設(shè)二元謂詞G(x,y

7、)：x>y，命題可符號化為： G(5,4) →G(4,6) 命題為假。,7,實(shí)例1,,練習(xí)：用0元謂詞將命題符號化 (1) 墨西哥位于南美洲 (2) 是無理數(shù)僅當(dāng) 是有理數(shù) (3) 如果2>3，則3<4,在一階邏輯中： (1) F(a)，其中，a：墨西哥，F(xiàn)(x)：x位于南美洲. (2) F( )?G( ),

8、 其中，F(xiàn)(x)：x是無理數(shù)，G(x)：x是有理數(shù) (3) F(2, 3)?G(3, 4)，其中，F(xiàn)(x, y)：x>y，G(x, y)：x<y,8,量詞,量詞——表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞 全稱量詞?: 日常生活中常用的”一切的”，“所有的”，“每一個(gè)”，“任意的”，“凡”，“都”等詞統(tǒng)稱為全體量詞， ?x : 對個(gè)體域中所有的x 如, ?xF(x)表示個(gè)體域中所有的

9、x具有性質(zhì)F ?x?yG(x,y)表示個(gè)體域中所有的x和y有關(guān)系G 存在量詞?: 表示存在, 有一個(gè)，有的，至少有一個(gè). ?x : 個(gè)體域中有一個(gè)x 如, ?xF(x)表示個(gè)體域中有一個(gè)x具有性質(zhì)F ?x?yG(x,y)表示個(gè)體域中存在x和y有關(guān)系G ?x?yG(x,y)表示對個(gè)體域中每一個(gè)x都存在一個(gè)y使得

10、 x和y有關(guān)系G ?x?yG(x,y)表示個(gè)體域中存在一個(gè)x使得對每一個(gè)y, x和y有關(guān)系G,9,實(shí)例2,例 2 在一階邏輯中將下面命題符號化 (1) 人都愛美 (2) 有人用左手寫字個(gè)體域分別為 (a) D為人類集合 (b) D為全總個(gè)體域,解 (a)

11、 (1) ?xG(x), G(x)：x愛美,(2) ?xG(x), G(x)：x用左手寫字,(b) F(x)：x為人，G(x)：x愛美,(1) ?x(F(x)?G(x)),(2) ?x(F(x)?G(x)),1. 引入特性謂詞F(x) 2. (1),(2)是一階邏輯中兩個(gè)“基本”公式,10,實(shí)例3,例3 在一階邏輯中將下面命題符號化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無理數(shù)大于有的有理數(shù),解 注意：題目中沒

12、給個(gè)體域，一律用全總個(gè)體域 (1) 令F(x)：x為正數(shù)，G(y)：y為負(fù)數(shù), L(x,y)：x>y,?x(F(x)??y(G(y)?L(x,y)))或者 ?x?y(F(x)?G(y)?L(x,y)),(2) 令F(x)：x是無理數(shù)，G(y)：y是有理數(shù)，L(x,y)：x>y,?x(F(x)??y(G(y)?L(x,y)))或者 ?x?y(F(x)?G(y)?L(x,y)),11,實(shí)例4,例4 在一

13、階邏輯中將下面命題符號化 (1) 沒有不呼吸的人 (2) 不是所有的人都喜歡吃糖,解 (1) F(x): x是人, G(x): x呼吸,??x(F(x)??G(x)),?x(F(x)?G(x)),(2) F(x): x是人, G(x): x喜歡吃糖,?x(F(x)??G(x)),??x(F(x)?G(x)),12,實(shí)例5,例5 設(shè)個(gè)體域?yàn)閷?shí)數(shù)域, 將下面命題符號化 (1) 對每一個(gè)數(shù)x都存在一個(gè)數(shù)y使得x<

14、;y (2) 存在一個(gè)數(shù)x使得對每一個(gè)數(shù)y都有x<y,解 L(x,y):x<y,(1) ?x?yL(x,y),注意: ?與?不能隨意交換顯然(1)是真命題, (2)是假命題,(2) ?x?yL(x,y),13,4.2 一階邏輯公式及解釋,定義4.1 設(shè)L是一個(gè)非邏輯符集合, 由L生成的一階語言L 的字母表包括下述符號：非邏輯符號 (1) 個(gè)體常項(xiàng)符號：a, b, c, …, ai, b

15、i, ci, …, i ?1 (2) 函數(shù)符號：f, g, h, …, fi, gi, hi, …, i ?1 (3) 謂詞符號：F, G, H, …, Fi, Gi, Hi, …, i ?1邏輯符號 (4) 個(gè)體變項(xiàng)符號：x, y, z, …, xi, yi, zi, …, i ?1 (5) 量詞符號：?, ? (6) 聯(lián)結(jié)詞符號：?, ?, ?, ?, ? (7) 括號與逗號：(, )

16、, ，,14,一階語言L 的項(xiàng)與原子公式,定義4.2 L 的項(xiàng)的定義如下：(1) 個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng).(2) 若?(x1, x2, …, xn)是任意的n元函數(shù)，t1, t2, …, tn是任意的 n個(gè)項(xiàng)，則?(t1, t2, …, tn) 是項(xiàng).(3) 所有的項(xiàng)都是有限次使用(1),(2)得到的 如, a, x, x+y, f(x), g(x,y)等都是項(xiàng),定義4.3 設(shè)R(x1, x2,

17、…, xn)是L 的任意n元謂詞，t1, t2, …, tn 是L 的任意n個(gè)項(xiàng)，則稱R(t1, t2, …, tn)是L 的原子公式. 如，F(xiàn)(x, y), F(f(x1, x2), g(x3, x4))等均為原子公式,15,定義4.4 L 的合式公式定義如下： (1) 原子公式是合式公式. (2) 若A是合式公式，則 (?A)也是合式公式 (3) 若A, B是合式公式，則(A?B), (A?B), (A?B

18、), (A?B)也是 合式公式 (4) 若A是合式公式，則?xA, ?xA也是合式公式 (5) 只有有限次地應(yīng)用(1)—(4)形成的符號串才是合式公式.合式公式簡稱公式 如, F(x), F(x)??G(x,y), ?x(F(x)?G(x)) ?x?y(F(x)?G(y)?L(x,y))等都是合式公式,一階語言L 的公式,16,封閉的公式,定義4.5 在公式 ?xA 和 ?xA 中，

19、稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域. 在?x和 ?x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項(xiàng)均稱為是自由出現(xiàn)的. 例如，?x(F(x,y)?G(x,z))， x為指導(dǎo)變元，(F(x,y)?G(x,z))為?x 的轄域，x的兩次出現(xiàn)均為約束出現(xiàn)，y與 z 均為自由出現(xiàn)又如, ?x(F(x,y,z)??y(G(x,y)?H(x,y,z))), ?x中的x是指導(dǎo)變元, 轄域?yàn)?F(x,y,z)??y(G

20、(x,y)?H(x,y,z))). ?y中的y是指導(dǎo)變元, 轄域?yàn)?G(x,y)?H(x,y,z)). x的3次出現(xiàn)都是約束出現(xiàn), y的第一次出現(xiàn)是自由出現(xiàn), 后2次是約束出現(xiàn), z的2次出現(xiàn)都是自由出現(xiàn),17,封閉的公式,定義4.6 若公式A中不含自由出現(xiàn)的個(gè)體變項(xiàng)，則稱A為封閉的公式，簡稱閉式.例如，?x?y(F(x)?G(y)?H(x,y)) 為閉式，而 ?x(F(x)?G(x,y)) 不是閉式,18,

21、公式的解釋,,,定義4.7 設(shè)L 是L生成的一階語言, L 的解釋I由4部分組成： (a) 非空個(gè)體域 DI . (b) 對每一個(gè)個(gè)體常項(xiàng)符號a?L, 有一個(gè) ?DI, 稱 為a在I 中的解釋. (c) 對每一個(gè)n元函數(shù)符號f?L, 有一個(gè)DI上的n元函數(shù) , 稱 為f在I中

22、的解釋. (d) 對每一個(gè)n元謂詞符號F?L, 有一個(gè)DI上的n元謂詞常項(xiàng) , 稱 為F在I中的解釋.,設(shè)公式A, 取個(gè)體域DI , 把A中的個(gè)體常項(xiàng)符號a、函數(shù)符號f、謂詞符號F分別替換成它們在I中的解釋 、 、 , 稱所得到的公式A?為A在I下的解釋, 或A在I下被解釋成A?.,19,實(shí)例,,,,例6 給定解釋 I 如下： (a) 個(gè)體域 D=R (b) (c

23、) (d) 寫出下列公式在I下的解釋, 并指出它的真值. (1) ?xF(f(x,a),g(x,a)),?x(x+0=x?0) 真,(2) ?x?y(F(f(x,y),g(x,y))?F(x,y)),?x?y(x+y=x?y?x=y) 假,(3) ?xF(g(x,y),a),?x(x?y=0) 真值不定, 不是命題,20,公式的

24、類型,定理4.1 閉式在任何解釋下都是命題注意: 不是閉式的公式在解釋下可能是命題, 也可能不是命題. 定義4.8 若公式A在任何解釋下均為真, 則稱A為永真式(邏輯有效式). 若A在任何解釋下均為假, 則稱A為矛盾式(永假式). 若至少有一個(gè)解釋使A為真, 則稱A為可滿足式.幾點(diǎn)說明： 永真式為可滿足式，但反之不真 判斷公式是否是可滿足的(永真式, 矛盾式)是不可判定的,21,代換實(shí)例,定義4.9

25、 設(shè)A0是含命題變項(xiàng) p1, p2, …, pn的命題公式，A1, A2, …, An是n個(gè)謂詞公式，用Ai (1?i?n) 處處代替A0中的pi，所得公式A稱為A0的代換實(shí)例.例如， F(x)?G(x), ?xF(x)??yG(y)等都是p?q的代換實(shí)例.定理4.2 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式.,22,實(shí)例,例7 判斷下列公式中，哪些是永真式，哪些是矛盾式？ (1) ?xF(x)?(?x?yG(

26、x,y)??xF(x)),重言式 p?(q?p) 的代換實(shí)例，故為永真式.,(2) ?(?xF(x)??yG(y))??yG(y),矛盾式 ?(p?q)?q 的代換實(shí)例，故為永假式.,(3) ?x(F(x)?G(x)),解釋I1: 個(gè)體域N, F(x):x>5, G(x): x>4, 公式為真 解釋I2: 個(gè)體域N, F(x):x<5, G(x):x<4, 公式為假結(jié)論: 非永真式的可滿

27、足式,23,第四章 習(xí)題課,主要內(nèi)容個(gè)體詞、謂詞、量詞一階邏輯命題符號化一階語言L 項(xiàng)、原子公式、合式公式公式的解釋 量詞的轄域、指導(dǎo)變元、個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn)、閉式、解釋公式的類型 永真式(邏輯有效式)、矛盾式(永假式)、可滿足式,24,基本要求,準(zhǔn)確地將給定命題符號化 理解一階語言的概念 深刻理解一階語言的解釋 熟練地給出公式的解釋 記住閉式的性質(zhì)并能應(yīng)用它 深刻理解永真式、矛盾

28、式、可滿足式的概念, 會判斷簡 單公式的類型,25,練習(xí)1,1. 在分別取個(gè)體域?yàn)?(a) D1=N (b) D2=R (c) D3為全總個(gè)體域的條件下, 將下面命題符號化，并討論真值 (1) 對于任意的數(shù)x，均有,解 設(shè)G(x): (a) ?xG(x),(b) ?xG(x),(c) 又設(shè)F(x):x是實(shí)數(shù) ?x(F(x)?G(x)),真,真,

29、假,26,練習(xí)1(續(xù)),解 設(shè)H(x)：x+7=5 (a) ?xH(x),,(2) 存在數(shù)x，使得 x+7=5,(b) ?xH(x),(c) 又設(shè)F(x)：x為實(shí)數(shù) ?x(F(x)?H(x)),本例說明：不同個(gè)體域內(nèi)，命題符號化形式可能不同（也可能相同），真值可能不同（也可能相同）.,真,真,假,27,練習(xí)2,2. 在一階邏輯中將下列命題符號化 (1) 大熊貓都可愛,(2) 有人愛發(fā)脾氣,

30、(3) 說所有人都愛吃面包是不對的,設(shè)F(x): x為大熊貓，G(x): x可愛 ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛發(fā)脾氣 ?x(F(x)?G(x)),設(shè)F(x): x是人，G(x): x愛吃面包 ??x(F(x)?G(x)) 或 ?x(F(x)??G(x)),28,練習(xí)2,(4) 沒有不愛吃糖的人,(5) 任何兩個(gè)不同的人都不一樣高,(6) 不是所有的汽車都比所有的火車快

31、,設(shè)F(x): x是人，G(x): x愛吃糖??x(F(x)??G(x)) 或 ?x(F(x)?G(x)),設(shè)F(x):x是人, H(x,y), x與y相同, L(x,y): x與y一樣高 ?x(F(x)??y(F(y)??H(x,y)??L(x,y))) 或 ?x?y(F(x)?F(y)??H(x,y)??L(x,y)),設(shè)F(x):x是汽車, G(y):y是火車, H(x,y):x比y快 ??x?y

32、(F(x)?G(y)?H(x,y)) 或 ?x?y(F(x)?G(y)??H(x,y)),29,練習(xí)3,?x(2x=x) 假,,3. 給定解釋 I 如下: (a) 個(gè)體域D=N (b) =2 (c) (d) 說明下列公式在 I 下的涵義,并討論真值 (1) ?xF(g(x,a),x),(2) ?x?y(F(f(x,a),y)?F(f(y,a),x)),?x

33、?y(x+2=y?y+2=x) 假,30,練習(xí)3,(3) ?x?y?zF(f(x,y),z),,(5) ?xF(f(x,x),g(x,x)),(4) ?x?y?zF(f(y,z),x),?x?y?z(y+z=x) 假,?x?y?z(x+y=z) 真,?x(x+x=x?x) 真,(3),(4)說明?與?不能隨意交換,31,練習(xí)4,4. 證明下面公式既不是

34、永真式，也不是矛盾式:,(1) ?x(F(x)?G(x)),(2) ?x?y(F(x)?G(y)?H(x,y)),解釋1: D1=N, F(x):x是偶數(shù), G(x): x是素?cái)?shù), 真,解釋2: D2=N, F(x):x是偶數(shù), G(x): x是奇數(shù), 假,解釋1: D1=Z, F(x):x是正數(shù), G(x): x是負(fù)數(shù), H(x,y):x>y

35、 真,解釋2: D2=Z, F(x):x是偶數(shù), G(x): x是奇數(shù), H(x,y):x>y 假,32,練習(xí)5,5. 證明下列公式為永真式: (1) (?xF(x)??yG(y))??xF(x)??yG(y),(2) ?x(F(x)?(F(x)?G(x))),(A?B)?A?B的代換實(shí)例,設(shè)I是任意的一個(gè)解釋, 對每一個(gè)x?DI, F(x)?(F(