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