第3章命题逻辑优秀PPT.ppt

《第3章命题逻辑优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第3章命题逻辑优秀PPT.ppt（37页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第第3章命题逻辑章命题逻辑2022/10/221现在学习的是第1页，共37页5.1.1 5.1.1 命题命题 定定义义5.15.1 具具有有确确切切真真值值的的陈陈述述句句称称为为命命题题,该该命题可以取一个命题可以取一个“值值”，称为，称为真值真值。真真值值只只有有“真真”和和“假假”两两种种，分分别别用用“”(或或“”)和和“”(或或“”)表示。表示。5.1 5.1 命题与命题联结词命题与命题联结词第第5章章 命题逻辑命题逻辑例例1.1 (1)加拿大是一个国家。加拿大是一个国家。(2)成都是中国的首都。成都是中国的首都。(3)那个人是老师。那个人是老师。(T)(F)(T或或F)2022/1

2、0/222022/10/222 2现在学习的是第2页，共37页(4)(4)。(5)(5)。(6)(6)我喜欢踢足球。我喜欢踢足球。(7)(7)把门关上。把门关上。(8)(8)你要出去吗？你要出去吗？(9)(9)今天天气真好啊！今天天气真好啊！(11)(11)明天我要去旅游。明天我要去旅游。(12)(12)。(13)(13)这个语句是假的。这个语句是假的。(F)(T或或F)(T或或F)(T或或F)2022/10/222022/10/223 3现在学习的是第3页，共37页一般来说，命题可分两种类型：一般来说，命题可分两种类型：命题的分类命题的分类原子命题原子命题(简单命题简单命题)：不能再：不能再

3、分解分解为更为简单命为更为简单命 题的命题。题的命题。复合命题复合命题：可以：可以分解分解为更为简单命题的命题。或者说由简为更为简单命题的命题。或者说由简单命题经单命题经命题联结词命题联结词复合而成的命题。复合而成的命题。例如例如:今天下雨。今天下雨。例如例如:今天下雨并且刮风。今天下雨并且刮风。命题的表示命题的表示通常用通常用大写的带或不带下标的英文字母大写的带或不带下标的英文字母,.,Ai,Bi,Ci,.等表示命题等表示命题.2022/10/222022/10/224 4现在学习的是第4页，共37页5.1.2 5.1.2 命题联结词命题联结词联接词联接词记号记号记法记法 (基本意思基本意思

4、)真值结果真值结果否定否定A (A的否定的否定)A为真当且仅当为真当且仅当A为假为假合取合取A B(A并且并且B)A B为为真真当当且且仅仅当当A,B同同为真为真析取析取A B(A或者或者B)A B为为真真当当且且仅仅当当A,B中中至少一个为真至少一个为真蕴涵蕴涵AB(若若A则则B)AB为为假假当当且且仅仅当当A为为真真B为假为假等价等价A B(A当且仅当当且仅当B)AB为为真真当当且且仅仅当当A,B同同为真假为真假2022/10/222022/10/225 5现在学习的是第5页，共37页例例1 1.2 2 用复合命题表示如下图所示的开关电路用复合命题表示如下图所示的开关电路图图5-5-1 1

5、 图图5-25-2 图图5-5-3 3ABABA设：设：开关闭合；：开关闭合。：开关闭合；：开关闭合。2022/10/222022/10/226 6现在学习的是第6页，共37页用用复复合合命命题题表表示示如如下下图图所所示示的的逻逻辑辑电电路路。P P Q Q P P Q Q P P 图图5-5-4 4 图图5-5-5 5 图图5-5-6 6例例1 1.2 2（续）续）2022/10/222022/10/227 7现在学习的是第7页，共37页约定约定:1.命题联结词之命题联结词之优先级优先级如下：如下：否定否定合取合取析取析取蕴涵蕴涵等价等价 2.2.若运算要求与优先次序不一致时，可使用若运算

