我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿玄机1站开奘结果 > 前束范式 >

一种求解前束析(合)取范式简单方法pdf

归档日期:07-27       文本归类:前束范式      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  CN43—1258/TP 计算机工程与科学 2008年第30卷第10期 V01.30,No.10,2008 贼1007—130X COMPUTERENGINEERING&SCIENCE 文章编号:1007—130X(2008)10-0082—03 范式的简单方法。 一种求解前束析(合)取 A Methodfor rene:: Simple SolvinggmvlobxenerP Forms unction)Normal Disjunction(Conj 潘美芹.丁志军 PAN Mei-qin,DINGZhi-jIill (山东科技大学信息科学与工程学院.山东青岛266510) ofInformationScienceand ofScienceand (School University Technology,Qingdao266510,China) Engineering-Shandong 摘要:本文提出了一种由前束析(合)取范式求前束舍(析)取范式的简单方法。该方法根据谓词逻辑自身的特点,结 合命题逻辑中命题公式的主析取范式和主合取范式的互补关系,将前柬析(合)取范式转化为主析(合)取范式,再得出相应 的主合(析)取范式,最后准确地得出前束合(析)取范式。 is Abstract:This a methodfor forms,which paperproposessimple solvingprenexdisjunction(conjunction)normal basedonthe characteristicsandthe relationsofthe normalform predicatelogic’s mutual-complementarymajordisjunction andthe normalform.It the formintothe changes disjunction(toniunction)normalmajordisjune- majorconjunction prenex then the the form,andgetsmajorconjunction(disjunction)normalform,andfinallygets tion(conjunction)normal prenex form. eonj’unction(disjunction)normal 关键词:数理逻辑;谓词逻辑;范式;前束范式 form normal Keywords:propositionallogic;predicatelogic;normalform;prenex 中图分类号:0158 文献标识码:A 1 引言 2主析取范式和主合取范式 离散数学是随着计算机的发展而逐渐完善起来的一门 在命题逻辑中。同一命题公式有各种相互等价的表达 新兴学科,它是计算机专业的-tl重要基础课。学生对这门 形式。为了规范命题公式,故有范式的概念,而范式又分为 课程对掌握的好坏,直接影响到后继专业课程的学习以及将 析取范式和合取范式。对于任何一命题公式,都存在与其 来在专业上的发展。由于离散数学和传统数学在基本思想 等价的析取范式和合取范式。然而,命题公式的合取范式 和方法上有很大差别,学生在学习这门课程时普遍存在很多 和析取范式是不唯一的。为进一步规范化命题公式,引进 困难。在我们所选的教材中(绝大部分教材都如此),数理逻 了主析取范式和主合取范式。主析取范式是由小项的析取 辑安排在第一篇,它的概念很抽象,逻辑性强,而其中的谓词 构成,主合取范式是由大项的合取构成,从小项和大项的定 逻辑更是难点。由于谓词逻辑中的前柬范式中通常有多个 义可知,主析取范式和主合取范式有着“互补”关系。见例 量词,而且量词的作用域中又涉及多个命题函数,学生做前 AR)的真值表如表l所示,公式 1,公式(P^Q)V(一P 束析取范式和前束合取范式的练习时往往无从下手,并且稍 含三个命题变元,故真值表中有八种指派,表中画线对应的 有不慎就会得出错误的结果。事实上,根据渭词逻辑自身的 是主合取范式的四个大项,其余部分对应的是主析取范式 特点,结合命题逻辑中命题公式的主析取范式和主合取范式 的四个小项。根据这个特点,当用公式化归法求解出某一 的互补关系,在求出前束析取范式时,遵循我们的简单方法, 公式的主析取范式时,利用互补性,马上可得到其主合取范 会准确地得出前束合取范式,反之亦然。 式,反之亦然。 万方数据 (析)取式中必含所有的命题函数,为方便起见,我们称这样 例1求(P^Q)V(一P^R)的主析取范式和主合 取范式。 的前束析(合)取范式为前束主析(合)取范式。 解方法1:线一个谓词公式如果具有如下形式,则称为前 画出(P^Q)V(一7P^R)的线所示。束主析取范式: 表1真值表 P Q R甘P^Q——-P^R(P^9V(—,^尺) V(A.1^…^Ad,)) T T T F T F T 其中,口可能为V或j,研是客体变元,山是原子谓词公 T T F F T F T 式或其否定,而且在合取项(An^…^A:)中,所有原子 T F T F F F F 谓词公式或其否定出现一次且仅出现一次。 T F F F F F F 定义2一个谓词公式如果具有如下形式,则称为前 F T T T F T T F T F T F F F 束主合取范式: F F T T F T T (口01)^(口耽)…(口%)((A11V…VA1^)^… F F F T F F F ^(A。lV…VAo,)) 其中,口可能为V或了,让是客体变元,A是原子谓词公 表中使(P^Q)V(一P^R)的真值为T的指派所对 式或其否定。而且,在析取项(A-V…V山:)中,所有原 应的小项的析取即为此公式的主析取范式,使(P^Q)V 子谓词公式或其否定出现一次且仅出现一次。 (一7P^R)的真值为F的指派所对应的大项的合取,即为 任意一个谓词公式均和一个前束析(合)取范式。而前 此公式的主合取范式。故此公式的主析取范式为: 束主析(合)取范式只是在前束析(合)取范式基础上对所缺 (P^Q)V(—-7P^R){号(P^Q^R)V(P^Q^ 的某原子谓词公式进行补项后,按分配律和结合律化归为 —,R)V(—,P^Q^R)V(—,P^—,Q^R) 前束主析(合)取范式。在化归过程中都保持等价性质,故 其主合取范式为: 任意一个谓词公式,均和一个前束主析(合)取范式。 (P^Q)V(_7P^R)铮(_7PVQ V V_7R)^(一P 求前束主析(合)取范式的步骤如下: V V R) Q R)^(PV—-7QR)^(PVQV Stepl求出公式的前束范式; 方法2:公式化归方法。 Step2利用分配律、结合律将公式化归为析(合)取范式; 由(P^Q)V(一P^R)易得主析取范式: Step3对各析(合)取范式进行原子谓词公式的补人, Stel)4利用分配律、结合律将公式化归为前束主析(合)取范 (P^Q)V(—_7P^R){=》((P^Q^(RV—,R))V 式. (_7P^(Q V—Q)^R)骨(P^Q^R)V(P^Q^ 结合命题逻辑中主析取范式和主合取范式的“互补”关 -7R)V(_7P^Q^R)V(.7P^-7Q^R) 系,我们可得到如下结论:前束主析(合)取范式中的作用域 再由互补性得主合取范式: 与前束(合)析取范式的作用域也有“互补”关系。 (P^Q)V(—-7P^R)々号(P^Q^R)V(P^Q^ 所以,当我们求出公式的前束主析(合)取范式时,将前 —,R)V(—,P^Q^R)V(—,P^—,Q^R) 柬主析(合)取范式的命题函数记成相应的命题变元,从而 得到主析(合)取范式,利用主析取范式和主合取范式的“互 3前束析取范式和前束合取范式 补”关系,得到对应的主合(析)取范式,再将主合(析)取范 式中命题变元换为原来的命题函数,从而得到前束主合 在谓词逻辑中,谓词公式的规范形式称为前束范式。 (析)取范式,也是前束合(析)取范式。 前束范式有前束析取范式和前束合取范式之分。由于谓词 例2求下列公式的前束析取范式和前束合取范式。 公式中含有命题函数,元法对其进行赋值,故无法用线)(Vz)(P(z) 一 (Vy)((Vz)Q(x,y)一 方法求解其前束范式,而只能采用公式化归法求解。当求 一(Vz)R(y,z))) 解某谓词公式的前束析取范式和前束合取范式时,先将公 解 (V动(P(z)(Vy)((Vz)Q&,y) 一 一 式化归为前束范式,再利用分配律、结合律,将其化归为前 束析(合)取范式。 —,R(y,z)))∞(Vz)(—,P(z)V V (Vy)(—,Q(z,y) 由于前束范式中往往有多个量词,而且量词的作用域 V _7R(y,o))铮(Vo(Vy)(一P(z)—Q(z,y)V 中又涉及多个命题函数,当由前束析(合)取范式化归为前 —rR(y,z)) 束合(析)取范式时,稍有不慎就会得出错误的结果。事实 故前束合取范式为: 上,根据谓词逻辑是命题逻辑的推广的特点,结合命题逻辑 的主析取范式和主合取范式的互补关系,求出谓词公式的 该前束合取范式中为前束主合取范式。前束主合取范 前束析(合)取范式时,就会准确地得出相应的前束合(析)式的作用域对应的命题公式为(一7PV-7QV.7R),该公 取范式。即将前束析取范式中的命题函数记成对应的命题 式为主合取范式,由互补性得其主析取范式: 变元,从而得到主析取范式;利用主析取范式和主合取范式 的“互补”关系,得到对应的主合取范式;再将主合取范式中 命题变元换为原来的命题函数,从而得到前束合取范式。 Q^—-7R)V(—,P^—,Q^R) 但是,要求在该前束析(合)取范式中量词作用域的各合 故对应的前束主析取范式,也为前束析取范式: 83 万方数据 (Vz)(V少((一P(z)^-,Q(z,少A1R(y,力)V 范式转化为主析(合)取范式,再得出相应得主合(析)取范 (P(z)AQ(x,y)A—,R(y,z))V 式,最后准确地得出前束合(析)取范式。 (P(工)A—,Q(z,y)A R(y,工))V 参考文献: (P(工)A—,Q(z,y)A,R(y,工))V (—,P(工)^Q(上,y)A I-O吴顺唐.离散数学[M].上海:华东师范大学出版社,1999. R(y,z))V (,P(x)A [2]左孝凌,等.离散数学[M].上海:上海科学技术文献出版社, Q(z,y)A,R(y,z))V 1998. (—,尸(z)A—,Q(z,少A R(y,z))) [33左孝凌,等.离散数学习题集FM].上海:上海科学技术文献 (2)(V工)((Vy)P(z)V(Vz)Q(z,y)—.—,(Vy)R(x, 出版社,1998. y)) [4]耿索云,屈婉玲,张立昂.离散数学[M].北京:清华大学出版 解 社,1999. (V工)((V 3,)P(z)V(Vz)Q(z,y)一一(Vy)R(x, [5]王元元,张桂芸.计算机科学中的离散结构[M].北京:机械 y)) 工业出版社,2004. 甘(Vz)(P(z) V (Vz)Q(z,3,)—,—,(Vy)R(x,y)) H.RosenDiscreteMathematicsandIts [6]Kenneth Applications 甘(Vz)(_7(P(功V(Vz)Q(z,少)V--7(Vy)R(x,y)) [M].4thEdition.北京:机械工业出版社,2001. R Mathematical 甘(V工)(—,P(工)^(了z)--,Q(z,y))V(jy)—,R(z,y))KolmanB,BusbyC,Ross&Discrete [7] Edition.北京:高等教育出版社,2001. 甘(Vz)(_7P(曲A(j力棚(z,少)V(jYl)蝴Q,M))Structures[M].4th {与(V曲(j [8]AndrewSimpon.离散数学导学[M].冯速译.北京:机械工 z)(—,P(z)^—,Q(z,y))V(j砷)—,R(z,北)) 业出版社,2005. 甘(V力(jz)(jM)((_7P(z)^一Q(2,y))V—尔(工, y1))) 铮(Vo(3 (上接第81页) z)(3Y1)((一P(z)V_7R(z,了1))^ 得: (-7Q(z,y)V-7R(士,M))) 甘(Vo(jz)(3M)((一P(西V(川(z,y)AQ(z,必)V 丑 墨 1 现 =0 —,R(z,y1))A((—,P(工)AP(z))V—,Q(z,y)V = 抓(工,y1))) 而 0或1 ,●●●,●●,、●●●●●L 丑 =0 甘(V力(了力(jyl)((—PC力V—gz,力V—Ro,M))^ (—,P(z)V 第四步:分析。 Q(z,y)V—,R(z,肋))^ (一P(工)V—Q(z,了)V-7R(z,Y1))A从方程组的解中可知,-2:2的值是为0。因此,可以推出 (P(工)V—-7Q(z,y)V—。,R(z,y1))) 结论]q的线。 口 甘(Vz)(j力(jM)((_7P(曲V—Q(z,力V—7R(z,M))^ (—,P(工)V 7结束语 Q(z,y)V—,R(z,y1))^ (P(z)V—,Q(=,少V_7尺(z,y1))) 即前束合取范式的作用域的公式为: 本文尝试利用纯代数的方式,通过解多项式方程组对 V-7Q VQV_7R)^ 命题逻辑进行演算、推理。这有别于通过语法、语义分析实 (一P V.7R)^(一P (PV—QV—rR) 现命题公式代数化。 该公式为主合取范式,由互补性得其主析取范式为: 参考文献: (-7P^.7Q^—R)V(一P^一Q^R)V(一7P^ [1]王元元.计算机科学中的离散结构[M].北京:机械工业出版 Q^—rR)V(PA_7Q^—R)V(P^Q^—冀) 社,2006. 故对应的前束析取范式为: [2]吴尽晗.多值逻辑定理及其证明的代数方法口].计算机学 (V曲(了力(3M)(卜7P(oV川&,少V,Ro,M))A 报,1990. R(x,y1))A (一P(z)V—Q(z,y)V [3]吴尽晗.一阶谓词演算定理及其证明的余式方法[J].计算机 (—-7P(z)V Q(z,y)V—,R(z,y1)))A 学报,1990. (P(z)V—,Q(z,y)V—,尺(z,y1))^ tO D,NarendranP.AnEquational Theorem [4]Kapur Approach (P(工)VQ(z,y)V—·尺(z,姐)) inFirst-OrderPredicate ofthe Proving Calculus[C]//Proc 10thInt’1 ConfOnArtificial loint 4结束语 1153. [5]王捍贫.数理逻辑(离散数学第一分册)[M].北京:北京大学 谓词逻辑中的前束范式中通常有多个量词,而且量词 出版社,1997. 的作用域中又涉及多个命题函数,故求前束析取范式和前 [6]李晶,杨宗源.吴方法在命题逻辑中的应用[刀.华东师范大 学学报(自然科学版),2006(1):80-86. 束合取范式的练习时稍有不慎就会出错。本文提出了一种 由前束析(合)取范式求前束合(析)取范式的简单方法。该 方法根据谓词逻辑自身的特点,结合命题逻辑中命题公式 的主析取范式和主合取范式的互补关系,将前束析(合)取 84 万方数据

本文链接:http://scrinzoom.com/qianshufanshi/703.html