資源描述：
《離散數(shù)學(xué)第一章命題演算基礎(chǔ)-真假性.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、第一章命題演算基礎(chǔ)1.1命題和聯(lián)結(jié)詞1.2真假性1.2.1解釋1.2.2等價(jià)公式1.2.3聯(lián)結(jié)詞的完備集1.2.4對(duì)偶式和內(nèi)否式1.3范式及其應(yīng)用完全解釋、部分解釋定義：設(shè)n元公式?中所有的不同的命題變?cè)獮镻1,…,Pn如果對(duì)每個(gè)命題變?cè)o予一個(gè)確定的值，則稱對(duì)公式?給了一個(gè)完全解釋；如果僅對(duì)部分變?cè)o予確定的值，則稱對(duì)公式?給了一個(gè)部分解釋。n元公式?有2n個(gè)完全解釋。例考察公式?=（P?Q）?RPQR?TTTTTTFFTT*不能確定F**T成真解釋與成假解釋定義：對(duì)于任何公式?，凡使得?取真值的解釋，不管是完全解釋還是部分解釋，均稱為?的成真解釋。定義：對(duì)于任何
2、公式?，凡使得?取假值的解釋，不管是完全解釋還是部分解釋，均稱為?的成假解釋。例考察公式?=（P?Q）?RPQR?TTTT1個(gè)成真解釋TTFF1個(gè)成假解釋TT*不能確定1個(gè)成真解釋1個(gè)成假解釋F**T4個(gè)成真解釋永真公式與永假公式定義：如果一個(gè)公式的所有完全解釋均為成真解釋，則稱該公式為永真公式或稱為重言式。定義:如果一個(gè)公式的所有完全解釋均為成假解釋，則稱該公式為永假公式或稱為予盾式。例由定義可知：P??P為永假公式；P??P為永真公式?？蓾M足公式與非永真公式定義：如果一個(gè)公式存在成真解釋，則稱該公式為可滿足公式；如果一個(gè)公式存在成假解釋，則稱該公式為非永真公式。例
3、由定義可知：P??P永假公式P??P永真公式P?Q可滿足公式，非永真公式P?Q可滿足公式，非永真公式第一章命題演算基礎(chǔ)1.1命題和聯(lián)結(jié)詞1.2真假性1.2.1解釋1.2.2等價(jià)公式1.2.3聯(lián)結(jié)詞的完備集1.2.4對(duì)偶式和內(nèi)否式1.3范式及其應(yīng)用邏輯等價(jià)定義：給定兩個(gè)公式?和?，設(shè)P1，P2，……，Pn為?和?的所有命題變?cè)?，那?和?有2n個(gè)解釋。如果對(duì)每個(gè)解釋，?和?永取相同的真假值，則稱?和?是邏輯等價(jià)的，記為?=?。???八組重要的等價(jià)公式雙重否定律??P=P結(jié)合律（P?Q）?R=P?（Q?R）（P?Q）?R=P?（Q?R）分配律P?（Q?R）=（P?Q）?（
4、P?R）P?（Q?R）=（P?Q）?（P?R）交換律P?Q=Q?PP?Q=Q?P八組重要的等價(jià)公式等冪律P?P=PP?P=PP?P=TP?P=T等值公式P?Q=?P?QP?Q=（P?Q）?（Q?P）=（?P?Q）?（P??Q）=（P?Q）?（?P??Q）?（P?Q）=?P??Q?（P?Q）=?P??Q八組重要的等價(jià)公式部份解釋P?T=PP?F=FP?T=TP?F=PT?P=PF?P=TP?T=TP?F=?PT?P=PF?P=?P吸收律P?（P?Q）=PP?（P?Q）=P?例判斷下列公式的類型q∨?((?p∨q)∧p)永真解:q∨?((?p∨q)∧p)=q∨(?(?p∨
5、q))∨?p=(q∨?p)∨(?(?p∨q))=T所以，它是永真的。例判斷下列公式的類型(p∨?p)?((q∧?q)∧r)永假解:(p∨?p)?((q∧?q)∧r)=T?((q∧?q)∧r)=(q∧?q)∧r=F∧r=F所以，它是永假的。例判斷下列公式的類型(p?q)∧?p可滿足解:(p?q)∧?p=(?p∨q)∧?p=?p所以，它是可滿足的。成真解釋和成假解釋的求解方法（1）否定深入：即把否定詞一直深入至命題變?cè)?；?）部分解釋：選定某個(gè)出現(xiàn)次數(shù)最多的變?cè)獙?duì)它作真或假的兩種解釋從而得公式；（3）化簡(jiǎn)；（4）依次類推，直至產(chǎn)生公式的所有解釋。例(p7)試判定公式?(
6、P?Q)?((?Q?P)??R)的永真性和可滿足性。解1：否定深入原式=(?P??Q)?((?Q?P)??R)對(duì)P=T進(jìn)行解釋并化簡(jiǎn)，結(jié)果見(jiàn)教材。例(p7)(?P??Q)?((?Q?P)??R)解2：在否定深入的基礎(chǔ)上對(duì)P=F進(jìn)行解釋并化簡(jiǎn)。原式=（?F??Q）?（（?Q?F）??R）=（?Q?F）??R=Q??RQ=T時(shí)，原式=T??R=?R，于是R=T時(shí)，原式=FR=F時(shí)，原式=T因此，公式存在成真解釋（P，Q，R）=（F，T，F(xiàn)）；公式存在成假解釋（P，Q，R）=（F，T，T）。故公式可滿足但非永真。例(p7)?(P?Q)?((?Q?P)??R)解3：所以，公式
7、存在成真解釋：(T,T,*),(T,F,F),(F,T,F),(F,F,T);公式存在成假解釋：(T,F,T),(F,T,T),(F,F,F)。故公式可滿足但非永真。(P,Q,R)A=?(P?Q)B=?Q?PC=B??RA?C(T,T,T)FTFT(T,T,F)FFFT(T,F,T)TTFF(T,F,F)TTTT(F,T,T)TTFF(F,T,F)TTTT(F,F,T)TFTT(F,F,F)TFFF例試求下列公式的成真解釋和成假解釋??（P??Q）?（Q?（?R?P））解:當(dāng)P=T時(shí),原式=(T??Q)?(Q?(?R?T))=?Q?(Q?(?R))=
