离散数学第二章 谓词逻辑

(51) 2024-03-12 09:01:02

离散数学第二章 谓词逻辑

2-1谓词的概念与表示

  • 用以刻划客体的性质或关系的即是谓词

  • 我们将用大写字母表示谓词,用小写字母表示客体名称

  • 用谓词表达命题,必须包含客体和谓词字母两个部分,一般地说,“b是A”类型的命题可用A(b)表达

    对于“a是小于b”这种两个客体之间关系的命题,可表达为B(a,b),这里B表示“是小于”。又如命题“点a在b与c之中”可表示为L:…在…和…之中,故可记为L(a,b,c)

  • 我们把A(b)称作一元谓词,B(a,b)称作二元谓词,L(a,b,c)称作三元谓词,依次类推

    一般地说,n元谓词需要n个客体名称插入到固定的位置上,如果A为n元谓词,a1,a2…,an是客体的名称,则A(a1,a2,…,an)就可成为一个命题

  • 通常,一元谓词表达了客体的“性质”,而多元谓词表达了客体之间的“关系”。

举例

  1. H:能够到达山顶 l:李四

    H(l):李四能够到达山顶

  2. A(x,y,z):x加上y等于z

    A(1,2,4):1+2=4

2-2命题函数与量词

简单命题函数:由一个谓词和一些客体变元组成的表达式,称为简单命题函数。

根据这个定义可以看到,n元谓词就是有n个客体变元的命题函数,当n=0时,称为0元谓词,它本身就是一个命题,故命题是n元谓词的一个特殊情况。

由一个或n个简单命题函数以及逻辑联结词组合而成的表达式,称复合命题函数

eg.:H(x,y):x比y长得高 l:李四 c:张三

¬H(l,c):李四不比张三长得高

¬H(l,c)∧¬H(c,l):张三与李四一样高

命题函数不是一个命题,只有客体变元取特定名称时,才能成为一个命题。但是客体变元在哪些范围内取特定的值,对是否成为命题及命题的真值极有影响。

eg1:R(x):x是大学生

x的讨论范围为某大学里班级中的学生,则R(x)是永真式

x的讨论范围为某中学班级中的学生,则R(x)是永假式

x的讨论范围为一个剧场中的观众,则R(x)对某些观众为真,对另一些观众为假

eg2:(P(x,y)∧P(y,z))→P(x,z)

若P(x,y)解释为“x小于y”,则这是一个永真式

若P(x,y)解释为“x为y的儿子”,则这是一个永假式

若P(x,y)解释为“x距离y10米”,则它有可能为T,也可能为F

在命题函数中,客体变元的论述范围称作个体域。个体域可以是有限的,也可以是无限的,把各种个体域综合在一起作为论述范围的域称全总个体域

为了避免理解上的混乱,需要引入量词,以刻划“所有的”和“存在一些”的不同概念。

eg:(a) 所有的人都是要呼吸的。

​ 设M(x):x是人, H(x):x要呼吸。

​ (∀x)(M(x)→H(x))

​ (b) 任何整数或是正的或是负的。

​ 设I(x):x是整数, R(x):x是正数,N(x):x是负数。

​ (∀x)(I(x)→(R(x)∨N(x)))

​ (c ) 有些人早饭吃面包。

​ 设M(x):x是人,E(x):x早饭吃面包。

​ (∃x)(M(x)∧E(x))

练习

找出“有些大学生不钦佩运动员”对应的谓词表达式

S(x):x是大学生,L(x):x是运动员,A(x,y):x钦佩y

分析:(∃x)(x是大学生 且 x不钦佩运动员)

​ (∃x)(S(x)∧(∀y)(y是运动员→x不钦佩y))

: (∃x)(S(x)∧(∀y)(L(y)→¬A(x,y)))

2-3谓词公式与翻译

我们把A(x1,x2,…,xn)称作谓词演算的原子公式,其中x1,x2,…,xn是客体变元

eg:Q, A(x), A(x,y), A(f(x),y), A(x,y,z), A(a,y)

