`
somefuture
  • 浏览: 1090054 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

谓词逻辑之 等价关系证明

 
阅读更多

前面说到了谓词逻辑的一些等价关系:

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Φ 

3.(a)∀xΦ∧∀xΨ⇔∀x(Φ∧Ψ)

   (b)∃xΦ∨∃xΨ⇔∃x(Φ∨Ψ)

4.(a)∀x∀yΦ⇔∀y∀xΦ

   (b)∃x∃yΦ⇔∃y∃xΦ

 

现在来证明其中的一些,需要用到之前的命题逻辑演算规则和量词证明规则。

先来看证明的思路:证明相继式┐∀xP(x)├ ∃x┐p(x)的有效性

 这个过程比较简单:先假设相继式右边不成立(第2行),然后对一个任意变量x0假设p(x0)不成立,则得出存在一个x使得p(x)不成立(第5行,这个x起码可以是x0),但和第2行的结论冲突了,所以第4行的假设不靠谱,必须有p(x0)成立(第7行)。既然x0是任意的,那么对于所有x有P(x)成立(第8行)。但这和我们的前提冲突了,所以我们最初的假设是错误的。证明完毕。

 看明白了吧,接下来我们主要这样进行证明。

 

要证明一个等价关系,需要分别证明左边能推导出右边和右边能推导出左边。

一、证明┐∀xΦ├ ∃x┐Φ的有效性,这个和上面的过程完全一致

 证明逆∃x┐Φ├ ┐∀xΦ的有效性

 这个更简单些。不过如果不熟悉全称消去规则需要回到上一篇看看。

这样我们证明了第一个等价规则:┐∀xΦ⇔∃x┐Φ。

 

二、证明∀xΦ∧Ψ├ ∀x(Φ∧Ψ)的有效性(注意条件:x在Ψ中不是自由的)


 由于x在Ψ中不是自由的,进行代换时并不处理Ψ,因此第6行和第5行是一样的。

证明∀x(Φ∧Ψ)├ ∀xΦ∧Ψ的有效性:

 

三、证明矢列∃xΦ∨∃xΨ├∃x(Φ∨Ψ)

 证明矢列∃xΦ∨∃xΨ-|∃x(Φ∨Ψ)

 

其余等价关系类似,有兴趣可以自己尝试一下。

 

 

  • 大小: 7.5 KB
  • 大小: 7.8 KB
  • 大小: 5.1 KB
  • 大小: 6.5 KB
  • 大小: 8.9 KB
  • 大小: 7.4 KB
  • 大小: 6.9 KB
分享到:
评论

相关推荐

    人工智能导论课件:第四章 谓词逻辑与归结原理.ppt

    这些方法可以将谓词逻辑公式转化为等价的子句集,然后使用归结原理进行证明。 在人工智能领域中,谓词逻辑和归结原理有着广泛的应用,例如知识表示、自动推理、机器学习等等。它们可以用来描述复杂的关系和状态,...

    人工智能-谓词逻辑 精品资料.pptx

    SKOLEM定理是指谓词逻辑的任意公式都可以化为与之等价的前束范式,但其前束范式不唯一。SKOLEM定理可以用来解决谓词逻辑中的各种问题,如推理、证明等。 人工智能-谓词逻辑精要是人工智能领域中的一种重要技术,...

    人工智能知识表示方法谓词逻辑70 精品资料.pptx

    谓词逻辑法是人工智能中的一种基本形式语言,基于谓词分析,用于描述问题解决和定理证明。 2.1 谓词逻辑法 谓词逻辑法是数理逻辑的基本形式,是基于谓词分析的一种形式语言。它通过符号系统来表达客观对象以及相关...

    详细关于谓词逻辑的介绍

    谓词逻辑,也被称为一阶逻辑或一阶谓词演算,是一种形式逻辑系统,它扩展了命题逻辑的能力,允许我们描述更为复杂的关系和性质。在谓词逻辑中,不仅有简单的命题,还可以通过谓词和量词来表达更丰富的语义。 1. **...

    离散I讲稿\3-谓词逻辑.ppt

    在命题逻辑中,我们只能处理简单的真值命题,而在谓词逻辑中,我们可以使用谓词和量词来表达关于个体的性质和关系。 谓词是谓词逻辑中的核心概念,它们是带有零个、一个或多个参数(通常称为变量)的函数,用来描述...

    谓词逻辑与归结原理.ppt

    在谓词逻辑中,一个谓词是一个表达式,它可以描述一个个体的性质或关系。例如,"苏格拉底是人"是一个谓词,它描述了苏格拉底的性质。谓词可以是 unary(一元谓词),binary(二元谓词)或 n-ary(n元谓词),...

    人工智能知识表示方法谓词逻辑70.pptx

    谓词逻辑是知识表示方法中的一种,它可以用来描述问题求解和定理证明。谓词逻辑是数理逻辑的基本形式,是基于谓词分析的一种形式化(数学)语言。 在谓词逻辑中,基本概念包括命题、谓词、变量、函数、常量等。命题...

    离散数学谓词逻辑PPT课件.pptx

    等价式用于表示两个谓词逻辑公式在逻辑上等价,蕴含式描述了从一个公式推导出另一个公式的逻辑关系,而前束范式则是简化和标准化谓词逻辑推理的一种形式。 通过学习谓词逻辑,我们可以更精确地表达和推理关于个体和...

    人工智能-谓词逻辑.pptx

    在解决实际问题时,谓词逻辑和它的这些工具被广泛应用于知识表示、自动推理和证明等任务,特别是在人工智能的领域中,如知识库的设计、自然语言理解等。通过谓词逻辑,我们可以更准确地表达和处理复杂的逻辑关系,...

    第2章 谓词逻辑-3rd1

    谓词逻辑是形式逻辑的一个分支,它用于表达和推导涉及个体对象和关系的复杂陈述。在本章“第2章 谓词逻辑-3rd1”中,我们将深入探讨谓词逻辑的关键概念和推理规则。 首先,谓词公式是谓词逻辑的基本构建块,它们由...

    命题逻辑和谓词逻辑习题课的题目及参考答案.doc

    谓词逻辑不仅考虑了命题的真假性,还引入了谓词、量词等概念来更精确地表达事物之间的关系。 3. **合式公式**(Well-formed Formula, WFF):谓词逻辑或命题逻辑中符合一定语法结构的表达式。 4. **量词**:分为...

    知识的一阶谓词逻辑表示法学习教案.pptx

    【一阶谓词逻辑表示法】是一门深入探讨人工智能领域中知识表示的重要技术。它是一种形式化的语言系统,用于精确地描述和处理复杂的概念、关系和事实。在人工智能中,一阶谓词逻辑被广泛应用于知识表示、推理和决策...

    人工智能第2章(知识表示方法3-谓词逻辑)74.pptx

    谓词逻辑,也称为一阶逻辑或一阶谓词演算,是数理逻辑的核心部分,主要用于形式化地表示和推理复杂的关系和属性。在人工智能领域,谓词逻辑被广泛应用于知识表示,以便准确地描述和处理现实世界中的复杂情况。 在...

    数学谓词逻辑PPT学习教案.pptx

    数学谓词逻辑是逻辑学的一个重要分支,主要研究如何用符号表示和推理关于对象及其性质的命题。在本PPT学习教案中,我们将探讨数学谓词逻辑中的前束范式和斯科伦范式,以及自由变量的代入规则。 首先,前束范式...

    离散数学复习题.docx

    在本文中,我们将对谓词逻辑的相关知识点进行总结和分析,包括谓词公式的构成、量词的应用、自由变元和约束变元的定义、谓词公式的等价式的证明等。 三、集合论 集合论是研究集合的数学模型和方法论的数学分支。...

    人工智能逻辑ppt课件

    谓词逻辑的演算律包括推理规则和等价规则,如蕴含引入和消除、重言式等。这些规则提供了推导新真理和验证已有命题有效性的工具,是谓词逻辑推理的基础。 2.4 非二值逻辑 非二值逻辑是对传统命题逻辑和谓词逻辑的...

    Propositional and Predicate Calculus: A Model of Argument

    - **形式化证明**:在数学证明和理论计算机科学中,谓词逻辑是构造严谨证明的基础。 #### 四、结论 《命题与谓词逻辑:一种论证模型》这本书全面介绍了数学逻辑的两个核心分支——命题逻辑和谓词逻辑,并通过丰富...

    数理逻辑讲义 20220411.zip

    综上所述,这些讲义涵盖了数理逻辑的核心概念,从简单的命题逻辑逐步深入到谓词逻辑,然后探讨了公理系统、数字逻辑的基础以及逻辑系统的可靠性与完备性问题,为理解形式推理和数学证明的逻辑基础提供了全面的框架。

    论文研究-并发系统中谓词行为图的行为时序逻辑表达.pdf

    介绍行为时序逻辑的语法、语义及简单推理规则, 用一个简单的实例说明使用谓词行为图去描述并发转移系统的有效性, 并用系统规约的TLA公式对谓词行为图表达能力进行证明, 表明两者具有等价性, 为描述和分析并发转换...

Global site tag (gtag.js) - Google Analytics