命題邏輯等值演算

1、第二章命題邏輯等值演算例1 .設三元真值函數(shù)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 試用一個僅含聯(lián)結詞 ，的命題形式來表示f。解：根據三元真值函數(shù)f的定義，可知其具有以下真值表：PQRf(P,Q,R)TTTTTTFFTFTTTFFTFTTTFTFFFFTTFFFF那么根據真值表法可以求出f的主合取范式為:(PV Q VR)A(PV Q VR)A(PVQ VR)而：(PV Q VR)A(PV

2、Q 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(

4、PVQV 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

7、 (PAQ)(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中聯(lián)結詞的公式。(1)( P (Q (Q AR)(2) P (Q R)解：(1)( P (Q (Q AR)( PV(Q(QAR)A(QAR)Q)( PV( QV(Q AR)A( (QAR)VQ)( PV( QVR)PAQAR(2) P (Q R)(P(QR)A(Q R) P)(P(QR)A(RQ) A(QR)A(RQ

8、) P)(PV(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. 在某班班委成員的選舉中，王小紅、李強、丁金生三位同學被選進了 班委會，該班的甲、乙、丙三名學生預言： 甲說：王小紅為班長，李強為生活委員。 乙說：丁金生為班長，王小紅為生活委員。 丙說：李強為班長，王小紅為學習委員。班委會分工名單公布后發(fā)現(xiàn)，甲、乙、丙三人恰好都猜對了一半。問王小 紅、李強、丁金生各任何職(用等值演算求解)？解：

9、設P:王小紅為班長； 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 不能同時為真 (因為這樣不符合題意),故上式變?yōu)椋篏 ( PAQ

10、ARA S) A( M AN)V(M A 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即

11、為永真式，故PAQ (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 . (討論題) 聯(lián)結詞“ 和“ 服從結合律么？解： 聯(lián)結詞“ 和“ 均不服從結合律。證明方法有以下兩種：方法一： (P Q) R( (PAQ)AR)(PAQ)V R而 P (Q R)(PA (QAR)PV(QAR)一般而言(PAQ) V R與 PV(P AQ)是不等價的，故聯(lián)結詞“不服從(P Q) R 而 P (Q R)結合律。( (PVQ)VR)(PVQ)A R(PV ( QVR)PA(QV

12、R)一般而言(PVQ) A R與 PA(Q VR)是不等價的，故聯(lián)結詞“不服從結合律。方法二：可以舉例如下：對于，給出一組真值指派：P為F，Q為T, R為T，那么(P Q) R 為F,但是P (Q R)為T,故聯(lián)結詞“ 不服從結合律。對于，給出一組真值指派：P為T, Q為F，R為F，那么(P Q) R 為T,但是P (Q R)為F,故聯(lián)結詞“ 不服從結合律。例10 .(思考題)設計一個保密鎖的控制電路，鎖上共有三個按鈕A,Q,C。當三鍵同時按下，或只有A,Q兩鍵按下，或只有A,Q其中之一按下時，鎖被 翻開。請寫出此控制電路的公式并畫出線路圖。分析：此題是邏輯在電路設計中的應用。 解題時先用真值表求出開鎖條件， 再寫 出邏輯表達式，化成最簡的形式，最后根據最簡表達式畫出電路圖。解：根據題目要求，列出開鎖條件的真值表：設P： A按下，Q : B按下，R： C按下得真值表如下所示：PQRG0000001001010110100110101101