命题逻辑基础

命题

命题：能判断真假的陈述句

• 命题常量：p：小明是个男生(已指定了命题)
• 命题变量：p：（未指定命题）

真值： 真，假 命题分类： 真命题、假命题、简单命题(原子命题)、复合命题 命题公式：

• 重言式：真值恒为 1（永真式）
• 矛盾式：真值恒为 0（永假式）
• 可满足式：不是矛盾式的都是

命题逻辑中的基本联结词

neg : 否定（非） wedge : 合取（与） vee : 析取（或） rightarrow : 蕴含（if ... then ...） leftrightarrow: 等价(当且仅当)

真值表

与或非的简单真值表就不再赘述了，主要看蕴含和等价

例: 判断公式 pwedge r wedge neg(qrightarrow p) 的类型（真值表法）

故该式为矛盾式（永假式） 例 0：求公式 (neg p wedge q)rightarrow neg r 的成真赋值和成假赋值（同上，真值表法）

命题逻辑的等值演算

等值式：若 Aleftrightarrow B 是重言式，则可称 A 和 B 等值，记作 A<=>B

• 交换律：Avee B <=> Bvee A; Awedge B <=> Bwedge A
• 结合律：(Avee B)vee C <=> Avee (Bvee C)
• 分配律：Avee (Bwedge C)<=>(Avee B)wedge (Avee C)
• 双重否定律：negneg A <=> A
• 等幂律：A<=>Avee A;A<=>Awedge A
• 摩根律：neg (Avee B)<=>neg A wedge neg B;neg(Awedge B)<=>neg Avee neg B
• 吸收律：Avee (Awedge B)<=>A;Awedge (Avee B)<=>A
• 同一律：Avee 0<=>A; Awedge 1 <=> A
• 零律：Avee 1 <=> 1;Awedge 0<=>0
• 排中律：Avee neg A<=>1
• 矛盾律：Awedge neg A<=>0
• 蕴含等值式：A rightarrow B <=> neg Avee B
• 等价等值式：Aleftrightarrow B<=>(Arightarrow B)wedge (Brightarrow A)
• 假言易位式：Arightarrow B <=> neg Brightarrow neg A
• 等价否定等值式：A leftrightarrow B <=> neg A leftrightarrow neg B
• 归谬论：(Arightarrow B)wedge (Arightarrow neg B)<=>neg A

牢记上述基本等值式，以用来进行对复杂等值式的等值演算，比如现在我们用上述公式来证明一下归谬论：

析取范式、合取范式

def1: p 为任意命题变量，则 p 和 neg p 称为 文字 def2: 有限个文字的析取称为析取式；有限个文字的合取称为合取式 def3:

• 有限个合取式的析取称为析取范式，如 (p_1wedge q_1)vee(p_2wedge q_2)vee ... vee(p_nwedge q_n);
• 有限个析取式的合取称为合取范式，如 (p_1vee q_1)wedge(p_2vee q_2)wedge ... wedge(p_nvee q_n);

主析取范式、主合取范式

def1: 含有 n 个命题变量的 合取式 G(p_1,p_2,...,p_n) 若每个 p_i 和 neg p_i 出现且仅出现一次，而且出现次序与 p_1,p_2,...,p_n 的次序保持一致，则称该式 G(p_1,p_2,...,p_n) 为一个 小项 。而对于一个 析取范式 A_1 vee A_2 vee ... vee A_n, 若其中的每一个合取范式 A_i 都是 小项 ，则称该析取范式为 主析取范式。

def2: 含有 n 个命题变量的 析取式 G(p_1,p_2,...,p_n) 若每个 p_i 和 neg p_i 出现且仅出现一次，而且出现次序与 p_1,p_2,...,p_n 的次序保持一致，则称该式 G(p_1,p_2,...,p_n) 为一个 大项 。而对于一个 合取范式 A_1 wedge A_2 wedge ... wedge A_n, 若其中的每一个析取范式 A_i 都是 大项 ，则称该析取范式为 主合取范式。 结合例子来学习上述定义：

例 1：求 p rightarrow q 的主合取范式和主析取范式

法一：真值表法（不妨先求主析取）

1. 先写小项
2. 写小项的成真赋值
3. 找出使 prightarrow q 为真的小项，将它们析取 同理若求主合取则先写大项，写大项的成假赋值，找出使 prightarrow q 为假的小项，将它们合取

故主析取范式为：

主合取范式为：(找 prightarrow q 为假时的小项对应的大项再将它们合取)

法二：等值演算法(常用) 左边 = prightarrow q <=> neg p vee q<=> (neg p wedge color{red}{(qvee neg q)})vee (color{red}{(p vee neg p)}wedge q)<=> color{green}{(neg p wedge q)}vee(neg p wedge neg q)vee(p wedge q)vee color{green}{(neg p wedge q)}<=> color{green}{(neg p wedge q)}vee(neg p wedge neg q)vee(p wedge q)

再看一个稍微复杂点的例子 例 2：求 p rightarrow ((prightarrow q)wedge neg (neg q vee neg p)) 的主合取范式 proof: 左边 =p rightarrow ((prightarrow q)wedge neg (neg q vee neg p)) <=> neg p vee ((neg p vee q)wedge (qwedge p))<=> (neg p vee(neg p vee q))wedge (neg p vee (q wedge p))<=> (neg p vee q)wedge (neg p vee q)wedge (neg p vee p)<=> (neg p vee q)wedge (neg p vee q)<=>(neg p vee q)

联结词的完备集 $(neg vee wedge rightarrow leftrightarrow)$

def: S 是一个联结词集合，若任意一个命题公式都可以由 S 中的额联结词表示出来且命题公式与之等价，则称 S 为一个联结词的 完备集。 Th: 以下联结词的集合都是一个联结词完备集：

• S_1 = {neg, vee, wedge}
• S_2 = {neg, vee, wedge, rightarrow}
• S_3 = {neg, vee, wedge, rightarrow, leftrightarrow}
• S_4 = {neg, wedge}
• S_5 = {neg, vee}
• S_6 = {neg, rightarrow}
• S_7 = {uparrow} 与非 p uparrow q <=> neg(pwedge q)
• S_8 = {downarrow} 或非 p downarrow q <=> neg(p vee q)

来看一个对应知识的例题 例 3：将 prightarrow q 分别化成上述 S_4,S_5,S_7,S_8 集合上的公式 Proof: prightarrow q <=> neg p vee qS_5 <=> negneg(neg p vee q)<=> neg(p wedge neg q)S_4 <=> puparrow neg q<=>puparrow(neg qvee neg q)<=>puparrowneg(qwedge q)<=>puparrow(quparrow q)S_7 prightarrow q<=>negneg(neg pvee q)<=>neg(neg pdownarrow q)<=>neg(pdownarrow pdownarrow q)<=>(pdownarrow pdownarrow q)downarrow(pdownarrow pdownarrow q)S_8