第一章--命题逻辑分析课件

第一章第一章 命题逻辑命题逻辑 Proposition LogicProposition Logic1.1 命题及其表示法命题及其表示法1.2 联结词联结词1.3 命题公式与翻译命题公式与翻译1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式1.5 等价与蕴含等价与蕴含1.6 其它联结词其它联结词1.7 对偶与范式对偶与范式1.8 推理理论推理理论7/5/20241chapter1第一章 命题逻辑 Proposition Logic1.PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.1 命题及其表示法命题及其表示法1、命题、命题命题命题非真即假的陈述句。非真即假的陈述句。命题的真值命题的真值对，成立，则真值为真，对，成立，则真值为真，T，1 错，不成立，则真值为假，错，不成立，则真值为假，F，0 断言断言是一陈述语句。一个命题命题是一个或真或假而不能两者都是的断言。如果命题是真,我们说它的真值真值为真真；如果命题是假，我们说它的真值真值是假假。7/5/20242chapter1 1.1 命题及其表示法1、命题命题的真值对，成立，则真值PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例1】判定下列各语句是否为命题：判定下列各语句是否为命题：(a)巴黎在法国。巴黎在法国。(b)煤是白色的。煤是白色的。(c)3+2=5(d)别的星球上有生物。别的星球上有生物。(e)全体立正。全体立正。(f)明天是否开大会？明天是否开大会？(g)天气多好啊！天气多好啊！(h)我正在说谎。我正在说谎。(i)如果天气好，那么我去散步。如果天气好，那么我去散步。(j)x3（是）（是）（是）（是）（是）（是）（是）（是）（否，祈使句）（否，祈使句）（否，疑问句）（否，疑问句）（否，感叹句）（否，感叹句）（否（否,悖论）悖论）（是（是,复合命题）复合命题）（否，不能确定真值）（否，不能确定真值）1.1 1.1 命题及其表示法命题及其表示法命题及其表示法命题及其表示法7/5/20243chapter1【例1】判定下列各语句是否为命题：（是）（是）（是）（是）PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、命题的表示、命题的表示命题变元命题变元常用常用P、Q、R、S等大写字母或加下标的大等大写字母或加下标的大写字母写字母P1,Q2,R10,表示来表示一个命题，称为命题表示来表示一个命题，称为命题变元。变元。如：如：P:巴黎在法国。巴黎在法国。Q:煤是白色的。煤是白色的。1.1 1.1 命题及其表示法命题及其表示法命题及其表示法命题及其表示法7/5/20244chapter12、命题的表示 1.1 命题及其表示法8/13/20234PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 3、命题相关概念、命题相关概念简单命题（原子命题）简单命题（原子命题）不能再分解的命题。不能再分解的命题。复合命题复合命题由若干个简单命题复合而成的命题。由若干个简单命题复合而成的命题。真值表真值表把组成复合命题的各命题变元的真值的所有把组成复合命题的各命题变元的真值的所有组合及其相对应的复合命题的真值列成表，称为真值表。组合及其相对应的复合命题的真值列成表，称为真值表。1.1 命题及其表示法命题及其表示法7/5/20245chapter13、命题相关概念 1.1 命题及其表示法8/13/2023PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例2】求公式求公式(PQ)P的真值表。的真值表。解：解：分以下步求得分以下步求得:(1)写出公式写出公式P的真值表的真值表;(2)写出公式写出公式PQ的真值表的真值表;(3)根据根据(1)和和(2),写出公式写出公式(PQ)P的真值表。的真值表。为清楚起见为清楚起见,我们将这步列在一个表内我们将这步列在一个表内,见下表。见下表。1.1 命题及其表示法命题及其表示法7/5/20246chapter1【例2】求公式(PQ)P的真值表。1.1 命题PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例3】求公式求公式(PR)(QR)的真值表。的真值表。解：解：公式含有个命题变元公式含有个命题变元P、Q、R,真值表有真值表有3=8行。其真值表如下表行。其真值表如下表 所示：所示：1.1 命题及其表示法命题及其表示法7/5/20247chapter1【例3】求公式(PR)(QR)的真值表。1.1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.2 1.2 联结词联结词联结词联结词 命题和原子命题常可通过一些联结词构成新命题,这种新命题叫复复合合命命题题（Compositional Proposition）。例如：P:明天下雪,Q:明天下雨是两个命题,利用联结词“不”,“并且”,“或”等可构成新命题:“明天不下雪”；“明天下雪并且下雨”；“明天下雪或下雨”等。7/5/20248chapter1 1.2 联结词 命题和原子命题常可通过一些PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.2 联结词联结词即：“非P”；“P并且Q”；“P或Q”等。在代数式x+3 中,x,3 叫运算对象,+叫运算符,x+3 表示运算结果。在命题演算中,联联结结词词就是命题演算中的运算符,叫逻逻辑辑运运算算符符或叫逻逻辑辑联联结结词词。常用的有以下 5 个。7/5/20249chapter1 1.2 联结词即：8/13/20239chapter1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1、否定、否定 P是是P的否定，读作的否定，读作“非非P”，“P的否定的否定”。0110p如：如：P:成都是中国的首都。成都是中国的首都。P：成都不是中国的首都。：成都不是中国的首都。否定与汉语中的否定与汉语中的“非非”、“不是不是”、“否定否定”是一致是一致的。的。1.2 联结词联结词7/5/202410chapter11、否定 0110p如：P:成都是中国的首都。1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、合取、合取 PQ是是P和和Q的合取的合取,读做读做“P与与Q”或或“P并且并且Q”。如：如：P:王华的成绩很好。王华的成绩很好。Q:王华的品德很好。王华的品德很好。PQ:王华的成绩很好并且品德很好。王华的成绩很好并且品德很好。合取与汉语中的合取与汉语中的“和和”、“与与”、“并且并且”是一致的。是一致的。P QP Q0 00 11 01 10001 1.2 联结词联结词7/5/202411chapter12、合取 如：P:王华的成绩很好。P PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 3、析取、析取 PQ是是P和和Q的析取的析取,读做读做“P或或Q”。如：如：P:小王喜欢唱歌。小王喜欢唱歌。Q:小王喜欢跳舞小王喜欢跳舞。P Q:小王喜欢唱歌或喜欢跳舞小王喜欢唱歌或喜欢跳舞。从真值表可知从真值表可知PQ为真为真,当且仅当当且仅当P或或Q至少有一为真。至少有一为真。P QP Q0 00 11 01 10111 1.2 联结词联结词7/5/202412chapter13、析取 如：P:小王喜欢唱歌。P PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 “或”字常见的含义有两种:一种是“可兼或可兼或”,如上例中的或,它不排除小王既喜欢唱歌又喜欢跳舞这种情况。一种是“排斥或排斥或”（异或）（异或）,例如“人固有一死,或重于泰山,或轻于鸿毛”中的“或”,它表示非此即彼,不可兼得。运算符运算符表示可兼或表示可兼或,排斥或以后用另一符号表达。排斥或以后用另一符号表达。如：(1)小李明天出差去上海或去广州。(2)刘昕这次考试可能是全班第一也可能是全班第二。这两例表示的均是排斥或，即两种情况不能同时出现，这时便不能仅用析取词表示。1.2 联结词联结词7/5/202413chapter1 “或”字常见的含义有两种:一种是“可兼或”,如上PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 4、条件、条件 PQ,读做读做“如果如果P,那么那么Q”或或“P则则Q”。运算对象运算对象P叫做前提叫做前提,假设或前件假设或前件,而而Q叫做结论或后件。叫做结论或后件。P QP Q0 00 11 01 11101 1.2 联结词联结词如：如：P:雪是黑的。雪是黑的。Q:太阳从东方升起太阳从东方升起。P Q:如果雪是黑的，则太阳从东方升起如果雪是黑的，则太阳从东方升起。命题命题PQ是假是假,当且仅当当且仅当P是真而是真而Q是假。是假。7/5/202414chapter14、条件 P QP QPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 条件与汉语中条件与汉语中“如果如果，就，就”相类似，但有所区相类似，但有所区别别:(1)自然语言中，自然语言中，“如果如果P则则Q”，往往，往往P和和Q有一定的因果有一定的因果关系，而条件复合命题关系，而条件复合命题PQ中中 P和和Q 可以完全不相关。可以完全不相关。(2)自然语言中，自然语言中，“如果如果P则则Q”，当，当P为为0、Q为为1时，整个时，整个句子真值难以确定；而条件复合命题句子真值难以确定；而条件复合命题PQ中，当中，当P为为0时，时，复合命题的真值为复合命题的真值为1。P则则Q的逻辑含义的逻辑含义:P是是Q的充分条件的充分条件,Q是是P的必要条件。的必要条件。所以所以,“如果如果P则则Q”,“只要只要P则则Q”,只有只有Q才才P”,“仅当仅当Q则则P”都可符号化为都可符号化为PQ 的形式。的形式。1.2 联结词联结词7/5/202415chapter1 条件与汉语中“如果，就”相类似，但有所区别:1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 如：小李对小王说：如：小李对小王说：“如果天不下雨，我就来找你如果天不下雨，我就来找你”。天没下雨，小李去找了小王。天没下雨，小李去找了小王。天没下雨，小李没去找小王。天没下雨，小李没去找小王。天下雨了，小李去找了小王。天下雨了，小李去找了小王。天下雨了，小李没去找小王。天下雨了，小李没去找小王。1.2 联结词联结词【例【例4】电灯不亮是电灯坏或电路有毛病。】电灯不亮是电灯坏或电路有毛病。解：设解：设P电灯不亮，电灯不亮，Q电灯坏，电灯坏，R电路有毛病。电路有毛病。上述语句应表示为上述语句应表示为:(Q R)P7/5/202416chapter1如：小李对小王说：“如果天不下雨，我就来找你”。1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 5、双条件、双条件 P Q,读做读做“P当且仅当当且仅当Q”。如：如：P:两个三角形全等。两个三角形全等。Q:两个三角形的对应边相等两个三角形的对应边相等。P Q:两个三角形全等当且仅当其对应边相等两个三角形全等当且仅当其对应边相等。P当且仅当当且仅当Q的逻辑含义的逻辑含义:P和和Q互为充要条件互为充要条件。P QP Q0 00 11 01 11001 1.2 联结词联结词7/5/202417chapter15、双条件 如：P:两个三角形全等。P PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 6、联结词的优先次序、联结词的优先次序联结词的优先级：联结词的优先级：,，括号优先。，括号优先。如：如：(PQ)R 可写成可写成：PQR (PQ)R 可写成：可写成：PQR (P Q)R)(RP)Q)可写成：可写成：(P QR)RPQ 为方便起见，公式最外层的括号可省略。有时为了为方便起见，公式最外层的括号可省略。有时为了看起来清楚醒目看起来清楚醒目,也可保留某些原可省去的括号。也可保留某些原可省去的括号。1.2 联结词联结词7/5/202418chapter1 6、联结词的优先次序 1.2 联结词8/13/2023PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 单单个个命命题题变变元元和和命命题题常常元元叫叫原原子子公公式式。由以下形成规则生成的公式叫命题公式命题公式(简称公式简称公式):(1)单个原子公式单个原子公式A、B是命题公式。是命题公式。(2)如如果果A和和B是是命命题题公公式式,则则(A),(AB),(AB),(AB),(AB)是命题公式。是命题公式。(3)只只有有有有限限步步使使用用(1)和和(2)所所组组成成的的包包含含命命题题变变元元、联结词以及成对的括号组成的符号串才是命题公式。联结词以及成对的括号组成的符号串才是命题公式。这种定义叫归纳定义,也叫递归定义。由这种定义产生的公式也叫合合式式公公式式（Well-Formed Formulas），简简写为写为wff。1.3 命题公式命题公式7/5/202419chapter1 单个命题变元和命题常元叫原子公式。由以下PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例5】判断下列表达式是否为合式公式判断下列表达式是否为合式公式:p(pq)(pq)r)(p(qr)(pq)(qr)(pq)r)(pq)r)s)(pq)r)s（是）（是）（是）（是）（否）（否）（否）（否）（否）（否）（是）（是）（是）（是）1.3 命题公式命题公式7/5/202420chapter1【例5】判断下列表达式是否为合式公式:（是）（是）（否）（PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例例6】将下列自然语言形式化将下列自然语言形式化:(a)如果天不下雨并且不刮风，我就去书店。如果天不下雨并且不刮风，我就去书店。解解：设：设P：今天天下雨，：今天天下雨，Q：今天天刮风，：今天天刮风，R：我去书店。：我去书店。则原命题符号化为：则原命题符号化为：(PQ)R(b)小王边走边唱。小王边走边唱。解：设解：设p：小王走路，：小王走路，q：小王唱歌。：小王唱歌。则原命题符号化为：则原命题符号化为：pq(c)除非除非a能被能被2整除，否则整除，否则a不能被不能被4整除。整除。解：设解：设p：a能被能被2整除，整除，q：a能被能被4整除。整除。则原命题符号化为：则原命题符号化为：p q 或或 q p1.3 命题公式命题公式7/5/202421chapter1 【例6】将下列自然语言形式化:1.3 命题公式8/1PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 (d)此时，小刚要么在学习，要么在玩游戏。此时，小刚要么在学习，要么在玩游戏。解：设解：设p：小刚在学习，：小刚在学习，q：小刚在玩游戏。：小刚在玩游戏。则原命题符号化为：则原命题符号化为：(pq)(pq)或或 (pq)(pq)(e)如果天不下雨，我们去打篮球，除非班上有会。如果天不下雨，我们去打篮球，除非班上有会。解：设解：设p：今天天下雨，：今天天下雨，q：我们去打篮球，：我们去打篮球，r：今天班上：今天班上有会。有会。则原命题符号化为：则原命题符号化为：r (p q)1.3 命题公式命题公式7/5/202422chapter1 (d)此时，小刚要么在学习，要么在玩游戏。1.3 命PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1、重言式（重言式（Tautology）重言式重言式(永真式永真式)真值恒为真值恒为1的公式。如：的公式。如：PP【例例7】判断判断（P P(P Q)）是否为重言式。）是否为重言式。P QPQP(PQ)P P(PQ)0 00 11 01 10 0 010 0 111 1 11（P P(P Q)）为重言式。）为重言式。1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式7/5/202423chapter1 1、重言式（Tautology）P QPQPPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、矛盾式（矛盾式（Contradiction)矛盾式（永假式）矛盾式（永假式）真值恒为真值恒为0的公式。如：的公式。如：P P【例例8】判断判断(PQ)P是否为矛盾式。是否为矛盾式。P QPQ(PQ)P0 00 11 01 10 0 010 0 00（(PQ)P）为矛盾式。）为矛盾式。1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式7/5/202424chapter1 2、矛盾式（Contradiction)P QPPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 3、可满足公式（可满足公式（Satisfaction）可满足公式可满足公式至少有一种真值为至少有一种真值为1的情况。的情况。(除矛盾式之外的公式除矛盾式之外的公式)，永真式也是可满足公式。，永真式也是可满足公式。定理：由定理：由n个命题变元一共可组成个命题变元一共可组成 个不同的命题。其中个不同的命题。其中永真式有一个，矛盾式有一个，可满足公式有永真式有一个，矛盾式有一个，可满足公式有 个。个。1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式7/5/202425chapter13、可满足公式（Satisfaction）定理：由n个命题PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例9】构造公式构造公式PQ、(PQ)、PQ、Q P的真值的真值。解：真值表如下：解：真值表如下：由例题可见，公式由例题可见，公式PQ、(PQ)、PQ、Q P的真值表是完全相同的，我们称其为等值的。那么如何判的真值表是完全相同的，我们称其为等值的。那么如何判断两个公式等值呢？断两个公式等值呢？1.5 等价与蕴涵等价与蕴涵7/5/202426chapter1 【例9】构造公式PQ、(PQ)、PQ、QPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.5.1 等价等价1、等价的定义等价的定义等价等价设设A、B是两个命题公式，当是两个命题公式，当A与与B有完全相有完全相同的真值，则称同的真值，则称A和和B等价，即为等价，即为AB。定理：设定理：设A、B是两个命题公式，是两个命题公式，AB 的充要条件是的充要条件是AB为永真式。为永真式。等价置换：假设等价置换：假设X是公式是公式A的子公式，如果的子公式，如果XY，则将，则将X置换为置换为Y所得的公式与所得的公式与A等价。等价。1.5 等价与蕴涵等价与蕴涵7/5/202427chapter11.5.1 等价1.5 等价与蕴涵8/13/202327PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、等价等价与与双条件双条件的区别的区别等价等价：不是一个联结词，：不是一个联结词，AB不是一个命题公式，表不是一个命题公式，表示的是示的是A、B之间的逻辑关系。之间的逻辑关系。双条件双条件：是一个联结词，：是一个联结词，AB是命题公式。是命题公式。1.5 等价与蕴涵等价与蕴涵7/5/202428chapter12、等价与双条件的区别1.5 等价与蕴涵8/13/2PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 3、常用的等值式、常用的等值式(1)双重否定律双重否定律 A A(2)幂等律幂等律 A AA A AA(3)交换律交换律 AB BA AB BA(4)结合律结合律 (AB)C A(BC)(AB)C A(BC)(5)分配律分配律 A(BC)(AB)(AC)A(BC)(AB)(AC)(6)德德摩根律摩根律 (AB)AB (AB)AB1.5 等价与蕴涵等价与蕴涵7/5/202429chapter1 3、常用的等值式1.5 等价与蕴涵8/13/20232PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 (7)吸收律吸收律 A(AB)A A(AB)A(8)零律零律 A1 1 A0 0(9)同一律同一律 A0 A A1 A(10)否定律否定律 AA 1 AA 0(11)蕴涵等值式蕴涵等值式 AB AB(12)等价等值式等价等值式 AB(AB)(BA)(13)逆反律逆反律 AB BA(14)输出律输出律 A(BC)(AB)C(15)归谬论归谬论 (AB)(AB)A1.5 等价与蕴涵等价与蕴涵7/5/202430chapter1 (7)吸收律 A(AB)A PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 思考：思考：证明两个公式等价的方法：证明两个公式等价的方法：1、构造真值表。、构造真值表。2、等价推导法。（若一个公式变元太多，由于、等价推导法。（若一个公式变元太多，由于n个变元个变元组成的真值表有组成的真值表有2n行，所以用等价推导的方法来证明。）行，所以用等价推导的方法来证明。）1.5 等价与蕴涵等价与蕴涵7/5/202431chapter1 思考：1.5 等价与蕴涵8/13/202331chapPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例11】用等值演算证明】用等值演算证明p(qr)(pq)r。证明：证明：p(qr)p(qr)（蕴涵等值式）（蕴涵等值式）p(qr)（蕴涵等值式）（蕴涵等值式）(pq)r （结合律）（结合律）(pq)r （德（德摩根律）摩根律）(pq)r （蕴涵等值式）（蕴涵等值式）1.5 等价与蕴涵等价与蕴涵7/5/202432chapter1 【例11】用等值演算证明p(qr)(pq)rPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例12】化解公式】化解公式(p(qr)(qr)(pr)。解：解：(p(qr)(qr)(pr)(pqr)(qp)r)(pq)r)(qp)r)(pq)(qp)r (pq)(qp)r 1r r 1.5 等价与蕴涵等价与蕴涵7/5/202433chapter1 【例12】化解公式(p(qr)(qr)(PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.5.2 蕴含蕴含1、蕴涵的定义、蕴涵的定义蕴含蕴含设设A、B是两个命题公式，若是两个命题公式，若A为真，为真，B必定为必定为真，则称真，则称A蕴含蕴含B，记作，记作AB。定理：设定理：设A、B是两个命题公式，是两个命题公式，AB 的充要条件是的充要条件是AB为永真式。为永真式。1.5 等价与蕴涵等价与蕴涵7/5/202434chapter1 1.5.2 蕴含1.5 等价与蕴涵8/13/20233PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、蕴含、蕴含与与条件条件的区别的区别蕴含蕴含：不是一个联结词，：不是一个联结词，AB不是一个命题公式，表不是一个命题公式，表示的是示的是A、B之间的逻辑关系。之间的逻辑关系。条件条件：是一个联结词，：是一个联结词，AB是命题公式。是命题公式。1.5 等价与蕴涵等价与蕴涵7/5/202435chapter1 2、蕴含与条件的区别1.5 等价与蕴涵8/13/2PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例13】证明证明(PQ)PQ。证明：真值表如下：证明：真值表如下：由真值表可见，由真值表可见，(PQ)P为为1时，时，Q为真。为真。(PQ)PQ P QPQ(PQ)P(PQ)PQ0 00 11 01 11 1 010 0 011 1 111.5 等价与蕴涵等价与蕴涵7/5/202436chapter1 【例13】证明(PQ)PQ。由真值表可见，PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1、异或（不可兼析取）异或（不可兼析取）P Q，读作，读作“P异或异或Q”或或P、Q的异或（排斥或）的异或（排斥或）1.6 其它联结词其它联结词0110PQQ11011000QP7/5/202437chapter11、异或（不可兼析取）1.6 其它联结词0110PPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.6 其它联结词其它联结词2、条件否定条件否定 ，读作，读作“P和和Q的条件否定的条件否定”0100P Q11011000QP7/5/202438chapter11.6 其它联结词2、条件否定0100P Q110PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.6 其它联结词其它联结词3、与非与非 P QP Q ，读作，读作“P与与Q的否定的否定”0111P Q11011000QP7/5/202439chapter11.6 其它联结词3、与非 P Q0111PPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.6 其它联结词其它联结词4、或非或非 P QP Q ，读作，读作“P或或Q的否定的否定”0001P Q11011000QP7/5/202440chapter11.6 其它联结词4、或非 P Q0001PPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1、对偶、对偶定义定义1.7-1 在给定的命题公式中，将联结词在给定的命题公式中，将联结词 换成换成，将，将 换成换成，若有特殊变元，若有特殊变元0和和1亦相互取代，所得公式亦相互取代，所得公式A*称为称为A的对偶式。的对偶式。显然显然A也是也是A*的对偶式。的对偶式。【例【例14】写出下列表达式的对偶式。】写出下列表达式的对偶式。（1）(PQ)R 的对偶式是的对偶式是(P Q)R（2）(PQ)T的对偶式是的对偶式是(PQ)F（3）(PQ)(P (QS)的对偶式是的对偶式是(PQ)(P(QS)1.7 对偶与范式对偶与范式7/5/202441chapter1 1、对偶1.7 对偶与范式8/13/202341chaPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例15】求】求PQ，PQ的对偶式。的对偶式。解：因为解：因为PQ (PQ)，故，故PQ 的对偶式为的对偶式为(PQ)，即，即 PQ。同理同理PQ的对偶式是的对偶式是PQ。定理定理1.7-1设设A和和A*是对偶式，是对偶式，P1，P2，Pn是出现在是出现在A和和A*中的原子变元，则中的原子变元，则1.7 对偶与范式对偶与范式定理定理1.7-2 设设P1，P2，Pn是出现在公式是出现在公式A和和B中的所有中的所有原子变元，如果原子变元，如果AB，则，则A*B*。7/5/202442chapter1 【例15】求PQ，PQ的对偶式。1.7 对偶与范PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 2、合取范式、合取范式定义定义1.7-2 一个命题公式称为合取范式，当且仅当它具有一个命题公式称为合取范式，当且仅当它具有型式：型式：P1P2Pn，其中，其中P1，P2，Pn都是由命都是由命题变元或其否定所组成的析取式。题变元或其否定所组成的析取式。3、析取范式、析取范式定义定义1.7-3 一个命题公式称为析取范式，当且仅当它具有一个命题公式称为析取范式，当且仅当它具有型式：型式：P1P2Pn，其中，其中P1，P2，Pn都是由命都是由命题变元或其否定所组成的合取式。题变元或其否定所组成的合取式。1.7 对偶与范式对偶与范式7/5/202443chapter1 2、合取范式1.7 对偶与范式8/13/202343cPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 定理定理1.7-3 任一命题公式都存在着与之等值的析取范式和任一命题公式都存在着与之等值的析取范式和合取范式。合取范式。注：任何一个命题公式，可以通过下面三个步骤求它的注：任何一个命题公式，可以通过下面三个步骤求它的合取范式或析取范式：合取范式或析取范式：（1）将公式中的联结词化归成）将公式中的联结词化归成，及及 。（2）利用德）利用德摩根律将否定摩根律将否定 直接到各个命题变元之前。直接到各个命题变元之前。（3）利用分配律、结合律将公式归约为合取范式或析取）利用分配律、结合律将公式归约为合取范式或析取范式。范式。1.7 对偶与范式对偶与范式7/5/202444chapter1 定理1.7-3 任一命题公式都存在着与之等值的析取范式和PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例16】求】求(P(Q R)S的合取范式。的合取范式。解：解：1.7 对偶与范式对偶与范式【例【例17】求】求(PQ)(PQ)的的 析取范式。析取范式。解：解：7/5/202445chapter1【例16】求(P(Q R)S的合取范式。1.7 PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 4、主范式、主范式定义定义1.7-4 对于公式对于公式A，包含，包含A中所有命题变元或其否定一中所有命题变元或其否定一次且仅一次的简单合取式称为次且仅一次的简单合取式称为极小项极小项。注：小项有如下几个性质：注：小项有如下几个性质：1）每一个小项当其真值指派与编码相同时，其真值为）每一个小项当其真值指派与编码相同时，其真值为T，在其余，在其余2n-1种指派情况下均为种指派情况下均为F。2）任意两个不同小项的合取式永假。）任意两个不同小项的合取式永假。3）全体小项的析取式永为真，记为：）全体小项的析取式永为真，记为：1.7 对偶与范式对偶与范式7/5/202446chapter14、主范式1.7 对偶与范式8/13/202346chapPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 定义定义1.7-5 对于给定的命题公式，如果有一个等价公式，对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的它仅由小项的析取所组成，则该等价式称作原式的主析主析取范式取范式。定理定理1.7-4 在真值表中，一个公式的真值为在真值表中，一个公式的真值为T的指派所对的指派所对应的小项的析取，即为此公式的主析取范式。应的小项的析取，即为此公式的主析取范式。1.7 对偶与范式对偶与范式7/5/202447chapter1定义1.7-5 对于给定的命题公式，如果有一个等价公式，它仅PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例18】给定】给定PQ，PQ和和(PQ)，求这些公式的主，求这些公式的主析取范式。析取范式。1.7 对偶与范式对偶与范式PQPQ P Q(P Q)001010111110011111107/5/202448chapter1【例18】给定PQ，PQ和(PQ)，求这些公式的主PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例19】求】求(PQ)(PR)(QR)的主析取范式。的主析取范式。1.7 对偶与范式对偶与范式 一个命题公式的主析取范式，可一个命题公式的主析取范式，可由公式的真值表得出由公式的真值表得出或或由基本等价公式推出由基本等价公式推出。其步骤可归纳为：。其步骤可归纳为：（1）化归为析取范式。）化归为析取范式。（2）除去析取范式中所有永假的析取项。）除去析取范式中所有永假的析取项。（3）将析取式中重复出现的合取项和相同的变元合并。）将析取式中重复出现的合取项和相同的变元合并。（4）对合取项补入没有出现的命题变元，即添加）对合取项补入没有出现的命题变元，即添加(PP)式，然后，应用分配律展开公式。式，然后，应用分配律展开公式。7/5/202449chapter1【例19】求(PQ)(PR)(QR)的主析取范PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 定义定义1.7-6 对于公式对于公式A，包含，包含A中所有命题变元或其否定一中所有命题变元或其否定一次且仅一次的简单析取式称为极大项。次且仅一次的简单析取式称为极大项。注：大项有如下性质：注：大项有如下性质：1）每一个大项当其真值指派与编码相同时，其真值为）每一个大项当其真值指派与编码相同时，其真值为F，在其余在其余2n-1种指派情况下均为种指派情况下均为T。2）任意两个不同大项的析取式为永真。）任意两个不同大项的析取式为永真。MiMj T (ij)3）全体大项的合取式永为假，记为：）全体大项的合取式永为假，记为：1.7 对偶与范式对偶与范式7/5/202450chapter1定义1.7-6 对于公式A，包含A中所有命题变元或其否定一次PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 定义定义1.7-7 对于给定的命题公式，如果有一个等价公式仅由对于给定的命题公式，如果有一个等价公式仅由大项的合取所组成，则该等价式称作原式的大项的合取所组成，则该等价式称作原式的主合取范式主合取范式。定理定理1.7-5 在真值表中，一个公式的真值为在真值表中，一个公式的真值为F的指派所对应的指派所对应的大项的合取，即为此公式的主合取范式。的大项的合取，即为此公式的主合取范式。注：公式的主合取范式，可用基本等价式推出，其步骤为：注：公式的主合取范式，可用基本等价式推出，其步骤为：（1）化归为合取范式。）化归为合取范式。（2）除去合取范式中所有为永真的合取项。）除去合取范式中所有为永真的合取项。（3）合并相同的析取项和相同的变元。）合并相同的析取项和相同的变元。（4）对析取项补入没有出现的命题变元，即添加）对析取项补入没有出现的命题变元，即添加(PP)式，然后，应用分配律展开公式。式，然后，应用分配律展开公式。1.7 对偶与范式对偶与范式7/5/202451chapter1定义1.7-7 对于给定的命题公式，如果有一个等价公式仅由大PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例20】化】化(PQ)(PR)为主合取范式。为主合取范式。1.7 对偶与范式对偶与范式7/5/202452chapter1【例20】化(PQ)(PR)为主合取范式。1.7 PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.8.1 推理推理推理推理已知已知H1、H2、Hm，证明，证明C的过程。的过程。写成命题逻辑的形式为：写成命题逻辑的形式为：H1 H2 HmC 其中，其中，H1、H2、Hm称为推理的前提，称为推理的前提，C为这一组前为这一组前提的有效结论。提的有效结论。推理的过程就是证明推理的过程就是证明H1H2HmC的过程。的过程。1.8.2 推理方法推理方法 证明证明H1H2Hm C为永真式。为永真式。1、真值表法、真值表法2、等价推导法、等价推导法1.8 推理理论推理理论7/5/202453chapter1 1.8.1 推理1.8 推理理论8/13/202353PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例21】证明】证明(PQ)(QR)(PR)证明：证明：(PQ)(QR)(PR)(PQ)(QR)(PR)(P Q)(Q R)(P R)(P Q)(Q R)(P R)(PQ)(QR)(PR)(PQ)P)(QR)R)(QP)(QR)T 1.8 推理理论推理理论7/5/202454chapter1 【例21】证明(PQ)(QR)(PR)1.8PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 3、几种常用的推理的定律、几种常用的推理的定律(1)假言推理（肯定的肯定）假言推理（肯定的肯定）P(PQ)Q 通过肯定条件的前件从而肯定条件的后件。通过肯定条件的前件从而肯定条件的后件。如：如：PQ：如果他喝酒，则他脸红。：如果他喝酒，则他脸红。P：他喝酒。：他喝酒。Q：他脸红。：他脸红。但是，但是，PQ：如果他喝酒，则他脸红。：如果他喝酒，则他脸红。Q：他脸红。：他脸红。P：他喝酒。：他喝酒。不成立不成立注意：不能通过肯定条件的后件而肯定条件的前件。注意：不能通过肯定条件的后件而肯定条件的前件。1.8 推理理论推理理论7/5/202455chapter13、几种常用的推理的定律 Q：PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 (2)拒取式（否定的否定）拒取式（否定的否定）Q(PQ)P 通过否定条件的后件从而否定条件的前件。通过否定条件的后件从而否定条件的前件。如：如：PQ：小王评上三好学生，则小王成绩好。：小王评上三好学生，则小王成绩好。Q：小王成绩不好。：小王成绩不好。P：小王没评上三好学生。：小王没评上三好学生。注意：不能通过否定条件的前件而肯定条件的后件。注意：不能通过否定条件的前件而肯定条件的后件。1.8 推理理论推理理论7/5/202456chapter1 (2)拒取式（否定的否定）P PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 (3)(3)析取三段论析取三段论 (PQ)PQ 产生一个事件的原因有产生一个事件的原因有P和和Q，否定，否定P，则一定是，则一定是Q。如：如：PQ：成绩不好是老师教得不好或自己不努力。：成绩不好是老师教得不好或自己不努力。P：老师教得好。：老师教得好。Q：自己不努力。：自己不努力。推广：推广：(PQRS)PQR S 1.8 推理理论推理理论7/5/202457chapter1(3)析取三段论 PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 (4)假言三段论假言三段论 (PQ)(QR)PR 如：如：PQ：如果不下雨，就开运动会。：如果不下雨，就开运动会。QR：如果开运动会，就不上课。：如果开运动会，就不上课。PR：如果不下雨，就不上课。：如果不下雨，就不上课。1.8 推理理论推理理论7/5/202458chapter1 (4)假言三段论 PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 1.8 推理理论推理理论常用的蕴涵式常用的蕴涵式 (9 9)P P，P PQ QQ Q；(1010)Q Q，P PQ QP P；(1111)P P，P PQ QQ Q；(1212)P PQ Q，Q QR RP PR R；(1313)P PQ Q，P PR R，Q QR RR R；(1414)P PQ Q，R RS S(P PR R)()(Q QS S)；(1515)P P，Q QP PQ Q。(1 1)P PQ QP P；(2(2)P PQ QQ Q；(3 3)P PP PQ Q；(4 4)Q QP PQ Q；(5 5)P P(P PQ Q)；(6 6)Q Q(P PQ Q)；(7 7)(P PQ Q)P P；(8 8)(P PQ Q)Q Q；7/5/202459chapter11.8 推理理论常用的蕴涵式 (9PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 4、证明方法（形式演绎）、证明方法（形式演绎）(1)P规规则则（前前提提引引入入规规则则）：给给定定的的前前提提在在证证明明的的过过程程中随时都可以加以引用。中随时都可以加以引用。(2)规规则则（结结论论引引用用规规则则）：在在证证明明过过程程中中产产生生的的结结论论可以作为后续证明的前提加以引用。可以作为后续证明的前提加以引用。(3)CP规则（附加前提引入规则）：规则（附加前提引入规则）：如如果果证证明明的的形形式式为为H1 H2 Hm AB，等等价价于证明于证明H1H2HmAB。A称为附加前提。称为附加前提。1.8 推理理论推理理论7/5/202460chapter1 4、证明方法（形式演绎）1.8 推理理论8/13/20PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 证明：证明证明：证明H1 H2 HmAB等价于证明等价于证明(H1 H2 Hm)(AB)为永真式。为永真式。(H1 H2 Hm)(AB)(H1 H2 Hm)(AB)(H1 H2 HmA)B(H1 H2 HmA)B证明证明H1 H2 Hm AB等价于证等价于证明明 H1H2HmAB。1.8 推理理论推理理论7/5/202461chapter1 证明：证明H1 H2 HmAB等价PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例23】证明】证明 P(QS)，RP，Q(RS)证明：证明：RP P RP T R CP P T P(QS)P QS T Q P S T 1.8 推理理论推理理论7/5/202462chapter1 【例23】证明 P(QS)，RP，Q(RS)PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例22】证明】证明(PQ)(PR)(QS)(RS)证明：证明：PQ P PQ T QS P PS T SP T PR P SR T RS T 1.8 推理理论推理理论7/5/202463chapter1 【例22】证明(PQ)(PR)(QS)(RPropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例24】证明下面诸命题推得的结论是有效的证明下面诸命题推得的结论是有效的:如果今天如果今天是星期三是星期三,那么我有一次离散数学或数据结构测验那么我有一次离散数学或数据结构测验;如果如果离散数学课老师有事离散数学课老师有事,那么没有离散数学测验那么没有离散数学测验;今天是星今天是星期三且离散数学老师有事期三且离散数学老师有事,所以所以,我有一次数据结构测验。我有一次数据结构测验。证明：先将各命题形式化。证明：先将各命题形式化。设设 A:今天是星期三。今天是星期三。B:我有一次离散数学测验。我有一次离散数学测验。C:我有一次数据结构测验。我有一次数据结构测验。D:离散数学课老师有事。离散数学课老师有事。则本题要求证则本题要求证:ABC,DB,ADC。1.8 推理理论推理理论7/5/202464chapter1 【例24】证明下面诸命题推得的结论是有效的:如果今天PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 ABC,DB,ADC AD P A T ABC P BC T D T DB P B T C T 1.8 推理理论推理理论7/5/202465chapter1 ABC,DB,ADC1.8 推理理论PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 【例【例25】公安人员审一件盗窃案。公安人员审一件盗窃案。已知：已知：(1)甲或乙盗窃了电脑。甲或乙盗窃了电脑。(2)若甲盗窃了电脑，若甲盗窃了电脑，则作案时间不能发生在午夜前。则作案时间不能发生在午夜前。(3)若乙证词正确，若乙证词正确，则在午夜时屋里灯光未灭。则在午夜时屋里灯光未灭。(4)若乙证词不正确，若乙证词不正确，则作案时间发生在午夜前。则作案时间发生在午夜前。(5)午夜时屋里灯光灭了。午夜时屋里灯光灭了。问：问：谁是盗窃犯？谁是盗窃犯？解解:设设P：甲甲盗盗窃窃了了电电脑脑，Q：乙乙盗盗窃窃了了电电脑脑，R：作作案案时时间间发发生生在在午午夜夜前前，S：乙乙证证词词正正确确，T：午午夜夜时时屋屋里里灯光灭了。灯光灭了。前提：前提：PQ，PR，ST，SR，T1.8 推理理论推理理论7/5/202466chapter1 【例25】公安人员审一件盗窃案。已知：1.8 推PropositionProposition LogicLogic命题逻辑命题逻辑命题逻辑命题逻辑 前提：前提：PQ，PR，ST，SR，T推理：推理：T P ST P S T SR P R T PR P P T Q T 因此可得结论：因此可得结论：乙是盗窃犯。乙是盗窃犯。1.8 推理理论推理理论7/5/202467chapter1 前提：PQ，PR，ST，SR，T1.8