6、要求与优先次序不一致时，可使用圆括号圆括号.例例1.3 设命题设命题 P：明天上午七点下雨；：明天上午七点下雨；Q：明天上午七点下雪；：明天上午七点下雪；R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：1.如果明天上午七点不是雨夹雪，则我将去学校。如果明天上午七点不是雨夹雪，则我将去学校。2.如果明天上午七点不下雨并且不下雪，则我将去学校。如果明天上午七点不下雨并且不下雪，则我将去学校。3.明天上午七点下雨或下雪，当且仅当我将不去学校。明天上午七点下雨或下雪，当且仅当我将不去学校。4.明天上午我将雨雪无阻一定去学校。明天上午我将雨雪无阻一定去学校。2022/10/222022/1

7、0/228 8现在学习的是第8页，共37页解：解：1.如果明天上午七点不是雨夹雪，则我将去学校。如果明天上午七点不是雨夹雪，则我将去学校。可符号化为：可符号化为：(PQ)R。2.如果明天上午七点不下雨并且不下雪，则我将去学校。如果明天上午七点不下雨并且不下雪，则我将去学校。可符号化为可符号化为:(PQ)R。3.明天上午七点下雨或下雪，当且仅当我将不去学校。明天上午七点下雨或下雪，当且仅当我将不去学校。可符号化为可符号化为:(PQ)R。4.明天上午我将雨雪无阻一定去学校。明天上午我将雨雪无阻一定去学校。可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)。或或(PQ)(PQ)(PQ)

8、(PQ)R。2022/10/222022/10/229 9现在学习的是第9页，共37页例例1 1.4 4 符号化语句：符号化语句：除非你陪伴我或代我叫车子，否则我将不除非你陪伴我或代我叫车子，否则我将不出去。出去。则则句子可符号化为：句子可符号化为：(PQ)R 或或 R(PQ)解：解：设命题设命题 P：你陪伴我；：你陪伴我；Q：你代我叫车子；：你代我叫车子；R：我将出去。：我将出去。2022/10/222022/10/221010现在学习的是第10页，共37页定义定义5.7 一个特定的命题是一个一个特定的命题是一个常值命题常值命题，它不是，它不是具有值具有值“T”(“1”)，就是具有值，就是具

9、有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为一个变量命题，常称它为命题变量命题变量(或或命题变元命题变元);命题变量无具体的真值，命题变量无具体的真值，其其变域是集合变域是集合 T，F(或或0，1)。说明说明 含有命题变元的含有命题变元的原子原子或复合命题实际上是或复合命题实际上是命题变元的命题变元的“函数函数”，可称为，可称为“真值函数真值函数”，或称或称为为命题公式命题公式，命题公式没有确，命题公式没有确切切真值。真值。5.2命题公式、解释与真值表命题公式、解释与真值表2022/10/222022/10/221

