《离散数学命题逻辑》由会员分享，可在线阅读，更多相关《离散数学命题逻辑（51页珍藏版）》请在金锄头文库上搜索。
1、第一章 命题逻辑Proposition Logic1.1 命题及其表示法1.2 联结词1.3 命题公式与翻译1.4 重言式、矛盾式、可满足公式1.5 等价与蕴含1.6 推理理论*1chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 1.1 命题及其表示法1、命题命题非真即假的陈述句。命题的真值对，成立，则真值为真，T，1 错，不成立，则真值为假，F，0 断言是一陈述语句。一个命题是一个或真或假而不能两者都是的断言。如果命题是真, 我们说它的真值为真；如果命题是假，我们说它的真值是假。Date2chapter1PropositionProposi
2、tion LogicLogic 命题逻辑命题逻辑 【例1 】判定下列各语句是否为命题：(a) 巴黎在法国。(b) 煤是白色的。(c) 3+2=5(d) 别的星球上有生物。(e) 全体立正。(f) 明天是否开大会？(g) 天气多好啊！(h) 我正在说谎。(i) 如果天气好，那么我去散步。(j) x3（是）（是） （是） （是）（否，祈使句） （否，疑问句） （否，感叹句） （否, 悖论） （是,复合命题）（否，不能确定真值）1.1 命题及其表示法Date3chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 2、命题的表示命题变元常用P、Q、R、S
3、等大写字母或加下标的大写字母P1, Q2, R10, 表示来表示一个命题，称为命题变元。如： P:巴黎在法国。Q:煤是白色的。1.1 命题及其表示法Date4chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 3、命题相关概念简单命题（原子命题）不能再分解的命题。复合命题由若干个简单命题复合而成的命题。真值表把组成复合命题的各命题变元的真值的所有组合及其相对应的复合命题的真值列成表，称为真值表。1.1 命题及其表示法Date5chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 【例2 】求公式(
4、PQ)P的真值表。 解： 分以下步求得: (1) 写出公式P的真值表;(2) 写出公式PQ的真值表; (3) 根据(1)和(2), 写出公式(PQ)P的真值表。 为清楚起见, 我们将这步列在一个表内, 见下表。1.1 命题及其表示法Date6chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 【例3 】求公式 (PR)(QR)的真值表。 解：公式含有个命题变元P、Q、R, 真值表有3=8行。其真值表如下表 所示： 1.1 命题及其表示法Date7chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑
5、 1.2 联结词命题和原子命题常可通过一些联结词构成新命题, 这种新命题叫复合命题（Compositional Proposition ）。例如：P: 明天下雪, Q: 明天下雨是两个命题, 利用联结词“不”, “并且”, “或”等可构成新命题:“明天不下雪”； “明天下雪并且下雨”；“明天下雪或下雨”等 。Date8chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 1.2 联结词即 ：“非P”；“P并且Q”；“P或Q”等 。在代数式x+3 中, x , 3 叫运算对象, +叫运算符, x+3 表示运算结果。在命题演算中, 联结词就是命题演算
6、中的运算符, 叫逻辑运算符或叫逻辑联结词。常用的有以下 5 个。Date9chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 1、否定 P是P的否定，读作“非P”， “ P的否定” 。 0 1 1 0 p如： P:成都是中国的首都。P：成都不是中国的首都。 否定与汉语中的“非”、“不是”、“否定”是一致的。1.2 联结词Date10chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 2、合取 PQ是P和Q的合取, 读做“P与Q”或“P并且Q”。如： P: 王华的成绩很好。Q: 王华的品德很好。P
7、Q: 王华的成绩很好并且品德很好。合取与汉语中的“和”、“与”、“并且”是一致的。P QP Q0 0 0 1 1 0 1 10 0 0 11.2 联结词Date11chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 3、析取 PQ是P和Q的析取, 读做“P或Q”。如： P:小王喜欢唱歌。Q:小王喜欢跳舞 。P Q:小王喜欢唱歌或喜欢跳舞 。从真值表可知PQ为真, 当且仅当P或Q至少有一为真。P QP Q 0 0 0 1 1 0 1 10 1 1 11.2 联结词Date12chapter1PropositionProposition Logic
8、Logic 命题逻辑命题逻辑 “或”字常见的含义有两种: 一种是“可兼或”, 如上例中的或, 它不排除小王既喜欢唱歌又喜欢跳舞这种情况。一种是“排斥或”（异或）, 例如“人固有一死, 或重于泰山, 或轻于鸿毛”中的“或”, 它表示非此即彼, 不可兼得。运算符表示可兼或, 排斥或以后用另一符号表达。如：(1)小李明天出差去上海或去广州。(2)刘昕这次考试可能是全班第一也可能是全班第二。这两例表示的均是排斥或，即两种情况不能同时出现，这时便不能仅用析取词表示。 1.2 联结词Date13chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 4、条件
9、PQ, 读做 “如果P, 那么Q”或“P则Q” 。 运算对象P叫做前提 , 假设或前件, 而Q叫做结论或后件。P QP Q 0 0 0 1 1 0 1 11 1 0 11.2 联结词如： P:雪是黑的。Q:太阳从东方升起 。P Q:如果雪是黑的，则太阳从东方升起 。 命题PQ是假, 当且仅当P是真而Q是假。Date14chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 条件与汉语中“如果，就”相类似，但有所区别:(1)自然语言中，“如果P则Q”，往往P和Q有一定的因果关系，而条件复合命题PQ中 P和Q 可以完全不相关。(2)自然语言中，“如果P
10、则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 联结词Date15chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 如：小李对小王说：“如果天不下雨，我就来找你”。天没下雨，小李去找了小王。天没下雨，小李没去找小王。天下雨了，小李去找了小王。天下雨了，小李没去找小王。1.2 联结词【例4 】电灯不亮是电灯坏或电路有毛病。解：设P电灯
11、不亮，Q电灯坏，R电路有毛病。上述语句应表示为: (Q R) PDate16chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 5、双条件 P Q, 读做 “P当且仅当Q” 。如： P:两个三角形全等。Q:两个三角形的对应边相等 。P Q:两个三角形全等当且仅当其对应边相等 。P当且仅当Q的逻辑含义:P和Q互为充要条件 。P QP Q 0 0 0 1 1 0 1 11 0 0 11.2 联结词Date17chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 6、联结词的优先次序联结词的优先级： ,
12、 , , , ，括号优先。如： (PQ)R 可写成 ：PQR(PQ)R 可写成：PQR(P Q)R)(RP)Q)可写成： (P QR)RPQ为方便起见，公式最外层的括号可省略。有时为了看起来清楚醒目, 也可保留某些原可省去的括号。 1.2 联结词Date18chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 单个命题变元和命题常元叫原子公式。由以下形成规则生成的公式叫命题公式 (简称公式):(1) 单个原子公式A、B是命题公式。(2) 如果A和B是命题公式, 则(A) , (AB) , (AB) , (AB) , (AB)是命题公式。 (3)
13、只有有限步使用(1)和(2)所组成的包含命题变元、联结词以及成对的括号组成的符号串才是命题公式。这种定义叫归纳定义, 也叫递归定义。由这种定义产生的公式也叫合式公式（Well-Formed Formulas），简写为wff。1.3 命题公式Date19chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 【例5】 判断下列表达式是否为合式公式:p(pq) (pq)r)(p(qr)(pq)(qr) (pq)r)(pq)r) s)(pq)r) s（是）（是）（否）（否 ）（否 ）（是）（是）1.3 命题公式Date20chapter1Proposit
14、ionProposition 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 命题公式Date21chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 (d) 此时，小刚要么在学习，要么在玩游戏。解：设p：小刚在学习，q：小刚在玩游戏。则原命题符号化为： (pq)(pq)或 (pq)(pq)(e) 如果天不下雨，我们去打篮球，除非班上有会。解：设p：今天天下雨，q：我们去打篮球，r：今天班上有会。则原命题符号化为： r (p q)1.3 命题公式Date22chapter1PropositionProposition LogicLogic 命题逻辑命题逻辑 1、 重言式（Tautology）重言式(永真式)真值恒为1的公式。如：PP【例7】判断（P P(P Q)）是否为重言式。P Q PQP(P Q)P P(PQ) 0 0 0
