1-7对偶与范式.ppt

1、第一章命题逻辑17对偶和范式，要求：掌握对偶和范式(均针对有限公式)，可以找到命题公式的主分析范式和主合范式。重点和难点：求出命题公式的注释范式和主合范式。复习命题的规律。表1-4.8(都是限制公式)，1-7对偶和范式1，对偶存在这种公式和对偶。上表成对出现的规律是对偶的反映，即对偶的。利用对偶形式的命题法则，可以扩大等价数量，减少证明次数。限制公式：万，的命题公式，1，对偶的定义：在给定命题公式(限制公式)中，连接词为，为，为，为，特殊参数F和T徐璐替换的话，结果公式A*称为A的双重式(dual)。(PQ)R(A)(PQ)T(B)(PQ)(P(QS)(C)，解析：这些表示式的双工为(a) (

2、PQ) r(相同PQ的，示例3设置A*(S，W，R)是证明A*(S，W，R) A(S，W，R) A(S，W，R)A(S，W，R)的S (W R)，因此A命题引数否定的公式表明，等于对偶式的否定。2，原态和对偶的关系，证明：德摩根定律：(PQ)PQ，(PQ)PQ，以及TF，FT，表示应用(或)原子命题，将其转化为否定。Qi=Pi，pi=qi (I=1，2，n)。所以：A(Q1，Q2，Q n) A*(Q1，Q2，Q n)。即A(Q1，Q2，Q n) A*(Q1，Q2，Q n)。移植都得到证明。定理1-7-2:设置P1，P2，Pn是公式A和B中出现的所有原子参数，如果A B，则为A * B *。证明

3、：P1，P2，P N是出现在A，B中的所有原子参数。A B是A(P1，P2，P n) B(P1，P2，P n)，因此A(P1，P2，P n) B(P1，P2，因此，A(P1，P2，P n)B(P1，P2，P n)也是中性的，因此A(P1，P2，P n)B(P1，P2，P清理1-)，注：将等价性改为隐含会产生什么结果？等价性，赋值规则，替代规则，双重定理可以得到更多的零进制，可以证明更多的等价性，简化简单的命题公式更方便。2，范式(因为每个公式的等价表达式太多，所以需要规范)(1)一般范式(不是唯一的)1，合取范式，定义1-7-2:命题公式被称为合取范式.在An (n1)中，A1、A2例如，公式

4、P、Q、PQ、PQP等都是简单联集式，而P、Q、P是对应的简单联集式的联集。公式P、Q、PQ、PQP等都是简单提取表达式，而P、Q、P是相应简单提取表达式的分离项。命题自变量或否定可以是简单的联合表达式，也可以是简单的分离表达式(例如P、Q等)。，3，一般范式的句法，无论是什么命题公式，求其合法范式或提取范式，都将(1)公式中的连接词加在一起，(2)利用(P)P和dr-mor gan方法将否定符号直接放在每个命题参数前面。(3)利用分配法、结合法将公式归入合取范式或提取范式。示例3查找(P(QR)S的联合范例。解决方案：示例4球面(PQ)(PQ)的提取范式。解决方案：4。范式的应用可以利用提取

5、范式和合取范式来判定公式。*定理1.6.4公式A为永久公式的填充条件是，A的提取范式中的每个简单求和包含一个或多个命题自变量和否定。*定理1.6.5公式A为零进制的填充条件是，A的合法范式中的每个简单提取表达式包含一个或多个命题自变量和否定。(b)主要范式(唯一)，范式基本上解决了公式的判定问题。但是由于范式不唯一，认识公式之间的对等存在困难，公式的主要范式解决了这个问题。下面将分别讨论主范式中的主分离范式和主合并范式。1，主要提取范式(1)小项目的定义，1-7-4: n个命题参数的联合式定义，称为布尔并集或小项目或小项目。每个参数和否定不能同时存在，但两者必须同时出现，并且只能出现一次。例如

6、，两个命题参数P和Q是构成PQ，PQ，PQ，PQ，PQ，PQ的小项目。三个命题参数P、Q、R是由PQR、PQR、PQR、PQR、PQR、PQR、PQR、PQR、PQR、PQR和PQR组成的小项目。可以证明n个命题引数共形成2n个小项目。(2)小项目的编码，小项目分配与true值相对应的二进制数(只有一个真值，因为编码必须唯一)。如果按字母顺序排序命题参数，将命题参数对应于1，将命题参数的否定对应于0，那么将2n个小项目编码为二进制数，这样通过这种编码得到的2n个小项目的真值表可以明显地反映小项目的性质。表1.7.1和表1.7.2分别给出了两个命题参数P和Q，三个命题参数P，Q，R的小项真值表。

7、(0)两个小项目不相等。也就是说，每个小项目的真值表都不同。(1)如果实际值与编码相同，则每个小项目为t；在剩馀的2n-1分配中，则为f。(2)两个不同小项目的合取(很可能是假的)式休假。mm J F(IJ)(3)对整个小项的提取(真相的可能性很大)表达式永远真实，(3)小项的性质(可通过真值表获得)，(4)主提取范式的定义，对给定命题公式，(5)主提取，所以a B .证明：将给定的公式设置为A，真值为T的分配对应的小项为m1，m2，MK，这些小项的提取表达式写为B。要证明A B，只要A和B在该分配中具有相同的真值，只要A和B具有相同的真值。首先，在A为T的分配中，如果相应的小项目是mi，mi

8、包含在B中，则B为T，因为m1、m2、mi-1mi 1、MK都是F。第二，与A为F的分配相对应的小项目不包含在B中。也就是说，m1、m2、MK是F，因此B是F。范例6寻找公式P Q、P Q和(P Q)的主要萃取范例。解三个公式的真值表如下。因此，p q (p q) (p q) (p q)、p q (p q) (p q)、(p q)(p q)(p q)(p q)(p q，公式A的主要提取样例如下a(P Q R)(P Q R)(P Q R)(P Q R)，b .等效公式发布法和基本等效公式发布法的估计步骤概括如下：(1)分类为提取范式。(2)从提取范式中删除所有永久性假提取项(3)从分离表达式中重

9、复的联合表达式等参数组合(4)添加不出现在联合式补充中的命题参数，即(PP)表达式，然后应用分配法展开公式，(P F P)，(pqr)(pqr)(pr Q)(pr Q)(QR P)(QR P)，(pqr) (pqr) (pq r) (p q r)，例如，2，主要统一范式(1)大项的定义，1-7，6: n定义命题自变量的分离式，布尔提取或大项。每个参数和否定不能同时存在，但两者必须同时出现，并且只出现一次。例如，由两个命题参数P和Q组成的大项目是PQ，PQ，PQ，PQ，PQ，PQ。三个命题参数P、Q和R构成PQR、PQR、PQR、PQR、PQR、PQR、PQR、PQR、PQR和PQR。n个命题的

10、自变量都可以证明是2n个大项。(2)大项的编码，使大项分配与假真值相对应的二进制数。n=2 M00=PQ，M01=PQ M10=PQ，M11=PQ n=3 M000=PQ R，m100=M110=PQ R M011=PQ R，M111=下标I是用二进制数数字化的十进制数，这种代码要求的2n个大项目的真值表可以直接反映大项目的性质。表1.7.3给出了构成两个命题参数P和所有大项目的真值表。(0)两个大项目不相等。(1)如果实际值与编码相同，则每个大项目的值为F，在其馀2n-1分配中，每个大项目的值为T。(2)两个不同大项目的分离式是零进。Mi Mj T (ij) (3)整个对抗的联合式总是假的，

11、(3)对抗的性质，(4)对联合式的定义，对于给定命题公式，如果有仅由对抗的联合式组成的等加工式，则该等加式称为原式，(5)主联合式范式的句法例10利用真值表技术寻找(P Q) (P R)的主合范式和主提取范式。求解公式(P Q) (P R)的参与值表如下：(P Q)(P Q)(P R)(P Q R)(P Q R)(P Q R)(P QR)(P QR)主提取样例是(P Q)(2)从并集样例中删除所有用于永久合并的内容b .等加工式引入法，(，(p q r) (p q r) (p q r)，(p q r)，(q p r) (q p r) (p r q) (p r q) (q r p通过主分析范式和

12、主分析范式之间的关系，可以看出，从A的主分析范式中求其主分析范式的阶段是求不在(A) A的主分析范式中的小项目的阶段。(b) (a)查找与中小项目下标相同的大项目。(c) (b)合并重大项目是A的合并范式。例如，(PQ) QM1M3=1，3，(PQ) QM0M2=0，2，(1)评价问题也可以根据主范式的定义和定理包含N个命题。根据以下条件，如果： (a) A或A可以变成具有相应2n个小项目的主提取范式，则A是零真。(b)如果a或a可以变成包含相应的2n个大项的联合范式，则a是永久表达式。(c)如果A不相等或不相等，不包含2n个小项目或大项目，则A可以满足。主范式的应用，可以利用主范式解决判定问题，也可以证明等价形式的成立。(2)等价式成立证明：因为某个公式的主范式是唯一的，所以在给定的公式中求那个主范式，如果主范式相同，给定的两个公式是相等的。(还有其他应用问题的解决)，另外，1，一个公式是零真(零假)式的充电条件，它的主分析(和)范式包含所有小(大)项目，主和(分析)范式是空公式。2，