离散数学

您所在的位置:网站首页 离散数学e规则 离散数学

离散数学

2024-01-12 02:28| 来源: 网络整理| 查看: 265

一阶逻辑等值式

一阶逻辑等值式除了前面的十六组二十四个等值式之外,在引入量词之后,进而有了几组量词相关的等值式,下面对其作重点介绍。

1、量词否定等值式

(1)  ¬∀xA(x)  ∃x¬A(x)

(等值符号我不会打,只能用来代替,请见谅)

(2)  ¬∃xA(x)  ∀x¬A(x)

记住等值式并且会运用的前提是理解,不仅要会数学上推导,而且要从文字方面理解。

我们可以举一个例子:

给出解释为x是学生,A(x)是喜欢写作业。

那么第一个,不是所有的学生都喜欢写作业,和存在不喜欢写作业的学生。这两句话描述的是有的学生喜欢写作业,而有的学生不喜欢,是完全等价的;第二个,不存在学生喜欢写作业,和所有的学生都不喜欢写作业。这两句话描述的是所有的学生都不喜欢写作业,没有喜欢写作业的学生,也是完全等价的。

从中我们可以知道,全称量词和存在量词是可以相互转换的:                                                          不是所有存在不是的,¬∀ ∃¬

        没有一个所有都没有,¬∃  ∀¬

另外,在证明公式时,不是只有存在否定符号时才可以用量词否定等值式,可以先用双重否定律(A ¬¬A)让式子中出现¬,然后再用上面两个式子进行量词的转换。

这组式子比较容易掌握,我们来看下面一组。

2、量词辖域收缩与扩张等值式

设公式A(x)含有x的自由出现,而B中不含x的自由出现(这个条件为什么是这个样子,后文会作解释,现在先不用管)。

(1)   ∀x(A(x) ∨ B)  ∀xA(x) ∨ B

        ∀x(A(x) ∧ B)  ∀xA(x) ∧ B

        ∀x(A(x) → B)  ∃xA(x) → B

        ∀x(B → A(x))  B → ∀xA(x)

(2)    ∃x(A(x) ∨ B)  ∃xA(x) ∨ B

        ∃x(A(x) ∧ B)  ∃xA(x) ∧ B

        ∃x(A(x) → B)  ∀xA(x) → B

        ∃x(B → A(x))  B → ∃xA(x)

我们来仔细观察以上两组式子,可以发现这两组式子形式基本上是一致的,第一组式子和第二组式子的不同仅仅在于换了个量词。

下面我们来解释第一组的第一个式子:

给出解释为x是警察,A(x)是聪明,B是世界末日。

那么第一组中的第一个,对于所有的警察,要么很聪明,要么世界末日,和所有聪明的警察,或者世界末日。很明显,这两句话表达的意思是一样的。我们一定会觉得“世界末日”和“警察”,即变量x,没有关系。这正好是呼应了上文的条件,B中是不含x自由出现的,也即“世界末日”这个谓词,不能形容警察,也就不能和警察有联系。

在这个式子中,我们看到,量词的辖域收缩或者扩张了,辖域即量词的作用域,能让这个量词起作用的地方。

然而我们能轻易理解的一般是有关联的例子,没有关联的例子在逻辑数学中成立,但在现实生活中就不一定成立。为了更好的理解第一个式子,我们先假设B和x是有联系的,即让B中含有x的自由出现,看看下面这个等值式是否成立:

 ∀x(A(x) ∨ B(x))  ∀xA(x) ∨ ∀xB(x)

给出解释为x是学生,A(x)是x聪明,B(x)是x漂亮。

那么对于所有的学生,不是聪明,就是漂亮,和要么所有的学生都聪明,要么所有的学生都漂亮。第一句话表示所有的学生中,既有聪明的人,又有漂亮的人,与第二句话的意思明显不同,所以这个式子是不成立的,这也就解释了为什么量词辖域收缩与扩张等值式要求B中不含x的自由出现了。

同样的道理,我们可以理解第一组和第二组的前两个式子。下面我们来看第一组和第二组的第三个式子。

给出解释为x是警察,A(x)是x聪明,B是小偷被抓。

那么第一组的第三个,对于所有的警察都满足,如果警察聪明,那么小偷被抓,和如果存在聪明的警察,那么小偷被抓。这两句话都是描述所有聪明的警察都可以使小偷被抓;第二组的第三个,存在警察满足,如果警察聪明,那么小偷被抓,和如果所有的警察都聪明,那么小偷被抓。这两句话都是表达了有些聪明的警察能够使小偷被抓,而有些不能。

从这两个式子我们可以看出,如果A(x)在前件,即蕴含符号的前面,在收缩或者扩张时,是需要变量词的。而如果A(x)在后件,看第四个式子,就不需要变量词。第四个式子也可以套用上面的解释来理解,这里就不再赘述了。

3、量词分配等值式

∀x(A(x) ∧ B(x))  ∀xA(x) ∧ ∀xB(x)

∃x(A(x) ∨ B(x))  ∃xA(x) ∨ ∃xB(x)

仍然取上文中的一个解释,x是学生,A(x)是x聪明,B(x)是x漂亮。

第一个式子,对于所有的学生满足,既聪明又漂亮,和所有的学生都聪明并且所有的学生都漂亮。容易看出这两句话是一个意思。而让我们再对比之前的∀x(A(x) ∨ B(x))  ∀xA(x) ∨ ∀xB(x)(不成立),可以看出,对于全称量词,只有A(x)和B(x)合取的时候可以分配,而析取的时候不能。同样的,我们也可以推出,对于存在量词,只有A(x)和B(x)析取的时候可以分配,而合取的时候不能。

置换规则

简单来说就是把式子套进等值式中,从而进行一系列的推导。这个比较好理解,不用多说。

换名规则

就是将某个量词辖域中的字母换成另一个字母,字母怎么换都是不影响式子的表达的,更换前后式子等值,换不换都行,但是在某些情况下必须换。

举个例子:

∀x(A(x) ∨ B(x))  ∀xA(x) ∨ ∀xB(x)

这个式子不是不成立吗?但是如果将B(x)换成B(y),即∀x(A(x) ∨ B(y))  ∀xA(x) ∨ ∀xB(y),就成立了,它是量词辖域收缩与扩张等值式中第一组第一个式子。

再举一个例子:

(∀x1 F(x1,x2) → ∃x2 G(x2)) → ∀x1 H(x1,x2,x3)

我们可以看到,这个式子中的x1约束出现在了F谓词和H谓词中,在求解前束范式时也需要进行换名操作。因为x1虽然都是约束出现,但是谓词不一样,它们表示的不是一个东西,所以需要通过换名来区分。

PS:量词的顺序是不能颠倒的,但是消去量词时,不用考虑消去量词的顺序。

//以上是我个人的理解,如有错误,还请指正,我会及时修改的,谢谢。



【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3