《求下列各公式的主析取范式和主合取范式》由会员分享，可在线阅读，更多相关《求下列各公式的主析取范式和主合取范式（11页珍藏版）》请在金锄头文库上搜索。
1、一、求下列各公式的主析取范式和主合取范式：1、PQPQ P Q(主合取范式)( P (Q Q) ( P P) Q)( P Q) ( P Q) ( P Q) (P Q)( P Q) ( P Q) (P Q) (主析取范式)2、(P Q) R(P Q) R ( P Q ) R( P R) (Q R) (析取范式)( P(QQ)R)(PP)Q R)( PQR)(PQR)(P Q R)( PQ R)( PQR)(PQR)(P Q R)(主析取范式)(P Q) R)(PQR)(P QR)(PQ R)(P Q R) ( P Q R)(原公式否定的主析取范式) (P Q) R (P Q R) (P Q R)
2、 ( P Q R) ( P Q R) ( P Q R) (主合取范式)3、P QP Q (主合取范式)( P ( Q Q) ( P P) Q)(PQ)( PQ)( PQ) (P Q)(PQ)( PQ)( PQ)(主析取范式)4、Q ( PR) Q ( PR)Q P R(主合取范式)(Q( P R)( P Q R) ( P Q R) ( P Q R) ( P Q R) (P Q R) ( P Q R) (P Q R)(原公式否定的主合取 范式)Q( PR)(P Q R)( P Q R)(P Q R)(P Q R)( P Q R)( P Q R) ( P Q R)(主析取范式)5、(P Q) (R
3、 P)(P Q) (R P) ( P Q) (R P)(P Q) (R P) (析取范式)(P Q (R R) (P ( Q Q) R)(P Q R) (PQ R) (P Q R) (P Q R)(P Q R) (PQ R) (P Q R)(主析取范式)( (P Q) (R P) (P Q R) ( P Q R) ( P Q R)( P Q R) ( P Q R) (原公式否定的主析取范式) (P Q) (R P) ( P Q R) (P Q R) (P Q R)(P Q R) (P Q R)(主合取范式)6、P (P Q)P (P Q) P ( P Q) (P P) QT( 主合取范式 )(
4、 P Q) ( P Q) (P Q) (P Q)(主析取范式)7、P QP Q(主析取范式) (P (Q Q) (P P) Q)(P Q) (P Q) (P Q) ( P Q)(P Q) (P Q) ( P Q)(主合取范式)8、(P R) (Q R) P(P R) (Q R) P(析取范式)(P (Q Q) R) (P P) Q R) ( P (Q Q) (R R)(P Q R) (P Q R) (P Q R) ( P Q R)( P Q R) ( P Q R) ( P Q R) ( P Q R)(P Q R) (P Q R) ( P Q R) ( P Q R)( P Q R) ( P Q
5、R) ( 主析取范式 )(P R) (Q R) P)(P Q R) ( P Q R)(原公式否定的主析取范式) (P R) (Q R) P ( P Q R) ( P Q R)(主合取范式)二、证明：1、PQ，Q R， R，S P= S证明：1、 （1）R前提（2）QR前提（3）Q（1），（2）（4）PQ前提（5）P（3），（4）（6）SP前提（7）S（5），（6）2、P(QR)，R(QS) = P (QS)1) P附加前提（2）Q附加前提（3）P (QR)前提（4）Q R（1），（3）（5）R（2），（4）（6）R (Q S)前提（7）Q S（5），（6）（8）S（2），（7）（9）Q SCP
6、，（2），（ 8）（10）P (Q S)CP ，（1），（ 9）3、PQ， P R, QS= R S证明（1）R附加前提（2）P R前提（3）P（1），（2）（4）P Q前提（5）Q（3），（4）（6）Q S前提（7）S（5），（6）（8）R SCP ，（ 1），（8）4、A (CB)，B A，D C = A D证明（1）A附加前提（8）A (C B)前提（9）CB（1），（2）（10）B A前提（11）B（1），（4）（12）C（3），（5）（13）D C前提（14）D（6），（7）（15）A DCP ，（1），（8）5、B D，(E F) D， E= B证明：（1）B附加前提（16）BD前
7、提（17）D（1），（2）（18）(E F) D 前提（19）(E F)（ 3），（4）（20）E F（ 5）（21）E（6）（22）E前提（23）E E（7），（ 8）6、 (P Q) (RS)， (QW) (SX)， (W X) ，PR = P ( 1) P 附加前提2）P R前提3）R（1），（2）4）(P Q) (R S)前提5）P Q（4）6）R S（5）7）Q（1），（5）8）S（3），（6）9）(Q W) (SX)前提10)Q W（9）11)S X（10）12)W（7），（10）13)X（8），（11）14)W X（12），（13）15)(W X)前提( 16) (W X) (W
8、 X) (14)，(15)7、A(B C)，C( D E) ， F(DE),A=BF证明： 1、（1） A前提（24）A (B C)前提（25）B C（1），（2）（26）B附加前提（27）C（3），（4）（28）C ( D E)前提（29）DE（5），（6）（30）F(D E)前提（31）F（7），（8）32） B FCP，（4），（9）8、P Q， P R，R S =S Q（1）S附加前提（2）R S前提（3）R（1），（2）（4）PR前提（5）P（3），（4）（6）P Q前提（7）Q（5），（6）（8）S QCP ，（1），（7）三、设，是三个集合，证明：1、A(BC)(AB)(AC)(
9、AB)(AC)= (AB) A C =(AB) ( A C) =(AB A ) (AB C )= A B C =A( B C ) =A( B-C)2、A=BA B= 设 A=B，则 A B=(A-B) ( B-A)= 。设 A B= ，则 A B=(A-B) ( B-A)= 。故 A-B= ，B-A= ， 从而 A B，B A，故 A=B。3、设，是三个集合，证明：(1)、 (A B)(AC)=A(BC)(2)、AB=AC，AB=AC，则 C=B 证明：(1)、(A-B) (A-C)=(A B ) (AC) =A( B C)=A B C = A-(B C)(2)、B=B(A A)=(B A)
10、(B A)=(C A) (C A )=C(A A)=C4、设，是三个集合，证明：( 1)、A(B C)(A B)C (2)、 AB = AC，A B=A C，则 C=B 证明：( 1)、A (B C)= AB C=A( B C)=(AB)C= (A-B) C=(A-B)-C(2)、B=B(A B)= B(A C)= (B A) (BC)= (A C) (BC)= C(A B)= C (A C)=C5、设，是三个集合，证明：( 1)、(A B)(A C)=A(B C)( 2)、A B=A C， A B=A C，则C=B证明：(1)、(A-B)(AC)=(AB)(AC)=(AA)( BC)= A
11、B C =A(B C)(2)、B=B ( AA)=(B A) (B A)=(CA) (C A)=C ( A A)=C四、证明：1、单位元有惟一逆元。证明：设G, 是一个群， e 是关于运算 的单位元。若 e1,e 2 都是 e 的逆元，即 e1*e=e 且 e2*e=e。因为 e 是关于运算 的单位元，所以 e1=e1*e=e=e2*e=e2。 即单位元有惟一逆元。2、设G, 是一个群，则对于 a,b G，必有唯一的 xG，使得 a x=b。 证明：因为 a-1*bG，且 a*(a -1*b)=(a*a -1 )*b=e*b=b ，所以对于 a,b G，必 有 x G，使得 a x=b。若 x
12、1,x 2 都满足要求。即 a x1=b 且 a x2=b。故 a x1=a x2。 由于 *满足消去律，故 x1=x2。从而对于 a,b G，必有唯一的 x G，使得 a x=b。3、代数系统 G,*是一个群，则 G除单位元以外无其它等幂元。 证明：设 e 是该群的单位元。若 a是G,*的等幂元，即 a*a=a。 因为 a*e=a，所以 a*a=a*e 。由于运算 *满足消去律，所以 a=e。 即 G 除单位元以外无其它等幂元。4、证明在有 n 个结点的树中，其结点度数之和是 2n-2 。 证明：设 T=V,E是任一棵树，则 |V|=n ，且 |E|=n-1 。 由欧拉握手定理，树中所有结点的度数之和等于 2|E|. 从而结点度数之和是 2n-2 。5、若连通简单无向平面图 G有 n 个结点， m条边，p 个面，且每个面至少 由 k(k 3) 条边围成，则 m k( 2) (2)。证明：设连通简单无向平面图 G=V,E,F ，则|V|=n,|E|=m,|F|=p 。 由已知对任一 f F, deg(f) k。由公式 deg(f)=2|E| 可得， 2|E| k|F| 。fF再由欧拉公式 |V|-|E|+|F|=2 可得|V|-|E|+ 2 |E| 2。k即 k(n-2) (k-2)m 。所以 m k( 2) ( 2) 。6、在半群G,*中，
