二章命题逻辑等值演算ppt课件

1、1第二章第二章:命题逻辑等值演算命题逻辑等值演算q主要内容：主要内容：q 等值式与根本的等值式等值式与根本的等值式q 等值演算与置换规那么等值演算与置换规那么q 析取范式与合取范式，主析取范式与主合取析取范式与合取范式，主析取范式与主合取范式范式q 结合词完备集结合词完备集q本章与其他各章的联络本章与其他各章的联络q 是第一章的笼统与延伸是第一章的笼统与延伸q 是后续各章的先行预备是后续各章的先行预备2q q第一节：等值式第一节：等值式32.1 等值式等值式q假设等价式假设等价式AB是重言式，那么称是重言式，那么称A与与B等等值，记作值，记作AB，并称，并称AB是等值式是等值式q 几点阐明：几

2、点阐明：q定义中，定义中，A, B, 均为元言语符号均为元言语符号qA或或B中能够有哑元出现中能够有哑元出现. 例如，在例如，在q (pq) ( pq) ( rr)q 中，中，r为左边公式的哑元为左边公式的哑元. q用真值表可验证两个公式能否等值用真值表可验证两个公式能否等值42.1 等值式等值式pppp p01011011q例子例子q 判别判别ppq 52.1 等值式等值式pqppqp q(pq) (p q)001111011111100001110111q例子例子q 判别判别 pq pqq 62.1 等值式等值式q假设命题变项很多，怎样办？假设命题变项很多，怎样办？q - 利用知的等值式经

3、过代换得到新的等值式利用知的等值式经过代换得到新的等值式q命题：设命题：设A是一个命题公式，含有命题变项是一个命题公式，含有命题变项p1，p2，pn，又设，又设A1，A2，An是恣意的命是恣意的命题公式题公式. 对每个对每个ii=1，2，n，把，把pi在在A中中的一切出现都交换成的一切出现都交换成Ai，所得到的新命题公式记，所得到的新命题公式记作作B. 那么，假设那么，假设A是重言式，那么是重言式，那么B也是重言式也是重言式.72.1 等值式等值式q否认律否认律q双重否认律双重否认律 ppq德摩根律德摩根律q (p q) p qq (p q) p qq幂等律幂等律 p p p， p p pq交

4、换律交换律 qp q q p qp q q p qp q q p82.1 等值式等值式q结合律结合律q(p q) r p (q r)q(p q) r p (q r)q(p q) r p (q r)q分配律分配律qp (q r) (p q) (p r)qp (q r) (p q) (p r)92.1 等值式等值式q常元律常元律q零律零律: p 1 1， p 0 0q同一概同一概: p 0 p， p 1 pq排中律排中律: p p 1q矛盾律矛盾律: p p 0q吸收律吸收律qp (p q) pqp (p q) p102.1 等值式等值式q蕴涵等值式蕴涵等值式 p q p qq等价等值式等价等值式

5、 p q (p q) (q p)q假言易位假言易位 p q q pq等价否认等值式等价否认等值式 p q p qq归谬论归谬论 (p q ) (p q ) p 112.1 等值式等值式阐明：阐明： (1)16组等值方式都可以给出无穷多个同类型的详组等值方式都可以给出无穷多个同类型的详细的等值式。细的等值式。 (2)证明上述证明上述16组等值式的代入实例方法可用真值组等值式的代入实例方法可用真值表法，把表法，把改为改为所得的命题公式为永真式，那所得的命题公式为永真式，那么么成立。成立。122.1 等值式等值式q等值演算：由知的等值式推上演另外一些等值等值演算：由知的等值式推上演另外一些等值式的过

6、程式的过程q置换规那么：设置换规那么：设(A)是含公式是含公式A的命题公式，的命题公式， (B)是用公式是用公式B置换了置换了(A)中一切中一切A后得到的后得到的命题公式，假设命题公式，假设B ，那么，那么(A) (B) q阐明：阐明：q等值演算过程中遵照的重要规那么等值演算过程中遵照的重要规那么q一个命题公式一个命题公式A，经多次置换，所得到的新公，经多次置换，所得到的新公式与原公式等价式与原公式等价132.1 等值式等值式1.用等值演算验证等值式用等值演算验证等值式 试证：试证：p(qr) (p q)r证明：证明：p(qr)p(qr) p(qr)pqr pqr(p q) r(p q) r

