命題邏輯等值演算_第1頁
命題邏輯等值演算_第2頁
命題邏輯等值演算_第3頁
已閱讀5頁,還剩2頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論