首页 谓词逻辑

谓词逻辑

举报
开通vip

谓词逻辑null谓词逻辑谓词逻辑例:苏格拉底论断 前提 “所有的人都是要死的” “苏格拉底是人” 结论 “所以苏格拉底是要死的” 命题逻辑限定原子命题是不能细分的整体 命题逻辑的局限性PQRP∧QR不是命题演算的有效推理问题的提出:(为什么要对原子命题进一步细分?)原子命题不能细分吗?(能否对原子命题进一步细分?)原子命题不能细分吗?(能否对原子命题进一步细分?)例 P1:小张是大学生 P2:小李是大学生 Q1:2大于3 Q2:6大于4 不同原子命题之间是有内在联系的,但命题逻辑无法研究这种内在联系 解决问题的方法 分析...

谓词逻辑
null谓词逻辑谓词逻辑例:苏格拉底论断 前提 “所有的人都是要死的” “苏格拉底是人” 结论 “所以苏格拉底是要死的” 命题逻辑限定原子命题是不能细分的整体 命题逻辑的局限性PQRP∧QR不是命题演算的有效推理问题的提出:(为什么要对原子命题进一步细分?)原子命题不能细分吗?(能否对原子命题进一步细分?)原子命题不能细分吗?(能否对原子命题进一步细分?)例 P1:小张是大学生 P2:小李是大学生 Q1:2大于3 Q2:6大于4 不同原子命题之间是有内在联系的,但命题逻辑无法研究这种内在联系 解决问题的方法 分析原子命题,分离其主语和谓语 考虑一般和个别,全称和存在1.6 谓词和量词1.6 谓词和量词1.6.1 谓词 谓词的概念和 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示(如何对原子命题进一步细分?) 在原子命题中,用来刻划一个个体的性质或几个个体之间关系的成分称为谓词。 刻划一个个体性质的词称为一元谓词;刻划n个个体之间关系的词称为n元谓词。谓词常用大写英文字母表示。 谓词与个体词一起才能表示命题。用A(a)表示“A具有性质A”(或“a属于A类”),用B(a1,a2,…,an)表示“a1,a2,…,an关系满足B”。 个体 能够独立存在的事物,思维的对象 通常用小写英文字母a、b、c、...表示个体常量 用小写英文字母x、y、z...表示任何个体,则称这些字母为个体变元三个要件以命题逻辑为基础例例(a) 5是质数 (b) 张明生于北京 (c) 7=3×2 P(x):x是质数 G(x, y): x生于y ,a:张明,b:北京 H(x, y, z) :x=y×zP(5)G(a,b)H(7,3,2)N元谓词填式中变元的次序很重要思考:x>y>z该怎么表示?练习练习小张不是工人 张三和李四是表兄弟 小莉是非常聪明和美丽的 实数x大于实数y 大灰狼偷吃了小羊羔 W(a)W(x):x是工人 a: 小张 P(a,b)P(a)∧Q(a)R(x):x是实数 G(x,y): x>y G(R(x),R(y))?R(x)∧R(y)∧G(x,y)否定命题P(x)∧Q(y)∧E(x,y)P1(x)∧P2(x)∧P3(x)∧ Q1(y)∧Q2 (y)∧E(x,y)问题:R(x,y):x和y是实数?××分解到词null谓词常元 一个字母代表一特定谓词, 则称此字母为谓词常元(量)。例如P(x)表示“x是质数”这种模式的判断,P就是谓词常元。 谓词变元 若字母代表任意谓词, 则称此字母为谓词变元 论域 谓词命名式中个体变元的取值范围 个体域与全总域 空集不能作为论域命题函数命题函数谓词命名式不是命题 若谓词是常元 个体词是常元 谓词命名式才成为一个命题 命题函数 由一个谓词和若干个个体变元组成的命题形式称为简单命题函数,表示为P(x1,x2,…,xn)。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数 n=0时 命题变元null例 A(x):x身体好 B(x):x学习好 C(x):x工作好 表示“如果x身体不好,则x的学习与工作都不会好”的复合命题函数 A(x)→(B(x)∧C(x)) 命题函数不是命题,没有确定真值,但其中谓词是谓词常量时,可通过个体指派使其成为命题。如:若简单命题函数P(X)表示“x是质数”,则P(1)为F,P(2)为T。 除个体指派外,还常用“量”作出判断,如:“所有的人都是要死的”、“有的数是质数”。这种表述在数理逻辑目标语言中需要引入量词,当然量化与个体指派之间是有联系的,数理逻辑中常用量词有两个——全称量词和存在量词。1.6.2 量词1.6.2 量词例 “所有的正整数都是素数” “有些正整数是素数” 假设 只有两个正整数a和b 个体域为{a,b} P(x):x是素数P(a)∧ P(b)P(a)∨ P(b)全称量词全称量词记作 表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等 x读作“任意x”, “所有x”, “对一切x ” 量词后边的个体变元,指明对哪个个体变元量化,称为量词后的指导变元 例 所有人都是要死的 D(x):x是要死的 个体域:所有人构成的集合 x D(x)存在量词存在量词记作 表示“有些”、“一些”、“某些”、“至少一个”等 x读作“存在x”,“对某些x”或“至少有一x” 指导变元 例 有些有理数是整数 I(x):x是整数 个体域:有理数集合 xI(x)全总个体域(全总域)全总个体域(全总域)含有量词的命题的真值与论域有关 含有量词的命题的表达式的形式与论域有关 全总个体域 宇宙间所有的个体聚集在一起所构成的集合 约定 除特殊说明外,均使用全总个体域 对个体变化的真正取值范围,用特性谓词加以限制例例所有的人都是要死的 有的人活百岁以上 D(x):x是要死的 G(x) :x活百岁以上 个体域E为全体人组成的集合 x D(x) x G(x) 全总个体域 引入特性谓词 M(x):x是人 x(M(x) D(x)) x (M(x)∧G(x))特性谓词添加规则特性谓词添加规则对全称量词, 特性谓词作为条件式之前件加入 对存在量词, 特性谓词作为合取项而加入 例 (a) 没有不犯错误的人 F(x):x犯错误 M(x):x是人 ¬ x (M(x)∧¬F(x)) (b) 凡实数, 或大于零,或等于零,或小于零 R(x):x是实数 L(x, y):x>y E (x, y) : x = y S(x, y):x < y x(R(x) L(x, 0)∨ E (x, 0) ∨ S (x, 0)) 1.6.3 量化断言和命题的关系1.6.3 量化断言和命题的关系假设论域有限,不妨设论域D={1,2,3} xP(x)? xP(x) P(1)∧ P(2) ∧ P(3) xP(x)? xP(x) P(1)∨ P(2) ∨P(3) 若论域无限可数,概念可以推广 两个量词共轭 ¬xP(x)  x¬P(x) ¬xP(x)  x¬P(x)量化断言和个体指派的关系x取遍论域中的所有值T关于x的命题函数A(x)取值皆为T全称命题xA(x)的真值为TF关于x的命题函数A(x)取值皆为F存在命题xA(x)的真值为F量化断言和个体指派的关系x取遍论域中的所有值总之: 1.全称命题xA(x)为真,当且仅当a∈D,A(a)皆为真。 2.全称命题xA(x)为假,当且仅当a∈D,A(a)为假。 3.存在命题xA(x)为真,当且仅当a∈D,A(a)为真。 4.存在命题xA(x)为假,当且仅当a∈D,A(a)皆为假。1.6.4 谓词 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 1.6.4 谓词公式个体函数(函词) 例 小王比他的父亲高 H(x,y):x比y高 a:小王 b:小王的父亲 H(a,b) 无法显示个体之间的依赖关系 定义函数 f(x)=x的父亲 H(a, f(a)) null函词与谓词的区别 函词中的个体变元用个体代入后的结果依然是个体 f(a)=小王的父亲 谓词中的个体变元用确定的个体带入后就变成了命题 M(x):x是人 M(a):小王是人 函词是论域到论域的映射 f : D→D 谓词是从论域到{T,F}的映射 M : D →{T,F}项和原子公式项和原子公式项(item) 表示个体 定义 个体常量是项 个体变元是项 如果f是一个n(n≥1)元函词,其t1, t2,…, tn都是项,则f(t1, t2,…, tn)是项 例 a, b, c x, y, z f (x), g (a, f (y)) null原子公式(atom) 定义 若P是一个n元谓词,且t1,t2,…,tn是项,则P(t1,t2,…,tn)是原子 命题词也是原子(n=0) 例 P, Q (x), A (x, f (x)), B (x, y, a)谓词演算的合式公式(Wff)谓词演算的合式公式(Wff)也叫谓词公式,简称公式 定义 (1)原子公式是合式公式 (2)如果A、B是合式公式,则(A)、(A∧B)、(A∨B)、(A→B)、(AB)都是合式公式 (3)如果A是合式公式,x是个体变元,则xA和xA也是合式公式 (4)有限次地使用规则(1)至(3)求得的公式是合式公式 子公式 括号省略规则 例 P,(Q(x)∧P),x(A(x)→B(x)),xC(x), xZ(y)命题符号化命题符号化谓词逻辑中比较复杂 命题的符号表达式与论域有关系 例:每个自然数都是整数 论域D=N I(x):x是整数 x I (x) 论域为全总个体域 特性谓词N(x):x是自然数 x(N(x)→I(x))例:将下列命题符号化例:将下列命题符号化(1)所有大学生都喜欢一些歌星。 S(x):x是大学生,X(x):x是歌星,L(x,y):x喜欢y x(S(x)→y(X(y)∧L(x,y))) (2)发光的不都是金子。 P(x):x发光,G(x):x是金子 x(P(x)→G(x)) (3)某些人对食物过敏 F(x, y):x对y过敏,M(x):x是人, G(x):x是食物 x (M(x)∧y(G(y)∧F(x,y))) null(4)每个人都有些缺点 H(x, y):x有y,M(x):x是人, S(x):x是缺点 x(M(x)→ y(S(y)∧H(x,y)) (5)尽管有人聪明, 但未必人人聪明 M(x):x是人, S(x):x聪明 x(M(x)∧S(x))∧¬x(M(x)→S(x)) (6)所有老虎都能吃人 (7)不管白猫黑猫,凡能逮住耗子的就是好猫 (8)无论是步行的、骑马的、乘车的,凡口渴的皆要喝水练习:将下列命题符号化练习:将下列命题符号化所有教练员都是运动员;(J(x),L(x)) 某些运动员是大学生;(S(x)) 某些教练员是年老的,但是健壮的;(O(x),V(x)) 金教练虽不年老,但不健壮;(j) 不是所有运动员都是教练员; 某些大学生运动员是国家选手;(C(x)) 没有一个国家选手不是健壮的; 所有老的国家选手都是运动员; 没有一位女同志既是国家选手又是家庭妇女;(W(x),H(x)) 有些女同志既是教练员又是国家选手; 所有运动员都钦佩某些教练员;(A(x, y)) 有些大学生不钦佩运动员。练习参考答案练习参考答案x(J(x)→L(x)) x(L(x)∧S(x)) x(J(x)∧O(x)∧V(x)) J(j)∧O(j)∧V(j) x(L(x)→J(x)) x(S(x)∧L(x)∧C(x)) x(C(x)∧V(x)) x((C(x)∧O(x))→L(x)) x(W(x)∧C(x)∧H(x)) x(W(x)∧J(x)∧C(x)) x(L(x)→y(J(y)∧A(x,y))) x(S(x)∧y(L(y)→A(x,y)))几个特别的例子几个特别的例子(1) 如果明天下雨,则某些人将被淋湿 不是个体定义命题词P:明天下雨, M(x):x是人,W(x):x将被淋湿 P x(M(x)∧ W(x))(2) 有且仅有一个偶素数A(x):x是偶素数 x(A(x)∧ y(A(y)x=y))或者x(A(x)∧¬y(x≠y∧A(y))(3) 顶多只有一台机器是好的 A(x):x是好机器用符号 !xA(x) 表示有且仅有一个个体满足Axy(A(x)∧A(y)x=y)用符号 !!xA(x) 表示顶多有一个个体满足A思考:用E(x)表示“x是偶数”, P(x)表示“x是素数”,公式会是怎么样?null (4) 如果人都爱美,则漂亮衣服有销路 M(x):x是人,L(x):x爱美, C(x):x是衣服, B(x):x是漂亮的,S(x):x有销路 x(M(x)L(x))x(C(x)∧B(x)  S(x))问题一:前后两个x是否指同一个个体? 答:前后两个x不是同一个个体 问题二:若写成如下形式是否正确? x(M(x)L(x))  y(C(y)∧B(y)  S(y)) 答:是正确的,显然 x(M(x)L(x))  x(C(x)∧B(x)  S(x))  x(M(x)L(x))  y(C(y)∧B(y)  S(y))1.6.5 自由变元与约束变元1.6.5 自由变元与约束变元量词的作用域(辖域) 定义:在谓词公式中,量词的作用范围称之为量词的作用域,也叫量词的辖域。 例 xA(x) x的辖域为A(x) x((P(x)∧Q(x))→yR(x,y)) x的辖域是((P(x)∧Q(x))→yR(x,y)) y的辖域为R(x,y) xyz(A(x,y)→B(x,y,z))∧C(t)x的辖域z的辖域y的辖域自由变元null一般地, 如果量词后边只是一个原子谓词公式时,该量词的辖域就是此原子谓词公式。 如果量词后边是括号,则此括号所表示的区域就是该量词的辖域。 如果多个量词紧挨着出现,则后边的量词及其辖域就是前边量词的辖域。null约束变元 如果个体变元x在x或者x的辖域内,则称x在此辖域内约束出现,并称x在此辖域内是约束变元 自由变元 如果个体变元x不在任何量词的辖域内,则称x是自由出现,并称x是自由变元 例 x(F(x,y)→yP(y))∧Q(z) F(x,y)中的x和P(y)中的y是约束变元 而F(x,y)中的y和Q(z)中的z是自由变元例:指出下列各公式中的量词辖域及自由变元和约束变元例:指出下列各公式中的量词辖域及自由变元和约束变元xy(P(x)∧Q(y))→zR(z) x的辖域y(P(x)∧Q(y)) y的辖域P(x)∧Q(y) z的辖域R(z) x(P(x,y)→yQ(x,y,z))∧S(x,z) x的辖域P(x,y)→yQ(x,y,z) 其中x是约束变元 y是自由变元 y的辖域Q(x,y,z) 其中y是约束变元 x, z是自由变元 S(x,z)中x,z是自由变元对约束变元和自由变元的几点说明对约束变元和自由变元的几点说明约束变元用什么符号表示无关紧要 xA(x)与yA(y)是一样的 一个谓词公式如果无自由变元,它就表示一个命题 例:A(x)表示x是个大学生 xA(x)或者xA(x)是命题 一个n元谓词P(x1,x2,…,xn),若在前边添加k个量词,使其中的 k个个体变元变成约束变元,则变成n-k元谓词函数例例P(x,y,z)表示x+y>z 假设论域是整数集,xyP(x,y,z)表示? “任意给定的整数x,都可以找到整数y,使得x+y>z” 。 令z=1,则xyP(x,y,1)表示? “任意给定的整数x,都可以找到整数y,使得x+y>1”,…。 xyP(x,y,1)表示?约束变元换名约束变元换名不同个体以相同的符号出现容易产生混淆 例 x(F(x,y)→yP(y))∧Q(z) 约束变元的换名规则 换名的变元名称范围是量词后的指导变元以及该量词辖域内该个体变元符号的一切约束出现 改名后用的个体变元名称,不能与该量词的辖域内的其它变元名称相同约束关系不变换名前后公式等价例例x(P(x)→Q(x,y))∨(R(x)∧A(x)) x以两种形式出现 对x换名 z(P(z)→Q(z,y))∨(R(x)∧A(x)) x(P(x,y)→yQ(x,y,z))∧S(x,y) 对x和y换名 u(P(u,v)→vQ(u,v,z))∧S(x,y) 错误 u(P(u,y)→zQ(u,z,z))∧S(x,y) 错误 u(P(u,y)→vQ(u,v,z))∧S(x,y) 正确自由变元换名自由变元换名自由变元也可以换名 此换名叫代入 自由变元的代入规则 换名的变元名称范围是该谓词公式中该自由变元的一切自由出现 并不要求用以代换的是变元符号,而可以是任何形式的项(但其中的变元不能受量词约束)约束关系不变换名前后公式一般不等价例例x(P(x)→Q(x,y))∨(R(x)∧A(x)) 用z代替自由变元x x(P(x)→Q(x,y))∨(R(z)∧A(z)) x(P(x,y)→yQ(x,y,z))∧S(x,z) 用w和t分别代自由变元x和y x(P(x,t)→yQ(x,y,z))∧S(w,z) 1.7 谓词演算的永真公式1.7 谓词演算的永真公式谓词公式的解释I包括: 指定一个论域D(称I为D上的解释) 对A中出现的每一个n元函数,指定一个D上的 n元个体函数常量 对A中出现的每一个n元谓词,指定一个D上的n元谓词常量 对A中出现的每一个个体常量及自由变元,指定D中的一个个体常量 对A中出现的每一个命题变元P,指派一个真值T或F 由此得到一个命题AI,称AI的真值为合适公式A在解释I 下的真值例例取解释I如下: D={1,2}, 定义D上的二元谓词P真值为 P(1,1): T; P(1,2): F; P(2,1):F; P(2,2): T 则xyP(x,y)和yxP(x,y) 在解释I下的真值分别为? xyP(x,y)xyP(x,y)TTFFTTT关于x的一元函数yxP(x,y)yxP(x,y)TFFFFFT关于y的一元函数例例取解释I如下: D={1,2}, 令 a:1, f(1)=2, f(2)=1 定义D上的谓词P和Q为 P(1): F; P(2): T; Q(1,1):T; Q(1,2):T; Q(2,1):F; Q(2,2): F 求谓词公式x(P(x)→Q(f(x),a))在解释I下的真值P(1)→Q(f(1),1)P(2)→Q(f(2),1)TTx(P(x)→Q(f(x),a))在解释I下的真值为T谓词公式的永真式谓词公式的永真式定义 给定谓词公式A,E是其论域,如果在任何解释下公式A的真值都为真,则称公式A在论域E上是永真式。如果不论对什么论域E,都使得公式A为永真式,则称A为永真式。 例:I(x):x是整数,论域E为自然数集合 I(x)在E上是永真式 I(x) ∨ I(x)是与论域无关的永真式 谓词公式的永假式 谓词公式的可满足式例:试说明以下公式的类型例:试说明以下公式的类型 xA(x)→A(y) xA(x)→A(y) A(x) (A(x) :x+6=5) x( A(x) ∧ ¬A(x)) x (A(x)∨B(x)) → xA(x)∨xB(x) x (A(x)∧B(x))  xA(x) ∧ xB(x)永真式 可满足式 可满足式永假式永真吗?永真式的判定永真式的判定命题逻辑的永真式问题是可判定的。 至少可用真值表 谓词逻辑的永真式问题是不可判定的。 研究谓词逻辑永真式判定问题非常有意义: 联词与量词的关系 问题与否问题的关系 构造证法的一种典型情形 公式形成规则、联词、量词、变元约束等知识点 逐步推演思想 完整地自顶向下逐步求精思想问题与否问题问题与否问题问题:所给公式是永真式吗? 否问题:所给公式不是永真式吗? 这两个问题有不同的难度 是永真式:在任何论域的任何解释下皆为真 不是永真式:存在一个使该公式为假的特定解释问题证明的一般方法问题证明的一般方法直接证明法反证法数学归纳法递归或递推的 形式给出算法问题描述方式决定Px(Q(x)→R(x))PxA(x)构造证法找出实例给出算法1.明确问题形式结构x:Q(x)  R(x)2.转换形式结构 Q1(x) R1(x) 3.引用已知条件PP(问题具体描述)(问题抽象描述)(两种方式)null例:试判断xA(x)∨xB(x) → x(A(x)∨B(x))是否是永真式,并说明理由。分析:试图找到一个使该公式为假的解释,首先考虑论域。 论域大了,过程会复杂,论域小了,无法区分全称与存在,所以取D={1,2}。xA(x)为T或xB(x)为TA(1)∨B(1)为F或A(2)∨B(2)为F不妨取不妨取所以结论:所给公式不是永真式例(续前):试判断xA(x)∨xB(x) → x(A(x)∨B(x))是否是永真式,并说明理由。例(续前):试判断xA(x)∨xB(x) → x(A(x)∨B(x))是否是永真式,并说明理由。解:所给公式不是永真式,理由如下。 考虑D={1,2}上的解释I:此处取T亦可 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 总结总的思路:试图在D={1,2}上找到一个使所给公式为假的解释。 注意:以前进行运算都是根据形成过程由里往外逐次进行的,但这里的过程正好相反:自顶向下逐步推演。 在推演过程中,首先考虑以下事实: 若是上述五种情况之外的情况,则利用D中元素的对称性避免讨论。永真式判定问题非常有意义,下面16个公式要完整掌握永真式判定问题非常有意义,下面16个公式要完整掌握x(A(x)∨B(x)) → xA(x)∨xB(x) x(A(x)∧B(x)) → xA(x)∧xB(x) x(A(x)∨B(x)) → xA(x)∨xB(x) x(A(x)→B(x)) → (xA(x)→xB(x)) x(A(x)→B(x)) → (xA(x)→xB(x)) x(A(x)→B(x)) → (xA(x)→xB(x)) x(A(x)→B(x)) → (xA(x)→xB(x)) xyA(x,y) → yxA(x,y) x(A(x)↔B) ↔ (xA(x)↔B) 又例:试判断x(A(x)∨B(x)) → xA(x)∨xB(x)是否是永真式,并说明理由。又例:试判断x(A(x)∨B(x)) → xA(x)∨xB(x)是否是永真式,并说明理由。不妨取不妨取FTT结论:所给公式不是永真式(自己完成说理过程)四个都是选择条件再例:试判断x(A(x)→B(x)) → (xA(x)→xB(x))是否是永真式,并说明理由。再例:试判断x(A(x)→B(x)) → (xA(x)→xB(x))是否是永真式,并说明理由。null选择条件选择条件选择条件但注意FF结论:所给公式是永真式问题:怎么证明?证明:x(A(x)→B(x)) → (xA(x)→xB(x))是永真式证明:x(A(x)→B(x)) → (xA(x)→xB(x))是永真式真值表技术 等价变换 逻辑推证×附加前提考虑论域D上任一使x(A(x)→B(x))和xA(x) 皆为T的解释I, 在I下:注意与命题演算的不同 “存在”判断的条件(本质上)先引用形式推理 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 格式形式推理标准格式⑴ x(A(x)→B(x)) P ⑵ xA(x) P(附加前题) ⑶ A(c) ES⑵ ⑷ A(c)→B(c) US⑴ ⑸ B(c) T⑶⑷ I ⑹ xB(x) EG⑸ ⑺ xA(x)→xB(x) CP 谓词公式的等价谓词公式的等价定义 两个任意谓词公式A和B, E是它们共有的论域, 若在任何解释下,A与B作的真值都相同(或者说AB是永真式),则称公式A与B在论域E上是等价的。如果不论对什么论域E,都使得公式A与B等价,则称A与B等价,记作AB。 例:I(x):x是整数,N(x):x是自然数,论域E是自然数集合 I(x)与N(x)在E上是等价的 N(x)→I(x) N(x)∨I(x)谓词公式的蕴含谓词公式的蕴含定义 两个任意谓词公式A和B,E是它们的论域,若在任何解释下,都使得公式A→B为永真式,则称在论域E上公式A永真蕴含B。如果不论对什么论域E, A→B是永真式,则称A永真蕴含B,记作AB。 例:G(x):x大于5,N(x):表示x是自然数,论域E={-1,-2,6,7,8,9,....} 在E上公式G(x)→N(x)是永真式 (G(x)∧N(x))→N(x)是与论域无关的永真式,所以(G(x)∧N(x))N(x)1.7.2 谓词演算的基本永真公式1.7.2 谓词演算的基本永真公式命题演算的永真公式也是谓词演算的永真公式 含有量词的谓词演算的基本永真公式 (ⅰ) xAA xAA (ⅱ) xP(x)P(y) 或 xP(x)P(x) P(y)xP(x) 或 P(x)xP(x) (ⅲ) 量词的否定 xP(x) xP(x)  xP(x) xP(x) 量词转换公式共轭例 例 xyz(x+z=y) xyz(x+z=y) xyz(x+z=y)   xy z(x+z=y)   xy z(x+z≠y) null(ⅳ) 量词辖域的扩张和收缩 xA(x)∨Px(A(x)∨P) xA(x)∧Px(A(x)∧P) xA(x)∨Px(A(x)∨P) xA(x)∧Px(A(x)∧P) P→xA(x)x(P→A(x)) P→xA(x)x(P→A(x)) xA(x)→Px(A(x)→P) xA(x)→Px(A(x)→P) P是不含个体变元x的谓词公式证明式1: 一方面,当P为F时, xA(x)∨PxA(x)∨FxA(x) x(A(x)∨P)x(A(x)∨F)xA(x) 另一方面,当P为T时, xA(x)∨PxA(x)∨TT x(A(x)∨P)x(A(x)∨T)Tnull(v) 量词的分配形式 x(A(x)∧B(x))xA(x)∧xB(x) x(A(x)∨B(x))xA(x)∨xB(x) x(A(x)∧B(x))xA(x)∧xB(x) xA(x)∨xB(x)x(A(x)∨B(x)) 证明式1: 个体域中每一个体x,使得 A(x)∧B(x)为真, 等价于对一切x, A(x)是真并且对一切x, B(x)是真 证明式2:由1得x( A(x)∧  B(x))xA(x)∧xB(x) 即 x(A(x)∨B(x)) (xA(x)∨xB(x)) 故 x(A(x)∨B(x)) xA(x)∨xB(x) null注意:式3和式4不是等价公式,而是永真蕴含式 例: 给定如下解释 A(x): x是奇数 B(x):x是偶数 则 xA(x)∧xB(x)为真 x(A(x)∧B(x)) 为假 所以xA(x)∧xB(x)不蕴含x(A(x)∧B(x)) 或 D={1,2} A(1): T A(2): F B(1): F B(2): Tnull证明式3 x(A(x)∧B(x))xA(x)∧xB(x) 证明:假设前件x(A(x)∧B(x))为真, 则论域中至少有一个个体a,使得 A(a)∧B(a)为真, 即A(a)和B(a)都为真, 所以有xA(x)以及xB(x)为真,得 xA(x)∧xB(x)为真 所以 x(A(x)∧B(x))xA(x)∧xB(x)null证明式4 xA(x)∨xB(x)x(A(x)∨B(x)) 证明:由3得 x(A(x)∧B(x))xA(x)∧xB(x) x(A(x)∨B(x))xA(x)∧xB(x) x(A(x)∨B(x))(xA(x)∨xB(x)) 即xA(x)∨xB(x)x(A(x)∨B(x)) 公式4得证。 特别要注意蕴含式的方向,不要搞错null(vi) 量词对及→的处理 x(A(x)→B(x))xA(x)→xB(x) xA(x)→xB(x)x(A(x)→B(x)) 证明1. xA(x)→xB(x) xA(x)∨xB(x) xA(x)∨xB(x) x(A(x)∨B(x)) x(A(x)→B(x)) 证明2. xA(x)→xB(x) xA(x)∨xB(x) xA(x)∨xB(x) x(A(x)∨B(x)) x(A(x)→B(x))null(vii) 关于多个量词的永真式 xyA(x,y)yxA(x,y) xyA(x,y)yxA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)xyA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)yxA(x,y) yxA(x,y)xyA(x,y) xyA(x,y)yxA(x,y)1.7.3 几条规则(命题演算的推广)1.7.3 几条规则(命题演算的推广)代入规则 设A是命题逻辑中的永真式,则用谓词逻辑的合适公式代替A中的某些命题变元得到的代入实例也是永真式;如果A是永假式,则上述代入实例也是永假式 例 A(x)A(x)∨B(x) PP∨Q x(A(x)→B(x))x(A(x)∨B(x)) P→QP∨Q (xA(x)∧xB(x))xA(x)∨xB(x) 摩根律null替换规则 设A(x1, x2,…, xn) B(x1, x2, …, xn), 而A是公式C中的子公式, 将B替换C中之A不必每一处得D, 则CD。 对偶原理 在公式A  B或A  B中, A , B仅含运算符∧ , ∨和, 将上式中的全称量词与存在量词互换, ∧与∨互换, T和F互换, 则 A*  B *, B*  A*1.8 谓词演算的推理规则1.8 谓词演算的推理规则谓词演算中推理的形式结构 推理的形式结构仍为 H1∧H2∧…∧Hn  C 若H1∧H2∧…∧Hn →C是永真式,则称 前提H1,H2,…,Hn逻辑的推出结论C, 其中H1,H2,…,Hn和C都是谓词公式 谓词演算中的推理规则 命题演算中的推理规则,可在谓词推理理论中应用 P规则、T规则、CP规则 与量词有关的规则全称指定规则 US (Universal Specialization)全称指定规则 US (Universal Specialization)又称全称示例规则 作用:去掉全称量词 两种形式: xA(x)A(y) xA(x)A(c) 使用此规则时要注意: (1)y为任意不在A(x)中约束出现的个体变元; (2)c为任意的个体常元 例:设A(x,y):x
本文档为【谓词逻辑】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑, 图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
下载需要: 免费 已有0 人下载
最新资料
资料动态
专题动态
is_598372
暂无简介~
格式:ppt
大小:881KB
软件:PowerPoint
页数:0
分类:
上传时间:2011-10-12
浏览量:105