离散数学(第3讲)

冯伟森Email：[e-mail]2020年1月21日星期二2020/1/21计算机学院2定义1.12设G、H是公式，如果在任意解释Ｉ下，G与H的真值相同，则称公式G、H是等价的，记作GH。等价式的性质:1）自反性：AA2）对称性：若AB，则BA3）可传递性:若AB，BC，则AC1.3命题公式的等价2020/1/21计算机学院3基本等价式——命题定律1.Ｅ1:GH(G→H)∧(H→G)(等价律)2.Ｅ2：(G→H)(～G∨H)(蕴涵律)3.Ｅ3：G∨GG(幂等律)Ｅ4：G∧GG4.Ｅ5：G∨HH∨G(交换律)Ｅ6：G∧HH∧G5.Ｅ7：G∨(H∨S)(G∨H)∨S(结合律)Ｅ8:G∧(H∧S)(G∧H)∧S6.Ｅ9：G∨(G∧H)G(吸收律)Ｅ10：G∧(G∨H)G2020/1/21计算机学院47.Ｅ11：G∨(H∧S)(G∨H)∧(G∨S)Ｅ12：G∧(H∨S)(G∧H)∨(G∧S)8.Ｅ13：G∨FGＥ14：G∧TG9.Ｅ15：G∨TTＥ16：G∧FF10.Ｅ17：G∨～GTＥ18：G∧～GF基本等价式（续）(分配律）(矛盾律)(同一律)(零律)2020/1/21计算机学院511.Ｅ19：～(～G)G(双重否定律)12.Ｅ21：（GH）(～G∧H)∨(G∧～H)(排中律)13.Ｅ22：P→Q～Q→～P14.Ｅ23：～(G∨H)～G∧～HＥ24：～(G∧H)～G∨～H。基本等价式（续）（逆反律）(De.Morgan定律)2020/1/21计算机学院6替换定理定理1.2设G1是G的子公式(即G1是公式G的一部分)，H1是任意的命题公式，在G中凡出现G1处都以H1替换后得到新的命题公式H，若G1H1，则GH。替换定理是经常使用的重要定理。定理1.3公式G、H等价的充分必要条件是公式GH是永真公式。此定理是从另一角度来看待等价性2020/1/21计算机学院7首先，双条件词“”是一种逻辑联结词，公式GH是命题公式，其中“”是一种逻辑运算，GH的结果仍是一个命题公式。而逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，GH表示“命题公式G等价于命题公式H”，GH的结果不是命题公式。其次，如果要求用计算机来判断命题公式G、H是否逻辑等价，即GH那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。“”与“”的区别2020/1/21计算机学院8等价式的判定1.真值表法2.公式推演（等价变换）例1-3.1：试证P→Q～Q→～P证：P→Q～P∨Q蕴涵E2～P∨～～Q双重否定E19～～Q∨～P交换律E5～Q→～P蕴涵E22020/1/21计算机学院9试将下图所示之逻辑电路简化。PQR解:可将上述电路写成如下命题公式：((P∧Q)∨(P∧R))∧(Q∨R)利用基本等价公式转化为：((P∧Q)∨(P∧R))∧(Q∨R)(P∧(Q∨R))∧(Q∨R)（分配律）P∧(Q∨R)(幂等律)例1-3.2ANDANDANDOROR与门或门2020/1/21计算机学院10所以该电路图可简化为：PQR例1-3.2（续）2020/1/21计算机学院11P∨┐((P∨┐Q)∧Q)是永真公式。证：P∨┐((P∨┐Q)∧Q)P∨┐(P∨┐Q)∨┐Q(DeMorgan定律)(P∨┐Q)∨┐(P∨┐Q)(交换律)(结合律)T■（矛盾律）例1-3.32020/1/21计算机学院12对偶式E3～E18，E23～E24都是成对出现的，它是逻辑系统对偶性的反映，即对偶式。利用对偶式可以扩大等价式的个数，也可减少证明的次数。定义1.13：设A和A*是两个包含、∨、∧的命题公式。如果把A中的联结词∨换成∧，把∧换成∨，把Ｔ换成Ｆ，把Ｆ换成Ｔ后得到的正是A*，则称A*是A的对偶公式。如公式（P∨Q）∧R的对偶式为（P∧Q）∨R～P∨（Q∧R）的对偶式为～P∧（Q∨R）2020/1/21计算机学院13问题：如果两个公式等价，那么它们的对偶式是否也是等价的？定理1.4：设P1,P2,…Pn是公式A和A*中的所有命题变元，则～A（P1,P2,…Pn）A*（～P1,～P2,…,～Pn）证：∵由DeMorgan定律可知～（P∨Q）～P∧～Q，～（P∧Q）～P∨～Q～TF，～FT∴对公式的否定可以直接作用到原子本身，并且把公式中的∧变成∨，把∨变成∧，即得～A（P1,P2,…Pn）A*（～P1,～P2,…,～Pn）2020/1/21计算机学院14对偶原理（定理1.5）设A和B是两个命题公式，若AB，则A*B*例1-3.4证明（a）～(P∧Q)→(～P∨(～P∨Q)～P∨Q（b）(P∨Q)∧(～P∧(～P∧Q))～P∧Q证明:（a）～(P∧Q)→(～P∨(～P∨Q))(P∧Q)∨(～P∨(～P∨Q))（蕴涵）(P∧Q)∨～P∨Q(幂等律)((P∨～P)∧(Q∨～P))∨Q(结合律)（分配律）～P∨Q∨Q（矛盾律）(同一律)～P∨Q(幂等律)（b）该式正好是（b）左端的对偶式,由（a）及对偶原理得证该式正好是右端的对偶式2020/1/21计算机学院151.4联结词的完备集前面我们已经介绍了最常见的6种逻辑联结词。他们都和自然语言中使用的联结词紧密相关，易于理解。不同联结词产生的真值表是互不相同的，根据对含两个命题变元的公式的解释方式看，共有2*2=4种不同的解释，因而公式的真值表相应有2*2*2*2=16种可能结果。对其中每一种真值表都应该存在相应的联结词。下面从真值表取值情况的角度定义几个新的联结词。2020/1/21计算机学院16下面是含两个命题变元的所有公式的真值表所能取得的情况：PQ1234567891011121314151611100100PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000Q→PP→QPQPQPQ～Q～PP∧QＰ∨QTF2020/1/21计算机学院17PQP↑Q111001000111定义1.14设P和Q是命题公式，分别称P↑Q和P↓Q为“与非”和“或非”命题公式。其相应的真值表如下所示：2020/1/21计算机学院18PQP↓Q111001000001由真值表可以看出P↑Q～（P∧Q）,P↓Q～（P∨Q）2020/1/21计算机学院19根据联结词↑和↓的定义，不难证明下面的等价式。①P↑P～（P∧P）～P②(P↑Q)↑(P↑Q)～(P↑Q)P∧Q③(P↑P)↑(Q↑Q)～P↑～Q～（～P∧～Q）P∨Q④P↓P～（P∨P）～P⑤(P↓Q)↓(P↓Q)～(P↓Q)P∨Q⑥(P↓P)↓(Q↓Q)～P↓～Q～（～P∨～Q）P∧Q2020/1/21计算机学院20这些等价式告诉我们，↑可由∧和～表示出来，↓可由∨和～表示出来，反过来，↑和↓都可以单独表示出所有已知联结词，它们的这一性质使得在逻辑电路设计中只用一种门式电路元件就能实现任何电路功能，当然，元件的数量通常也显得更多。2020/1/21计算机学院21还有一个二元联结词“”,称为条件否定，可以用下面的真值表定义：PQPQ111001000100显然，PQ～(P→Q)2020/1/21计算机学院22至此我们定义了9个联结词，其中1个一元联结词，8个二元联结词。那么，还能不能定义出新的联结词呢？下面是含两个命题变元的所有公式的真值表所能取得的情况：2020/1/21计算机学院23PQ12345678910111213141516111001001011101110000001101101100110001010101101010101001001110010111000Q→PP→QPQPQPQ～Q～PP∧QＰ∨QTFP↑QP↓QQPPQ2020/1/21计算机学院24显然公式1是永真式，2代表矛盾式，3代表Ｐ∨Q，4代表Q→P,5代表P→Q，6代表P↑Q，7是P，8是Q，9代表PQ，10代表PQ，11代表～Q，12代表～P，13代表P↓Q，14代表QP,15代表PQ，16代表P∧Q，可见，已定义的9个联结词就是全部可以定义的联结词。2020/1/21计算机学院25定义1.15设S是由某些联结词构成的集合，如果每个逻辑联结词的功能都能够由S中的联结词实现，则称S是逻辑联结词的一个功能完备集；进一步，如果去掉S中的任何一个联结词后，至少有一个联结词的功能不能由S中剩余的联结词实现时，则称S是逻辑联结词的一个最小功能完备集。2020/1/21计算机学院26根据定义,我们知道{↑}、{↓}是最小的功能完备集，那么{～，∨，∧}是不是最小功能完备集？由于P∨Q～(～P∧～Q)，可见∨可由{～，∧}表达；同理,P∧Q～(～P∨～Q),因而∧可由{～，∨}表达，这说明{～，∨，∧}不是最小功能完备集，但是在实际应用中，普遍采用的功能完备集却是{～,∨,∧},这也是逻辑系统中最主要的3个常用联结词。2020/1/21计算机学院27基本要求1、深刻理解等价式的定义，知道公式之间的等价关系具有自反性、对称性、传递性；2、牢记基本等价式的名称及它们的内容；3、熟练地应用基本等价式及置换规则进行等价演算4、理解对偶原理及在等价演算中的应用5、理解逻辑联结词功能完备集和最小功能完备集的概念2020/1/21计算机学院28习题一5（1）（3）、6、8(1)（3）、9、10、