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