数理逻辑命题逻辑幻灯片.ppt

《数理逻辑命题逻辑幻灯片.ppt》由会员分享，可在线阅读，更多相关《数理逻辑命题逻辑幻灯片.ppt（55页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数理逻辑命题逻辑第1页，共55页，编辑于2022年，星期六 引言引言q 给定一个命题公式，如何判断它的类型给定一个命题公式，如何判断它的类型是重言式、矛是重言式、矛盾式、还是可满足式？盾式、还是可满足式？q 目前已经给出了两种方法，即目前已经给出了两种方法，即真值表法真值表法和和逻辑等价逻辑等价演算法演算法。q 还有第三种方法，这就是把命题公式化成一种统一的、还有第三种方法，这就是把命题公式化成一种统一的、标准的公式标准的公式范式范式。2第2页，共55页，编辑于2022年，星期六给定命题变元给定命题变元p,qp,q，则则p，q，p，q，pq，p q，pq，pq等都是简单析取式，而等都是简单析取

2、式，而p，q，p，q，pq，p q，pq，pq 都都等都是简单合取式。等都是简单合取式。1.1.简单析取式和简单合取式简单析取式和简单合取式定义定义 仅由有限个命题变元或其否定构成的析取式称为仅由有限个命题变元或其否定构成的析取式称为简简单析取式单析取式。仅由有限个命题变元或其否定构成的合取式称。仅由有限个命题变元或其否定构成的合取式称为为简单合取式简单合取式。3第3页，共55页，编辑于2022年，星期六2.2.析取范式和合取范式析取范式和合取范式定定义义(1)(1)仅仅由有限个由有限个简单简单合取式合取式构成的构成的析取式析取式称称为为析取范式析取范式；(2)(2)仅由有限个仅由有限个简单析

3、取式简单析取式构成的构成的合取式合取式称为称为合取合取范式范式。u显然任何析取范式的对偶式为合取范式；任何合取范式显然任何析取范式的对偶式为合取范式；任何合取范式的对偶式为析取范式。的对偶式为析取范式。4第4页，共55页，编辑于2022年，星期六例如例如：A=(pqr)(pq)(pq)则则A为析取范式。为析取范式。A的对偶式为：的对偶式为：A*=(pqr)(pq)(pq)显然，显然，A*为合取范式。为合取范式。u对任何给定的命题公式，都能求出与之等价的析取对任何给定的命题公式，都能求出与之等价的析取范式与合取范式。范式与合取范式。5第5页，共55页，编辑于2022年，星期六定理定理(范式存在定

4、理范式存在定理)任一命题公式都存在着与之等任一命题公式都存在着与之等价的析取范式和合取范式。价的析取范式和合取范式。下述分析给出了任何命题公式范式存在性的证明，这证明下述分析给出了任何命题公式范式存在性的证明，这证明同时也是求其范式的同时也是求其范式的具体步骤具体步骤，即，即(1).消去对消去对、来说冗余的联结词。来说冗余的联结词。即用基本的逻辑恒等式及置换规则将即用基本的逻辑恒等式及置换规则将、联结词消联结词消去，所用的逻辑恒等式是去，所用的逻辑恒等式是pq pqpq(pq)(pq)6第6页，共55页，编辑于2022年，星期六(2).否定号消去或内移否定号消去或内移若遇有若遇有p或或(pq)

5、，(pq)等形式，利用双重否等形式，利用双重否定律和德定律和德.摩根律可将否定号消去或内移，即摩根律可将否定号消去或内移，即pp；(pq)pq；(pq)pq。7第7页，共55页，编辑于2022年，星期六(3).利用分配律利用分配律若是求析取范式，应该利用若是求析取范式，应该利用“”对对“”的分配的分配律；若是求合取范式，应该利用律；若是求合取范式，应该利用“”对对“”的分的分配律。配律。任给一个命题公式任给一个命题公式A，经过以上三步演算，可得到一，经过以上三步演算，可得到一个与个与A逻辑等价的析取范式或合取范式。逻辑等价的析取范式或合取范式。u值得注意的是，值得注意的是，任何命题公式的析取范

