离散数学第一章命题逻辑.ppt

第一章 命题逻辑 Proposition Logic 1.1 命题及其表示法 1.2 联结词 1.3 命题公式与翻译 1.4 重言式、矛盾式、可满足公式 1.5 等价与蕴含 1.6 推理理论 *1chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1.1 命题及其表示法 1、命题 命题非真即假的陈述句。 命题的真值 对，成立，则真值为真，T，1 错，不成立，则真值为假，F，0 断言是一陈述语句。一个命题是一个或真或假而不能 两者都是的断言。如果命题是真, 我们说它的真值为真； 如果命题是假，我们说它的真值是假。 Date2chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例1 】判定下列各语句是否为命题： (a) 巴黎在法国。 (b) 煤是白色的。 (c) 3+2=5 (d) 别的星球上有生物。 (e) 全体立正。 (f) 明天是否开大会？ (g) 天气多好啊！ (h) 我正在说谎。 (i) 如果天气好，那么我去散步。 (j) x3 （是） （是） （是） （是） （否，祈使句） （否，疑问句） （否，感叹句） （否, 悖论） （是,复合命题） （否，不能确定真值） 1.1 命题及其表示法 Date3chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 2、命题的表示 命题变元常用P、Q、R、S等大写字母或加下标的大 写字母P1, Q2, R10, 表示来表示一个命题，称为命题变 元。 如： P:巴黎在法国。 Q:煤是白色的。 1.1 命题及其表示法 Date4chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 3、命题相关概念 简单命题（原子命题）不能再分解的命题。 复合命题由若干个简单命题复合而成的命题。 真值表把组成复合命题的各命题变元的真值的所有 组合及其相对应的复合命题的真值列成表，称为真值表 。 1.1 命题及其表示法 Date5chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例2 】求公式(PQ)P的真值表。 解： 分以下步求得: (1) 写出公式P的真值表; (2) 写出公式PQ的真值表; (3) 根据(1)和(2), 写出公式(PQ)P的真值表。 为清楚起见, 我们将这步列在一个表内, 见下表。 1.1 命题及其表示法 Date6chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例3 】求公式 (PR)(QR)的真值表。 解：公式含有个命题变元P、Q、R, 真值表有3=8行。其真值表如下表 所示： 1.1 命题及其表示法 Date7chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1.2 联结词 命题和原子命题常可通过一些联结词构成新命题, 这 种新命题叫复合命题（Compositional Proposition ）。例 如： P: 明天下雪, Q: 明天下雨 是两个命题, 利用联结词“不”, “并且”, “或”等可构成新命题: “明天不下雪”； “明天下雪并且下雨”； “明天下雪或下雨”等 。 Date8chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1.2 联结词 即 ： “非P”； “P并且Q”； “P或Q”等 。 在代数式x+3 中, x , 3 叫运算对象, +叫运算符, x+3 表示运算结果。在命题演算中, 联结词就是命题演算 中的运算符, 叫逻辑运算符或叫逻辑联结词。常用的有以 下 5 个。 Date9chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1、否定 P是P的否定，读作“非P”， “ P的否定” 。 0 1 1 0 p 如： P:成都是中国的首都。 P：成都不是中国的首都。 否定与汉语中的“非”、“不是”、“否定”是一致的。 1.2 联结词 Date10chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 2、合取 PQ是P和Q的合取, 读做“P与Q”或“P并且Q”。 如： P: 王华的成绩很好。 Q: 王华的品德很好。 PQ: 王华的成绩很好并且品德很好。 合取与汉语中的“和”、“与”、“并且”是一致的。 P QP Q 0 0 0 1 1 0 1 1 0 0 0 1 1.2 联结词 Date11chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 3、析取 PQ是P和Q的析取, 读做“P或Q”。 如： P:小王喜欢唱歌。 Q:小王喜欢跳舞 。 P Q:小王喜欢唱歌或喜欢跳舞 。 从真值表可知PQ为真, 当且仅当P或Q至少有一为真。 P QP Q 0 0 0 1 1 0 1 1 0 1 1 1 1.2 联结词 Date12chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 “或”字常见的含义有两种: 一种是“可兼或”, 如上例中 的或, 它不排除小王既喜欢唱歌又喜欢跳舞这种情况。一 种是“排斥或”（异或）, 例如“人固有一死, 或重于泰山, 或 轻于鸿毛”中的“或”, 它表示非此即彼, 不可兼得。 运算符表示可兼或, 排斥或以后用另一符号表达。 如：(1)小李明天出差去上海或去广州。 (2)刘昕这次考试可能是全班第一也可能是全班第二 。 这两例表示的均是排斥或，即两种情况不能同时出现 ，这时便不能仅用析取词表示。 1.2 联结词 Date13chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 4、条件 PQ, 读做 “如果P, 那么Q”或“P则Q” 。 运算对象P叫做前提 , 假设或前件, 而Q叫做结论或后件 。 P QP Q 0 0 0 1 1 0 1 1 1 1 0 1 1.2 联结词 如： P:雪是黑的。 Q:太阳从东方升起 。 P Q:如果雪是黑的，则太阳从东方升起 。 命题PQ是假, 当且仅当P是真而Q是假。 Date14chapter1 PropositionProposition 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 联结词 Date15chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 如：小李对小王说：“如果天不下雨，我就来找你”。 天没下雨，小李去找了小王。 天没下雨，小李没去找小王。 天下雨了，小李去找了小王。 天下雨了，小李没去找小王。 1.2 联结词 【例4 】电灯不亮是电灯坏或电路有毛病。 解：设P电灯不亮，Q电灯坏，R电路有毛病。 上述语句应表示为: (Q R) P Date16chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 5、双条件 P Q, 读做 “P当且仅当Q” 。 如： P:两个三角形全等。 Q:两个三角形的对应边相等 。 P Q:两个三角形全等当且仅当其对应边相等 。 P当且仅当Q的逻辑含义:P和Q互为充要条件 。 P QP Q 0 0 0 1 1 0 1 1 1 0 0 1 1.2 联结词 Date17chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 6、联结词的优先次序 联结词的优先级： , , , , ，括号优先。 如： (PQ)R 可写成 ：PQR (PQ)R 可写成：PQR (P Q)R)(RP)Q) 可写成： (P QR)RPQ 为方便起见，公式最外层的括号可省略。有时为了 看起来清楚醒目, 也可保留某些原可省去的括号。 1.2 联结词 Date18chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 单个命题变元和命题常元叫原子公式。由以下形成 规则生成的公式叫命题公式 (简称公式): (1) 单个原子公式A、B是命题公式。 (2) 如果A和B是命题公式, 则(A) , (AB) , (AB) , (AB) , (AB)是命题公式。 (3) 只有有限步使用(1)和(2)所组成的包含命题变元、 联结词以及成对的括号组成的符号串才是命题公式。 这种定义叫归纳定义, 也叫递归定义。由这种定义产 生的公式也叫合式公式（Well-Formed Formulas），简 写为wff。 1.3 命题公式 Date19chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例5】 判断下列表达式是否为合式公式: p(pq) (pq)r) (p(qr) (pq)(qr) (pq)r) (pq)r) s) (pq)r) s （是） （是） （否） （否 ） （否 ） （是） （是） 1.3 命题公式 Date20chapter1 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 p 1.3 命题公式 Date21chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 (d) 此时，小刚要么在学习，要么在玩游戏。 解：设p：小刚在学习，q：小刚在玩游戏。 则原命题符号化为： (pq)(pq) 或 (pq)(pq) (e) 如果天不下雨，我们去打篮球，除非班上有会。 解：设p：今天天下雨，q：我们去打篮球，r：今天班上 有会。 则原命题符号化为： r (p q) 1.3 命题公式 Date22chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1、 重言式（Tautology） 重言式(永真式)真值恒为1的公式。如：PP 【例7】判断（P P(P Q)）是否为重言式。 P Q PQP(P Q) P P(PQ) 0 0 0 1 1 0 1 1 0 0 0 1 0 0 1 1 1 1 1 1 （P P(P Q)）为重言式。 1.4 重言式、矛盾式、可满足公式 Date23chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 2、 矛盾式（Contradiction) 矛盾式（永假式）真值恒为0的公式。如：P P 【例8】判断(PQ)P是否为矛盾式。 P Q PQ(PQ)P 0 0 0 1 1 0 1 1 0 0 0 1 0 0 0 0 （ (PQ)P ）为矛盾式。 1.4 重言式、矛盾式、可满足公式 Date24chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 3、 可满足公式（Satisfaction） 可满足公式至少有一种真值为1的情况。 (除矛盾式之外的公式) ，永真式也是可满足公式。 定理：由n个命题变元一共可组成 个不同的命题。其中 永真式有一个，矛盾式有一个，可满足公式有 个。 1.4 重言式、矛盾式、可满足公式 Date25chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例9】 构造公式PQ、(PQ)、PQ、Q P 的真值 。 解：真值表如下： 由例题可见，公式PQ、(PQ)、PQ、Q P的真值表是完全相同的，我们称其为等值的。那么如何判 断两个公式等值呢？ 1.5 等价与蕴涵 Date26chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1.5.1 等价 1、 等价的定义 等价设A、B是两个命题公式，当A与B有完全相 同的真值，则称A和B等价，即为AB。 定理：设A、B是两个命题公式， AB 的充要条件是 AB为永真式。 等价置换：假设X是公式A的子公式，如果XY，则将 X置换为Y所得的公式与A等价。 1.5 等价与蕴涵 Date27chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 2、 等价与双条件的区别 等价：不是一个联结词，AB不是一个命题公式，表 示的是A、B之间的逻辑关系。 双条件：是一个联结词， AB是命题公式。 1.5 等价与蕴涵 Date28chapter1 PropositionProposition 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) AB 1.5 等价与蕴涵 Date29chapter1 PropositionProposition 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) A 1.5 等价与蕴涵 Date30chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 思考： 证明两个公式等价的方法： 1、构造真值表。 2 、等价推导法。（若一个公式变元太多，由于n个变元 组成的真值表有2n行，所以用等价推导的方法来证明。） 1.5 等价与蕴涵 Date31chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例11】用等值演算证明p(qr) (pq)r。 证明： p(qr) p(qr) （蕴涵等值式） p(qr) （蕴涵等值式） (pq) r （结合律） (pq) r （德摩根律） (pq)r （蕴涵等值式） 1.5 等价与蕴涵 Date32chapter1 PropositionProposition 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 等价与蕴涵 Date33chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1.5.2 蕴含 1、蕴涵的定义 蕴含设A、B是两个命题公式，若A为真，B必定为 真，则称A蕴含B，记作AB。 定理：设A、B是两个命题公式， AB 的充要条件是 AB为永真式。 1.5 等价与蕴涵 Date34chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 2、蕴含与条件的区别 蕴含：不是一个联结词，AB不是一个命题公式，表 示的是A、B之间的逻辑关系。 条件：是一个联结词， AB是命题公式。 1.5 等价与蕴涵 Date35chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例13】 证明 (PQ)PQ 。 证明：真值表如下： 由真值表可见， (PQ)P为1时，Q为真。 (PQ)PQ P QP Q (PQ) P (PQ)P Q 0 0 0 1 1 0 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1.5 等价与蕴涵 Date36chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1.6.1 推理 推理已知H1、H2、Hm，证明C的过程。 写成命题逻辑的形式为： H1 H2 HmC 其中， H1、H2、Hm称为推理的前提，C为这一组前 提的有效结论。 推理的过程就是证明H1H2HmC的过程。 1.6.2 推理方法 证明H1H2Hm C为永真式。 1、真值表法 2、等价推导法 1.6 推理理论 Date37chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例14】证明 (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.6 推理理论 Date38chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 3、几种常用的推理的定律 (1) 假言推理（肯定的肯定） P(PQ)Q 通过肯定条件的前件从而肯定条件的后件。 如： PQ：如果他喝酒，则他脸红。 P：他喝酒。 Q：他脸红。 但是， PQ：如果他喝酒，则他脸红。 Q：他脸红。 P：他喝酒。 不成立 注意：不能通过肯定条件的后件而肯定条件的前件。 1.6 推理理论 Date39chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 (2) 拒取式（否定的否定） Q(PQ)P 通过否定条件的后件从而否定条件的前件。 如： PQ：小王评上三好学生，则小王成绩好。 Q ：小王成绩不好。 P ：小王没评上三好学生。 注意：不能通过否定条件的前件而肯定条件的后件。 1.6 推理理论 Date40chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 (3) 析取三段论 (PQ)PQ 产生一个事件的原因有P和Q，否定P，则一定是Q。 如： PQ：成绩不好是老师教得不好或自己不努力。 P ：老师教得好。 Q：自己不努力。 推广： (PQRS)PQR S 1.6 推理理论 Date41chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 (4) 假言三段论 (PQ)(QR)PR 如： PQ：如果不下雨，就开运动会。 QR：如果开运动会，就不上课。 PR ：如果不下雨，就不上课。 1.6 推理理论 Date42chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 1.6 推理理论 常用的蕴涵式 (9) P，PQQ； (10) Q，PQP； (11) P，PQQ； (12) PQ，QRPR； (13) PQ，PR，QRR； (14) PQ，RS(PR)(QS) ； (15) P，QPQ。 (1) PQP； (2) PQQ； (3) PPQ； (4) QPQ； (5) P(PQ)； (6) Q(PQ)； (7) (PQ)P； (8) (PQ)Q； Date43chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 4、证明方法（形式演绎） (1) P规则（前提引入规则）：给定的前提在证明的过程 中随时都可以加以引用。 (2) 规则（结论引用规则）：在证明过程中产生的结论 可以作为后续证明的前提加以引用。 (3) CP规则（附加前提引入规则）： 如果证明的形式为H1 H2 Hm AB，等价 于证明H1H2HmAB。A称为附加前提。 1.6 推理理论 Date44chapter1 PropositionProposition 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.6 推理理论 Date45chapter1 PropositionProposition LogicLogic 命题逻辑命题逻辑 【例15】证明 (PQ)(PR)(QS)(RS) 证明： PQ P PQ T QS P P