10、111现在学习的是第11页，共37页 5.2.1 5.2.1 命题公式命题公式定义定义5.8 (1)命题变元本身是一个公式；命题变元本身是一个公式；(2)如果如果P是公式，则是公式，则(P)也是公式；也是公式；(3)如果如果P，Q是公式，则是公式，则(PQ)、(PQ)、(PQ)、(PQ)也是公式；也是公式；(4)命题公式仅由有限步使用规则命题公式仅由有限步使用规则1-3后产生的结果。该后产生的结果。该公式常用符号公式常用符号 G、H、等表示。等表示。2022/10/222022/10/221212现在学习的是第12页，共37页符号串：符号串：(PQ)；(P(PQ)；(PQ)(RQ)(PR)；(

11、P(QR)(Q(SR)。等都是命题公式。例例2.2符号串：符号串：PQ,(P Q)；P(QR),(PQ)Q)等都不是合法的命题公式。例例2.12.12022/10/222022/10/221313现在学习的是第13页，共37页5.2.2 5.2.2 公式的解释与真值表公式的解释与真值表定义定义5.9设命题变元设命题变元P1,P2,P3,Pn是出是出现在公式现在公式G中的所有命题变元，指定中的所有命题变元，指定P1,P2,P3,Pn一组真值，则这组真值称为一组真值，则这组真值称为G 的一个的一个解释解释,常记为常记为。一般来说，若有一般来说，若有 n个命题变元，则应有个命题变元，则应有2n个不个

12、不同的解释。同的解释。定义定义5.10公式公式G在其所有可能的解释下所取在其所有可能的解释下所取真值的表，称为的真值的表，称为的真值表真值表。2022/10/222022/10/221414现在学习的是第14页，共37页 例例2 2.1.1 求公求公式：式：G1 PQ 和和 G2(P Q)(Q P)的的真值表真值表,其中其中P 和和Q 是是 G1和和 G2 的所有命题变元的所有命题变元.PQPPQ0011011110001101P Q1101解解 G1和和 G2的的真值表真值表为为:PQP Q Q PG200111011001001011111P Q10012022/10/222022/10/

13、221515现在学习的是第15页，共37页设设有有公公式式：G(PQ)R其其中中，P、Q、R是是G的所有命题变元，则其真值表如下：的所有命题变元，则其真值表如下：PQRP Q(P Q)R0000100101010010110110001101011101011111例例2 2.2 22022/10/222022/10/221616现在学习的是第16页，共37页该真值表可简化为：该真值表可简化为：PQR(P Q)R00010011010101111001101111001111例例2 2.2 2（续）续）2022/10/222022/10/221717现在学习的是第17页，共37页 5.2.3-

14、4 5.2.3-4 一些特殊的公式一些特殊的公式,等价公式等价公式例例3.1 考虑考虑(PQ)P 的真值表。的真值表。解解 真值表为真值表为:PQPQ(PQ)(PQ)P00101011011001111101注注:该公式对所有可能的解释均有该公式对所有可能的解释均有“真真”值值1.公式类型公式类型2022/10/222022/10/221818现在学习的是第18页，共37页定定义义5.11(1)公公式式 G 称称为为永永真真公公式式(重重言言式式)，如如果在它的所有解释之下都为果在它的所有解释之下都为“真真”。(2)公式公式G 称为称为永假公式永假公式(矛盾式矛盾式),如果在它的所如果在它的所

15、 有解释之下都为有解释之下都为“假假”。(3)公式公式 G 称为称为可满足的可满足的，如果它不是永假的。，如果它不是永假的。关系关系(1)永真式的否定是矛盾式；矛盾式的否定是永真式。永真式的否定是矛盾式；矛盾式的否定是永真式。(2)永真式一定是可满足式。永真式一定是可满足式。两个术语两个术语：如果公式如果公式G 在解释在解释下是真的，则称下是真的，则称 满足满足 G；如果；如果G 在解释在解释下是假的，则下是假的，则称称弄假弄假G。2022/10/222022/10/221919现在学习的是第19页，共37页例例3.2 列出真值表，验证下列公式是否是永真公式。列出真值表，验证下列公式是否是永真

16、公式。(1)(PQ)P)Q；(2)(P Q)(P Q)P QPQ(PQ)P(PQ)P)Q0 01010 11011 00011 1111解解 的真值表如下的真值表如下从上述真值表知从上述真值表知(1)(1)是永真公式。是永真公式。2022/10/222022/10/222020现在学习的是第20页，共37页(2)(2)(P Q)(P Q)的真值表如下：的真值表如下：从上述真值表知从上述真值表知是永真公式。是永真公式。P QP Q(P Q)P QP Q 原式原式00011111011010011010010111100001例例3.23.2（续）（续）2022/10/222022/10/2221

17、21现在学习的是第21页，共37页定定义义5.12公公式式G、H说说是是等等价价的的(Equivalent)，记记作作GH，如如果在其任意的解释下，其真值相同。果在其任意的解释下，其真值相同。定理定理5.1 公式公式G、H 等价的充分必要条件是公式等价的充分必要条件是公式GH 是永真公式。是永真公式。证证明明 “”假假定定G，H 等等价价，则则G，H在在其其任任意意解解释释下下或或同同为为真真或或同同为为假假，于于是是由由“”的的意意义义知知，GH在在下下为为“真真”，由，由的任意性的任意性 GH 为永真公式。为永真公式。“”假假定定公公式式GH是是永永真真公公式式，则则对对任任意意的的解解释

