《离散数学课件-2谓词逻辑》由会员分享，可在线阅读，更多相关《离散数学课件-2谓词逻辑（60页珍藏版）》请在金锄头文库上搜索。
1、第二章 谓词逻辑,合肥工业大学数学学院 邢燕,2.1 谓词的概念与表示,命题逻辑的局限性： 下列推理：凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 众所周知，这是真命题。但在命题逻辑中 ( P Q ) R ，难证其为重言式。,原因：命题逻辑不考虑命题之间的内在联系和数量关系。 办法：将命题再次细分。,2.1 谓词的概念与表示,谓词 在反映判断的句子中，用以刻划客体的性质或关系的即是谓词。 例：(1)3是有理数。 (2)x是无理数。 (3)阿杜与阿寺同岁。 (4)x与y有关系L。 其中，“是有理数”、“是无理数”、“与同岁”、“与有关系L”均为谓词。前两个是指明客体性质的谓词，后两个是
2、指明两个客体之间关系的谓词。,2.1 谓词的概念与表示,将上述谓词分别记作大写字母F、G、H、L，用小写字母表示客体名称，则上述可表示为： (1)F(3) (2)G(x) (3)H(a,b) a:阿杜 b:阿寺 (4)L(x,y) 谓词填式 单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。,2.1 谓词的概念与表示,n元谓词 由n个客体插入到固定位置上的谓词填式。 例如：A(b)称作一元谓词，B(a, b)称作二元谓词，L(a, b, c)称作三元谓词，P(x1 , x2 , , xn)称作n元谓词。 注意：代表客体名称的字母，它在多元谓词中出现的次序是固定的，与事先约
3、定的次序有关，如L(a, b, c)和L(b, c, a)代表两个不同的命题。,2.2 命题函数与量词,例：H是谓词“能够到达山顶”，t表示老虎，c表示汽车，z表示张三，那么H(t), H(c), H(z)表示三个不同的命题，但它们有一个共同的形式H(x)，当x分别取t, c, z 时。 L(x, y)表示“x小于y”，那么L(2, 3)表示了一个真命题“2小于3”，而L(5, 1)表示假命题“5小于1”。可以看出，L(x, y)本身不是一个命题，只有当变元x, y取特定的客体时，才是一个命题。,2.2 命题函数与量词,简单命题函数 由一个谓词，一些客体变元组成的表达式称为简单命题函数。 n元
4、谓词就是有n个客体变元的命题函数。 不带任何客体变元的谓词称为0元谓词。 复合命题函数 由一个或n个简单命题函数以及逻辑联结词组合而成的表达式称复合命题函数。,2.2 命题函数与量词,命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。 但客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。 例：R(x)表示“x是大学生”，如果x的讨论范围是某大学里班级中的学生，则R(x)是永真式。如果x的讨论范围是某中学里班级中的学生，则R(x)是永假式。如果x的讨论范围为一剧场中的观众，那么对某些观众，R(x)为真，对另一些观众，R(x)为假。,2.2 命题函数与量词,个体
5、可以独立存在的具体的或抽象的客体。 个体常量：具体的或特定的，一般用a,b,c,表示。 个体变元：抽象的或泛指的，一般用x,y,z,表示。 个体域 个体变元的论述范围。 全总个体域 把各种个体域综合在一起作为论述范围的域。,2.2 命题函数与量词,量词 用来表示个体常量或变元之间数量关系的词。量词分为两种： 全称量词 表示“一切”,“所有”,“凡”,“每一个”,“任意”等意的词称为全称量词，记作。 如：x 表示个体域内所有的x。 存在量词 表示“某个”,“对于一些”,“存在一些”,“至少有一个”等意的词称为存在量词，记作。 如：y 表示个体域内存在一些y。,2.2 命题函数与量词,例：用谓词表
6、达式写出下列命题。 (1)凡是人都呼吸。 (2)有的人是左撇子。 解：令F(x)：x 呼吸。G(x)：x 是左撇子。 当个体域为人类集合时： (1) xF(x) (2)xG(x) 当个体域为全总个体域时： 令M(x)：x 是人。 (1) x(M(x) F(x) (2) x(M(x)G(x),2.2 命题函数与量词,约定：以后如不指定个体域，默认为全总个体域。 特性谓词 在讨论带有量词的命题函数时，必须确定其个体域。当使用全总个体域时，对客体变元的变化范围限制的词，称作特性谓词。 如上例中，M(x)为F(x)和G(x)的特性谓词，它限定了变元x的范围。 一般，对全称量词，特性谓词常作条件的前件；
7、对存在量词，特性谓词常作合取项。,2.2 命题函数与量词,例：将下列命题符号化，并讨论其真值。 (1)所有的人都长头发。 解: 令M(x): x是人。F(x): x 长头发。则 x(M(x) F(x) 真值为0 (2)有的人吸烟。 解: 令M(x): x是人。S(x): x 吸烟。则 x(M(x)S(x) 真值为1,2.2 命题函数与量词,(3)没有人登上过木星。 解: 令M(x): x是人。D(x): x 登上过木星。则 x(M(x)D(x) 真值为1 (4)清华大学的学生未必都是高素质的。 解: 令Q(x): x 是清华大学的学生。H(x): x 是高素质的。则 x(Q(x) H(x) 真
8、值为1 或 x(Q(x)H(x) 可见，有些命题的符号化形式不止一种。,2.2 命题函数与量词,至此，下列推理即可解决： 凡是人都是要死的。 苏格拉底是人。 苏格拉底是要死的。 令M(x): x 是人。D(x): x 是要死的。s: 苏格拉底。则谓词表达式为： (x)(M(x) D(x) M(s) D(s),2.3 谓词公式与翻译,一阶语言 一阶语言F 的字母表定义如下: (1) 个体常项：a,b,c,ai,bi,ci,i1. (2) 个体变项：x,y,z,xi,yi,zi,i1. (3) 函数符号：f,g,h,fi,gi,hi,i1. (4) 谓词符号：F,G,H,Fi,Gi,Hi,i1.
9、(5) 量词符号：，. (6) 联结词符号：，. (7) 括号与逗号：( , ) , , .,2.3 谓词公式与翻译,F 的项： (1)个体常项和个体变项都是项。 (2)若f(x1, x2, , xn)是任意的n元函数，t1, t2, , tn是任意的n个项，则f(t1, t2, , tn)是项。 (3)所有的项都是有限次使用(1),(2)得到的。 原子公式 若A(x1, x2, , xn)是F 的任意n元谓词，t1, t2, , tn是F 的任意n个项，则称A(t1, t2, , tn)为谓词演算的原子公式。,2.3 谓词公式与翻译,谓词演算的合式公式/谓词公式 (1)原子公式是合式公式。
10、(2)若A 是合式公式，则 (A) 也是合式公式。 (3)若A和B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。 (4)若A是合式公式，x是A中出现的任何变元，则xA和xA，也是合式公式。 (5)只有有限次应用规则(1)(4)构成的符号串才是合式公式。,2.3 谓词公式与翻译,约定：最外层的圆括号可以省略。但量词后面若有括号则不能省略。 例：将下列命题符号化 。 (1)没有不能表示为分数的有理数。 解: 令Q(x):x是有理数。W(x):x能表示成分数。 则x(Q(x)W(x) 或 x(Q(x)W(x),2.3 谓词公式与翻译,(2)在北京买菜的人不全是外地人。 解: 令B
11、(x):x在北京买菜的人。F(x):x是外地人。则 x(B(x)F(x) 或 x(B(x)F(x) 例：将下列命题符号化 。 (1)火车都比轮船快。 解: 令T(x):x是火车。S(x):x是轮船。F(x,y):x 比y 跑得快。则 xy(T(x)S(y) F(x,y),2.3 谓词公式与翻译,(2)有的火车比有的汽车快。 解: 令T(x):x是火车。C(x):x是汽车。F(x,y):x 比y 跑得快。则 xy(T(x)C(y)F(x,y) (3)不存在比所有火车都快的汽车。 解: 令T(x):x是火车。C(x):x是汽车。F(x,y):x 比y 跑得快。则 x(C(x)y(T(y)F(x,y
12、) 或 x(C(x) y(T(y)F(y,x),2.4 变元的约束,给定A为一谓词公式，其中有一部分公式形为xP(x)或xP(x)。和后面所跟的x，称为相应量词的指导变元。P(x)称为相应量词的作用域/辖域。在x和x的辖域中，x的所有出现都称为x在公式A中的约束出现，所有约束出现的变元，叫做约束变元。A中不是约束出现的变元均称作自由变元。,2.4 变元的约束,(1)x(F(x) G(x,y) x是指导变元，量词的辖域为(F(x)G(x,y)，其中，x是约束出现两次，y是自由出现一次。 (2)x F(x,y) y G(x,y) x是指导变元，量词的辖域是F(x,y)，其中，x是约束出现一次，y是
13、自由出现一次；同时，y也是指导变元，量词 的辖域是G(x,y)，其中，y是约束出现一次，x是自由出现一次。,2.4 变元的约束,(3)x y (F(x,y)G(y,z)x H(x,y,z) x、y是指导变元，对应量词、的辖域为(F(x,y)G(y,z)，其中x是约束出现一次，y是约束出现两次，z是自由出现一次；后一个x也是指导变元，量词的辖域为H(x,y,z)，其中x是约束出现一次，y、z是自由出现一次。,2.4 变元的约束,例: (1) x(H(x,y) y(W(y)L(x,y,z) (2) x(H(x)W(y) y(F(x)L(x,y,z) 为了避免由于变元的约束与自由同时出现，引起概念上
14、的混乱，故可对约束变元进行换名。使得一个变元在一个公式中只呈一种形式出现，即呈自由出现或呈约束出现。 一个公式的约束变元所使用的名称符号是无关紧要的，即xP(x)与yP(y)具有相同的意义，xP(x)与yP(y)意义也相同。,2.4 变元的约束,约束变元的换名规则： 对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，公式的其余部分不变。 换名时一定要更改为作用域中没有出现的变元名称。 例: 对x(H(x,y) y(W(y)L(x,y,z)换名。 解: 可换名为x(H(x,y) u(W(u)L(x,u,z),2.4 变元的约束,对于公式中的自由变元，
15、也允许更改，这种更改叫做代入/代替。 自由变元的代入规则： 对于谓词公式中的自由变元，可以作代入，代入时需对公式中出现该自由变元的每一处进行。 用以代入的变元与原公式中所有变元的名称不能相同。,2.4 变元的约束,例:对x(H(x)W(y)y(F(x)L(x,y,z)代入。 解:经代入后公式为 x(H(x)W(v) y(F(u)L(u,y,z),2.4 变元的约束,A(x1, x2, , xn)是n元谓词，它有n个相互独立的自由变元。若对其中k个变元进行约束则成n - k元谓词。若谓词公式中没有自由变元出现，则该式就成为一个命题。 当论域的元素有限时，可以消去公式中的量词。设论域元素为a1, a2, , an。则 (x)A(x)A(a1)A(a2)A(an) (x)A(x)A(a1)A(a2)A(an),2.4 变元的约束,量词对变元的约束，往往与量词的次序有关。命题中的多个量词，我们约定从左到右的次序读出。注意: 量词的次序不能颠倒，否则将与原命题不符。,2.5 谓词演算的等价式与蕴含式,赋值/解释 在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。一个谓词公式经过赋值以后，就成为命题。 等价 给定任何两个谓词公
