形式陈述

对只含有限多个命题变量 $p_1,\ldots,p_n$$p_1,\dots ,p_n$ 的命题公式，真值表列出全部 $2^n$$2^n$ 个赋值 $v:\{p_1,\ldots,p_n\}\to\{\bot,\top\}$$v:\{p_1,\dots ,p_n\}\to \{\mathrm{\perp },\mathrm{\top }\}$，并按联结词的真值函数递归计算每个子公式和整式的值。例如

$$ v(\neg\varphi)=\neg v(\varphi),\qquad v(\varphi\land\psi)=v(\varphi)\land v(\psi). $$$$v(\mathrm{\neg }\phi )=\mathrm{\neg }v(\phi ),v(\phi \wedge \psi )=v(\phi )\wedge v(\psi ).$$

表的每一行对应一个完整赋值。整式列全真表示永真，全假表示不可满足，真假兼有表示偶然式。真值表是命题语义的有限穷举判定过程。

直觉

把所有可能世界逐行列完，再机械执行公式中的布尔运算；没有遗漏赋值时，最后一列就完整刻画公式的语义。

例子与边界

$p\lor\neg p$$p\vee \mathrm{\neg }p$ 的两行都为真；$p\land\neg p$$p\wedge \mathrm{\neg }p$ 的两行都为假。含 $n$$n$ 个实际出现变量的公式需要 $2^n$$2^n$ 行，而不是按语言中所有潜在变量计数。变量重复出现必须在同一行取相同值。真值表能判定命题公式，但指数行数使它不等于高效 SAT 算法，也不能直接穷举含无限论域量词的一阶语义。

推论与应用

真值表用于验证逻辑等价、构造 CNF/DNF、检查电路和教授联结词语义。它给命题逻辑可判定性的直接证明，并是布尔函数完整表示的一种形式。

参考资料

• Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019，§1.2, truth tables。
• Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed., Academic Press, 2001，§1.2, truth assignments and tautological implication。