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

1、2 命题公式与真值表命题公式与真值表命题公式命题公式 命题常元：表示确定的命题命题常元：表示确定的命题T，F。命题变元：没有指定真值的命题。常用大写英文字母命题变元：没有指定真值的命题。常用大写英文字母表示。表示。命题公式：由命题变元、常元、联结词、括号，以规定命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。的格式联结起来的字符串。命题公式可按下述法则来生成：命题公式可按下述法则来生成：）孤立的命题变元孤立的命题变元是一个命题公式。是一个命题公式。）若是命题公式，）若是命题公式，也为命题公式。也为命题公式。）若、是命题公式，则（）若、是命题公式，则（）、（）、（）、）、

2、（）、（）、（）均为命题公式。）均为命题公式。）当且仅当有限次使用）当且仅当有限次使用1),2),3)所生成的公式才是命题公式。所生成的公式才是命题公式。例如：例如：(P Q)(P Q)，P P(Q R)，(PQ)R，P都是都是命题公式。命题公式。(P)，(P)都不是命题公式。都不是命题公式。2命题公式的真值表命题公式的真值表 命题变元用特定的值来取代，这一过程称为对该命题命题变元用特定的值来取代，这一过程称为对该命题变元进行变元进行指派或赋值指派或赋值。定义定义：命题公式：命题公式A在其所有可能的赋值下取得的值在其所有可能的赋值下取得的值列成的表称为列成的表称为A的真值表。的真值表。构造真值

3、表的步骤如下：构造真值表的步骤如下：1)找出给定命题公式中所有的命题变元，列出所有可能的找出给定命题公式中所有的命题变元，列出所有可能的赋值。赋值。2)按照命题公式的运算次序列出命题公式的各层次。按照命题公式的运算次序列出命题公式的各层次。3)对应每个赋值，计算命题公式各层次的值，直到最后计对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。算出整个命题公式的值。P QP Q（）（）F FFFTF TTFTT FTTFT TTTF例构造命题公式例构造命题公式（）的真值表。）的真值表。例写出命题公式例写出命题公式（）的真值表）的真值表 PQR（)FFF F FFFT F FFT

4、F F FFTT T TTFF F TTFT F TTTF F TTTT T T 由上二例可见，个命题由上二例可见，个命题变元有组真值指派；变元有组真值指派；个命题变元有个命题变元有23 组组真值指派，个命题变元真值指派，个命题变元则有则有 2n个真值指派。个真值指派。步骤如下：步骤如下：(1)(1)找出各简单命题，分别符号化。找出各简单命题，分别符号化。(2)(2)选择适当的联结词，把简单命题逐个联结起来。选择适当的联结词，把简单命题逐个联结起来。命题公式的翻译命题公式的翻译例例.将下列命题符号化将下列命题符号化.(1)李明是计算机系的学生，他住在李明是计算机系的学生，他住在312室或室或3

5、13室。室。解：首先用字母表示简单命题。解：首先用字母表示简单命题。P：李明是计算机系的学生。：李明是计算机系的学生。Q：李明住在：李明住在312室。室。R：李明住在：李明住在313室。室。该命题符号化为：该命题符号化为：P（QR）(2)张三和李四是朋友。张三和李四是朋友。这是一个简单句，则该命题符号化为：这是一个简单句，则该命题符号化为：P (3)虽然交通堵塞，但是老王还是准时到达了车站。虽然交通堵塞，但是老王还是准时到达了车站。首先用字母表示简单命题。首先用字母表示简单命题。P：交通堵塞。：交通堵塞。Q：老王准时到达了车站。：老王准时到达了车站。该命题符号化为：该命题符号化为：P Q(4)