7、(p q)r142.1 等值式等值式试证：试证：(p q)(p(p q)(pq)左边左边 (p q) (p(p q) (p q) (p(p q) (p q) (p q) (p p q) (q p q) (p q)152.1 等值式等值式2. 用等值演算判别公式的类型用等值演算判别公式的类型证明：证明：(pq) (p (qr)(pq)(p r)为为一永真式一永真式证明：原式证明：原式 (pq) (p(q r)(pq)(pr) (pq) (pq) (pr)(pq) (pr) (pq) (pr)(pq) (pr) 1162.1 等值式等值式 3解断定问题解断定问题 在某次研讨会的中间休憩时间，在某次

8、研讨会的中间休憩时间，3名与会者名与会者根据王教授的口音对他是哪个省市的人判别如根据王教授的口音对他是哪个省市的人判别如下：下： 甲：王教授不是苏州人，是上海人甲：王教授不是苏州人，是上海人 乙：王教授不是上海人，是苏州人乙：王教授不是上海人，是苏州人 丙：王教授既不是上海人，也不是杭州人丙：王教授既不是上海人，也不是杭州人 听完这听完这3人的判别后，王教授笑着说，他们人的判别后，王教授笑着说，他们3人中有一人说得全对，有一人说对了一半，另人中有一人说得全对，有一人说对了一半，另一人说得全不对。试用逻辑演算分析王教授究一人说得全不对。试用逻辑演算分析王教授究竟是哪里人。竟是哪里人。17q q第

9、二节：析取范式与合取范式第二节：析取范式与合取范式182.2 析取范式和合取范式析取范式和合取范式 q文字文字(literal): 命题变项及其否认命题变项及其否认q简单析取式简单析取式:仅由有限个文字构成的析取式仅由有限个文字构成的析取式q简单合取式简单合取式:仅由有限个文字构成的合取式仅由有限个文字构成的合取式q例：设例：设p、q为二个命题变元为二个命题变元qp，q，pp，qq，pq， q p，pq，p q 称为简单析取式称为简单析取式qp，q，pp，qq， pq， q p，pq，p q 称为简单合取式。称为简单合取式。192.2 析取范式和合取范式析取范式和合取范式q定理定理: q1)一

10、个简单析取式是永真式当且仅当它同一个简单析取式是永真式当且仅当它同时含某个命题变元及它的否认式时含某个命题变元及它的否认式qq2)一个简单合取式是永假式当且仅当它同一个简单合取式是永假式当且仅当它同时含某个命题变元及它的否认式时含某个命题变元及它的否认式q202.2 析取范式和合取范式析取范式和合取范式q析取范式析取范式:由有限个简单合取式构成的析取式由有限个简单合取式构成的析取式qA1 An, Ai 为简单合取式为简单合取式q( p q) (p r)q合取范式合取范式:由有限个简单析取式构成的合取式由有限个简单析取式构成的合取式qA1 An, Ai 为简单析取式为简单析取式q( p q) (

11、p r)q析取范式与合取范式统称为范式析取范式与合取范式统称为范式212.2 析取范式和合取范式析取范式和合取范式q定理：定理：qAi 简单合取式，简单合取式， A1 An F 当且仅当当且仅当 Ai F，恣意，恣意AiqAi 简单析取式，简单析取式， A1 An T 当且仅当当且仅当 Ai T，恣意，恣意Ai222.2 析取范式和合取范式析取范式和合取范式q范式存在定理范式存在定理: 恣意命题公式都存在着与之等值的恣意命题公式都存在着与之等值的析取范式与合取范式析取范式与合取范式q方法：方法： q步骤一：消去步骤一：消去“、“结合词结合词q步骤二：消去双重否认符，内移否认符步骤二：消去双重否

12、认符，内移否认符q步骤三：运用分配律步骤三：运用分配律232.2 析取范式和合取范式q范式存在定理范式存在定理: 恣意命题公式都存在着与之等值的恣意命题公式都存在着与之等值的析取范式与合取范式析取范式与合取范式q方法：方法： q步骤一：消去步骤一：消去“、“结合词结合词q步骤二：消去双重否认符，内移否认符步骤二：消去双重否认符，内移否认符q步骤三：运用分配律步骤三：运用分配律242.2 析取范式和合取范式q步骤一：利用等值公式：化去步骤一：利用等值公式：化去“、“结合结合词词q p q p qq p q (p q) (q p)252.2 析取范式和合取范式q范式存在定理范式存在定理: 恣意命题

13、公式都存在着与之等值的恣意命题公式都存在着与之等值的析取范式与合取范式析取范式与合取范式q方法：方法： q步骤一：消去步骤一：消去“、“结合词结合词q步骤二：消去双重否认符，内移否认符步骤二：消去双重否认符，内移否认符q步骤三：运用分配律步骤三：运用分配律262.2 析取范式和合取范式q消去双重否认符，内移否认符消去双重否认符，内移否认符q德摩根律德摩根律q (p q) p qq (p q) p qq双重否认律双重否认律 p p272.2 析取范式和合取范式q范式存在定理范式存在定理: 恣意命题公式都存在着与之等值的恣意命题公式都存在着与之等值的析取范式与合取范式析取范式与合取范式q方法：方法

14、： q步骤一：消去步骤一：消去“、“结合词结合词q步骤二：消去双重否认符，内移否认符步骤二：消去双重否认符，内移否认符q步骤三：运用分配律步骤三：运用分配律282.2 析取范式和合取范式q利用利用“对对“的分配，将公式化成为析取范式的分配，将公式化成为析取范式qp (q r) (p q) (p r)q利用利用“对对“的分配，将公式化成为合取范式的分配，将公式化成为合取范式qp (q r) (p q) (p r)292.2 析取范式和合取范式q 例：求例：求(p q) (p q)的析取范式的析取范式 q 化去化去q ( p q) (p q)q “对对“分配，化为析取范式分配，化为析取范式q (

15、p p q) (q p q) q 最简析取范式最简析取范式q p q 302.2 析取范式和合取范式q例：求例：求(p q) r) p的析取范式和合取范式的析取范式和合取范式q (一一) 求析取范式求析取范式q原式原式 ( (p q) r) pq ( (p q) r) pq ( (p q) r) pq (p q) r) pq (p r) (q r) pq p (p r) (q r)q p (q r)312.2 析取范式和合取范式(二二)求合取范式求合取范式原式原式 ( (p q) r) p ( (p q) r) p ( (p q) r) p (p q) r) p (p p q) (p r) (

16、p q) (p r)322.2 析取范式和合取范式问题：问题：一个命题公式的析取范式是不是独一的？一个命题公式的析取范式是不是独一的？同一命题公式的析取范式是不是等值的？同一命题公式的析取范式是不是等值的？332.2 析取范式和合取范式q极小项极小项(极大项极大项):含有含有n个命题变项的简单合取式个命题变项的简单合取式 q(简单析取式简单析取式)，并满足，并满足q每个命题变元和它的否认式不同时出现，而二者每个命题变元和它的否认式不同时出现，而二者之一必出现且仅出现一次之一必出现且仅出现一次q第第i个命题变项或它的否认式出如今从左算起的个命题变项或它的否认式出如今从左算起的第第i位上位上(假设

17、无角标，那么按字典顺序陈列假设无角标，那么按字典顺序陈列)q假设有个命题变项，那么有假设有个命题变项，那么有2n个极小项极个极小项极大项大项q假设我们把不带否认符的命题变项取成假设我们把不带否认符的命题变项取成1，带否，带否认符的命题变项取成认符的命题变项取成0，那么每一个极小项都对，那么每一个极小项都对应一个二进制数，因此也对应一个十进制数应一个二进制数，因此也对应一个十进制数342.2 析取范式和合取范式q极小项的编码极小项的编码:对应成真赋值对应成真赋值q三个变元三个变元p、q、r可构造可构造8个极小项：个极小项：q pqr FFF 0 记作记作 m0q pqr FFT 1 记作记作 m

