命題邏輯和一階邏輯

稱為一個推理( sequent )，如果使用Natural Deduction的方式進(jìn)行推導(dǎo)( derivation )，可以由 得到 ，那么這個推理是有效的。
定義：

對于合理的推理 ，能否在真值表的語義下，保證當(dāng) 為T時， 不可能是F。

若 中，當(dāng)全 部成立時， 也成立，則稱 語義蘊(yùn)含 。

soundness：若 是合理的，則$$

completeness：若 ，則是 合理的

證明：太長不看

實(shí)際是想說：一個邏輯系統(tǒng)需要滿足soundness和completeness的一致性。

signature：三個部分

分別是函數(shù)名、常數(shù)名、謂詞名

一般省略 ，因?yàn)槠淇煽醋鳠o參數(shù)的

一階邏輯的公式中，兩類：

一階邏輯的語義：

proof-based logic：給出一個operative的，通過Natural Deduction方式的 證明

優(yōu)點(diǎn)：一旦找到一個證明方式成功推導(dǎo)，即可證明

缺點(diǎn)：難以證明 ，需要遍歷全部可能的證明方式，才能夠得到結(jié)論

semantic-based logic：通過真值表驗(yàn)證 的正確性

優(yōu)點(diǎn)：更容易證明 ，只要找到一個左側(cè)為T的assignment，而右側(cè)為F即可

缺點(diǎn)：想要證明 更困難，需要遍歷全部的真值組合。

一階邏輯evaluate的難點(diǎn)：每一個變量都是一個可能的具體值的占位符

對 ，每個x， 都為真，則最終取值為真

對 ，找到一個x0， 為真，則最終取值為真

如果 的結(jié)構(gòu)為 等（解析樹根節(jié)點(diǎn)），那么最終的真值可以按照各謂詞公式的真假，遵循命題邏輯中的連接詞運(yùn)算進(jìn)行求解

問題進(jìn)一步轉(zhuǎn)為求解 的真值。對此需要明確謂詞常量的含義和term的含義。

的模型 ：

例， ，R是二元謂詞，F(xiàn)是一元謂詞， 包含：

環(huán)境：將變量映射到具體值的look-up table

對于在l環(huán)境下的滿足性定義：

給出模型解釋的時候，需要使用擴(kuò)展簽名，否則將會出現(xiàn)bug：

用解釋的方式定義：

函數(shù)常量alma，

在解釋空間中取值替換變量y（例如a），替換變量：

，此時出現(xiàn)問題， 沒有定義，因?yàn)镮nterpretation的domain必須是 的子集。

于是擴(kuò)展 為 ，此處的*是abc實(shí)際值的名字，

并且，原有定義下 為真，當(dāng)且僅當(dāng)對所有的 ， 為真

改為：

當(dāng)且僅當(dāng)對所有的 ， 為真

這一解釋就沒有問題了。

Logic in CS中的定義下，雖然未考慮 。對于模型的映射直接是

一個全局的具體取值A(chǔ)

其實(shí)是相同的，因?yàn)楹瘮?shù)和謂詞就是signature的組成部分。

檢查任意性和存在性時，

變量：直接替換為A中的元素，相當(dāng)于隱性定義了對于非signature中的元素，映射的結(jié)果是元素值自身。

在謂詞邏輯中是重載的，對模型而言表示滿足，對兩個formula而言表示語義蘊(yùn)含。

for all

一個模型滿足一個公式組，當(dāng)且僅當(dāng)這一模型滿足公式組中的每一個公式，如果這一公式組的每個模型都還滿足另一個公式 ,那么這個公式組蘊(yùn)含這一公式。

存在一個模型，使得 ，則 可滿足

一階邏輯無法表達(dá)傳遞閉包：

能否找到一個公式 ，公式中只包含兩個自由變量u和v，一個謂詞關(guān)系R，通過這個公式可以表達(dá)：

這樣的R無法找到，這樣的公式是無止盡的。

一階邏輯公式的合理性是undecidable的：給定一個FOL公式 ， 是否成立？

這個問題無法解答。

==》FOL的滿足性問題也是undecidable的

證明： 是合理的 當(dāng)且僅當(dāng) 是不可滿足的（可滿足：存在一個interpretation I，

一階邏輯的生成規(guī)則

