離散數學命題邏輯課件

離散數學

云南大學軟件學院

任課教師：謝仲文

2013年秋季學期1離散數學

云南大學軟件學院

任課教師：謝仲文

201緒論課程介紹和要求主要內容教材說明什么是離散數學？為什么要學習離散數學？怎樣學習離散數學？課程要求與考試2緒論課程介紹和要求主要內容2教材主教材：1、郝林等編著.離散數學.北京:科學出版社,2012年5月參考書目：2、屈婉玲等編著.離散數學.北京:高等教育出版社，2008年3月3、左孝凌等編著.離散數學.上海:上?？茖W技術文獻出版社,2004年1月3教材主教材：3問題什么是數理邏輯？（符號化+推理規(guī)則）經典數理邏輯和現代數理邏輯主要內容命題邏輯謂詞邏輯推理與證明技術第一部分數理邏輯4問題第一部分數理邏輯4第一講命題邏輯的基本概念主要內容命題與聯結詞命題及其分類聯結詞與復合命題命題公式及其賦值5第一講命題邏輯的基本概念主要內容5命題與真值命題：判斷結果惟一的陳述句命題的真值：判斷的結果真值的取值范圍：真與假真命題與假命題注意：感嘆句、祈使句、疑問句都不是命題陳述句中的悖論，判斷結果不惟一確定的不是命題

1.1命題與聯結詞6命題與真值1.1命題與聯結詞6悖論如果有一個句子B，如果承認B，則可以推出非B成立；反之，如果承認非B，又可推出B成立。例子：1、我正在說假話。2、羅素的理發(fā)師悖論。3、克里特人伊壁孟德：所有的克里特人都是撒謊者。悖論不是命題！悖論的共同特征：論斷者屬于論斷主體集。7悖論如果有一個句子B，如果承認B，則可以推出非B成立；7例1

下列句子中那些是命題？(1)是有理數.(2)2+5=7.(3)x+5>3.(4)你去教室嗎？(5)這個蘋果真大呀！(6)請不要講話！(7)2050年元旦下大雪.假命題命題概念真命題不是命題不是命題不是命題不是命題命題，但真值現在不知道判斷給定句子是否為命題的方法和步驟：1、判斷它是否為陳述句；2、判斷它是否有唯一的真值。8例1下列句子中那些是命題？假命題命題概念真命題不是命題分類：簡單命題（也稱原子命題）與復合命題簡單命題符號化：命題常量用小寫英文字母p,q,r,…,pi,qi,ri(i1)表示簡單命題用“1”或“1”表示真，用“0”或“0”表示假例如，令p：是有理數，（p的真值為0）q：2+5=7，（q的真值為1）復合命題符號化：由常量和聯結詞組成的公式

命題分類9命題分類：簡單命題（也稱原子命題）與復合命題命題分類9否定、合取、析取聯結詞定義1.3設p,q為兩個命題，復合命題“p或q”稱作p與q的析取式，記作p∨q，∨稱作析取聯結詞.規(guī)定p∨q為假當且僅當p與q同時為假.定義1.1設p為命題，復合命題“非p”(或“p的否定”)稱為p的否定式，記作p，符號稱作否定聯結詞.規(guī)定p為真當且僅當p為假.定義1.2設p,q為兩個命題，復合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q，∧稱作合取聯結詞.規(guī)定p∧q為真當且僅當p與q同時為真.10否定、合取、析取聯結詞定義1.3設p,q為兩個命題，復合例2

將下列命題符號化.(1)吳穎既用功又聰明.(2)吳穎不僅用功而且聰明.(3)吳穎雖然聰明，但不用功.(4)張輝與王麗都是三好生.(5)張輝與王麗是同學.合取聯結詞的實例11例2將下列命題符號化.合取聯結詞的實例11解令p:吳穎用功,q:吳穎聰明(1)pq(2)pq(3)pq(4)設p:張輝是三好生,q:王麗是三好生

