真值表

一行可以看作一次独立的输入测试，但整张表与抽样测试不同：有限个布尔输入的所有组合已经列完，因而没有遗漏的情形。每个变元在同一行中的值固定，重复出现多少次都不能另作选择。括号确定计算顺序，先填较小子公式，可以避免把不同语法结构误算成同一式子。

真值表只读取原子命题的真假，不解释它们之间可能存在的数学约束。例如把“$x=0$”和“$x=1$”分别记为 $p,q$ 后，纯命题表仍会列出 $p,q$ 同真一行；这一行在实数语境中无法实现，却是检验命题形式本身是否永真时必须考虑的赋值。

蕴含的四种输入 ​

比较 $p\to q$ 与 $\mathrm{\neg }p\vee q$：

以第三行为例：先固定 $p$ 假、$q$ 真，计算得 $\mathrm{\neg }p$ 真，再计算“真或真”为真；另一列的蕴含因前件假也为真。对其他三行执行同样的自下而上计算，最后两列一致，因此两式等价。唯一使蕴含为假的情形是前件成立而后件失败。这个定义不表达因果关系；当前件为假时，蕴含为真，也不能据此反推前件。

例如从 $p\to q$ 与 $q$ 推出 $p$ 的推理无效：第三行使两个前提都真，结论却假。有效推理要求不存在“所有前提真而结论假”的行，不要求结论在每一行都为真。

穷举范围与计算代价 ​

$p\vee \mathrm{\neg }p$ 两行全真，$p\wedge \mathrm{\neg }p$ 两行全假；两式虽然各出现两次 $p$，仍各只需两行。一个长度为 $m$、含 $n$ 个不同变元的公式可在每行按语法树计算，完整穷举所需时间量级为 $O(m{2}^n)$。流式处理时只需保留当前行，指数行数并不强制指数工作内存。

一阶量词还需要指定论域与符号解释，不能直接用有限命题真值表穷尽任意结构。对已给定的有限论域，才可以将量词展开成有限合取或析取后再使用这种方法。

永真式理路永真式Tautology · Valid propositional formula在每个真值赋值下均为真的命题公式。要求每行真，可满足公式理路可满足公式Satisfiable formula存在至少一个真值赋值使其为真的命题公式。只要求存在一行真，逻辑等价理路逻辑等价Logical equivalence两个公式在指定语义类的每个结构与赋值下具有相同真值。则比较两列是否处处一致。三项检查的量词不同，不应混为一谈。

真值表还给出析取范式（DNF）的直接构造。对每一真行，把取真的变元原样写出、取假的变元加否定，然后用“且”连接。这一项恰好只在该行成立；把各真行对应的项用“或”连接，就恢复原公式。例如异或的真行为“真假”和“假真”，故得到 $(p\wedge \mathrm{\neg }q)\vee (\mathrm{\neg }p\wedge q)$。

合取范式（CNF）则逐个排除假行。异或的假行为“真真”和“假假”：前者对应只在该行失败的子句 $\mathrm{\neg }p\vee \mathrm{\neg }q$，后者对应 $p\vee q$；把它们合取，便得 $(\mathrm{\neg }p\vee \mathrm{\neg }q)\wedge (p\vee q)$。这里从假行生成文字时，取反规则与 DNF 相反。

电路检查、Karnaugh 图、BDD 与 SAT 求解器共享这些布尔语义，但后几种表示或搜索方法可在许多实例上避免展开全部行。