离散数学(第2讲)

1、冯伟森Email138081922758/6/2022离散数学计算机学院8/6/20221计算机科学与工程学院主要内容 1、命题合适公式与真值表 1）命题常项与命题变项 2）命题公式与赋值 3）永真式 4）矛盾式 2、命题公式的等价 1）基本等价式 2）等价式的判断 8/6/20222计算机科学与工程学院1.2 命题合适公式与真值表一个特定的命题是一个常值命题，它不是具有值“T”(“1”)，就是具有值“F”(“0”)。而一个任意的没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的值域是集合T，F(或0，1)。当原子

2、命题是命题变元时，其复合命题也即为命题变元的“函数”，且该“函数”的值仍为“真”或“假”值，这样的函数可形象地称为“真值函数”,或称为命题公式,此命题公式没有确切真值。8/6/20223计算机科学与工程学院命题公式定义1-2.1(命题公式)命题变元（原子命题变元）本身是一个公式；如P，Q是公式，则(P)、(PQ)、(PQ)、(PQ)、(PQ)也是公式；命题公式仅由有限步使用规则1-2后产生的结果。该公式常用符号G、H、等表示。为书写和输入计算机及计算方便起见，约定：（1）最外层括号可以省略（2）按联结词的优先级的括号可以省略8/6/20224计算机科学与工程学院 符号串：(P(QR)(Q(SR

3、)； (PQ)； (P(PQ)； (PQ)(RQ)(PR)。 等都是命题公式。 符号串：(PQ)Q)；(PQ；(PQ(R； PQ。等都不是合法的命题公式。例2.1定义1-2.2：如公式A是公式B的一部分，则称A是B的子公式。8/6/20225计算机科学与工程学院公式的解释与真值表定义1-2.3 设P1、P2、Pn是出现在公式G中的所有命题变元，指定P1、P2、Pn的一组真值（如1，0，1，0，1），则这组真值称为G的一个解释,常记为。一般来说，若有个命题变元，则应有2n个不同的解释。 定义1-2.4 如果公式G在解释下是真的，则称满足G；如果G在解释下是假的，则称弄假G。将公式G在其所有可能解

4、释下的真值情况列成的表，称为G的真值表。n个8/6/20226计算机科学与工程学院构造公式G1：PQ的真值表如下：PQPPQ0011011110001101例2.2PQ和PQ的真值表完全一致8/6/20227计算机科学与工程学院构造公式G2(PQ) ()的真值表PQPQ(PQ) ()0010 00110 01001 01110 0例2.3该公式对所有可能的解释取值均为08/6/20228计算机科学与工程学院PQPQ(PQ)0011011110011111例2.4构造公式G3(PQ)的真值表该公式对所有可能的解释取值均为18/6/20229计算机科学与工程学院从这三个真值表可以看到一个非常有趣的

5、事实：公式G3对所有可能的解释具有“真”值公式G2对所有可能的解释均具有“假”值公式G1则具有“真”和“假”值结论8/6/202210计算机科学与工程学院定义1-2.5公式G3称为永真公式(重言式)，如果在它的所有解释之下都为“真”。公式G2称为永假公式(矛盾式，不可满足公式),如果在它的所有解释之下都为“假”。公式G1称为可满足的，如果它不是永假的（即存在解释使公式取值1）。8/6/202211计算机科学与工程学院永真式G的否定G是矛盾式；矛盾式G的否定G是永真式。永真式一定是可满足式,可满足式不一定是永真式。两个永真式的合取、析取、条件、双条件均为永真式。 这样由简单的重言式，可以推出无数

6、个复杂的重言式。判定给定公式是否为永真式，永假式或可满足式的问题，称为给定公式的判定问题。 在逻辑研究和计算机推理以及决策判断时，人们对于所研究的命题，最关心的莫过于“真”、“假”问题，所以永真公式在数理逻辑的研究中占有特殊且重要的地位。 永真式的特点8/6/202212计算机科学与工程学院 命题逻辑的基本任务之一，就是找出那些属于永真式的命题公式。（1）真值表法（简单、直观）（2）置换（代换，代入）法则 如果公式A中的一些变元，用一些公式代入，而且每次出现同一变元时，总用同一公式代入，就可从公式A得到公式B，则称公式B为公式A的置换（代入）实例（例式）。置换定理：永真式的任何置换（代入）实例

7、仍是一个永真式。永真式的判断8/6/202213计算机科学与工程学院 例如： PQ P（永真式） 对上式中的P，用（RS）代入， 对Q，用（MN）代入后得到： （RS）（MN）（RS） 该公式也是一个永真式（3）公式推演法（等价变换、替换（取代）规（范）则） 具体方法在下节中介绍8/6/202214计算机科学与工程学院定义1-3.1 设G、H是公式，如果在任意解释下，G与H的真值相同，则称公式G、H是等价的 ，记作GH。定理1-3.2公式G、H等价的充分必要条件是公式 GH是永真公式。 此定理是从另一角度来看待等价性等价式的性质:1）自反性：A A2）对称性：若 A B，则 B A3）可传递性

8、:若 A B，B C，则A C1.3 命题公式的等价8/6/202215计算机科学与工程学院 首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。 而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH 的结果不是命题公式。 其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。 “” 与“”的区别8/6/202216计算机科学与工程学院基本等价式命题定律 Equivalence 设G，H，S是任何的公式，则：1:(G

9、H)(GH)(HG)(等价)2：(GH) (GH) (蕴涵)3：GG G (幂等律)4：GG G5：GH HG (交换律)6：GH HG7：G(HS) (GH)S (结合律)8: G(HS) (GH)S9：G(GH) G (吸收律) 10：G(GH) G 8/6/202217计算机科学与工程学院11：G(HS) (GH)(GS) (分配律)12：G(HS) (GH)(GS)13：GF G(同一律)14：GT G 15：GT T(零律)16：GF F 17：GG T (矛盾律)18：GG F19： (G) G (双重否定律)20：（GH)S G（HS） （输出律）21：（GH）(GH)(GH)

10、(排中律)22：PQ QP （逆反律）23： (GH) GH (De Morgan定律)24： (GH) GH。基本等价式（续）8/6/202218计算机科学与工程学院替换定理定理1-3.1设G1是G的子公式(即 G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1 H1，则G H。 替换定理是经常使用的重要定理。 8/6/202219计算机科学与工程学院等价式的判定1.真值表法2.公式推演（等价变换）例3.1：试证 PQ QP 证：PQ PQ 蕴涵 E2 PQ 双重否定 E19 QP 交换律 E5 QP E28/6/202220计算机科学与

11、工程学院试用较少的开关设计一个与下图有相同功能的电路。例3.28/6/202221计算机科学与工程学院解：可将上图所示之开关电路用下述命题公式表示：(PQS)(PRS)利用基本等价公式，将上述公式转化为： (PQS)(PRS) (PS)Q)(PS)R)(结合律) (PS)(QR)（分配律）所以其开关设计图可简化为：例3.2（续）8/6/202222计算机科学与工程学院试将下图所示之逻辑电路简化。PQR解: 可将上述电路写成如下命题公式： (PQ)(PR)(QR)利用基本等价公式转化为： (PQ)(PR)(QR)(P(QR)(QR)（分配律）P(QR) (幂等律)例3.3并联符号ANDANDAN

12、DOROR与门或门8/6/202223计算机科学与工程学院所以该电路图可简化为：PQR例3.3（续）8/6/202224计算机科学与工程学院证明P(PQ)Q) 是永真公式。证：P(PQ)Q) P(PQ)Q (De Morgan定律) (PQ)(PQ) (交换律) (结合律) T （矛盾律）例3.48/6/202225计算机科学与工程学院证明P(QR) (PQ)R证：P(QR) P(QR)（蕴涵） P(QR) （蕴涵） (PQ)R (结合律) (PQ)R （蕴涵） (PQ)R （蕴涵）例3.58/6/202226计算机科学与工程学院例3.6试证明(P(QR)(PQR) P证明： (P(QR)(P

13、QR) P(QR)(QR)（分配律） P(QR)(QR) (De Morgan定律) PT（矛盾律）P(同一律)8/6/202227计算机科学与工程学院例3.7试证明(P(QR)(QR)(PR)R证明：(P(QR)(QR)(PR) (PQ)R）(QP)R)（结合律、分配律）(PQ)R)(QP)R) (De Morgan定律)(PQ)(QP)）R（分配律）TR(交换律、矛盾律）R （同一律）8/6/202228计算机科学与工程学院 将下面一段程序简化If AB then If BC then X Else Y EndElse If AC then Y Else X EndEnd例3.8 执行程序

14、段X 的条件为(AB)（B C）（AB） （AC） （ABC）If ABC then Y Else X End执行程序段Y的条件为(AB)（B C）（AB） （AC） ABC8/6/202229计算机科学与工程学院对偶式E3E18，E23E24都是成对出现的，它是逻辑系统对偶性的反映，即对偶式。利用对偶式可以扩大等价式的个数，也可减少证明的次数。定义：在给定的仅使用联结词、的命题公式A中，若把和，F和T互换而得的公式A*，则称A*为A的对偶（公）式。 如公式（PQ）R的对偶式为（PQ）R P（QR）的对偶式为P（QR）8/6/202230计算机科学与工程学院问题：如果两个公式等价，那么它们的对

15、偶式是否也是等价的？引理：设P1,P2,Pn是公式A和A*中的所有命题变元，则 A（P1,P2,Pn）A*（P1,P2,Pn） A(P1,P2,Pn) A*(P1,P2,Pn)证：由 De Morgan定律可知 （PQ） PQ， （PQ） P Q T F， F T 对公式的否定可以直接作用到原子本身，并且把公式中的变成，把变成，即得 A（P1,P2,Pn）A*（P1,P2,Pn）同理可得 A(P1,P2,Pn) A*(P1,P2,Pn)8/6/202231计算机科学与工程学院对偶原理设A和B是两个命题公式，若A B， 则 A* B*例3.9 证明（a）(PQ)(P(PQ) PQ （b）(PQ) (P(PQ) PQ证明:（a） (PQ)(P (PQ) (PQ)(P(PQ) （蕴涵） (PQ)PQ (幂等律) (PP)(QP)Q (结合律) （分配律） PQQ （矛盾律）(同一律) PQ (幂等律) （b） 该式正好是（b）左端的对偶式 由（a）及对偶原理得证该式正好是右端的对偶