18、释，GH 均均为为真真，因因此此，G、H或或同同为为真真，或或同同为为假假，由由的的任任意性，故有意性，故有GH。2.2.等价公式等价公式2022/10/222022/10/222222现在学习的是第22页，共37页2.2.=与与 的区别的区别:说明说明 1.1.定理定理5.1表明表明:G=H GH 是永真公式是永真公式;这这是符号是符号=与与 的联系的联系.（1）“”是逻辑联结词，是逻辑联结词，而而“”是关系是关系符符.若若G,H 是命题公式，是命题公式，则则 GH 仍是一个命题公式仍是一个命题公式;而而GH 却不却不是命是命题公式题公式。（2）如果要用计算机来判断如果要用计算机来判断是否是

19、否有有 G H，直接，直接“计算计算”那是办不到的那是办不到的，然而计算机却可然而计算机却可通过通过“计算计算”公式公式 GH 是否是否是永真公式是永真公式而达目的而达目的。2022/10/222022/10/222323现在学习的是第23页，共37页定理定理5.2(代入定理代入定理)设设G(P1,P2,Pn)是一个命题公式，是一个命题公式，其中其中：P1、P2、Pn 是命题变元，是命题变元，G1(P1,P2,Pn)、G2(P1,P2,Pn)、.、Gn(P1,P2,Pn)为任意的命题公式，此时若为任意的命题公式，此时若G是永真公式或永假公式是永真公式或永假公式,则用则用G1取代取代P1、G2取

20、代取代P2、Gn取代取代Pn后，而得到的新的命后，而得到的新的命题题公式：公式：G(G1,G2,Gn)G(P1,P2,Pn)也是一个永真公式或永假公式。也是一个永真公式或永假公式。3.3.两个两个定理定理2022/10/222022/10/222424现在学习的是第24页，共37页定定理理5 5.3.3(替替换换定定理理 )若若G1是是G的的子子公公式式(即即 G1是是公公式式G的的一一部部分分)，H1是是任任意意的的命命题题公公式式，设设在在G中中凡凡出出现现G1处处都都以以H1替替换换后后得得到到新新的的命命题题公式公式为为H，若，若G1H1，则，则GH。4.基本等价公式基本等价公式设设G

21、，H，S 是任意的公式，则：是任意的公式，则：(1)1:G(HS)(GH)S 2：G(HS)(GH)S (结合律结合律)2022/10/222022/10/222525现在学习的是第25页，共37页(2)3：GHHG 4：GHHG (交换律交换律)(3)5：GGG 6：GGG (幂等律幂等律)(4)7：G(GH)G 8:G(GH)G (吸收律吸收律)(5)9：G(HS)(GH)(GS)10：G(HS)(GH)(GS)(分配律分配律)(6)(6)1111：GG 1212：GG (同一律同一律)2022/10/222022/10/222626现在学习的是第26页，共37页(7)13：G 14：G

22、(零律零律)(8)15：GG (排中律排中律)(9)16：GG(矛盾律矛盾律)(10)17：(G)G (双重否定律双重否定律)(11)18：(GH)GH 19：(GH)GH (De MoRGan定律定律)(12)20：(G H)(GH)(HG)(等价等价)(13)21：(GH)(GH)(蕴涵蕴涵)基本等价公式（续）基本等价公式（续）2022/10/222022/10/222727现在学习的是第27页，共37页例例3.3 证明证明 PQ Q P 证证 PQ PQ Q P (Q)P Q P 例例3.4 判断判断P(PQ)Q)是否永真公式。是否永真公式。解解 原式原式 P(PQ)Q (PQ)(PQ)

