高等數(shù)學(xué)-離散數(shù)學(xué)及其應(yīng)用-課件-第四章一階邏輯基本概念

1、1,主要內(nèi)容一階邏輯命題符號化 個體詞、謂詞、量詞 一階邏輯命題符號化一階邏輯公式及其解釋 一階語言 合式公式 合式公式的解釋 永真式、矛盾式、可滿足式,第四章 一階邏輯基本概念,2,4.1 一階邏輯命題符號化,個體詞——所研究對象中可以獨立存在的具體或抽象的客體 個體常項：具體的事務(wù)，用a, b, c等表示 個體變項：抽象的事物，用x, y, z等表示

2、 個體域(論域)——個體變項的取值范圍 有限個體域，如 {a, b, c}, {1, 2} 無限個體域，如 N, Z, R, … 全總個體域——由宇宙間一切事物組成,3,謂詞,謂詞——表示個體詞性質(zhì)或相互之間關(guān)系的詞 謂詞常項 如, F(a)：a是人 謂詞變項 如, F(x)：x具有性質(zhì)F n(n?1)元謂詞 一元謂詞(n

3、=1)——表示性質(zhì) 多元謂詞(n?2)——表示事物之間的關(guān)系 如, L(x,y)：x與 y 有關(guān)系 L，L(x,y)：x?y，… 0元謂詞——不含個體變項的謂詞, 即命題常項 或命題變項,4,量詞,量詞——表示數(shù)量的詞 全稱量詞?: 表示所有的 ?x : 對個體域中所有的x

4、 如, ?xF(x)表示個體域中所有的x具有性質(zhì)F ?x?yG(x,y)表示個體域中所有的x和y有關(guān)系G 存在量詞?: 表示存在, 有一個 ?x : 個體域中有一個x 如, ?xF(x)表示個體域中有一個x具有性質(zhì)F ?x?yG(x,y)表示個體域中存在x和y有關(guān)系G ?x?yG(x,y)表示對個體域中每一個x

5、都存在一個y使得 x和y有關(guān)系G ?x?yG(x,y)表示個體域中存在一個x使得對每一個y, x和y有關(guān)系G,5,實例1,,例1 用0元謂詞將命題符號化 (1) 墨西哥位于南美洲 (2) 是無理數(shù)僅當(dāng) 是有理數(shù) (3) 如果2>3，

6、則3<4,解：在命題邏輯中： (1) p, p為墨西哥位于南美洲（真命題） (2) p→q, 其中, p： 是無理數(shù), q： 是有理數(shù). 是假命題 (3) p?q, 其中, p：2>3, q：3<4. 是真命題,6,實例1解答,在一階邏輯中： (1) F(a)，其中，a：墨西哥，F(xiàn)(x)：x位于南美洲. (2) F( )?G( ),

7、 其中，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,實例2,例 2 在一階邏輯中將下面命題符號化 (1) 人都愛美 (2) 有人用左手寫字個體域分別為 (a) D為人類集合 (b) D為全總個體域,解 (a) (1) ?xG(x), G(x)：x愛美,(2) ?xH(x), H(

8、x)：x用左手寫字,(b) F(x)：x為人,(1) ?x(F(x)?G(x)),(2) ?x(F(x)?H(x)),說明: 1. 引入特性謂詞F(x) 2. (1),(2)是一階邏輯中的兩個“基本”公式,8,實例3,例3 在一階邏輯中將下面命題符號化 (1) 正數(shù)都大于負(fù)數(shù) (2) 有的無理數(shù)大于有的有理數(shù),解 注意：題目中沒給個體域，一律用全總個體域 (1) 令F(x)：x為正數(shù)，G

9、(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)),9,實例4,例4 在一階邏輯中將下面命題符號化 (1) 沒有不呼吸的人 (2) 不

10、是所有的人都喜歡吃糖,解 (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)),10,實例5,例5 設(shè)個體域為實數(shù)域, 將下面命題符號化 (1) 對每一個數(shù)x都存在一個數(shù)y使得x<y (2) 存在一個數(shù)x使得對每一個數(shù)y都有x<y

11、,解 L(x,y): x<y,(1) ?x?yL(x,y),注意: ?與?不能隨意交換顯然(1)是真命題, (2)是假命題,(2) ?x?yL(x,y),11,4.2 一階邏輯公式及解釋,定義4.1 設(shè)L是一個非邏輯符集合, 由L生成的一階語言L 的字母表包括下述符號：非邏輯符號 (1) 個體常項符號：a, b, c, …, ai, bi, ci, …, i ?1 (2) 函數(shù)符號：f,

