离散数学 第2版 教学课件 作者 王元元 离散第14，15讲 谓词演算永真式(上,下).ppt

《离散数学 第2版 教学课件 作者 王元元 离散第14，15讲 谓词演算永真式(上,下).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机专业基础课程授课人：王元元单位：计算机理论教研室理工大学指挥自动化学院量词嵌套语句的谓词形式化每个人都有些缺点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))∧xy(P

2、(x)∧Q(x)∧P(y)∧Q(y)→x=y)2第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)┐xy(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

3、)→z(F(z)∧Q(z,y)∧P(x,z))))3第14讲谓词演算永真式PowerPointTemplate_Sub1谓词演算基本概念2谓词演算永真式4第14讲谓词演算永真式谓词演算永真式（上）《离散数学》第14讲Page54to56回顾(p∧q)∨r(p∨q∨r)∧(p∨┐q∨r)∧(┐p∨q∨r)(0,0,0)(0,1,0)(1,0,0)xL(x2,y)个体域：实数域L(x,y)：x≥y当y=0时，为真；当y≠0时，为假；指派决定命题公式真值只有在给定了个体域和谓词的意义，再给每一自由变元都指定一个具体的个体之后，谓词公式成为关于个体域的一个命题，才可判定其真值6

4、第14讲谓词演算永真式回顾x(f(x)=a)∧y=1个体域：实数域函数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真当公式中出现函数和个体常元时，还必须确定函数的意义和常元的取值，才能确定谓词公式的真值7第14讲谓词演算永真式回顾和展望下午马芳或去看电影或去游泳。她没去看电影。所以，她去游泳了p:马芳下午去看电影;q:马芳下午去游泳前提：p∨q，┐p结论：q(p∨q)∧┐p┝q，(p∨q)∧┐p→q为永真式所有人

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)为永真式?8第14讲谓词演算永真式解释与谓词公式的真值定义：将公式中的谓词、函数符号、常元符号对应于个体域上具体的性质、关系、函数、对象，这种对应关系称为解释，常用大写字母I表示I恒把命题常元解释为真值0或1谓词公式真值的确定确定个体域给定一个解释（谓词、函数

6、符号、常元符号）将自由变元指派到个体域中具体的个体9第14讲谓词演算永真式谓词公式的真值个体域D1={3,4}D2={3,5}个体域解释指派P(x)yP(y)yP(y)→P(x)D1I1x=3x=4I2x=3x=4D2I1x=3x=5I2x=3x=5解释I1：P(x)表示x是质数I2：P(x)表示x是合数10第14讲谓词演算永真式谓词公式的真值个体域D1={3,4}D2={3,5}个体域解释指派P(x)yP(y)yP(y)→P(x)D1={3,4}I1：P(x)表示x是质数x=3x=4101110I2：P(x)表示x是合数x=3x=4011101D2={3,5}I1

7、：P(x)表示x是质数x=3x=5111111I2P(x)表示x是合数x=3x=5000011解释I1：P(x)表示x是质数I2：P(x)表示x是合数11第14讲谓词演算永真式谓词公式的多层次真值概念我们给谓词公式定义以下四个层次的真值概念1、在确定的域D上，在D上确定的解释I下，指派下真2、在确定的域D上，解释I下真3、在域D上真(D上永真)4、永真式——在一切域D上永真，即对每一个域上的一切解释下，对每一解释的任一指派下均为真12第14讲谓词演算永真式谓词公式的真值P(x)个体域{﹣1，2}，P(x)的解释：