概念

命题逻辑

研究由联结词（与、或、非、蕴涵）组成的命题复合规则，核心工具是真值表、等值演算与主析取/主合取范式。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

已是本主题的起点

命题逻辑逻辑与集合论

01定义

命题逻辑研究由联结词（与、或、非、蕴涵）复合而成的命题：真值表给出语义，等值演算给出化简，主范式给出标准形。它是形式推理的最底层，也是数字电路的代数原型。

蕴涵 P→Q 的真值表：唯一为假的情形是 P 真而 Q 假

$\neg, \wedge, \vee, \to, \leftrightarrow$ 五种联结词由真值表定义；任何真值函数都可由 $\{\neg,\wedge\}$ 表达（功能完备）。

德摩根律、分配律、吸收律等构成化简工具箱；两公式等值当且仅当它们的真值表完全一致。

主析取/主合取范式给出公式的「标准指纹」；命题逻辑是可判定的（真值表穷举），但 SAT 问题是 NP 完全的——判定容易、高效难。

P\to Q\equiv\neg P\vee Q

\neg(P\wedge Q)\equiv\neg P\vee\neg Q\quad(\text{德摩根})

斯多葛学派已研究命题推理；弗雷格 1879 年《概念文字》创立现代命题与谓词演算；真值表方法由维特根斯坦与 Post 在 1920 年代普及。

数字电路的逻辑门设计、程序中的条件判断化简、SAT 求解器（软件验证与芯片设计的核心引擎）都建立在命题逻辑之上。

命题逻辑真值表切换联结词：p∧q / p∨q / p→q / p↔q 的真值

联结词2