数理逻辑1.3.ppt

《数理逻辑1.3.ppt》由会员分享，可在线阅读，更多相关《数理逻辑1.3.ppt（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1.3命题公式间的逻辑等价关系命题公式间的逻辑等价关系 1.3.1基本概念1.3.2替换定理1.3.3代入定理1.3.4逻辑等价变换1.3.5联结词归约与范式1.3.1 基本概念 定定义义1设,是两个命题公式。如果对于与的合成变元组(即这两个公式所有不同命题变元合在一起)的任意指派，均有()=()则称与逻辑等价逻辑等价，也称永真等价或同真假。记为。判断两个命题公式逻辑等价的第一种方法是使用真值表。先将与的合成变元组的各种指派和与在各种指派下的真假值写在同一张表上，然后检验与的相应位置上的真值是否相同。例如，利用真值表即可验证命题公式PQ与命题公式P(PQ)逻辑等价。PP双重否定律PPP,PPP

2、幂等律(PQ)RP(QR)(PQ)RP(QR)结合律PQQP,PQQP交换律P(QR)(PQ)(PR)P(QR)(PQ)(PR)分配律(PQ)PQ(PQ)PQDeMorgan律PFP,PTP同一律PTT,PFF零律PPT,PPF否定律PQPQPQ(PQ)(QP)联结词归约基 本 逻 辑 等 价 式请用真值表验证各个逻辑等价公式研究两个命题公式之间逻辑等价关系的方法之二是利用命题公式的永真性。定理定理1设,为命题公式，当且仅当为永真公式。命题公式间的逻辑等价关系具有：1)自反性：；2)对称性：若，则；3)传递性：若且，则。应当指出的是，两个命题公式逻辑等价与两个命题公式相等是有所区别的。前者是指

3、结果相同，后者是指形式相同(当然结果必相同)。因此相等比逻辑等价的要求更高。以后仍用“”表示相等。1.3.2替换定理定定义义2设命题公式，是命题公式的一部分且是命题公式，则称是的子命题公式。定定义义3设是命题公式，若将的子命题公式用另一命题公式替换，则称替换后产生的命题公式是关于替换为的结果。利用替换，可以将原有的命题公式改造成新的命题公式。例如，命题公式P(P(PQ)关于P(PQ)替换为PQ的结果为P(PQ)。替换定理替换定理设是关于替换为的结果。如果，则。引理引理设1,2,1,2均为命题公式。若11,22,则1)112)12123)12124)12125)1212证：3）设1,2,1,2的

4、合成变元组为(P1,P2,Pn)。对于该合成变元组的任一指派，由条件11,22有1()=1()2()=2()于是有1()2()=1()2()由于(12)()=1()2()(12)()=1()2()于是有(12)()=(12)()由指派的任意性和逻辑等价的定义知有1212。替换定理替换定理设是关于替换为的结果。如果，则。证：对中除之外的联结词个数k进行归纳证明。当k=0时，为下述两种形式之一。1)=P(P是命题变元)，2)=对于1)根据的定义可知，此时=P。于是有=P，当然有。对于2)有=。设当kn时，结论成立。下证当k=n时，结论也成立。事实上，按照命题公式的定义可知，必呈下述形式之一。1,1

5、2,12,12,12仅以12为例进行证明。由于是关于替换为的结果，而且只是对中以外的联结词进行归纳，即12中的不是中的联结词。因此，必呈12的形式，其中1,2分别是1,2关于替换为的结果。又由于1,2中除之外的联结词的个数必然小于n。于是按照归纳假设可知，有1122再由引理知，有1212,即。1.3.3代入定理代入是通过已有的永真公式推出更多的永真公式的一种有效途径。例如，是否可由PP是永真公式而直接推断出PQPQ是永真公式。这就是代入定理所要回答的问题。定定义义4设为命题公式，P是中的命题变元，是任一命题公式。如果将中P的所有出现均用命题公式代替，则称代替后所得到的命题公式为关于P代入为的结

6、果，简称的代入实例，记为/P。例例=(P(PQ)Q，=PQ，代入P后则有/P=(PQ)(PQ)Q)Q 代代入入定定理理设为命题公式，P是中的命题变元。如果是永真公式，那么对任意命题公式，有/P为永真公式。证证令=/P。设的变元组为(P1,P2,Pn)，的变元组为(Q1,Q2,Qm)。于是的变元组应为(Q1,Q2,Qm,P1,P2,Pn)于是的变元组的任何指派=(Q10,Q20,Qm0,P10,P20,Pn0)必确定了的一个指派1=(Q10,Q20,Qm0)令P0=(1)，于是得到的一个完全指派2=(P0,P10,P20,Pn0)注意到是将中P的所有出现均用代替，于是有()=(2)而是永真公式，

7、于是有(2)=T，即有()=T。由指派的任意性和永真公式的定义知为永真公式。由于代入定理的引入，获得永真公式的手段就更加丰富了。由代入定理 知，每 一 个 永 真 公 式 都 是 一 族 永 真 公 式 的 代 表。例 如，由(P(PQ)Q是永真公式可推知所有形如()的命题公式均为永真公式。因此，每个永真公式中的命题变元都可以理解为子命题公式的形式。将代入定理运用于命题公式之间的逻辑等价，可以得到如下结论。推论推论设,是命题公式。若，则/P/P。证证由条件知，由定理1知是永真公式。根据代入定理有/P/P是永真公式。再由定理1知/P/P。利用这个推论，可将上节给出的基本逻辑等价式中的命题变元理解

8、为命题公式。例如，PQQP可理解为等等。1.3.4逻辑等价变换利用代入定理、替换定理和基本逻辑等价式，可以十分方便地进行命题公式间的逻辑等价变换。例例证明PQ(PQ)(PQ)1.3.5联结词归约和范式 1)异或联结词异或联结词异或联结词将成分命题P,Q组成新的命题“P或者Q之一成立”，即前面曾经提到的“不可兼或”。记为PQ，其中称为异或词。它们的真假值关系由表3确定。表3异或联结词之真值表从异或词的定义知PQ(PQ)(PQ)PQPQTTFTFTFTTFFF 2)与非联结词与非联结词与非联结词将成分命题P,Q组成新的命题“P且Q不成立”，记为PQ，其中称为与非词。它们的真假值关系由表4确定。表4

