命题逻辑等值演算

1、第二章命题逻辑等值演算例1 .设三元真值函数f为：f (0,0,0 )= 0, f (0,0,1 )= 1 , f (0,1,0 )= 0 , f (1,0,0 )= 1 f( 0,1,1 )= 1, f (1,0,1 )= 1, f (1,1,0 )= 0, f (1,1,1 )= 1 试用一个仅含联结词 ，的命题形式来表示f。解：根据三元真值函数f的定义，可知其具有以下真值表：PQRf(P,Q,R)TTTTTTFFTFTTTFFTFTTTFTFFFFTTFFFF则根据真值表法可以求出f的主合取范式为:(PV Q VR)A(PV Q VR)A(PVQ VR)而：(PV Q VR)A(PV Q

2、 VR)A(PVQ VR)(PV Q VR)A(PVR)(PV Q) AP)VR(P A Q) VR又由于：PAQ(P Q)PVQP Q所以，(PA Q) VR(P A Q) R(P Q) R所以，f可以用仅含, 的命题(P Q)R来表示。例2 .不用真值表判断下列公式是永真式、永假式还是其它(1) (PVQ)(PAQ);(2) (Q P)V P)A(PVR);(PVQ)R) (P V Q) VR).解：(1) (P VQ)所以，(PVQ)( PA Q)V(PAQ)(P AQ)(P VQ) V(P AQ)2)(Q P)V P)A(PVR)( QVP)V P)A(PVR)(P AQ)既非永真式也