12、 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)結(jié)詞符號：?, ?, ?, ?, ? (7) 括號與逗號：(, ), ，,12,一階語言L 的項與原子公式,定義4.2

13、 L 的項的定義如下：(1) 個體常項和個體變項是項.(2) 若?(x1, x2, …, xn)是n元函數(shù)符號，t1, t2, …, tn是 n個項， 則?(t1, t2, …, tn) 是項.(3) 所有的項都是有限次使用(1),(2)得到的 如, a, x, x+y, f(x), g(x,y)等都是項,定義4.3 設(shè)R(x1, x2, …, xn)是L 的n元謂詞符號，t1, t2, …, t

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

15、是合式公式，則?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 的公式,14,量詞的轄域,定義4.5 在公式 ?xA 和 ?xA 中，稱x為指導(dǎo)變元，A為相應(yīng)量詞的轄域. 在?x和 ?x的轄域中

16、，x的所有出現(xiàn)都稱為約束出現(xiàn)，A中不是約束出現(xiàn)的其他變項均稱為是自由出現(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)變元, 轄域為(F(x,y,z)??y(G(x,y)?H(x,y,z))). ?y中的y

17、是指導(dǎo)變元, 轄域為(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).,15,封閉的公式,定義4.6 若公式A中不含自由出現(xiàn)的個體變項，則稱A為封閉的公式，簡稱閉式.例如，?x?y(F(x)?G(y)?H(x,y)) 為閉式，而 ?x(F(x)?G(x,y)) 不是閉式,16,公式的解釋,,,,定義4.7 設(shè)L 是L生

18、成的一階語言, L 的解釋I由4部分組成： (a) 非空個體域 DI . (b) 對每一個個體常項符號a?L, 有一個 ?DI, 稱 為a在I 中的解釋. (c) 對每一個n元函數(shù)符號f?L, 有一個DI上的n元函數(shù) , 稱 為f在I中的解釋. (d) 對每一個n元謂詞符

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

20、寫出下列公式在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) 真值不定, 不是命題,18,公式的類型,定理4.1 閉式在任何解釋下都是命

21、題注意: 不是閉式的公式在解釋下可能是命題, 也可能不是命題. 定義4.8 若公式A在任何解釋下均為真, 則稱A為永真式(邏輯有效式). 若A在任何解釋下均為假, 則稱A為矛盾式(永假式). 若至少有一個解釋使A為真, 則稱A為可滿足式.幾點說明： 永真式為可滿足式，但反之不真 判斷公式是否是可滿足的(永真式, 矛盾式)是不可判定的,19,代換實例,定義4.9 設(shè)A0是含命題變項 p1, p2, …

22、, 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 重言式的代換實例都是永真式，矛盾式的代換實例都是矛盾式.,20,實例,例7 判斷下列公式的類型: (1) ?xF(x)?(?x?yG(x,y)??xF(x)),重言式 p?(q?p) 的代換實例，故為

23、永真式.,(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, 公式為假結(jié)論: 非永真式的可滿足式,21,第四章 習(xí)題課,主要內(nèi)容個體詞、謂詞、量詞一階邏輯

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

25、,1. 在分別取個體域為 (a) D1=N (b) D2=R (c) D3為全總個體域的條件下, 將下面命題符號化，并討論真值 (1) 對于任意的數(shù)x，均有,解 設(shè)G(x): (a) ?xG(x),(b) ?xG(x),(c) 又設(shè)F(x):x是實數(shù) ?x(F(x)?G(x)),真,真,假,24,練習(xí)1(續(xù)),解 設(shè)H(x)：x+7=5

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

27、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)),練習(xí)2,(4) 沒有不愛吃糖的人,(5) 任何兩個不同的人都不一樣高,(6) 不是所有的汽車都比所有的火車快,設(shè)F(x): x是人，G(x): x愛吃糖??x(F(x)??G

28、(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(F(x)?G(y)?H(x,y)) 或 ?x?y(F(x)?

29、G(y)??H(x,y)),27,練習(xí)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?y(x+2=y?y+2=x) 假,

30、28,練習(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)說明?與?不能隨意交換,29,練習(xí)4,4. 證明下面公式既不是永真式，也不是矛盾式:,(1) ?x(F(x)?G(x)),(2)

31、?x?y(F(x)?G(y)?H(x,y)),解釋1: D1=N, F(x):x是偶數(shù), G(x): x是素數(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 真,解釋2: D2=Z, F(x):x是偶數(shù)