pq(5)p:張輝與王麗是同學(1)—(3)說明描述合取式的靈活性與多樣性(4)—(5)要求分清“與”所聯結的成分合取聯結詞的實例12解令p:吳穎用功,q:吳穎聰明合取聯結詞的實例12例3將下列命題符號化(1)2或4是素數.(2)2或3是素數.(3)4或6是素數.(4)小元元只能拿一個蘋果或一個梨.(5)王小紅生于1975年或1976年.析取聯結詞的實例13例3將下列命題符號化析取聯結詞的實例13解(1)令p:2是素數,q:4是素數,pq(2)令p:2是素數,q:3是素數,pq(3)令p:4是素數,q:6是素數,pq(4)令p:小元元拿一個蘋果,q:小元元拿一個梨(pq)(pq)(5)p:王小紅生于1975年,q:王小紅生于1976年,(pq)(pq)(1)—(3)為相容或(4)—(5)為排斥或合取和析取如何記憶？析取聯結詞的實例14解析取聯結詞的實例14定義1.4設p,q為兩個命題，復合命題“如果p,則q”稱作p與q的條件式，記作pq，并稱p是條件式的前件，q為條件式的后件，稱作條件聯結詞.規(guī)定：pq為假當且僅當p為真q為假.蘊涵聯結詞(1)pq的邏輯關系：q為p的必要條件(2)“如果p,則q”有很多不同的表述方法：若p，就q只要p，就qp僅當q只有q才p除非q,才p或除非q，否則非p，…．(3)當p為假時，pq恒為真(4)常出現的錯誤：不分充分與必要條件15定義1.4設p,q為兩個命題，復合命題“如果p,則q”例4設p：天冷，q：小王穿羽絨服，將下列命題符號化(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當天冷的時候.蘊涵聯結詞的實例pq注意：pq與qp、pq等值（真值相同）pqpqqpqppqqpqp16例4設p：天冷，q：小王穿羽絨服，將下列命題符號化蘊涵定義1.5設p,q為兩個命題，復合命題“p當且僅當q”稱作p與q的等價式，記作pq，稱作等價（雙條件）聯結詞.規(guī)定pq為真當且僅當p與q同時為真或同時為假.pq的邏輯關系：p與q互為充分必要條件等價聯結詞例5求下列復合命題的真值(1)2+2＝4當且僅當3+3＝6.(2)2+2＝4當且僅當3是偶數.(3)2+2＝4當且僅當太陽從東方升起.(4)2+2＝4當且僅當美國位于非洲.(5)函數0(x)在x0可導的充要條件是它在x0連續(xù).1001017定義1.5設p,q為兩個命題，復合命題“p當且僅當q”自學內容課本P8—P9：四種次重要聯結詞18自學內容18本小節(jié)中p,q,r,…均表示命題.聯結詞集為{,,,,}，p,pq,pq,pq,pq為基本復合命題.其中要特別注意理解pq的涵義.反復使用{,,,,}中的聯結詞組成更為復雜的復合命題.復合命題的各個原子命題之間可以無任何實際聯系。 設p:是無理數，q:3是奇數，r:蘋果是方的，s:太陽繞地球轉則復合命題(pq)((rs)p)是假命題.小結聯結詞的運算順序：,,,,,同級按先出現者先運算.聯結詞的對稱性。19本小節(jié)中p,q,r,…均表示命題.聯結詞集為{,1.2命題公式及其賦值命題變項與合式公式命題變項合式公式合式公式的層次公式的賦值公式賦值公式類型真值表201.2命題公式及其賦值命題變項與合式公式20命題變項與合式公式命題常項、命題變項（命題變元）：類比常量和變量。常項與變項均用p,q,r,…,pi,qi,ri,…,等表示.定義1.6合式公式（簡稱公式）的遞歸定義：(1)單個命題變項和命題常項是合式公式,稱作原子命題公式(2)若A是合式公式，則(A)也是(3)若A,B是合式公式，則(AB),(AB),(AB),(AB)也是(4)只有有限次地應用(1)—(3)形成的符號串才是合式公式幾點說明：1、命題公式可以是沒有真假值的；2、并不是由命題常（變）元、聯結詞和一些括號組成的字符串都能成為命題公式；3、遞歸定義：由基礎、歸納和界限組成。21命題變項與合式公式命題常項、命題變項（命題變元）：類比常量合式公式的層次定義1.7(1)若公式A是單個命題變項，則稱A為0層公式.(2)稱A是n+1(n≥0)層公式是指下面情況之一：(a)A=B,B是n層公式；(b)A=BC,其中B,C分別為i層和j層公式，且n=max(i,j)；(c)A=BC,其中B,C的層次及n同(b)；(d)A=BC,其中B,C的層次及n同(b)；(e)A=BC,其中B,C的層次及n同(b).(3)若公式A的層次為k,則稱A為k層公式.例如公式A=p,B=p,C=pq,D=(pq)r,E=((pq)r)(rs)分別為0層，1層，2層，3層，4層公式.22合式公式的層次定義1.722第二講命題邏輯的等值演算上一講主要內容回顧：簡單命題和復合命題、5個重要聯結詞；命題常項和命題變項；公式的遞歸定義、公式的層次；第二講主要內容1-4真值表與等價公式1-5重言式與蘊含式23第二講命題邏輯的等值演算上一講主要內容回顧：23定義1.8

設p1,p2,…,pn是出現在公式A中的全部命題變項,給p1,p2,…,pn各指定一個真值,稱為對A的一個賦值或解釋.若使A為1,則稱這組值為A的成真賦值;若使A為0,則稱這組值為A的成假賦值.例：如000,010,101,110是(pq)r的成真賦值001,011,100,111是成假賦值.說明：A中僅出現p1,p2,…,pn，給A賦值=12…n是指p1=1,p2=2,…,pn=n,i=0或1,i之間不加標點符號

A中僅出現p,q,r,…,給A賦值123…是指

p=1,q=2,r=3…思考：含n個命題變項的公式有多少個賦值？公式賦值24定義1.8設p1,p2,…,pn是出現在公式A中定義1-4.1

將命題公式A在所有賦值下取值的情況列成表,稱作A的真值表.構造真值表的步驟:(1)找出公式中所含的全部命題變項p1,p2,…,pn(若無下角標則按字母順序排列),列出2n個全部賦值,從000開始,按二進制加法,每次加1,直至111為止.

(2)按從低到高的順序寫出公式的各個層次.(3)對每個賦值依次計算各層次的真值,直到最后計算出公式的真值為止.真值表25定義1-4.1將命題公式A在所有賦值下取值的情況列成表,例6

寫出下列公式的真值表,并求它們的成真賦值和成假賦值:(1)(pq)r(2)(qp)qp(3)(pq)q真值表26例6寫出下列公式的真值表,并求它們的成真賦值和成假真值表(1)A=(pq)r成真賦值:000,001,010,100,110;成假賦值:011,101,111

pqrpq

r

(pq)r000001010011100101110111001111111010101011101010真值表127(1)A=(pq)r成真賦值:000,001(2)B＝(qp)qp成真賦值:00,01,10,11;無成假賦值p

q

qp(qp)q(qp)qp00011011101100011111真值表228(2)B＝(qp)qp成真賦值:00,01,10,(3)C＝(pq)q的真值表成假賦值:00,01,10,11;無成真賦值p

q

ppq(pq)(pq)q000110111100110100100000真值表329(3)C＝(pq)q的真值表成假賦值:00,0問題思考1、回顧：含n個命題變元的公式共有多少個不同的賦值？2、含n個命題變元的真值表共有多少種不同的真值情況？3、真值表與公式之間的關系？30問題思考1、回顧：含n個命題變元的公式共有多少個不同的賦值？公式的類型定義1.10

(1)若A在它的任何賦值下均為真,則稱A為重言式或永真式;(2)若A在它的任何賦值下均為假,則稱A為矛盾式或永假式;(3)若A不是矛盾式,則稱A是可滿足式.由例1可知,(pq)r,(qp)qp,(pq)q分別為非重言式的可滿足式,重言式,矛盾式.思考：重言式與可滿足式、矛盾式之間的關系？31公式的類型定義1.1031真值表的用途真值表可用于求出公式的全部成真賦值與成假賦值,判斷公式的類型注意：1、如果兩個公式的真值表對所有賦值最后一列都相同，則稱兩個公式的真值表相同；2、真值表只考慮最后的結果，而不考慮構造真值表的中間過程。32真值表的用途真值表可用于求出公式的全部成真賦值與成假賦值,等價公式－概念兩種定義：1、給定兩個命題公式A和B，設P1，P2，…，Pn為所有出現于A和B中的原子變元，若給P1，P2，…，Pn任一組真值指派，A和B的真值都相同，則稱A和B是等價公式或邏輯相等，記作AB。2、若等價式AB是重言式，則稱A與B等值，記作AB，并稱AB是等值式，A和B是等價公式。說明：1、與的區(qū)別；2、A或B中可能有啞元出現.例(pq)((pq)(rr))r為左邊公式的啞元.33等價公式－概念兩種定義：33等值式例題例1判斷下列各組公式是否等值:(1)p(qr)與(pq)r111111011111110111011101000001010011100101110111(pq)rp(qr)qr

pqrpq00000011結論:p(qr)(pq)r34等值式例題例1判斷下列各組公式是否等值:11100等值式例題(2)p(qr)與(pq)r010111011111110111011101000001010011100101110111(pq)rp(qr)qr

pqrpq11110011結論:p(qr)與(pq)r不等值35等值式例題(2)p(qr)與(pq)r基本等價公式(1/2)雙重否定律AA冪等律AAA,AAA交換律ABBA,ABBA結合律(AB)CA(BC),(AB)CA(BC)分配律A(BC)(AB)(AC),A(BC)(AB)(AC)德摩根律(AB)AB

(AB)AB吸收律A(AB)A,A(AB)A36基本等價公式(1/2)雙重否定律AA36基本等價公式(2/2)零律A11,A00同一律A0A.A1A排中律AA1矛盾律AA0蘊涵等值式ABAB等價等值式AB(AB)(BA)假言易位ABBA等價否定等值式ABAB歸謬論(AB)(AB)A特別提示：必須牢記這16組等值式，這是繼續(xù)學習的基礎37基本等價公式(2/2)零律等價演算1.等值演算——由已知的等值式推演出新的等值式的過程2.等值演算的基礎：(1)等值關系的性質：自反性、對稱性、傳遞性(2)基本的等值式(3)置換規(guī)則（關于如何應用16組基本等價公式）38等價演算1.等值演算——由已知的等值式推演出新的等值式的過置換規(guī)則定義1-4.3如果A是合式公式(A)的一部分，且A本身也是一個合式公式，則稱A為合式公式(A)的子公式。定理1-4.1（置換規(guī)則P17定理1.3.3）設(A)是含公式A的命題公式（A為(A)的子公式），(B)是用公式B置換(A)中所有的A后得到的命題公式；若BA，則(B)(A)。39置換規(guī)則定義1-4.3如果A是合式公式(A)的一部分，且等值演算的應用舉例(1/2)證明兩個公式等值例2證明p(qr)(pq)r證p(qr)

p(qr)（蘊涵等值式，置換規(guī)則）(pq)r（結合律，置換規(guī)則）

(pq)r（德摩根律，置換規(guī)則）(pq)r（蘊涵等值式，置換規(guī)則）注：可在注明中省去置換規(guī)則思考：可否用等值演算直接證明兩個公式不等值？40等值演算的應用舉例(1/2)證明兩個公式等值40證明兩個公式不等值例3證明p(qr)與(pq)r不等值證方法一真值表法方法二觀察法.觀察到000,010是左邊的成真賦值，是右邊的成假賦值方法三先用等值演算化簡公式，然后再觀察p(qr)pqr(pq)r(pq)r(pq)r

更容易看出前面的兩個賦值分別是左邊的成真賦值和右邊的成假賦值等值演算的應用舉例(2/2)41證明兩個公式不等值等值演算的應用舉例(2/2)41作業(yè)復習本次課的內容作業(yè)本：P45的4,5；P45的7；P46:8的(4)(6)。預習下次課內容:蘊含式42作業(yè)復習本次課的內容42第三講蘊含式上一講主要內容回顧：賦值（解釋）、成真賦值、成假賦值；真值表、重言式、矛盾式、可滿足式；等價公式（兩種定義）、16組基本等價關系；子公式、置換規(guī)則。第三講主要內容1-5蘊含式43第三講蘊含式上一講主要內容回顧：43判斷公式類型:A為矛盾式當且僅當A0A為重言式當且僅當A1例4用等值演算法判斷下列公式的類型(1)q(pq)(2)(pq)(qp)(3)((pq)(pq))r)等值演算判斷公式類型(1/2)解(1)q(pq)

q(pq)（蘊涵等值式）

q(pq)（德摩根律）

p(qq)（交換律，結合律）

p0（矛盾律）

0（零律）矛盾式44判斷公式類型:A為矛盾式當且僅當A0等值演算判斷公式判斷公式類型(2/2)(2)(pq)(qp)

(pq)(qp)（蘊涵等值式）

(pq)(pq)（交換律）

1重言式(3)((pq)(pq))r)

