一、命题逻辑 Proposition Logic

1. 命题 Proposition

1. 命题的定义：或为真、或为假的陈述（statement）
   • 命题必须为陈述，因此疑问句不能作为命题
   • 用小写字母表示命题： $p,q,r,…$
2. 可分为原子命题（Atom）和复合命题（Compound）
   • 原子命题：在结构上不能再分解出其他命题
   • 复合命题：由原子命题结合而成

2. 逻辑运算符 Logical Operators

1. Negation（非）
   • 符号： $\neg p$
2. Conjunction（与，合取）
   • 符号： $p\land q$
3. Disjunction（或，析取）
   • 符号： $p\lor q$
   • “或”的两重解释：
     • 包含或（Inclusive Or）：两者至少一者为真，则结果为真（本处所指的含义）
     • 互斥或（Exclusive Or）：两者有且只有一者为真，则结果为真（又称“异或”，用 $\oplus$ 表示）
4. Implication（蕴含）

   • 符号： $p\rightarrow q$

   • 含义：若 p 成立，则 q 必定成立

   • 称呼：

     • 称 p 为 hypothesis（假设）或 premise（前提）
     • 称 q 为 conclusion（结论）或 consequence（结果）

   • 真值表：

     

   • 常用称法

     if p then q	如果 p 成立，则 q 成立
     p is sufficient for q	p 是 q 的充分条件
     p implies q	p 揭示了 q
     p only if q	p 成立，只有当 q 成立时
     q is necessary for p	q 是 p 的必要条件
     if q whenever p	q 成立，每当 p 成立

     示例（p 和 q 的先后判断）：

     

   • Everything implies truth, False implies Everything.

     示例：

     

5. Bioconditional（等价）

   • 符号： $p\leftrightarrow q$

   • 含义：当且仅当 p 和 q 的真值相同时，该式为真

   • 真值表：

     

3. 命题公式 Proposition Formula

1. 命题公式的定义

   

2. 优先级

   • 第一优先级： $\neg$
   • 第二优先级： $\land , \lor$
   • 第三优先级： $\rightarrow , \leftrightarrow$

3. 命题公式的分类

   • 恒真式（Tautology）
   • 恒假式（Contradiction）
   • 或真或假式（Contigence）

4. 命题的规范形式 Propositional Normal Forms

1. 命题的规范形式有两种：

   • Disjunctive Normal Form（DNF，析取形式）
   • Conjunctive Normal Form（CNF，合取形式，不使用）

2. 析取形式

   • 定义：每个局部为与关系，局部与局部之间是或关系

     • 字面量（Literal）是一个变量或它的取反
     • 析取形式是指由析取（或运算） 连接的合取项（与运算）组成的逻辑表达式

   • 基本形式

     $(A_1\land A_2\land … \land A_m)\lor (B_1\land B_2\land … \land B_n) \lor …$

     （其中，每个 $A_i、B_i$ 都是字面量）

   • 定理：任一命题公式一定与一个以析取形式表述的命题公式逻辑等价

   示例：

   

3. 将表达式转化为析取形式

   • 使用以下二式，将蕴含和等价关系转化为与、或、非关系

   

   • 使用双重否定为肯定的规律，以及狄摩根定律，处理括号外面的取反操作
   • 使用分布律

   示例：

   

4. 全析取形式（Full Disjunctive Form）

   • 定义
     • 全析取形式是一种严格的析取形式，它确保每个合取项都包含所有变量（即所有变量都出现一次，要么是原变量，要么是其否定）
     • 满足上述定义条件的合取项称为最小项（minterm）
   • 最小项的性质

     • 若 $A、B$ 是两个不同的最小项，则 $A\land B \Leftrightarrow F$

     • 最小项用符号 $m_i$ 表示，注意 i 的二进制形式与 $m_i$ 的表达式形式的联系