离散数学03谓词和量词

1、11.3 谓词和量词2l含变量的陈述句不是命题？！含变量的陈述句不是命题？！ 教室教室 x 正在上课正在上课l命题函数命题函数 p(x)谓词谓词 主语主语(x)：变量，谓语：变量，谓语(p)：x 具有的性质具有的性质 变量被赋值后，谓词变量被赋值后，谓词 命题命题 谓词本身不是命题！谓词本身不是命题！例例 13l谓词谓词 p(x) 可以有多个变量：可以有多个变量：多元谓词多元谓词 例例2, 例例3l有有 n 个变量的谓词个变量的谓词 记为记为 p(x1, x2, , xn)n 元谓词元谓词4l程序中的谓词程序中的谓词 谓词谓词 p(x)：x0l程序验证中的谓词程序验证中的谓词 前置条件前置条件

2、 p(x, y)： x = x0, y = y0 后置条件后置条件 q(x, y)： x = y0, y = x0例例 7temp = xx = yy = temp例例 6if ( x0 ) x = x + 15l含变量的陈述句：主语含变量的陈述句：主语个体词个体词，谓语，谓语谓词谓词 变量变量个体变量个体变量，陈述句，陈述句命题函数命题函数 p(x)：x 3l变量赋值后的陈述句变量赋值后的陈述句 变量值变量值个体常量个体常量，陈述句，陈述句命题命题 p(2)：2 36l三段论三段论每个人都要死每个人都要死张三是人张三是人张三要死张三要死l实际中经常使用的推理方式实际中经常使用的推理方式 在命

3、题逻辑系统中应如何表示？在命题逻辑系统中应如何表示？7l命题逻辑符号化命题逻辑符号化每个人都要死每个人都要死张三是人张三是人张三要死张三要死l在符号化后的形式结构中，看不到推理在符号化后的形式结构中，看不到推理pqr8l复合命题复合命题 p q r p(每个人都要死每个人都要死)，q(张三是人张三是人)，r(张三要死张三要死) p、q、r 是是 3 个独立命题个独立命题 明显地，明显地，3 句话之间存在关联句话之间存在关联 进一步，是进一步，是 3 句话的内部成分之间有关联句话的内部成分之间有关联 命题逻辑无法表示出这些内部成分及其关系！命题逻辑无法表示出这些内部成分及其关系！9l因为：命题逻

4、辑中原子命题是不可分的因为：命题逻辑中原子命题是不可分的 现在需要分解，才能找出相互之间的关系现在需要分解，才能找出相互之间的关系l引入命题函数引入命题函数(个体词谓词个体词谓词) 如如 p(x)：x 是人，是人，q(x)：x 要死要死 x张三张三 p(张三张三)：张三是人，：张三是人，q(张三张三)：张三要死：张三要死 “每个人都要死每个人都要死” 如何表示？如何表示？10l命题函数：展现出语句的内部结构命题函数：展现出语句的内部结构 p(x)：x 是人，是人，q(x)：x 要死要死 p(张三张三)：张三是人，：张三是人，q(张三张三)：张三要死：张三要死l“每个人都要死每个人都要死”？ 与

5、上述两个命题函数之间的关联？与上述两个命题函数之间的关联？ 如果是人，那么要死：如果是人，那么要死：p(x)q(x)“每个人每个人”呢？呢？11lex. 以下公式中以下公式中 x 属于整数属于整数(z) (x+1)2=x2+2x+1 任意整数代入均正确：任意整数代入均正确：x 的的取值范围取值范围=z x+1=5 只有只有 1 个整数代入才正确：个整数代入才正确：x 的的取值范围取值范围= 4 0 x+13，则，则3y，g(x, y)：xy2324l王强是大学生李华也是大学生王强是大学生李华也是大学生 论域论域所有大学生所有大学生 令令f(x)：x是大学生是大学生 令令a：王强，：王强，b：李

