【正文】 如果前提中既有存在量詞公式，又有全稱量詞公式，應(yīng)先消去存在量詞公式中的量詞以避免上述錯(cuò)誤。 全稱量詞引入規(guī)則 (U+規(guī)則 )： A(y) ? (?x)A(x) 要求： (1) y在 A(y)中自由出現(xiàn)，且 y取任何值時(shí) A均為真 ； (2) 取代 y的 x不能在 A(y)中約束出現(xiàn) 。 二、 常見等值式的應(yīng)用 (前束范式 ) 解 : ( ?xP(x)??yR(y))??xF(x) ? (?xP(x)??yR(y)) ??zF(z) (1) 更換變元符號 ? ?x?y?z((P(x) ? R(y)) ? F(z)) (2) 擴(kuò)大作用域 二、常見等值式的應(yīng)用 (前束范式 ) 例 求下列合式公式的前束范式 (1) (?x)P(x) ? ? (?x)Q(x) 解： (?x)P(x) ? ? (?x)Q(x) ? (?x)P(x) ?(?x) ? Q(x) ? (?x)(P(x) ?? Q(x)) 二、常見等值式的應(yīng)用 (前束范式 ) 例 求下列合式公式的前束范式 (2) (?x)P(x)? ? (?x)Q(x) 解： (?x)P(x)? ? (?x)Q(x) ? (?x)P(x)?(?x) ? Q(x) ? (?x)P(x)?(?y) ? Q(y) ? (?x)(?y)(P(x)? ? Q(y)) 二、常見等值式的應(yīng)用 (前束范式 ) (3) (?x)P(x)?(?x)Q(x) ? (?x)P(x) ?(?y)Q(y) ? (?x)(?y)(P(x) ? Q(y)) 二、常見等值式的應(yīng)用 (前束范式 ) (4) (?x)P(x)?(?x)Q(x) ? (?x)P(x) ?(?y)Q(y) ? (?x)(?y)(P(x) ? Q(y)) 例 求下列合式公式的前束范式 例 求下列合式公式的前束范式 (5) (?xF(x， y) ? ?yG(y)) ? ?xH(x， y) 二、 常見等值式的應(yīng)用 (前束范式 ) ?(?xF(x， z) ? ?yG(y)) ? ?xH(x， z) ?(?xF(x， z) ? ?yG(y)) ? ?uH(u， z) ??x?y(F(x， z) ? G(y))? ?uH(u， z) ? ?x ?y ?u((F(x， z) ? G(y))? H(u， z) 前束合取范式： 前束范式 (?x)P(x)的命題公式部分即 P(x)為合取范式。 一階邏輯等值式及前束范式 一、謂詞演算中常見等值式： (I) 命題公式的推廣 24個(gè)常用的命題演算等值式及其代換可推廣到謂詞演算中使用 ,如 2. (?x)P(x)?(?y)R(x,y) ? ? (? (?x)P(x) ? ? (?y)R(x, y)) 3. (?x)H(x,y)?? (?x)H(x,y)?F 1. (?x)(P(x)?Q(x))?(?x)(? P(x)?Q(x)) (Ⅱ ) 量詞否定等值式 (量詞轉(zhuǎn)換律 ) ? (?x)P(x) ? (?x)? P(x) ? (?x)P(x) ? (?x)? P(x) 實(shí)例： “ 不是所有人今天都來上課 ” ? “ 存在一些人今天沒來上課 ” “ 沒有一個(gè)人今天來上課 ” ? “ 所有的人今天都沒來上課 ” 。 (2 解： p ? (q ? p)是重言式，所以 (2)為邏輯有效式。 G(x,y)為 G(i， j)=1 ， i, j=2,3。0, x) 2022/8/21 離散數(shù)學(xué) 45 解：在解釋 N 下， (2) ? ? x ?y (F (x, y) ? F (y, x)) 例 8：給定解釋 N 如下： (a) DN 為自然數(shù)集合； (b) DN 中特定元素 a = 0； (c) DN 上特定函數(shù) f(x , y) = x + y ， g (x, y) = x 在整個(gè)公式中， x約束出現(xiàn) 3次，自由出現(xiàn) 1次 ，y約束出現(xiàn) 1次，自由出現(xiàn) 1次 ， z自由出現(xiàn) 1次。 在作用域中 ， x的一切出現(xiàn)為 約束出現(xiàn) ， 非約束出現(xiàn)的其它變元叫 自由出現(xiàn)變元 。 解： (1) 設(shè) R(x)： x是實(shí)數(shù)， Q(x)： x是有理數(shù) 對應(yīng)謂詞公式： ? (?x)(R(x)?Q(x)) 二、應(yīng)用 或： (?x)(R(x) ? ? Q(x)) 解： 設(shè) F(x)： x犯錯(cuò)誤， M(x)： x是人 對應(yīng)謂詞公式： ? (?x)(M(x) ? ? F(x)) 或： (?x)(M(x) ? F(x)) 解： F(x,y)： x都有 y， M(x)： x是人， G(y)： y是缺點(diǎn) 對應(yīng)的謂詞公式： (?x)(?y)(M(x)?(G(y)?F(x,y))) (3) 每個(gè)人都有一些缺點(diǎn) 。 2. 如沒有事先給出個(gè)體域 ,都應(yīng)以全總個(gè)體域?yàn)閭€(gè)體域。 (2) 有些人活百歲以上 。 謂詞變項(xiàng) ：表示抽象的或泛指的性質(zhì)或關(guān)系的謂詞，也用大寫字母 F， G， …… ， 表示。 。 q: 蘇格拉底是人 。 r: 蘇格拉底是要死的 . 由上述文字構(gòu)造的命題邏輯推理結(jié)構(gòu)為 : (p ? q)? r 可知 : (p ? q)? r不是一個(gè)重言式 ,因此 ,按命題邏輯的方法 ,無法證明上述問題 . 為了在命題演算中 ， 反映命題的內(nèi)在聯(lián)系 ， 常常要將簡單命題分解成 個(gè)體詞 、 謂詞 、 量詞 等 ， 并對它們的形式結(jié)構(gòu)及邏輯關(guān)系加以研究 ， 總結(jié)出正確的推理形式和規(guī)則 ， 這就是本章一階邏輯要研究的內(nèi)容 。2如：李明、自然數(shù)、 2如： (1) 是無理數(shù) (性質(zhì) ) (2) 小李 比 小趙 高 2厘米 (關(guān)系 ) 簡單命題總可以被分解成 個(gè)體詞 和 謂詞 兩部分。 一般根據(jù)上、下文區(qū)分常項(xiàng)與變項(xiàng)。 考慮以下形式命題的符號化 : 量 詞 表示數(shù)量的詞，分 全稱量詞 與 存在量詞 。 3. 在引入特性謂詞后，引入全稱量詞與存在量詞符號化 的形式是不同的 。 或： (?x) (M(x)?(?y) (G(y)?F(x,y))) (2) 沒有不犯錯(cuò)誤的人 ； 符號化方法 找到所有的個(gè)體詞 。 在謂詞公式中，我們還用到以下概念。 三、謂詞公式的改寫 考慮到謂詞公式中 ， 有的個(gè)體變項(xiàng)既可以約束出現(xiàn) ， 又可以自由出現(xiàn) ， 為避免這種雙重性 ，以引起混淆 ， 我們要將謂詞公式進(jìn)一步改寫 ，改寫規(guī)則如下 ： (?x)(P(x) ? (?x)Q(x, z)?(?y)R(x, y))?Q(x, y) 1. 換名規(guī)則 ： 將量詞作用域中出現(xiàn)的某個(gè) 約束出現(xiàn) 的個(gè)體變項(xiàng)及對應(yīng)的指導(dǎo)變項(xiàng)改成另一個(gè)作用域中沒有出現(xiàn)過的個(gè)體變項(xiàng)符號，公式的其余部分不變。 y ； (d) DN 上特定謂詞 F(x , y)為 x = y 。 L(x,y)為 L(2,2)= L(3,3)=1。 (3) 解： ? ( p ? q ) ? q是矛盾式，所以 (3)是矛盾式。 一、謂詞演算中常見等值式： (Ⅲ ) 量詞作用域的擴(kuò)張與收縮等值式 ?xA(x)?B??x(A(x)?B) ?xA(x)?B??x(A(x)?B) * ?xA(x)?B??x(A(x)?B) B??xA(x) ??x(B?A(x)) ?xA(x)?B??x(A(x)?B) ?xA(x)?B??x(A(x)?B) * ?xA(x)?B??x(A(x)?B) B??xA(x) ??x(B?A(x)) 注意記住 (*)，且各等價(jià)式中的 B可含其他非指導(dǎo)變元。 前束析取范式： 前束范式 (?x)P(x)的命題公式部分即 P(x)為析取范式。 例 ： F(x,y)： x y， x,y ?R, 設(shè) A(y)= ?xF(x ,y)對任意給定的 y都是成立的 ， 若取 x代替 y，得： ?x?x(x x) 該命題為假命題，原因是違背了條件 (2). 存在量詞引入規(guī)則 (E+規(guī)則 )： A(c) ? (?x)A(x) 要求： (1) c是特定的個(gè)體常項(xiàng) (2) 取代 c的 x不能已在 A(c)中出現(xiàn)過 . 例