前面我们说过 “不是所有的鸟都会飞”用谓词逻辑表示有两种方式:
B(x):x是一只鸟
F(x):x可以飞翔
这个语句就可以编码为:﹁(∀xB(x)→ F(x))
换而言之“只要是鸟就会飞,这种情况是不成立的”,上句话也可以编码为:∃ x(B(x) ∧﹁F(x) )
所以可知,在某些量词形式之间存在着语义的等价。本节就对其中的一些最常见和最常用的量词等价给出证明。
定理: 设Φ和Ψ是谓词逻辑公式,则具有下面的等价关系:
1.(a) ┐∀xΦ⇔∃x┐Φ
(b) ┐∃xΦ⇔∀x┐Φ
这两条比较好理解。
2.假设x在Ψ中不是自由的,那么:
(a)∀xΦ∧Ψ⇔∀x(Φ∧Ψ)
(b)∀xΦ∨Ψ⇔∀x(Φ∨Ψ)
(c)∃xΦ∧Ψ⇔∃x(Φ∧Ψ)
(d)∃xΦ∨Ψ⇔∃x(Φ∨Ψ)
(e)∀x(Ψ→Φ)⇔Ψ→∀xΦ
(f) ∃x(Φ→Ψ)⇔∀xΦ→Ψ
(g)∀x(Φ→Ψ)⇔∃xΦ→Ψ
(h)∃x(Ψ→Φ)⇔Ψ→∃xΦ
这里出现了一个概念:自由变量。这是一个和谓词逻辑公式语法树相关联的概念,还记得语法树的概念吗?
引入量词后,语法树变化并不大。下面是(∀x(P(x) ∧ Q(x))) -> (┐P(x) ∨ Q(y))的语法树:
如果x是Φ的语法分析树中的一个叶结点,而且不存在从结点x到∀x或∃x的向上路径就称x的出现是自由的。否则,称x的出现是约束的。对∀xΦ或∃xΦ,我们称除去Φ的任何形如∀x或∃x的子公式的Φ分别是∀x或∃x的作用范围。那么你能说出上面这个语法树中哪个变量是自由的哪个是约束的吗?
3.(a)∀xΦ∧∀xΨ⇔∀x(Φ∧Ψ)
(b)∃xΦ∨∃xΨ⇔∃x(Φ∨Ψ)
4.(a)∀x∀yΦ⇔∀y∀xΦ
(b)∃x∃yΦ⇔∃y∃xΦ
看完这些等价公式,有没有感觉很自然。不过即使这样,我们也需要证明它们。
证明就需要用到量词的演算规则:
(1)等价关系规则
等价引入规则,不需要前提,一个变量总是和它自身相等
等价消去规则,使用了代换。说一下代换的概念:
给定变量x、项t和公式Φ,定义Φ[t/x]为用t代替Φ中的变量x的每个自由出现而得到的公式。
变量只是占位符,我们需用更具体的信息代替它,使其具有某种含义。从语法角度来讲,我们常用一个完全项t的语法分析树去代换叶结点x。由公式的定义,对x的代换只能是项,不会是谓词表达式,或者更复杂的公式,因为x只作为谓词符号的变量出现。切记在用t代换x时,必须避开那些受约束的变量x,因为它们处在某个∀x或∃x的作用范围,分别表示某些非特指的或所有的值。
此种变量代换也会产生意外副作用,如果t包含变量y,x在Φ中的自由出现处于Φ中∀x 或∃x的作用范围内。这种预料之外的变量捕捉是无论如何要避免的。
比如:考虑下图分析树公式Φ,并令t是f(y,y)。x在Φ中的两次出现全是自由的,出现在最左端的x可以被代换,因为它不在任何量词的作用范围之内。但是最右端叶结点x会引入一个t中的新变量y,它被∀y约束,所以f(y,y)对Φ中的x不是自由的。
(2)全称量词消去规则
全称量词引入规则
(3)存在量词引入规则
存在量词消去规则
这一篇说到这,其中概念很多,理解上也比较难。
下一篇需要用到刚说的量词证明规则和前面的命题演算规则对等价关系进行证明。
相关推荐
加深对归结原理进行定理证明过程的理解,掌握基于谓词逻辑的归结过程中子句变换过程、替换与合一算法即归结策略等重要环节,进一步了解实 现机器自动定理证明的步骤。 采用C++
人工智能课件,关于谓词逻辑与归结原理,在学习了离散数学的基础上,进一步深入的学习谓词逻辑,掌握人工智能的初步知识
人工智能谓词逻辑归结问题的推理系统是很好的学习资料 ,可以帮助广大学子进一步学习人工智能的相关知识。
对命题逻辑和谓词逻辑的核心归纳可以做到一目了然
谓词逻辑离散数学
命题逻辑与谓词逻辑PPT课件.pptx
人工智能的实验题目。输入一组合适公式,以及一个目标子句,输出归结树。 我奋斗了几乎5天总算弄出来了,放过bin出来show一下^_^。 至于代码,想要的可以联系我。 这里给出一个测试用例吧: ;假设:所有不贫穷且...
用于人工智能的学习,内容全面,人工智能 谓词逻辑
谓词逻辑推理,人工智能的基本理论,为人工智能系统的开发奠定了一定的理论基础
离散数学 谓词逻辑 PPT 基础 有用 好好学习
东北大学 离散数学课件 谓词逻辑 保证很详细哦
第 2 章谓词逻辑命题逻辑对于反映在自然语言中的逻辑思维进行了精确的形式化描述,能够对一些比较复杂的逻辑推理,用形式化方法进行分析。在命题逻辑中,把命题分解到原
离散数学 谓词逻辑 习题课PPT课件.pptx
课件主要简介离散数学的谓词逻辑,帮助我们更好理解这章内容,除此之外,也使学生从逻辑的角度了解数学
人工智能课件:第三章 谓词逻辑与搜索原理.pdf
第2章(知识表示方法3-谓词逻辑)
人工智能导论课件:第四章 谓词逻辑与归结原理.ppt
这是我的文章的第三章的第二节,因为有公式没法发,直接放这里了。
离散数学之谓词逻辑.ppt
离散数学第二章谓词逻辑,非常好的资源,欢迎下载