3-谓词逻辑

null第三章 谓词逻辑第三章 谓词逻辑第三章 谓词逻辑第三章 谓词逻辑§3.1 谓词逻辑的基本概念 §3.2 谓词公式 §3.3 谓词公式的等价关系和蕴含关系 §3.4 范式 §3.5 例 §3.6 谓词逻辑的应用§3.1 谓词逻辑的基本概念§3.1 谓词逻辑的基本概念§3.1.1 谓词和量词§3.1.1 谓词和量词例如，逻辑学中著名的三段论： 凡人必死 张三是人 张三必死 在命 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 逻辑中就无法 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示这种推理过程。§3.1.1 谓词和量词§3.1.1 谓词和量词因为，如果用P代表 “凡人必死”这个命题，Q代表 “张三是人”这个命题，R代表 “张三必死”这个命题，则按照三段论，R应该是P和Q的逻辑结果。但是，在命题逻辑中，R却不是P和Q的逻辑结果，因为公式 PQR 显然不是恒真的，解释{P，Q，R}就能弄假上面的公式。 §3.1.1 谓词和量词§3.1.1 谓词和量词定义3.1.1 可以独立存在的物体称为个体。（它可以是抽象的，也可以是具体的。） 如人、学生、桌子、自然数等都可以做个体。在谓词演算中，个体通常在一个命题里表示思维对象。§3.1.1 谓词和量词§3.1.1 谓词和量词定义3.1.2 设D是非空个体名称集合，定义在Dn上取值于{1，0}上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。 一般地，一元谓词描述个体的性质，二元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题，这样，谓词逻辑包括命题逻辑。§3.1.1 谓词和量词§3.1.1 谓词和量词下面我们举一个谓词的例子： 令G(x，y)： “x高于y”，于是，G(x，y)是一个二元谓词。将x代以个体 “张三”，y代以个体 “李四”，则G(张三，李四)就是命题： “张三高于李四”。随便将x，y代以确定的个体，由G(x，y)都能得到一个命题。但是，G(x，y)不是命题，而是一个命题函数即谓词。§3.1.1 谓词和量词§3.1.1 谓词和量词于是，用谓词的概念可将三段论做如下的符号化： 令 H(x)表示 “x是人”， M(x)表示 “x必死”。 则三段论的三个命题表示如下： P： H(x)M(x) Q： H(张三) R： M(张三)§3.1.1 谓词和量词§3.1.1 谓词和量词例如我们想得到 “命题”P的否定 “命题”，应该就是“命题”P。但是， P=(H(x)M(x)) =(H(x)M(x)) =H(x)M(x) 亦即，“命题”P的否定 “命题”是 “所有人都不死”。这和人们日常对命题 “所有人都必死”的否定的理解，相差得实在太远了。 §3.1.1 谓词和量词§3.1.1 谓词和量词其原因在于，命题P的确切意思应该是： “对任意x，如果x是人，则x必死”。 但是 H(x)M(x) 中并没有确切的表示出 “对任意x”这个意思，亦即H(x)M(x)不是一个命题。 因此，在谓词逻辑中除引进谓词外，还需要引进 “对任意x”这个语句，及其对偶的语句 “存在一个x”。 §3.1.1 谓词和量词§3.1.1 谓词和量词定义3.1.3 语句 “对任意x”称为全称量词，记以x； 语句 “存在一个x”称为存在量词，记以x。 这时，命题P就可确切地符号化如下： x(H(x)M(x)) 命题P的否定命题为： P=(x(H(x)M(x))) =x(H(x)M(x)) 亦即 “有一个人是不死的”。这个命题确实是 “所有人都要死”的否定。 §3.1.1 谓词和量词§3.1.1 谓词和量词三段论的三个命题，在谓词逻辑中是如下这样表示的： P：x(H(x)M(x)) Q：H(张三) R：M(张三) 以后可以证明：在谓词逻辑中，R是P和Q的逻辑结果。 §3.1.1 谓词和量词§3.1.1 谓词和量词设G(x)是一元谓词，任取x0D，则G(x0)是一个命题。于是xG(x)是这样一个命题 “对任意xD，都有G(x)”。故对命题xG(x)的真值做如下规定： xG(x)取1值对任意xD，G(x)都取1值； xG(x)取0值有一个x0D，使G(x0)取0值。§3.1.1 谓词和量词§3.1.1 谓词和量词xG(x)是命题 “存在一个x0D，使得G(x0)成立”。对命题xG(x)的真值规定如下： xG(x)取1值有一个x0D，使G(x0)取1值； xG(x)取0值对所有xD，G(x)都取0值。 §3.1.1 谓词和量词§3.1.1 谓词和量词当D={x0 ，x1，…}是可数集合时， xG(x)等价于G(x1)G(x2)… xG(x)等价于G(x1)G(x2)… §3.1.1 谓词和量词§3.1.1 谓词和量词对于一个谓词，如果其中每一个变量都在一个量词作用之下。则它就不再是命题函数，而是一个命题了。但是，这种命题和命题逻辑中的命题毕竟有所不同。因为终归这种命题里还有变量，当然这种变量和命题函数中的变量还有区别。 使用量词时应注意以下几个问题： 1. 量词的论域，即D中都有那些元素； 2. 在多重量词时，应注意量词的顺序； 3. 量词的作用域。 §3.1.2 改名规则 §3.1.2 改名规则 定义3.1.4 在一个由谓词，量词，逻辑联结词，括号组成的有意义的符号串(实际是指下一节将严格定义的公式)中，变量的出现说是约束的，当且仅当它出现在使用这个变量的量词范围之内；变量的出现说是自由的，当且仅当这个出现不是约束的。 例如，x(P(x，y)Q(x，z))R(x)。从左向右算起，变量x的第一，第二次出现是约束的，第三次出现是自由的；变量y，z的出现是自由的。 §3.1.2 改名规则 §3.1.2 改名规则 定义3.1.5 变量说是约束的，如果至少一个它的出现是约束的；变量说是自由的，如果至少一个它的出现是自由的。 由定义可以看出一个变量可以既是约束变量又是自由变量。 例如，上例中的x既是约束变量，又是自由变量；y，z只是自由变量。 §3.1.2 改名规则 §3.1.2 改名规则 显然，xG(x)与yG(y)的真值一样，xG(x)与yG(y)的真值一样，亦即，谓词逻辑中的命题的真值，与命题中的约束变量的记法无关。这就引出了谓词逻辑中的改名规则。 §3.1.2 改名规则 §3.1.2 改名规则 在由谓词，量词，逻辑联结词，括号组成的有意义的符号串(实际是下节定义的公式)中，我们可将其中出现的约束变量改为另一个约束变量，这种改名必须在量词作用区域内各处以及该量词符号中实行，并且改成的新约束变量要有别于改名区域中的所有其它变量。显然改名规则不改变原符号串的真值。 例:例:对于x(P(x，y)Q(x，z))，可改名为u(P(u，y)Q(u，z))。但下面的改名都是不对的： a. u(P(u，y)Q(x，z)) b. x(P(u，y)Q(u，z)) c. u(P(x，y)Q(x，z)) d. y(P(y，y)Q(y，z)) e. z(P(z，y)Q(z，z)) §3.2 谓词公式 §3.2 谓词公式 §3.2.1 公式 §3.2.1 公式 在形式化中，我们将使用如下四种符号： 1. 常量符号：用小写英文字母a，b，c，…表示，当个体名称集合D给出时，它可以是D中某个元素。 2. 变量符号：用小写英文字母x，y，z，…表示，当个体名称集合D给出时，D中任意元素可代入变量符号。§3.2.1 公式 §3.2.1 公式 3. 函数符号：用小写英文字母f，g，…表示，当个体名称集合D给出时，n元函数符号f(x1，…，xn)可以是Dn到D的任意一个映射。 4. 谓词符号：用大写英文字母P，Q，R，…表示，当个体名称集合D给出时，n元谓词符号P(x1，…，xn)可以是Dn上的任意一个谓词。 定义3.2.1 项定义3.2.1 项谓词逻辑中的项，被递归定义为： 1) 常量符号是项； 2) 变量符号是项； 3) 若f(x1, …, xn)是n元函数符号，t1, …, tn 是项，则f(t1, …, tn)是项； 4) 所有项都是有限次使用1)，2)，3)生成 的符号串。 定义3.2.2 定义3.2.2 若P(x1,…,xn)是n元谓词符号，t1,…,tn是项，则P(t1,…,tn)是原子。 定义3.2.3 公式 定义3.2.3 公式 谓词逻辑中的公式，被递归定义如下： 1) 原子是公式； 2) 若G，H是公式，则(G)，(GH)，(GH)， (GH)，(GH)是公式； 3) 若G是公式，x是G中的自由变量，则xG， xG是公式； 4) 所有公式都是有限次使用1)～3)生成的符号 串。 §3.2.2 解释 §3.2.2 解释 定义3.2.4 谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号，函数符号，谓词符号以下列规则进行的一组指定组成： 1. 对每个常量符号，指定D中一个元素； 2. 对每个n元函数符号，指定一个函数，即指 定Dn到D的一个映射； 3. 对每个n元谓词符号，指定一个谓词，即指 定Dn到{0，1}的一个映射。 §3.2.2 解释 §3.2.2 解释 今后我们对讨论的公式做如下规定：公式中无自由变量，或将自由变量看做常量。 例:例:给出如下两个公式： 1) G=x(P(f(x))Q(x，f(a))) 2) H=x(P(x)Q(x，a)) 给出如下的解释I： D={2，3} a 2 f(2) f(3) 3 2 P(2) P(3) Q(2, 2) Q(2, 3) Q(3, 2) Q(3, 3) 0 1 1 1 0 1例:例:TI(G) = TI((P(f(2))Q(2，f(2))) (P(f(3))Q(3，f(2)))) = TI((P(3)Q(2，3))(P(2)Q(3，3))) =(11)(00) =1 TI(H) = TI(P(2)Q(2，2)P(3)Q(3，2)) =0110 =0null定义3.2.5 公式G称为可满足的，如果存在解释I，使G在I下取1值，简称I满足G。若I不满足G，则简称I弄假G。 定义3.2.6 公式G称为是恒假的(或不可满足的)，如果不存在解释I满足G；公式G称为恒真的，如果G的所有解释I都满足G。 §3.3 谓词公式的等价关系和蕴含关系 §3.3 谓词公式的等价关系和蕴含关系 §3.3.1 公式的等价和蕴涵 §3.3.1 公式的等价和蕴涵 定义3.3.1 公式G，H称为等价，记以G=H，如果公式GH是恒真的。 由定义显然可以看出：公式G，H等价的充要条件是：对G，H的任意解释I，G，H在I下的真值相同。 因为对任意公式G，H，在解释I下，G，H就是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。 §3.3.1 公式的等价和蕴涵 §3.3.1 公式的等价和蕴涵 定义3.3.2 设G，H是公式，称G蕴涵H，或H是G的逻辑结果，如果公式GH是恒真的，并记以GH。 显然，对任意两个公式G，H，G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H。 同样，命题逻辑中的基本蕴涵式仍成立。 §3.3.1 公式的等价和蕴涵 §3.3.1 公式的等价和蕴涵 令G1 =x(H(x)M(x))，G2=H(a)，H=M(a) 证明：H是G1 G2的逻辑结果。 因为，设I是G1 ，G2，H的一个解释(I指定a为张三)，且I满足G1G2，即I满足 x(H(x)M(x))H(a) 所以，I满足M(a)。 否则，令M(a)在I下为假，而H(a)在I下为真，于是H(a)M(a)在I下为假，故x(H(x)M(x))在I下为假，矛盾! 故M(a)在I下为真命题，而I指定a为 “张三”，故M(张三)为真命题。§3.3.1 公式的等价和蕴涵 §3.3.1 公式的等价和蕴涵 由于谓词逻辑中的恒真(恒假)公式，要求所有解释I都满足(弄假)该公式。而解释I依赖于一个非空集合D。由于集合D可以是无穷集合，而集合D的 “数目”也可能是无穷多个，因此，所谓公式的 “所有”解释，实际上是无法考虑的。这就使得谓词逻辑中公式的恒真，恒假性的判断变得异常困难。1936年Church和Turing分别独立地证明了：对于谓词逻辑，判定问题是不可解的。 null设G(x)是一元谓词符号，若公式xG(x)是恒真公式，则这件事实可被叙述为如下的一个真命题：对任意一元谓词G(x)，命题xG(x)都是真的。 但是，如果想把这个命题加以否定，则在谓词逻辑中是办不到的。因为： 1) 这个命题的否定，应该是如下命题：有一个一元谓词G(x)，使得命题xG(x)是假的。 2) 公式xG(x)的否定是公式(xG(x))。而后一个公式表示的命题是：公式xG(x)是恒假的，亦即，对任意一元谓词G(x)，命题xG(x)都是假的。 null1)和2)所表示出的事实相差得太远了。发生这件事的原因是：用 “公式xG(x)是恒真的”来表达命题 “对任意一元谓词G(x)，命题xG(x)都是真的”是不确切的。确切地，后一个命题，应该用 “公式G(xG(x))是恒真的”来表达。 这个公式中，不仅有关于个体变量x的量词，而且有关于谓词变量(即谓词符号，亦即原子)的量词。由这样的公式组成的系统就称为高阶逻辑。高阶逻辑中，不仅判定问题不可解，甚至连一个完备的公理系统都没有。 §3.3.2 谓词演算的推理理论 §3.3.2 谓词演算的推理理论 前提引入规则：在证明的任何 步骤 新产品开发流程的步骤课题研究的五个步骤成本核算步骤微型课题研究步骤数控铣床操作步骤 上都可以引用前提。 结论引入规则：在证明的任何步骤上所得到的结论都可以在其后的证明中引用。 置换规则：在证明的任何步骤上，公式的子公式都可以用与之等价的其他公式置换。 代入规则：在证明的任何步骤上，恒真公式中的任一原子都可以用一公式代入，得到的仍是恒真的公式。 null全称特定化规则(US)：xA(x) A(y) 这里的A(y)是将A(x)中的x处代以y。要求y在A(x)中不约束出现。这里自由变量y也可以写成个体常量c，这时c为个体域中任意一个确定的个体。 这个规则的意思是说，如果个体域的所有元素都具有性质A，则个体域中的任一个元素具有性质A。 null存在特定化规则(ES)：xA(x)  A(c) 这里c是个体域中的某个确定的个体。这个规则是说，如果个体域中存在有性质A的元素，则个体域中必有某一元素c具有性质A。 但是，如果xA(x)中有其它自由变量出现，且x是随其它自由变量的值而变，那么就不存在唯一的c使得A(c)对自由变量的任意值都是成立的。这时，就不能应用存在特定化规则。 null例如，x(x=y)中，x、y的论域是实数集合。若使用ES规则，则得c=y，即在实数集中有一实数c，等于任意实数y。结论显然不成立，这是因为A(x)：x=y中的x依赖于自由变量y，此时不能使用ES规则。另外，要注意的是，如果xP(x)和xQ(x)都真，则对于某个c和某个d，可以断定 P(c) Q(d)必真，但不能断定P(c) Q(c)为真。 null 全称一般化规则(UG)：A(x)yA(y) 这个规则是说，如果个体域中任意一个个体都具有性质A，则个体域中的全体个体都具有性质A。这里要求x必须为自由变量，并且y不出现在A(x)中。 存在一般化规则(EG)：A(c)yA(y) 这个规则是说，如果个体域中某一元素c具有性质A，则个体域中存在着具有性质A的元素。这里要求y不在A(c)中出现。 例3.3.1 证明: x(P(x)Q(x))P(c)Q(c)例3.3.1 证明: x(P(x)Q(x))P(c)Q(c)证明： （1）x(P(x)Q(x)) 前提 （2）P(c)Q(c) (1)；US （3）P(c) 前提 （4）Q(c) (2),(3) 例3.3.2 证明： x(P(x)Q(x)), xP(x)xQ(x) 例3.3.2 证明： x(P(x)Q(x)), xP(x)xQ(x) 证明：用反证法，假设xQ(x)成立。 xP(x) 前提 P(y) (1)；US xQ(x) 假设 xQ(x) (3) Q(y) (4)；US P(y)Q(y) (2)，(5) null (P(y) Q(y)) (6) x(P(x)Q(x)) 前提 P(y) Q(y) (8),US (P(y) Q(y)) (P(y) Q(y)) (7), (9) 因为(P(y) Q(y)) (P(y) Q(y))是恒假公式，所以x(P(x)Q(x))，xP(x)xQ(x)。 例3.3.3 指出下面推理中的错误。 例3.3.3 指出下面推理中的错误。 （1）x(F(x)G(x)) 前提 （2）F(c)G(c) (1),ES （3）F(c) （2） （4）y(H(y)I(y)) 前提 （5）H(c)I(c) （4） （6）H(c) （5） （7）F(c)H(c) (3),(6） （8）x(F(x)H(x)) (7), EG。 §3.4 范式 §3.4 范式 §3.4.1 前束范式 §3.4.1 前束范式 定义3.4.1 谓词逻辑中公式G称为前束范式，如果G有如下形状： Q1x1…QnxnM 其中 Qixi或者是xi，或者是xi，i=1，…，n，M是不含量词的公式，Q1x1…Qnxn称为首标，M称为母式。 例如， xyz(P(x，y)Q(x，z)) xyzP(x，y，z)引理1 引理1 设G是公式，其中自由变量有且仅有一个x，记以G(x)，H是不含变量x的公式，于是有： 1) x(G(x)H)=xG(x)H 1’) x(G(x)H)=xG(x)H 2) x(G(x)H)=xG(x)H 2’) x(G(x)H)=xG(x)H 3) (xG(x))=x(G(x)) 4) (xG(x))=x(G(x)) 证明： 证明： 1) 设I是G(x)和H的一个解释。若x(G(x)H)在I下取1值，则在I下，对任意xD，G(x)H都是真命题。若H是真命题，则xG(x)H是真命题；若H是假命题，则必然是对每个xD，G(x)都是真命题，故xG(x)取1值。所以xG(x)H在I下取1值。 若x(G(x)H)在I下取0值，则必有一个x0D，使G(x0) H在I下取0值。故G(x0)为假命题，并且H为假命题。所以xG(x)取0值。从而xG(x)H在I下取0值。 （1）‘的证明（1）‘的证明设I是G(x)和H的一个解释。若 x(G(x)H)在I下取1值，则在I下，存在x0 D，G(x0)H是真命题。若H是真命题，则 xG(x)H是真命题；若H是假命题，则必然有G(x0) 是真命题，故 xG(x)取1值。所以 xG(x)H在I下取1值。 若 x(G(x)H)在I下取0值，则在I下对任意的xD，使G(x) H在I下取0值。故G(x)和H都为假命题，所以 xG(x)H在I下取0值。（3）的证明（3）的证明若I满足( xG( x))，则I弄假 xG(x)。则必有某一个x0 D，G(x0) 是假命题，于是G(x0) 是真命题，即 x ( G(x))在I下是真命题，故I满足x ( G(x)) 若I弄假( xG(x))，则I满足 xG(x)。即对任意的xD，有G(x)是真命题。也就是对任意的xD，G(x)是假命题，于是x(G(x))是假命题，故I弄假x(G(x))。 证明： 证明： 若I满足(xG( x))，则I弄假xG(x)。故对任意xD，G(x)都是假命题，从而G(x)都是真命题，故I满足x(G(x)) 若I弄假(xG(x))，则I满足xG(x)。故有x0D，使得G(x0)是真命题。从而G(x0)是假命题，故I弄假x(G(x))。引理2 引理2 设G，H是两个公式，其中自由变量有且只有一个x，分别记以G(x)，H(x)，于是有： 1) xG(x)xH(x)=x(G(x)H(x)) 2) xG(x)xH(x)=x(G(x)H(x)) 3) xG(x)xH(x)=xy(G(x)H(y)) 4) xG(x)xH(x)=xy(G(x) H(y)) 1) 证明： 1) 证明： 设I是G(x)和H(x)的一个解释。若xG(x)xH(x)在I下取1值，则在解释I下，对任意xD，G(x)、H(x)都是真命题，所以G(x)H(x)是真命题，即对任意xD， G(x)H(x)是真命题，所以x(G(x)H(x))在I下取1值。 若xG(x)xH(x)在I下取0值，则xG(x)为假，或xH(x)为假，若xG(x)为假，必有一个x0D，使G(x0) 在I下取0值，所以G(x0) H(x0)为假命题，所以x(G(x)H(x))在I下取0值。若xH(x)为假，同理可证。3) 证明： 3) 证明： xG(x)xH(x) =xG(x)yH(y) 改名规则=x(G(x)yH(y)) 引理1 =xy(G(x)H(y)) 引理1定理3.4.1 定理3.4.1 对任意公式G，都存在与其等价的前束范式。 证明：通过如下算法，可将公式G化成等价的前束范式。 1. 使用基本等价 (KH)=(KH)(HK) (KH)=KH 可将公式G中的和删除。null2. 使用(H)=H，摩根律，引理1，可将公式中所有否定号放在原子之前。 3. 如果必要的话，则将约束变量改名。 4. 使用引理1，2将所有量词都提到公式的最左边。 于是，将公式G在等价意义下化成了一个前束范式。 例3.4.1 例3.4.1 xy(z(P(x,z)P(y,z))uQ(x,y,u)) =xy((z(P(x,z)P(y,z)))uQ(x,y,u)) =xy(z(P(x,z)P(y,z))uQ(x,y,u)) =xyz(P(x,z)P(y,z)uQ(x,y,u)) =xyzu(P(x,z)P(y,z)Q(x,y,u)) §3.4.2 Skolem范式 §3.4.2 Skolem范式 定义3.4.2 设G是一个公式，Q1x1…QnxnM是与G等价的前束范式，其中M为合取范式形式。若Qr是存在量词，并且它左边没有全称量词，则取异于出现在M中所有常量符号的常量符号c，并用c代替M中所有的xr，然后在首标中删除Qrxr。§3.4.2 Skolem范式 §3.4.2 Skolem范式 若Qs1, …, Qsm是所有出现在Qrxr左边的全称量词(m1，1s1