谓词演算的合式公式可由下述各条组成:

  1. 原子谓词公式是合式公式。

  2. 若A是合式公式,则¬A是一个合式公式。

  3. 若A和B都是合式公式,则(A∧B), (A∨B), (A→B)和(A⇄B)是合式公式。

  4. 如果A是合式公式,x是A中出现的任何变元,则 (∀x)A和(∃x)A都是合式公式。

  5. 只有经过有限次地应用规则(1),(2),(3),(4)所得到的公式是合式公式。

eg1:并非每个实数都是有理数。(R(x),Q(x))

:¬(∀x)(R(x)→Q(x))

eg2:

离散数学第二章 谓词逻辑 (https://mushiming.com/)  第1张

2-5谓词演算的等价式与蕴含式

(1).量词与联结词¬之间的关系

¬(∀x)P(x)⇔(∃x)¬P(x)

¬(∃x)P(x)⇔(∀x)¬P(x)

(2).量词作用域的扩张与收缩

量词的作用域中,常有合取或析取项,如果其中为一个命题,则可将该命题移至量词作用域之外:

(∀x)(A(x)∨B)⇔((∀x)A(x)∨B)

(∀x)(A(x)∧B)⇔((∀x)A(x)∧B)

(∃x)(A(x)∨B)⇔((∃x)A(x)∨B)

(∃x)(A(x)∧B)⇔((∃x)A(x)∧B)

这是因为在B中不出现约束变元x,故它属于或不属于量词的作用域均有同等意义。

从上述几个式子,我们还可推得如下几个式子:

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

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

(B→(∀x)A(x))⇔(∀x)(B→A(x))

(B→(∃x)A(x))⇔(∃x)(B→A(x))

当谓词的变元与量词的指导变元不同时,亦能有类似于上述的公式:

(∀x)(P(x)∨Q(y))⇔((∀x)P(x)∨Q(y))

(∀x)((∀y)P(x,y)∧Q(z))⇔((∀x)(∀y)P(x,y)∧Q(z))

(3).量词与命题联结词之间的一些等价式

(∀x)(A(x)∧B(x))⇔(∀x)A(x)∧(∀x)B(x)

(∃x)(A(x)∨B(x))⇔(∃x)A(x)∨(∃x)B(x)

(4).量词与命题联结词之间的一些蕴含式

(∀x)A(x)∨(∀x)B(x)⇒(∀x)(A(x)∨B(x))

(∃x)A(x)∧(∃x)B(x)⇒(∃x)(A(x)∧B(x))

类似的有:

(∀x)(A(x)→B(x))⇒(∀x)A(x)→(∀x)B(x)

(∀x)(A(x)⇄B(x))⇒(∀x)A(x)⇄(∀x)B(x)

常用式子集合

离散数学第二章 谓词逻辑 (https://mushiming.com/)  第2张

2-7谓词演算的推理理论

(1).全称指定规则(US)

离散数学第二章 谓词逻辑 (https://mushiming.com/)  第3张

若对任意x满足P,且c属于x,则c满足P

(2).全程推广规则(UG)

离散数学第二章 谓词逻辑 (https://mushiming.com/)  第4张

若能证明对论域任意的x均能保证P(x)成立,则可得结论(∀x)P(x)成立

(3).存在指定规则(ES)

离散数学第二章 谓词逻辑 (https://mushiming.com/)  第5张

若存在x使P(x)成立,则可指定c使P(c )成立

(4).存在推广原则(EG)

离散数学第二章 谓词逻辑 (https://mushiming.com/)  第6张

对某些客体c,若P(c )成立,则在论域中必有(∃x)P(x)为真

例题

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-m80QXuh0-1617101554814)(C:\Users\27745\AppData\Roaming\Typora\typora-user-images\image-20210330183449031.png)]">

tips:注意本例推导过程中第(3)与(4)两条次序不能颠倒,若先用US规则得到C(a)→ W(a) ∧R(a), 则再用ES规则时,不一定得到C(a)∧Q(a), 一般地应为C(b)∧Q(b),故无法推证下去。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2EyNpgLB-1617101554815)(C:\Users\27745\AppData\Roaming\Typora\typora-user-images\image-20210330184602970.png)]">
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-BHcCshUT-1617101554817)(C:\Users\27745\AppData\Roaming\Typora\typora-user-images\image-20210330184651030.png)]](https://img-blog.csdnimg.cn/20210330185554918.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzU2MTUwNjY0,size_16,color_FFFFFF,t_70)">

THE END

发表回复