(p(qq))r（分配律）

p1r（排中律）

pr（同一律）可滿足式，存在啞元，101和111是成真賦值，其它都是成假賦值.

45判斷公式類型(2/2)(2)(pq)(qp)(重言式的性質定理1-5.1任何兩個重言式的合取或析取，仍然是一個重言式。定理1-5.2一個重言式，對同一分量（命題變量）都用任何的同一個合式公式置換，其結果仍為一重言式。（代入規(guī)則，注意與置換規(guī)則的比較）思考：1、舉出與定理對應的例子。2、矛盾式的情況？3、可滿足式的情況？46重言式的性質定理1-5.1任何兩個重言式的合取或析取，仍蘊含式定義a設P，Q是兩個公式。稱Q是P的邏輯結果(或稱P蘊涵Q)，當且僅當對P，Q的任意解釋I，如果I滿足P，則I也滿足Q，記作PQ。定義b

當且僅當PQ是一個重言式時，我們稱“P蘊含Q”，并記作PQ。注意：1、PQ不是對稱式2、和的區(qū)別逆換式：QP，反換式：P

Q，逆反式：Q

P由真值表可見：PQ

Q

P QPP

Q即：條件命題公式與其逆反式是等價的。47蘊含式定義a設P，Q是兩個公式。稱Q是P的邏輯結果(或稱蘊含式的證明方法根據真值表：要證PQ，只需證對于任意的P的成真賦值I，I也是Q的成真賦值。根據蘊含式定義：要證PQ，只需證PQ是重言式。對于PQ來說，只有P的真值取1，Q的真值取0這樣一種指派時，PQ的真值為0。（破壞該條件）證明PQ是重言式方法：證法一：假設前件P為1時，導出后件Q為1(前真看后真)。證法二：假設后件Q為0時，前件P為0(后假看前假)

。48蘊含式的證明方法根據真值表：要證PQ，只需證對于任意的練習：推證┐Q∧(P→Q）┐P證法2(后假看前假)

假定┐P為F，則P為T。(a）：若Q為F，則P→Q為F，┐Q∧(P→Q）為F。(b）：若Q為T，則┐Q為F，┐Q∧(P→Q）為F。所以┐Q∧(P→Q)┐P成立。證法1(前真看后真)假定┐Q∧(P→Q）為T，則┐Q為T，且(P→Q）為T。由Q為F，則必須P為F，故┐P為T。49練習：推證┐Q∧(P→Q）┐P證法2(后多前提蘊含設G1,…,Gn，H是公式，稱H是G1,…,Gn的邏輯結果(或稱G1,…,Gn共同蘊涵H)，當且僅當公式G1…Gn蘊涵H；G1,…,Gn共同蘊涵H記為：G1,…,GnH。顯然，公式H是G1,…,Gn的邏輯結果的充要條件是：公式((G1…Gn)H)是恒真的。例如，P，PQ共同蘊涵Q。定理：如果H1，…，Hm，P共同蘊涵公式Q，則H1，…，Hm共同蘊涵公式PQ。例如，因為公式PQ，QR，P共同蘊涵R，所以PQ，QR共同蘊涵PR。50多前提蘊含設G1,…,Gn，H是公式，稱H是G1,…證明：(1)因為(H1…HmP)Q，所以公式(H1…HmP)Q是恒真的。(2)利用下面的基本等價公式：

P1(P2P3)(P1P2)P3(3)于是，(H1…HmP)Q=(H1…Hm)(PQ)。故(H1…Hm)(PQ)是恒真的。(4)結論：H1，…，Hm共同蘊涵PQ。定理證明51證明：定理證明51基本蘊含式PQPPQQPPQQPQP(PQ)Q(PQ)(PQ)P(PQ)QP，QPQP，PQQP，PQQQ，PQPPQ，QRPRPQ，PR，QRR52基本蘊含式PQP(PQ)Q52蘊含式－性質1定理1-5.4設P、Q為任意兩個命題公式，PQ的充分必要條件是PQ且QP。思考和總結：兩個命題公式等價的證明方法有哪些？1、真值表法；2、對基本等價公式使用置換規(guī)則；3、從重言式出發(fā)使用代入規(guī)則；4、分別證明PQ且QP；5、……53蘊含式－性質1定理1-5.4設P、Q為任意兩個命題公式，P蘊含式－性質2蘊含的常用性質：（1）設A、B、C為合式公式，若AB且A是重言式，則B必是重言式。（2）若AB，BC，則AC，即蘊含關系是傳遞的。（3）若AB，且AC，那末A(BC)。（4）若AB，CB，則(AC)B。54蘊含式－性質2蘊含的常用性質：54多前提蘊含的證明方法若給出前提集合S={G1，…，Gk}，公式G，證明SG的方法如下：原理：根據一些基本等價式和基本蘊涵式，從S出發(fā)，演繹出G，在演繹過程中遵循以下三條規(guī)則：規(guī)則1.可隨便使用前提(P規(guī)則)。規(guī)則2.可隨便使用前面演繹出的某些公式的邏輯結果(T規(guī)則)。規(guī)則3.

如果需要演繹出的公式是PQ的形式，則我們可將P做為附加前提使用，而力圖去演繹出Q。(CP規(guī)則)55多前提蘊含的證明方法若給出前提集合S={G1，…，Gk}多前提蘊含的證明例子例：證明{P(QS)，RP，Q}RS RP 規(guī)則1 R 規(guī)則3 P 規(guī)則2，由1,2根據10 P(QS) 規(guī)則1 QS 規(guī)則2，由3,4根據11 Q 規(guī)則1 S 規(guī)則2，由5,6根據11 RS 規(guī)則3，根據2,756多前提蘊含的證明例子例：證明{P(QS)，RP，Q}回顧1-6其他聯結詞回顧4種次重要聯結詞：、、c57回顧1-6其他聯結詞、c57真值函數定義{0,1}上的n元函數0:{0,1}n{0,1}稱為n元真值函數.4個一元真值函數確定了4個不等價的命題公式；真值函數確定了所需的聯結詞的個數；一元真值函數確定了只需要一個一元算子。一元真值函數

p

000111010158真值函數定義{0,1}上的n元函數0:{0,1}n{0二元真值函數PQ聯結詞1聯結詞2聯結詞3聯結詞4聯結詞5聯結詞6聯結詞7聯結詞8聯結詞9聯結詞10聯結詞11聯結詞12聯結詞13聯結詞14聯結詞15聯結詞1611101100101010101010101001011001011001100110011010010100100011010110101010PQ?P?QP∧QP∨QP→QP?QQ→P10PQ?P?QP∧QP↑QP∨QP↓QP→QPQP?QPQQ→PQPcc由表可見只需要九個聯結詞。59二元真值函數PQ聯結詞1聯結詞2聯結詞3聯結詞4聯結詞5聯結二元真值函數pq00011011

00000000000011110011001101010101pq00011011111111110000111100110011010101012元真值函數按序排列60二元真值函數pq0000公式與真值函數任何一個含n個命題變項的命題公式A都對應惟一的一個n元真值函數F,F恰好為A的真值表.等值的公式對應的真值函數相同.例如：pq,pq都對應61公式與真值函數任何一個含n個命題變項的命題公式A都對應惟一的聯結詞完備集定義

設S是一個聯結詞集合，如果任何n(n1)元真值函數都可以由僅含S中的聯結詞構成的公式表示，則稱S是聯結詞完備集.若S是聯結詞完備集,則任何命題公式都可由S中的聯結詞表示.62聯結詞完備集定義設S是一個聯結詞集合，如果任何n(n1)極小聯結詞完備集由(PQ)(PQ)(QP)，故可把包含的公式等價變換為包含和的公式。由PQPQ，說明包含“”的公式可以變換為包含“”和“”的公式。由PQ(PQ)，PQ(PQ)。故由“

”這五個聯結詞組成的命題公式，必可由{，}或{，}組成的命題公式等價置換。一個聯結詞完備集中，若不包含冗余的聯結詞，則稱該集合為一個極小聯結詞完備集。63極小聯結詞完備集由(PQ)(PQ)(Q其他聯結詞對于其他聯結詞，有下列性質：PQ

(PQ)PQ

(PQ)PQ

(PQ)PQ

(PQ)結論：S={,,}是聯結詞完備集c64其他聯結詞對于其他聯結詞，有下列性質：c64聯結詞完備集思考判斷以下是否是聯結詞完備集？(1)S1={,,,}(2)S2={,,,,}(3)S3={,}(4)S4={,}(5)S5={,}證明(1),(2)在聯結詞完備集中加入新的聯結詞后仍為完備集(3)AB

(AB)(4)AB

(AB)(5)ABAB{,,,}不是聯結詞完備集,0不能用它表示它的子集{},{},{},{},{,},{,,}等都不是65聯結詞完備集思考判斷以下是否是聯結詞完備集？{,,,極小完備集定理2.7{}與{}為聯結詞完備集.證明{,,}為完備集p

pp

(pp)

pp

pq

(pq)

pq

(pp)(qq)pq

(pq)

(pq)(pq)(pq)得證{}為聯結詞完備集.對{}類似可證結論：任意命題公式都可由僅包含｛，∨｝或｛，∧｝的命題公式等價代換。｛，∨｝或｛，∧｝為極小完備集。極小完備集亦可為｛｝或｛｝。66極小完備集定理2.7{}與{}為聯結詞完備集.66第一章數理邏輯1-7對偶與范式671-7對偶命題公式中僅含有｛、∨、∧｝中的聯結詞觀察教材p16，表1-22等價公式聯結詞符號的特征，找出規(guī)律。如：分配律P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)67第一章數理邏輯671-7對偶命題公式中僅含有｛、∨、∧對偶式定義：1-7.1在給定的命題公式中（僅含有、∨、∧三種聯結詞），將聯結詞換成，將換成，若有特殊變元0和1亦互相取代，所得公式A*稱為A的對偶公式。顯然，A也是A*的對偶式。求對偶式的方法：先化為僅含有、∨、∧三種聯結詞的公式；按定義依次完全替換。68對偶式定義：1-7.1在給定的命題公式中（僅含有、∨、∧第一章數理邏輯1-7對偶與范式69對偶－舉例例題:寫出下列表達式的對偶式(PQ)(P(QS))(PQ)R(PQ)1PQPQPQQR?(PQ)?(PQ)69第一章數理邏輯69對偶－舉例例題:寫出下列表達式的對偶式第一章數理邏輯1-7對偶與范式70對偶－德摩根律的普遍形式定理1-7.1：設A和A*是對偶式，P1,P2,…,Pn是出現在A和A*中的原子變元，則?A(P1,P2,…,Pn)?A*(?P1,?P2,…,?Pn)A(?P1,?P2,…,?Pn)??A*(P1,P2,…,Pn)3種關系：整個公式的否定式；對偶式；內否式；70第一章數理邏輯70對偶－德摩根律的普遍形式定理1-7.1：第一章數理邏輯1-7對偶與范式71德摩根律的普遍形式（驗證）例題3設A*(S,W,R)是S(WR)驗證A*(S,W,R)A(S,W,R)對偶式的重要應用：求公式的否定；思考：若A是重言式，A*？71第一章數理邏輯71德摩根律的普遍形式（驗證）例題3設A*第一章數理邏輯1-7對偶與范式72對偶定理定理1-7.2設P1,P2,…,Pn是出現在公式A和B中的所有原子變元，如果A?B，則A*?B*。證明：因為A?B，即A(P1,P2,…Pn)?B(P1,P2,…,Pn)是一個重言式，故A(?P1,?P2,…,?Pn)?B(?P1,?P2,…,?Pn)也是一個重言式。即A(?P1,?P2,…?Pn)?B(?P1,?P2,…,?Pn)由定理1-7.1得?A*(P1,P2,…,Pn)??B*(P1,P2,…,Pn)因此A*?B*再次觀察教材p16，表1-22等價公式。72第一章數理邏輯72對偶定理定理1-7.2設P1,P2,相容概念定義1-8.2假設公式H1,H2,…,Hm中的命題變元為P1,P2,…,Pn, 對于P1,P2,…,Pn的一些真值指派，如果能使H1∧H2∧…∧Hm的真值為T，則稱公式H1,H2,…,Hm是相容的。 如果對于P1,P2,…,Pn的每一組真值指派，H1∧H2∧…∧Hm的真值均為F，則稱公式H1,H2,…,Hm是不相容的。73相容概念定義1-8.2假設公式H1,H2,…,Hm中的命題間接證法－反證法要證H1∧H2∧…∧Hm?C，設H1∧H2∧…∧Hm為S，即證S?CSC為重言式（永真式）即證?C?S永為真，即證C∨?S為永真，C∨?S(?C∧S)即證?C∧S為永假。因此要證明H1∧H2∧…∧Hm?C，只要證明H1,H2,…,Hm與?C是不相容的。例題3證明AB,?(B∨C)可邏輯推出?A74間接證法－反證法要證H1∧H2∧…∧Hm?C，設H1∧H2∧作業(yè)（1）復習本章的內容，自學“范式”長假過后第一次單元考試，重點：真值表、等價公式；重言式、蘊含式；對偶；范式作為附加題。75作業(yè)（1）復習本章的內容，自學“范式”75作業(yè)（2）為了順序地促進云南省移動互聯網協會的成立，請各位老師（通知一下你教的本科班學生，作為一個必教的課后作業(yè)），博士生，碩士生，每一個人提交一份作業(yè)，作業(yè)的內容是關于運行在手機上的一個應用的設想。這個手機平臺上的應用，應該能夠方便人們的生活，如交通路線查詢，學校課程及上課教室查詢等（不能是游戲）。內容可以不要求很詳細，A4一張紙就可以了，紙質和電子版各一份。76作業(yè)（2）為了順序地促進云南省移動互聯網協會的成立，請各位老第五講范式引子畫出教材P23例1.4.5的真值表，并仔細研究其賦值情況77第五講范式引子771-7析取范式與合取范式基本概念(1)文字——命題變項及其否定的總稱(2)簡單析取式（析取項）——有限個文字構成的析取式p,q,pq,pqr,…(3)簡單合取式（合取項）——有限個文字構成的合取式p,q,pq,pqr,…(4)析取范式——由有限個簡單合取式組成的析取式

p,pq,pq,(pq)(pqr)(qr)(5)合取范式——由有限個簡單析取式組成的合取式

p,pq,pq,(pqp(pqr)(6)范式（NF）——析取范式與合取范式的總稱781-7析取范式與合取范式基本概念78范式概念兩類特殊情況說明：單個文字既是簡單析取式，又是簡單合取式形如pqr,pqr的公式既是析取范式，又是合取范式79范式概念兩類特殊情況說明：79范式的性質定理1(1)一個簡單析取式是重言式當且僅當它同時含有某個命題變項和它的否定式.(2)一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項和它的否定式.定理2(1)一個析取范式是矛盾式當且僅當它每個簡單合取式都是矛盾式.(2)一個合取范式是重言式當且僅當它的每個簡單析取式都是重言式.80范式的性質定理1(1)一個簡單析取式是重言式當且僅當它同命題公式的范式定理3（范式存在定理）任何命題公式都存在與之等值的析取范式與合取范式。公式A的析取(合取)范式與A等值的析取(合取)范式求公式A的范式的步驟：(1)消去A中的,（若存在）ABAB

AB(AB)(AB)

(2)否定聯結詞的內移或消去AA(AB)AB

(AB)AB81命題公式的范式定理3（范式存在定理）81命題公式的范式(3)使用分配律A(BC)(AB)(AC)求合取范式

A(BC)(AB)(AC)求析取范式82命題公式的范式(3)使用分配律82求公式的范式例

求下列公式的析取范式與合取范式

(1)(pq)r(2)(pq)r解(1)(pq)r(pq)r（消去）

pqr（結合律）最后結果既是析取范式(由3個簡單合取式組成的析取式)，又是合取范式(由一個簡單析取式組成的合取式)83求公式的范式例求下列公式的析取范式與合取范式83(2)(pq)r(pq)r（消去第一個）

(pq)r（消去第二個）(pq)r（否定號內移——德摩根律)析取范式(pr)(qr)（對分配律）合取范式例

求公式的合取范式：p(p(qr))公式范式的不足？不惟一不能直觀反映真值表的情況解決方法：進一步規(guī)范化主范式求公式的范式84(2)(pq)r求公式的范式84極小項與極大項定義在含有n個命題變項的簡單合取式（簡單析取式）中，若每個命題變項均以文字的形式在其中出現且僅出現一次，而且第i個文字出現在左起第i位上（1in），稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.幾點說明：n個命題變項有2n個極小項和2n個極大項2n個極小項（極大項）均互不等值用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示.用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示.（mi（Mi）稱為極小項（極大項）的名稱.）85極小項與極大項定義在含有n個命題變項的簡單合取式（簡單析取觀察由兩個命題變項p,q形成的極小項與極大項極小項極大項公式成真賦值名稱公式成假賦值名稱pqpqpqpq

00011011m0m1m2m3

pq

pqpqpq

00011011M0M1M2M386觀察由兩個命題變項p,q形成的極小項與極大項極小項極大實例極小項極大項公式成真賦值名稱公式成假賦值名稱pqrpq

rpq

rpq

rpqrpq

rpq

rpq

r000001010011100101110111m0m1m2m3m4m5m6m7

p

q

r

p

q

r

p

q

r

p

qrp

q

rp

q

rp

q

rp

qr000001010011100101110111M0M1M2M3M4M5M6M7由三個命題變項p,q,r形成的極小項與極大項.mi與Mi的關系？思考P29定理1.4.6

mi

Mi,Mi

mi

87實例極小項極大項公式成真賦值名稱公式成假賦值名稱pq主析取范式與主合取范式主析取范式——由極小項構成的析取范式主合取范式——由極大項構成的合取范式例如，n=3,命題變項為p,q,r時，(pqr)(pqr)

m1m3——主析取范式(pqr)(pqr)

M1M7——主合取范式公式A的主析取(合取)范式——與A等值的主析取(合取)范式定理(主范式的存在惟一定理)任何命題公式都存在與之等值的主析取范式和主合取范式,并且是惟一的（如果命題變元的順序固定）88主析取范式與主合取范式主析取范式——由極小項構成的析取范式8求公式主范式的步驟求公式主析取范式的步驟:設公式A含命題變項p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是簡單合取式j=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成BjBj(pipi)(Bjpi)(Bjpi)重復這個過程,直到所有簡單合取式都是長度為n的極小項為止(3)消去重復出現的極小項,即用mi代替mimi(4)將極小項按下標從小到大排列89求公式主范式的步驟求公式主析取范式的步驟:89求公式主范式的步驟求公式的主合取范式的步驟:設公式A含命題變項p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是簡單析取式j=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成BjBj(pipi)(Bjpi)(Bjpi)重復這個過程,直到所有簡單析取式都是長度為n的極大項為止(3)消去重復出現的極大項,即用Mi代替MiMi(4)將極大項按下標從小到大排列90求公式主范式的步驟求公式的主合取范式的步驟:90實例例6(1)求公式A=(pq)r的主析取范式和主合取范式解(pq)r

(pq)r（析取范式）①(pq)

(pq)(rr)(pqr)(pqr)

m6m7②r(pp)(qq)r

(pqr)(pqr)(pqr)(pqr)

m1m3m5m7③②,③代入①并排序，得(pq)r

m1m3m5

m6m7（主析取范式）91實例例6(1)求公式A=(pq)r的主析取范式實例(pq)r(pr)(qr)（合取范式）④

pr

p(qq)r

(pqr)(pqr)

M0M2⑤

qr

(pp)qr

(pqr)(pqr)

M0M4

⑥

⑤,⑥代入④并排序，得(pq)r

M0M2M4（主合取范式）92實例(pq)r92由主析取范式確定主合取范式例設A有3個命題變項,且已知A=m1m3m7,求A的主合取范式.解A的成真賦值是1,3,7的二進制表示,成假賦值是在主析取范式中沒有出現的極小項的下角標0,2,4,5,6的二進制表示,它們恰好是A的主合取范式的極大項的下角標,故

AM0M2M4M5M6用成真賦值和成假賦值確定主范式由主合取范式確定主析取范式用真值表確定主范式93由主析取范式確定主合取范式用成真賦值和成假賦值確定主范式由主G=(PQ)(PR)(QR)PQRG0

00000110

10001111000101011011111主析取范式：(PQR)(PQR)(PQR)(PQR)

主合取范式：

(PQR)(PQR)(PQR)(PQR)94G=(PQ)(PR)(QR)PQRG0000主范式的應用1.求公式的成真成假賦值設公式A含n個命題變項,A的主析取范式有s個極小項,則A有s個成真賦值,它們是極小項下標的二進制表示,其余2n-s個賦值都是成假賦值例如(pq)r

m1m3m5

m6m7成真賦值為001,011,101,110,111，成假賦值為000,010,100.類似地，由主合取范式也立即求出成假賦值和成真賦值.95主范式的應用1.求公式的成真成假賦值952.判斷公式的類型

設A含n個命題變項.A為重言式

A的主析取范式含全部2n個極小項

A的主合取范式不含任何極大項,記為1.A為矛盾式A的主合取范式含全部2n個極大項

A的主析取范式不含任何極小項,記為0.A為非重言式的可滿足式

A的主析取范式中至少含一個、但不是全部極小項

A的主合取范式中至少含一個、但不是全部極大項.主范式的應用962.判斷公式的類型主范式的應用96例用主析取范式判斷公式的類型:(1)A

(pq)q(2)B

p(pq)(3)C(pq)r解(1)A

(

pq)q(pq)q0矛盾式(2)B

p(pq)1m0m1m2m3

重言式(3)C(pq)r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3m5m7

非重言式的可滿足式主范式的應用97例用主析取范式判斷公式的類型:主范式的應用973.判斷兩個公式是否等值例用主析取范式判以下每一組公式是否等值⑴p(qr)與(pq)r⑵p(qr)與(pq