2020-06-24 命题逻辑符号

做一个命题逻辑的总结：

看了好多资料还是晕 :(

Entailment 蕴含式

符号：|=

S entails P (S|=P) if whenever all formulae in S are True, P is True.

当条件S中的所有项为真，P必定为真。但是，P为真的时候，S未必全为真。

判断方式：真值表

Proof 证明

符号：|-

φ1,φ2,…,φn |- ψ

这就叫一次推理.其中 φi 叫做前提(premise), ψ 叫做结论(conclusion)。

推理需要满足 命题逻辑的自然推导规则

---

对于proof system:

Soundness 可靠性

可靠性定理：令 φ1, φ2, …, φn和 ψ 为命题逻辑中的公式，如果 φ1, φ2, …, φn|- ψ 是有效的， 那么 φ1, φ2, …, φn|= ψ 是有效的。

Whenever S ⊢ P, S |= P

Completeness 完备性

完备性定理：令 φ1, φ2, …, φn和 ψ 为命题逻辑中的公式，如果 φ1, φ2, …, φn|= ψ 是有效的， 那么 φ1, φ2, …, φn|- ψ 是有效的。

Whenever S |= P, S ⊢ P

decidable 可判定的（没找到这个中文叫什么）

A proof systemis decidable if there is a mechanical procedure (computer program) which when asked whether S ⊢ P,can always answer‘yes’– or‘no’ –correctly.

对于一个证明系统，其推理过程可以利用计算机程序判断出是否正确时，这个系统就是可判定的。

参考资料：https://blog.csdn.net/on_1y/article/details/8727346

---

Normal Forms 范式

Conjunctive Normal Form( CNF) 合取范式

子句用 and 连接

当且仅当它是一个或多个文字的一个或多个析取的合取

Disconjunctive Normal Form( DNF) 析取范式

子句用 or 连接

当且仅当它是一个或多个文字的一个或多个合取的析取