6、华：李华 f(a) f(b)25l中国代表团访问朝鲜中国代表团访问朝鲜 论域所有国家论域所有国家 f(x, y)：x 访问访问 y a：中国代表团，：中国代表团，b：朝鲜：朝鲜 f(a, b)26l这座大楼建成了这座大楼建成了 论域所有楼宇论域所有楼宇 f(x)：x建成了建成了 g(x)：x是大的是大的 h(x)：x是楼是楼 a：这个：这个 f(a) g(a) h(a)27l这个人正在看那本红皮面的书这个人正在看那本红皮面的书 论域全总论域论域全总论域 f(x,y)：x正在看正在看y g(x)：x是人是人 h(y)：y是红皮面的是红皮面的 u(y)：y是书是书 a：这个，：这个，b：那本：那本

7、 f(a,b) g(a) h(b) u(b)28l实例：将下面命题符号化实例：将下面命题符号化1. 论域：人类集合论域：人类集合人都爱美人都爱美有人用左手写字有人用左手写字2. 论域：全总论域论域：全总论域人都爱美人都爱美有人用左手写字有人用左手写字29l论域：人类集合论域：人类集合 人都爱美：人都爱美： xg(x) g(x)：x爱美爱美 有人用左手写字：有人用左手写字： xg(x) g(x)：x用左手写字用左手写字30l论域：全总论域论域：全总论域 (个体变量可以是任意事物个体变量可以是任意事物)人都爱美人都爱美 f(x) x ( f(x)g(x) ) 错误的表示！错误的表示！ x ( f(

8、x) g(x) )有人左手写字有人左手写字 f(x) x ( f(x) g(x) ) 错误的表示！错误的表示！ x ( f(x)g(x) )x 是人，是人，g(x)：x 爱美爱美x 是人，是人，g(x)：x 左手写字左手写字31l3 个命题组成的推理链个命题组成的推理链 前前2个命题：前提个命题：前提(premises) 最后最后1个命题：结论个命题：结论(conclusion) 3个命题整体：论证个命题整体：论证(argument)l例例26、例、例27 为什么这样的推理是有效的为什么这样的推理是有效的?32l所有大于所有大于1mb的邮件将被压缩的邮件将被压缩l如果有一个用户被激活，至少要有

9、一个如果有一个用户被激活，至少要有一个可用网络连接可用网络连接33l所有大于所有大于1mb的邮件将被压缩的邮件将被压缩 论域论域 = 所有邮件所有邮件 s(x)：x大于大于1mb c(x)：x被压缩被压缩 x(s(x)c(x)34l如果有一个用户被激活，至少要有一个如果有一个用户被激活，至少要有一个可用网络连接可用网络连接 论域论域所有用户所有用户所有网络连接所有网络连接 a(u)：用户：用户u被激活被激活 s(i)：网络连接：网络连接i可用可用 u a(u)i s(i)35l出现在其他量词作用域内的量词出现在其他量词作用域内的量词 给出表达式中的量词、谓词含义给出表达式中的量词、谓词含义 整

10、理含义，争取用简单句子表示整理含义，争取用简单句子表示l嵌套量词嵌套量词多重循环多重循环例例 1、236l当不同类型量词交叉嵌套时，顺序很重要当不同类型量词交叉嵌套时，顺序很重要 、 交叉嵌套交叉嵌套l两个变量的嵌套顺序两个变量的嵌套顺序 表表1-24 (注意：注意： 与与 不能随意交换不能随意交换)例例 3, 4, 537l练习：设论域为实数域，将下面命题符号化练习：设论域为实数域，将下面命题符号化 对每一个数对每一个数x，都存在一个数，都存在一个数y，使得，使得xy x yl(x,y)，l(x,y)：xy 存在一个数存在一个数x，使得对每一个数，使得对每一个数y，都有，都有xy x yl(x，y)，l(x，y)：xy38l数学语句数学语句谓词逻辑表达式谓词逻辑表达式 例例 6、7、8 量词隐含在语句中量词隐含在语句中l日常语句日常语句谓词逻辑表达式谓词逻辑表达式 例例 11、12、13 论域的范围决定量词的使用论域的范围决