离散数学第二章 谓词逻辑 |
您所在的位置:网站首页 › 离散数学第一章集合 › 离散数学第二章 谓词逻辑 |
离散数学第二章 谓词逻辑
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: ¬(∀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) 常用式子集合若对任意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)为真 例题tips:注意本例推导过程中第(3)与(4)两条次序不能颠倒,若先用US规则得到C(a)→ W(a) ∧R(a), 则再用ES规则时,不一定得到C(a)∧Q(a), 一般地应为C(b)∧Q(b),故无法推证下去。
|
今日新闻 |
推荐新闻 |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |