1离散数学离散数学(Discrete 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）， (AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。 （3）当当且且仅仅当当有有限限次次地地应应用用(1)(2)所所得得到到的的包包含含原原子公式、子公式、联结词和括号的符号串是合式公式。联结词和括号的符号串是合式公式。4第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.3命题命题公式与翻译公式与翻译例例1 1：指出(P(PQ)是否是命题公式(wff)，如果是，则具体说明。解： P是wff 由(1) Q是wff 由(1) PQ是wff 由(2) (P(PQ) 由(2) (PQ）(Q)，(PQ，(PQ）Q），PQ S , (P W) Q)不是合式公式。联结词的优先级：联结词的优先级：联结词的优先级：联结词的优先级：、。 则：则： PQR 是合式公式是合式公式等价于等价于WffWff ： （PQ）R ）命题公式外层的括号可以省略命题公式外层的括号可以省略等价于等价于WffWff ： （PQ）R不等价于不等价于WffWff ： P（QR）第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.3命题命题公式与翻译公式与翻译6第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.3命题命题公式与翻译公式与翻译1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)自然语言的语句用自然语言的语句用Wff 形式化形式化： 要准确要准确确定原子命题确定原子命题，并将其，并将其形式化形式化。 要选用恰当的联结词，尤其要善于要选用恰当的联结词，尤其要善于识别自然语言中的联识别自然语言中的联结词结词（有时它们被省略），（有时它们被省略），否定词的位置否定词的位置要放准确。要放准确。 必要必要时可以时可以进行改述进行改述，即改变原来的叙述方式，即改变原来的叙述方式，但要保证表达意思一致但要保证表达意思一致。 需要的需要的括号不能省略括号不能省略，而可以省略的括号，而可以省略的括号，在需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。 要注意语句的形式化要注意语句的形式化未必是唯一未必是唯一的。的。可以把本命题表达为：(P Q）。 解 P：上海到北京的14次列车是下午五点半开。 Q：上海到北京的14次列车是下午六点开。在本例中，汉语的“或”是不可兼或，而逻辑联结词是“可兼或”，因此不能直接对两命题析取。构造如表1-3.1所示。PQ原命题PQ(P Q)TT F T FTF T F TFT T F TFF F T F表1-3.1例题例题2 2 上海到北京的上海到北京的1414次列车是下午五点半或六点次列车是下午五点半或六点开。开。 解 这个命题的意义，亦可理解为： 如果你不努力则你将失败。 若设 P：你努力。 Q：你失败。 本例可表示为： PQ例题例题5 5 除非你努力，否则你将失败。除非你努力，否则你将失败。 解 这个命题的意义是： 可兼或 若设 P：张三可以做这事。 Q：李四可以做这事。 本例可表示为： P Q例题例题6 6 张三或李四都可以做这件事。张三或李四都可以做这件事。10第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.3命题命题公式与翻译公式与翻译1) 1) 我今天进城，除非下雨。我今天进城，除非下雨。1-3.(7)1-3.(7)2) 2) 仅当你走我将留下。仅当你走我将留下。 1-3.(7) 1-3.(7)3) 3) 假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里 读书或看报。读书或看报。 1-3.(7) 1-3.(7)4)4)一个人起初说：一个人起初说：“占据空间的、有质量的而且不占据空间的、有质量的而且不断变化的叫做物质断变化的叫做物质”；后来他改说，；后来他改说，“占据空间占据空间的有质量的叫做物质，而物质是不断变化的。的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式问他前后主张的差异在什么地方，试以命题形式进行分析进行分析。 1-3.(6)1-3.(6)练习练习111第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.3命题命题公式与翻译公式与翻译1)1)我今天进城，除非下雨。我今天进城，除非下雨。1-3.(7)1-3.(7)P：我今天进城。Q:天下雨。 QP2) 2) 仅当你走我将留下。仅当你走我将留下。 1-3.(7) 1-3.(7)P: 你走。 Q:我留下。 QP3) 3) 假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里 读书或看报。读书或看报。 1-3.(7) 1-3.(7)P: 上午下雨。 Q:我去看电影。 R:我在家里读或看报。(PQ)(PR)）（要么看电影要么留在家里，排斥或）解答12第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.3命题命题公式与翻译公式与翻译5)5)一个人起初说：一个人起初说：“占据空间的、有质量的而且不断变化占据空间的、有质量的而且不断变化的叫做物质的叫做物质”；后来他改说，；后来他改说，“占据空间的有质量的占据空间的有质量的叫做物质，而物质是不断变化的。叫做物质，而物质是不断变化的。”问他前后主张的问他前后主张的差异在什么地方，试以命题形式进行分析。差异在什么地方，试以命题形式进行分析。 1-1-3.(6)3.(6)P:它占据空间Q:它有质量R:它不断变化S:它是物质这个人起初主张：(PQR) S后来主张：(（PQ）S)(SR)解答练习练习2 （小李不在图书馆），（他要么找老师去了），（要么就（小李不在图书馆），（他要么找老师去了），（要么就是因为身体不适，回宿舍去了）。是因为身体不适，回宿舍去了）。命题符号化是很重要的，一定要掌握好，在命题推命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。好，等于说推理的首要前提没有了。解解 设设 P P：小李在图书馆。：小李在图书馆。Q Q：小李找老师。：小李找老师。 R R：小李身体不适。：小李身体不适。S S：小李回宿舍。：小李回宿舍。则命题符号化为：则命题符号化为： （P P）（(Q (RS)(Q (RS)）（小李不是（小李不是而是而是 ）（要么（要么要么要么 排斥或）排斥或）14第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic）1.3命题命题公式与翻译公式与翻译小结小结：本节介绍了命题公式的概念及复：本节介绍了命题公式的概念及复合命题的符号化合命题的符号化.重点是理解命题公式的重点是理解命题公式的递归定义递归定义,掌握复合命题的符号化方法掌握复合命题的符号化方法.作业：作业：p12(5)15离散数学离散数学(Discrete Mathematics)1.4.1 真值表真值表(Truth Table)1.4.2 等价公式等价公式(Propositional Equivalences)Propositional Equivalences)16第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表与等价公式真值表与等价公式定定义义1.4.2(真真值值表表) 在在命命题题公公式式A中中, 对对于于命命题题变变元元的的每每一一组组赋赋值值和和由由它它们们所所确确定定的的命命题题公公式式A的的真真值值列列成成表表，称做命题公式称做命题公式A 的的真值表真值表。考考虑虑：含含有有n个个命命题题变变元元的的公公式式共共有有多多少少组组不不同同的的赋赋值值？2n17第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表与等价公式真值表与等价公式对公式对公式A构造真值表的具体步骤为：构造真值表的具体步骤为：（1）找出公式中所有命题变元）找出公式中所有命题变元P1 , P2 ,Pn（2）按按从从小小到到大大的的顺顺序序列列出出对对命命题题变变元元P1 , P2 ,Pn ,的全部的全部2n组赋值。组赋值。（3）对对应应各各组组赋赋值值计计算算出出公公式式A的的真真值值，并并将将其其列列在对应赋值的后面。在对应赋值的后面。18第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式例例1. 1. 给出给出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q(P(P Q Q) )PP QQ(P(P Q) Q) (P(P Q)Q)0 0 0 00 0 1 11 1 0 01 1 1 119第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式例例1. 1. 给出给出(P(P Q)Q)(P(P Q)Q)的真值表：的真值表：P P Q Q P P Q Q(P(P Q Q) )PP QQ(P(P Q) Q) (P(P Q)Q)0 0 0 00 0 1 11 1 0 01 1 1 10 00 00 01 11 11 11 10 01 11 11 10 01 11 11 11 120第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式例例2：构造公式：构造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R00000101001110010111011121第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式例例2：构造公式：构造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R000100011101010011111000010100110101111122第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式练习练习1：构造公式：构造公式 (PQ)( Q P）真值表。真值表。PQ P QP Q Q P(P Q)( Q P)0001101123第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式练习练习1：构造公式：构造公式 (PQ)( Q P）真值表。真值表。PQ P QP Q Q P(P Q)( Q P)001111101101111001001110011124第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式PQ (P Q) (P Q) (P Q) Q00011011练习练习2：构造公式：构造公式 (P Q） Q 真值表。真值表。25第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式PQ (P Q) (P Q) (P Q) Q00100011001001011100练习练习2：构造公式：构造公式 (P Q） Q 真值表。真值表。永真公式永真公式 永假公式：永假公式：无论对其分量作怎样的真值指派，其真值永为无论对其分量作怎样的真值指派，其真值永为T，称为永真公式，记为称为永真公式，记为T 。如例如例1无论对其分量作怎样的真值指派，其真值永为无论对其分量作怎样的真值指派，其真值永为F，称为永假公式，记为称为永假公式，记为F 。如例如例2 第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式 从真值表中可以看到，从真值表中可以看到，有些命题公式有些命题公式在分量的不同指派在分量的不同指派下，其对应的真值与下，其对应的真值与另一命题公式完全相同另一命题公式完全相同，如，如P Q与与PQ的对应真值相同，如表的对应真值相同，如表1-4.5所示。所示。 PQPQPQTT T TTF F FFT T TFF T T表1-4.5我们说我们说P Q和和PQ是等价的，这是等价的，这在以后的推理中特在以后的推理中特别有用。别有用。第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式1.4.2 等价公式等价公式 同理(PQ)(PQ)与P Q对应的真值相同，如表1-4.6所示。 表1-4.6 P Q PQ (PQ)(PQ)TT T TTF F FFT F FFF T T第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式1.4.2 等价公式等价公式29第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式定义定义1.4.3: 给定两个命题公式给定两个命题公式A和和B,设设P1 , P2 ,Pn为出现为出现于于A和和B中的所有原子变元中的所有原子变元,若给若给P1 , P2 ,Pn任一组任一组真值指派真值指派, A和和B的真值都相同的真值都相同,则则称称A和和B是等价是等价. 记作记作A B。1.4.2 等价公式等价公式30第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 见真值表例题见真值表例题1.1.例例2. 2. 证明证明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)(PQ) (QP(QP) )0 00 00 01 11 10 01 11 1证明公式等价的方法：证明公式等价的方法：31第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式1. 真值表法真值表法 2. 等值演算法等值演算法1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 见真值表例题见真值表例题1.1.例例2. 2. 证明证明: P: PQ Q (PQ)(PQ) (QP)(QP)P PQ QP PQ QQPQPPQPQ (PQ)(PQ) (QP(QP) )0 00 01 11 11 11 10 01 10 00 01 10 01 10 00 01 10 00 01 11 11 11 11 11 1所以：所以：P PQ Q (PQ)(PQ) (QP)(QP)(PQ)(PQ)试用等值演算方法证明试用等值演算方法证明另外，另外， P PQ Q (PQ) (Q P)32第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式2. 等值演算法等值演算法(Equivalent Caculation)（利用（利用P15表表1-4.8)重要的等价式重要的等价式(补充补充): 11. 蕴涵等值式蕴涵等值式: : P PQ Q PP Q Q Q Q PP Q Q PP（假言易位）（假言易位） 12. 等价等价等值式等值式: : P PQ Q (PQ)(PQ) (QP)(QP) (PQ) (Q P) (PQ) (Q P) (PQ)(PQ)(PQ)(PQ) 13. 假言易位假言易位: P PQ Q Q Q PP 14. 等价否定等值式等价否定等值式: P PQ Q PPQ Q 15. 归谬论归谬论: (P PQ Q ) ( ( P P Q)Q) P P 对合律P P1幂等律PP P，PP P2结合律(PQ）R P（QR）(PQ）R P（QR）3交换律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P（QR） （PQ）（PR）5吸收律P（PQ） PP（PQ） P6德摩根律(PQ) PQ(PQ) PQ7同一律PF P，PT P8零律PT T，PF F9否定律PP T，PP F10表1-4.8命题定律任何数与0相或还是任何数任何数任何数与1相与为为1任何数与1相与还是任何数任何数与0相与为为0例题6 验证吸收律 P（PQ） P P（PQ） P证明 列出真值表 表1-4.9PQPQP（PQ）PQP（PQ）TT T T T TTF F T T TFT F F T FFF F F F F 由表1-4.9可知吸收律成立。练习18页（4）35第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式 等值等值演算中使用的一条重要规则：演算中使用的一条重要规则：置换规则。置换规则。定义定义1.4.4 子公式：子公式：如果如果X X是是wff Awff A的一部分的一部分, ,且且X X本身也是本身也是wffwff，则称则称X X是是A A的子公式的子公式。 例如例如, , P(PQ)为为Q Q (P P (P(P Q)Q)的子公式的子公式。定理定理1.4.1 置换定理：置换定理：设设X X是是wff Awff A的子公式，若的子公式，若X XY Y，则若将，则若将A A中的中的X X用用Y Y来置换，所得公式来置换，所得公式B B与与A A等价，即等价，即A AB B。定义定义1.4.51.4.5 等值演算：等值演算：根据已知的等价公式根据已知的等价公式, ,推演出另外一些等推演出另外一些等价公式的过程称为价公式的过程称为等值演算等值演算. .36第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式例例1 1： 证明证明 QQ（P P （P P Q Q）QPQP 证证: Q: Q（P P （P P Q Q）QPQP P( P(吸收律吸收律) ) 例例2 2： 证明证明 （P P QQ） Q Q P P Q Q 证：证： (P(P Q)Q) Q Q(P(P Q)Q) ( (QQ Q)Q)( (P P Q)Q) T TP P Q Q例例3 3：证明（：证明（PQPQ）（Q Q R R） P P Q Q R R证：（证：（PQPQ）（Q Q R R）（P P Q Q）（Q Q R R） ( (P P Q)Q) （Q Q R R） （P P QQ） （Q Q R R） （P P Q Q R R） （Q Q Q Q R R） (P Q R) (Q Q Q Q) ) R)R) (P Q R) (T(T R)R) (P Q R) T T (P Q R) 37第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式例例4：验证：验证P(QR) (P Q) R证证: 右右 (P Q) R（蕴含等值）（蕴含等值） P Q R（德摩根律）（德摩根律） P ( Q R) （结合律）（结合律） P (Q R) （蕴含等值）（蕴含等值） P (Q R) （蕴含等值）（蕴含等值） 例例5：根据真值表方法根据真值表方法“排斥或排斥或”可表示为可表示为 (P(PQ )Q ) 证明：证明：(P(PQ )Q ) ( (PP Q) Q) ( (Q Q P P) ) 证证: : (P PQ Q ) ) （PQPQ） （Q QP P） （ P P Q Q） （Q Q P P） （PP Q Q） （QQ P P） （P P QQ） （P P Q Q）练：练：1.(P Q) (P R) P (Q R) 2.(P Q) ( P Q) (P Q) (P Q) 39第一章第一章 命题逻辑命题逻辑（Propositional LogicPropositional Logic） 1.4真值表真值表与等价公式与等价公式v等等值值演演算算在在计计算算机机硬硬件件设设计计中中,在在开开关关理理论论和和电电子子元元器器件中都占有重要地位件中都占有重要地位.v小小结结: 本本节节介介绍绍了了真真值值表表、公公式式等等价价、等等值值演演算算和和等等价价置置换换等等概概念念，给给出出了了常常用用的的重重要要等等价价公公式式（24个个）。重重点点掌掌握握用用真真值值表表法法验验证证公公式式的的等等价价性性和和等等值值演演算算法法推演两个公式等价。推演两个公式等价。作业：作业：P19 （7）.预习预习: 1.5, 1.6思考题：思考题：