第一章 命題及命題公式

1. 命題與連接詞

在數(shù)理邏輯中把能夠判斷真假的陳述句稱為命題。

一般用小寫英文字母或小寫英文字母帶下標表示命題。

命題包含兩個要素：

• 陳述句
• 能判斷真假

原子命題：不可再分解的命題。

復合命題：可以分解成多個原子命題的命題。

通常用符號來表示一個命題，這個過程稱為命題的符號化。

常用的命題聯(lián)結詞：

• 否定聯(lián)結詞 --> 取反（?）

• 合取聯(lián)結詞 --> 與操作(∧)

• 析取聯(lián)結詞 --> 或操作（∨）

• 條件聯(lián)結詞 --> if (->)

• 雙條件聯(lián)結詞 <-> 兩個命題同時同樣值是為真

2.命題公式的等值演算

按下列規(guī)則構成的符號串稱為命題演算的合式公式，也稱為命題公式，簡稱公式。

1. 單個命題變元和常元是合式公式。
2. 如果A是合式公式，那么?A也是合式公式。
3. 如果A和B是合適公式，那么（A∧B）（A∨B）(A->B) (A<->B)是合式公式。
4. 當且僅當有限次地應用了1，2，3，所得到的符號串是合式公式

命題公式一般是用大寫的英文字母A/B/C...表示。

規(guī)定聯(lián)結詞的優(yōu)先級由高到低依次為：

? ∧ ∨ -> <->

命題公式中的命題變元，也稱為命題公式的分量。

命題的符號化可按如下步驟進行：

• 找出符合命題中的原子命題。
• 用英文字母表示這些原子命題。
• 使用命題聯(lián)結詞將這些英文字母連接起來。

若指定的一種指派使A的值為真，則稱這組值為A的成真指派。

若指定的一種指派使A的值為假，則稱這組值為A的成假指派。

在命題公式A中，對A的每一個賦值，就確定了A的一個真值，把它們匯列成表，稱該表為命題公式的 真值表。

設A和B是兩個命題公式，設P1，P2,....Pn為所有出現(xiàn)于A和B中的原子變元，若給定P1，P2...Pn任一組真值指派，A和B的真值都相同，則稱A和B是等值的或者等價的，記為A<=>B.

證明兩個命題公式等價的方法：

方法1-----真值表法。

根據(jù)等價的定義，用真值表證明。

證明公式 p->q <=> ?pVq

方法2-----等價演算法。

基本思想：先用真值表證明一組基本等價式，以它們?yōu)榛A進行公式之間的演算?；镜葍r式常叫 命題定律。

下面是常用的命題定律：

重言式 and 矛盾式

設A是任一命題公式

• 若對A的任意賦值，其真值永為真，則稱命題公式A為 重言式 或 永真式
• 若對A的任意賦值，其真值永為真，則稱命題公式A為 矛盾式 或 永假式
• 若A不是矛盾式，則命題公式A為可滿足式
• 由此定義可以看出，任何重言式都是可滿足的。

蘊涵式

設A和B式命題公式，若A->B是重言式，則稱A蘊涵B，記為A=>B.

證明蘊涵式的方法：

• 真值表法，即構造命題公式A->B的真值表。
• 等價演算法。
• 對A指定真值 T,若由此推出B的真值為T，則A->B是重言式，即A=>B(蘊涵式).
• 對B指定真值 F,若由此推出A的真值為T，則A->B是重言式，即A=>B(蘊涵式).

3.聯(lián)結詞完備集

• 兩個變元總共有8種不同的取值，有2^4（16）個不同的命題公式。
• 三個個變元總共有16種不同的取值，有2^8個不等價的命題公式。
• 兩個變元總共有2^n+1種不同的取值，有2^n個不等價的命題公式。

第二章 命題邏輯的推理理論

第三章 謂詞邏輯