9、与非联结词之真值表由与非词的定义知PQ(PQ)PQPQTTFTFTFTTFFT 3)或非联结词或非联结词或非联结词将成分命题P,Q组成新的命题“P或者Q不成立”，记为PQ，其中称为或非词。它们的真假值关系由表5确定。表5或非联结词之真值表由或非词的定义知PQ(PQ)PQPQTTFTFFFTFFFT 定定义义5设P1,P2,Pn是n 个命题变元，f 是从T,Fn到T,F的对应关系。如果对于n 个命题变元的任一指派，通过f均有唯一的真假值与之对应，则称f 是n 元真值函数。例例 三元真值函数W的真值表 定义定义6若A是真值函数集合的子集，则称A是联结词集合。P1P2P3W(P1,P2,P3)TTT

10、FTTFFTFTFTFFTFTTFFTFFFFTFFFFT 定定义义7设A是联结词集合。若任一真值函数都可以用A中的联结词表示，则称A是全功能(功能完备)的。定理定理2联接词集合,是全功能的。证证对于任一n元真值函数f(P1,P2,Pn)，其所有的成真指派为|f()=T=1,2,m其中i=(P1i,P2i,Pni),i=1,2,3,m.对于每个i，通过下述方法给出相应的i其中于是对于每个i有,i()=T当且仅当=i。令=12m，于是有()=T当且仅当存在一个i，使得=i。于是有f()=T当且仅当()=T。即f(P1,P2,Pn)(P1,P2,Pn)而是仅含有,的命题公式，故,是全功能的。定定义

11、义8设A是全功能联结词集合。若A中的任一联结词不能用其它联结词来表示，则称A是极小全功能的。定理定理3下面的联结词集合都是极小全功能的。,定理定理4下述联结词集合是极小全功能的。,证证只证是全功能的。只要证明全功能联结词集,中的每个联结词可分别由表示。由于PPPPQ(PQ)(PQ)故是全功能的。由于中只有一个联结词，故是极小全功能的。由定理4可知，所有真值函数均可由一个联结词或来表示。这正是在数字逻辑电路中选择“与非门”或“或非门”作为基本逻辑器件的理论根据。但从另一个角度来看，单由或组成的命题公式不满足结合律。这给人们直接用或进行研究带来不便。定义定义9设是命题公式。如果具有下述形式=12n

12、其中诸i为命题变元或命题变元的否定或命题变元和命题变元的否定构成的合取式，则称为析取范式。例例(PQR)RQ是析取范式。定义定义10设是命题公式。如果具有下述形式=12n其中诸i为命题变元或命题变元的否定或命题变元和命题变元的否定构成的析取式，则称为合取范式。例例P(PQR)(QR)是合取范式。任何一个命题公式都可以通过下述步骤化为析取范式或合取范式。1)联结词归约：将命题公式中的所有联结词化归成仅含,的命题公式。2)否定词深入：利用deMorgan律将否定词移到每个命题变元之前。3)调整与：利用与的分配律、结合律等性质将命题公式化归成析取范式或合取范式。定义定义11设是n元命题公式。如果具有

13、下述形式=12n并且诸i具有形式其中为Pi或Pi，称为小项范式(主析取范式)，称i为小项。定义定义12设是n元命题公式。如果具有下述形式=12n并且诸i具有形式其中为Pi或Pi，称为大项范式(主合取范式)，称i为大项。例例 (PQR)(PQR)(PQR)是主析取范式。(PQR)(PQR)(PQR)是主合取范式。下面给出求一个命题公式的主析取范式的步骤(求主合取范式的步骤类似)。1)联结词归约：同前。2)否定词深入：同前。3)调整与：同前。4)消除永假项：若某个i中同时含有同一命题变元及其否定，则将此i去掉。5)变元合并：若某个i中含有两个以上同名的命题变元，则只保留一个。6)补足变元：若某个命

14、题变元P在i中没有出现，则用i(PP)替换i，然后用分配律展开。7)合并相同项：若i与j相同，则只保留i。例例 求(PQ)(PR)的主析取范式。引理引理设是含有n个命题变元P1,P2,Pn的小项，即=(P10,P20,Pn0)是的任一指派。则()=T当且仅当 定理定理5主析取范式或主合取范式是唯一的。证证只证主析取范式的唯一性。设是n元命题公式，的成真指派分别为1,2,m根据引理，由这些成真指派可分别确定出相应的小项1,2,m由它们之间的一一对应关系可知，的主析取范式为12m当然，这里的唯一性并不保证各小项及各命题变元的位置的唯一性。而命题变元的位置可以事先约定。根据上面的讨论，不难得出这样的结论：两个命题公式逻辑等价必须且只须它们相应的主范式相同。当然，如果两个命题公式的主范式相同时，这两个命题公式必然逻辑等价。