一階邏輯基本概念ppt.ppt

第4章一階邏輯基本概念 離散數(shù)學(xué) 本章說明 本章的主要內(nèi)容一階邏輯基本概念 命題符號化一階邏輯公式 解釋及分類本章與后續(xù)各章的關(guān)系克服命題邏輯的局限性是第五章的先行準(zhǔn)備 命題邏輯的缺陷 把命題看成是一個(gè)個(gè)孤立的命題 忽略了命題之間的聯(lián)系 不能反映某些重要的常見的邏輯思維過程 1 繁瑣例 表述集合個(gè)體性質(zhì)及相互關(guān)系S 1 2 50 表述S中所有元素都大于3這樣一個(gè)性質(zhì) 需要1 3 2 3 50 3等50個(gè)命題 2 不能描述命題間的邏輯聯(lián)系例如 邏輯學(xué)中著名的蘇格拉底三段論 P 所有人必死Q 蘇格拉底是人R 蘇格拉底必死表示為命題邏輯 應(yīng)該有 P Q R 也就是公式 P Q R應(yīng)該是恒真的 顯然該公式不是恒真的 解釋 P Q R 就能弄假該公式 原因 命題R和命題P Q是有內(nèi)在關(guān)系的 只是這種關(guān)系在命題邏輯中無法表示 因此 需要對命題的成分 結(jié)構(gòu)和命題間的共同特性等作進(jìn)一步的分析 分析出個(gè)體詞 謂詞和量詞 以期達(dá)到表達(dá)出個(gè)體與總體的內(nèi)在聯(lián)系和數(shù)量關(guān)系 這正是謂詞邏輯所要研究的問題 本章內(nèi)容 4 1一階邏輯命題符號化4 2一階邏輯公式及解釋本章小結(jié)習(xí)題作業(yè) 4 1一階邏輯命題符號化 一階邏輯命題符號化的三個(gè)基本要素個(gè)體詞謂詞量詞 個(gè)體詞及相關(guān)概念 個(gè)體詞一般是充當(dāng)陳述句主語的名詞或代詞 說明 個(gè)體詞 指所研究對象中可以獨(dú)立存在的具體或抽象的客體 舉例命題 電子計(jì)算機(jī)是科學(xué)技術(shù)的工具 個(gè)體詞 電子計(jì)算機(jī) 命題 他是三好學(xué)生 個(gè)體詞 他 心物一元or心物二元 量子力學(xué)中的測不準(zhǔn)原理 個(gè)體常項(xiàng) 表示具體或特定的客體的個(gè)體詞 用小寫字母a b c 表示 個(gè)體變項(xiàng) 表示抽象或泛指的客體的個(gè)體詞 用x y z 表示 個(gè)體域 或稱論域 指個(gè)體變項(xiàng)的取值范圍 可以是有窮集合 如 a b c 1 2 可以是無窮集合 如N Z R 全總個(gè)體域 universe 由宇宙間一切事物組成 個(gè)體詞及相關(guān)概念 本教材在論述或推理中 如果沒有指明所采用的個(gè)體域 都是使用的全總個(gè)體域 說明 謂詞及相關(guān)概念 謂詞 predicate 是用來刻畫個(gè)體詞性質(zhì)及個(gè)體詞之間相互關(guān)系的詞 1 是無理數(shù) 是個(gè)體常項(xiàng) 是無理數(shù) 是謂詞 記為F 命題符號化為F 2 x是有理數(shù) x是個(gè)體變項(xiàng) 是有理數(shù) 是謂詞 記為G 命題符號化為G x 3 小王與小李同歲 小王 小李都是個(gè)體常項(xiàng) 與 同歲 是謂詞 記為H 命題符號化為H a b 其中a 小王 b 小李 4 x與y具有關(guān)系L x y都是個(gè)體變項(xiàng) 謂詞為L 命題符號化為L x y 謂詞常項(xiàng) 表示具體性質(zhì)或關(guān)系的謂詞 用大寫字母表示 如 1 2 3 中謂詞F G H 謂詞變項(xiàng) 表示抽象的 泛指的性質(zhì)或關(guān)系的謂詞 用大寫字母表示 如 4 中謂詞L n n 1 元謂詞 P x1 x2 xn 表示含n個(gè)個(gè)體變項(xiàng)的n元謂詞 n 1時(shí) 一元謂詞 表示x1具有性質(zhì)P n 2時(shí) 多元謂詞 表示x1 x2 xn具有關(guān)系P 0元謂詞 不含個(gè)體變項(xiàng)的謂詞 如F a G a b P a1 a2 an 若F G P為謂詞常項(xiàng) 則上述0元謂詞為命題常項(xiàng) 若F G P為謂詞變項(xiàng) 則為命題變項(xiàng) n元謂詞是命題嗎 不是 只有用謂詞常項(xiàng)取代P 用個(gè)體常項(xiàng)取代x1 x2 xn時(shí) 才能使n元謂詞變?yōu)槊} 思考 謂詞及相關(guān)概念 謂詞的形式化定義 設(shè)D是非空個(gè)體名稱集合 定義在Dn上取值于 0 1 上的n元函數(shù) 稱為n元命題函數(shù)或n元謂詞 其中Dn表示集合D的n次笛卡爾乘積 例 令G x y x高于y G x y 是一個(gè)二元謂詞 將x代以個(gè)體 張三 y代以個(gè)體 李四 則G 張三 李四 就是命題 張三高于李四 G x y 不是命題 而是一個(gè)命題函數(shù)即謂詞 將x y代以任意確定的個(gè)體 由G x y 都能得到一個(gè)命題 D 2 3 4 設(shè)P x x大于3 則P x 為一元謂詞 指定元素 命題 P 2 0 P 3 0 P 4 1設(shè)P x y x大于y 則P x y 為二元謂詞 指定元素 命題 P 2 3 0 P 4 2 1設(shè)P x y z 若x y 1 z 則P x y z 為1 否則為0 則P x y z 為三元謂詞 指定元素 命題 P 2 3 4 1 P 4 2 2 0 例題 例題 將命題 這只大紅書柜擺滿了那些古書 符號化 1 設(shè)F x y x擺滿了y R x x是大紅書柜Q y y是古書 a 這個(gè)書柜b 那些書符號化為 R a Q b F a b 2 設(shè)A x x是書柜 B x x是大的C x x是紅的 D y y是古老的E y y是圖書 F x y x擺滿了ya 這個(gè)東西b 那些東西符號化為 A a B a C a D b E b F a b 用謂詞的概念可將蘇格拉底三段論做如下的符號化 令H x 表示 x是人 M x 表示 x必死 則三段論的三個(gè)命題表示如下 P H x M x Q H 蘇格拉底 R M 蘇格拉底 現(xiàn)在可以將蘇格拉底三段論符號化為 令命題P為 所有人都會死 其否定命題為 P H x M x H x M x H x M x 亦即 命題P 所有人都會死 的否定命題是 所有人都不會死 這和人們對命題 所有人都必死 的否定的理解並不一致 但問題是 原因 命題P的確切意思應(yīng)該是 對任意x 如果x是人 則x必死 但是H x M x 中并沒有確切的表示出 對任意x 這個(gè)意思 因此 在謂詞邏輯中除引進(jìn)謂詞外 還需要引進(jìn) 對任意x 這個(gè)語句 及其對偶的語句 存在一個(gè)x 量詞 quantifier 是表示個(gè)體常項(xiàng)或個(gè)體變項(xiàng)數(shù)量屬性的詞 1 全稱量詞 符號化為 All 日常生活和數(shù)學(xué)中所用的 一切的 所有的 每一個(gè) 任意的 凡 都 等詞可統(tǒng)稱為全稱量詞 x表示個(gè)體域里的某個(gè)個(gè)體 xF x 表示個(gè)體域里所有個(gè)體都有性質(zhì)F 2 存在量詞 符號化為 Exist 日常生活和數(shù)學(xué)中所用的 存在 有一個(gè) 有的 至少有一個(gè) 等詞統(tǒng)稱為存在量詞 y表示個(gè)體域里某個(gè)個(gè)體 yG y 表示個(gè)體域里存在個(gè)體y具有性質(zhì)G 量詞及相關(guān)概念 引入謂詞后 命題P就可確切地符號化如下 x H x M x 命題P的否定命題為 P x H x M x x H x M x 亦即 至少有一個(gè)人是不死的 這個(gè)命題才是 所有人都要死 的否定 三段論的三個(gè)命題 在謂詞邏輯中可以如下表示 P x H x M x Q H 蘇格拉底 R M 蘇格拉底 以后可以證明 在謂詞邏輯中 R是P和Q的邏輯結(jié)果 例符號化下述命題 1 所有的老虎都要吃人 2 每一個(gè)大學(xué)生都會說英語 3 所有的人都長著黑頭發(fā) 4 有一些人登上過月球 5 有一些自然數(shù)是素?cái)?shù) 解設(shè)有如下謂詞 P x x會吃人 Q x x會說英語 R x x長著黑頭發(fā) S x x登上過月球 T x x是素?cái)?shù) 1 x P x x 老虎 2 x Q x x 大學(xué)生 3 x R x x 人 4 x S x x 人 5 x T x x 自然數(shù) 不便之處 1 從書寫上十分不便 總要特別注明個(gè)體域 2 在同一個(gè)比較復(fù)雜的句子中 不同命題函數(shù)中的個(gè)體可能屬于不同的個(gè)體域 此時(shí)無法清晰表達(dá) 如例 1 和 4 的合取 x P x x R x x 人 x 老虎 不便之處 續(xù) 3 若個(gè)體域的注明不清楚 將造成無法確定命題真值 即對于同一個(gè)n元謂詞 不同的個(gè)體域有可能帶來不同的真值 例如對于語句 x x 6 5 可表示為 有一些x 使得x 6 5 該語句在下面兩種個(gè)體域下有不同的真值 a 在實(shí)數(shù)范圍內(nèi)時(shí) 確有x 1使得x 6 5 因此 x x 6 5 為 真 b 在正整數(shù)范圍內(nèi)時(shí) 則找不到任何x 使得x 6 5為 真 所以 x x 6 5 為 假 不便之處的根源 因?yàn)樾枰貏e標(biāo)注每個(gè)謂詞的個(gè)體域 特性謂詞 新的問題出現(xiàn)了 U x 如何與 x P x x S x 結(jié)合才符合邏輯呢 例將下面兩個(gè)命題符號化 1 所有的老虎都會吃人 2 有些人登上過月球 特性謂詞的使用 1 令P x x會吃人U x x是老虎則符號化的正確形式應(yīng)該是 x U x P x 它的含義