第3章命题逻辑精选PPT.ppt

第第3章命题逻辑章命题逻辑2023/4/161第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)2023/4/162023/4/162 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)2023/4/162023/4/163 3第3页，本讲稿共37页一般来说，命题可分两种类型：一般来说，命题可分两种类型：命题的分类命题的分类原子命题原子命题(简单命题简单命题)：不能再：不能再分解分解为更为简单命为更为简单命 题的命题。题的命题。复合命题复合命题：可以：可以分解分解为更为简单命题的命题。或者说为更为简单命题的命题。或者说由简单命题经由简单命题经命题联结词命题联结词复合而成的命题。复合而成的命题。例如例如:今天下雨。今天下雨。例如例如:今天下雨并且刮风。今天下雨并且刮风。命题的表示命题的表示通常用通常用大写的带或不带下标的英文字母大写的带或不带下标的英文字母,.,Ai,Bi,Ci,.等表示命题等表示命题.2023/4/162023/4/164 4第4页，本讲稿共37页5.1.2 5.1.2 命题联结词命题联结词联接词联接词记号记号记法记法 (基本意思基本意思)真值结果真值结果否定否定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同为真假同为真假2023/4/162023/4/165 5第5页，本讲稿共37页例例1 1.2 2 用复合命题表示如下图所示的开关电路用复合命题表示如下图所示的开关电路图5-1 图5-2 图5-3ABABA设：设：开关闭合；：开关闭合。：开关闭合；：开关闭合。2023/4/162023/4/166 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（续）续）2023/4/162023/4/167 7第7页，本讲稿共37页约定约定:1.命题联结词之命题联结词之优先级优先级如下：如下：否定否定合取合取析取析取蕴涵蕴涵等价等价 2.2.若运算要求与优先次序不一致时，可使用若运算要求与优先次序不一致时，可使用圆括号圆括号.例例1.3 设命题设命题 P：明天上午七点下雨；：明天上午七点下雨；Q：明天上午七点下雪；：明天上午七点下雪；R：我将去学校。：我将去学校。符号化下述语句：符号化下述语句：1.如果明天上午七点不是雨夹雪，则我将去学校。如果明天上午七点不是雨夹雪，则我将去学校。2.如果明天上午七点不下雨并且不下雪，则我将去学校。如果明天上午七点不下雨并且不下雪，则我将去学校。3.明天上午七点下雨或下雪，当且仅当我将不去学校。明天上午七点下雨或下雪，当且仅当我将不去学校。4.明天上午我将雨雪无阻一定去学校。明天上午我将雨雪无阻一定去学校。2023/4/162023/4/168 8第8页，本讲稿共37页解：解：1.如果明天上午七点不是雨夹雪，则我将去学校。如果明天上午七点不是雨夹雪，则我将去学校。可符号化为：可符号化为：(PQ)R。2.如果明天上午七点不下雨并且不下雪，则我将去学校。如果明天上午七点不下雨并且不下雪，则我将去学校。可符号化为可符号化为:(PQ)R。3.明天上午七点下雨或下雪，当且仅当我将不去学校。明天上午七点下雨或下雪，当且仅当我将不去学校。可符号化为可符号化为:(PQ)R。4.明天上午我将雨雪无阻一定去学校。明天上午我将雨雪无阻一定去学校。可符号化为：可符号化为：(PQR)(PQR)(PQR)(PQR)。或或(PQ)(PQ)(PQ)(PQ)R。2023/4/162023/4/169 9第9页，本讲稿共37页例例1 1.4 4 符号化语句：符号化语句：除非你陪伴我或代我叫车子，否则我将不出除非你陪伴我或代我叫车子，否则我将不出去。去。则则句子可符号化为：句子可符号化为：(PQ)R 或或 R(PQ)解：解：设命题设命题 P：你陪伴我；：你陪伴我；Q：你代我叫车子；：你代我叫车子；R：我将出去。：我将出去。2023/4/162023/4/161010第10页，本讲稿共37页定义定义5.7 一个特定的命题是一个一个特定的命题是一个常值命题常值命题，它不是，它不是具有值具有值“T”(“1”)，就是具有值，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为一个变量命题，常称它为命题变量命题变量(或或命题变元命题变元);命题变量无具体的真值，命题变量无具体的真值，其其变域是集合变域是集合 T，F(或或0，1)。说明说明 含有命题变元的含有命题变元的原子原子或复合命题实际上是或复合命题实际上是命题变元的命题变元的“函数函数”，可称为，可称为“真值函数真值函数”，或称或称为为命题公式命题公式，命题公式没有确，命题公式没有确切切真值。真值。5.2命题公式、解释与真值表命题公式、解释与真值表2023/4/162023/4/161111第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、等表示。等表示。2023/4/162023/4/161212第12页，本讲稿共37页符号串：符号串：(PQ)；(P(PQ)；(PQ)(RQ)(PR)；(P(QR)(Q(SR)。等都是命题公式。例例2.2符号串：符号串：PQ,(P Q)；P(QR),(PQ)Q)等都不是合法的命题公式。例例2.12.12023/4/162023/4/161313第13页，本讲稿共37页5.2.2 5.2.2 公式的解释与真值表公式的解释与真值表定义定义5.9设命题变元设命题变元P1,P2,P3,Pn是出是出现在公式现在公式G中的所有命题变元，指定中的所有命题变元，指定P1,P2,P3,Pn一组真值，则这组真值称为一组真值，则这组真值称为G 的一个的一个解释解释,常记为常记为。一般来说，若有一般来说，若有 n个命题变元，则应有个命题变元，则应有2n个不个不同的解释。同的解释。定义定义5.10公式公式G在其所有可能的解释下所取在其所有可能的解释下所取真值的表，称为的真值的表，称为的真值表真值表。2023/4/162023/4/161414第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 Q10012023/4/162023/4/161515第15页，本讲稿共37页设设有有公公式式：G(PQ)R其其中中，P、Q、R是是G的所有命题变元，则其真值表如下：的所有命题变元，则其真值表如下：PQRP Q(P Q)R0000100101010010110110001101011101011111例例2 2.2 22023/4/162023/4/161616第16页，本讲稿共37页该真值表可简化为：该真值表可简化为：PQR(P Q)R00010011010101111001101111001111例例2 2.2 2（续）续）2023/4/162023/4/161717第17页，本讲稿共37页 5.2.3-4 5.2.3-4 一些特殊的公式一些特殊的公式,等价公式等价公式例例3.1 考虑考虑(PQ)P 的真值表。的真值表。解解 真值表为真值表为:PQPQ(PQ)(PQ)P00101011011001111101注注:该公式对所有可能的解释均有该公式对所有可能的解释均有“真真”值值1.公式类型公式类型2023/4/162023/4/161818第18页，本讲稿共37页定定义义5.11(1)公公式式 G 称称为为永永真真公公式式(重重言言式式)，如如果在它的所有解释之下都为果在它的所有解释之下都为“真真”。(2)公式公式G 称为称为永假公式永假公式(矛盾式矛盾式),如果在它的所如果在它的所 有解释之下都为有解释之下都为“假假”。(3)公式公式 G 称为称为可满足的可满足的，如果它不是永假的。，如果它不是永假的。关系关系(1)永真式的否定是矛盾式；矛盾式的否定是永真式。永真式的否定是矛盾式；矛盾式的否定是永真式。(2)永真式一定是可满足式。永真式一定是可满足式。两个术语两个术语：如果公式如果公式G 在解释在解释下是真的，则称下是真的，则称 满足满足 G；如果；如果G 在解释在解释下是假的，则下是假的，则称称弄假弄假G。2023/4/162023/4/161919第19页，本讲稿共37页例例3.2 列出真值表，验证下列公式是否是永真公式。列出真值表，验证下列公式是否是永真公式。(1)(PQ)P)Q；(2)(P Q)(P Q)P QPQ(PQ)P(PQ)P)Q0 01010 11011 00011 1111解解 的真值表如下的真值表如下从上述真值表知从上述真值表知(1)(1)是永真公式。是永真公式。2023/4/162023/4/162020第20页，本讲稿共37页(2)(2)(P Q)(P Q)的真值表如下：的真值表如下：从上述真值表知从上述真值表知是永真公式。是永真公式。P Q P Q(P Q)P QP Q 原式原式0 00111110 11010011 01001011 1100001例例3.23.2（续）（续）2023/4/162023/4/162121第21页，本讲稿共37页定定义义5.12公公式式G、H说说是是等等价价的的(Equivalent)，记记作作GH，如如果果在其任意的解释下，其真值相同。在其任意的解释下，其真值相同。定理定理5.1 公式公式G、H 等价的充分必要条件是公式等价的充分必要条件是公式GH 是永真公式。是永真公式。证证明明 “”假假定定G，H 等等价价，则则G，H在在其其任任意意解解释释下下或或同同为为真真或或同同为为假假，于于是是由由“”的的意意义义知知，GH在在下下为为“真真”，由由的任意性的任意性 GH 为永真公式。为永真公式。“”假假定定公公式式GH是是永永真真公公式式，则则对对任任意意的的解解释释，GH 均均为为真真，因因此此，G、H或或同同为为真真，或或同同为为假假，由由的的任任意性，故有意性，故有GH。2.2.等价公式等价公式2023/4/162023/4/162222第22页，本讲稿共37页2.2.=与与 的区别的区别:说明说明 1.1.定理定理5.1表明表明:G=H GH 是永真公式是永真公式;这这是符号是符号=与与 的联系的联系.（1）“”是逻辑联结词，是逻辑联结词，而而“”是关系是关系符符.若若G,H 是命题公式，是命题公式，则则 GH 仍是一个命题公式仍是一个命题公式;而而GH 却不却不是命题公式是命题公式。（2）如果要用计算机来判断如果要用计算机来判断是否是否有有 G H，直接，直接“计算计算”那是办不到的那是办不到的，然而计算机却可然而计算机却可通过通过“计算计算”公式公式 GH 是否是永真公式是否是永真公式而达目的而达目的。2023/4/162023/4/162323第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取代取代P2、Gn取代取代Pn后，而得到的新的命后，而得到的新的命题题公式：公式：G(G1,G2,Gn)G(P1,P2,Pn)也是一个永真公式或永假公式。也是一个永真公式或永假公式。3.3.两个两个定理定理2023/4/162023/4/162424第24页，本讲稿共37页定定理理5 5.3.3(替替换换定定理理 )若若G1是是G的的子子公公式式(即即 G1是是公公式式G的的一一部部分分)，H1是是任任意意的的命命题题公公式式，设设在在G中中凡凡出出现现G1处处都都以以H1替替换换后后得得到到新新的的命命题题公式公式为为H，若，若G1H1，则，则GH。4.基本等价公式基本等价公式设设G，H，S 是任意的公式，则：是任意的公式，则：(1)1:G(HS)(GH)S 2：G(HS)(GH)S (结合律结合律)2023/4/162023/4/162525第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 (同一律同一律)2023/4/162023/4/162626第26页，本讲稿共37页(7)13：G 14：G (零律零律)(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)(蕴涵蕴涵)基本等价公式（续）基本等价公式（续）2023/4/162023/4/162727第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)T所以所以,原式是永真公式。原式是永真公式。2023/4/162023/4/162828第28页，本讲稿共37页例例3.5 证明证明 P(QR)(PQ)R证证 左边左边 P(QR)(PQ)R (PQ)R (PQ)R例3.6 试用较少的开关设计一个与右图有相同功能的电路。2023/4/162023/4/162929第29页，本讲稿共37页解解 可可将将图图中中所所示示之之开开关关电电路路用用下下述述命命题题公公式表示为：式表示为：(PQS)(PRS)而上述公式而上述公式 (PQS)(PRS)(PS)Q)(PS)R)(PS)(QR)所以开关设计图可简化为：所以开关设计图可简化为：2023/4/162023/4/163030第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 Y2023/4/162023/4/163131第31页，本讲稿共37页从框图可知：执行从框图可知：执行X的条件为：的条件为：()()()STARTABBXYEND执行执行Y的条件为：的条件为：()()()经转换后，这段程经转换后，这段程序可简化：序可简化：If B then X else Y其流程图如下图。其流程图如下图。STARTENDBXY2023/4/162023/4/163232第32页，本讲稿共37页5.3 5.3 联结词的完备集联结词的完备集1.1.其它联结词其它联结词 除除了了包包含含五五个个基基本本联联结结词词外外，引引进进如如下下几几个个联联结结词。词。联结词联结词记号记号复合命题复合命题读法读法记法记法异或异或A不可兼或不可兼或BA异或异或BA B蕴涵否定蕴涵否定A,B蕴涵否定蕴涵否定A蕴涵否定蕴涵否定BA B与非与非A和和B的与非的与非A与非与非BAB或非或非A和和B的或非的或非A或非或非BAB2023/4/162023/4/163333第33页，本讲稿共37页其真值结果如下：其真值结果如下：ABA B A B ABAB000011011010101110110000性质性质:(1)(1)A B=(A B)(2)(2)A B=(A B)(3)(3)A B=(A B)(4)(4)A B=(A B)2023/4/162023/4/163434第34页，本讲稿共37页定义定义5.13设设S是联结词集合，如果是联结词集合，如果 (1)用用S 中中的的联联结结词词表表示示的的等等价价公公式式，可可以以表表示任何命题公式。示任何命题公式。(2)从从S中中删删除除任任何何一一个个联联结结词词而而得得到到的的新新联联结结词词集集合合S1,至至少少存存在在一一个个命命题题公公式式不不能能用用 S1中的联结词表示的中的联结词表示的等价公式等价公式表示出来。表示出来。则称则称 S 是一个是一个全功能联结词集合全功能联结词集合。2.2.全功能联结词集合全功能联结词集合2023/4/162023/4/163535第35页，本讲稿共37页1)1)，,，可可以以构构成成功功能能联联结结词词集集合合。使使用用上上述述全全功功能能联联结结词词集集合合表表达达的的命命题公式类的系统常称为题公式类的系统常称为BooleBoole代数系统代数系统2)2)，也也可可构构成成全全功功能能联联结结词词集集合合。该该全全功功能能联联结结词词集集合合在在研研究究逻逻辑辑系系统统的的演演绎绎与与推理，以及在程序系统的研究中经常遇到。推理，以及在程序系统的研究中经常遇到。3)3),是是全全功功能能联联结结词词集集合合。在在大大规规模集成电路中有广泛的应用。模集成电路中有广泛的应用。一些重要的全功能联结词集合一些重要的全功能联结词集合2023/4/162023/4/163636第36页，本讲稿共37页2023/4/162023/4/163737第37页，本讲稿共37页