6、式和合取范任何命题公式的析取范式和合取范式都不是唯一的，我们把其中运算符最少的称为式都不是唯一的，我们把其中运算符最少的称为最简最简析取析取(合取合取)范式范式。8第8页，共55页，编辑于2022年，星期六例例1求下面命题公式的合取范式和析取范式。求下面命题公式的合取范式和析取范式。解解(1)(1)求合取范式求合取范式 至此，求出了原公式的合取范式。但上式可再化简，得但上式可再化简，得：(pq)(rp)，该式也是原公式的合取范式（最简），这说该式也是原公式的合取范式（最简），这说明与某个命题公式等价的合取范式是不唯一的。明与某个命题公式等价的合取范式是不唯一的。9第9页，共55页，编辑于202

7、2年，星期六(2)(2)求析取范式求析取范式 最后结果为原公式的析取范式，利用交换律和吸收律最后结果为原公式的析取范式，利用交换律和吸收律得得 ，也是原公式的析取范式，由此可见，也是原公式的析取范式，由此可见，与命题公式等值的析取范式也是不唯一的。与命题公式等值的析取范式也是不唯一的。10第10页，共55页，编辑于2022年，星期六例例2求求P(PQ)的最简析取范式。的最简析取范式。解：解：P(PQ)P(PQ)PPPQ0PQPQ11第11页，共55页，编辑于2022年，星期六3.极小项与主析取范式极小项与主析取范式定义定义在含在含n个命题变元的简单合取式中，若每个命个命题变元的简单合取式中，若

8、每个命题变元与其否定不同时存在，而二者之一题变元与其否定不同时存在，而二者之一必出现且仅必出现且仅出现一次出现一次，且第，且第i个命题变元或其否定出现在从左起的个命题变元或其否定出现在从左起的第第i位上位上(若命题变元无下标，则按字典顺序若命题变元无下标，则按字典顺序)，这样的，这样的简单合取式称为简单合取式称为极小项极小项。显然，n个变元可构成2n个不同的极小项。12第12页，共55页，编辑于2022年，星期六例如，3个命题变元可形成8个极小项。PQR PQR PQ R PQR PQR PQR PQ R PQR13第13页，共55页，编辑于2022年，星期六u 如果将命题变元看成1，命题变元

9、的否定看成0，则每个极小项对应一个二进制数，因而也对应一个十进制数。14第14页，共55页，编辑于2022年，星期六3个命题变元构成的8个极小项对应情况如下：PQR0000 PQR 0011 PQ R 0102 PQR 0113 PQR 1004 PQR 1015 PQ R 1106 PQR 1117极小项 二进制 十进制15第15页，共55页，编辑于2022年，星期六可用对应的十进制数作下标，用可用对应的十进制数作下标，用m mi i表示这一项表示这一项,即：即：PQR0000m0 PQR 0011m1 PQ R 0102m2 PQR 0113m3 PQR 1004m4 PQR 1015m5

10、 PQ R 1106m6 PQR 1117m7 极小项 二进制 十进制 mi表示16第16页，共55页，编辑于2022年，星期六一般地一般地,n个变元的极小项是个变元的极小项是:m0P1P2P3Pnm1 P1P2P3Pnm2n-1P1P2P3Pn17第17页，共55页，编辑于2022年，星期六极小项有以下3个性质：(1)(1)在极小项中，将命题变元记为在极小项中，将命题变元记为1 1，命题变元的否定记，命题变元的否定记为为0 0，则每个极小项对应一个二进制数。则该，则每个极小项对应一个二进制数。则该二进制数二进制数是是该极小项唯一的该极小项唯一的成真赋值成真赋值。18第18页，共55页，编辑于

11、2022年，星期六极小项有以下3个性质：(1)(1)在极小项中，将命题变元记为在极小项中，将命题变元记为1 1，命题变元的否定记为，命题变元的否定记为0 0，则每个极小项对应一个二进制数。则该，则每个极小项对应一个二进制数。则该二进制数二进制数是该极是该极小项唯一的小项唯一的成真赋值成真赋值。(2)(2)任意两个不同的任意两个不同的极小项的合取式极小项的合取式的值永假。例如，的值永假。例如，19第19页，共55页，编辑于2022年，星期六极小项有以下3个性质：(1)(1)在极小项中，将命题变元记为在极小项中，将命题变元记为1 1，命题变元的否定，命题变元的否定记为记为0 0，则每个极小项对应一

