《04-面向计算机的数理逻辑(ch3).ppt》由会员分享，可在线阅读，更多相关《04-面向计算机的数理逻辑(ch3).ppt（97页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、面向计算机的数理逻辑面向计算机的数理逻辑主讲：李伟刚西北工业大学软件与微电子学院1第三章第三章 谓词逻辑谓词逻辑23.1 我们需要更丰富的语言v命题逻辑通过三个角度来展开研究证明论（自然演绎演算）句法（公式的树状性质）语义（公式的实际含义）l这是基于：判断语句，即关于现实世界论述的每个赋值或模式都能给出真值。3我们知道，命题演算的基本研究单位是原子命题，在命题演算中，原子命题是不能再分割的了。这对研究命题间的关系是比较合适的。但是，在进一步研究时就会发现，仅仅命题演算对我们是很不够的并且也不充分，比如：三段论在命题演算系统中是无法完成的。例如：所有的科学是有用的 数理逻辑是科学 所以，数理逻辑
2、是有用的 又例如：凡人必死 张三是人 故张三必死4 上述两个例子用命题逻辑描述不充分的主要原因就是在于这种推理中需要对原子命题作进一步分解，在上述两个例子中，每个例子三个命题间，具有必然的内在逻辑关系，只有对这种内存逻辑联系深入研究后，才能解决形式逻辑中的一些推理问题。谓词演算正是为了这样的目的，换言之也就是对原子命题进行进一步的分解。5 在谓词演算中，将原子命题分解为谓词与个体两部分，在上例中，“数理逻辑是科学”即主语“数理逻辑”与谓语“是科学”，“张三是人”中的“张三”是主语，“是人”为谓语。换言之在数理逻辑中将主语称为个体，将谓语称为谓词。所谓个体是可以独立存在的物体。它可以是抽象的，也
3、可以是具体的，如：鲜花，代表团，自行车，自然数，唯物主义等等都是个体。谓词是用来刻划个体的性质或关系。如“3整除6”这里3与6是个体，关系“整除”是谓词。一个谓词可以与某个个体相联，此种谓词称为一元谓词。上例中张三，3，6等也可以是抽象的，比如x，y，称为变元/变量。由个体组成的集合称为个体域（或论述域），以某个个体域I为变域的变元叫做个体变元。6 一个单独的谓词是没有含义的，如：“是大学生“，这个谓词必须跟随一定数量的个体后才有明确的含义，最重要的是能分别其真假。个体谓词中的次序有时也是很重要的，如“上海位于南京与杭州之间”，此命题为真，其中“上海”、“南京”、“杭州”三个个体间次序不能随便
4、颠倒，如果写成“杭州位于南京和上海之间”，则此时命为假。所以，由谓词以及跟随它的若干个有一定次序的个体便可构成一个完整的命题。7 下面我们一般用大写字母A，BE表示谓词，用小写字母a，b，cz表示个体（或个体变元），这样x，y间具有关系B可记作B（x，y），x，y，z具有关系C，记作C（x，y，z），上述是二元谓词和三元谓词，当然也可以表示为n元谓词就是有n个个体变元的谓词，并约定0元谓词是命题。n元谓词当然需要赋于n个个体变元才有意义，我们把谓词后填以个体称为谓词填式。有了谓词的概念后我们可以将一些日常用语及命题更深刻地刻划出来，下面我们以几个例子说明：8 例1：王强是大学生李华也是大学生。
5、解：F表示是大学生，F（x）表示x是大学生。a表示“王强”，b表示“李华”，则此式可表示为：F（a）F（b）例2：我国领导人访问美国。解：F（x，y）表示x访问y，a表示我国领导人，b表示美国，则此式可表示为：F（a，b）9 例例3：大楼建成了。解解：F（x）表示“x建成了”，G（x）表示“x是大的”，H（x）表示“x是楼”，则此式可表示为：F F（a a）G G（a a）H H（a a）例例4：这个人正在看那本红皮面的书。解解：F（x，y）表示“x正在看y”，G（x）表 示“x是人”，H（y）表示“y是红皮面的”，U（y）表示“y是书”，a表示“这个”，b表示“那 本”，则此式可表示为：F
6、F（a a，b b）G G（a a）H H（b b）U U（b b）10一般地讲，对日常的语句，我们可给出一个大体的准则，根据这些准则可写出其逻辑表达式来。名词：专用名词（如王强，美国等）为个体 通用名词（如楼房，人等）一般可为个体 代名词：人称代词（如：你，我，他），指示代词（如这个，那个）为个体 不定代词（如任何，每个，有些，一些等）为量词 形容词：一般为谓词 数词：一般为量词 动词：一般为谓词 副词：与所修饰的动词合并为一谓词，不再分解 前置词：与其它有关字合并为一，本身不独立表示 连接词：一般为命题联结词 以上准则只供参考，在具体应用时常常也有许多例外 113.2 作为形式语言的谓词逻
7、辑v在谓词逻辑中，将句子表达的复杂事实编码为逻辑公式很重要v编码一旦完成，我们的主要目标成为：对那些公式中表达的相关信息进行符号地（）或语义地（）推导。123.2.1 量词量词 在数学上或日常生活中经常碰到“对一切”、“所有的”、“存在一个”、“至少有一个“等的概念，我们学过的命题逻辑是无法表达清楚的。一个谓词演算中的表达不一定是确定的，个体域中不同的个体代入后可得到不同的真假值。如我们考察下面两个式子（它们均以整数作为其个体域）：（1）（x+1x+1）2 2=x=x2 2+2 x+1+2 x+1 （2）X+6=5 对于（1）我们发现任何整数代入后等式总是正确，但是对 （2）分析则不然，它只存
8、在一个整数即（-1）代入后使得等式 成立。又如：“q或者大于0，或者等于0，或者小于0”，当然 该句可写成：q0q=0q0a=0a（x x，0 0），），=（x x，0 0），），（x x，0 0）=（x x，0 0）yzy）。该式中的约束变元x不能改名y（y是作用域中的约束变元），但可改名为z（z也是作用域中的约束变元），因为该公式 x x（x2 0 y 0 y（x=yx=yz z（zyzy）的意思是“对于任何个体，其平方必0，并且对于任何新个体，原个体都与新个体相等，并且存在一个个体，它大于该新个体”。而改名为y后的结果式为：y y（y2 0 y 0 y（y=yy=y z z（zy)zy)
9、32 其意思是“对于任何个体，其平方必0，并且对于任何新个体，新个体必与自己相等并且存在一个个体，它大于该新个体”，显然它们的意思不相同，从约束关系看，结果式的约束关系显然与原来的约束关系不相同。但是：z（z2 0 y（z=y z（z y）意思与原式相同，从约束关系看，结果式的约束关系与原式一样。例如例如：上面这个例子中，如果将原式的约束变元y改名为其它变元，如改名为t，再将约束变元x改名为y结果式为：y（y2 0 t（y=t z（z t）显然与原来的约束关系完全相同，所以说这是正确的改名。是否不改变原约束关系的改名都是正确的改名呢？确实如此。33 总之改名规则用更加简单的途述为：（1 1）改
10、名时需要更改的变元符号范围是量词中的变元以及该量词辖域中此变元所有约束出现处，而在公式之其余部分不变。（2 2）对受某量词约束的变元改名时，新名决不能与该量词的辖域中的其它自由变元同名。（3）改名前与改名后的约束关系保持不变。34 接下来我们在讨论代入问题。第一第一.代入是对自由变元而言，也就是说对自由变元可施行代入。第二第二.特别注意代入是有条件的，不能盲目代入，不则将发生错误。35 例如例如：x x（x=x=y y z z）该公式中的自由变元y可以代以2,z,y+z,sin(t)等因为代入后的结果式 x x（x=2x=2 z z）,x x（x=z x=z z z）,x,x（x=(y+z)x
11、=(y+z)z z）,x x（x=(x=(sin(t)sin(t)z z）均是原式的特例,也就是说约束变元没有变化,所以是正确的。又例如:x(x=:x(x=y.zy.z)由自由变元y代以x或者代以含x的式子就错了，如，自由变元y决不能代以x，x+t，sin(x)等等，代入后的结果式为：x(x=x(x=x xz z)，x(x=x(x=（x+tx+t）z)z)，x(x=x(x=（sin(xsin(x)）z)z)均不是原式的特例，也就是说这时的约束关系与原式不同。36 再例如：如果一定要代以x或代以含x的项，则必须先把原式中的约束变元改名，使得与代入项无关，比如将上式改为u，而后施行代入，这时结果式
12、为：u u（u=u=x xz z），），u u（u=u=（x+tx+t）z z），），u u（u=u=（sin(xsin(x)）z z）显然这是原式的特例，约束关系与原式一致。第三.代入必须“处处”进行。所谓“处处”进行是指当对某自由变元施行代入时，必须对该公式中该变元的一切自由出现均施行代入，否则将是错误的。37 第四.为了确保对自由个体变元的正确代入，我们规定，代入前先对原式施行改名，使得原式中所有约束变元名与代入式中所有变元名互不相同，然后再施行代入。第五.对于命题变元和谓词变元也可施行代入，而且代入也是有条件的，其条件仍就是代入前后约束关系必须保持不变。下面我们举例说明对命题变元和谓词
13、变元的代入。38 例例一.试在 y（pA（y）（p xA（x）中把p代入以y B（x，y），和把p代以x B（x，y）注意：y B（x，y），x B（x，y）也可以写为 y B xy，x Bxy。解解：因为对p用y B（x，y）代入以后约束关系不发生变化，所以可立即施行代入得 y（y B（x，y）A（y）（y B（x，y）x A（x）。对于 x B（x，y）代p的情形，如盲目代入的话，约束关系就将发生变化，从而出现错误，所以必须先将原式中的约束变元y改名，使之与代入式中的变元无关，如将y改为t得 t（x B（x，y）A（t)(x B（x，y）x A（x）这个结果显然是原式的特例，故代入正确。3
14、9 经过分析为了确保对命题变元的代入正确我们规定，代入前先对原式施行改名，然后施行代入，显然，按此规定施行代入，结果一定正确。而且一切正确的关于命题变元的代入均可按此规定得到。谓词变元的代入比较复杂，因为在公式中为此变元均是以谓词填式的形式出现，因此在代入前应先将代入的谓词变成相应的填式，然后再把代入好的填式代到原式中去，因此要使每个代入正确，必须保证二次代入均正确，即二次代入过程中的约束关系均不应发生变化，我们举例说明这一过程。40 例2.试在 x（X（x，y）y（x）yX（t，y）中，把X（e1，e2）代以 tA（e1，e2，x，t)。解：因为代入式 tA（e1，e2，x，t）中x是自由变
15、元，t是约束变元，而原式中谓词填式X（x，y）中x是约束变元，所以若盲目代入的话，必须发生变元混乱，产生错误。为此必须先对原式及代入式进行改名，使之相互间的变元均不同名，然后施行代入。1)先把代入式改名为 uA（e1，e2，x，u）2)再把原式改名为 z(X(z,y)Y(z)yX（t，y）3)再作关于X(z,y)的代入式的填式 uA(z,y,x,u)4)再作关于X(t,y)的代入式的填式 uA(t,y,x,y)5)最后将这两个填式3),4)代入到原式即可 z(u A(z,y,x,u)Y(z)yu A(t,y,x,y)同理,为了确保对谓词变元的代入正确,我们仍然参照命题变元的代入规定执行。41
16、定义.项的定义：（1）任何变量都是项。（2）若cF是零元函数，则c是项。（3）若t1,t2,.,tn是项，且fF的元n0，则f(t1,t2,.,tn)是项。（4）没有其他形式的项。BNF写法：t:=x|c|f(t,.,t)，其中x在变量集合var中选取；c在F中的零元函数符号中选取；f在F中的多元函数符号中选取。Note:v项的第一批构建块内容是常量（零元函数）和变量；v更复杂的项是由以前构造好的项与其元数相匹配数目的函数符号得到的；v项的概念依赖于集合F，如果改变了F，就改变了项的集合。42 定义.给定变量x,项t和公式，定义t/x为用t代替中变量x的每个自由出现而得到的公式。Note:vt
17、/x实际意味着对实施运算t/x所得到的公式；v如果是公式，则t/x 也是一个公式；v替代过程应满足前面讨论的改名和代入规则。43 定义.给定变量x,项t和公式，说t关于中的x是自由的，如果对出现在t中的任何变量y，中没有自由的叶子结点x处于 y y或 y y的作用范围之内。Note:v实质上是不能由替换引入多余的约束。例子：用项f(x,y)替代x44例子：用项f(y,y)替代x453.3 谓词逻辑的证明论3.3.1 自然演绎规则自然演绎规则 谓词逻辑中自然演绎演算的证明和命题逻辑一致，但是需要增加新的规则，用于处理量词和相等符号。对量词和相等的附加规则以两种形式出现：引入规则和消去规则。461
18、.相等的证明规则相等的证明规则 相等的含义：不是语义或内在的相等，而是计算结果的相等。由于任何项t必然与它本身相等，所以有“相等引入规则”：（3-5）Note：仅当t为项时，这个规则才被引用 更一般地，我们需要一个可以反复做相等代换的规则。可以将代换表示为规则=e：Note:无论何时引用规则=e，都要求t1和t2对中的x是自由的。47 约定.写形如t/x的代换时，假定t对中变量x是自由的。Note:v由上一节，没有此约定条件，代换是没有意义的。例子：例子：证明矢列 （3-6）证明：48例子：例子：证明矢列 （3-7）证明：Note：对规则=i和=e的讨论说明相等具有自反性 (3-5)对称性 (
19、3-6)传递性 (3-7)492.全称量词的证明规则全称量词的证明规则 的消去规则如下：它的含义是：若 x x是真的，可以将中的x用任何项t去代替（要求t关于中的x是自由的），并且可以得出t/x也是真的。证明:t/x是通过把中所有自由出现的x用t代换得到的。可以将t视为x的一个更为具体的实例。因为我们假定了对所有x的取值都是真的，则对于任何项t的情形也应该是真。50讨论:=y(xy)，用项y代换x。假设用“小于”关系研究关于数的推理。x的含义是：对所有的数n，必然存在某个比n大的数m，这对自然数和实数都正确。然而，y/x是公式y(y0的fF，从集合A上n元组An到A的具体函数fM：An A4.
20、对每个元数n0的谓词PP，A上的n元组An的子集PM：PMAn Note：f和P是符号，fM和PM分别表示模型M中的一个具体函数（或元素）和关系75例子：令 ，；其中i是常量，F是一个一元谓词符号，R是一个二元谓词符号。模型M包含一组具体元素的集合A，它可能是计算机程序的状态集合。则iM、RM、FM可以分别解释为设计的初始状态、状态迁移关系和最终状态的集合。例如，令 ，a,对这个模型非形式化地检验一些谓词逻辑公式：1.公式存在从初始状态到某个状态的迁移。762.公式表示：初始状态不是可接受的最终状态。3.公式表示：状态之间的迁移关系具有确定性，即始于任何一个状态的所有迁移都至多到一个状态。4.
21、公式表示：这个模型不存在死锁，即任何状态都可以迁移到某个状态。77定义：对具体值的论域A，一个查询表或环境指的是从变量集合var到A的函数l：varA。对这样的l，用 表示将x映射到a并将其他变量y映射到l(y)的查询表。定义：给定关于(F,P)的模型M和环境l，对于(F,P)上的每个逻辑公式和查询表l，通过对的结构归纳定义一个满足关系 。若 成立，则称在模型M中，相对于环境l，的赋值为T。P:如果的形式为P(t1,t2,tn)，则在集合A中将t1,t2,tn解释为：根据l把所有变量用它们的值代替。用这种方式，对这些项的每项来计算A的具体值a1,a2,an，其中任何函数符号fF可通过fM来描述
22、。成立当且仅当(a1,a2,an)在PM集合中。78x:关系 成立，当且仅当 对所有aA都成立。x：对偶地，关系 成立，当且仅当 对某个aA成立。：关系 成立，当且仅当 不成立。：关系 成立，当且仅当 或 成立。：关系 成立，当且仅当 和 都成立。：关系 成立，当且仅当只要 成立，则 成立。有时，用 表示 不成立。79归纳论断：成立，当且仅当 成立，只要l与l是的自由变量上的两个相同环境。特别地，如果根本没有自由变量，称是一个语句语句。此时不考虑l的选择，就可以推出 成立或不成立。因此，对语句来讲，直接写成 ，其成立与否与环境无关。80例子：令F alma，P friend，其中alma是一个
23、常量，friend是两个变量的谓词。选择模型M包括个体集A a,b,c，常量函数almaM a,以及谓词friendM (a,a),(b,a),(c,a)。需要检测模型M是否满足：alma的朋友的朋友都不是alma的朋友解：首先，使用谓词逻辑表达此语句：xy(friend(x,alma)friend(y,x)friend(y,alma)取x为a，取y为b，显然，模型M不满足此公式。假设重新定义friend为(b,a),(c,b)情况如何？813.4.2 语义推导语义推导考虑：命题逻辑中，1,2,n 成立的含义？对谓词逻辑公式，如何定义？定义：设是谓词逻辑中的公式集合（可能是无限集合），是谓词逻
24、辑公式。1.语义推导成立当且仅当对所有的模型M和查询表l，对所有的 ，都成立，则 也成立。2.公式是可满足的当且仅当存在某个模型M和环境l，使得 成立。3.公式是有效的当且仅当在我们能够检测的所有模型M和环境l中，成立。4.集合是一致的或可满足的当且仅当存在一个模型M和一个查询表l，使得对所有的公式 ，成立。82Note：在谓词逻辑中，符号有更多的含义：它表示模型检测“M”和语义推导“1,2,n”。难题一：M，若M的具体值的论域A是无限的，则需要验证无穷多个元素a；难题二：1,2,n，需要检测所有可能的模型，这对于机器来说不可能完成。83例子：语义推导含义：设M是满足x(P(x)Q(x)的模型
25、，需要证明M也满足xP(x)xQ(x)。有蕴含式含义可知，若不是模型的所有元素都满足P，那么问题就解决了。否则，每个元素都满足P，而且由于M满足x(P(x)Q(x)，这事实上使得模型里的每个元素也满足Q。综上，所以M满足xP(x)xQ(x)。843.4.3 相等的语义相等的语义函数=M为关于模型M的集合A上的实际相等关系（a，b）属于集合=M当且仅当a和b是集合A中的相同元素。例子：给定 ，相等的解释=M必然是：（a，a），（b，b），（c，c）853.5 谓词逻辑的不可判定性谓词逻辑的不可判定性命题逻辑中，可以通过统一的可机械执行的程序判定命题逻辑公式的有效性：若有n个原子命题，那么的真值表
26、有2n行，成立当且仅当真值表中对应于的那一列都是T现在讨论谓词逻辑的有效性。给定谓词逻辑中的一个逻辑公式，成立与否？结论：对每个公式都可以通过验证得出是有效的还是无效的，但是对所有的，不存在一个统一的可机械执行的程序能够判定的有效性86定理：谓词逻辑中的有效性判定问题是不可判定的：不存在对任意给定的，判定是否成立的程序。（证明略）另外两个不可判定结果：1.可满足性 是不可满足的当且仅当是有效的。由于不能判定有效性，所以不能计算满足性。2.合理性和完备性：成立，当且仅当因为不能判定有效性，因此不能判定可证性873.6 谓词逻辑的表达能力谓词逻辑的表达能力谓词逻辑比命题逻辑有更强的表达能力：谓词、
27、函数符号、量词符号但是：牺牲了有效性、可满足性和可证明性然而，关于模型的公式检测是实用的：SQL，XQuery状态图的例子：模型M是定义在具体“状态”集合A上的二元谓词R的解释，比如 给定状态集合A=s0,s1,s2,s3，令RM是集合(s0,s1),(s1,s0),(s1,s1),(s1,s2),(s2,s0),(s3,s0),(s3,s2)可以用有向图来描述88问题：如何用谓词逻辑表达“可达性”？为此定理（紧致性定理）设是谓词逻辑的一个语句集合。若的所有有限子集都是可满足的，则也是可满足的证明：反证法。假设不可满足，则语义推导成立，因为没有模型使所有的都为真。由完备性，这意味着矢列是有效的
28、。因此，在自然演绎中，这个矢列有一个证明；这个证明只能使用中有限个前提集合。但是也是有效的，因此由合理性，有。但是后者与的所有有限子集都是可满足的矛盾。证毕。Note：这里用到了关于矢列更一般的概念，可以处理无限多个前提。合理性和完备性依然为真89定理：可达性用谓词逻辑是不可表达的：不存在仅以u和v为自由变量且仅有一个二元谓词符号R的谓词逻辑公式，使得在有向图中成立当且仅当该有向图中存在一条从伴随u的结点到伴随v的结点的路径。证明：假设存在一个公式，满足存在一条从与u相伴的结点到与v相伴的结点的路径。设c和c是常量，设n是公式，为表达存在一条从c到c的长度为n的路径：我们定义0是c=c，1是R
29、(c,c)，且对n1，定义 90令=i|i0c/uc/v。中的所有公式都是语句且是不可满足的，因为中所有的语句的“合取”说的是不存在长度为0、1、的从标记为c的结点到标记为c的结点的路径，但存在一条从c到c的有限路径，因为c/uc/v为真。然而，的每个有限子集都是可满足的，因为存在任意有限长的路径。因此，由紧致性定理，本身是可满足的。这是一个矛盾。因此，不存在这样的公式。913.6.1 存在式二阶逻辑存在式二阶逻辑如何才能表达可达性？寻求谓词逻辑的一种扩展，而不是发明一套全新的语法、语义和证明论试图将量词用于谓词符号：对于n 1个参量的谓词符号P，考虑形如的公式，其中是出现谓词P的一个谓词逻辑
30、公式。这种形式的公式就是“存在式二阶逻辑”的公式。92一个二元的例子：(2-12)其中Ci是霍恩子句（见2.5.3节）：如果把R和P看成是状态集上的两个迁移关系，那么C4的含义是任意R边都是P边，C1说明P是自反的，C2指出P是传递的，而C3保证了不存在从与u相伴的结点到与v相伴的结点的P路径。含义：公式(2-12)在有向图中成立，当且仅当该图中不存在从与u相伴的结点到与v相伴的结点的一条有限路径。这说明了不可达性不可达性。933.6.2 全称式二阶逻辑全称式二阶逻辑对(2-12)式使用德摩根律得到：(2-14)这是一个全称式二阶逻辑公式。该公式表达了可达性。定理：设M=(A,RM)是任意模型
31、，则公式(2-14)在M中查询表l下成立，当且仅当在M中，从l(u)出发，l(v)是R可达的。证明：1.假设对P的所有解释T,有：成立那么，对RM的自反、传递闭包解释也成立。但对这个T，仅当 成立，则 必成立，而其它子句Ci(i3)都是假的。但这意味着必须成立。所以(l(u),l(v)T成立，则存在从l(u)到l(v)的有限路径。942.反之，设在M中，从l(u)出发，l(v)是R可达的。v对P的任何非自反、非传递或不包含RM的解释T，关系 成立。因为T使子句C1,C2或C4成立。v另一种可能是：T是包含RM的自反、传递关系，则T包含RM的自反传递闭包。由假设，(l(u),l(v)在该闭包中。因此，在查询表l下的解释T中，C3为真，故，成立。总之，对所有解释TAA,上式都成立，即原式成立。证毕。95完整的二阶逻辑(2-15)(2-15)式成立，当且仅当存在某个T，对所有U，有：如果对关系的关系取量词，就得到三阶逻辑一阶逻辑中的一个模型检测96第三章 完97