左孝凌离散数学课件1.3命题公式与翻译-1.4真值表与等价公式.ppt

1离散数学离散数学( (Discrete MathematicsDiscrete Mathematics) )1.3.1 命题公式 1.3.2 复合命题的符号化(翻译)2第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译1.3.1 合式公式(Well-formed formula)(wff)定义1.3.1:原子公式单个命题变元和命题常量称为原子公式3第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译定义1.3.2：合式公式(1)原子公式是合式公式(wff) （2）若A，B是合式公式，则（ A）， (A∧B)， (A∨B)，(AB)，(AB)也是合式公式3）当且仅当有限次地应用(1)(2)所得到的包含原 子公式、联结词和括号的符号串是合式公式4第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译例1：指出(P→(PQ))是否是命题公式(wff)，如果是，则 具体说明。

解： ① P是wff 由(1)② Q是wff 由(1)③ PQ是wff 由(2) ①②④ (P→(PQ)) 由(2) ①③(P→Q）→(∧Q)，(P→Q，(P∧Q）→Q），PQ ∨S , (P  W) Q)不是合式公式• • 联结词的优先级：联结词的优先级：┐、∧、∨、→、 则： P∧Q→R 是合式公式 等价于WffWff ： （（P∧Q）→R ）命题公式外层的括号可以省略 等价于WffWff ： （P∧Q）→R 不等价于WffWff ： P∧（Q→R）第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译6第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译• 1.3.2 复合命题的符号化(翻译) • 自然语言的语句用WffWff 形式化： ① 要准确确定原子命题，并将其形式化。

② 要选用恰当的联结词，尤其要善于识别自然语言中的联 结词（有时它们被省略），否定词的位置要放准确 ③ 必要时可以进行改述，即改变原来的叙述方式， 但要保证表达意思一致 ④ 需要的括号不能省略，而可以省略的括号， 在需要提高公式可读性时亦可不省略 ⑤ 要注意语句的形式化未必是唯一的可以把本命题表达为 ：┐(P ↔Q）解 P：上海到北京的14次列车是下午五点半开Q：上海到北京的14次列车是下午六点开 在本例中，汉语的“或”是不可兼或，而逻辑联结词∨是“可兼或 ”，因此不能直接对两命题析取构造如表1-3.1所示PQ原命题P↔Q┐(P ↔ Q) TT F T F TF T F T FT T F T FF F T F表1-3.1例题2 上海到北京的14次列车是下午五点半或六点开 解 这个命题的意义，亦可理解为：如果你不努力则你将失败若设P：你努力 Q：你失败本例可表示为：┐P→Q例题5 除非你努力，否则你将失败解 这个命题的意义是：可兼或若设P：张三可以做这事 Q：李四可以做这事。

本例可表示为：P ∨ Q例题6 张三或李四都可以做这件事10第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译1) 我今天进城，除非下雨[1-3.(7)] 2) 仅当你走我将留下 [1-3.(7)] 3) 假如上午不下雨，我去看电影，否则就在家里读书或看报 [1-3.(7)] 4)一个人起初说：“占据空间的、有质量的而且不断 变化的叫做物质”；后来他改说，“占据空间的 有质量的叫做物质，而物质是不断变化的问 他前后主张的差异在什么地方，试以命题形式进 行分析 [1-3.(6)]练习111第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译1)我今天进城，除非下雨[1-3.(7)] P：我今天进城Q:天下雨 ┓Q→P 2) 仅当你走我将留下 [1-3.(7)] P: 你走 Q:我留下 Q→P 3) 假如上午不下雨，我去看电影，否则就在家里读书或看报 [1-3.(7)] P: 上午下雨。

