“永真式、可满足公式与 逻辑等价都可由真值表定义性检验。它还用于构造 CNF/DNF、检查电路和讲解联结词语义,既给出命题逻辑可判定性的直接证明,也是布尔函数的完整表示。Karnaugh 图、…”
形式陈述 ​
命题逻辑公式
直觉
永真式在每个命题赋值下都为真,因此其有效性完全来自逻辑形式,而非变量代表的具体事实;把任意具体命题代入也不会变假。它与可满足公式不同:可满足只需要一个成功赋值,永真则要求没有反例。公式
例子与边界
分配律可写成永真式
它在全部八种赋值下都为真,因此可作为任意具体命题的合法替换规则。相比之下,
推论与应用
永真式表达有效推理模式、布尔恒等式和组合电路规范。真值表可决定有限命题公式是否永真,命题可靠性与完备性保证永真式恰为可证明公式;检查
参考资料
- Daniel J. Velleman, How to Prove It: A Structured Approach, 3rd ed., Cambridge University Press, 2019,§1.2, truth tables and tautologies。
- Herbert B. Enderton, A Mathematical Introduction to Logic, 2nd ed., Academic Press, 2001,§1.2, tautologies and tautological implication。