命题逻辑基础

命题

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

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

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

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

命题逻辑中的基本联结词

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

真值表

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

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

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

命题逻辑的等值演算

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

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

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

析取范式、合取范式

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

• 有限个合取式的析取称为析取范式，如 (p_1\wedge q_1)\vee(p_2\wedge q_2)\vee ... \vee(p_n\wedge q_n);
• 有限个析取式的合取称为合取范式，如 (p_1\vee q_1)\wedge(p_2\vee q_2)\wedge ... \wedge(p_n\vee 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. 找出使 p\rightarrow q 为真的小项，将它们析取 同理若求主合取则先写大项，写大项的成假赋值，找出使 p\rightarrow q 为假的小项，将它们合取

故主析取范式为：

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

法二：等值演算法(常用) 左边 = p\rightarrow q <=> \neg p \vee q<=> (\neg p \wedge \color{red}{(q\vee \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 ((p\rightarrow q)\wedge \neg (\neg q \vee \neg p)) 的主合取范式 proof: 左边 =p \rightarrow ((p\rightarrow q)\wedge \neg (\neg q \vee \neg p)) <=> \neg p \vee ((\neg p \vee q)\wedge (q\wedge 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(p\wedge q)
• S_8 = {\downarrow} 或非 p \downarrow q <=> \neg(p \vee q)

来看一个对应知识的例题 例 3：将 p\rightarrow q 分别化成上述 S_4,S_5,S_7,S_8 集合上的公式 Proof: p\rightarrow q <=> \neg p \vee qS_5 <=> \neg\neg(\neg p \vee q)<=> \neg(p \wedge \neg q)S_4 <=> p\uparrow \neg q<=>p\uparrow(\neg q\vee \neg q)<=>p\uparrow\neg(q\wedge q)<=>p\uparrow(q\uparrow q)S_7 p\rightarrow q<=>\neg\neg(\neg p\vee q)<=>\neg(\neg p\downarrow q)<=>\neg(p\downarrow p\downarrow q)<=>(p\downarrow p\downarrow q)\downarrow(p\downarrow p\downarrow q)S_8