12、个二进制数。则该，则每个极小项对应一个二进制数。则该二进制二进制数数是该极小项唯一的是该极小项唯一的成真赋值成真赋值。(2)(2)任意两个不同的任意两个不同的极小项的合取式极小项的合取式的值永假。例如，的值永假。例如，(3)(3)全体全体极小项的析取式极小项的析取式的值永真，即的值永真，即20第20页，共55页，编辑于2022年，星期六定义定义 设命题公式设命题公式A中含中含n个命题变元，如果个命题变元，如果A的析取范式的析取范式中的中的简单合取式全是极小项简单合取式全是极小项，则称该析取范式为，则称该析取范式为A的的主析主析取范式取范式。定理定理 任何命题公式的主析取范式都是存在的，并且是唯

13、任何命题公式的主析取范式都是存在的，并且是唯一的。一的。这是因为任何一个命题公式都可求得它的这是因为任何一个命题公式都可求得它的析取范式析取范式（范式（范式存在定理），而存在定理），而析取范式可化为主析取范式析取范式可化为主析取范式。21第21页，共55页，编辑于2022年，星期六求给定命题公式求给定命题公式A的主析取范式的步骤如下：的主析取范式的步骤如下：1.求求A的最简析取范式的最简析取范式A；22第22页，共55页，编辑于2022年，星期六求给定命题公式求给定命题公式A的主析取范式的步骤如下：的主析取范式的步骤如下：1.求求A的最简析取范式的最简析取范式A；2.若若A的某简单合取式的某简

14、单合取式B中不含命题变元中不含命题变元pi 或其否或其否定定pi，则将，则将B展成如下形式：展成如下形式：23第23页，共55页，编辑于2022年，星期六求给定命题公式求给定命题公式A的主析取范式的步骤如下：的主析取范式的步骤如下：1.求求A的最简析取范式的最简析取范式A；2.若若A的某简单合取式的某简单合取式B中不含命题变元中不含命题变元pi 或其否或其否定定pi，则将，则将B展成如下形式：展成如下形式：3.将重复出现的命题变元、矛盾式及重复出现的极将重复出现的命题变元、矛盾式及重复出现的极小项都小项都“消去消去”。即将。即将pppp用用p p代替，代替，pppp用用0代替、代替、mimi用

15、用 mi代替。代替。24第24页，共55页，编辑于2022年，星期六求给定命题公式求给定命题公式A的主析取范式的步骤如下：的主析取范式的步骤如下：1.求求A的最简析取范式的最简析取范式A；2.若若A的某简单合取式的某简单合取式B中不含命题变元中不含命题变元pi 或其否或其否定定pi，则将，则将B展成如下形式：展成如下形式：3.将重复出现的命题变元、矛盾式及重复出现的极小项将重复出现的命题变元、矛盾式及重复出现的极小项都都“消去消去”。即将。即将pppp用用p p代替，代替，pppp用用0代替、代替、mimi用用 mi代替。代替。4.将极小项按由小到大的顺序排列，并用将极小项按由小到大的顺序排列

16、，并用表示之，表示之，如如m1m2m5用用 表示。表示。25第25页，共55页，编辑于2022年，星期六例例1 1 求命题公式求命题公式 的主析取范式的主析取范式解解 先求地原公式的析取范式为：先求地原公式的析取范式为：p(qr)p(qr)含两个简单合取式含两个简单合取式p p和和(qr)(qr)。在在p p中无中无q q或或qq，r r或或rr出现，因而应该用出现，因而应该用p(qq)(rr)p(qq)(rr)取代。取代。在在(qr)(qr)中无中无p p 或或p p，因而应该用，因而应该用(pp)(qr)(pp)(qr)取代，然后展开得极小项。取代，然后展开得极小项。于是有：于是有：26第

17、26页，共55页，编辑于2022年，星期六(析取范式析取范式)27第27页，共55页，编辑于2022年，星期六由由极小项定义可知，上式中，由由极小项定义可知，上式中，2，4，5，6，7的二进制表示的二进制表示010，100，101，110，111为原公式的为原公式的成真赋值成真赋值，而此公式的主析取，而此公式的主析取范式中没出现的极小项范式中没出现的极小项m0、m1、m3 的下标为的下标为0、1、3，则对应的，则对应的二进制表示二进制表示000，001，011为原公式的为原公式的成假赋值成假赋值。因而，只要知道。因而，只要知道一个命题公式一个命题公式A的主析取范式，可立即写出的主析取范式，可立

