一階邏輯和命題邏輯等價嗎?

時間 2021-12-20 03:50:12

1樓:于佳銘

是個好問題,知乎之前竟然沒有人問過這個嗎?

首先,我們可以明確一點:當所考慮的論域是有限的,且所有的論域中的元素都被命名為某個常量(即,我們可以去直接地引用它),那麼任何乙個一階邏輯的語句,都可以用題目中所描述的方式,轉變為乙個等價的命題邏輯的句子。這點比較顯然:

我們可以用連續合取來展開乙個全稱語句,用連續析取來展開乙個存在語句。我們得到的式子也將是有限長的。在這種情況下,命題邏輯所能表達的式子恰好是所有一階邏輯能夠表達的式子,即兩者的表達能力(Expressive Power)是等同的,我們根據題目,可以視這種情況為「兩種邏輯是等價的」。

在記法上,我們可以作如下規定:

如果 是用集合 作指標集的式子的集合,即 ,那麼我們可以將 寫成 。

如果 是乙個以序數 為指標的變元的集合,即 ,那麼我們可以將 寫成 。

當然,我給出的定義省略了一些細節,不過不難看到,無窮邏輯的表達能力是高於其有限的。回到題主的問題,我們顯然可以對乙個可數論域的全稱語句進行展開,得到零階無窮邏輯中的一句無窮合取。而由於我們定義無窮邏輯時,使用的是更廣義的無窮基數,我們甚至可以允許將例如 這樣的論域不可數的句子展開為乙個無窮合取的式子。

所以,問題解決了?題主的問題確實解決了,不過既然無窮邏輯這麼好用這麼強大,為什麼邏輯學家並沒有將其作為主流使用的邏輯語言呢?這就回到我們之前所提到過的無窮邏輯所包含的一些弊端。

具體地說,任何無窮邏輯都不是緊緻的(Compact),而絕大多數無窮邏輯(除外)甚至也不是完備的(Complete)。

我們先來看為什麼無窮邏輯不是緊緻的。簡而言之,無窮邏輯可以用來表徵[6]良序這一事實就蘊含了其非緊致性。我們首先引入緊緻性的定義:

定義 2.對於乙個語言 ,我們稱其是緊緻的,如果:任何乙個 中的句子的(可能無限大的)集合 是可滿足的(Satisfiable,即擁有乙個模型)當且僅當它的任意有限子集 是可滿足的。

這句句子在任何乙個有限論域內都不能為真,但是在任何乙個無限論域內都為真。我們因此得出無窮邏輯是不緊緻的。

2樓:Jackson-IT

一階邏輯包含命題演算和謂詞演算兩部分,在一階邏輯中,最重要的是關於量詞的刻畫和研究,所以一階邏輯也叫量詞邏輯,命題邏輯無法刻畫量詞,謂詞邏輯能分析命題的基本結構(個體詞、謂詞與量詞之間的關係),能夠刻畫量詞,所以一階邏輯也叫謂詞邏輯,所以一階邏輯和命題邏輯不等價。

3樓:李三畏

語法系統級的等價,的確不好定義。

若僅從量詞使用與否上看,零階邏輯公式與一階邏輯公式是可以轉換的:https://

zhuanlan /p/431755299

數學,邏輯,為什麼原命題和逆否命題等價?

Gusttavo Chan 因為以下公理在古典邏輯下正反均可證。有基礎的童鞋可能感覺到了,逆方向的證明是需要雙重否定消去 RAA 的,所以這個公理在直覺主義邏輯和最小邏輯下是只有正方向成立的,不等價。 Chen George 要看你用的是哪家的公理系統。在 Whitehead Russell 的 P...

一階邏輯和高階邏輯的區別,能不能具象一點說明?

雲兒 高階謂詞是接受其他謂詞作為引數的謂詞。一般的,階為 n 的高階謂詞接受乙個或多個 n 1 階的謂詞作為引數,這裡的 n 1。對高階函式類似的評述也成立。1應用高階邏輯在數學中,高階邏輯在很多方面有別於一階邏輯。其一是變數型別出現在量化中 粗略的說,一階邏輯中禁止量化謂詞。允許這麼做的系統請參見...

這個一階邏輯中的菱形交換圖引理如何證明?

T 不一致,則必然有它的乙個有限子集T 不一致。把T 裡關於M的表述合取起來叫 關於N的表述合取起來叫 C是M和N的公共子結構,所以M和N肯定都滿足僅涉及C裡面變數的那些公式。裡面的變數有來自e C 的和來自M e C 的,的變數有來自f C 和來自N f C 的,這裡分別用x1和x2表示。因為T有...