第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.2.1 解釋 1.2.2 等價公式 1.2.3 聯(lián)結詞的完備集 1.2.4 對偶式和內(nèi)否式 1.3 范式及其應用,,完全解釋、部分解釋,定義：設n元公式中所有的不同的命題變元為 P1, ,Pn 如果對每個命題變元均給予一個確定的值，則稱對公式給了一個完全解釋； 如果僅對部分變元給予確定的值， 則稱對公式給了一個部分解釋。,n元公式有2n個完全解釋。,例 考察公式 =（PQ） R,成真解釋與成假解釋,定義：對于任何公式，凡使得取真值的解釋，不管是完全解釋還是部分解釋，均稱為的成真解釋。 定義：對于任何公式，凡使得取假值的解釋，不管是完全解釋還是部分解釋，均稱為的成假解釋。,例 考察公式 =（PQ） R,永真公式與永假公式,定義：如果一個公式的所有完全解釋均為成真解釋，則稱該公式為永真公式或稱為重言式。 定義: 如果一個公式的所有完全解釋均為成假解釋，則稱該公式為永假公式或稱為予盾式。,例 由定義可知： PP為永假公式； PP為永真公式。,,可滿足公式與非永真公式,定義：如果一個公式存在成真解釋， 則稱該公式為可滿足公式； 如果一個公式存在成假解釋， 則稱該公式為非永真公式。,例 由定義可知： PP 永假公式 PP 永真公式 PQ 可滿足公式，非永真公式 PQ 可滿足公式，非永真公式,,第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.2.1 解釋 1.2.2 等價公式 1.2.3 聯(lián)結詞的完備集 1.2.4 對偶式和內(nèi)否式 1.3 范式及其應用,,邏輯等價,定義：給定兩個公式和， 設P1，P2，，Pn為和的所有命題變元， 那么和有2n個解釋。 如果對每個解釋，和永取相同的真假值， 則稱和是邏輯等價的，記為=。, ,八組重要的等價公式,雙重否定律 P=P 結合律 （P Q） R = P （Q R） （P Q） R = P （Q R） 分配律 P （Q R）=（P Q ）（P R） P （QR）=（P Q ）（P R） 交換律 P Q= Q P P Q= Q P,八組重要的等價公式,等冪律 P P = P P P = P P P = T P P = T 等值公式 P Q = P Q P Q =（PQ）（Q P） =（P Q）（P Q） =（P Q）（P Q） （P Q）= PQ （P Q）= PQ,八組重要的等價公式,部份解釋 P T = P P F = F P T = T P F = P T P = P F P = T P T = T P F = P T P = P F P = P 吸收律 P （PQ）= P P （P Q）= P,?,例 判斷下列公式的類型,q((pq) p),永真,解: q((pq) p) =q((pq) ) p =(q p )((pq) ) =T 所以，它是永真的。,例 判斷下列公式的類型,(pp) ((qq) r),永假,解: (pp) ((qq) r) = T ((qq) r) = (qq) r =Fr =F 所以，它是永假的。,例 判斷下列公式的類型,(pq) p,可滿足,解: (pq) p =(pq) p =p 所以，它是可滿足的。,成真解釋和成假解釋的求解方法,（1）否定深入：即把否定詞一直深入至命題變元上； （2）部分解釋：選定某個出現(xiàn)次數(shù)最多的變元對它作真或假的兩種解釋從而得公式； （3）化簡； （4）依次類推，直至產(chǎn)生公式的所有解釋。,例(p7) 試判定公式,(PQ)((QP)R) 的永真性和可滿足性。 解1：否定深入 原式 = (PQ)((QP)R) 對 P=T 進行解釋并化簡， 結果見教材。,例(p7) (PQ)((QP)R),解2：在否定深入的基礎上對P=F進行解釋并化簡。 原式=（FQ）（（QF）R） = （QF）R = Q R Q=T 時， 原式 =TR = R， 于是 R=T 時，原式=F R=F 時，原式=T 因此，公式存在成真解釋 （P，Q，R）=（F，T，F(xiàn)） ； 公式存在成假解釋 （P，Q，R）=（F，T，T）。 故公式可滿足但非永真。,例(p7) (PQ)((QP)R),解3：,所以，公式存在成真解釋： (T,T,*), (T,F,F), (F,T,F), (F,F,T); 公式存在成假解釋： (T,F,T), (F,T,T), (F,F,F)。 故公式可滿足但非永真。,例 試求下列公式的成真解釋和成假解釋,（PQ）（Q（RP）） 解:當P=T時, 原式= (TQ)(Q(RT)) =Q(Q(R))=QR 當P=F時, 原式= (FQ)(Q(RF)) = T(QF)=Q 由上可知: 公式不是永真公式,是可滿足的. 成真解釋為(P,Q,R)=(T,F,F),(F,T,*), 成假解釋為（(P,Q,R)=(T,T,T),(T,F,T),(T,T,F),(F,F*).,第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.2.1 解釋 1.2.2 等價公式 1.2.3 聯(lián)結詞的完備集 1.2.4 對偶式和內(nèi)否式 1.3 范式及其應用,,聯(lián)結詞的完備集,定義 設S是聯(lián)結詞的集合，如果 對任何命題演算公式均可以由S中的聯(lián)結詞表示出來的公式與之等價， 則說S是聯(lián)結詞的完備集。,由聯(lián)結詞的定義知，聯(lián)結詞集合 ，，，， 是完備的。,定理1 聯(lián)結詞的集合，，是完備的。,證明：因為 PQ =P Q PQ =（P Q） （P Q） 所以 ，，可以表示集合 ，，，，。 又因為，，，，是完備的， 即任何公式均可以由集合，，，，中聯(lián)結詞表達出來的公式與之等價， 所以任何公式均可以由集合，，中的聯(lián)結詞表達出來的公式與之等價。 故集合，，是完備的。,定理 聯(lián)結詞的集合， 是完備的。,證明：因為 P Q=( P Q) 所以 ，可以表示集合，， 又因為，，是完備的，即任何公式均可以由集合，，中聯(lián)結詞表達出來的公式與之等價， 所以任何公式均可以由集合，中的聯(lián)結詞表達出來的公式與之等價。 故集合，是完備的。,定理 聯(lián)結詞的集合， 是完備的。,證明：因為 P Q=( P Q) 所以 ，可以表示集合，， 又因為，，是完備的，即任何公式均可以由集合，，中聯(lián)結詞表達出來的公式與之等價， 所以任何公式均可以由集合，中的聯(lián)結詞表達出來的公式與之等價。 故集合，是完備的。,定理 聯(lián)結詞的集合， 是完備的。,證明：因為 P Q = P Q 所以 P Q= P Q 即， 可以表示集合， 又因為，是完全備的，即任何公式均可以由集合，中聯(lián)結詞表達出來的公式與之等價， 所以任何公式均可以由集合， 中的聯(lián)結詞表達出來的公式與之等價。 故集合， 是完備的。,與非: PQ,PQ = （P Q）,P Q PQ T T F T F T F T T F F T,,,定理2(p8) 聯(lián)結詞的集合是完備的。,證明：顯然，有： P = P P P Q= （PQ） 所以 可以表示集合， 又因為， 是完備的，即任何公式均可以由集合， 中的聯(lián)結詞表達出來的公式與之等價， 所以任何公式均可以由集合中的聯(lián)結詞表達出來的公式與之等價。 故集合是完備的。,或非 PQ=(PQ),定理： 聯(lián)結詞的集合是完備的。,例(p8) 試證明聯(lián)結詞集合不完備。,證明：假設是完備的 根據(jù)完備性的定義知 P = Q1 Q2 Q3 Qn 當P，Q1, Q2, Q3, , Qn全取為真時， 公式左邊=F， 公式右邊=T。 顯然矛盾。 故聯(lián)結詞集合不完備。,第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.2.1 解釋 1.2.2 等價公式 1.2.3 聯(lián)結詞的完備集 1.2.4 對偶式和內(nèi)否式 1.3 范式及其應用,,對偶式的定義,定義：將任何一個不含蘊含詞和等價詞的命題演算公式中的 換為 ， 換為 后所得的公式稱為的對偶式，記為*。,例 已知公式 = P（Q（RS））, 則 *= P（Q（RS）） (*)*= P（Q（RS））,,例 求如下公式 的對偶式：, =(PR) (P (Q R)) 解： PQ= PQ PQ= (P Q) (P Q) =(PR)((PQR)(P(Q R))) * =(PR)((PQR)(P(Q R))),注意：求合式公式的對偶式時，應先消去公式中的蘊含詞和等價詞。,內(nèi)否式的定義,定義：將任何命題演算公式中的所有 肯定形式換為否定形式、 否定形式換為肯定形式 后所得的公式稱為的內(nèi)否式，記為 。,例 如公式 = P （Q （R S）） 則 = P （Q（R S）） （ ） = P（Q （R S））= ,,例 =(PR) (P (Q R)),求公式的對偶式與內(nèi)否式。 解： PQ= PQ PQ= (P Q) (P Q) =(PR)((P Q R)(P(Q R))) * =(P R) ((P Q R) (P (Q R))) =(P R)((P Q R)( P( Q R))),例 = (PQ)((QR)P),試寫出公式的對偶式和內(nèi)否式 解： 因為 PQ= PQ, 所以 = (PQ)((QR)P) 于是 * = (PQ)((QR) P) - = (PQ)((QR)P),雙重對偶式和內(nèi)否式,性質1 （*）* = （） = ,例 = (PQ)((QR)P) * = (PQ)((QR) P) (*)* = (PQ)((QR)P) = - = (PQ)((QR)P) (-)- = (PQ)((QR)P) =,合取與析取的對偶式和內(nèi)否式,性質2 (A B)* = A* B* (A B) = A B (A B)* = A* B* (A B) = A B,對偶式和內(nèi)否式的否定,定理1(p9) （A*）=（A）* （A）=（A）,證明可以模仿定理2的證明進行，省略,約定在討論對偶式和內(nèi)否式的定理時，命題公式中僅含有，和三個聯(lián)結詞，即應先消去公式中的蘊含詞和等價詞。,定理2(p9) A =A*,證明：對公式A中出現(xiàn)的聯(lián)結詞的個數(shù)n進行歸納證明 奠基：當n=0時 A中無聯(lián)結詞，便有 A=P， 從而有 A=P， 且A*=P ， 所以A* = P= A，即定理成立。 歸納：設nk時定理成立。 考察n=k+11，A中至少有一個聯(lián)結詞， 可分為下面三種情形： A=A1， A=A1A2， A=A1A2 其中A1，A2中的聯(lián)結詞個數(shù) k,定理2的證明（續(xù)）,依歸納假設 A1= A1* ， A2= A2* 當A=A1時， A =（ A1） =（A1*） 歸納假設 =（A1）* 定理1 = A* 當A=A1A2時，A = （A1A2） = A1 A2 等值公式 = A1* A2* 歸納假設 =（A1* A2*） 內(nèi)否的定義 =（A1 A2）* 對偶的定義 = A* 同理可證當當A=A1A2時結論成立。 數(shù)學歸納法知，定理得證。,勘誤！,定理3、定理4,定理3 A和A既同永真又同可滿足。 定理4 AB和B*A*既同永真又同可滿足。 AB和A*B*既同永真又同可滿足。,不難證明，證明省略。,第一章 命題演算基礎,1.1 命題和聯(lián)結詞 1.2 真假性 1.2.1 解釋 1.2.2 等價公式 1.2.3 聯(lián)結詞的完備集 1.2.4 對偶式和內(nèi)否式 1.3 范式及其應用,,