[經(jīng)濟(jì)學(xué)]第二章謂詞邏輯-資料下載頁
2024-10-19 02:54本頁面
【正文】 任一謂詞公式 Ai代換永真公式 Ｂ 中某一命題變元Pi的所有出現(xiàn)，所得到的新公式 B180。仍然是永真式（但在 Ai的個體變元中不應(yīng)有Ｂ中的約束變元出現(xiàn)），并有 。 39。BB?規(guī)則 4：取代規(guī)則 ? 設(shè) 都是含 n個自由變元的謂詞公式，且 A180。是 A的子公式。若在 A中用 B180。取代 A180。的一處或多處出現(xiàn)后所得的新公式是 B ，則有 。如果 A為永真式，則 B也是永真式。 1 2 1 2( , , .. ., ) ( , , .. ., )nnA x x x B x x x?? ?AB?謂詞邏輯的推理 在謂詞邏輯中，推理的形式結(jié)構(gòu)仍為 若 是永真式， 則稱由前提 邏輯的推出結(jié)論 C， 在此 , C均為謂詞公式。 規(guī)則 5：量詞的增加和刪除規(guī)則 ? 全稱特指規(guī)則 US：從 可得出結(jié)論 A(y) ，其中 y是個體域中任一個體，即： ? 注意： y不能和 A(x)中其它指導(dǎo)變元重名。 ? 存在特指規(guī)則 ES：從 可得出結(jié)論 A(a) ，其中 a是 和在此之前不曾出現(xiàn)過的個體常量，即： ? 注意： a不能和指定前提中任一自由變元同名，也不能和使用本規(guī)則以前任一推導(dǎo)步驟上得到的公式的自由變元同名。 ( ) ( )x A x?( ) ( ) ( )x A x A y??( ) ( )x A x?( ) ( )x A x?( ) ( ) ( )x A x A a?? ? 命題邏輯中的兩種范式都可以直接推廣到謂詞邏輯中來，只要把原子命題公式換成原子謂詞公式即可， ? 根據(jù)量詞在公式中出現(xiàn)的情況不同，又可分為 前束范式 和 斯柯林范式 。 前束范式 ? 定義：對任一謂詞公式 F，如果其中所有量詞均非否定的出現(xiàn)在公式的最前面，且它們的轄域為整個公式，則稱公式 F為 前束范式 。 ( ) ( ) ( ) ( ( , ) ( , ) ( , , ) )x y z P x y Q x y R x y z? ? ? ? ?前束范式 ? 任意一個公式都可以轉(zhuǎn)化成與之等價的前束范式，方法如下： ? 消去公式中的聯(lián)結(jié)詞 和 → ，例如 ? 將公式內(nèi)的否定符號深入到謂詞變元前并化簡到謂詞變元前只有一個否定號； ? 利用 改名、代入規(guī)則 使所有的約束變元均不同名，且使自由變元與約束變元亦不同名； ? 擴(kuò)充量詞的轄域至整個公式。 ?( ) ( )A B A B A B? ? ? ? ? ? ?A B A B? ? ? ?前束范式 例：將下列公式轉(zhuǎn)化成前束范式。 解： ( ( ) ( ) ( ) ( ) ) ( ) ( )x P x y R y x F x? ? ? ? ?( ( ) ( ) ( ) ( ) ) ( ) ( )x P x y R y x F x? ? ? ? ?( ( ) ( ) ( ) ( ) ) ( ) ( )x P x y R y x F x? ? ? ? ? ? ?( ) ( ) ( ) ( ) ( ) ( )x P x y R y x F x? ? ? ? ? ? ? ?( ) ( ) ( ) ( ) ( ) ( )x P x y R y z F z? ? ? ? ? ? ? ?( ) ( ) ( ) ( ( ) ( ) ( ) )x y z P x R y F z? ? ? ? ? ? ? ?斯柯林范式 ? 定義：如果前束范式中所有的存在量詞均在全稱量詞之前，則稱這種形式為 斯柯林范式 。 ( ) ( ) ( ) ( ( , ) ( , ) ( ) )x z y P x y Q y z R y? ? ? ? ?斯柯林范式 ? 任何一個公式都可以化為與之等價的斯柯林范式，方法如下： ? 先將給定公式化為前束范式； ? 將前束范式中的所有 自由變元用全稱量詞 （ UG）約束； ? 若經(jīng)上述改造后的公式 A中，第一個量詞不是存在量詞，則可以將等價變換成如下形式 ? 如果前束范式是由 n個存在量詞開始，然后是 m個全稱量詞，后面還跟有存在量詞，則可以利用下述等價式將這些全稱量詞逐一移到存在量詞之后去： ( ) ( ( ( ) ( ) ) )u A G u G u? ? ? ?1 1 2( ) .. .( ) ( ) ( , , .. ., , )nnx x y P x x x y? ? ?1 1 2 1 212( ) .. .( ) ( ) ( , , .. ., , ) ( , , .. ., ,() )( ) ( , , .. ., ,())n n nnx x y P x x x y H x x x yz H x x x z? ? ? ? ? ???斯柯林范式 例：將公式 化成斯柯林范式。 解： ( ) ( ( ) ( ) ( ) ) ( )x P x y Q y R z? ? ? ?( ) ( ( ) ( ) ( ) ) ( )( ) ( ( ) ( ) ( ) ) ( )( ) ( ) ( ( )()( ) ) ( )( ) ( ) ( ( ) ( ) ) ( ) ( )( ) ( ) ( ) ( ( ( ) ( ) ) ( ) )( ) ( ) ( ) ( ) ( ) ( ) ( )( ( ) ( ) )()( ) ( ) ((()x P x y Q y R zx P x y Q y R zx y P x Q y R zx y P x Q y z R zx y z P x Q y R zu x y z P x Q y R zG u G uux? ? ? ?? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ?? ? ? ? ? ? ? ? ???? ? ? ) ( ) ( ) ( ) ( )( ( ) ( ) ) ( , ) ( ) ( , )( ) ( ) ( ) (()) ( ) ( ) ( ) ( )( ( ) ( ) ) ( , ) ()()(,)()()()( (()) ))y z P x Q y R zG u G u H u x s H u su x y z s P x Q y R zG u G u H u x H u s? ? ? ? ? ?? ? ? ? ? ?? ? ? ? ? ? ? ? ? ?? ? ? ? ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1