1、第一章第一章 命题逻辑命题逻辑 Proposition LogicProposition Logic1.1 命题及其表示法命题及其表示法1.2 联结词联结词1.3 命题公式与翻译命题公式与翻译1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式1.5 等价与蕴含等价与蕴含1.6 其它联结词其它联结词1.7 对偶与范式对偶与范式1.8 推理理论推理理论 6/2/2022 7:50 PMchapter121.1 命题及其表示法命题及其表示法1、命题、命题命题命题非真即假的陈述句。非真即假的陈述句。命题的真值命题的真值对，成立，则真值为真，对，成立，则真值为真，T，1 错，不成立，则真值为假
2、，错，不成立，则真值为假，F，0 断言断言是一陈述语句。一个命题命题是一个或真或假而不能两者都是的断言。如果命题是真, 我们说它的真值真值为真真；如果命题是假，我们说它的真值真值是假假。 6/2/2022 7:50 PMchapter13【例例1 】判定下列各语句是否为命题：判定下列各语句是否为命题：(a) 巴黎在法国。巴黎在法国。(b) 煤是白色的。煤是白色的。(c) 3+2=5(d) 别的星球上有生物。别的星球上有生物。(e) 全体立正。全体立正。(f) 明天是否开大会？明天是否开大会？(g) 天气多好啊！天气多好啊！(h) 我正在说谎。我正在说谎。(i) 如果天气好，那么我去散步。如果天
3、气好，那么我去散步。(j) x3（是）（是）（是）（是）（是）（是）（是）（是）（否，祈使句）（否，祈使句）（否，疑问句）（否，疑问句）（否，感叹句）（否，感叹句）（否（否, 悖论悖论）（是（是,复合命题复合命题）（否，不能确定真值）（否，不能确定真值） 1.1 命题及其表示法命题及其表示法 6/2/2022 7:50 PMchapter142、命题的表示、命题的表示命题变元命题变元常用常用P、Q、R、S等大写字母等大写字母或加下标的大或加下标的大写字母写字母P1, Q2, R10, 表示表示来表示一个命题，称为命题变来表示一个命题，称为命题变元。元。如：如： P:巴黎在法国。巴黎在法国。 Q
4、:煤是白色的。煤是白色的。 1.1 命题及其表示法命题及其表示法 6/2/2022 7:50 PMchapter153、命题相关概念、命题相关概念简单命题（原子命题）简单命题（原子命题）不能再分解的命题。不能再分解的命题。复合命题复合命题由若干个简单命题复合而成的命题。由若干个简单命题复合而成的命题。真值表真值表把组成复合命题的各命题变元的真值的所有把组成复合命题的各命题变元的真值的所有组合及其相对应的复合命题的真值列成表，称为真值表。组合及其相对应的复合命题的真值列成表，称为真值表。1.1 命题及其表示法命题及其表示法 6/2/2022 7:50 PMchapter16【例例2 】求公式求公
5、式(PQ)P的真值表。的真值表。 解：解： 分以下步求得分以下步求得: (1) 写出公式写出公式P的真值表的真值表;(2) 写出公式写出公式PQ的真值表的真值表; (3) 根据根据(1)和和(2), 写出公式写出公式(PQ)P的真值表。的真值表。 为清楚起见为清楚起见, 我们将这步列在一个表内我们将这步列在一个表内, 见下表。见下表。1.1 命题及其表示法命题及其表示法 6/2/2022 7:50 PMchapter17【例例3 】求公式求公式 (PR)(QR)的真值表。的真值表。 解：解：公式含有个命题变元公式含有个命题变元P、Q、R, 真值表有真值表有3=8行。其真值表如下表行。其真值表如
6、下表 所示：所示： 1.1 命题及其表示法命题及其表示法 6/2/2022 7:50 PMchapter18 1.2 联结词联结词 命题和原子命题常可通过一些联结词构成新命题, 这种新命题叫复合命题（复合命题（Compositional Proposition ）。例如： P: 明天下雪, Q: 明天下雨是两个命题, 利用联结词“不”, “并且”, “或”等可构成新命题: “明天不下雪”； “明天下雪并且下雨”； “明天下雪或下雨”等 。 6/2/2022 7:50 PMchapter191.2 联结词联结词即 ： “非P”； “P并且Q”； “P或Q”等 。 在代数式x+3 中, x , 3
7、 叫运算对象, +叫运算符, x+3 表示运算结果。在命题演算中, 联结词联结词就是命题演算中的运算符, 叫逻辑运算符逻辑运算符或叫逻辑联结词逻辑联结词。常用的有以下 5 个。 6/2/2022 7:50 PMchapter1101、否定、否定 P是是P的否定，读作的否定，读作“非非P”， “ P的否定的否定” 。0110pp如：如： P:成都是中国的首都。成都是中国的首都。 P：成都不是中国的首都。：成都不是中国的首都。 否定与汉语中的否定与汉语中的“非非”、“不是不是”、“否定否定”是一致是一致的。的。1.2 联结词联结词 6/2/2022 7:50 PMchapter1112、合取、合取
8、 PQ是是P和和Q的合取的合取, 读做读做“P与与Q”或或“P并且并且Q”。如：如： P: 王华的成绩很好。王华的成绩很好。 Q: 王华的品德很好。王华的品德很好。 PQ: 王华的成绩很好并且品德很好。王华的成绩很好并且品德很好。合取与汉语中的合取与汉语中的“和和”、“与与”、“并且并且”是一致的。是一致的。P QP Q0 00 11 01 100011.2 联结词联结词 6/2/2022 7:50 PMchapter1123、析取、析取 PQ是是P和和Q的析取的析取, 读做读做“P或或Q”。如：如： P:小王喜欢唱歌。小王喜欢唱歌。 Q:小王喜欢跳舞小王喜欢跳舞 。 P Q:小王喜欢唱歌或喜
9、欢跳舞小王喜欢唱歌或喜欢跳舞 。从真值表可知从真值表可知PQ为真为真, 当且仅当当且仅当P或或Q至少有一为真。至少有一为真。P QP Q0 00 11 01 101111.2 联结词联结词 6/2/2022 7:50 PMchapter113 “或”字常见的含义有两种: 一种是“可兼或可兼或”, 如上例中的或, 它不排除小王既喜欢唱歌又喜欢跳舞这种情况。一种是“排斥或排斥或”（异或）（异或）, 例如“人固有一死, 或重于泰山, 或轻于鸿毛”中的“或”, 它表示非此即彼, 不可兼得。 运算符运算符表示可兼或表示可兼或, 排斥或以后用另一符号表达。排斥或以后用另一符号表达。如：(1)小李明天出差去
10、上海或去广州。 (2)刘昕这次考试可能是全班第一也可能是全班第二。 这两例表示的均是排斥或，即两种情况不能同时出现，这时便不能仅用析取词表示。 1.2 联结词联结词 6/2/2022 7:50 PMchapter1144、条件、条件 PQ, 读做读做 “如果如果P, 那么那么Q”或或“P则则Q” 。运算对象运算对象P叫做前提叫做前提 , 假设或前件假设或前件, 而而Q叫做结论或后件。叫做结论或后件。P QP Q0 00 11 01 111011.2 联结词联结词如：如： P:雪是黑的。雪是黑的。 Q:太阳从东方升起太阳从东方升起 。 P Q:如果雪是黑的，则太阳从东方升起如果雪是黑的，则太阳从
11、东方升起 。命题命题PQ是假是假, 当且仅当当且仅当P是真而是真而Q是假。是假。 6/2/2022 7:50 PMchapter115 条件与汉语中条件与汉语中“如果如果，就，就”相类似，但有所区别相类似，但有所区别:(1)自然语言中，自然语言中，“如果如果P则则Q”，往往，往往P和和Q有一定的因果有一定的因果关系，而条件复合命题关系，而条件复合命题PQ中中 P和和Q 可以完全不相关。可以完全不相关。(2)自然语言中，自然语言中，“如果如果P则则Q”，当，当P为为0、Q为为1时，整个时，整个句子真值难以确定；而条件复合命题句子真值难以确定；而条件复合命题PQ中，当中，当P为为0时，时，复合命题
12、的真值为复合命题的真值为1。 P则则Q的逻辑含义的逻辑含义:P是是Q的充分条件的充分条件,Q是是P的必要条件。的必要条件。 所以所以,“如果如果P则则Q”, “只要只要P则则Q”,只有只有Q才才P”, “仅当仅当Q则则P”都可符号化为都可符号化为PQ 的形式。的形式。1.2 联结词联结词 6/2/2022 7:50 PMchapter116如：小李对小王说：如：小李对小王说：“如果天不下雨，我就来找你如果天不下雨，我就来找你”。 天没下雨，小李去找了小王。天没下雨，小李去找了小王。 天没下雨，小李没去找小王。天没下雨，小李没去找小王。 天下雨了，小李去找了小王。天下雨了，小李去找了小王。 天下
13、雨了，小李没去找小王。天下雨了，小李没去找小王。1.2 联结词联结词【例例4 】电灯不亮是电灯坏或电路有毛病。电灯不亮是电灯坏或电路有毛病。解：设解：设P电灯不亮，电灯不亮，Q电灯坏，电灯坏，R电路有毛病。电路有毛病。上述语句应表示为上述语句应表示为: (Q R) P 6/2/2022 7:50 PMchapter1175、双条件、双条件 P Q, 读做读做 “P当且仅当当且仅当Q” 。如：如： P:两个三角形全等。两个三角形全等。 Q:两个三角形的对应边相等两个三角形的对应边相等 。 P Q:两个三角形全等当且仅当其对应边相等两个三角形全等当且仅当其对应边相等 。P当且仅当当且仅当Q的逻辑含
14、义的逻辑含义:P和和Q互为充要条件互为充要条件 。P QP Q0 00 11 01 110011.2 联结词联结词 6/2/2022 7:50 PMchapter118 6、联结词的优先次序、联结词的优先次序联结词的优先级：联结词的优先级： , , , , ，括号优先。，括号优先。如：如： (PQ)R 可写成可写成 ：PQR (PQ)R 可写成：可写成：PQR (P Q)R)(RP)Q) 可写成：可写成： (P QR)RPQ 为方便起见，公式最外层的括号可省略。有时为了为方便起见，公式最外层的括号可省略。有时为了看起来清楚醒目看起来清楚醒目, 也可保留某些原可省去的括号。也可保留某些原可省去的
15、括号。 1.2 联结词联结词 6/2/2022 7:50 PMchapter119 单个命题变元和命题常元叫原子公式。单个命题变元和命题常元叫原子公式。由以下形成规则生成的公式叫命题公式命题公式 (简称公式简称公式): (1) 单个原子公式单个原子公式A、B是命题公式。是命题公式。 (2) 如果如果A和和B是命题公式是命题公式, 则则(A) , (AB) , (AB) , (AB) , (AB)是命题公式。是命题公式。 (3) 只有有限步使用只有有限步使用(1)和和(2)所组成的包含命题变元、所组成的包含命题变元、联结词以及成对的括号组成的符号串才是命题公式。联结词以及成对的括号组成的符号串才
16、是命题公式。 这种定义叫归纳定义, 也叫递归定义。由这种定义产生的公式也叫合式公式（合式公式（Well-Formed Formulas），简），简写为写为wff。1.3 命题公式命题公式 6/2/2022 7:50 PMchapter120【例例5】 判断下列表达式是否为合式公式判断下列表达式是否为合式公式: p(pq) (pq)r) (p(qr) (pq)(qr) (pq)r) (pq)r) s) (pq)r) s（是）（是）（是）（是）（否）（否）（否）（否）（否）（否）（是）（是）（是）（是）1.3 命题公式命题公式 6/2/2022 7:50 PMchapter121 【例例6】 将下
17、列自然语言形式化将下列自然语言形式化:(a) 如果天不下雨并且不刮风，我就去书店。如果天不下雨并且不刮风，我就去书店。解解 ：设：设P：今天天下雨，：今天天下雨，Q：今天天刮风，：今天天刮风，R：我去书店。：我去书店。 则原命题符号化为：则原命题符号化为： (PQ)R (b) 小王边走边唱。小王边走边唱。解：设解：设p：小王走路，：小王走路，q：小王唱歌。：小王唱歌。 则原命题符号化为：则原命题符号化为： pq (c) 除非除非a能被能被2整除，否则整除，否则a不能被不能被4整除。整除。解：设解：设p：a能被能被2整除，整除，q：a能被能被4整除。整除。 则原命题符号化为：则原命题符号化为：
18、p q 或或 q p1.3 命题公式命题公式 6/2/2022 7:50 PMchapter122 (d) 此时，小刚要么在学习，要么在玩游戏。此时，小刚要么在学习，要么在玩游戏。解：设解：设p：小刚在学习，：小刚在学习，q：小刚在玩游戏。：小刚在玩游戏。 则原命题符号化为：则原命题符号化为： (pq)(pq) 或或 (pq)(pq)(e) 如果天不下雨，我们去打篮球，除非班上有会。如果天不下雨，我们去打篮球，除非班上有会。解：设解：设p：今天天下雨，：今天天下雨，q：我们去打篮球，：我们去打篮球，r：今天班上：今天班上有会。有会。 则原命题符号化为：则原命题符号化为： r (p q)1.3
19、命题公式命题公式 6/2/2022 7:50 PMchapter123 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 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式 6/2/2022 7:50 PMchapter124 2、 矛盾式（矛盾式（Contradiction)矛盾式（永假式）矛盾式（永假式）真值恒为
20、真值恒为0的公式的公式。如：。如：P P 【例例8】判断判断(PQ)P是否为矛盾式。是否为矛盾式。P QPQ(PQ)P0 00 11 01 10 0 010 0 00（ (PQ)P ）为矛盾式。）为矛盾式。1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式 6/2/2022 7:50 PMchapter1253、 可满足公式（可满足公式（Satisfaction） 可满足公式可满足公式至少有一种真值为至少有一种真值为1的情况的情况。 (除矛盾式之外的公式除矛盾式之外的公式) ，永真式也是可满足公式。，永真式也是可满足公式。定理：由定理：由n个命题变元一共可组成个命题变元一共可组成 个
21、不同的命题。其中个不同的命题。其中永真式有一个，矛盾式有一个，可满足公式有永真式有一个，矛盾式有一个，可满足公式有 个。个。 n22122n1.4 重言式、矛盾式、可满足公式重言式、矛盾式、可满足公式 6/2/2022 7:50 PMchapter126 【例【例9】 构造公式构造公式PQ、(PQ)、PQ、Q P的真值的真值 。解：真值表如下：解：真值表如下： 由例题可见，公式由例题可见，公式PQ、(PQ)、PQ、Q P的真值表是完全相同的，我们称其为等值的。那么如何判的真值表是完全相同的，我们称其为等值的。那么如何判断两个公式等值呢？断两个公式等值呢？ 1.5 等价与蕴涵等价与蕴涵 6/2/
22、2022 7:50 PMchapter1271.5.1 等价等价1、 等价的定义等价的定义等价等价设设A、B是两个命题公式，当是两个命题公式，当A与与B有完全相有完全相同的真值，则称同的真值，则称A和和B等价，即为等价，即为AB。定理：定理：设设A、B是两个命题公式，是两个命题公式， AB 的充要条件是的充要条件是AB为永真式。为永真式。等价置换：假设等价置换：假设X是公式是公式A的子公式，如果的子公式，如果XY，则将，则将X置换为置换为Y所得的公式与所得的公式与A等价。等价。1.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter1282、 等价等价与与双条件双条件的区别
23、的区别等价等价：不是一个联结词，：不是一个联结词，AB不是一个命题公式，表不是一个命题公式，表示的是示的是A、B之间的逻辑关系。之间的逻辑关系。双条件双条件：是一个联结词，：是一个联结词， AB是命题公式。是命题公式。 1.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter129 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)德
24、德摩根律摩根律 (AB) AB (AB) AB1.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter130 (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 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter131 思考：思考：证
25、明两个公式等价的方法：证明两个公式等价的方法：1、构造真值表。、构造真值表。2 、等价推导法。（若一个公式变元太多，由于、等价推导法。（若一个公式变元太多，由于n个变元个变元组成的真值表有组成的真值表有2n行，所以用等价推导的方法来证明。）行，所以用等价推导的方法来证明。）1.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter132 【例【例11】用等值演算证明】用等值演算证明p(qr) (pq)r。证明：证明： p(qr) p(qr) （蕴涵等值式）（蕴涵等值式） p(qr) （蕴涵等值式）（蕴涵等值式） (pq) r （结合律）（结合律） (pq) r （德（德摩根律
26、）摩根律） (pq)r （蕴涵等值式）（蕴涵等值式） 1.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter133 【例【例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 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter134 1.5.2 蕴含蕴含1、蕴涵的定义、蕴涵的定义蕴含蕴含设设A、B是两个命题公式，若是两个命题公式，若A为真，为真，B必定为必定为真，则称真，则称A蕴含蕴含B，记作，记作A
27、B。定理：定理：设设A、B是两个命题公式，是两个命题公式， AB 的充要条件是的充要条件是AB为永真式。为永真式。1.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter135 2、蕴含、蕴含与与条件条件的区别的区别蕴含蕴含：不是一个联结词，：不是一个联结词，AB不是一个命题公式，表不是一个命题公式，表示的是示的是A、B之间的逻辑关系。之间的逻辑关系。条件条件：是一个联结词，：是一个联结词， AB是命题公式。是命题公式。 1.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter136 【例【例13】 证明证明 (PQ)PQ 。证明：真值表如下：证明：真值
28、表如下：由真值表可见，由真值表可见， (PQ)P为为1时，时，Q为真。为真。 (PQ)PQ P QPQ(PQ)P(PQ)PQ0 00 11 01 11 1 010 0 011 1 111.5 等价与蕴涵等价与蕴涵 6/2/2022 7:50 PMchapter1371、 异或（不可兼析取）异或（不可兼析取） P Q，读作，读作“P异或异或Q”或或P、Q的异或（排斥或）的异或（排斥或）1.6 其它联结词其它联结词0110PQQ11011000QP qpqpqpqpqpqp_ 6/2/2022 7:50 PMchapter1381.6 其它联结词其它联结词qpqpqpqpc2、 条件否定条件否定
29、，读作，读作“P和和Q的条件否定的条件否定”QPcQPc0100P Q11011000QPc 6/2/2022 7:50 PMchapter1391.6 其它联结词其它联结词qpqpqp3、 与非与非 P QP Q ，读作，读作“P与与Q的否定的否定”0111P Q11011000QP 6/2/2022 7:50 PMchapter1401.6 其它联结词其它联结词qpqpqp4、 或非或非 P QP Q ，读作，读作“P或或Q的否定的否定”0001P Q11011000QP 6/2/2022 7:50 PMchapter141 1、对偶、对偶定义定义1.7-1 在给定的命题公式中，将联结词在
30、给定的命题公式中，将联结词 换成换成，将，将 换成换成，若有特殊变元，若有特殊变元0和和1亦相互取代，所得公式亦相互取代，所得公式A*称为称为A的对偶式。的对偶式。显然显然A也是也是A*的对偶式。的对偶式。 【例【例14】写出下列表达式的对偶式。】写出下列表达式的对偶式。（1） (PQ)R 的对偶式是的对偶式是(P Q) R （2） (PQ)T的对偶式是的对偶式是 (PQ)F （3）(PQ)(P (Q S)的对偶式是的对偶式是(PQ)(P (Q S)1.7 对偶与范式对偶与范式 6/2/2022 7:50 PMchapter142 【例【例15】求】求PQ，PQ的对偶式。的对偶式。解：因为解：
31、因为PQ (PQ) ，故，故PQ 的对偶式为的对偶式为(PQ) ，即，即 PQ 。同理同理PQ的对偶式是的对偶式是PQ 。定理定理1.7-1设设A和和A*是对偶式，是对偶式，P1，P2，Pn是出现在是出现在A和和A*中的原子变元，则中的原子变元，则1.7 对偶与范式对偶与范式),.,(),.,(),.,(),.,(21212121nnnnPPPAPPPAPPPAPPPA定理定理1.7-2 设设P1，P2，Pn是出现在公式是出现在公式A和和B中的所有中的所有原子变元，如果原子变元，如果AB ，则，则A*B*。 6/2/2022 7:50 PMchapter143 2、合取范式、合取范式定义定义1
32、.7-2 一个命题公式称为合取范式，当且仅当它具有一个命题公式称为合取范式，当且仅当它具有型式：型式： P1P2Pn，其中，其中P1，P2 ，Pn都是由命都是由命题变元或其否定所组成的析取式。题变元或其否定所组成的析取式。3、析取范式、析取范式定义定义1.7-3 一个命题公式称为析取范式，当且仅当它具有一个命题公式称为析取范式，当且仅当它具有型式：型式： P1P2Pn，其中，其中P1，P2 ，Pn都是由命都是由命题变元或其否定所组成的合取式。题变元或其否定所组成的合取式。1.7 对偶与范式对偶与范式 6/2/2022 7:50 PMchapter144 定理定理1.7-3 任一命题公式都存在着
33、与之等值的析取范式和任一命题公式都存在着与之等值的析取范式和合取范式。合取范式。注：任何一个命题公式，可以通过下面三个步骤求它的注：任何一个命题公式，可以通过下面三个步骤求它的合取范式或析取范式：合取范式或析取范式：（1）将公式中的联结词化归成）将公式中的联结词化归成， 及及 。（2）利用德）利用德摩根律将否定摩根律将否定直接到各个命题变元之前直接到各个命题变元之前。（3）利用分配律、结合律将公式归约为合取范式或析取）利用分配律、结合律将公式归约为合取范式或析取范式。范式。1.7 对偶与范式对偶与范式 6/2/2022 7:50 PMchapter145 【例【例16】求】求(P(Q R)S的
34、合取范式。的合取范式。解：解：1.7 对偶与范式对偶与范式)()()()()()()()(RSPQSPRQSPSRQPSRQPSRQPSRQP 【例【例17】求】求(PQ) (PQ)的的析取范式。析取范式。解：解：)()()()()()()()()()()()()()()(QPPQQQQPPQPPQPQPQPQPQPQPQPQPQPQP 6/2/2022 7:50 PMchapter1464、主范式、主范式定义定义1.7-4 对于公式对于公式A，包含，包含A中所有命题变元或其否定一中所有命题变元或其否定一次且仅一次的简单合取式称为次且仅一次的简单合取式称为极小项极小项。注：小项有如下几个性质：
35、注：小项有如下几个性质：1）每一个小项当其真值指派与编码相同时，其真值为）每一个小项当其真值指派与编码相同时，其真值为T，在其余在其余2n-1种指派情况下均为种指派情况下均为F。2）任意两个不同小项的合取式永假。）任意两个不同小项的合取式永假。3）全体小项的析取式永为真，记为：）全体小项的析取式永为真，记为：1.7 对偶与范式对偶与范式Tmmmmnnii1210120. 6/2/2022 7:50 PMchapter147定义定义1.7-5 对于给定的命题公式，如果有一个等价公式，对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的它仅由小项的析取所组成，则该等
36、价式称作原式的主析主析取范式取范式。定理定理1.7-4 在真值表中，一个公式的真值为在真值表中，一个公式的真值为T的指派所对的指派所对应的小项的析取，即为此公式的主析取范式。应的小项的析取，即为此公式的主析取范式。1.7 对偶与范式对偶与范式 6/2/2022 7:50 PMchapter148【例【例18】给定】给定PQ，PQ和和(PQ) ，求这些公式的，求这些公式的主析取范式。主析取范式。1.7 对偶与范式对偶与范式PQPQ P Q (P Q) 00101011111001111110)()()()()()()()()()(QPQPQPQPQPQPQPQPQPQPQPQP 6/2/2022
37、 7:50 PMchapter149【例【例19】求】求 (PQ)(PR)(QR)的主析取范式。的主析取范式。1.7 对偶与范式对偶与范式)()()()()()()()()()(QRPQRPRQPRQPPPRQQQRPRRQPRQRPQP 一个命题公式的主析取范式，可一个命题公式的主析取范式，可由公式的真值表得出由公式的真值表得出或或由基本等价公式推出由基本等价公式推出。其步骤可归纳为：。其步骤可归纳为：（1）化归为析取范式。）化归为析取范式。（2）除去析取范式中所有永假的析取项。）除去析取范式中所有永假的析取项。（3）将析取式中重复出现的合取项和相同的变元合并。）将析取式中重复出现的合取项和
38、相同的变元合并。（4）对合取项补入没有出现的命题变元，即添加）对合取项补入没有出现的命题变元，即添加(PP) 式，然后，应用分配律展开公式。式，然后，应用分配律展开公式。 6/2/2022 7:50 PMchapter150定义定义1.7-6 对于公式对于公式A，包含，包含A中所有命题变元或其否定一中所有命题变元或其否定一次且仅一次的简单析取式称为极大项。次且仅一次的简单析取式称为极大项。注：大项有如下性质：注：大项有如下性质：1）每一个大项当其真值指派与编码相同时，其真值为）每一个大项当其真值指派与编码相同时，其真值为F，在其余在其余2n-1种指派情况下均为种指派情况下均为T。2）任意两个不
39、同大项的析取式为永真。）任意两个不同大项的析取式为永真。MiMj T (ij)3）全体大项的合取式永为假，记为：）全体大项的合取式永为假，记为：1.7 对偶与范式对偶与范式FMMMMnnii1210120. 6/2/2022 7:50 PMchapter151定义定义1.7-7 对于给定的命题公式，如果有一个等价公式仅由对于给定的命题公式，如果有一个等价公式仅由大项的合取所组成，则该等价式称作原式的大项的合取所组成，则该等价式称作原式的主合取范式主合取范式。定理定理1.7-5 在真值表中，一个公式的真值为在真值表中，一个公式的真值为F的指派所对应的指派所对应的大项的合取，即为此公式的主合取范式
40、。的大项的合取，即为此公式的主合取范式。注：公式的主合取范式，可用基本等价式推出，其步骤为：注：公式的主合取范式，可用基本等价式推出，其步骤为：（1）化归为合取范式。）化归为合取范式。（2）除去合取范式中所有为永真的合取项。）除去合取范式中所有为永真的合取项。（3）合并相同的析取项和相同的变元。）合并相同的析取项和相同的变元。（4）对析取项补入没有出现的命题变元，即添加）对析取项补入没有出现的命题变元，即添加(P P) 式，然后，应用分配律展开公式。式，然后，应用分配律展开公式。1.7 对偶与范式对偶与范式 6/2/2022 7:50 PMchapter152【例【例20】化】化 (PQ)(P
41、R)为主合取范式。为主合取范式。1.7 对偶与范式对偶与范式)()()()()()()()()()()()()()()()()()()()()()()()(RQPRQPRQPRQPPRQPRQQRPQRPRPQRPQPPRQQQRPRRPQRQRPPQRQRPPQPPRQPPQPRPQP 6/2/2022 7:50 PMchapter153 1.8.1 推理推理推理推理已知已知H1、H2、Hm，证明，证明C的过程。的过程。写成命题逻辑的形式为：写成命题逻辑的形式为： H1 H2 HmC 其中，其中， H1、H2、Hm称为推理的前提，称为推理的前提，C为这一组前为这一组前提的有效结论。提的有效结
42、论。推理的过程就是证明推理的过程就是证明H1H2HmC的过程。的过程。 1.8.2 推理方法推理方法 证明证明H1H2Hm C为永真式。为永真式。1、真值表法、真值表法2、等价推导法、等价推导法1.8 推理理论推理理论 6/2/2022 7:50 PMchapter154 【例【例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 推理理论推理理论 6/2/2022 7:5
43、0 PMchapter1553、几种常用的推理的定律、几种常用的推理的定律(1) 假言推理（肯定的肯定）假言推理（肯定的肯定）P(PQ)Q 通过肯定条件的前件从而肯定条件的后件。通过肯定条件的前件从而肯定条件的后件。如：如： PQ：如果他喝酒，则他脸红。：如果他喝酒，则他脸红。 P：他喝酒。：他喝酒。 Q：他脸红。：他脸红。但是，但是， PQ：如果他喝酒，则他脸红。：如果他喝酒，则他脸红。 Q：他脸红。：他脸红。 P：他喝酒。：他喝酒。不成立不成立注意：不能通过肯定条件的后件而肯定条件的前件。注意：不能通过肯定条件的后件而肯定条件的前件。1.8 推理理论推理理论 6/2/2022 7:50 P
44、Mchapter156 (2) 拒取式（否定的否定）拒取式（否定的否定）Q(PQ)P 通过否定条件的后件从而否定条件的前件。通过否定条件的后件从而否定条件的前件。如：如： PQ：小王评上三好学生，则小王成绩好。：小王评上三好学生，则小王成绩好。 Q ：小王成绩不好。：小王成绩不好。 P ：小王没评上三好学生。：小王没评上三好学生。注意：不能通过否定条件的前件而肯定条件的后件。注意：不能通过否定条件的前件而肯定条件的后件。1.8 推理理论推理理论 6/2/2022 7:50 PMchapter157(3) (3) 析取三段论析取三段论 (PQ)PQ 产生一个事件的原因有产生一个事件的原因有P和和
45、Q，否定，否定P，则一定是，则一定是Q。如：如： PQ：成绩不好是老师教得不好或自己不努力。：成绩不好是老师教得不好或自己不努力。 P ：老师教得好。：老师教得好。 Q：自己不努力。：自己不努力。推广：推广： (PQRS)PQR S 1.8 推理理论推理理论 6/2/2022 7:50 PMchapter158 (4) 假言三段论假言三段论 (PQ)(QR)PR 如：如： PQ：如果不下雨，就开运动会。：如果不下雨，就开运动会。 QR：如果开运动会，就不上课。：如果开运动会，就不上课。 PR ：如果不下雨，就不上课。：如果不下雨，就不上课。1.8 推理理论推理理论 6/2/2022 7:50
46、PMchapter1591.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 P
47、P 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； 6/2/2022 7:50 PMchapter160 4、证明方法（形式演绎）、证明方法（形式演绎）(1) P规则（前提引入规则）：规则（前提引入规则）：给定的前提在证明的过程给定的前提在证明的过程中随时都可以加以引用。中随时都可以加以引用。(2) 规则（结论引用规则）：规则（结论引用规则）：在证明过程中产生的结论在证明过程中产生的结
48、论可以作为后续证明的前提加以引用。可以作为后续证明的前提加以引用。(3) CP规则（附加前提引入规则）：规则（附加前提引入规则）：如果证明的形式为如果证明的形式为H1 H2 Hm AB，等价，等价于证明于证明H1H2HmAB。A称为附加前提。称为附加前提。1.8 推理理论推理理论 6/2/2022 7:50 PMchapter161 证明：证明证明：证明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等价于证等
49、价于证明明 H1H2HmAB。1.8 推理理论推理理论 6/2/2022 7:50 PMchapter162 【例【例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 推理理论推理理论 6/2/2022 7:50 PMchapter163 【例【例22】证明】证明 (PQ)(PR)(QS)(RS)证明：证明： PQ P PQ T QS P PS T SP T PR P SR T RS T 1.8 推理理论推理理论 6/2/2022 7:50 PMchapter164 【例【例24】 证明下面诸命题
50、推得的结论是有效的证明下面诸命题推得的结论是有效的: 如果今天如果今天是星期三是星期三, 那么我有一次离散数学或数据结构测验那么我有一次离散数学或数据结构测验; 如果如果离散数学课老师有事离散数学课老师有事, 那么没有离散数学测验那么没有离散数学测验; 今天是星今天是星期三且离散数学老师有事期三且离散数学老师有事, 所以所以, 我有一次数据结构测验。我有一次数据结构测验。 证明：先将各命题形式化。证明：先将各命题形式化。 设设 A: 今天是星期三。今天是星期三。 B: 我有一次离散数学测验。我有一次离散数学测验。 C: 我有一次数据结构测验。我有一次数据结构测验。 D: 离散数学课老师有事。离
