数字电路课件.ppt

文档介绍：1-7对偶与范式目的要求:、关系及性质。(析取)范式、主合取(析取)范式的定义。(析取)范式、主合取(主析取)范式的方法与步骤。重点会求命题公式的主合取(析取)范式1---、对偶式在前面介绍的命题定律中,大多都是成对出现的,这些成对出现的定律是对偶性质的体现。利用对偶式的命题定律,可以扩大等价式的个数。-,把联结词换成,将换成,若有特殊变元F和T亦互相取代,所得公式称为A的对偶式,记为A*。显然,A称为A*的对偶式一、对偶式例1:写出下列命题公式的对偶式1)(P∨Q)∧R2)(P∧Q)∨T3)ר(P∨Q)∧(P∨ר(Q∧רS)(P∧Q)∨R(P∨Q)∧Fר(P∧Q)∨(P∧ר(Q∨רS)一、-(对偶定理):设A和A*是对偶式,P1,P2,…,Pn是出现在A和A*中的原子变元,则 רA(P1,P2,…,Pn)A*(רP1,רP2,…,רPn) A(רP1,רP2,…,רPn)רA*(P1,P2,…,Pn).证明:-,P2,…,Pn是出现在A和B中的所有原子变元,如果AB,则A*B*二、公式的标准型--范式同一命题公式可以有各种相互等价的表达形式,为了把命题公式规范化,需要讨论命题公式的标准型。例如:PQ  (P→Q)∧(Q→P)  (P∧Q)∨(P∧Q)简单合取式:除联结词∧外不出现其他任何二元联结词的命题公式,其中每个命题变元或其否定称为合取项。如P,רQ,P∧Q,רP∧Q∧R简单析取式:除联结词∨外不出现其他任何二元联结词的命题公式,其中每个命题变元或其否定称为析取项。如P,רQ,P∨Q,רP∨Q∨רR注意:一个命题变元或其否定既可以是简单合取式,也可以是简单析取式。-,当且仅当A表示为简单析取式的合取,即AA1∧A2∧…∧An,(n≥1)其中A1,A2,…,An为简单析取式。例如:(רP∨Q∨R)∧(רP∨Q)∧רQ为合取范式。若干个简单析取式的合取构成合取范式。定义1-,当且仅当A表示为简单合取式的析取,即AA1∨A2∨…∨An,(n≥1)其中A1,A2,…,An为简单合取式。例如:רP∨(P∧Q)∨(P∧רQ∧R)为析取范式。若干个简单合取式的析取构成析取范式。:任何一个命题公式,求它的合取范式或析取范式,可以通过下面三个步骤进行:(1)使用命题定律,消去公式中除∧、∨及ר外的所有出现的、等联结词。(2)利用德•摩根律将否定符号ר直接移到各个命题变元之前。(3)利用分配律、结合律将公式划为合取范式或析取范式。