《2022年永真式[兼容模式]可用 .pdf》由会员分享，可在线阅读，更多相关《2022年永真式[兼容模式]可用 .pdf（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1谓词公式的换名?x (Q(x ,y) ? y(P(x, y) R(y) 此公式中 y既有约束出现又有自由出现。为了避免变元的约束和自由的同时出现，引起概念上的混乱，可以对约束进行改名使得同一个变元要么自由出现变元进行改名，使得同个变元要么自由出现，要么约束出现，之所以可以这么做，是因为一个公式的约束变元所用的符号跟公式的真假是无关的。比如公式 ?yP(y) 和? x(P(x) 具有同样的意义。换名规则1.约束变元可以换名，但是自由变元不能够换名，换名时应对量词辖域内所出现的该约束变元都进行换名。2.换名后用的符号一定是该辖域内没有的变元名称。换名后用的符号定是该辖域内没有的变元名称例如： ?
2、 x (Q(x ,y) ? y(P(x, y) R(y) ? x D(x)可以换名为：? x (Q(x ,y) ? z(P(x, z) R(z) ?u D(u)但是不能够换为：?x (Q(x ,y) ? x(P(x,x) R(x)? u D(u)，因为此时改变了变元的约束关系第二章谓词逻辑2.1 谓词和量词2.2 项和公式2.3 解释和赋值2.4 永真式2.5 等值演算2.6 逻辑推论作业2.4 永真式定义 2.16 设 A 是公式。1.如果 A 在每个解释中为真，则称A 为永真式，也称 A 为逻辑有效的公式。2.如果 A 在每个解释中为假，则称A 为永假式，也称 A 为矛盾式，不可满足式。3
3、.如果有解释 I 和 I 中赋值 v 使得 I(A)(v) = 1 ，则称 A 为可满足式，并称解释I 和赋值 v 满足 A。显然,A是永真式当且仅当?A是永假式，A是永假式当且仅当?A是永真式，永真式一定是可满足式，可满足式未必是永真式。A是永假式当且仅当A不是可满足式? xP(x，y) ? xP(x，y) 是永真式，因为不管怎样指定解释和赋值，这个蕴含式得前件和后件总有相同得真值由连接词和后件总有相同得真值，由连接词得真值表知道该公式总为真。该公式得永真性是由连接词得性质决定得，与谓词和量词得意义无关，这类永真式称为重言式。定义 2.17 用谓词逻辑公式B1, Bn 分别同时替换命题逻辑公
4、式A 中不同命题变元p1, pn 得到的谓词逻辑公式记为，并称其为 A 的替换实例。命题逻辑永真式的替换实例称为重言式 。重言式的永真性是由联结词的意义决定的，而与对量词符号、谓词符号、函数符号、常元等的解释无言nnppBBA,11LL关。 ?xP(x) ? xP(x) 是重言式，无论如何解释全称量词符号 ? 和谓词符号 P 的意义，蕴涵式? xP(x) ? xP(x) 的前后件的真值总是一样的，而蕴涵联结词的真值表决定了它总是真。? xP(x) P(a) 不是重言式，如果将全称量词符号? 的意义解释为存在量词，它就可能假。名师资料总结 - - -精品资料欢迎下载 - - - - - - -
5、- - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 5 页 - - - - - - - - - 2如 何 辨 别 一 个 公 式 是 不 是 重 言 式 呢 ？把原子公式和形式为?xA 的公式统称为初等公式。如果把初等公式看做命题变元，不同的初等公式看做不同的命题变元，该公式成为命题逻辑的永真式，则该公式就是谓词逻辑的重言式。例如，公式(? xA ? x(A B) (?xB ?x(A B) (?xA ? xB ? x(A B)是重言式，因为在这个公式中有三个初等公式?xA, ? xB, ? x(A B)，如果把它们分别看做命题变元 p, q,
6、r，则该公式成为命题逻辑永真式(p r) (q r) (p q r)? xP(x) ?xP(x) 是永真式，但不是重言式。? xP(x) ?xP(x) 是 ? xP(x) ? x? P(x) 的缩写。将初等公式 ? xP(x) 和 ? x?P(x) 分别看作命题变元p 和 q，则 ?xP(x) ? x?P(x) 成为 p ? q，这不是命题逻辑永真式。不是命题逻辑永真式? xP(x) ? yP(y) 是永真式，但不是重言式。将初等公式 ? xP(x) 和 ? yP(y) 分别看作命题变元p 和 q，则 ? xP(x) ? yP(y) 成为 p q，这不是命题逻辑永真式。定理2.4 重言式一定是
7、永真式。证明将命题逻辑公式A 的替换实例记为A*。任取解释 I 和 I 中赋值 v ，指定真值赋值vI, v 如下：nnppBBA,11LL?ppvBI是若)(11归纳证明：对于每个命题逻辑公式A ，vI, v(A) = I(A*)(v)?=nnvppvBIpvI是若)(,MM1. 若 A 是 pi ，其中 1 i n，则 A* 是 Bi，2. 若 A 是 ?B，则 A* 是 ? B* ，vI, v(A) = ? vI, v(B) = ? I(B*)(v) = I(A*)(v)3. 若 A B CA* B* C* )()()(*,vAIvBIpAvivivIvI=是，则是，vI, v(A) =
8、 vI, v(B) vI, v(C) = I(B*)(v) I(C*)(v) = I(A*)(v)若 A 是命题逻辑永真式，则对于任意解释I 和 I 中任意赋值 v ， I(A*)(v) = vI, v(A) = 1，所以 A* 是永真式。重言式都是永真式，永真式未必是重言式。永真式都是可满足式，可满足式未必是永真式。一个公式是永假式当且仅当它不是可满足式。从语义上划分，谓词逻辑公式可分为以下四类：1.重言式，如 P(x) P(x)。2.不是重言式的永真式，如? xP x ?xP x 。( )( )3.非永真的可满足式，如?xP(x) ?xP(x)。4.永假式，如 P(x) ?P(x)，? x
9、P(x) ? P(x)。以下公式是重言式：A (B A), (? A ? B) (B A),(A (B C) (A B) (A C)永假公式的类型可满足式式永真式重言式非重言的永真式非永真的可满足式名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 5 页 - - - - - - - - - 3例2.17 判断 ?xA 类型，其中项 t 对于公式 A中的 x 是可代入的。永真式，设解释I 和 I 中赋值 v 使得 I( )(v) = 0，因为 I(A)(vx/I(t)(v)
10、= I( )(v) = 0，又I(t)(v)DI，)xtAxtAxtA所以有论域中元素使得I(A)(vx/I(t)(v) 0所以 I(? xA)(v) = 0。但是不能保证 ? xA 总是重言式，例如，?xP(x) P(a) 就不是重言式。它只能是p 和p q 这样的非永真的命题逻辑公式的替换实例。xtA当项 t 对于公式 A 中的变元 x 不可代入时，公式可能不是永真的，举反例如下：取 A 为 ?yP(x, y)， t 为 y，则为 ?yP(y, y)。因为?yP(x, y) 中变元的约束出现数为2，而 ?yP(y, y) 中变元的约束出现数为3，所以项 t 对于公式 A 中xIxtAxtA
11、xA?的变元 x 不可代入。给解释I 如下：DI = 1, 2 ，PI(x, y) = 1 当且仅当 x y 。则 I (? x?yP(x, y) = 1 ，而 I(?yP(y, y) = 0 ，所以? x?yP(x, y) ?yP(y, y)不是永真式。例2.19 设 n 是正整数， x1, xn 是不同变元，项t1, tn 对于公式 A 中的 x1, xn 是可代入的，则是永真式。证明 任取解释 I 和 I 中赋值 v。如果)1则对于任意nnxxttnAAxx,111LLL?I(? x1? xnA)(v) = 1，则对于任意 d1, dn DI，I(A)(vx1/ d1, xn/dn )
12、= 1所以，因此，是永真式。1)(/,),)(/)()(11,11=vtIxvtIxvAIvAInnxxttnnLLLnnxxttnAAxx,111LLL?例2.18 判断语句 ?x?yP(x, y) ? y?xP(x, y) 类型解：永真式，不是重言式。若解释 I 满足 ?x? yP(x, y)，则有 dDI 使得对于每个 cDI ，PI(d, c) = 1。因此，对于每个c DI ，都有同一个 d DI 使得 PI(d, c) = 1。这表明 I 满足? y?xP(x, y)。因此， ?x? yP(x, y) ? y?xP(x, y) 是永真式。?x?yP(x, y) ? y?xP(x,
13、y) 是? x? yP(x, y) ?y? x? P(x, y)的缩写， ? p q 不是命题逻辑永真式。例2.18 判断语句?y?xP(x, y) ?x?yP(x, y)类型解：是非永真的可满足式。若解释 I 使得 I(? y?xP(x, y) ?x? yP(x, y) = 0，则 I满足 ? y?xP(x, y)，但是不满足?x? yP(x, y)。对于每个 dDI ，存在 cd DI 使得 PI(cd , d ) = 1。cd 中的下ddd标 d 表示 cd 依赖于 d ，对不同的d ，cd 可能不同。因此，可能没有同一个c DI 使得对于每个dDI ，PI(c, d ) = 1。 I
14、不满足 ?x? yP(x, y) 是可能的。显然， ? y?xP(x, y) ?x? yP(x, y) 不是永假式。我们只需找出两个解释，其中一个使它假，另一个使它真。给定使其为真的解释I 如下：论域 DI = d, e，PI(d, d) = 0，PI(d, e) = 0，PI(e, d) = 0， PI(e, e) = 0I(? y?xP(x, y) = 0， I(?x? yP(x, y) = 0，所以 I(?y?xP(x, y) ?x? yP(x, y) = 1。给定使其为假的解释I 如下：论域 DI = d, e，PI (d, d) = 1, PI(d, e) = 0, PI(e, d)
15、 = 0, PI(e, e) = 1I (?y?xP(x, y) = 1， I (?x?yP(x, y) = 0，所以 I (? y?xP(x, y) ?x? yP(x, y) = 0。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 5 页 - - - - - - - - - 4例2.18 判断语句 ?x(P(x) Q(x) (?xP(x) ?xQ(x) 的类型是什么？若解释 I 不满足该语句，则I(?x(P(x) Q(x) = 1 且 I(?xP(x) ?xQ(x) =
16、 0，因而 I(?xP(x) = 1，I(?xQ(x) = 0。存在 a DI 使得 PI(a) = 1，并且对于每个 d DI ，QI(d) = 0。若还有b DI 使得则因此可得PI(b) = 0，则 I(?x(P(x) Q(x) = 1。因此，可得到使得该语句为假的解释I 如下：DI = a, b ，PI(a) = 1，PI(b) = 0，QI(a) = QI(b) = 0该语句的一个模型I 如下：DI= a，PI (a) = QI (a) = 1该语句是非永真的可满足式。语句 ? x(P(x) P(a) 的类型是什么？解释 I 使得 I(? x(P(x) P(a) = 0，当且仅当存在
17、dDI 使得 PI(d ) PI(aI ) = 0，即 PI(d ) = 1 且PI(aI ) = 0。这是可以办到的。可取解释I 如下。DI= a, b ， PI(a) = 0， PI(b) = 1，aI = a)I(? x(P(x) P(a) = (PI(a) PI(a) (PI(b) PI(a) = 0可取满足语句? x(P(x) P(a) 的解释 I 如下。DI = b， PI (b) = 1，aI = bI (?x(P(x) P(a) = PI (b) PI (b) = 1语句 ? x(P(x) P(a) 是非永真的可满足式。设 I 是一个解释， P 是一元谓词符号，我们可把论域 D
18、I 上的一元谓词 PI看作 DI 的子集 x | x DIPI(x) = 1I(?xP(x) = 1 当且仅当 PI ?I(? xP(x) = 1 当且仅当 PI = DI I(?x(P(x) Q(x) = 1 当且仅当 PI? QII(?x(P(x) ?Q(x) = 1 当且仅当 PI= QII(?x(P(x) Q(x) = 1 当且仅当 PIQI = DI I(?x(P(x) Q(x) = 1 当且仅当 PIQI ?语句 (?xP(x) ?xQ(x) ?x(P(x) ?Q(x) 的类型是什么？解释 I 使得 I(?xP(x) ?xQ(x) = 1 当且仅当(PI = QI= ? ) 或者
19、(PI? 且 QI? )。解释 I 使得 I(?x(P(x) ?Q(x) = 1 当且仅当PI QI? 或者 ( PI ) ( QI ) ? 。1.若 PI = QI= ? ， 则 ( PI )( QI )= DI ? 。2.若 PI? 且 QI? ，这时 PI QI= ? 且( PI ) ( QI ) = ? 是可能的。这表明该语句可能不是永真式。可取不满足 (?xP(x) ?xQ(x) ?x(P(x) ?Q(x) 的解释 I 如下。DI= a, b ，PI(a) = 0, PI(b) = 1, QI(a) = 1, QI(b) = 0(?xP(x) ?xQ(x) ?x(P(x) ?Q(x)
20、不是永真式。可取满足 (?xP(x) ?xQ(x) ?x(P(x) ?Q(x) 的如下解释 I 如下。DI = a, b，PI (a) = QI (a) = 0，PI(b) = QI (b) = 1I (?xP(x) ?xQ(x) = 1， I (?x(P(x) ?Q(x) = 1 (?xP(x) ?xQ(x) ?x(P(x) ?Q(x) 不是永假式，是非永真的可满足式。要判断一个公式A 的类型，首先分析它在一个解释和该解释中的一个赋值下的意义，看其是否能够成为真命题或假命题，得出关于A 的类型的初步结论。若估计A 是永真式（或永假式），则证明对于任意解释I 和 I 中任意赋值 v， I(A)
21、(v) = 1（或I A v) = 0）。若估计A 不是永真式（或永假式），( )( )若估计不是永真式或永假式，则具体给出一个解释I 和 I 中一个赋值 v 使得I(A)(v) = 0（或 I(A)(v) = 1）。因此，若估计A 是非永真的可满足式，则需具体给出解释 I 和 I 中赋值 v ，以及解释 I 和 I 中赋值v ，使得 I(A)(v) = 1， I (A)(v ) = 0。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 5 页 - - - - - - -
22、- - 5设 W 是一个集合，S 是 W 的子集， P 是以 W 中元素为输入的程序。若 P 满足以下条件：如果以S 中元素为输入，则P 运行终止且输出“是”；如果以不在S 中的元素为输入，则 P 运行终止且输出“否”。我们称 P 解决了 S 的判定问题。如果有一个程序解决了S 的判定问题，就称 S 的判定问题是 可解的 。若 P 满足以下条件：如果以S 中元素为输入，则P 运行终止且输出“是”，如果以不在S 中的元素为输入，则 P 运行不终止；我们就称P 部分地解决了 S 的判定问题。如果有一个程序部分地解决了S 的判定问题，就称S 的判定问题是 半可解的 。取 W 为所有一阶逻辑公式的集合
23、，取S 为所有永真式的集合。可以证明，S 的判定问题是半可解的，但不是可解的，即一阶谓词逻辑是半可判定的，但不是可判定的。若取 S 为所有重言式的集合，可以证明，S 的判定问题是可解的。取 W 为所有二阶逻辑公式的集合，取S 为所有永真式的集合。可以证明，S 的判定问题不是半可解的。公式 A 是永真式当且仅当A 的闭包是永真式。证明 设 A 的闭包是 ? x1? xn A 。(? ) 设 A 是永真式。任取解释 I 和任意 d1, , dn DI ，令 I 中赋值 v 满足 v x ) = d , i = 1 , , n。因为 A 是永真式，所以(i)iI(A)(v) = 1，因此 I(? x
24、1? xn A ) = 1。这表明 A 的闭包是永真式。(? ) 因为 ? x1? xn A A 是永真式，所以若A 的闭包是永真式，则A 也是永真式。公式 A 是永假式当且仅当A 的存在闭包是永假式。证明设 A 的存在闭包是?x1?xn A。(? ) 设 A 是永假式。任取解释 I 和任意 d1, , dn DI ，令 I 中赋值 v 满足 v x) = d , i = 1 , , n。因为 A 是永假式，所以(i)iI(A)(v) = 0，因此 I(?x1?xn A) = 0。这表明 A 的存在闭包是永假式。(? ) 因为 A ?x1?xn A 是永真式，所以若A 的存在闭包是永假式，则A 也是永假式。作 业11. (4), (5), (6), (7)12. (6)名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 5 页 - - - - - - - - -