7.谓词演算

谓词演算0命题逻辑的基本概念1谓词演算的基本概念2归结3归结反演系统4基于归结法的问答系统5归结法的应用•命题：能判断真假（不是既真又假）的陈述句。简单陈述句描述事实、事物的状态、关系等性质。例如：1．1+1=2•2．雪是黑色的。•3．北京是中国的首都。•4．到冥王星去渡假。判断一个句子是否是命题，有先要看它是否是陈述句，而后看它的真值是否唯一。以上的例子都是陈述句，第4句的真值现在是假，随着人类科学的发展，有可能变成真，但不管怎样，真值是唯一的。因此，以上4个例子都是命题。而例如：1．快点走吧！2．到那去？3．x+y10等等句子，都不是命题。命题逻辑的基本概念合取式：p与q，记做pΛq析取式：p或q，记做p∨q蕴含式：如果p则q，记做p→q等价式：p当且仅当q，记做p=q若A无成假赋值，则称A为重言式或永真式；若A无成真赋值，则称A为矛盾式或永假式；若A至少有一个成真赋值，则称A为可满足的；析取范式：仅由有限个简单合取式组成的析取式。合取范式：仅由有限个简单析取式组成的合取式命题表示公式将陈述句转化成命题公式。如：设“下雨”为p，“骑车上班”为q，，1．“只要不下雨，我骑自行车上班”。～p是q的充分条件，因而，可得命题公式：～p→q2．“只有不下雨，我才骑自行车上班”。～p是q的必要条件，因而，可得命题公式：q→～p3．“如果我进城我就去看你，除非我很累。”设：p，我进城，q，去看你，r，我很累。则有命题公式：～r→(p→q)。4．“应届高中生，得过数学或物理竞赛的一等奖，保送上北京大学。”设：p，应届高中生，q，保送上北京大学上学，r，是得过数学一等奖。t，是得过物理一等奖。则有命题公式公式：p∧(r∨t)→q。•基本等值式–交换率：p∨q=q∨p；pΛq=qΛp–结合率：(p∨q)∨r=p∨(q∨r);(pΛq)Λr=pΛ(qΛr)–分配率：p∨(qΛr)=(p∨q)Λ(p∨r)；pΛ(q∨r)=(pΛq)∨(pΛr)–摩根率:～(p∨q)=～pΛ～q；～(pΛq)=～p∨～q–吸收率:p∨(pΛq)=p；pΛ(p∨q)=p–同一律:p∨0=p；pΛ1=p–蕴含等值式:p→q=～p∨q–假言易位式:p→q=～p→～q1谓词演算的基本概念几个基本定义个体词：描述独立存在的客体，或一个具体的事物，或一个抽象的概念谓词：刻画个体词的性质或个体词之间的关系个体常量：表示具体的或特定的个体的词个体变量：表示抽象的或泛指的个体的词个体域：个体变量的取值范围，一般用D表示谓词常量：表示具体性质或关系的谓词，一般用大写英文字母P，Q，R，T表示谓词变量：表示抽象的或泛指的谓词，一般表示为P(x)，Q(x,y)，R(x,b)等N元谓词：含有n个个体的谓词一阶谓词：谓词中只含有个体词，不含有谓词1谓词演算的基本概念几个基本定义1原子公式：由原子符号与项构成的公式为原子公式，形如：A(x1,x2,……xn)其中：A是谓词，x1,x2,……xn是项，项包括：常量符号、变元、函数例如：A(f(x),y)2合适公式：(1)原子谓词公式是合适公式(2)如果A、B是合适公式，则～A、A∨B、A∧B、A→B、AB是合适公式(3)如果A是合适公式，则是合适公式(4)有限次使用上述规则得到的公式是合适公式例如：)(),(xxAxxA))()((yRxPxy3文字：一个原子公式及原子公式的否定称作文字4句子：所有变量均受约束的合适公式称作句子5二个重要推理规则：（1）假言推理：W1,W1→W2W2（2）全称消去推理：6谓词公式的真值：给定谓词公式wffA，个体域E（1）如果对于A的所有赋值wffA都为真，则称wffA在E上是有效的（永真）（2）如果对于A的所有赋值wffA都为假，则称wffA在E上是不可满足的（永假）（3）如果至少在一种赋值下wffA为真，则称wffA在E上是可满足的7子句：文字的析取组成的公式称子句如：A∨～B)()(AWXxW8前束范式：一个公式，如果所有量词都在整个公式的开头，其作用域延伸到公式的末尾，则称该公式为前束范式，记为：F=(Q1X1)(Q2X2)……(QnXn)M其中：Q1,Q2,……Qn表示量词X1,X2,……Xn表示个体变元M表示不含量词的谓词公式（母式）例如：9合取前束范式：一个前束范式中，谓词公式M由若干合取项构成的公式称作合取前束范式。如：、))(),((zRyxQzyx))),()(())()(((~yxSzRyQxPyzx2公式标准化目的：将一个给定的公式化成一个合取前束范式，最终得到一个子句集以下例说明公式标准化的过程))]}(),((~))),(()(([)({yPyxQyyxfPyPyxPx1消去蕴含符号：利用公式QPQP~))]}(),((~~))),(()((~[)({~yPyxQyyxfPyPyxPx2缩小否定符号的辖域：利用DeMorgan定律QPQP~~~）（QPQP~~~）（))]}(~),(())),(()((~[)({~yPyxQyyxfPyPyxPx3变量标准化：利用变量代换使不同的量词所约束的变元各不相同))]}(~),(())),(()((~[)({~wPwxQwyxfPyPyxPx5化成前束形式：对于不含有存在量词的谓词公式可以将所有全称量词移到公式左边。此时，每个全称量词的辖域都是整个公式。4消去存在量词：（斯托林标准化）例如：),(yxxPy解释为：对于任何一个学生y，都存在一个老师x。显然任取的学生不同，所对应的老师也不同。斯托林函数：受存在量词约束的变元可以用一个函数来代替，函数的自变量包括该存在量词左边全部全称量词约束的变元。如上例中的变元x可以用y的函数代替，得斯托林常量：不含有变量的斯托林函数)),((yyfyP)))]}((~))(,(())),(()((~[)({~xgPxgxQyxfPyPyxPx7消去全称量词：由于公式中的所有变元均受全程量词约束，所以可直接将全称量词消去。6将母式化成合取范式：（每个合取项是一个析取式）利用分配律：)()()(RPQPRQP)))]}((~)(,())),(()([(~)({~xgPxgxQyxfPyPxPyx))](,()([~))],(()(~)({[~xgxQxPyxfPyPxPyx))]}((~)([~xgPxP))](,()([~))],(()(~)([~xgxQxPyxfPyPxP))]((~)([~xgPxP8消去合取符号：每个合取项用一个与其等价的子句表示，得到一个子句集。9更换变元名称：（变元分离标准化）))((~)(~3xgPxP）（关于公式标准化的讨论：（1）利用斯托林函数标准化得前束范式称为S_标准形。（2）S_标准形不唯一。选择不同的斯托林函数可以得到不同的S_标准形。（3）公式F与其S_标准形Fs在F非永假时不等价。)),(()(~)(~1yxfPyPxP）（))(,()(~2xgxQxP）（))((~)(~333xgPxP）（)),(()(~)(~111yxfPyPxP）（))(,()(~2222xgxQxP）（一个定理：设Fs是合适公式F的S_标准形子句集，则F永假的充要条件是Fs为永假。归结归结原理数理逻辑问题的证明方法：问题：给定公式集F1,F2,…Fn，求证：公式W为真，即：要证明F1,F2,…Fn→W为永真式。1直接证明：设：F1∧F2∧…∧Fn为真，推出W为真。2间接证明：设：F1∧F2∧…∧Fn∧～W为假，推出矛盾。对于间接证明，设S0={F1,F2,…Fn}，构造集合S=S0∪{～W}，证明集合S为假。下面给出归结的基本过程。1构造初始子句集S=S0∪{~W}2检验S中是否存在空子句（即永假式：P∧～P），如有空子句，则结束3否则，用归结方法扩大子句集S，GOTO2命题逻辑归结原理(1)关于归结式互补：一个文字L与其否定式～L称为互补。归结式定义：给定二个子句C1，C2，若C1中有一个文字L1，C2中有一个与L1互补的文字L2，则分别从C1中删去L1，从C2中删去L2，其余部分组成的析取式称为C1，C2的归结式。例：给定C1=L∨C’1，C2=～L∨C’2，求归结式。解：根据归结式定义，消去L和～L，得到归结式为：C=C’1∨C’2值得注意：C1和C2的归结式C与C1∧C2并非等价，即：CCC21例如：C1=P∨Q，C2=～P，则归结式C=Q设C1∧C2为真，则～P为真，P为假，所以Q为真，即归结式C为真。反之，设归结式C为真，则Q为真，但是P和～P的真值无法确定，所以不能确切得出C1∧C2的真值。定理：二个子句C1和C2的归结式C是C1和C2的逻辑结论。即：证明：不失一般性，设C1=L∨C’1，C2=～L∨C’2，则C=C’1∨C’2据题：设C1和C2为真讨论：（1）L为真，则～L为假∵C2=～L∨C’2为真，∴C’2为真，则有：C=C’1∨C’2为真。（2）L为假∵C1=L∨C’1为真，∴C’1为真，则有：C=C’1∨C’2为真。证毕CCC21一个重要结论：同理，可以得到：推论：设C是子句Ci和Cj的归结式，则子句集S={C1,C2,…Cn}与子句S’={C,C1,C2,…Cn}的不可满足性是等价的其中：Ci，Cj∈S证明：（1）充分性：设：S是不可满足的，则C1,C2,…Cn中至少有一个Ci为假∵Ci∈S’∴S’是不可满足的（2）必要性：设S’是不可满足的，讨论如下：①设C为真，则C1,C2,…Cn中至少有一个Ci为假，∵Ci∈S∴S是不可满足的②设C为假，则由可知：Ci，Cj中至少有一个为假且Ci，Cj∈S∴S是不可满足的证毕PQQP~~）（）（2121~~CCCCCC）（jiCCC~~(2)命题逻辑归结归结过程：给定公理集F（前提）和命题P（结论）①用子句形式表示公理集F，得到子句集S0②将P的否定式～P用子句表示，构成子句集S=S0∪{~P}③反复利用归结方法，直到得出空子句（即矛盾式），证明结束例：已知公理集如下(1)(2)(3)(4)求证：R为真证明：首先写出(2)、(3)式的子句表达式RQP）（PQTS）（T得到子句集S={P,~P∨~Q∨R,~S∨Q,~T∨Q,T,~R}归结树：RQPRQP~~)2(）（式)(~)(~)~(~)3(QTQSQTSQTS）（式~P∨~Q∨RP~Q∨R~R~Q~T∨Q~TTNIL谓词逻辑归结合一：寻找项对变量的置换，使表达式达到一致的过程称为合一。项：由常量、变量和函数组成。表达式的例：在表达式中，用置换项置换变量后得到的特定表达式。例如：表达式P(x,f(y),B),用z置换x，用w置换y，得到一个置换例P(z,f(w),B)置换：用集合S={t1/v1,t2/v2,…tn/vn}表示任一置换其中：ti/vi为对vi的任何出现用ti代替置换要求：①某变量的每次出现均用同一个项来代替②变量不可用含有同一个变量的项代替（如：f(x)/x）用S对表达式E置换后的例记为：Es例：对P(x,f(y),B)用以下4个置换作用后得到的置换例如下：置换置换例S1={z/x,w/y}Es1=P(z,f(w),B)(1)S2={A/y}Es2=P(x,f(A),B)(2)S3={g(z)/x,A/y}Es3=P(g(z),f(A),B)(3)S4={C/x,A/y}Es4=P(C,f(A),B)(4)(1)式为原始文字的初等变式，它只是变量改名。(4)式基例，置换后的例中不含变量。合成置换：二个置换s1,s2的合成置换用s1s2表示。它是s2作用到s1的项，再附加上在s1的变量中未出现的那些s2的置换对所得到的置换例，记作：Es1s2例如：S1={g(x,y)/z},S2={A/x,B/y,C/w,D/z}合成