3、非永假式。TA(PVR)FA(PVR)F所以，(Q P)V P) A(P VR)为永假式。( 3 )( PVQ)R)(PVQ)VR)( ( PVQ)VR)(PV Q)VR)(PV Q)VR)(PVQ)VR)T所以，( PVQ) R)(PVQ) VR)为永真式。例 3 . 证明下列等价式。( 1) (P Q)A(PR) PQAR ;(2) PAQA( PV Q)PA QA(PVQ) .解：说明 : 这两道题看似麻烦，但是如果不采用直接推导的方法，而是利用范式 或是左右夹击推导的方法，会起到事半功倍的效果。(1) . (P Q)A(P R) ( PVQ)A( PVR)( P VQ VR) A( P

4、VQV R)A( PV QVR)M4 AM5 AM6P QARPV(QAR)( PVQ)A( PVR)( P VQ VR) A( PVQV R)A( PV QVR)M4 AM5 AM6所以，(P Q) A(P R) P Q AR 成立。(2) .PAQA( PV Q)(PAQA P)V(PAQA Q)FPA QA(PVQ)( PA QAP)V( PA QAQ)F所以， PAQA( PV Q)PA QA(PVQ)例 4 . 试求下列各公式的主析取范式和主合取范式。(1) (P(QAR)A(P(QR)(2) (PVQ)R) P解: (1)(P(Q AR) A(P(QR)( PV(Q AR)A(P

5、V(Q VR)(PVQ) A( PVR)人(PVQ VR)(PVQ VR)A( PVQ V R)A( PV Q VR) A(P VQ VR)M4AM5AM6AM0 (主合取范式 ) 则其主析取范式为 m1 Vm2 Vm3 Vm7(2)(PVQ) R) P( (PVQ)VR)VP(PVQ) A R)VP(PA R)V(QA R)VP(QA R)VP(QVP)A( RVP)(PVQVR)A(PVQV R)A(PV QV R) M0AM1AM3 (主合取范式 ) 则其主析取范式为 m2 Vm4 Vm5 Vm6 Vm7例 5 . 用等值演算法证明下面等值式。(1) P(PAQ)V(PA Q)(2) (

6、P Q)A(PR) P(QAR)(3) (P Q) (PVQ)A (PAQ)(4) (PA Q)V( PAQ)(PVQ)A (PAQ)解: (1) 右边PA(PV Q) A(P VQ) A(Q V Q)PA(PV QAQ)ATPAPP 左边所以 P (PAQ)V(PA Q)(2) 左边 ( PVQ)A( PVR)PVQARP(QAR)右边所以(PQ) A(PR) P (Q AR)(3) 左边(PQ)A(QP)( PVQ)V ( QVP)PA QVQA P(PVQ)A(PV P)A( QVQ)A( QV P)(PVQ)A( QV P)(PVQ)A (PAQ)右边所以 (P Q)(PVQ)A (P

7、AQ)(4) 左边 (PA Q)V( PAQ)(P V P) A(P VQ) A(Q V P)A( Q VQ)(PVQ)A( QV P)(PVQ)A (PAQ)右边所以 (PA Q)V( PAQ)(PVQ)A (PAQ)例 6 . 将下列公式化成与之等值且只含 , V, A中联结词的公式。(1)( P (Q (QAR)(2) P (Q R)解：(1)( P (Q (QAR)( PV(Q(QAR)A(QAR)Q)( PV( QV(QAR)A( (QAR)VQ)( PV( QVR)PAQAR(2) P (Q R)(P(QR)A(Q R) P)(P(QR)A(RQ) A(QR)A(RQ) P)(PV

8、(QVR)A(RVQ)A(QR)A(RQ)VP)(PV(QVR)A(RVQ)A( QVR)V (RVQ)VP)( PV QA RVRAQ) A(Q A RVRA QVP) ( PAQA R)V( PA QAR)V(PA QA R)V(PAQAR)例 7. 在某班班委成员的选举中，已知王小红、李强、丁金生三位同学被选进了 班委会，该班的甲、乙、丙三名学生预言： 甲说：王小红为班长，李强为生活委员。 乙说：丁金生为班长，王小红为生活委员。 丙说：李强为班长，王小红为学习委员。班委会分工名单公布后发现，甲、乙、丙三人恰好都猜对了一半。问王小 红、李强、丁金生各任何职(用等值演算求解)？解：设P:王小

9、红为班长； Q :李强为生活委员；R: 丁金生为班长；S:王小红为生活委员；M :李强为班长；N :王小红为学习委员由已知条件可得公式:T: ( PAQ)V(PA Q)U: ( RAS)V(RA S)W: ( M AN) V(M A N)根据题意得GT AU AWT,于是GTAU AW(P AQ) V(P A Q) A( R AS) V(R A S)AW(PAQARAS)V(PAQARAS) V(P AQ AR AS) V(P AQ ARA S)AW由于 P 和 R 不能同时为真, Q 和 S 不能同时为真, P 和 S 不能同时为真 (因为这样不符合题意),故上式变为：G ( PAQARA

10、S) A( MAN)V(MA N)( PAQARA SA MAN)V( PAQARA SAMA N)由于 P,R,M 不能同时为真, P,S,N 不能同时为真(因为这样不符合题意) , 则上式仅剩一项 PAQ ARA SA M AN，可见王小红不是班长，李强是生活委员， 丁金生是班长,王小红不是生活委员,李强不是班长,王小红是学习委员, 于是得到：王小红是学习委员，李强是生活委员，丁金生是班长。例 8 . (讨论题) 试用多种方法证明蕴含式 PAQ (P Q)解：方法一：只要证明PAQ(P Q)是永真式。PAQ (P Q)(PAQ)V( PVQ)PV QV PVQQV PVQT即为永真式，故P

11、AQ (P Q)成立。方法二：设PAQ为T,则P和Q都为T,则P Q为T,故PAQ (P Q)。 方法三：设P Q为F,则P为T,Q为F,则PAQ为F,故PAQ (P Q)。例 9 . (讨论题) 联结词“ ”和“ ”服从结合律么？解： 联结词“ ”和“ ”均不服从结合律。证明方法有以下两种：方法一： (P Q) R( (PAQ)AR)(PAQ)V R而 P (Q R)(PA (QAR)PV(QAR)一般而言(PAQ) V R与 PV(P AQ)是不等价的，故联结词“”不服从(P Q) R 而 P (Q R)结合律。( (PVQ)VR)(PVQ)A R(PV ( QVR)PA(QVR)一般而言

12、(PVQ) A R与 PA(Q VR)是不等价的，故联结词“”不服从结合律。方法二：可以举例如下：对于，给出一组真值指派：P为F，Q为T, R为T，则(P Q) R 为F,但是P (Q R)为T,故联结词“ ”不服从结合律。对于，给出一组真值指派：P为T, Q为F，R为F，则(P Q) R 为T,但是P (Q R)为F,故联结词“ ”不服从结合律。例10 .(思考题)设计一个保密锁的控制电路，锁上共有三个按钮A,Q,C。当三键同时按下，或只有A,Q两键按下，或只有A,Q其中之一按下时，锁被 打开。请写出此控制电路的公式并画出线路图。分析：本题是逻辑在电路设计中的应用。 解题时先用真值表求出开锁条件， 再写 出逻辑表达式，化成最简的形式，最后根据最简表达式画出电路图。解：根据题目要求，列出开锁条件的真值表：设P： A按下，Q : B按下，R： C按下得真值表如下所示：PQRG000000100101011010011010110111