18、即写出A的真值表。的真值表。反之，若知道了反之，若知道了A的真值表的真值表，找出，找出A A的所有成真赋值，用其对应的所有成真赋值，用其对应的十进制数作为极小项的下标，就可求得的十进制数作为极小项的下标，就可求得A的主析取范式中所含的全部的主析取范式中所含的全部极小项，从而极小项，从而可得到可得到A的主析取范式的主析取范式。定理定理 在公式在公式A A的真值表中，所有真值为的真值表中，所有真值为1 1的赋值所对应的赋值所对应的极小项的析取式即为的极小项的析取式即为A A的主析取范式。的主析取范式。28第28页，共55页，编辑于2022年，星期六例2 试由 pqr 的真值表求它的主析取范式。11

19、11111011101010000110110000101010000000pqrpqrqp由表可知，001，011，101，110，111是原公式的成真赋值，因而对应的十进制数1，3，5，6，7为下标的极小项 构成 的主析取范式，而其它极小值不在它的主析取范式中，即29第29页，共55页，编辑于2022年，星期六主析取范式的用途主析取范式的用途 1.判断两命题公式是否逻辑等价判断两命题公式是否逻辑等价。由于任何命题公式的主析由于任何命题公式的主析取范式都是唯一的，因而若取范式都是唯一的，因而若AB，说明，说明A与与B有相同的主析取范式，有相同的主析取范式，反之，若反之，若A，B有相同的主析取

20、范式，必有有相同的主析取范式，必有AB 。举例举例2.判断命题公式的类型判断命题公式的类型。设设A是含是含n个命题变元的命题公式，个命题变元的命题公式，A为重言式，当且仅当为重言式，当且仅当A的主析取范式中含全部的主析取范式中含全部2n 个极小项；个极小项；A为矛为矛盾式，当且仅当盾式，当且仅当A的主析取范式中不含任何极小项，可设的主析取范式中不含任何极小项，可设A的主析的主析取范式为取范式为0；若；若A的主析取范式中至少含一个极小项，则的主析取范式中至少含一个极小项，则A是可满足式。是可满足式。举例举例3.求命题公式的成真和成假赋值求命题公式的成真和成假赋值。举例举例30第30页，共55页，

21、编辑于2022年，星期六练习：用主析取范式法判断题下列公式的类型，并求练习：用主析取范式法判断题下列公式的类型，并求公式的成真赋值。公式的成真赋值。(pq)(qp)分析：分析：求主析取范式可用真值表法，也可以用逻辑等价演算法：求主析取范式可用真值表法，也可以用逻辑等价演算法：(pq)(qp)(pq)(qp)(消去消去)(pq)pq(内移内移)(已为析取范式已为析取范式)(pq)(pq)(pq)(pq)(pq)m2m0m1m1m3m0m1m2m3所以，该式为重言式，所以，该式为重言式，00，01，10，11为成真赋值。为成真赋值。31第31页，共55页，编辑于2022年，星期六4.4.极大项与主

22、合取范式极大项与主合取范式 定义定义 在含在含n个命题变元的个命题变元的简单析取式简单析取式中，若每个命题变中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现元与其否定不同时存在，而二者之一必出现且仅出现一次，且第一次，且第i i个命题变元或其否定出现在左起的第个命题变元或其否定出现在左起的第i i位位上上(若命题变元无角码，则按字典顺序排列若命题变元无角码，则按字典顺序排列)，这样的，这样的简单析取式称为简单析取式称为极大项极大项。同极小项情况类似，n个命题变元可产生2n个极大项，每个极大项对应一个二进制数和一个十进制数，二进制数为该极大项的成假赋值，十进制数作为该极大项的抽象表

