【正文】 ： F(x,y)： x y， x,y ?R, 設(shè) A(2)= ?xF(x ,2), A(2) 為真命題 ， x已在 A(2)中出現(xiàn)過(guò)。 ⑦ G(y)? ? F(y) ④⑥ 假言三段論 ⑧ (?x)(G(x)? ? F(x)) ⑦ U+規(guī)則 ⑤ (?x)(G(x)? H(x)) 前提引入 ⑥ G(y)?H(y) ⑤ U規(guī)則 ④ H(y)?? F(y) ③ U規(guī)則 ③ (?x)(H(x)? ? F(x)) ② 置換 證明： ① ? (?x)(F(x)?H(x)) 前提引入 ② (?x)(? F(x)?? H(x)) ① 置換 例 構(gòu)造下列推理的證明： 前提： ?(?x)(F(x)?H(x))， (?x)(G(x)?H(x)) 結(jié)論： (?x)(G(x)? ? F(x)) 例 證明：每個(gè)科學(xué)工作者都是刻苦鉆研的，每個(gè)刻苦鉆研而又聰明的人在他的事業(yè)中都將獲得成功。 解： 命題符號(hào)化： F(x)： x是學(xué)術(shù)會(huì)會(huì)員 G(x)： x是專家 H(x)： x是工人 R(x)： x是青年人 二、 謂詞邏輯推理中遵循的推理規(guī)則 前提： (?x)(F(x)?G(x)?H(x))， (?x)(F(x)?R(x)) 結(jié)論： (?x)(F(x)?R(x)?G(x)) 證明： ① (?x)(F(x)?R(x)) 前提引 入 ④ F(c)?G(c)?H(c) ③ U規(guī)則 ② F(c)?R(c) ① E 規(guī)則 ③ (?x)(F(x)?G(x)?H(x)) 前提引入 二、 謂詞邏輯推理中遵循的推理規(guī)則 ⑨ (?x)(F(x)?R(x)?G(x)) ⑧ E+ 規(guī)則 ⑦ G(c) ⑥ 化簡(jiǎn) ⑧ F(c)?R(c)?G(c) ②⑦ 合取 ⑤ F(c) ② 化簡(jiǎn) ⑥ G(c)?H(c) ④⑤ 假言推理 注意： 如果將證明步驟改為： 1. (?x)(F(x)?G(x)?H(x)) (c)?R(c) 2. F(c)?G(c)?H(c) 3. (?x)(F(x)?R(x)) … 最后也可推出 (?x)(F(x)?R(x)?G(x))， 但 (4)是有錯(cuò)誤的，因?yàn)?(2)中 c不一定剛好滿足 (3)。 例： F(x， y)： x y， x， y ?R,則公式 ?x?yF(x ,y)是真命題，設(shè) A(x)= ?yF(x ,y)， x在 A(x)中是自由出現(xiàn)的，但 y在 A(x)中是約束出現(xiàn)的，若取 y代替 x， 得 ： ?x?yF(x， y) ? ?yF(y， y) 該命題是假命題 。 例 將合式公式 ((?x)P(x)?(?y)R(y))?(?x)F(x)化為前束范式： 任一合式公式表示成前束范式可按如下步驟進(jìn)行： (1) 消去公式中出現(xiàn)的多余量詞； 解題思想 二、 常見(jiàn)等值式的應(yīng)用 (前束范式 ) (2) 利用雙重否定定律 、 德 ? 摩根律及量詞轉(zhuǎn)換律將公式中的否定字符深入到謂詞字母前 (否定符緊貼 )； (3) 利用換名和代換規(guī)則使所有約束變?cè)幌嗤?,并且使自由變?cè)才c約束變?cè)煌?(更名 )； (4) 利用量詞作用域的擴(kuò)張和收縮律 ， 擴(kuò)大量詞的作用域至整個(gè)公式 (擴(kuò)域 )。 (1) ? xF (x) ? ? xF (x)； p ? q p ? (q ? p) ? ( p ? q ) ? q p ? q 167。因此公式是邏輯有效式。 函數(shù) f(x)為 f(2)=3， f(3)=2； 謂詞 F(x)為 F(2)=0， F(3)=1。 解題思想 三、謂詞公式的解釋（續(xù)） 解： (?x)(P(x)?Q(x))?(P(1)?Q(1)?(P(2)?Q(2)) ?(1?0)?(0?1) ? 0?1 ? 0 三、謂詞公式的解釋（續(xù)） 2022/8/21 離散數(shù)學(xué) 44 例 8：給定解釋 N如下： (a)DN 為自然數(shù)集合； (b)DN中特定元素 a=0；(c)DN 上特定函數(shù) f(x,y)= x + y ， g(x,y)= x *y ； (d)DN 上特定謂詞 F(x, y)為 x =y. 在解釋 N下，下列公式那些為真？那些為假？ (1) ? xF (g (x, a), x)； 三、謂詞公式的解釋（續(xù)） (2) ? x ?y (F (f (x, a) , y) ? F (f (y, a) , x))； (3) ? x ?y ? z F (f (x, y), z) (4) F (f (x, y), f (y, z)) 因此 (1)為假命題 ? ? x(0 = x) 解：在解釋 N 下， (1) ? ? xF (x 解： (?x)Q(x, z)中 x是作用變?cè)?， ?的轄域?yàn)?Q(x， z)，其中 x 約束出現(xiàn) ， z自由出現(xiàn)； (3) (?x)(P(x) ? (?x)Q(x, z)?(?y)R(x, y))?Q(x, y) ； (?y)R(x, y)中，y是作用變?cè)??的轄域?yàn)?R(x, y)， 其中 y約束出現(xiàn)， x自由出現(xiàn)； 在 (?x)(P(x)?(?x) Q(x,z)?(?y)R(x, y)) 中，作用變?cè)獮?x， ?的作用域?yàn)?(P(x)?(?x)Q(x, z) ?(?y)R(x, y)), 但 Q(x, z)中的 x不是 ?的作用變?cè)?x, y均為約束出現(xiàn)， z自由出現(xiàn)； Q(x, y)中， x, y為自由變?cè)? 量詞 ?， ?后面的 x叫做量詞的 作用變?cè)?， 或指導(dǎo)變?cè)?， P(x)叫做 量詞的作用域 （ 轄域 ） 。 例 用謂詞 (一階邏輯合式 )公式表示下列命題： (1) 并非每個(gè)實(shí)數(shù)都是有理數(shù)； (2)沒(méi)有不犯錯(cuò)誤的人 ； (3) 每個(gè)人都有一些缺點(diǎn)。 將命題 (公式 )“有些人活百歲以上 ” 符號(hào)化 M(x)： x是人 (特性謂詞 ) F(x)： x活百歲以上 命題 (公式 )符號(hào)化為： ?x(M(x) ?F(x)) 分析一下： 它與 ?xF(x)有什么區(qū)別？ 解： 使用量詞時(shí) , 應(yīng)該注意以下幾點(diǎn) : 1 .在不同的個(gè)體域中，命題符號(hào)化的形式可能不一樣 。 解： 引入一元謂詞： F(x) ––– x是素?cái)?shù) G(x) ––– x是偶數(shù) 命題符號(hào)化： a為 2 (1) 符號(hào)化為 F(a) G(a) ? (0元謂詞 ) (1) 2是素?cái)?shù)且是偶數(shù) ； 解： 引入二元謂詞： L(x, y)––– x比 y大 命題符號(hào)化： a為 2 ,b為 3， c為 4 (2) 符號(hào)化為 L(a,b) ? L(a, c) (2) 如果 2大于 3，則 2大于 4 ； 類(lèi)似于 (2)， 自己做！ (3) 如果張明比李民高，李民比趙亮高，則張明比趙亮高 ； (1) 所有的人都是要死的 。 謂詞常項(xiàng) ：表示具體性質(zhì)或關(guān)系的謂詞，用大寫(xiě)英文字母 F， G， …… ， 表示。 謂 詞 ：用來(lái)刻劃個(gè)體詞的 性質(zhì) 或個(gè)體詞之間 關(guān)系 的。 ” p: 所有的人是要死的 。 2022/8/21 離散數(shù)學(xué) 4 第二章 一階邏輯 167。 167。 個(gè)體變項(xiàng) x具有性質(zhì) F： 記作 F(x) 個(gè)體變項(xiàng) x、 y具有關(guān)系 L： 記作 L(x,y) 2(1) 是無(wú)理數(shù) (性質(zhì) ) (2) 小李 比 小趙 高 2厘米 (關(guān)系 ) F(x) : x 是無(wú)理數(shù) , 2:a ).()1( aF可表示