左孝凌离散数学13命题公式与翻译14真值表与等价课件

《左孝凌离散数学13命题公式与翻译14真值表与等价课件》由会员分享，可在线阅读，更多相关《左孝凌离散数学13命题公式与翻译14真值表与等价课件（39页珍藏版）》请在装配图网上搜索。

1、左孝凌离散数学13命题公式与翻译14真值表与等价11.3.1 命题公式命题公式1.3.2 复合命题的符号化复合命题的符号化(翻译翻译)左孝凌离散数学13命题公式与翻译14真值表与等价21.3命命题公式与翻译题公式与翻译1.3.1 合式公式合式公式(Well-formed formula)(wff)定义定义1.3.1: :原子公式原子公式 单个单个命题变元命题变元和和命题常量命题常量称为称为原子公式原子公式。左孝凌离散数学13命题公式与翻译14真值表与等价31.3命命题公式与翻译题公式与翻译定义定义1.3.2：合式公式：合式公式 (1)原子公式原子公式是是合式公式合式公式(wff)。 （2）若）

2、若A，B是合式公式，则（是合式公式，则（ A），）， (AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。 （3）当且仅当当且仅当有限次地应用有限次地应用(1)(2)所得到的包含所得到的包含原原子公式、子公式、联结词和括号的符号串是合式公式。联结词和括号的符号串是合式公式。左孝凌离散数学13命题公式与翻译14真值表与等价41.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

3、 W) Q)不是合式公式。左孝凌离散数学13命题公式与翻译14真值表与等价、。则：则： PQR 是合式公式是合式公式等价于等价于 ： （PQ）R ）命题公式外层的括号可以省略命题公式外层的括号可以省略等价于等价于 ： （PQ）R不等价于不等价于 ： P（QR）1.3命命题公式与翻译题公式与翻译左孝凌离散数学13命题公式与翻译14真值表与等价61.3命命题公式与翻译题公式与翻译 1.3.2 复合命题的符号化复合命题的符号化(翻译翻译) 自然语言的语句用自然语言的语句用 形式化形式化： 要准确要准确确定原子命题确定原子命题，并将其，并将其形式化形式化。 要选用恰当的联结词，尤其要善于要选用恰当的联

4、结词，尤其要善于识别自然语言中的联识别自然语言中的联结词结词（有时它们被省略），（有时它们被省略），否定词的位置否定词的位置要放准确。要放准确。 必要必要时可以时可以进行改述进行改述，即改变原来的叙述方式，即改变原来的叙述方式，但要保证表达意思一致但要保证表达意思一致。 需要的需要的括号不能省略括号不能省略，而可以省略的括号，而可以省略的括号，在需要提高公式可读性时亦可不省略。在需要提高公式可读性时亦可不省略。 要注意语句的形式化要注意语句的形式化未必是唯一未必是唯一的。的。左孝凌离散数学13命题公式与翻译14真值表与等价可以把本命题表达为：(P Q）。 解 P：上海到北京的14次列车是下午五

5、点半开。 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次列车是下午五点半或六点开。次列车是下午五点半或六点开。左孝凌离散数学13命题公式与翻译14真值表与等价 解 这个命题的意义，亦可理解为： 如果你不努力则你将失败。 若设 P：你努力。 Q：你失败。 本例可表示为： PQ例题例题5 5 除非你努力，否则你将失败。除非你努力，否则你将失败。左孝

6、凌离散数学13命题公式与翻译14真值表与等价 解 这个命题的意义是： 可兼或 若设 P：张三可以做这事。 Q：李四可以做这事。 本例可表示为： P Q例题例题6 6 张三或李四都可以做这件事。张三或李四都可以做这件事。左孝凌离散数学13命题公式与翻译14真值表与等价101.3命命题公式与翻译题公式与翻译1) 1) 我今天进城，除非下雨。我今天进城，除非下雨。1-3.(7)1-3.(7)2) 2) 仅当你走我将留下。仅当你走我将留下。 1-3.(7) 1-3.(7)3) 3) 假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里 读书或看报。读书或看报。 1-3.(7

7、) 1-3.(7)4)4)一个人起初说：一个人起初说：“占据空间的、有质量的而且不断占据空间的、有质量的而且不断变化的叫做物质变化的叫做物质”；后来他改说，；后来他改说，“占据空间的占据空间的有质量的叫做物质，而物质是不断变化的。有质量的叫做物质，而物质是不断变化的。”问问他前后主张的差异在什么地方，试以命题形式进他前后主张的差异在什么地方，试以命题形式进行分析行分析。 1-3.(6)1-3.(6)练习练习1左孝凌离散数学13命题公式与翻译14真值表与等价111.3命命题公式与翻译题公式与翻译我今天进城，除非下雨。我今天进城，除非下雨。1-3.(7)1-3.(7)P：我今天进城。Q:天下雨。

