《离散数学 第2版 教学课件 ppt 作者 王元元 离散第14，15讲 谓词演算永真式(上,下)》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第14，15讲 谓词演算永真式(上,下)（34页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,理工大学指挥自动化学院,-2-,第14讲 谓词演算永真式,量词嵌套语句的谓词形式化,每个人都有些缺点 M(x): x是人；F(x): x是缺点；H(x,y):x有y x (M(x) y(F(y)H(x,y) 每个人都有人爱，但没有人为所有人爱 M(x)：x是人，L(x,y)：x爱y x (M(x)y(M(y)L(y,x) x (M(x)y(M(y)L(y,x) 有且仅有一个偶质数 P(x)：x是偶数；Q(x)：x是质数 !x(P(x)Q(x) x(P(x)Q(x)y(P(y)Q(y)x=y) x(P(x)Q(x)xy(P(x)Q(x
2、)P(y)Q(y) x=y),-3-,第14讲 谓词演算永真式,量词嵌套语句的谓词形式化,并不是火车都比汽车跑的快，有的汽车比有的火车跑的快 T(x): x是火车；C(x): x是汽车；F(x,y):x比y快 x (T(x)y(C(y)F(x,y)x(C(x)y(T(y)F(x, y) xy(T(x)C(y)F(x,y)x(C(x)y(T(y)F(x, y) 有位妇女已搭乘过世界上每一条航线上的航班 W(x)：x是妇女；L(x)：x是航线；F(x)：x是航班 Q(x, y)：x是y航线上的航班； P(x, y)：x搭乘过y航班 x(W(x)y(L(y)z(F(z)Q(z,y)P(x, z),P
3、owerPoint Template_Sub,谓词演算基本概念,谓词演算永真式,谓词演算永真式（上）,离散数学第14讲,Page 54 to 56,-6-,第14讲 谓词演算永真式,回顾,(pq)r,(p qr) (pqr) (pqr),(0,0,0),(0,1,0),(1,0,0),xL(x2,y),个体域：实数域 L(x,y)：x y 当y=0时，为真；当y0时，为假；,指派决定命题公式真值,只有在给定了个体域和谓词的意义，再给每一自由变元都指定一个具体的个体之后，谓词公式成为关于个体域的一个命题，才可判定其真值,-7-,第14讲 谓词演算永真式,回顾,x(f(x) = a)y=1,个体域
4、：实数域 函数f：f(x) = x2 个体常元a：a = 5 个体变元y：y = 1 真,个体域：实数域 函数f：f(x) = x2 个体常元a：a = 2 个体变元y：y = 1 假,个体域：实数域 函数f：f(x) = x3 个体常元a：a = 2 个体变元y：y = 1 真,当公式中出现函数和个体常元时，还必须确定函数的意义和常元的取值，才能确定谓词公式的真值,-8-,第14讲 谓词演算永真式,回顾和展望,下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了 p:马芳下午去看电影; q:马芳下午去游泳 前提： pq， p 结论： q (pq)p q， (pq)pq为永真式 所有人都
5、是要死的，苏格拉底是人，那么苏格拉底也是要死的 M(x): x是人；D(x): x是要死的 前提： x(M(x)D(x),M(Socrates) 结论： D(Socrates) x(M(x)D(x)M(Socrates)D(Socrates) ? x(M(x)D(x)M(Socrates)D(Socrates) 为永真式?,-9-,第14讲 谓词演算永真式,解释与谓词公式的真值,定义：将公式中的谓词、函数符号、常元符号对应于个体域上具体的性质、关系、函数、对象，这种对应关系称为解释，常用大写字母I表示 I恒把命题常元解释为真值0或1 谓词公式真值的确定 确定个体域 给定一个解释（谓词、函数符号
6、、常元符号） 将自由变元指派到个体域中具体的个体,-10-,第14讲 谓词演算永真式,谓词公式的真值,个体域 D1=3, 4 D2=3, 5,解释 I 1：P(x)表示x是质数 I 2：P(x)表示x是合数,-11-,第14讲 谓词演算永真式,谓词公式的真值,个体域 D1=3, 4 D2=3, 5,解释 I 1：P(x)表示x是质数 I 2：P(x)表示x是合数,-12-,第14讲 谓词演算永真式,谓词公式的多层次真值概念,我们给谓词公式定义以下四个层次的真值概念 1、在确定的域D上，在D上确定的解释I下，指派下真 2、在确定的域D上，解释I下真 3、在域D上真(D上永真) 4、永真式在一切域
7、D上永真，即对每一个域上的一切解释下，对每一解释的任一指派下均为真,-13-,第14讲 谓词演算永真式,谓词公式的真值,P(x) 个体域1，2，P(x)的解释：x0，Q(x)表示x=1，R(x)表示x是偶数 公式为假，非永真式 xP(x) xP(x) 只有一个元素的个体域D上，总是D上永真的 当D中的成员个数大于1时，它就不再是D上永真了 x(P(x)P(x) xP(x)xP(x),-14-,第14讲 谓词演算永真式,可满足式与不可满足式,定义：公式A称为可满足的，如果能够找到某一个体域，该域上的某种解释，以及对公式中变元的某一种指派，使得A在此个体域、解释和指派下为真。否则称A为不可满足的，
8、或永假式 当A为永真式时，A一定是永假式；反之亦然,-15-,第14讲 谓词演算永真式,逻辑等价和逻辑蕴涵,定义：设A和B是谓词公式，如果AB为永真式，即对一切的域、每一域上的一切解释、以及每一解释下个体变元的任一指派，A和B都具有相同的真值，则称A逻辑等价于B，记作AB 定义：设A和B是谓词公式，如果AB为永真式，即对一切的域和每一域上的一切解释，任一使A真的个体变元指派均同时使B真，则称A逻辑蕴涵B，记作A B B表示B永真 B,-16-,第14讲 谓词演算永真式,由命题演算重言式得到的谓词演算永真式,命题是0元谓词，命题公式是谓词公式的一个子集 所有命题演算中的重言式都是谓词演算的永真式
9、 命题演算中的逻辑等价式都是谓词演算中的逻辑等价式 命题演算中的逻辑蕴涵式都是谓词演算中的逻辑蕴涵式,A(BC)(AB)(AC) ABCA(BC) ABAB ABBA (AB) (AB) A ,A AB, B AB AB A, AB B A(AB) B (AB)B A A(AB) B ,-17-,第14讲 谓词演算永真式,由命题演算重言式得到的谓词演算永真式,ABAB,A(x)B(x)A(x)B(x),AA,A(x) A(x),(AB)AB,(A(x) B(x) A(x) B(x),A(BC)(AB)(AC),A(x)(B(x)C(x)(A(x)B(x)(A(x)C(x),(AB) (AB)
10、A,(A(x) B(x) (A(x) B(x) A(x),命题演算的重言式中，同一命题变元用相同的谓词公式代替后所得的仍是永真式,pp,P(x) P(x) yP(x,y) yP(x,y),p(qp),P(x,y) (yP(x,y)Q(y) P(x,y),-18-,第14讲 谓词演算永真式,谓词演算特有的永真式,1、消去量词等价式 设个体域为有限集D=a1,a2,an，有 xA(x)A(a1) A(a2) A(an) xA(x)A(a1) A(a2) A(an) 若A是不含有自由变元x的谓词公式 xAA xAA,-19-,第14讲 谓词演算永真式,谓词演算特有的永真式,2、 e是任一个体常元 x
11、A(x) A(e) A(e) xA(x) xA(x) xA(x),-20-,第14讲 谓词演算永真式,谓词演算特有的永真式,3、 号深入量词的辖域 xA(x)xA(x) xA(x)xA(x) xA(x)xA(x) xA(x)xA(x),个体域为有限集D=a1,a2,an xA(x)(A(a1) A(a2) A(an) A(a1) A(a2) A(an) xA(x),-21-,第14讲 谓词演算永真式,谓词演算特有的永真式,3、 号深入量词的辖域 xA(x)xA(x) xA(x)xA(x) xA(x)xA(x) xA(x)xA(x),应用：x y z(x=y+z),从公式看，x和x具有对偶性，两
12、个量词之一可以由另一个代替，所以从理论上讲，量词只需一个就够了,-22-,第14讲 谓词演算永真式,谓词演算特有的永真式,4、量词辖域的扩张与收缩 如果B是不含有自由变元x的谓词公式，则 xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B) xA(x)Bx(A(x)B),个体域为有限集D=a1,a2,an xA(x) B (A(a1)A(a2) A(an) B (A(a1) B) (A(an) B) x(A(x) B),应用： xA(x) yB(y),-23-,第14讲 谓词演算永真式,谓词演算特有的永真式,5、量词的分配形式 x(A(x)B(x)xA(x)
13、x B(x) xA(x)x B(x) x(A(x)B(x) x(A(x)B(x) xA(x)x B(x) x(A(x)B(x)xA(x)x B(x),个体域为有限集D=a1,a2,an x(A(x)B(x) (A(a1)B(a1)(A(a2)B(a2)(A(an)B(an) (A(a1)A(a2)A(an) (B(a1)B(a2)B(an) xA(x)x B(x),-24-,第14讲 谓词演算永真式,谓词演算特有的永真式,5、量词的分配形式 x(A(x)B(x)xA(x)x B(x) xA(x)x B(x) x(A(x)B(x) x(A(x)B(x) xA(x)x B(x) x(A(x)B(x
14、)xA(x)x B(x),x(A(x)B(x)xA(x)x B(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),-25-,第14讲 谓词演算永真式,谓词演算特有的永真式,5、量词的分配形式 x(A(x)B(x)xA(x)x B(x) xA(x)x B(x) x(A(x)B(x) x(A(x)B(x) xA(x)x B(x) x(A(x)B(x)xA(x)x B(x),x(A(x)B(x)xA(x)xB(x)？,个体域为自然数集合；A(x):x是奇数；B(x):x是偶数,x(A(x)B(x)xA(x)xB(x)？,个体域为自然数集合；A(x):x是奇数；B(x):x是偶数,x(A(x)B(x) xA(x)x B(x)不能成立,xA(x)xB(x) x(A(x)B(x)不能成立,能否从(2
