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

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）当且仅当有限次地应用(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）,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,6,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,1.3.2 复合命题的符号化(翻译) 自然语言的语句用Wff 形式化：, 要准确确定原子命题，并将其形式化。, 要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。, 必要时可以进行改述，即改变原来的叙述方式， 但要保证表达意思一致。, 需要的括号不能省略，而可以省略的括号， 在需要提高公式可读性时亦可不省略。, 要注意语句的形式化未必是唯一的。,可以把本命题表达为：(P Q）。,解 P：上海到北京的14次列车是下午五点半开。 Q：上海到北京的14次列车是下午六点开。 在本例中，汉语的“或”是不可兼或，而逻辑联结词是“可兼或”，因此不能直接对两命题析取。构造如表1-3.1所示。,表1-3.1,例题2 上海到北京的14次列车是下午五点半或六点开。,解 这个命题的意义，亦可理解为： 如果你不努力则你将失败。 若设 P：你努力。 Q：你失败。 本例可表示为： PQ,例题5 除非你努力，否则你将失败。,解 这个命题的意义是： 可兼或 若设 P：张三可以做这事。 Q：李四可以做这事。 本例可表示为： P Q,例题6 张三或李四都可以做这件事。,10,第一章 命题逻辑（Propositional Logic）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: 你走。 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 后来主张：(（PQ）S)(SR),解答,练习2 （小李不在图书馆），（他要么找老师去了），（要么就是因为身体不适，回宿舍去了）。,命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。,解 设 P：小李在图书馆。Q：小李找老师。 R：小李身体不适。S：小李回宿舍。 则命题符号化为： （P）（(Q (RS)） （小李不是而是 ） （要么要么 排斥或）,14,第一章 命题逻辑（Propositional Logic）1.3命题公式与翻译,小结：本节介绍了命题公式的概念及复合命题的符号化.重点是理解命题公式的递归定义,掌握复合命题的符号化方法. 作业：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构造真值表的具体步骤为： （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) 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,第一章 命题逻辑（Propositional 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是等价的，这在以后的推理中特别有用。,第一章 命题逻辑（Propositional 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,第一章 命题逻辑（Propositional 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 Logic） 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.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） 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) （结合律） P (Q R) （蕴含等值） P (Q R) （蕴含等值）,例5：根据真值表方法“排斥或”可表示为 (PQ ) 证明：(PQ ) (PQ) (QP) 证: (PQ ) （PQ）（QP） （ PQ）（Q P） （PQ）