8、QP2) 2) 仅当你走我将留下。仅当你走我将留下。 1-3.(7) 1-3.(7)P: 你走。 Q:我留下。 QP3) 3) 假如上午不下雨，我去看电影，否则就在家里假如上午不下雨，我去看电影，否则就在家里 读书或看报。读书或看报。 1-3.(7) 1-3.(7)P: 上午下雨。 Q:我去看电影。 R:我在家里读或看报。(PQ)(PR)）（要么看电影要么留在家里，排斥或）解答左孝凌离散数学13命题公式与翻译14真值表与等价121.3命命题公式与翻译题公式与翻译5)5)一个人起初说：一个人起初说：“占据空间的、有质量的而且不断变化占据空间的、有质量的而且不断变化的叫做物质的叫做物质”；后来他改

9、说，；后来他改说，“占据空间的有质量的占据空间的有质量的叫做物质，而物质是不断变化的。叫做物质，而物质是不断变化的。”问他前后主张的问他前后主张的差异在什么地方，试以命题形式进行分析。差异在什么地方，试以命题形式进行分析。 1-3.(6)1-3.(6)P:它占据空间Q:它有质量R:它不断变化S:它是物质这个人起初主张：(PQR) S后来主张：(（PQ）S)(SR)解答左孝凌离散数学13命题公式与翻译14真值表与等价 练习练习2 （小李不在图书馆），（他要么找老师去了），（要么就（小李不在图书馆），（他要么找老师去了），（要么就是因为身体不适，回宿舍去了）。是因为身体不适，回宿舍去了）。命题符号

