笔记 逻辑学导论 命题归结

课程地址 https://class.coursera.org/intrologic-003/class/index

命题归结Propositional Resolution是命题逻辑中非常给力的推理规则。

1 Clausal Form 子句形式

命题归结只对子句形式的表达适用,因此在使用之前必须将前提和结论转化成子句形式。
一些概念:
一个literal字符可以是一个不可以再分割的原子语句atomic sentence,也可以是一个原子语句的否定。如p和¬p
一个子句表达clause expression可以是一个字符也可以是字符的相与。如¬p V  q
一个子句是用集合包含子句表达中的字符后得到接形式。如{¬p, q}
转化的一般过程为I、N、D、O
  • I:Implication Out
    I
  • N:Negation
    N
  • D: Distribution
    D
  • O: Operators
    O
一个转化示例:
Ex1

2归结规则 Resolution Principle

如果给定一个子句中包含chi并且知道另一个子句中包含chi的否定,则根据归结规则可将两个子句合并起来并同时去除chi和chi的否定。
prrp

3 示例:

给定子句{¬p, r}{¬q,r}{p,q}是否可以推导出结论{r}?
Ex2
4不可满足定理
当且仅当Δ 与 {¬φ}的交集是无法满足的时候Δ |= φ
可以将Δ ∪ {¬φ}写成子句模式,然后看是否能够归结出空集{},如果可以,则表示确实无法满足。

Leave a Reply

Your email address will not be published. Required fields are marked *