一、命题逻辑 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）

二、命题等价性 Propositional Equivalence

1. 逻辑等价性的概念

1. 定义： $A$、 $B$ 是逻辑等价的，若 $A\leftrightarrow B$ 恒真。
2. 示例

   • 原命题 $p\rightarrow q$ 与它的反命题（Converse） $q\rightarrow p$ 不是逻辑等价的

   • 原命题与它的逆否命题（Contrapositive）是逻辑等价的

     $$ p\rightarrow q \Leftrightarrow \neg q\rightarrow \neg p $$

2. 重要的等价关系