23、示的角码。32第32页，共55页，编辑于2022年，星期六例如例如，n=3n=3时，有时，有8个极大项，对应的二进制数个极大项，对应的二进制数(成假赋值成假赋值)、下标及名称如下：下标及名称如下：-000-0，记作，记作M0-001-1，记作，记作M1-010-2，记作，记作M2-011-3，记作，记作M3-100-4，记作，记作M4-101-5，记作，记作M5-110-6，记作，记作M6-111-7，记作，记作M733第33页，共55页，编辑于2022年，星期六一般情况下，一般情况下，n个命题变项共产生个命题变项共产生 个极大项，分别记为个极大项，分别记为 。极大项也有。极大项也有3 3个性

24、质：个性质：(1)(1)在极大项中，将在极大项中，将命题变元记做命题变元记做0 0，命题变元的否，命题变元的否定记为定记为1 1，则每个极大项对应一个二进制数，该二，则每个极大项对应一个二进制数，该二进制数是该极大项唯一的进制数是该极大项唯一的成假赋值成假赋值。(2)(2)任意两个不同的极大任意两个不同的极大项项的析取式的的析取式的值值永真永真。例如，。例如，(3)(3)全体极大项的合取式的值永假全体极大项的合取式的值永假，即，即 34第34页，共55页，编辑于2022年，星期六定定义义 设设命命题题公式公式A中含中含n个命个命题变项题变项，如果，如果A的合取范的合取范式中的式中的简单简单析取

25、式全是极大析取式全是极大项项，则则称称该该合取范式合取范式为为主合主合取范式取范式。任一命题公式的主合取范式一定存在，且是唯一的。任一命题公式的主合取范式一定存在，且是唯一的。求一命题公式求一命题公式A的主合取范式与求主析取范式的步骤非的主合取范式与求主析取范式的步骤非常相似，也是先求出常相似，也是先求出合取范式合取范式A。若。若A的某简单析取的某简单析取式式B中不含命题变项中不含命题变项pi或其否定或其否定 pi，则将，则将B展成如下形展成如下形式：式：35第35页，共55页，编辑于2022年，星期六例例求求 的主合取范式。的主合取范式。解解:其中 表示合取。36第36页，共55页，编辑于2

26、022年，星期六5.5.主析取范式与主合取范式的关系主析取范式与主合取范式的关系u 一个命题公式的主析取和主合取范式关系非常密切。一个命题公式的主析取和主合取范式关系非常密切。u 因为因为极小项极小项与与极大项极大项之间存在着如下关系：之间存在着如下关系：例如例如，37第37页，共55页，编辑于2022年，星期六设命题公式设命题公式A中含中含n个命题变元，如果个命题变元，如果A的主析取范式的主析取范式中中含含k个极小项个极小项 。则则A的主析取范式的主析取范式中必含中必含 个极小项，设为个极小项，设为 即即38第38页，共55页，编辑于2022年，星期六u 简而言之，简而言之，一个命题公式的极

27、小项下标与极大项下标是一个命题公式的极小项下标与极大项下标是互补的互补的。u 因此，只要求出了一个命题公式的主析取范式，就可根因此，只要求出了一个命题公式的主析取范式，就可根据它的极小项下标立即求得极大项，并求出主合取范式据它的极小项下标立即求得极大项，并求出主合取范式(反之亦然反之亦然)。39第39页，共55页，编辑于2022年，星期六例如例如，A中含中含3个命题变项，主析取范式为个命题变项，主析取范式为 因为极大项与极小项小标互补，则因为极大项与极小项小标互补，则A A的主合取范的主合取范式为式为 40第40页，共55页，编辑于2022年，星期六6.6.主析取范式在实际中的应用主析取范式在

28、实际中的应用 例例 某科研所要从某科研所要从3 3名骨干名骨干A A、B B、C C中挑选中挑选1-21-2名出国进修，名出国进修，由于工作需要选派时要满足以下条件：由于工作需要选派时要满足以下条件：（1 1）若）若A A去，则去，则C C同去。同去。（2 2）若）若B B去，则去，则C C不能去。不能去。（3 3）若）若C C不去，则不去，则A A或或B B可以去。可以去。问所里应如何选派他们？问所里应如何选派他们？41第41页，共55页，编辑于2022年，星期六解解 先命题符号化。设先命题符号化。设p p：派：派A A去。去。q q：派：派B B去。去。r r：派：派C C去。则由已知条件

