第1章-命题演算ppt课件

第一章 命题演算1.1 命题及联结词可以分辨其真假的语句叫做命题一般用大写字母表示例如：A：中华人民共和国的首都是北京。B：2+45。C：我是大学生。请勿吸烟！x+y5 。这束花多么好看啊！第一章 命题演算1.1 命题及联结词11.1 命题及联结词上述命题也称为原始命题或原子命题。命题的真值有两个即：真（T）和假（F）由复合语句表达的命题叫做复合命题。例如：D：你看书，我也看书。E：灯泡有故障或开关有故障。F：如果你不去，那么我也不去了。1.1 命题及联结词上述命题也称为原始命题或原子命题。21.1 命题及联结词1、否定定义1.1.1 设P是一个命题，我们构造一新命题是原命题的P的否定，称它是命题P的取否命题，表示为 P。如：P：今天下雨。P：今天不下雨。真值表：PPTFFT1.1 命题及联结词1、否定PPTFFT31.1 命题及联结词2、合取定义1.1.2 设P和Q是两个命题，我们构造一新命题“P与Q”，称它是命题P和命题Q的合取命题，表示为P Q。如：P：我将去北京。Q：你将去上海。P Q：我将去北京并且你将去上海。真值表：PQP QTTTTFFFTFFFF1.1 命题及联结词2、合取PQP QTTTTFFFT41.1 命题及联结词3、析取定义1.1.3 设P和Q是两个命题，我们构造一新命题“P或Q”，称它是命题P和命题Q的析取命题，表示为P Q。如：P：灯泡有故障。Q：开关有故障。P Q：灯泡有故障或开关有故障。真值表：PQP QTTTTFTFTTFFF1.1 命题及联结词3、析取PQP QTTTTFTF51.1 命题及联结词上述三个联结词称为基本联结词。4、条件定义1.1.4 设P和Q是两个命题，我们构造一新命题“如果P则Q”，表示为P Q。如：P：你去。Q：我去。P Q：如果你去，则我就去。真值表：PQP QTTTTFFFTTFFT1.1 命题及联结词上述三个联结词称为基本联结词。PQ61.1 命题及联结词5、双条件定义1.1.5 设P和Q是两个命题，我们构造一新命题“P当且仅当Q”，表示为P Q。如：P：两个三角形是全等的。Q：两个三角形的三条对应边相等。P Q：两个三角形全等，当且仅当它们的三条对应边分别相等。真值表：PQP QTTTTFFFTFFFT1.1 命题及联结词5、双条件PQP QTTTTFF71.1 命题及联结词命题公式举例“如果明天不下雨且不下雪，那么我去学校”令：A：明天下雨。B：明天下雪。C：我去学校。则上述命题可表示为：(A)(B)C。五个联结词的强弱顺序为：，所以上式可简写为：A B C 1.1 命题及联结词命题公式举例81.2 命题变元与命题公式在一个命题公式中可能出现三类符号：大写字母，即命题变元。联结符号，。括号（）。如：(P Q)Q。定义 1.2.1（递归定义）命题演算的命题公式（简称公式）规定为：每一个命题变元是命题公式。如果A是命题公式，则A是命题公式。如果A、B是命题公式，则(A B),(A B),(A B),(A B)都是命题公式。一个由三类符号组成的符号串是命题公式，当且仅当是由上述三原则产生。1.2 命题变元与命题公式在一个命题公式中可能出现三类符91.2 命题变元与命题公式(PQ)(QP)的真值表：与P Q的真值表相同，称这两个命题等价。两个真值表相同的命题称为等价。u但真值表有时很大，因此凭真值表是否相同来判断是不现实的，我们还需寻找更多有效方法。PQPQ QQ QP P(PQ)Q)(Q QP)P)TTTTTTFFTFFTTFFFFTTT1.2 命题变元与命题公式(PQ)(QP)的真值表101.3 命题演算的关系式1.3.1命题公式的等价关系定义1.3.1设A和B是两个命题（或命题公式），P1,P2,Pn是A、B中的全部变元，假如P1,P2,Pn，的任意一组取值，A、B的取值都相同，就称A、B是等价的命题，表示为：AB。注意与的区别AB是命题，AB不是命题。AB当且仅当AB为逻辑真。命题等价的三条性质：自反性：AA对称性：若AB，则BA传递性：若AB，BC，则AC1.3 命题演算的关系式1.3.1命题公式的等价关系定义111.3.1命题公式的等价关系一些重要的等价关系（可以用真值表来验证）：等幂率：P P P；P P P结合率：(P Q)R P(QR)；(P Q)R P(Q R)交换率：P Q QP；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 PF吸收率：P(PQ)P；P(P Q)P德.摩根率：(PQ)P Q；(PQ)P Q双重否定率：P P1.3.1命题公式的等价关系一些重要的等价关系（可以用真值表121.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，那么PQ。例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命题公式的等价关系如果公式Q是公式P的一部分则称Q131.3.1命题公式的等价关系可以证明：P Q P QP Q (P Q)(Q P)(P Q)(P Q)例2 证明P(Q R)(P Q)R例3 证明P Q(P Q)P 1.3.1命题公式的等价关系可以证明：141.3.2 命题公式的蕴含关系定义1.3.2 当且仅当命题A B是逻辑真是（即A BT）时，称“A蕴含B”，表示为AB。注意与的区别。蕴含关系的三个性质：自反性：A A反对称性：如果AB，BA，则A B传递性：如果AB，BC，则AC一些重要的命题蕴含关系如果(H1 H2 ,Hm)Q，则H1,H2,Hm称推出Q。定理1.3.2 如果H1,H2,Hm和P推出Q，则H1,H2,Hm推出P Q。（使用例2的结果）1.3.2 命题公式的蕴含关系定义1.3.2 当且仅当命题A15一些重要的命题蕴含关系1P QP2P QQ3P P Q4 PPQ5Q PQ6(PQ)P7(PQ)Q8P(PQ)Q9 Q(PQ)P10 P(P Q)Q11(PQ)(QR)PR12(P Q)(PR)(QR)R一些重要的命题蕴含关系1PQP2PQQ3P PQ161.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命题公式的对偶关系如何一个公式P都可以经过代换化171.3.3命题公式的对偶关系由德.摩根率：可得如下定理：定理1.3.3（对偶定理1）A(P1,P2,Pn)A*(P1,P2,Pn)定理1.3.4（对偶定理）如果AB，则A*B*1.3.3命题公式的对偶关系由德.摩根率：可得如下定理：181.4 其他联结词1、不可兼析取定义1.4.1 设P、Q是两个命题，则称 作P和Q的不可兼析取（异或），的真值为真，当且仅当P与Q的值不同。的真值表：PQTTFTFTFTTFFF1.4 其他联结词1、不可兼析取PQTTFTFTFTTFFF19如：P：李明正在家里学习。Q：李明正在剧场看戏。则“李明正在家里学习或正在剧场看戏”表示成 。异或的性质如：20定理1.4.1 设P，Q，R为命题公式，如果 则 ，Q，且 为矛盾式。证：如果 ，则，定理1.4.1 设P，Q，R为命题公式，如果 211.4 其他联结词2、逆条件逆条件定义1.4.2 设P和Q是两个命题，复合命题 称作命题P和Q的条件否定（逆条件）u 的真值为T，当且仅当P为T，Q为F。真值表：PQTTFTFTFTFFFF1.4 其他联结词2、逆条件PQTTFTFTFTFFFF221.4 其他联结词从定义可知：例如：P：他去。Q：你去。则 ：并非如果他去你就去。1.4 其他联结词从定义可知：231.4 其他联结词3、与非、与非定义1.4.3设P和Q是两个命题，复合命题PQ称作命题P和Q的“与非”。当且仅当P和Q的真值为T时，PQ为F，否则PQ为T PQ的真值表：从定义可知：PQ (PQ)。PQP QTTFTFTFTTFFT1.4 其他联结词3、与非PQPQTTFTFTFTTFFT241.4 其他联结词例如：P：苹果是红的。Q：香蕉是黄的。则 PQ：并非苹果是红的与香蕉是黄的。与非的性质：PP(PP)P(PQ)(PQ)(PQ)PQ(PP)(QQ)PQ(PQ)PQ1.4 其他联结词例如：251.4 其他联结词4、或非 定义1.4.4设P和Q是两个命题，复合命题PQ称作命题P和Q的“或非”。当且仅当P和Q的真值为F时，PQ为T，否则PQ为F。PQ的真值表：从定义可知：PQ(PQ)。PQP QTTFTFFFTFFFT1.4 其他联结词4、或非 PQPQTTFTFFFTFFF261.4 其他联结词例如：P：他在家里。Q：他在做作业。则 PQ：并非他在家里或在做作业。或非的性质：1、PP(PP)P2、(PQ)(PQ)(PQ)PQ3、(PP)(QQ)PQPQ1.4 其他联结词例如：271.4 其他联结词联结词的强弱顺序，1.4 其他联结词联结词的强弱顺序281.5 范式1.5.1 析取范式和合取范式把命题公式化为一个标准形式，这个标准形式就是范式。定义1.5.1 一个命题公式称为析取范式，当且仅当它具有形式 ()，其中 都是命题变元或其否定所组成的合取式。如：P(PQ)(PQR)定义1.5.2 一个命题公式称为合取范式，当且仅当它具有形式 ()，其中 都是命题变元或其否或其否定所组成的析取式。如：(PQR)(PQ)Q。1.5 范式1.5.1 析取范式和合取范式把命题公式化为一291.5.1 析取范式和合取范式求命题公式的析取范式（或合取范式）的三个步骤：1、利用基本等价公式将公式中的联结词化归成，。2、利用德.摩根率将直接移到命题变元之前。3、利用分配率、结合率等将公式归纳为析取范式或合取范式。例1 求(PQ)(PQ)的析取范式。例2 求Q(PQ)(PQ)的合取范式。注：一个公式的析取范式、合取范式不是唯一的。1.5.1 析取范式和合取范式求命题公式的析取范式（或合取范301.5.2 主析取范式和主合取范式要把一个命题公式化成一个唯一等价的标准形式，必须化成为主范式。定义1.5.3 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现，且只出现一次。例如，两个变元P、Q的小项有：PQ，PQ，PQ，PQ ，4个三个变元的小项有8个，n个变元的小项有 个。我们用1代表T，0代表F。1.5.2 主析取范式和主合取范式要把一个命题公式化成一个唯311.5.2 主析取范式和主合取范式表表1.5.2 P、Q、R及其小项真值表及其小项真值表PQRPQRPQRPQRPQR00010000010100010001001100011000000101000011000001110000PQRPQRPQRPQRPQR000000000100000100000011000010010001010100110001011100011.5.2 主析取范式和主合取范式表1.5.2 P、Q、R及321.5.2 主析取范式和主合取范式我们记：PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR1.5.2 主析取范式和主合取范式我们记：331.5.2 主析取范式和主合取范式小项的性质：1、每个小项当其值指派与编码相同时，其真值为T，在其余 -1种指派下为F。2、任意两个不同小项的合取永假。3、全体小项的析取永真。定义1.5.4 对于给定的命题公式，如果有一个等价公式仅由小项所组成，则称该等价式为原式的主析取范式。定理1.5.1 在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。1.5.2 主析取范式和主合取范式小项的性质：341.5.2 主析取范式和主合取范式因此在求一个命题公式的主析取范式时有两种方法：1、真值表法，例3和例4（P20）。2、利用基本等价公式推演法，例5和例6(P21)。利用基本等价公式推演法步骤：1)、化归为析取范式。2)、除去析取范式中所有永假的析取项。3)、将析取式中重复出现的合取项和相同的变元合并。4)、对合取项补入没有出现的命题变元，然后利用分配率展开公式。1.5.2 主析取范式和主合取范式因此在求一个命题公式的主析351.5.2 主析取范式和主合取范式与主析取范式类似的是主合取范式。定义1.5.3 n个命题变元的合取式，称作布尔合取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现，且只出现一次。例如，两个变元P、Q的小项有：PQ，PQ，PQ，PQ ，4个三个变元的大项有8个，n个变元的小项有 个。每个大项用二进制编码（n=2时）：=PQ，=PQ，=PQ，=PQ1.5.2 主析取范式和主合取范式与主析取范式类似的是主合取361.5.2 主析取范式和主合取范式大项的性质：1、每个大项的当其值指派与编码相同时，其真值为F，在其余 -1种指派下为T。2、任意两个不同大项的析取永真。3、全体大项的合取永假。定义1.5.4 对于给定的命题公式，如果有一个等价公式仅由大项所组成，则称该等价式为原式的主合取范式。定理1.5.1 在真值表中，一个公式的真值为F的指派所对应的小项的析取，即为此公式的主合取范式。1.5.2 主析取范式和主合取范式大项的性质：371.5.2 主析取范式和主合取范式因此在求一个命题公式的主合取范式时有两种方法：1、真值表法，例7（P22）。2、利用基本等价公式推演法，例8(P23)。利用基本等价公式推演法步骤：1)、化归为合取范式。2)、除去合取范式中所有永真的合取项。3)、将合取式中重复出现的析取项和相同的变元合并。4)、对析取项补入没有出现的命题变元，然后利用分配律展开公式。1.5.2 主析取范式和主合取范式因此在求一个命题公式的主合381.5.2 主析取范式和主合取范式为了使主析取范式和主合取范式，今后用 表示小项的析取，表示 ，如表示大项的合取，表示 ，如可以证明，如果有n个变元的命题公式P的主析取范式为：则P的主合取范式为：1.5.2 主析取范式和主合取范式为了使主析取范式和主合取范391.6 命题演算的推理命题演算的推理从前提得到结论，要经过一系列的合理推导，叫做“推理”或形式证明。推理的三种基本方法：真值表技术，直接推演，间接推演。1.6 命题演算的推理从前提得到结论，要经过一系列的合理401.6.1 真值表技术真值表技术定义1.6.1 设H1，H2，Hm和C是命题，如果 H1H2HmC，则称从前提H1，H2，Hm推出结论C。例1 确定下面哪些结论C可以由前提H1和H2推出。H1：PQ，H2：Q C：PH2：PQ，H2：Q C：P1.6.1 真值表技术定义1.6.1 设H1，H2，411.6.1 真值表技术真值表技术解：考虑1，当：PQ，：Q同时为T时（最后一行，即H1H2为T），C：P为T，其它情况H1H2为F，所以H1H2C永真，即H1H2C，所以由前提H1和H2可以推出C。PQPQQPTTTFFTFFTFFTTFTFFTTT1.6.1 真值表技术PQPQQPTTTFFTFF421.6.1 真值表技术真值表技术1.6.1 真值表技术43