离散数学课件真值表与等价公式

1、1-3命题公式与翻译命题公式与翻译1-3.1 命题公式命题公式 p，p q，(p q) (pq)都是复合命都是复合命题。若题。若p和和q是命题变元，则上述各式均是命题变元，则上述各式均称作命题公式。称作命题公式。 p和和q称为命题公式的分称为命题公式的分量。量。命题公式是没有确定的真值的，仅当命题公式是没有确定的真值的，仅当在一个公式中命题变元用确定的命题代入在一个公式中命题变元用确定的命题代入时，才能得到一个命题。时，才能得到一个命题。1-3.1 命题公式命题公式定义定义1-3.1 命题演算的合式公式（命题演算的合式公式（wff）(well formed formula)(1)单个命题变元本

2、身是一个合式公式。单个命题变元本身是一个合式公式。(2)如果如果a是合式公式，那么是合式公式，那么 a是合式公式。是合式公式。(3)如果如果a和和b是合式公式，那么是合式公式，那么(a b), (a b), (ab), (a b)是合式公式。是合式公式。(4)当且仅当能够有限次地应用当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命题变元、联结词和括号的符所得到的包含命题变元、联结词和括号的符号串是合式公式。号串是合式公式。1-3.1 命题公式命题公式注：这是一个递归方式的定义（递归定义）注：这是一个递归方式的定义（递归定义） （1）是递归定义的基础）是递归定义的基础 （2）、（）、

3、（3）是归纳）是归纳 （4）是递归的界限）是递归的界限例：例： (p q)就不是合式公式就不是合式公式联结词的运算次序：联结词的运算次序：(1)使用括号使用括号(2) 规定运算符运算优先次序：规定运算符运算优先次序： , , , ,1-3.2 翻译翻译例例1. 除非你努力，否则你将失败。除非你努力，否则你将失败。解：设解：设p：你努力。：你努力。 q：你将失败。：你将失败。原命题可以符号化为：原命题可以符号化为： p q例例2. 除非除非(仅当仅当)我有时间，我才去看电影。我有时间，我才去看电影。解：设解：设p：我有时间。：我有时间。 q：我去看电影。：我去看电影。原命题可以符号化为：原命题可

4、以符号化为： p q 或化为：或化为：qp例例3. 如果你和他都不固执己见的话，那么不愉快如果你和他都不固执己见的话，那么不愉快的事也不会发生了。的事也不会发生了。解：设解：设p：你固执己见。：你固执己见。 q：他固执己见。：他固执己见。 r：不愉快的事也不会发生了：不愉快的事也不会发生了原命题可以符号化为：（原命题可以符号化为：（ pq）r例例4. 如果你和他不都是固执己见的话，那么不愉如果你和他不都是固执己见的话，那么不愉快的事也不会发生了。快的事也不会发生了。解：设解：设p：你固执己见。：你固执己见。 q：他固执己见。：他固执己见。 r：不愉快的事也不会发生了：不愉快的事也不会发生了原命

5、题可以符号化为：原命题可以符号化为： （p q）r作业(1-3)p12. (5)1-4真值表与等价公式真值表与等价公式定义定义1-4.1真值表：真值表： 对于给定的命题公式，对其分量进对于给定的命题公式，对其分量进行所有可能的真值指派得到该公式的相行所有可能的真值指派得到该公式的相应的真值取值情况，将其汇列成表，称应的真值取值情况，将其汇列成表，称做该命题公式的真值表。做该命题公式的真值表。例：给出例：给出 (pq)的的真值表。真值表。pqpq(pq)tttftfftfttffftf1-4 真值表与等价公式真值表与等价公式在真值表中，命题公式真值的取值数目，在真值表中，命题公式真值的取值数目，

6、决定于分量的个数。决定于分量的个数。n个命题变元组成的个命题变元组成的命题公式有命题公式有2n种真值情况。种真值情况。定义定义1-4.2 永真公式永真公式 永假公式：永假公式： 无论对其分量作怎样的真值指派，其无论对其分量作怎样的真值指派，其真值永为真值永为t，称为永真公式，记为，称为永真公式，记为t 。 无论对其分量作怎样的真值指派，其无论对其分量作怎样的真值指派，其真值永为真值永为f，称为永假公式，记为，称为永假公式，记为f 。 1-4 真值表与等价公式真值表与等价公式定义定义1-4.3 等价等价(equivalent)公式：公式： 设设a和和b是两个命题公式，是两个命题公式，p1，p2，

7、pn是出现在是出现在a和和b中的所有原子变元，若对中的所有原子变元，若对p1，p2，pn的任何真值指派，的任何真值指派， a和和b真值相真值相同，称同，称a和和b等价或逻辑相等。记作等价或逻辑相等。记作ab。 要证明两个命题公式等价，可用：要证明两个命题公式等价，可用：（1）真值表法）真值表法（2）等价命题定律。）等价命题定律。1-4 真值表与等价公式真值表与等价公式例例: pq p q p q (pq) (qp) p q (p q) ( pq)p15 表表1-4.8 命题定律命题定律1-4 真值表与等价公式真值表与等价公式定义定义1-4.4 子公式子公式设设a是一个命题公式，是一个命题公式，

8、x是是a的一部分且的一部分且x本身也是公本身也是公式，则称式，则称x为公式为公式a的子公式。的子公式。定理定理1-4.1（等价置换）（等价置换）设设a是一个命题公式，是一个命题公式，x是是a的一个子公式，若公式的一个子公式，若公式y与与x等价，用等价，用y置换置换a中的中的x得到一个公式得到一个公式b，则，则 a b。可用真值表法得证可用真值表法得证1-4 真值表与等价公式例：例：证明证明 q q( (p p ( (p p q) q) q qp p证明：应用吸收律证明：应用吸收律 p p ( (p p q) q) p p 左边左边 q qp p 得证！得证！1-4 真值表与等价公式p19 (7) a) p19 (7) a) 证明证明 a a( (b ba) a) a a(a(a b)b)证明证