18、1q pqr FTF 2 记作记作 m2q pqr FTT 3 记作记作 m3q pqr TFF 4 记作记作 m4 q pqr TFT 5 记作记作 m5q pqr TTF 6 记作记作 m6 q pqr TTT 7 记作记作 m7352.2 析取范式和合取范式q极大项的编码极大项的编码:对应成假赋值对应成假赋值q如三个变元如三个变元 p、q、r，其记法如下：，其记法如下：qpqr F F F 0 记作记作 M0qp q r F F T 1 记作记作 M1qp qr F T F 2 记作记作 M2qp q r F T T 3 记作记作 M3q qp q r T T T 7 记作记作 M736

19、2.2 析取范式和合取范式q定理定理:设设mi和和Mi是命题变元是命题变元p1, p2 pn构成的构成的极小项和极大项，那么：极小项和极大项，那么：q(1) mi mj F, (ij)q(2) Mi Mj T, (ij)q(3) mi Mi； Mi mi372.2 析取范式和合取范式q 主析取范式主析取范式(主合取范式主合取范式)：由：由n个命题变项构成的个命题变项构成的析取范式析取范式(合取范式合取范式)中一切的简单合取式中一切的简单合取式(简单析取简单析取式式)都是极小项都是极小项(极大项极大项)q 定理定理: 任何命题公式都存在着与其等值的主析取范任何命题公式都存在着与其等值的主析取范式

