命題邏輯等值演算

1、第二章命題邏輯等值演算例1 .設(shè)三元真值函數(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 試用一個(gè)僅含聯(lián)結(jié)詞 ，的命題形式來(lái)表示f。解：根據(jù)三元真值函數(shù)f的定義，可知其具有以下真值表：PQRf(P,Q,R)TTTTTTFFTFTTTFFTFTTTFTFFFFTTFFFF那么根據(jù)真值表法可以求出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來(lái)表示。例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 . 證明以下等價(jià)式。( 1) (P Q)A(PR) PQAR ;(2) PAQA( PV Q)PA QA(PVQ) .解：說(shuō)明 : 這兩道題看似麻煩，但是如果不采用直接推導(dǎo)的方法，而是利用范式 或是左右?jiàn)A擊推導(dǎo)的方法，會(huì)起到事半功倍的效果。(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)結(jié)詞的公式。(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. 在某班班委成員的選舉中，王小紅、李強(qiáng)、丁金生三位同學(xué)被選進(jìn)了 班委會(huì)，該班的甲、乙、丙三名學(xué)生預(yù)言： 甲說(shuō)：王小紅為班長(zhǎng)，李強(qiáng)為生活委員。 乙說(shuō)：丁金生為班長(zhǎng)，王小紅為生活委員。 丙說(shuō)：李強(qiáng)為班長(zhǎng)，王小紅為學(xué)習(xí)委員。班委會(huì)分工名單公布后發(fā)現(xiàn)，甲、乙、丙三人恰好都猜對(duì)了一半。問(wèn)王小 紅、李強(qiáng)、丁金生各任何職(用等值演算求解)？解：

9、設(shè)P:王小紅為班長(zhǎng)； Q :李強(qiáng)為生活委員；R: 丁金生為班長(zhǎng)；S:王小紅為生活委員；M :李強(qiáng)為班長(zhǎng)；N :王小紅為學(xué)習(xí)委員由條件可得公式:T: ( PAQ) V(PA Q)U: ( RAS)V(RA S)W: ( M AN) V(M A N)根據(jù)題意得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 不能同時(shí)為真, Q 和 S 不能同時(shí)為真, P 和 S 不能同時(shí)為真 (因?yàn)檫@樣不符合題意),故上式變?yōu)椋篏 ( PAQ

10、ARA S) A( M AN)V(M A N)( PAQARA SA MAN)V( PAQARA SAMA N)由于 P,R,M 不能同時(shí)為真, P,S,N 不能同時(shí)為真(因?yàn)檫@樣不符合題意) , 那么上式僅剩一項(xiàng) PAQ ARA SA M AN，可見(jiàn)王小紅不是班長(zhǎng)，李強(qiáng)是生活委員， 丁金生是班長(zhǎng),王小紅不是生活委員,李強(qiáng)不是班長(zhǎng),王小紅是學(xué)習(xí)委員, 于是得到：王小紅是學(xué)習(xí)委員，李強(qiáng)是生活委員，丁金生是班長(zhǎng)。例 8 . (討論題) 試用多種方法證明蘊(yùn)含式 PAQ (P Q)解：方法一：只要證明PAQ(P Q)是永真式。PAQ (P Q)(PAQ)V( PVQ)PV QV PVQQV PVQT即

11、為永真式，故PAQ (P Q)成立。方法二：設(shè)PAQ為T(mén),那么P和Q都為T(mén),那么P Q為T(mén),故PAQ (P Q)。 方法三：設(shè)P Q為F,那么P為T(mén),Q為F,那么PAQ為F,故PAQ (P Q)。例 9 . (討論題) 聯(lián)結(jié)詞“ 和“ 服從結(jié)合律么？解： 聯(lián)結(jié)詞“ 和“ 均不服從結(jié)合律。證明方法有以下兩種：方法一： (P Q) R( (PAQ)AR)(PAQ)V R而 P (Q R)(PA (QAR)PV(QAR)一般而言(PAQ) V R與 PV(P AQ)是不等價(jià)的，故聯(lián)結(jié)詞“不服從(P Q) R 而 P (Q R)結(jié)合律。( (PVQ)VR)(PVQ)A R(PV ( QVR)PA(QV

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