《交大数理逻辑课件4-1谓词逻辑的基本概念幻灯片》由会员分享，可在线阅读，更多相关《交大数理逻辑课件4-1谓词逻辑的基本概念幻灯片（29页珍藏版）》请在金锄头文库上搜索。
1、作业讲评1,第1章习题,P12：2(2)用自然语言叙述：(P Q) 设P：今天很冷，Q：正在下雪 (PQ)：今天不是既很冷又下雪 P13：5(7)形式自然语言： 如果水是清的，那么或者张三能见到池底或者他是个近视眼 设P：水是清的， Q：张三能见到池底， R：张本是个近视眼 P(QR)(QR) P (Q R),不可兼或,第1章习题,P13：6将下公式写成波兰式和逆波兰式 (1) PQ R S P Q R S P Q R S P (WR) Q P W R Q 或 P W R Q P W R Q ,第4章 谓词逻辑的基本概念,4.1 谓词和个体词 4.2 函数和谓词 4.3 合式公式 4.4 自然
2、语句的形式化 4.5 有限域下公式(x)P(x)、(x)P(x) 的表示法 4.6 公式的普遍有效性和判定问题,一阶逻辑,在命题逻辑中最基本的研究对象是命题 一个原子命题是不能再分割的,两个命题之间没有任何内在的联系 这种研究方法显然不足以刻划世界上事物间千变万化的逻辑关系 就连最古老、最简单的苏格拉底三段论也无法从命题逻辑中推出 前提：凡人都是要死的 p 苏格拉底是人 q 结论：苏格拉底是要死的 r,p q r,谓词演算,谓词演算(一阶谓词演算）是命题演算的扩充和发展 一阶谓词演算 是重要的符号逻辑系统 它是程序设计理论、语义形式化及程序逻辑研究的重要基础，是程序验证、程序分析、综合及自动生
3、成、定理证明和知识表示的有力工具。,4.1 谓词和个体词,在谓词演算中，将原子命题分解为谓词和个体两部分。 如： 张三是人。,个体 可以独立存在的东西，它可以是一个具体的事物，也可以是一个抽象的概念。 谓词 用于刻划个体的性质和个体之间的关系,个体,谓词,个体,考察下面的三个原子命题： 李玲是优秀共青团员。 张华比李红高。 小高坐在小王和小刘的中间。 个体的分类 个体常项：表示具体或特定个体的标识符 如 a：李玲，b：张华，c：李红，d：小高，e：小王，f：小刘 个体变项：表示任意个体或泛指某类个体的标识符 如：偶数、生物，用x, y, z表示 个体域D 个体变项的变化范围 有限个体域：如a,
4、 b, c, 1, 2 无限个体域：如N, Z, R, 全总个体域: 宇宙间一切事物组成（默认的个体域）,谓词,考察下面的三个原子命题： 李玲是优秀共青团员。 张华比李红高。 小高坐在小王和小刘的中间。 谓词:用于刻划个体性质或各个个体的关系，常用大写英文字母表示。 谓词常项： 如：F: 是人，则 F(a)：a是人 谓词变项： 如：F: 具有性质F，则F(x)：x具有性质F 如：可用F，G，H表示上面三个命题中谓词： F：是优秀共青团员。 G：比高。 H：坐在和的中间。,谓词,考察下面的三个原子命题： 李玲是优秀共青团员。 张华比李红高。 小高坐在小王和小刘的中间。 如：可用F，G，H表示上面
5、三个命题中谓词： F：是优秀共青团员。 G：比高。 H：坐在和的中间。 谓词的分类 一元谓词: 刻划一个个体的性质，如谓词F(x) 多元谓词: 刻划两个或以上个体间的关系， 如 L(x,y)：x与y有关系L，L(x,y)：xy， 如谓词G(x,y)、H(x,y,z) 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项,F(a),G(b,c),H(d,e,f ),a：李玲，b：张华，c：李红，d：小高，e：小王，f： 小刘,4.2 函数和量词,函数 它是某个体域到另一个体域的映射，由一个谓词字母和n个个体变项组成的表达式：F(x, y, , z) 注意： F(x, y, , z)不是命题，它
6、的真值无法确定，要想使它成为命题，必须指定某一谓词常项代替F，同时还要用n个个体常项代替n个个体变项。 如：L(x, y) 是一个二元谓词，它不是命题。 当令L表示“小于”之后，L(x, y) 还不是命题。 当令a=2，b=3时， L(a, b) 才是命题，并且是真命题。 当令c=2，d=1时， L(c, d) 为假命题。,将下列命题用谓词符号化,(1) 如果23，则33，q：3y， G(x,y)：xy, 命题符号化为 F(2,3) G(3,4),(2) 2是素数且是偶数。 在命题逻辑中, 设 p: 2是素数, q: 2是偶数 命题符号化为： p q, 这是真命题 在一阶逻辑中, 设F(x)：
7、x是素数。 G(x)：x是偶数。 a：2， 命题符号化为： F(a) G(a),将下列命题用谓词符号化,(3)如果张明比李民高，李民比李民高，则张明比赵亮高。 解：在命题逻辑中， 设：p：张明比李民高，q：李民比李民高 r：张明比赵亮高 则命题符号为： p q r 在一阶逻辑中， 设 H(x, y)：x比y高。 a：张明； b：李民；c：赵亮， 则命题符号化为： H(a, b) H(b, c) H(a, c),4.2.2 量词,引入量词表示个体域中所有个体或部分个体具有某种性质。 全称量词: 表示任意的, 所有的, 一切的等 如: x 表示对个体域中所有的x xF(x) 表示个体域里的所有个体
8、都有性质F 存在量词: 表示存在, 有的, 至少有一个等 如: x 表示在个体域中存在x xF(x)表示存在着个体域中的个体具有性质F,（1） 每个人都有一双手。 （2） 有的人很聪明。,（1） 每个人都有一双手。 （2） 有的人很聪明。 第一种情况考虑个体域D为人类集合。 (1) 符号化为：xF(x) ， 其中F(x) ：x都有一双手。 这个命题是真命题。 (2) 符号化为 xF(x)， 其中F(x) ：x很聪明。 这个命题也是真命题。,在一阶逻辑中将下面命题符号化,（1） 每个人都有一双手。 （2） 有的人很聪明。 第二种情况，考虑个体域D为全总个体域。 引出一个新的谓词，将人分离出来:
9、M(x)：x是人。 称这个谓词为特性谓词。 在全总个体域的情况下，以上两命题可叙述如下 (1)对所有个体而言，如果它是人，则它有一双手。 (2)存在着个体，它是人并且很聪明。 则（1）符号化为x( (M(x)F(x) ) （2）符号化为x ( (M(x)F(x) )，,在一阶逻辑中将下面命题符号化,4.2.3 约束变元和自由变元,定义 在公式(x)A和(x)A中，称x为指导变元，称A为辖域. 在x和x的辖域中， x的所有出现都称为约束出现， A中不是约束出现的其他变元均称为是自由变元。 如：在公式 (x)(F(x,y)G(x,z) 中 A=(F(x,y)G(x,z)为x的辖域， x是约束变元，
10、 y与z均为自由变元。 如(x)P(x) (z) Q(x, z) (y)R (x, y) Q(x, y) 在x中，x、y、z是约束变元， Q(x, y)中x，y是自由变元。 闭式: 不含自由变元的公式.,约束变元的换名规则,如：(x)P(x)R(x,y) (x)的辖域为P(x)，x是约束变元 R(x,y)中x, y 都是自由变元 x既可以是约束的、又可以是自由的，容易混淆。 换名规则 将量词辖域中的某个约束出现的个体变项及对应的指导变项改成公式中未曾出现的个体变项符号，公式中的其余部分不变。 注意： 改名时一定要更改为辖域中没有出现的变元名称。 例如： (x) P(x)R(x,y) 改名为：
11、(z) P(z)R(x,y) 或(x) P(x)R(z,y),自由变元的代入规则,代替规则 对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。 注意： 用以代入的变项与原公式中所有变项名不能相同 如： (x)F(x) G(x, y) 利用代替规则： (x)F(x) G(z, y) (x)P(x) (z)Q(x, z) (y)R(x, y) Q(x, y) 对Q(x, y)中自由出现的x用t代入，y用s代入则： (x)P(x) (z)Q(x, z) (y)R(x, y) Q(t, s),4.3 合式公式(谓词公式),量词的作用范围： 量词仅作用于个体变元，不允许
12、作用于命题变项和谓词变项，不出现： (p)(F(x,y)p), (F)(F(x,y)G(x,z) 本课程中用到的符号说明： 命题变项： p, q, r, , pi, qi, ri, , i 1 个体变项：x, y, z, , xi, yi, zi, , i 1 个体常项：a, b, c, , ai, bi, ci, , i 1 谓词变项：P, Q, R, , Pi, Qi, Ri, , i 1 谓词常项：GREAT, ON, 函数符号：f, g, h, , fi, gi, hi, , i 1 量词符号：, 联结词符号：, , , , 括号与逗号：(, ), ，,合式公式(谓词公式),合式公式定
13、义如下： (1) 命题常项、命题变项和原子谓词公式（不含联结词的谓词）是合式公式. (2) 若A是合式公式，则 (A)也是合式公式 (3)若A, B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式 (4) 若A是合式公式，而x在A中是自由变元，则 (x)A, (x)A 也是合式公式 (5) 只有适合以上4条的才是合式公式. 如：(x)( (M(x) F(x) ),4.4 自然语句的形式化,自然数集的形式描述 对每个数，有且仅有一个相继后元 解：注意到题目中没给个体域, 一律用全总个体域 设：谓词E(x,y)：x=y 函数 f(x)=x+1 (表示个体x的相继后元) 理解为
14、： 对每个x都存在y, y是x的相继后元，且对任一z，若它也是x的相继后元，则必有y=z 形式化为： (x)(y)(E(y,f(x) (z)(E(z,f(x)E(y,z),自然语句的形式化,自然数集的形式描述 没有这样的数，0是其相继后元 解：注意到题目中没给个体域, 一律用全总个体域 设：谓词E(x,y)：x=y 函数 f(x)=x+1 (表示个体x的相继后元) 理解为： 不存在x，它的相继后元为0 形式化为： (x)(E(0,f(x),自然语句的形式化,自然数集的形式描述 对除0外的数，有且仅有一个相继前元 解：注意到题目中没给个体域, 一律用全总个体域 设：谓词E(x,y)：x=y 函数
15、 g(x)=x -1 (表示个体x的相继前元) 理解为： 对每个x, 若x0, 都存在y, y是x的相继前元，且对任一z，若它也是x的相继前元，则必有y=z 形式化为： (x)(E(x,0)(y)(G(y,f(x) (z)(G(z,f(x)E(y,z),在一阶逻辑中将下面命题符号化,有的自然数无先驱数。 解：注意到题目中没给个体域, 一律用全总个体域 设： F(x)：x是自然数。 L(x,y)： x是y的先驱数。 此命题符号为： x (F(x) y (F(y) L( y , x) ) ) 解释为： 存在自然数x，对任意的自然数y，y不是x的先驱数,在使用量词时，应注意以下特点,在不同个体域中，命题符号化的形式可能不一样。 如 “有的人很聪明。” 在人类集合个体域中， xF(x) 在全总个体域中， x ( (M(x)F(x) ) 若事先没有给出个体域，都默认为全总个体域。 在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的 如 “有的人很聪明。” x ( (M(x) F(x) ) 如“每个人都有一双手” x( (M(x) F(x)
