形式陈述

从命题变量和联结词 $\neg,\land,\lor,\to$$\mathrm{\neg },\wedge ,\vee ,\to$ 递归生成公式。真值赋值 $v$$v$ 把变量映到 $\{0,1\}$$\{0,1\}$，并按联结词的真值函数扩张到全部公式。若公式 $\varphi$$\phi$ 在所有赋值下为真，记作 $\models\varphi$$\models \phi$。

直觉

它忽略命题内部结构，只研究“整句话真假如何组合”。真值表提供了有限、机械的语义检查方法。

例子与边界

$P\lor\neg P$$P\vee \mathrm{\neg }P$ 是重言式；$P\land\neg P$$P\wedge \mathrm{\neg }P$ 不可满足。命题逻辑不能表达“所有对象”或“存在某个对象”，这些量化结构需要一阶逻辑。

推论与应用

命题逻辑支撑布尔电路、SAT 求解、数字电路验证以及程序条件表达式的推理。

参考资料

• Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed., §1.1–1.3.
• Michael Huth and Mark Ryan, Logic in Computer Science, 2nd ed., Chapter 1.