合式公式（wff）的集合按如下規(guī)則遞歸的定義：
簡單和復(fù)雜的謂詞 如果 P 是 n 元（n ≥ 0）謂詞，則 Pa_1,...,a_n是合式的。如果 n ≤ 1，則 P 是原子。
歸納條款 I: 如果 Φ 是 wff，則 ┐ Φ 是 wff。
歸納條款 Ⅱ： 如果 Φ 和 ψ 是 wff，則 Φ∧ ψ， Φ∨ ψ，（Φ → ψ）和（Φψ） 是 wff。
歸納條款 Ⅲ： 如果 φ 是 包含變量 x 的一個自由實(shí)例的 wff，則 砢，φ和x，φ 是 wff。（此后在x，φ 和x，φ 中x 的任何實(shí)例都被稱為約束的 — 而不是自由的。）
閉包條款： 其他東西都不是 wff。 下列四個公理是謂詞演算的特征：
PRED-1:x Z(x) → Z(y)
PRED-2:Z(y) →x Z(x)
PRED-3:x (W → Z(x)) → (W →x Z(x))
PRED-4:x (Z(x) → W) → (x Z(x) → W)
它們實(shí)際上是公理模式，因?yàn)槠渲械闹^詞字母 W 和 Z 可以被任何謂詞字母所替代，而不改變這些公式的有效性。 叫做全稱普遍化的推理規(guī)則是謂詞演算的特征。它可以陳述為
|- Z(x),x Z(x)
這里的 Z(x) 假定表示謂詞演算的一個已證明的定理，而 砢娀（x) 是它針對于變量 x 的閉包。謂詞字母 Z 可以被任何謂詞字母所替代。
注意：全稱普遍化類似于模態(tài)邏輯的必然性規(guī)則，它是
- P,- □ P 在公告板中列出了一些重要的元邏輯定理。
不像命題演算，一階邏輯是不可判定性的。對于任意的公式 P，可以證實(shí)沒有判定過程，判定 P 是否有效，（參見停機(jī)問題）。（結(jié)論獨(dú)立的來自于邱奇和圖靈。）
有效性的判定問題是半可判定的。按哥德爾不完備定理所展示的，對于任何有效的公式 P,P 是可證明的。
單體謂詞邏輯（就是說，謂詞只有一個參數(shù)的謂詞邏輯）是可判定的。

什么是一階邏輯

一階邏輯是區(qū)別于高階邏輯的數(shù)理邏輯，它不允許量化性質(zhì)。性質(zhì)是一個物體的特性；所以一個紅色物體被表述為有紅色的特性。 一階謂詞演算或一階邏輯（FOL）允許量化陳述的公式，比如"存在著 x，..." (x) 或 "對于任何 x，..." （砢），這里的 x 是論域(domain of discourse)的成員。一階（遞歸）公理化理論是通過增加一階句子/斷定的遞歸可枚舉集合作為公理，可以被公理化為一階邏輯擴(kuò)展的理論。這里的"..."叫做謂詞并表達(dá)某種性質(zhì)。謂詞是適用于某些事物的表達(dá)。所以，表達(dá)"是黃色"或"喜歡椰菜"分別適用于是黃色或喜歡椰菜的那些事物。 一階邏輯是區(qū)別于高階邏輯的數(shù)理邏輯，它不允

什么是一階邏輯

一階邏輯是研究數(shù)學(xué)中由個體、函數(shù)及關(guān)系構(gòu)成的命題以及由這些命題經(jīng)使用量詞和命題連接詞構(gòu)成的更復(fù)雜的命題和這類命題之間的推理關(guān)系。在為數(shù)學(xué)的語言和推理建立形式系統(tǒng)的過程中，一階邏輯處于核心地位，多數(shù)常見的數(shù)學(xué)公理系統(tǒng)都可在一階邏輯中表述。（F.L.）G.弗雷格首先建立了一階邏輯的形式系統(tǒng)(1897)。人們也稱之為謂詞演算。其后，A.N.懷特海和B.A.W.羅素使其進(jìn)一步精確化(1910)。 1 正文 回到頂部意見反饋 相關(guān)搜索 大家都在搜 一階邏輯公式 一階邏輯與一階理論 一階邏輯的推理理論 離散數(shù)學(xué) 一階邏輯 正文折疊編輯本段 在一階邏輯中描述一個數(shù)學(xué)理論，首先會涉及這個理論所討論的對象、定義

什么是一階邏輯

實(shí)際上，一階邏輯是一種形式系統(tǒng)（Formal System)，即形式符號推理系統(tǒng)，也叫一階謂詞演算、低階謂詞演算(Predicate Calculus）、限量詞（Quantifier）理論，也有人稱其為“謂詞邏輯”，雖然這種說法不夠精確?？傊?，不管怎么說，一階邏輯就是一種形式推理的邏輯系統(tǒng)，是一種抽象推理的符號工具。 要注意的是，一階邏輯不同于單純的“命題邏輯”（Proposition Logic），因?yàn)?，一階邏輯里面使用了大量所謂“限量詞變量”（Quantified variables），比如：?x（意思是存在一個變量x），限量詞符號“?”是把字母“E”從左向右反轉(zhuǎn)過來產(chǎn)生的，其原本的意思的