1.什么是命題

什么是命題

數(shù)理邏輯研究的中心問題是推理，而推理的前提和結論都是命題。因而命題是推理的基本單位
具有確切真值的陳述句稱為命題(proposition)。該命題可以取一個“值”，稱為真值。真值只有“真”和“假”兩種，分別用“T”(或“1”) 和“F”(或“0”)表示

非命題

一切沒有判斷內(nèi)容的句子，如命令句 (或祈使句)、感嘆句、疑問句、二義性的陳述句等都不能作為命題。

復合命題 (如何產(chǎn)生新命題)

原子命題 (簡單命題)：不能再分解為更為簡單命題的命題。
復合命題：可以分解為更為簡單命題的命題。這些簡單命題之間是通過如“或者”、“并且”、“不”、“如果......則......”、“當且僅當”等這樣的關聯(lián)詞和標點符號復合而成。

2.命題聯(lián)結詞

否定聯(lián)結詞

設 P 是任意一個命題，復合命題“非 P”(或 “P 的否定”)稱為 P 的否定式(negation)，記作?P，“?” 為否定聯(lián)結詞。P 為真當且僅當 ?P 為假。

否定聯(lián)結詞

合取聯(lián)結詞

設 P、Q 是任意兩個命題，復合命題“P 并且 Q”(或 “P 和 Q”)稱為 P 與 Q 的合取式(conjunction)，記作P ∧ Q，“∧” 為合取聯(lián)結詞。P ∧ Q 為真當且僅當 P，Q 同為真。

合取聯(lián)結詞

“∧” 是自然語言中的 “并且”、“既…又…”、“但”、“和”、“與”、“不僅…而且…”、“雖然…但是…”、“一面…, 一面…” 等的邏輯抽象；但不是所有的“和”，“與”都要使用合取聯(lián)結詞表示，要根據(jù)句子的語義進行分析。

2 和 3 的最小公倍數(shù)是 6；
2 點 a 位于點 b 與點 c 之間。
這兩個命題都是簡單命題，不能再分。

析取聯(lián)結詞

設 P、Q 是任意兩個命題，復合命題“P 或 Q”稱為 P 與 Q 的析取式(disjunction)，記作P ∨ Q，“∨” 為析取聯(lián)結詞。P ∨ Q 為真當且僅當 P，Q 至少有一個為真。

析取連接詞

聯(lián)結詞 “∨” 是自然語言中的 “或”、“或者” 等的邏輯抽象。自然語言中的 “或” 有 “可兼
或”(或稱為同或)、“不可兼或”(即異或) 兩種。嚴格來講，析取聯(lián)結詞實際上代表的是可兼或，異或有時會使用單獨的異或聯(lián)結詞 “⊕” 或 “∨ˉ” 來表示。

命題：張紅生于 1982 年或 1983 年，令
1 P: 張紅生于 1982 年；
2 Q: 張紅生于 1983 年。
P 與 Q 不能同時為真，即為“不可兼或”

蘊涵聯(lián)結詞

設 P、Q 是任兩個命題，復合命題“如果 P，則 Q”稱為 P 與 Q 的蘊涵式(implication)，記作P → Q，“→” 為蘊涵聯(lián)結詞。P → Q 為假當且僅當 P 為真且 Q 為假。一般把蘊涵式 P → Q中的 P 稱為該蘊涵式的前件，Q 稱為蘊涵式的后件。

蘊涵聯(lián)結詞

等價聯(lián)結詞

設 P、Q 是任兩個命題，復合命題“P 當且僅當 Q”稱為 P 與 Q 的等價(equivalence)，記作P ? Q，“?” 為等價聯(lián)結詞(也稱作雙條件聯(lián)結詞)。P ? Q 為真當且僅當 P、Q 同為真假。

等價聯(lián)結詞

3.命題符號化及應用

回顧命題聯(lián)結詞

命題聯(lián)結詞的真值表

聯(lián)結詞是兩個命題真值之間的聯(lián)結，而不是命題內(nèi)容之間的連接，因此復合命題的真值只取決于構成他們的各簡單命題的真值，而與它們的內(nèi)容無關，與二者之間是否有關系無關。

1. 命題聯(lián)結詞的優(yōu)先級
2. 復合命題符號化
3. 命題聯(lián)接詞與開關電路
4. 命題聯(lián)接詞與邏輯電路
5. 命題聯(lián)接詞與位運算

4.命題公式和真值表

命題變元

一個特定的命題是一個常值命題，它不是具有值 “T”(“1”)，就是具有值 “F”(“0”)。

一個任意的沒有賦予具體內(nèi)容的原子命題是一個變量命題，常稱它為命題變量 (或命題變元)(propositional variable)，該命題變量無具體的真值，它的變域是集合{T, F}(或 {0, 1})。

命題公式

命題公式

1. 原子命題變元是最簡單的合式公式，稱為原子合式公式，簡稱原子公式；
2. 命題公式?jīng)]有真值，只有對其命題變元進行真值指派后，方可確定命題公式的真值；
3. 整個公式的最外層括號可以省略；公式中不影響運算次序的括號也可以省略。
4. 在實際應用中，為了便于存儲和運算，命題公式常用二元樹的方式來表達。

真值表

由公式 G 在其所有可能的解釋下所取真值構成的表，稱為 G 的真值表(truth table)。

真值表

5.公式的分類和邏輯等價

命題公式分類

真值表告訴我們什么？

1. 公式 G 稱為永真公式(重言式,tautology)，如果在它的所有解釋之下其真值都為“真”。
2. 公式 G 稱為永假公式(矛盾式,contradiction)，如果在它的所有解釋之下其真值都為“假”。
   有時也稱永假公式為不可滿足公式。
3. 公式 G 稱為可滿足公式(satisfiable)，如果它不是永假的。

G 是永真的當且僅當 ?G 是永假的；
G 是可滿足的當且僅當至少有一個解釋 I，使 G 在 I 下為真。
若 G 是永真式，則 G 一定是可滿足式，但反之可滿足公式不一定是永真式；

公式等價的充分必要條件

必要性：假定 G = H，則 G，H 在其任意解釋 I 下或同為真或同為假，于是由 “?” 的意義知，公式 G ? H 在其任何的解釋 I 下，其真值為“真”，即 G ? H 為永真公式。

充分性：假定公式 G ? H 是永真公式，I 是它的任意解釋，在 I 下，G ? H 為真，因此，G，H 或同為真，或同為假，由于 I 的任意性，故有 G = H。

6.基本等價關系及其應用

基本等價關系

基本等價關系

基本等價關系

基本等價關系

判斷公式類型