20、和主合取范式，并且是独一的。式和主合取范式，并且是独一的。382.2 析取范式和合取范式q证法一证法一q在真值表中，使命题公式的真值为在真值表中，使命题公式的真值为T的指派所对的指派所对应的极小项的析取，即为此公式的主析取范式应的极小项的析取，即为此公式的主析取范式q证：给定一个命题公式证：给定一个命题公式A，使其为，使其为T的真值指派所的真值指派所对应的极小项为对应的极小项为m1, m2, mk,这些极小项的析这些极小项的析取记为取记为B，为此要证，为此要证AB，即要证，即要证A与与B在一样的在一样的指派下具有一样的真值。指派下具有一样的真值。392.2 析取范式和合取范式首先对于使首先对于

21、使A为为T的指派显然使的指派显然使B为为T对于使对于使A为为F的指派，它对应的极小项的指派，它对应的极小项(设为设为mj )不不包含在包含在m1, m2, mk 中。所以中。所以 mj为使为使B为为F的指派的指派所以所以A B 得证得证402.2 析取范式和合取范式q一个公式的主析取范式即为令此公式的真值为一个公式的主析取范式即为令此公式的真值为T的指派所对应的极小项的析取。的指派所对应的极小项的析取。q一个命题公式的真值表是独一的，因此一个命一个命题公式的真值表是独一的，因此一个命题公式的主析取范式也是独一的题公式的主析取范式也是独一的412.2 析取范式和合取范式析取范式和合取范式p q

