离散数学课程基本内容.ppt

1、离散数学DISCRETE MATHEMATICS,教师:石兵Email:shibing_,二零一三,重点词 - 定义命题(简单命题复合命题)命题表示基本连接词重点掌握命题的翻译,上次课重点:,本次课重点,命题公式解释及真值表等价的定义证明推理的基础: 基本等价式,第二节 命题合适公式与真值表,一、命题合适公式定义1。原子命题标识符是合适公式2。如果P、Q都是合适公式，则 P、 Q、（P Q）、（P Q）、（P Q）、 （P Q）也都是合适公式。3。只有按照1 和 2 产生的公式是合适公式。,约定： 1）以后我们用WFF (well-formed formula)表示术语“合适公式”。 2）简称

2、合适公式为公式。 3）合适公式的外层括号可以去掉。例如 （ P Q） （ P Q） 可以写成 （P Q） （ P Q）。,二、子合适公式,定义： 设G是WFF，A是G的一部分，且A也是WFF，则称 A是G的子合适公式。简称A 是G的子公式。 例如：P、Q、（P Q）、（P Q）都是（P Q） （P Q）的子公式。,三、命题公式的解释,1。对公式G中的每个原子代以具体的命题称为 对G的解释。2。对原子代以真命题可以用对原子赋值 1来表 达，对原子代以假命题可以用对原子赋值 0 来表达。3。公式在每种解释下取得唯一的值。,例： 下面是对公式G=（R Q）（P Q） 的一个解释： P Q R 0 1

3、 0 在这个解释下，公式G的值是 (0 0） （0 1）=1。,四、公式的真值表,1。真值表：由公式的全部解释构成的表。 2。真值表类似于联结词功能表，公式的原子 列于最前几列，表中每行对应一种解释。 3。如果公式中有n个原子，则表中有 2 n 个不 同的解释行。,例： 构造公式G=（R Q） （P Q） 的真值表。 解：公式中含 3 个原子，故有 8 种可能的 解释，见下表。,P Q R | R Q P Q | G0 0 0 | 0 1 | 10 0 1 | 1 1 | 10 1 0 | 0 1 | 10 1 1 | 0 1 | 11 0 0 | 0 0 | 01 0 1 | 1 0 | 1

4、1 1 0 | 0 1 | 11 1 1 | 0 1 | 1,例：构造公式G1= P （P Q）和 G2= P (P Q)的真值表。解：下面把两个公式的真值表放在一起。P Q | P （P Q） | P （P Q） 0 0 | 1 | 00 1 | 1 | 01 0 | 1 | 01 1 | 1 | 0,五、公式的分类,1。永真式：在任何解释下都取真值 1 的公式。 也叫做重言式，如P （P Q）。永真式 通常用符号T表示。2。永假式：在任何解释下都取真值 0的公式。 也叫做矛盾式，如 P （P Q）。永假 式通常用符号F表示 。,3。可满足式：至少在一种解释下取真值 1 的公式。如 P Q等

5、。 显然，永真式是可满足公式，而矛盾 式是不可满足公式。 作业: 习题一 3,4(3) (7) 习题1. 2 1, 2(3)(7),第三节 命题公式的等价,一、定义：设A是 B两个WFF，如果在任何解 释下A和B都取相同的值，则说公式A和B 是等价的。1。A和 B等价记为 A B。2。定理1： A B当且仅当A B是永真式。,定理1：证明要点： 当A B时，任何解释下A 和 B同值，因此 A B 是永真式。反之， 当A B是永真式时，在任何解释下A和 B必须同值，因此 A B。,例： 验证 P Q P Q解：列出真值表如下：P Q | P Q |P Q 0 0 | 1 | 10 1 | 1 |

6、 11 0 | 0 | 01 1 | 1 | 1从值表可以看出，等价式成立。,例： 验证 （P Q） P Q解：列出真值表如下： P Q | （P Q） | P Q 0 0 | 1 | 10 1 | 0 | 01 0 | 0 | 01 1 | 0 | 0从真值表可以看出，等价式成立。,二、基本等价式,在教材中列出了常用的 14个等价式，可以利用真值表加以验证。它们表达了逻辑联结词满足的运算定律，具有普遍意义，必须记住。 1。 （ P） P （双重否定律） 2。P P P，P P P （幂等律） 3。P Q Q P，P Q Q P （交换律）,4。P （Q R） （PQ） R （ P Q R）

7、P （Q R） （P Q） R （ P Q R） （结合律）根据结合律，只含 或只含 的 公式，可以去掉括号。,5。 P （Q R） （P Q） （P R） P （Q R） （P Q） （P R） （分配律）6。 P （P R） P （吸收律） P （P R） P7。 （ P Q） P Q （德。摩根律） （P Q） P Q,8。P F P，P T P（同一律）9。P T T，P F F （零律）10。P P T，P P F（矛盾律）11。 P Q P Q (条件词转化)12。 P Q （P Q）（Q P） （P Q） ( P Q ） (双条件词转化),三、公式等价的性质,1。 A A （自反

8、性）2。如果A B，则 B A （对称性）3。如果A B， B C 则A C （传递性）4。设A是公式 X 的一个子公式，且A B。 又设用 B取代X中的子公式A后得到的新 公式为Y，则 X Y。,证明要点：因为A B，因而在任何解 释下，A和B取相同的值，因而X和 Y的 取值也都相同。 利用上面的性质和基本等价式，就可以 使用等价变换的方法去证明公式的等价 问题，下面是两个例子。,例1：证明 P Q Q P证明： P Q P Q （ Q） P Q P,煤是黑的(原命题) 如果是煤,则是黑的( P-Q)煤是不黑的(否命题) (P-Q)黑的是煤(逆命题) 如果是黑的,则是煤( Q-P)不黑不是煤

9、(逆否命题) 如果不黑,则不是煤( Q-P),例2：证明(P Q) ( P R) P (Q R) 证明： （P Q） （ P R ) ( P Q) ( P R) P ( Q R) P (Q R),四、对偶式,1。定义：设G是不含 和的WFF。把G 中联结词 换成 ，把 换成 、T换 成F、F换成T后得到的公式记为G*，称 之为G的对偶式。 例如：G= P ( Q R) ，则G 的对偶式 为 G* = P （Q R）。,求一般WFF的对偶式，必须用基本等价 式先化去 和 ，变成只含否定、析取、 合取之类联结词的等价公式后再作。 2。 定理：设A、B都是WFF。如果A B， 则A* B*。,例如：设A = P ( Q R) B=（ P Q） （ P R) 显然 ，A B。它们的对偶式分别是 A* = P ( Q R) B* =（ P Q） （ P R) 同样容易看出： A* B*。 作业: 习题一 5(3)(4), 6 习题1. 3 1(3)(4), 2,