Q:我去看电影 R:我在家里读或看报 ┓(┓P→Q)↔(P→R)）（要么看电影要么留在家里，排斥或）解答12第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译5)一个人起初说：“占据空间的、有质量的而且不断变化 的叫做物质”；后来他改说，“占据空间的有质量的 叫做物质，而物质是不断变化的问他前后主张的 差异在什么地方，试以命题形式进行分析 [1-3.(6)] P:它占据空间Q:它有质量R:它不断变化S:它是物质 这个人起初主张：(P∧Q∧R)  S 后来主张：(（P∧Q）S)∧(S→R)解答• 练习2 （小李不在图书馆），（他要么找老师去了），（要么就 是因为身体不适，回宿舍去了）命题符号化是很重要的，一定要掌握好，在命题推 理中常常最先遇到的就是符号化一个问题，解决不 好，等于说推理的首要前提没有了解 设 P：小李在图书馆Q：小李找老师R：小李身体不适S：小李回宿舍 则命题符号化为： （┐P）∧（┐(Q (R→S)） （小李不是……而是…… ∧ ） （要么……要么…… 排斥或）14第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.3命题 公式与翻译• 小结：本节介绍了命题公式的概念及复 合命题的符号化.重点是理解命题公式的 递归定义,掌握复合命题的符号化方法. • 作业：p12(5)15离散数学离散数学( (Discrete MathematicsDiscrete Mathematics) )1.4.1 真值表(Truth Table) 1.4.2 等价公式 (Propositional Equivalences)Propositional Equivalences)16第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.41.4真值表与等价公式真值表与等价公式定义1.4.2(真值表) 在命题公式A中, 对于命题变元的每 一组赋值和由它们所确定的命题公式A的真值列成表 ，称做命题公式A 的真值表。

考虑：含有n个命题变元的公式共有多少组不同的赋值 ？2n17第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic））1.41.4真值表与等价公式真值表与等价公式对公式A构造真值表的具体步骤为： （1）找出公式中所有命题变元P1 , P2 ,…,Pn （2）按从小到大的顺序列出对命题变元P1 , P2 ,…,Pn ,的全部2n组赋值 （3）对应各组赋值计算出公式A的真值，并将其列 在对应赋值的后面18第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式例1. 给出┐(PQ)(┐P┐Q)的真值表：P Q PQ ┐(PQ )┐P┐Q┐(PQ)  (┐P┐Q)0 00 11 01 119第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式例1. 给出┐(PQ)(┐P┐Q)的真值表：P Q PQ ┐(PQ )┐P┐Q┐(PQ)  (┐P┐Q)0 00 11 01 1000111101110111120第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式 例2：构造公式 (P Q) ∧R的 真值表。

PQRPQ(P Q) ∧R000 001010 011 100 101 110 11121第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式 例2：构造公式 (P Q) ∧R的 真值表PQRPQ(P Q) ∧R00010 0011101010 01111 10000 10100 11010 1111122第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式• 练习1：构造公式 (PQ)( Q P）真值表PQ  P  QP  Q Q P(P  Q)( Q   P)0001101123第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式• 练习1：构造公式 (PQ)( Q P）真值表PQ P  QP  Q Q P(P  Q)( Q   P)001111101101111001001110011124第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式PQ (P  Q) (P  Q)  (P  Q) ∧ Q00011011练习2：构造公式  (P Q） ∧Q 真值表。

25第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式PQ (P  Q) (P  Q)  (P  Q) ∧ Q00100011001001011100练习2：构造公式  (P Q） ∧Q 真值表永真公式 永假公式： • 无论对其分量作怎样的真值指派，其真值永为T， 称为永真公式，记为T 如例1 • 无论对其分量作怎样的真值指派，其真值永为F， 称为永假公式，记为F 如例2第一章第一章 命题逻辑命题逻辑（（Propositional LogicPropositional Logic）） 1.41.4真值表真值表 与等价公式与等价公式从真值表中可以看到，有些命题公式在分量的不同指派 下，其对应的真值与另一命题公式完全相同，如┐P∨Q与 P→Q的对应真值相同，如表1-4.5所示 PQ┐P∨QP→QTT T TTF F FFT T T FF T T表1-4.5我们说┐P∨Q和 P→Q是等价的，这 在以后的推理。