22、r m1 m3 m5 m6 m7pqrpqrFFFFFFTTFTFFFTTTTFFFTFTTTTFTTTTTpqr的真值表的真值表422.2 析取范式和合取范式析取范式和合取范式q证法二：构造法证法二：构造法q用等值演算方法求命题公式主析取范式的方用等值演算方法求命题公式主析取范式的方法法q将命题公式化归为与其等值的析取范式将命题公式化归为与其等值的析取范式q添变元添变元: q消去反复项消去反复项Ai (pj pj) (Ai pj) (Ai pj) 432.2 析取范式和合取范式q 例：求例：求(p(pq)q的主析取范式的主析取范式q 解：原式解：原式q (pp)(pq)q q -(1)化为析

23、取范式化为析取范式q (pq)q q -(2)化简化简q (pq)(q(pp)q (pq)(pq)(pq) q -(3)添项添项q (pq)(pq) m1 m3 q -(4)合并一样最小项合并一样最小项442.2 析取范式和合取范式q主合取范式主合取范式q任何一个命题公式都可求得它的主合取范式任何一个命题公式都可求得它的主合取范式q一个命题公式的主合取范式是独一的一个命题公式的主合取范式是独一的q在真值表中，令命题公式的真值为在真值表中，令命题公式的真值为“F的指派的指派就对应其主合取范式的一个极大项就对应其主合取范式的一个极大项q构造法构造法452.2 析取范式和合取范式q 例例:求求p(p

24、q)q的主合取范式的主合取范式 q 解：原式解：原式 p( pq)qq (p p)(pq)qq (pq)qq (pq) qq (pq)(q(p p)q (pq)( pq) q M0 M2 pq上式上式FFFFTTTFFTTT462.2 析取范式和合取范式q主析合取范式的用途讨论：主析合取范式的用途讨论：q求公式的成真与成假赋值求公式的成真与成假赋值q判别公式类型判别公式类型q判别两个命题公式能否等值判别两个命题公式能否等值q运用主析合取范式分析和处理实践问题运用主析合取范式分析和处理实践问题472.2 析取范式和合取范式q 1. 求公式的成真与成假赋值求公式的成真与成假赋值q 例：例：(pq)

25、r m1m3m5 m6m7q 成真赋值为成真赋值为001, 011, 101, 110, 111q 成假赋值为成假赋值为000, 010, 100482.2 析取范式和合取范式q 2. 判别公式的类型判别公式的类型q 设设A含含n个命题变项个命题变项q A为重言式为重言式 q A的主析取范式含的主析取范式含2n个极小项个极小项q A的主合取范式为的主合取范式为1q A为矛盾式为矛盾式 q A的主析取范式为的主析取范式为0 q A的主合析取范式含的主合析取范式含2n个极大项个极大项q A为非重言式的可满足式为非重言式的可满足式q A的主析取范式中至少含一个但不是全部的主析取范式中至少含一个但不是

26、全部极小项极小项q A的主合取范式中至少含一个但不是全部的主合取范式中至少含一个但不是全部极大项极大项492.2 析取范式和合取范式q2. 判别公式的类型判别公式的类型q 例：例： 用公式的主析取范式判别下述公式的类型用公式的主析取范式判别下述公式的类型：q 1( p q) qq 2p( p q)q 3( p q) r502.2 析取范式和合取范式q3. 判别两个命题公式能否等值判别两个命题公式能否等值q 例：例： 用主析取范式判两个公式能否等值用主析取范式判两个公式能否等值q p(qr) 与与 (pq)rq p(qr) 与与 (pq)rq 解：解： p(qr) m0m1m2m3 m4m5 m

27、7q (pq)r m0m1m2m3 m4m5 m7q (pq)r m1m3 m4m5 m7q 显见，中的两公式等值，而的不等值显见，中的两公式等值，而的不等值. 512.2 析取范式和合取范式q例：某研讨所要从例：某研讨所要从3名科研骨干名科研骨干A，B，C中挑中挑选选12名出国进修，由于任务需求，选派时名出国进修，由于任务需求，选派时要满足以下条件：要满足以下条件：q假设假设A去，那么去，那么C同去。同去。q假设假设B去，那么去，那么C不能去。不能去。q假设假设C不去，那么不去，那么A或或B可以去。可以去。q解解:设设p：派：派A去；去；q：派：派B去；去；r：派：派C去。去。q那么那么(p

28、r) (qr)(r (pq) 522.2 析取范式和合取范式经演算可得：经演算可得：(pr) (qr)(r (pq) m1m2m5可知选派方案有三种：可知选派方案有三种：C去，去，A，B都不去。都不去。B去，去，A，C不去。不去。A，C去，去，B不去。不去。532.2 析取范式和合取范式 主合取范式与主析取范式转换主合取范式与主析取范式转换公式公式: A = mi1 mi2 mis A = mj1 mj2 mjt ，t=2n-s A A (mj1 mj2 mjt ) mj1 mj2 mjt Mj1 Mj2 Mjt 542.2 析取范式和合取范式q讨论：具有讨论：具有n个变项的命题公式有多少个不

29、同的主个变项的命题公式有多少个不同的主析取范式？析取范式？q对于含有个变项的命题公式，必定可写出对于含有个变项的命题公式，必定可写出22n个个主析取范式主析取范式(包括包括0)。q同理，含有个变项的命题公式，也可写出同理，含有个变项的命题公式，也可写出22n个个主合取范式主合取范式(包括包括1)。55q q第三节：结合词的完备集第三节：结合词的完备集562.3 结合词的完备集“与非结合词：符号“(pq)读作：“p与q的否认(pq)(pq)pqpqFFTFTTTFTTTF572.3结合词的完备集q“或非结合词：或非结合词：q 符号：符号：“q (pq)读作：读作：“p或或q的否认的否认 q (p

30、q) (pq)pqpqFFTFTFTFFTTF582.3 结合词的完备集结合词的完备集q真值函数真值函数F: 0,1n 0,1q结合词完备集结合词完备集S: qS是一个结合词集合是一个结合词集合q每一个真值函数都可以由仅含每一个真值函数都可以由仅含S中的结合词构中的结合词构成的公式表示成的公式表示q定理定理: S = ，是结合词完备集是结合词完备集q 证明：任何一个证明：任何一个nn1元真值函数都与元真值函数都与独一的一个主析取范式等值，而主析取范式仅独一的一个主析取范式等值，而主析取范式仅含含 ，592.3 结合词的完备集结合词的完备集q推论推论: S = ，是结合词完备集是结合词完备集q

31、证明：证明：p q (p q)q ( p q) 602.3 结合词的完备集结合词的完备集q定理定理: ， 是结合词完备集是结合词完备集q证明：证明：q首先，首先， p (p p) ppq其次，其次，p q (p q)q (pq) q (pq) (pq) q p q (pp) (qq) q (pq) (pq)61第二章第二章 习题课习题课q主要内容主要内容q等值式与等值演算等值式与等值演算q根本等值式根本等值式1616组，组，2424个公式个公式q主析取范式与主合取范式主析取范式与主合取范式q结合词完备集结合词完备集62根本要求根本要求l 深化了解等值式的概念深化了解等值式的概念l 牢记根本等值

32、式的称号及它们的内容牢记根本等值式的称号及它们的内容l 熟练地运用根本等值式及置换规那么进展等值演算熟练地运用根本等值式及置换规那么进展等值演算l 了解文字、简单析取式、简单合取式、析取范式、合取范了解文字、简单析取式、简单合取式、析取范式、合取范式的概念式的概念l 深化了解极小项、极大项的概念、称号及下角标与成真、深化了解极小项、极大项的概念、称号及下角标与成真、成假赋值的关系成假赋值的关系l 熟练掌握求主范式的方法等值演算、真值表等熟练掌握求主范式的方法等值演算、真值表等l 会用主范式求公式的成真赋值、成假赋值、判别公式的类会用主范式求公式的成真赋值、成假赋值、判别公式的类型、判别两个公式

33、能否等值型、判别两个公式能否等值l 会将公式等值地化成指定结合词完备集中的公式会将公式等值地化成指定结合词完备集中的公式l 会用命题逻辑的概念及运算处理简单的运用问题会用命题逻辑的概念及运算处理简单的运用问题63练习练习1:概念概念1. 设设A与与B为含为含n个命题变项的公式，判别以下命题能个命题变项的公式，判别以下命题能否为真？否为真？(1) AB当且仅当当且仅当A与与B有一样的主析取范式有一样的主析取范式(2) 假设假设A为重言式，那么为重言式，那么A的主合取范式为的主合取范式为0(3) 假设假设A为矛盾式，那么为矛盾式，那么A的主析取范式为的主析取范式为1(4) 任何公式都能等值地化成任

34、何公式都能等值地化成, 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成, , 中的公式中的公式阐明阐明:(2) 重言式的主合取范式不含任何极大项，为重言式的主合取范式不含任何极大项，为1. (3) 矛盾式的主析取范式不含任何极小项矛盾式的主析取范式不含任何极小项, 为为0. (4) , 不是完备集，如矛盾式不能写成不是完备集，如矛盾式不能写成, 中的公式中的公式. (5) , 是完备集是完备集. 真真假假假假假假真真64练习练习2：结合词完备集：结合词完备集2将将A = (pq)r改写成下述各结合词集中的公改写成下述各结合词集中的公式式: (1) , , (2) , (3) , (4) ,