離散數學 第一章 命題邏輯

1.1 命題與邏輯連接詞1.1.1 命題

能夠判斷結論真假的陳述句
真值可隨條件變化
悖論不是命題
分類（原子命題、複合命題）

1.1.2 邏輯聯結詞及完備集

{∧,∨,～}同其它聯結詞
P▽Q ⟺ (～P∧Q)∨(～Q∧P)
P→Q ⟺ ～P∨Q
P↔Q ⟺ (P→Q)∧(Q→P)
P↑P ⟺ ～P
(P↑Q)↑(P↑Q) ⟺ P∧Q
(P↑P)↑(Q↑Q) ⟺ P∨Q
P↓P ⟺ ～P
(P↓Q)↓(P↓Q) ⟺ P∨Q
(P↓P)↓(Q↓Q) ⟺ P∧Q

功能完備集和最小功能完備集
功能完備集：S為聯結詞構成的集合，每個邏輯聯結詞的功能能由S中聯結詞實現。
最小功能完備集：S中去掉任意一個聯結詞後，至少有一個聯結詞的功能不能由S中剩餘聯結詞實現。
{↑}/ {↓}/ {～, ∨}/ {～, ∧}/ {～, →}/ {～, ⇢}

1.2 命題公式及其賦值1.2.1 命題常元和命題變元

命題常元：T/F
命題變元：字母表示/值域為『真/假』

1.2.2 命題公式/合適公式

組成：命題變元/邏輯聯結詞/括號

注意：
原子命題變元是公式
若P、Q是公式，則把P、Q用邏輯聯結詞聯繫起來也是公式
有限運用以上兩條生成的命題表達式是公式
若公式的字串P也是公式，則P為子公式

真值指派：給公式的所有變元各指定一個真值
真值表：公式的全部解釋

命題公式的類型
永真式（重言式）：真值表全為1
矛盾式（永假式）：真值表全為0
可滿足公式：真值表有1有0

1.3 命題公式的等價1.3.1 含義

真值表相同，用⟺表示

1.3.2 基本等價式

1.3.3 等價的判斷和性質

判斷：

⟺與↔
A、B是命題公式，A⟺B當僅A↔B

對偶原理
對偶式：公式A僅有聯結詞∧,∨,～。將∧,∨,T, F分別用∨, ∧, F, T替換獲得A*，則A*為A的對偶式。
注意：對偶式括號的優先順序不變

~A(P1, P2, …, Pn)⟺A*(~P1, ~P2,…, ~Pn)

A⟺B可得A⟺B

性質：

A⟺A

A⟺B ⇨ B⟺A

A⟺B, B⟺C ⇨ A⟺C

1.4 公式的範式表示1.4.1 相關概念

句節：原子公式及其否定

有限析取

有限合取

有限合取

極大項

有限析取

極小項

句節

子句

短語

合取範式

主合取範式

析取範式

主析取範式

任何命題公式都存在與之等價的析取範式和合取範式，永真式無主合取範式，矛盾式無主析取範式。

任何極大/小項都不是相互等價的

主合取範式和主析取範式唯一

1.4.2 主範式構造方法

真值表法
列出每個極大項/極小項，表示出對應公式（類似基向量線性組合）

公式的恆等變換法
將聯結詞全部轉換為∧, ∨, ～
運用等價變換變為析取範式或合取範式，並化簡
如果字母不夠，補上對應數量的T/F然後用P和～P表示，用分配律展開

1.5 命題公式的蘊涵1.5.1 含義

A取1時B也取1，用A⇒B表示

1.5.1 基本蘊涵式

1.5.2 蘊涵的判斷與性質

判斷：

A、B是命題公式，A⇒B當僅A→B

性質：

A⇒A

A⇒B, B⇒A ⇨ A⟺B

A⇒C, B⇒C ⇨ A⇒C

A⇒B, A⇒C iff A⇒(B∧C)

A⇒C, B⇒C ⇨ (A∧B)⇒C

(A∧B)⇒C iff A⇒(B→C)

A⇒B iff ～B⇒～A

A⇒B ⇨ A∧C⇒B∧C

1.6 命題公式的推理方法1.6.1 定義

若A1∧A2∧ … ∧An⇒B，則稱B為前提A1, A2, … , An的有效結論或邏輯結果
G: A1, A2, … ,An( = B)，則B是G的邏輯結果，G演繹出了B

注意：推理正確不等於結論為真

1.6.2 推理規則

蘊涵式

恆等式

P規則：推導過程中可隨時引入前提集合中的任意一個前提及附加前提

T規則：推導過程中經等價變換或者蘊涵得到的新公式可以隨時用於推理

CP規則：A1, A2, … ,An ⇒ B→C iff A1, A2, … ,An, B ⇒ C

合取引入規則：A, B⇒A∧B

1.6.3 推理方法

直接證明法
利用等價式或蘊涵式

CP規則推理法

反證法
A1, A2, … ,An ⇒ B ⇨ A1∧A2∧ … ∧An∧～B ⇒ F

消解原理
C1 = A∨B, C2 = ～A∧D,
((A∨B), (～A∧D)) ⇒ B∨D\

主範式法
寫出主合取範式，用簡化法則判斷是否蘊涵