离散数学第二章 谓词逻辑
离散数学第二章 谓词逻辑
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）就可成为一个命题
-
通常，一元谓词表达了客体的“性质”，而多元谓词表达了客体之间的“关系”。
举例
-
H：能够到达山顶 l：李四
H(l)：李四能够到达山顶
-
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)
谓词演算的合式公式可由下述各条组成：
-
原子谓词公式是合式公式。
-
若A是合式公式，则¬A是一个合式公式。
-
若A和B都是合式公式，则(A∧B), (A∨B), (A→B)和(A⇄B)是合式公式。
-
如果A是合式公式，x是A中出现的任何变元，则 (∀x)A和(∃x)A都是合式公式。
-
只有经过有限次地应用规则(1),(2),(3),(4)所得到的公式是合式公式。
eg1:并非每个实数都是有理数。(R(x),Q(x))
解：¬(∀x)(R(x)→Q(x))
eg2:
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)
常用式子集合
2-7谓词演算的推理理论
(1).全称指定规则(US)
若对任意x满足P，且c属于x，则c满足P
(2).全程推广规则(UG)
若能证明对论域任意的x均能保证P(x)成立，则可得结论(∀x)P(x)成立
(3).存在指定规则(ES)
若存在x使P(x)成立，则可指定c使P(c )成立
(4).存在推广原则(EG)
对某些客体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)">
