1、离散数学之数理逻辑（ 3）上海交通大学软件学院吴刚2009年 6月内容n 谓词逻辑n 谓词与个体n 量词n 函数n 谓词逻辑公式n 自由变元与约束变元n 谓词逻辑的永真公式n 范式命题逻辑的局限性n 前提 :n 四班的同学下周都要去春游n 张三是四班的同学n 结论 :n 张三下周要去春游n 用命题逻辑无法完成上述推理n 原子命题不可再分割谓词与个体n 将原子命题分解成谓词和个体，引出谓词逻辑n 个体：命题中名词性的主体n 谓词：用于描述个体的性质或个体间的关系n 一元谓词：与一个个体相连n 多元谓词：与多个个体相连n 多元谓词中有时个体的出现顺序是相关的谓词与个体n 符号表示n 用大写字母 F
2、/G等表示谓词，用小写字母a/b/c等表示个体n 例子：用 F(x)表示 x是大学生，用 a表示张三，用 b表示李四，则 “张三是大学生 ”表示为F(a)， ”张三和李四都是大学生 ”表示为F(a) F(b)；n 例子：用 F(x,y)表示 x严重影响了 y，用 a表示猪流感，用 b表示墨西哥，则 “猪流感严重影响了墨西哥 ”表示为 F(a,b)，而 F(b,a)是不正确的谓词与个体n 上述 F(x)和 F(x,y)中 x,y被称为 个体变元 ，其取值范围被称为 个体域n F(x)和 F(x,y)被称为 谓词命名式 ，明确了谓词与个体是如何构成命题的，其中个体变元的顺序是相关的。实际她就是一元
3、或多元函数，定义域是个体域，值域是 T或 F。当个体变元被赋值后，命题及其真值就确定了量词n 有些谓词命名式对于其中个体的 所有 取值，其真值均为 T；n 有些谓词命名式对于其中个体的 部分 取值，其真值为 T；n 如何区分 所有和部分 的关系呢？n 引入量词：全称量词和存在量词量词n 全称量词n 对于个体变元 x的所有取值 F(x)为真，则表示为 x (F(x)， x 叫全称量词n 存在量词n 对于个体变元 x的部分取值 F(x)为真，则表示为 x (F(x)， x 叫存在量词量词n 当给一个谓词命名式中的所有变元施加量词约束后，在 给定的个体域 下形成的公式其真值是确定的n 例子： F(x)表示 x会哺乳后代n 当个体域为哺乳动物时， x (F(x)为真；n 当个体域为所有动物时， x (F(x)为假，但 x (F(x)为真量词n 个体域的表达n 个体域的定义本身也是一个谓词命名式n x (F(x)且 x A，可以表达为 x (G(x) F(x)，用 G(x)表示 x An x (F(x)且 x A，可以表达为 x (G(x) F(x)，用 G(x)表示 x An 这样 x的取值就可以任意了