23、T所以所以,原式是永真公式。原式是永真公式。2022/10/222022/10/222828现在学习的是第28页，共37页例例3.5 证明证明 P(QR)(PQ)R证证 左边左边 P(QR)(PQ)R (PQ)R (PQ)R例例3.6 试试用用较较少少的的开开关关设设计计一一个个与与右右图图有有相同功能的电路。相同功能的电路。2022/10/222022/10/222929现在学习的是第29页，共37页解解 可可将将图图中中所所示示之之开开关关电电路路用用下下述述命命题题公式表示为：公式表示为：(PQS)(PRS)而上述公式而上述公式 (PQS)(PRS)(PS)Q)(PS)R)(PS)(QR

24、)所以开关设计图可简化为：所以开关设计图可简化为：2022/10/222022/10/223030现在学习的是第30页，共37页例例3.6 将下面的程序语言化简将下面的程序语言化简 If A then if B then X else Y else if B then X else YSTARTABBXYEND该程序用下图该程序用下图的流程图表的流程图表示为：示为：解解 该语言即该语言即 If A then if B then X else Y else if B then X else Y2022/10/222022/10/223131现在学习的是第31页，共37页从框图可知：执行从框图可知

25、：执行X的条件为：的条件为：()()()STARTABBXYEND执行执行Y的条件为：的条件为：()()()经转换后，这段程经转换后，这段程序可简化：序可简化：If B then X else Y其流程图如下图。其流程图如下图。STARTENDBXY2022/10/222022/10/223232现在学习的是第32页，共37页5.3 5.3 联结词的完备集联结词的完备集1.1.其它联结词其它联结词 除了包含五个基本联结词外，引进如下几个联结词。除了包含五个基本联结词外，引进如下几个联结词。联结词联结词记号记号复合命题复合命题读法读法记法记法异或异或A不可兼或不可兼或BA异或异或BA B蕴涵否定

26、蕴涵否定A,B蕴涵否定蕴涵否定A蕴涵否定蕴涵否定BA B与非与非A和和B的与非的与非A与非与非BAB或非或非A和和B的或非的或非A或非或非BAB2022/10/222022/10/223333现在学习的是第33页，共37页其真值结果如下：其真值结果如下：ABA B A BABAB000011011010101110110000性质性质:(1)(1)A B=(A B)(2)(2)A B=(A B)(3)(3)A B=(A B)(4)(4)A B=(A B)2022/10/222022/10/223434现在学习的是第34页，共37页定义定义5.13设设S是联结词集合，如果是联结词集合，如果 (1

27、)用用S 中中的的联联结结词词表表示示的的等等价价公公式式，可可以以表表示任何命题公式。示任何命题公式。(2)从从S中中删删除除任任何何一一个个联联结结词词而而得得到到的的新新联联结结词词集集合合S1,至至少少存存在在一一个个命命题题公公式式不不能能用用 S1中的联结词表示的中的联结词表示的等价公式等价公式表示出来。表示出来。则称则称 S 是一个是一个全功能联结词集合全功能联结词集合。2.2.全功能联结词集合全功能联结词集合2022/10/222022/10/223535现在学习的是第35页，共37页1)1)，,，可可以以构构成成功功能能联联结结词词集集合合。使使用用上上述述全全功功能能联联结

28、结词词集集合合表表达达的的命命题公式类的系统常称为题公式类的系统常称为BooleBoole代数系统代数系统2)2)，也也可可构构成成全全功功能能联联结结词词集集合合。该该全全功功能能联联结结词词集集合合在在研研究究逻逻辑辑系系统统的的演演绎绎与与推理，以及在程序系统的研究中经常遇到。推理，以及在程序系统的研究中经常遇到。3)3),是是全全功功能能联联结结词词集集合合。在在大大规规模集成电路中有广泛的应用。模集成电路中有广泛的应用。一些重要的全功能联结词集合一些重要的全功能联结词集合2022/10/222022/10/223636现在学习的是第36页，共37页2022/10/222022/10/223737现在学习的是第37页，共37页