离散数学课件第一章(第2讲).pptVIP

§2命题公式与真值表１．命题公式命题常元：表示确定的命题｛T，F｝。命题变元：没有指定真值的命题。常用大写英文字母Ａ…Ｚ表示。命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。命题公式可按下述法则来生成：１）孤立的命题变元是一个命题公式。２）若Ａ是命题公式，?Ａ也为命题公式。３）若Ａ、Ｂ是命题公式，则（ＡΛＢ）、（Ａ∨Ｂ）、（Ａ→Ｂ）、（Ａ?Ｂ）均为命题公式。４）当且仅当有限次使用1),2),3)所生成的公式才是命题公式。例如：?(P∨Q)，P→(Q→R)，(PΛQ)?R，P都是命题公式。(P→)，(P∨?)都不是命题公式。2．命题公式的真值表命题变元用特定的值来取代，这一过程称为对该命题变元进行指派或赋值。《定义》：命题公式A在其所有可能的赋值下取得的值列成的表称为A的真值表。构造真值表的步骤如下：1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。2)按照命题公式的运算次序列出命题公式的各层次。3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。PQP∨Q（Ｐ∨Ｑ）ΛＰ?（（Ｐ∨Ｑ）ΛＰ）FFFFTFTTFTTFTTFTTTTF例１．构造命题公式?（（Ｐ∨Ｑ）ΛＰ）的真值表。例２．写出命题公式Ｐ∨（ＱΛＲ）的真值表PQRＱΛＲＰ∨（ＱΛＲ)FFFFFFFTFFFTFFFFTTTTTFFFTTFTFTTTFFTTTTTT由上二例可见，２个命题变元有４组真值指派；３个命题变元有23＝８组真值指派，ｎ个命题变元则有2n个真值指派。步骤如下：(1)找出各简单命题，分别符号化。(2)选择适当的联结词，把简单命题逐个联结起来。§３命题公式的翻译例.将下列命题符号化.(1)李明是计算机系的学生，他住在312室或313室。解：首先用字母表示简单命题。P：李明是计算机系的学生。Q：李明住在312室。R：李明住在313室。该命题符号化为：P?（Q▽R）(2)张三和李四是朋友。这是一个简单句，则该命题符号化为：P(3)虽然交通堵塞，但是老王还是准时到达了车站。首先用字母表示简单命题。P：交通堵塞。Q：老王准时到达了车站。该命题符号化为：P?Q(4)只有一个角是直角的三角形才是直角三角形。首先用字母表示简单命题。P：三角形的一个角是直角。Q：三角形是直角三角形。该命题符号化为：Q?P或者：?P??Q(5)仅当天不下雨我才去镇上。该句可理解为：如果我去镇上，一定是天没下雨。首先用字母表示简单命题。P:天不下雨Q:我去镇上该命题符号化为：Q?P首先用字母表示简单命题。P:你努力Q:你失败该句可理解为：如果你没有努力，则必然失败。该命题符号化为：?P?Q该句也可理解为：如果你没有失败，则你一定努力了。该命题符号化为：?Q?P(6)除非你努力，否则你将失败。(7)老王或小李中有一个去上海出差。首先用字母表示简单命题。P：老王去上海出差。Q：小李去上海出差。该命题符号化为：P▽Q也可符号化为：（P??Q）?（?P?Q）(8)把下列语句的确切含义表达出来玫瑰香,牡丹香,玫瑰与牡丹都香,没有不香的玫瑰,也没有不香的牡丹。P：玫瑰香,Q：牡丹香P?Q?(P?Q)??(?P)??(?Q)等价于：P?Q玫瑰香，牡丹也香。(9)翻译下面的逻辑推理。2是素数或合数。若2是素数，则是无理数。则是无理数，则4不是素数。所以，如果4是素数，则2是合数。翻译：P：2是素数Q:2是合数R:是无理数S:4是素数前提：P∨Q,P?R,R??S结论：S?Q(10)翻译下面的逻辑推理。如果今天是周六，我们就去颐和园或圆明园