离散数学03-谓词逻辑.ppt

2020/6/10，1，北京交通大学软件学院，电子教案，离散结构，第5讲谓词逻辑，在Ls中，命题分解为原子命题，认为原子命题不能再分解。只研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。这样，很难用命题逻辑准确地表达某些推理。例如，著名的亚里士多德三段论苏格拉底推理道：所有的人都死了，苏格拉底是人，所以苏格拉底死了。根据常识，这个推理被认为是正确的。但是，如果用最小二乘法来表示，分别用P、Q和R来表示三个原子命题，那么有P和QR。然而，(PQ)R不是一个永久的真理，所以上面的推理形式是错误的。一个推理，得出矛盾的结论，问题在哪里？问题是，在这种推理中，命题之间的逻辑关系并不反映在原子命题中，而是反映在构成原子命题的内部成分中，即在命题结构的更深层次中。Ls对此无能为力。因此，在研究某些推理时，有必要进一步分析原子命题，分析单个词、谓词和量词，研究它们的形式结构、正确的推理形式和规则的逻辑关系，这是谓词逻辑(缩写为Lp)的基本内容。5.1个体、谓词和量词5.2谓词公式和翻译5.3约束论元和自由论元5.4公式解释和类型5.5等价和蕴涵5.6谓词公式范例5.7谓词逻辑推理理论5.1个体、谓词和量词。在Lp中，命题是一个有真、假意义的陈述句。从语法上讲，陈述句由主语和谓语组成。在Lp中，为了揭示命题的内部结构和不同命题之间的内部结构关系，命题按照这两个部分进行分析，主语称为个体或宾语，谓语称为谓语。个体、谓词和命题的谓词形式的定义5.1.1在原子命题中，所描述的对象称为个体；用来描述个体的本质或个体之间的关系的部分称为谓词。个人指的是可以独立存在的事物。它们可以是具体的或抽象的，如张明、计算机、精神等。表示一个特定的个体，称为个体常数，用底层对象表示为a、b、c或ai、bi、ci等。表示不确定的个体，称为个体参数，用x，y，z表示.还是xi、易、子.谓词，当与个体相关联时，它描述了个体的属性；当与两个或多个个体联系在一起时，它描述了个体之间的关系。表示特定谓词，称为谓词常数，表示不确定谓词，称为谓词参数，都用大写英文字母表示，如p，q，r，或它们的上下下标。在这本书里，谓词论证没有被更多地讨论。对于一个给定的命题，当用小写字母表示它的个体，用大写字母表示它的谓词时，需要在大写字母的右边的括号()中写小写字母。例如，在“张明是大学生”的命题中，“张明”是个体，“是大学生”是谓语，这就刻画了“张明”的本质。让我们：做一名大学生，c:张明，那么“张明是一名大学生”可以表示为S(c)，或者写成S(c):张明是一名大学生。例如，在“武汉位于北京和广州之间”的命题中，武汉、北京和广州是三个独立的个体，而“位于和之间”是一个谓语，它描述了武汉、北京和广州之间的关系。假设位于和之间。a:武汉，b:北京，c:广州，P(a，b，c):武汉位于北京和广州之间。定义5.1.2原子命题表示为P (a1，a2，an)用谓词(如P)和n个有序的单个常数(如A1，a2、安)，称为原子命题的谓词形式或命题的谓词形式。应该注意的是，个体在命题的谓词形式中出现的顺序会影响命题的真正价值，并且不会随意改变，否则真正的价值将会改变。和上面的例子一样，P(b，a，c)是假的。原子谓词公式的原子命题的谓词形式可以进一步抽象，例如，谓词右边括号中的n个独立常量元素被x1、x2、xn等独立变量所代替，从而得到命题结构的一种新的表达形式，称为n元原子谓词。定义5.1.3 P(x1，x2，xn)由谓词(例如p)和n个单独的变量(例如x1，x2，xn)被称为n元素原子谓词或n元素命题函数，或者简称为n元素谓词。个体论域的范围被称为个体域或话语域。当n=1时，它被称为一元谓词；当n=2时，它被称为二元谓词，特别是，当n=0时，它被称为零谓词。零元素谓词是命题，所以命题和谓词是统一的。n谓词不是命题，只有当个别的论证被特定的个别的或个别的常数所取代时，它才能成为命题。然而，个体论证采取哪种论域的特定价值对命题的真正价值有很大的影响。例如，让我们(x): x是一个大学生。如果x的宇宙是一所大学计算机系的所有学生，那么S(x)是真的；如果x的宇宙是一所中学的所有学生，那么S(x)是假的；如果x的宇宙是剧院中的观众，并且观众包括大学生和其他非大学生的观众，那么S(x)的真实值是不确定的。总的来说，n-谓词中每个个体的论域被整合在一起作为它的论域，这被称为n-谓词的总论域。整个一般领域的定义为进一步研究命题提供了便利。当一个命题没有规定话语的领域时，它通常被认为是整个话语领域中的话语领域。此时，谓词如P(x)通常用于限制单个参数x的取值范围，P(x)称为特征谓词。3.量词使用N元谓词和它们的定义域概念，有时它们仍然不能用符号来准确表达某些命题。例如，S(x)表示X是大学生，而X的个人域是某个单位的员工，因此S(x)可以表示某个单位的员工是大学生，或者某个单位的一些员工是大学生。为了避免理解上的歧义，在Lp中，有必要引入量词，用来描述“全部”、“有一些”和其他表示不同量的词。定义如下：定义5.1.4符号被称为通用量词，用于表示“为所有”、“为每个”、“为任何一个”、“为所有”等词；X被称为通用量词，X被称为引导论证。(2)符号被称为存在量词，用于表达“是一些”、“至少有一个”、“关于一些”和“一个”等词；x被称为存在量词，x被称为指令参数。(3)符号！它被称为存在唯一量词，用来表达“恰好一个”和“存在唯一”等词。X称为存在唯一量词，X称为引导论元。通用量词、存在量词以及存在和唯一量词统称为量词。量词符号是由逻辑学家弗雷引入的。有了量词，用逻辑符号表达命题的能力大大增强了。(1)所有大学生都热爱自己的祖国。(2)每个自然数都是实数；(3)部分大学生有远大理想；有些自然数是质数。答案是s (x): x是大学生，l (x): x热爱祖国，n (x): x是自然数，r (x): x是实数，i (x): x有一个伟大的理想，p (x): x是素数。例子中的命题分别表示为：(x)(S(x)l(x)(x)(N(x)r(x)(x)(S(x)I(x)(x)(N(x)p(x)，在例子的解中，由于在命题中没有指定单独的域，这意味着在整个一般域中讨论命题，因此使用所有的特征谓词，例如S(x)和N(x)。此外，可以看出量词和特征谓词的搭配有一定的规律，即完整的量词后面是一个条件表达式，而特征谓词作为其前身出现；存在量词后面跟有一个连词，特征谓词以连词的形式出现。如果在解决方案中指定了单个域，则字符这是因为在谓词被量化之后，命题的真值可以在整个单独的域中被考虑。这就像数学中的函数f(x)，它的值是不确定的，但它的值是可以确定的。谓词公式与翻译1。谓词公式将引入术语的概念，以便处理数学和计算机科学中的逻辑问题和直观清晰的谓词表示。定义项5.2.1由以下规则组成：个体常数和个体变量是项；(2)如果f是n元函数，t1，t2，tn是项，然后是f(t1，t2，tn)是一个术语；所有项目由和生成。有了术语的定义，函数的概念可以用来表示单个常数和单个变量。例如，让f(x，y)表示x y，谓词N(x)表示x是一个自然数，那么f(2，3)表示单个自然数5，而N(f(2，3)表示5是一个自然数。这里的功能是广义的。例如，P(x):x是教授，f(x):x的父亲，C :张强，那么P(f(c)的意思是“张强的父亲是教授”。函数的使用给谓词表示带来了极大的方便。例如，谓词被用来表达一个命题：对于任何整数x，x2-1=(x 1)(x-1)是一个恒等式。设I(x):x是一个整数，f(x)=x2-1，g(x)=(x 1)(x-1)，E(x，y):x=y，则命题可表示为：(x) (i (x) e (f (x)，g(x)。定义5.2.2如果P(x1，x2，xn)是n元谓词，t1，t2，tn是一个项目，那么P(t1，t2，tn)在Ls中称为原子谓词公式，简称为原子公式。其次，从原子公式出发，给出了Lp中复合谓词公式的归纳定义。定义5.2.3复合谓词公式当且仅当符号串由下列规则形成的原子公式是复合谓词公式；(2)如果A是复合谓词公式，(A)是复合谓词公式；(3)如果A和B是组合谓词公式，(AB)，(AB)，(AB)和(AB)都是组合谓词公式；(4)如果a是复合谓词公式，x是单个自变量，(x) a和(x) a都是复合谓词公式；(5)只有有限数量的使用(1)、(2)、(3)和(4)的术语形成复合谓词公式。谓词逻辑的翻译是指通过用谓词公式表达用词描述的命题来翻译或象征谓词逻辑。反之亦然，达拉斯到礼堂一般来说，象征的步骤如下：正确理解一个给定的命题。必要时，命题被重新分类，以便每个原子命题和原子命题之间的关系能够被清楚地表达。(2)将每个原子命题分解成个体、谓词和量词；在讨论整个一般领域时，我们应该给出特征谓词。(3)找出合适的量词。应该注意后面跟条件表达式的全量词(x)，后面跟连词表达式的量词(x)。(4)用适当的连接词来表达给定的命题。例5.2.2象征着“没有最大的自然数”的命题。在这个命题的解中，“没有最大值”显然适用于所有的自然数，因此可以理解为“对于所有的x，如果x是一个自然数，那么一定有一个大于x的自然数”，具体地说，“对于所有的x，如果x是一个自然数，那么一定有y，y也是一个自然数，并且y大于x”。如果N(x):x是一个自然数，而G(x，y):x大于y，则原命题表示为：(x) (n (x) (y) (n (y) g (y，x)。例如，5.2.3象征着“今天会有雨和雪，一些人会掉下来”这句话如果今天下雨下雪，会有x，x是人，x会掉下来。如果今天R:下雨，今天S:下雪，M(x):x是人，F(x):x下降，那么这个陈述可以表示为RS (x) (m (x) f (x)。因为人们对命题的字面意义有不同的理解和不同的强调，它会影响命题的象征形式。5.3约束变元和自由变元，定义5.3.1给定一个谓词公式A，其中一些被成形为(x) B(x)或(x) b (x)，它被称为A的x约束部分，而B(x)被称为相应量词的范围或管辖范围。在辖区内，x的所有出现都称为约束出现，x称为约束参数。在B中不受约束的其他单个变量的出现称为自由出现，这些单个变量称为自由变量。对于给定的预因此，确定量词的范围就是要找到量词后的相邻子公式，具体来说：(1)如果量词后有括号，括号中的子公式就是量词的范围；(2)如果量词后没有括号，与量词相邻的子公式就是量词的范围。要确定给定公式A中的单个参数是约束参数还是自由参数，关键是它在A中是显示为约束参数还是自由参数。将来，常用的元语言符号A(x)表示x是任意公式，其中单个变量之一可以自由显示，例如，A(x)可以是p (x) q (x)，p (x) (y) q (x，y)等。一旦量词(x)或(x)加在A(x)之前，就得到公式(x) a (x)或(x) a (x)。此时，X是约束。类似地，由A(x，y)表示的x和y是自由形式的公式。定义5.3.2把A设定为任何公式，如果在A中没有自由个体变量，那么A就叫做封闭公式，简称封闭公式。根据封闭形式的定义，封闭形式的所有单个变量都是受约束的。例如，(x) (p (x) q (x)和(x) (y) (p (x) q (x，y)是封闭的，而(x) (p (x) q (x，y)和(y) (z) l (x，y，z)不是封闭的。从下面的讨论中可以看出，在一个公式中，一些单独的变量可以是受约束的，也可以是自由的，这很容易混淆。为了避免混淆，采用了以下两条规则：约束变元名称规则，将量词范围内约束的单个变元及其对应的引导变元改为范围内未出现的单个变元，其余保持不变。(2)自由变量元进入规则，对于一个自由的个体变量可以用个体常数元或用不同于原子公式中的所有个体变量来代替，并到处代替。重命名规则和替换规则的共同点是约束关系不能改变，但区别在于：要实现的对象不同。重命名应用于约束变量，替换应用于自由变量。(2)实施范围不同。重命名只能应用于公式及其范围中的一个量词，即只能应用于公式的一个子公式；替换必须同时应用于整个公式中同一自由变量的所有自由出现，即必须应用整个公式。实施后的结果不同。名称更改后，公式的含义不会改变，因为约束变量只更改为另一个单独的变量，约束关系也不会改变。约束参数不能重命名为单个常量；替代，不仅可以用另一个单独的变量替代，也可以用单独的常数替代，从而将公式从普遍意义改变为只对单独的常数有意义，即公式的意义已经改变。上面表示约束变量名的改变规则和自由变量元的进入规则。有时在公式A(x)中，术语t也用来代替单个参数x，那么我们如何做到这一点而不改变量词和管辖区之间的关系呢？换句话说，在替换后的结果和替换前的结果之间，直观的解释是没有区别的，这就要求在A(x)中引入项T对X是自由的概念。定义5.3.3让A成为任意公式，X自由出现。如果x不出现在a的项t中包含的任何单个变量y的量词(y)或(y)的范围内，则项t对a中的x是自由的。例如，如果a是(x) b (x，y) (z) c (x，z)，则项f(x，w)对y不是自由的，项g(y，z)对y是自由的，项h(x，z)不是自由的，项y对x是自由的。根据定义， 对于任何公式a和任何单个参数x，x对于a中的x都是自由的，不管x是否在a中自由出现。一般来说，Lp中的公式包括：单个常数、单个