第1章-命题演算

第一章命题演算§1.1命题及联结词可以分辨其真假的语句叫做命题一般用大写字母表示例如：A：中华人民共和国的首都是北京。√B：2+45。√C：我是大学生。√请勿吸烟！×x+y5。×这束花多么好看啊！ק1.1命题及联结词上述命题也称为原始命题或原子命题。命题的真值有两个即：真（T）和假（F）由复合语句表达的命题叫做复合命题。例如：D：你看书，我也看书。E：灯泡有故障或开关有故障。F：如果你不去，那么我也不去了。§1.1命题及联结词1、否定定义1.1.1设P是一个命题，我们构造一新命题是原命题的P的否定，称它是命题P的取否命题，表示为¬P。如：P：今天下雨。¬P：今天不下雨。真值表：P¬PTFFT§1.1命题及联结词2、合取定义1.1.2设P和Q是两个命题，我们构造一新命题“P与Q”，称它是命题P和命题Q的合取命题，表示为P∧Q。如：P：我将去北京。Q：你将去上海。P∧Q：我将去北京并且你将去上海。真值表：PQP∧QTTTTFFFTFFFF§1.1命题及联结词3、析取定义1.1.3设P和Q是两个命题，我们构造一新命题“P或Q”，称它是命题P和命题Q的析取命题，表示为P∨Q。如：P：灯泡有故障。Q：开关有故障。P∨Q：灯泡有故障或开关有故障。真值表：PQP∨QTTTTFTFTTFFF§1.1命题及联结词◆上述三个联结词称为基本联结词。4、条件定义1.1.4设P和Q是两个命题，我们构造一新命题“如果P则Q”，表示为P→Q。如：P：你去。Q：我去。P→Q：如果你去，则我就去。真值表：PQP→QTTTTFFFTTFFT§1.1命题及联结词5、双条件定义1.1.5设P和Q是两个命题，我们构造一新命题“P当且仅当Q”，表示为P↔Q。如：P：两个三角形是全等的。Q：两个三角形的三条对应边相等。P↔Q：两个三角形全等，当且仅当它们的三条对应边分别相等。真值表：PQP↔QTTTTFFFTFFFT§1.1命题及联结词命题公式举例“如果明天不下雨且不下雪，那么我去学校”令：A：明天下雨。B：明天下雪。C：我去学校。则上述命题可表示为：[(¬A)(¬B)]→C。五个联结词的强弱顺序为：¬，，，→，↔所以上式可简写为：¬A¬B→C§1.2命题变元与命题公式◆在一个命题公式中可能出现三类符号：大写字母，即命题变元。联结符号¬，，，→，↔。括号（）。如：(PQ)→Q。定义1.2.1（递归定义）命题演算的命题公式（简称公式）规定为：①每一个命题变元是命题公式。②如果A是命题公式，则¬A是命题公式。③如果A、B是命题公式，则(AB),(AB),(A→B),(A↔B)都是命题公式。④一个由三类符号组成的符号串是命题公式，当且仅当是由上述三原则产生。§1.2命题变元与命题公式(P→Q)(Q→P)的真值表：与P↔Q的真值表相同，称这两个命题等价。◆两个真值表相同的命题称为等价。但真值表有时很大，因此凭真值表是否相同来判断是不现实的，我们还需寻找更多有效方法。PQP→QQ→P(P→Q)(Q→P)TTTTTTFFTFFTTFFFFTTT§1.3命题演算的关系式1.3.1命题公式的等价关系定义1.3.1设A和B是两个命题（或命题公式），P1,P2,…,Pn是A、B中的全部变元，假如P1,P2,…,Pn，的任意一组取值，A、B的取值都相同，就称A、B是等价的命题，表示为：AB。◆注意与↔的区别①AB是命题，AB不是命题。②AB当且仅当AB为逻辑真。命题等价的三条性质：①自反性：AA②对称性：若AB，则BA③传递性：若AB，BC，则AC1.3.1命题公式的等价关系一些重要的等价关系（可以用真值表来验证）：①等幂率：PPP；PPP②结合率：(PQ)RP(QR)；(PQ)RP(QR)③交换率：PQQP；PQQP④分配率：P(QR)(PQ)(PR)P(QR)(PQ)(PR)⑤同一率：PFP；PTP⑥零元率：PTT；PFF⑦补余率：P¬PT；P¬PF⑧吸收率：P(PQ)P；P(PQ)P⑨德.摩根率：¬(PQ)¬P¬Q；¬(PQ)¬P¬Q⑩双重否定率：¬¬PP1.3.1命题公式的等价关系如果公式Q是公式P的一部分则称Q是P的子公式。如P：A[(A→B)C]，则C，A→B，(A→B)C都是P的子公式。[(A→B)，B)C都不是P的子公式，因为不是公式。定理1.3.1（代换法则）设A是P的一个子公式，AB。如果将P中的子公式代换成公式B之后得到的是公式Q，那么PQ。例1证明(PQ)(P¬Q)P证(PQ)(P¬Q)[(PQ)P][(PQ)¬Q]P[(P¬Q)(Q¬Q)]P[(P¬Q)T]P(P¬Q)P1.3.1命题公式的等价关系●可以证明：①P→Q¬PQ②P↔Q(P→Q)(Q→P)(PQ)(¬P¬Q)例2证明P→(Q→R)(PQ)→R例3证明P↔Q[(PQ)↔P]1.3.2命题公式的蕴含关系定义1.3.2当且仅当命题A→B是逻辑真是（即A→BT）时，称“A蕴含B”，表示为AB。◆注意与→的区别。◆蕴含关系的三个性质：①自反性：AA②反对称性：如果AB，BA，则AB③传递性：如果AB，BC，则AC一些重要的命题蕴含关系◆如果(H1H2…,Hm)Q，则H1,H2,…,Hm称推出Q。定理1.3.2如果H1,H2,…,Hm和P推出Q，则H1,H2,…,Hm推出P→Q。（使用例2的结果）一些重要的命题蕴含关系1PQP2PQQ3PPQ4PPQ5QPQ6(PQ)P7(PQ)Q8P(PQ)Q9Q(PQ)P10P(PQ)Q11(PQ)(QR)PR12(PQ)(PR)(QR)R1.3.3命题公式的对偶关系◆如何一个公式P都可以经过代换化成一个只含有¬，，三个基本联结符的公式P。◆因此本节考虑只含有三个基本联结符的公式。对偶：用“*”来表示。*=，*=，¬*=¬T*=F,F*=T定义1.3.3设A(P1,P2,…,Pn)是一个命题公式，其中P1,P2,…,Pn是公式中的所有命题变元，如果将A中基本联结词及T和F改为其对偶，其余不变，所得到的新公式称作原公式的对偶，表示成A*(P1,P2,…,Pn)。显然(A*)*=A。1.3.3命题公式的对偶关系由德.摩根率：可得如下定理：定理1.3.3（对偶定理1）¬A(P1,P2,…,Pn)A*(¬P1,¬P2,…,¬Pn)定理1.3.4（对偶定理）如果AB，则A*B*1.4其他联结词1、不可兼析取定义1.4.1设P、Q是两个命题，则称作P和Q的不可兼析取（异或），的真值为真，当且仅当P与Q的值不同。的真值表：PQTTFTFTFTTFFF如：P：李明正在家里学习。Q：李明正在剧场看戏。则“李明正在家里学习或正在剧场看戏”表示成。异或的性质定理1.4.1设P，Q，R为命题公式，如果则，，Q，且为矛盾式。证：如果，则，1.4其他联结词2、逆条件定义1.4.2设P和Q是两个命题，复合命题称作命题P和Q的条件否定（逆条件）的真值为T，当且仅当P为T，Q为F。真值表：PQTTFTFTFTFFFF1.4其他联结词从定义可知：例如：P：他去。Q：你去。则：并非如果他去你就去。1.4其他联结词3、与非定义1.4.3设P和Q是两个命题，复合命题PQ称作命题P和Q的“与非”。◆当且仅当P和Q的真值为T时，PQ为F，否则PQ为TPQ的真值表：从定义可知：PQ¬(PQ)。PQPQTTFTFTFTTFFT1.4其他联结词例如：P：苹果是红的。Q：香蕉是黄的。则PQ：并非苹果是红的与香蕉是黄的。与非的性质：①PP¬(PP)¬P②(PQ)(PQ)¬(PQ)PQ③(PP)(QQ)¬P¬Q¬(¬P¬Q)PQ1.4其他联结词4、或非定义1.4.4设P和Q是两个命题，复合命题PQ称作命题P和Q的“或非”。◆当且仅当P和Q的真值为F时，PQ为T，否则PQ为F。PQ的真值表：从定义可知：PQ¬(PQ)。PQPQTTFTFFFTFFFT1.4其他联结词例如：P：他在家里。Q：他在做作业。则PQ：并非他在家里或在做作业。或非的性质：1、PP¬(PP)¬P2、(PQ)(PQ)¬(PQ)PQ3、(PP)(QQ)¬P¬QPQ1.4其他联结词•联结词的强弱顺序•¬••，，，•，•↔强弱1.5范式1.5.1析取范式和合取范式把命题公式化为一个标准形式，这个标准形式就是范式。定义1.5.1一个命题公式称为析取范式，当且仅当它具有形式()，其中都是命题变元或其否定所组成的合取式。如：¬P(PQ)(P¬QR)定义1.5.2一个命题公式称为合取范式，当且仅当它具有形式()，其中都是命题变元或其否定所组成的析取式。如：(P¬Q¬R)(¬PQ)¬Q。1.5.1析取范式和合取范式•求命题公式的析取范式（或合取范式）的三个步骤：1、利用基本等价公式将公式中的联结词化归成，，¬。2、利用德.摩根率将¬直接移到命题变元之前。3、利用分配率、结合率等将公式归纳为析取范式或合取范式。例1求¬(PQ)↔(PQ)的析取范式。例2求Q¬(PQ)¬(PQ)的合取范式。•注：一个公式的析取范式、合取范式不是唯一的。1.5.2主析取范式和主合取范式•要把一个命题公式化成一个唯一等价的标准形式，必须化成为主范式。•定义1.5.3n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现，且只出现一次。•例如，两个变元P、Q的小项有：•PQ，P¬Q，¬PQ，¬P¬Q，4个•三个变元的小项有8个，n个变元的小项有个。•我们用1代表T，0代表F。1.5.2主析取范式和主合取范式表1.5.2P、Q、R及其小项真值表PQR¬P¬Q¬R¬P¬QR¬PQ¬R¬PQR00010000010100010001001100011000000101000011000001110000PQRP¬Q¬RP¬QRPQ¬RPQR000000000100000100000011000010010001010100110001011100011.5.2主析取范式和主合取范式•我们记：•¬P¬Q¬R，¬P¬QR，•¬PQ¬R，¬PQR，•P¬Q¬R，P¬QR，•PQ¬R，PQR1.5.2主析取范式和主合取范式•小项的性质：1、每个小项当其值指派与编码相同时，其真值为T，在其余-1种指派下为F。2、任意两个不同小项的合取永假。3、全体小项的析取永真。•定义1.5.4对于给定的命题公式，如果有一个等价公式仅由小项所组成，则称该等价式为原式的主析取范式。•定理1.5.1在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。1.5.2主析取范式和主合取范式•因此在求一个命题公式的主析取范式时有两种方法：1、真值表法，例3和例4（P20）。2、利用基本等价公式推演法，例5和例6(P21)。•利用基本等价公式推演法步骤：1)、化归为析取范式。2)、除去析取范式中所有永假的析取项。3)、将析取式中重复出现的合取项和相同的变元合并。4)、对合取项补入没有出现的命题变元，然后利用分配率展开公式。1.5.2主析取范式和主合取范式•与主析取范式类似的是主合取范式。•定义1.5.3n个命题变元的合取式，称作布尔合取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现，且只出现一次。•例如，两个变元P、Q的小项有：•PQ，P¬Q，¬PQ，¬P¬Q，4个•三个变元的大项有8个，n个变元的小项有个。•每个大项用二进制编码（n