離散數學高教版第4章

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

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

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

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

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

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

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

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

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

10、 x和y有關系G ?x?yG(x,y)表示個體域中存在一個x使得對每一個y, x和y有關系G,9,實例2,例 2 在一階邏輯中將下面命題符號化 (1) 人都愛美 (2) 有人用左手寫字個體域分別為 (a) D為人類集合 (b) D為全總個體域,解 (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)是一階邏輯中兩個“基本”公式,10,實例3,例3 在一階邏輯中將下面命題符號化 (1) 正數都大于負數 (2) 有的無理數大于有的有理數,解 注意：題目中沒

12、給個體域，一律用全總個體域 (1) 令F(x)：x為正數，G(y)：y為負數, 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是無理數，G(y)：y是有理數，L(x,y)：x>y,?x(F(x)??y(G(y)?L(x,y)))或者 ?x?y(F(x)?G(y)?L(x,y)),11,實例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,實例5,例5 設個體域為實數域, 將下面命題符號化 (1) 對每一個數x都存在一個數y使得x<

14、;y (2) 存在一個數x使得對每一個數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 設L是一個非邏輯符集合, 由L生成的一階語言L 的字母表包括下述符號：非邏輯符號 (1) 個體常項符號：a, b, c, …, ai, b

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

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

17、…, xn)是L 的任意n元謂詞，t1, t2, …, tn 是L 的任意n個項，則稱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) 只有有限次地應用(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為指導變元，A為相應量詞的轄域. 在?x和 ?x的轄域中，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項均稱為是自由出現(xiàn)的. 例如，?x(F(x,y)?G(x,z))， x為指導變元，(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是指導變元, 轄域為(F(x,y,z)??y(G

20、(x,y)?H(x,y,z))). ?y中的y是指導變元, 轄域為(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)的個體變項，則稱A為封閉的公式，簡稱閉式.例如，?x?y(F(x)?G(y)?H(x,y)) 為閉式，而 ?x(F(x)?G(x,y)) 不是閉式,18,

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

22、的解釋. (d) 對每一個n元謂詞符號F?L, 有一個DI上的n元謂詞常項 , 稱 為F在I中的解釋.,設公式A, 取個體域DI , 把A中的個體常項符號a、函數符號f、謂詞符號F分別替換成它們在I中的解釋 、 、 , 稱所得到的公式A?為A在I下的解釋, 或A在I下被解釋成A?.,19,實例,,,,例6 給定解釋 I 如下： (a) 個體域 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為矛盾式(永假式). 若至少有一個解釋使A為真, 則稱A為可滿足式.幾點說明： 永真式為可滿足式，但反之不真 判斷公式是否是可滿足的(永真式, 矛盾式)是不可判定的,21,代換實例,定義4.9

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

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

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

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

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

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

31、,設F(x): x是人，G(x): x愛吃糖??x(F(x)??G(x)) 或 ?x(F(x)?G(x)),設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)),設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,練習3,?x(2x=x) 假,,3. 給定解釋 I 如下: (a) 個體域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,練習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,練習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是偶數, G(x): x是素數, 真,解釋2: D2=N, F(x):x是偶數, G(x): x是奇數, 假,解釋1: D1=Z, F(x):x是正數, G(x): x是負數, H(x,y):x>y

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