6、只有一个角是直角的三角形才是直角三角形。只有一个角是直角的三角形才是直角三角形。首先用字母表示简单命题。首先用字母表示简单命题。P：三角形：三角形 的一个角是直角。的一个角是直角。Q：三角形是直角三角形。：三角形是直角三角形。该命题符号化为：该命题符号化为：Q P 或者：或者：P Q(5)(5)仅当天不下雨我才去镇上。仅当天不下雨我才去镇上。该句可理解为：如果我去镇上，一定是天没下雨。该句可理解为：如果我去镇上，一定是天没下雨。首先用字母表示简单命题。首先用字母表示简单命题。P:P:天不下雨天不下雨Q:Q:我去镇上我去镇上该命题符号化为：该命题符号化为：Q Q P P首先用字母表示简单命题。首

7、先用字母表示简单命题。P:P:你努力你努力 Q:Q:你失败你失败该句可理解为：如果你没有努力，则必然失败。该句可理解为：如果你没有努力，则必然失败。该命题符号化为：该命题符号化为：P PQ Q该句也可理解为：如果你没有失败，则你一定努力了。该句也可理解为：如果你没有失败，则你一定努力了。该命题符号化为：该命题符号化为：Q Q P P(6)(6)除非你努力，否则你将失败。除非你努力，否则你将失败。(7)(7)老王或小李中有一个去上海出差。老王或小李中有一个去上海出差。首先用字母表示简单命题。首先用字母表示简单命题。P P：老王去上海出差。：老王去上海出差。Q Q：小李去上海出差。：小李去上海出差

8、。该命题符号化为：该命题符号化为：P P Q Q 也可符号化为：（也可符号化为：（P PQ Q）（P P Q Q）(8)(8)把下列语句的确切含义表达出来把下列语句的确切含义表达出来n玫瑰香玫瑰香,牡丹香牡丹香,玫瑰与牡丹都香玫瑰与牡丹都香,没有不香的玫瑰没有不香的玫瑰,也也没有不香的牡丹。没有不香的牡丹。P P：玫瑰香：玫瑰香,Q,Q：牡丹香：牡丹香 P P Q Q(P P Q Q)(P)P)(Q Q)等价于：等价于：P P Q Q玫瑰香，牡丹也香。玫瑰香，牡丹也香。(9)翻译下面的逻辑推理。翻译下面的逻辑推理。2是素数或合数。若是素数或合数。若2是素数，则是素数，则 是无理数。则是无理数。

9、则 是无理是无理数，则数，则4不是素数。所以，如果不是素数。所以，如果4是素数，则是素数，则2是合数。是合数。翻译：翻译：P：2是素数是素数 Q:2是合数是合数 R:是无理数是无理数 S:4是素数是素数 前提：前提：PQ,P R,R S 结论：结论：S Q(10)(10)翻译下面的逻辑推理。翻译下面的逻辑推理。如果今天是周六，我们就去颐和园或圆明园玩。如果颐和如果今天是周六，我们就去颐和园或圆明园玩。如果颐和园游人太多，就不去颐和园。今天是周六，并且颐和园游园游人太多，就不去颐和园。今天是周六，并且颐和园游人太多。所以我们去圆明园或动物园玩。人太多。所以我们去圆明园或动物园玩。翻译：翻译：P

10、P：今天是周六：今天是周六 Q:Q:我们到颐和园玩我们到颐和园玩 R:R:我们到圆明园玩我们到圆明园玩 S:S:颐和园游人太多颐和园游人太多 T:T:我们到动物园玩我们到动物园玩 前提：前提：P P (QR),S QR),S Q,Q,P P，S S 结论：结论：RT RT(11)(11)设设P:P:明天下雨，明天下雨，Q:Q:明天刮风，明天刮风，R:R:我去学校，则下列命我去学校，则下列命题公式各表示什么意思。题公式各表示什么意思。1 1）(P P Q)Q)R R如果明天不是风雨交加，则我去学校。如果明天不是风雨交加，则我去学校。2 2）(P PQ)Q)R R如果明天不下雨也不刮风，我才去学校。如果明天不下雨也不刮风，我才去学校。3 3）P Q P Q R R若明天下雨或刮风，则我不去学校。若明天下雨或刮风，则我不去学校。