29、可得公式：去。则由已知条件可得公式：(pr)(q r)(rpq)经过演算可得经过演算可得(pr)(q r)(rpq)m m1 1mm2 2mm5 5由于由于m m1 1=pqr,m=pqr,m2 2=pqr,m=pqr,m5 5=pqr=pqr。故，选派方案有以下三种：故，选派方案有以下三种：1.C1.C去，去，A A、B B不去。不去。2.B2.B去，去，A A、C C不去。不去。3.A3.A、C C同去，同去，B B不去。不去。42第42页，共55页，编辑于2022年，星期六7.7.主析取范式的个数主析取范式的个数 一般来说，含n个变元的命题公式，其数量是无限的，但每个命题公式都对应着一个

30、与它等价的主析取范式。如果两个命题公式有相同的主析取范式，我们称这两个命题公式属于一个等价类等价类。属于一个等价类的命题公式，显然是互相等价的那么，含含n个命题变元的命题公式，有多少个等价类呢？个命题变元的命题公式，有多少个等价类呢？43第43页，共55页，编辑于2022年，星期六当n=1时,极小项有 21=2 个,即P、P。主析取范式有:没有极小项 全部极小项 44第44页，共55页，编辑于2022年，星期六当当n=2时时，极极小小项项有有22=4个个。即即 P Q、PQ、P Q、PQ。主析取范式有。主析取范式有45第45页，共55页，编辑于2022年，星期六 共222=16 个。以此类推,

31、n个命题变元,可构造22n个不同的主析取范式(包括F)。这个数字增长非常快,如n=3时223=256,n=4 时224=65 536。主合取范式和主析取范式是一一对应的，因此，n个命题变元，也可构造22n个不同的主合取范式(包括T)。46第46页，共55页，编辑于2022年，星期六第一章第一章 命题逻辑命题逻辑 1.5联结词的扩充与归约联结词的扩充与归约47第47页，共55页，编辑于2022年，星期六1.1.联结词的扩充联结词的扩充 1）.一元运算一元运算Pf1f2 f3f40100110101永假永假恒等恒等否定式否定式永真永真48第48页，共55页，编辑于2022年，星期六2）.二元运算二

32、元运算49第49页，共55页，编辑于2022年，星期六除除f5、f6、f7、f8、f13、f14、f 15已已 定定 义义；f1、f10、f11、f16作作为为运运算算意意义义不不大大。因因此此，只只需需再再定定义义以以下下4个个联结词联结词:f12与非：与非：PQ(PQ)f2或非：或非：PQ(PQ)f9排斥或排斥或(异或异或)：P Q(P Q)PQPQf3,f4蕴含否定：蕴含否定：P Q(PQ)50第50页，共55页，编辑于2022年，星期六2.2.联结词的归约联结词的归约 9个联结词是否都必要个联结词是否都必要?显显然然不不是是的的,只只用用,三三个个联联结结词词构构造造的的式式子子,就就

33、足足以把一切命题公式等价地表示出来。以把一切命题公式等价地表示出来。根据德根据德摩根定律摩根定律:(PQ)PQ,(PQ)PQ所所以以,和和中中去去掉掉一一个个也也足足以以把把一一切切命命题题公公式式等等价价地表示出来。地表示出来。51第51页，共55页，编辑于2022年，星期六定定义义设设C是是一一个个联联结结词词集集合合,用用其其中中的的联联结结词词构构成成的的式式子子足足以以把把一一切切命命题题公公式式等等价价地地表表达达出出来来,则则这这个个联联结结词词集集合称为合称为全功能的全功能的。52第52页，共55页，编辑于2022年，星期六q显然显然,任一包含任一包含,的联结词集合都是的联结词集合都是全功能的全功能的。q,、,是是全功能的全功能的。q,也是也是全功能的全功能的。q但但 、,不是全功能的不是全功能的。53第53页，共55页，编辑于2022年，星期六例例1 1，如：，如：所以，所以，54第54页，共55页，编辑于2022年，星期六例例2判断下列命题公式的类型。判断下列命题公式的类型。所以，该式为重言式所以，该式为重言式。所以，该式为可满足式。所以，该式为可满足式。55第55页，共55页，编辑于2022年，星期六