10、化是很重要的，一定要掌握好，在命题推命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。好，等于说推理的首要前提没有了。解解 设设 P P：小李在图书馆。：小李在图书馆。Q Q：小李找老师。：小李找老师。 R R：小李身体不适。：小李身体不适。S S：小李回宿舍。：小李回宿舍。则命题符号化为：则命题符号化为： （P P）（(Q (RS)(Q (RS)）（小李不是（小李不是而是而是 ）（要么（要么要么要么 排斥或）排斥或）左孝凌离散数学13命题公式与翻译14真值表与等价141.3命命题

11、公式与翻译题公式与翻译 小结小结：本节介绍了命题公式的概念及复：本节介绍了命题公式的概念及复合命题的符号化合命题的符号化.重点是理解命题公式的重点是理解命题公式的递归定义递归定义,掌握复合命题的符号化方法掌握复合命题的符号化方法. 作业：作业：p12(5)左孝凌离散数学13命题公式与翻译14真值表与等价151.4.1 真值表真值表(Truth Table)1.4.2 等价公式等价公式(左孝凌离散数学13命题公式与翻译14真值表与等价16定义定义1.4.2(真值表真值表) 在命题公式在命题公式A中中, 对于命题变元的每对于命题变元的每一组赋值一组赋值和由它们所确定的和由它们所确定的命题公式命题公

12、式A的真值列成的真值列成表表，称做命题公式，称做命题公式A 的的真值表真值表。考虑：考虑：含有含有n个命题变元个命题变元的公式共有的公式共有多少组不同的赋值多少组不同的赋值？2n左孝凌离散数学13命题公式与翻译14真值表与等价17对公式对公式A构造真值表的具体步骤为：构造真值表的具体步骤为：（1）找出公式中所有命题变元）找出公式中所有命题变元P1 , P2 ,Pn（2）按从小到大的顺序列出对命题变元）按从小到大的顺序列出对命题变元P1 , P2 ,Pn ,的全部的全部2n组赋值。组赋值。（3）对应各组赋值计算出公式）对应各组赋值计算出公式A的真值，并将其列的真值，并将其列在对应赋值的后面。在对

13、应赋值的后面。左孝凌离散数学13命题公式与翻译14真值表与等价18例例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 1左孝凌离散数学13命题公式与翻译14真值表与等价19例例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

14、 00 00 01 11 11 11 10 01 11 11 10 01 11 11 11 1左孝凌离散数学13命题公式与翻译14真值表与等价20例例2：构造公式：构造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R000001010011100101110111左孝凌离散数学13命题公式与翻译14真值表与等价21例例2：构造公式：构造公式 (P Q) R的的 真值表。真值表。PQRPQ(P Q) R0001000111010100111110000101001101011111左孝凌离散数学13命题公式与翻译14真值表与等价22 练习练习1：构造公式：构造公式 (PQ)(

15、Q P）真值表。真值表。PQ P QP Q Q P(P Q)( Q P)00011011左孝凌离散数学13命题公式与翻译14真值表与等价23 练习练习1：构造公式：构造公式 (PQ)( Q P）真值表。真值表。PQ P QP Q Q P(P Q)( Q P)0011111011011110010011100111左孝凌离散数学13命题公式与翻译14真值表与等价24PQ (P Q) (P Q) (P Q) Q00011011练习练习2：构造公式：构造公式 (P Q） Q 真值表。真值表。左孝凌离散数学13命题公式与翻译14真值表与等价25PQ (P Q) (P Q) (P Q) Q0010001

16、1001001011100练习练习2：构造公式：构造公式 (P Q） Q 真值表。真值表。左孝凌离散数学13命题公式与翻译14真值表与等价永真公式永真公式 永假公式：永假公式： 无论对其分量作怎样的真值指派，其真值永为无论对其分量作怎样的真值指派，其真值永为T，称为永真公式，记为称为永真公式，记为T 。如例如例1 无论对其分量作怎样的真值指派，其真值永为无论对其分量作怎样的真值指派，其真值永为F，称为永假公式，记为称为永假公式，记为F 。如例如例2 左孝凌离散数学13命题公式与翻译14真值表与等价 从真值表中可以看到，从真值表中可以看到，有些命题公式有些命题公式在分量的不同指派在分量的不同指派

17、下，其对应的真值与下，其对应的真值与另一命题公式完全相同另一命题公式完全相同，如，如PQ与与PQ的对应真值相同，如表的对应真值相同，如表1-4.5所示。所示。 PQPQPQTT T TTF F FFT T TFF T T表1-4.5我们说我们说PQ和和PQ是等价的，这是等价的，这在以后的推理中特在以后的推理中特别有用。别有用。1.4.2 等价公式等价公式左孝凌离散数学13命题公式与翻译14真值表与等价 同理(PQ)(PQ)与P Q对应的真值相同，如表1-4.6所示。 表1-4.6 P Q PQ (PQ)(PQ)TT T TTF F FFT F FFF T T1.4.2 等价公式等价公式左孝凌离

18、散数学13命题公式与翻译14真值表与等价29定义定义1.4.3: 给定两个命题公式给定两个命题公式A和和B,设设P1 , P2 ,Pn为出现为出现于于A和和B中的所有原子变元中的所有原子变元,若给若给P1 , P2 ,Pn任一组任一组真值指派真值指派, A和和B的真值都相同的真值都相同,则则称称A和和B是等价是等价. 记作记作A B。1.4.2 等价公式等价公式左孝凌离散数学13命题公式与翻译14真值表与等价30 1. 真值表法真值表法 2. 等值演算法等值演算法v1. 真值表法真值表法 例例1. (P1. (P Q) Q) (P(P Q) Q) 见真值表例题见真值表例题1.1. 例例2. 2

19、. 证明证明: 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证明公式等价的方法：证明公式等价的方法：左孝凌离散数学13命题公式与翻译14真值表与等价31 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)

20、(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)左孝凌离散数学13命题公式与翻译14真值表与等价32 2. 等值演算法等值演算法(Equivalent Caculation)（利用（利用P15表表1-4.8)重要的等价式重要的等价式(补充补充): 11. 蕴涵等值式蕴涵等值式: : P PQ Q PP Q Q Q Q PP Q Q

21、 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 左孝凌离散数学13命题公式与翻译14真值表与等价对合律P P1幂等律PP P，PP P2结合律(PQ）R P（QR）(PQ）R P（QR）3交换律PQ QPPQ QP4分配律P（QR） （PQ）（PR）P

22、（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左孝凌离散数学13命题公式与翻译14真值表与等价例题6 验证吸收律 P（PQ） P P（PQ） P证明 列出真值表 表1-4.9PQPQ P（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）左孝凌离散数学1

23、3命题公式与翻译14真值表与等价35 等值演算中使用的一条重要规则：等值演算中使用的一条重要规则：置换规则。置换规则。定义定义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等价，即等

24、价，即A AB B。定义定义1.4.51.4.5 等值演算：等值演算：根据已知的等价公式根据已知的等价公式, ,推演出另外一些等推演出另外一些等价公式的过程称为价公式的过程称为等值演算等值演算. .左孝凌离散数学13命题公式与翻译14真值表与等价36例例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：证

25、明（：证明（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) 左孝凌离散数学13命题公式与翻译14真值表与等价37例例4：验证：验证P(QR) (P Q) R证证: 右右 (P Q) R（蕴含等值）（蕴含等值） P Q R（德摩根律）（德摩根律） P (

26、Q R) （结合律）（结合律） P (Q R) （蕴含等值）（蕴含等值） P (Q R) （蕴含等值）（蕴含等值） 左孝凌离散数学13命题公式与翻译14真值表与等价例例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

27、Q) (P Q) (P Q) 左孝凌离散数学13命题公式与翻译14真值表与等价39v等值演算等值演算在计算机硬件设计中在计算机硬件设计中,在开关理论和电子元在开关理论和电子元器件中都占有重要地位器件中都占有重要地位.v小结小结: 本节介绍了真值表、公式等价、等值演算和等本节介绍了真值表、公式等价、等值演算和等价置换等概念，给出了常用的重要等价公式（价置换等概念，给出了常用的重要等价公式（24个）。个）。重点掌握用真值表法验证公式的等价性和等值演算法重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价。推演两个公式等价。作业：作业：P19 （7）.预习预习: 1.5, 1.6思考题：思考题：