第三章.命題邏輯

離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院第三章輯重點(diǎn)掌和公式轉(zhuǎn)換方式求公式的主析取范式和主合取范式；利用規(guī)則、基本等價(jià)和蘊(yùn)涵公式、三種不同的推理方法完成命題邏輯推理；難點(diǎn)如題。他算人工能要更用學(xué)。詞掌邏邏。3.1 命題符號(hào)化及聯(lián)系結(jié)詞1命題切陳稱。謂切是在體境具時(shí)，體象具的等況下一的分：(1簡單命題：不能分解為更為簡單的句子的命題。(2復(fù)合命題：能夠分解為更為簡單的命題。2詞 P P并且Q析取 P或者Q

P 乛PP與Q的合取P∧QP與Q的析取P∨Q

乛P當(dāng)PP∧Q為真當(dāng)且僅當(dāng)P，Q同為真P∨Q為真當(dāng)且僅當(dāng)P，Q至少一個(gè)為蘊(yùn)涵 若P，則Q P蘊(yùn)涵Q P→Q P→Q為假當(dāng)且僅當(dāng)P為真，Q為假等價(jià) P當(dāng)且僅當(dāng)QP等價(jià)于Q P←→P→Q為真當(dāng)縣僅當(dāng)P，Q同為真假Q(mào)－3.1－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院詞要：（1）此詞結(jié)句句間聯(lián)而單名、容數(shù)詞等聯(lián)結(jié)；（2）此聯(lián)結(jié)詞兩子值的結(jié)而句具含聯(lián)，子以在；（3）聯(lián)與語之對(duì)非一，合結(jié)∧對(duì)自然語言中的“既??又??“不僅??而且??“雖然??但是??“并且“和、”蘊(yùn)詞PQ對(duì)加P則Q“只要P就Q，P當(dāng)Q“只有Q才P非Q則乛P”“→”對(duì)應(yīng)自語且必或中或。3.2 題式分類一般稱具有確切真值的簡單命題叫命題常量，用P，Q，R，?等表示。而沒有賦予具體內(nèi)容為元的P，R沒有具體的真值。1式（1）單個(gè)含1或0）是合式公式；（2若P是合式公乛P）也是合式；Q（3若PQPQPQPQP→。Q“”次的公?！薄皝^””“→”“””中為錯(cuò)，取取成等先別改或調(diào)先別，，同運(yùn)。2解表設(shè)G是命題公式，P1，P2，?，Pn(n1)是出現(xiàn)在公式G定P1，P2，?，Pn一組真值，則這組真值稱為G的一個(gè)解釋或賦值。此時(shí)不同的賦值就有2n種。將此2n種為G。3公類設(shè)G為一，（1如G在它所稱G為永真；（2如G在它所稱G矛；－3.2－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院（3如G在稱G滿。3.3 公算1系稱公式GH是等價(jià)的，如果在其任意的解釋下，為G=H。說明H式GH之G=H是公它接。要判斷GH，可H式GH是一個(gè)永真式。2．代入定理設(shè)P，P，，P任意公式，若G是永真式或永假式，則用G1，G2，?，Gn取代公式G的后而得的新公式G(G1，?，Gn)＝G’(P1，P2，?Pn)仍是一個(gè)永真式或永假式。3律設(shè)是：（1）冪∨GG＝G（3）交∨HG∧HG（5）吸GGGGG（6）同∨=G1=G(，1元)（7零：∨11∧0001分別是關(guān)于運(yùn)算∨元)（8）排乛G=1∧0=0乛G又做G元)（9，M律：乛G=乛G∧乛H乛G=乛G乛H（10）乛G＝G（：乛G∨H（12）等價(jià)等式G→HGH）∧→乛GH乛HG）（13）G乛H乛G（4）等價(jià)否GH＝乛G乛H（15：GH)∧乛H)乛G其中：要運(yùn)““”應(yīng)運(yùn)，－3.3－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院真值1“0應(yīng)集合中的全集E和空集律(1～(10)(1～(10).外～(15式,重住.4算利用等值定而的。5則設(shè)GG1)是含式G1的公GG2)用G2了GG1)的若G1＝G2，則G(G1)GG2)3.4 功聯(lián)結(jié)集1其詞表P QU30 00 11 01 U3

2UU1U2U4設(shè)PQU為其對(duì)應(yīng)的聯(lián)結(jié)則U作用于PQ后的表22。由組的義U，U2U3U4不有24＝16種，從0000到，為此除已有的五個(gè)聯(lián)結(jié)詞以外，還需引入下面四個(gè)聯(lián)結(jié)詞如表23所。表中，中非。2合設(shè)S用S從S除個(gè)聯(lián)結(jié)詞后結(jié)合S1，至少用S1中聯(lián)結(jié)示稱S。－3.4－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院表3詞號(hào) 題 法 法 果或 G或H G異或GHH

AH為真當(dāng)僅當(dāng).H不同為真假蘊(yùn)涵否定 G與H的蘊(yùn)涵否定G蘊(yùn)涵否定GHH

GH當(dāng)G，H為假非 ↑ G與H非G非H ↑H或非 ↓ G與H的或非G或非H ↓H

↑H為假當(dāng)且僅當(dāng),H同為真↓H為真當(dāng)且僅當(dāng)，H同為假3.5 式.式()命否；()限?。?)限??；()限為；()限為。求一式G。.式()有n元P1,P2,?,Pn括所有這n個(gè)命題與P1,P2,?,Pn于P1,P2,?,Pn的有2n，大也有2n；()由有限個(gè)極小項(xiàng)組成的析取范式稱為主析取范；()由有限個(gè)極大項(xiàng)組成的合取范式稱為主合取范。求個(gè)公式G演是真值表技術(shù)。該方法為：設(shè)GP1,P,?,P式對(duì)。()在真式G取值為真的所有行所析式G主取式。()在真式G取值為假的所有行所合式G的主如P為乛P，－3.5－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院如P值取原為1如R為00乛P乛Q乛極對(duì)如P取值為P，如P值1，在極為0如R為0乛P∧乛QR。3理()一等范；()任一命主；()如果一個(gè)命式它無主或空；()如果一個(gè)命式它無主或空；()兩個(gè)的；()任一公式對(duì)應(yīng)主析取范式包括的極小項(xiàng)的個(gè)數(shù)加對(duì)應(yīng)主合取范式包括的極大項(xiàng)的個(gè)為2。3.6 理論.推理的形式構(gòu)設(shè)G1,G2,?,G，H是題，稱G1∧G2∧?∧Gn→H為推中G1,G2,?,GnH為結(jié)論當(dāng)G1∧G2∧?∧Gn→H為永真稱G1,G2,?,Gn涵H是G1,G2,?,Gn輯，并且記為G1∧G2∧?∧GnH或記為G1,G2,?,GnH。說明G1,G2,?,GH僅述式G1,G2,?,Gn與公式H之間的邏輯，G1,G2,?,GH本。要判斷G1,G2,?,GH采：G1,G2,?,GH當(dāng)且僅當(dāng)G1∧G2∧?∧Gn→H是一個(gè)永真公式。.判法()真值表法：利用真值表法，可建立如下推理：設(shè)GHS：①附加HHGH②化簡∧GGH③合，GH－3.6－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院④假言，HH⑤拒GH，乛乛G⑥析取GH乛GH⑦假言GHH→S→S⑧二難∨GSH→S⑨等價(jià)?HHSG?S()等值演算法；()法；()構(gòu)造證明法。①推則P（前提引入合。規(guī)則則式S，式S的。規(guī)則加合P與公式P推導(dǎo)出從此前中P推導(dǎo)出P。②直接列C1,C2,?,其中C1,C2,?,Cn為應(yīng)規(guī)，Cn。③間接明G1,G2,?,GnH等價(jià)地證明G1,G2,?,G，乛H∧乛中RG1,G2,?,G,乛H∧乛R可采取直接證明方法。④帶P帶P規(guī)則的證明法主要是針對(duì)結(jié)論為P→或乛P∨S明G1,G2,?,GPS等明G1,G2,?,G，P，此時(shí)明G1,G2,?,G,PS時(shí)P為附論S，用P規(guī)則，即可由G1,?,Gn推出P→邏都是適用的，只是不同。3.7 結(jié)達(dá)：()要弄清命題與陳述句之間的關(guān)系與差別。命題都是陳述句；但陳述句不一定都結(jié)；－3.7－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院()用6聯(lián)（，，，?）來合題進(jìn)行翻譯及判斷真值；()記住24；()會(huì)利用真值表技術(shù)和公式的演算方法求一公式所對(duì)應(yīng)的主析取范式和主合取范滿；()握的。例題精選例3.1 設(shè)P表命下Q表R表命“乘公共車班大1995考：（1）；（2）；（3）；（4）。析對(duì)于要Q才P要P就Q非Q則P等成PQ，以述(1(2)()Q→乛P乛P→Q(3)乛Q→P子4)可翻譯為Q例3.2 ()項(xiàng)R式（R乛（R(乛乛乛R)（2）求（式（R）的主合取范式北大2001試。7(aM)0解(1)設(shè)=i 0中a1于R的。則乛=i01)Mi乛=a0M4∧a1M5∧a2M6∧a3M7∧a4M∧a5M∧a6M2∧a7M3,乛Q,R)=a0M2∧a1M3∧a2M0∧a3M1∧a4M∧a5M∧a6M1∧a7M2乛R)=a0M1∧a1M0∧a2M3∧a3M2∧a4M∧a5M∧a6M7∧a7M6由乛(乛,乛乛)項(xiàng)應(yīng)此：1a0)=a4=a2=a，(1a4)=a0=a6=a51a1)=a5=a3=a，(1a5)=a1=a7=a41a2)=a6=a0=a，(1a6)=a2=a4=a71a3)=a7=a1=a，(1a7)=a3=a5=a6所以a0=a3=a=a6a1=a2=a=a7－3.8－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院如令則此時(shí)M1∧M∧M4∧M=乛乛M乛M乛M乛M7)=乛乛P∨乛R)乛P乛Q∨R)乛(乛P∨R∨乛乛P乛Q乛R))令則此時(shí)M0∧M∧M5∧M=乛乛M0乛M3乛M乛M6=乛乛P∨Q∨R∨乛P乛Q乛R∨乛乛P∨乛R∨乛乛P乛QR)))M1∧M∧M4∧M=(P∨Q乛R∧乛P乛QR)∨乛P∨QR)∨乛P乛Q∨乛R)?主合取范式=M0∧M3∧M∧M6=(P∨R)∧P乛Q乛R∧(乛PQ乛R∧乛P∨乛Q∨R)?主合取范式例33 題P：明天上午下雨Q：明天雪R：我將去學(xué)校列：（1）；（2）；（3）；（4）。析根命題PQ的定義，它可對(duì)應(yīng)語句除非Q，乛P；只要P就Q；有Q才P。（12（可分別對(duì)應(yīng)符：（1R→（乛P乛Q）（2乛P∨乛Q→R（3RPQ）（氣，，4R該化：P（乛PQ）∨P乛Q）∨乛P∧乛Q）所句子4：P∧）∨乛P∧P∧乛Q）（乛P乛Q∧R或P∧R）∨乛P∧QRP乛QR）乛P乛Q）明由于雨雪無與R。－3.9－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院例3.4 求公式G1P，QR)PQ∧P)G2PQ)PQ)∧PQ)取取。析式G1G2元根據(jù)右公求的述公的式安采求。方法1 。建立式G1P，R)→Q∧PQ)表24。表24PQR (P→Q∧P∧Q)0 0 01 0 00 0 1 1 0 00 1 0 1 0 00 1 1 1 0 01 0 0 0 0 01 0 1 0 0 01 1 0 1 1 11 1 1 1 1 1則公式G1PQR)所對(duì)應(yīng)的主析取范式、主合取范分別為：G1（P，Q，R）（P∧Q∧乛R）∨（P∧Q∧R）?主析取范式G1PQRPQ∨P乛R∧P乛Q∨R)∧P乛Q乛)∧（乛P∨Q∨R）∧（乛P∨Q∨乛R）?主合取范式建立式G2PQ)PQ）∧PQ）的表．5。表25P Q PP）001 0 00 1 1 0 01 0 0 0 01 1 1 1 1則公式G2PQ)所對(duì)應(yīng)：G2（P，Q）=（P∧Q）?主析取范式G2（P，Q）=（P∨Q）∧（乛P∨Q）∧（P∨乛Q）?主合取范式方法2 。G1PQRP∧P∧Q乛P∨QPQPQP∧Q∧(乛R∨R)（P∧Q∧乛R）∨（P∧Q∧R）?主析取范式G1PQR）乛（乛G1P，R）乛（P乛Q∧R∨(乛P∧Q∧R∨P乛Q乛R)∨（乛P∧∧乛R）乛P乛QR乛P∧乛Q乛R）(乛P乛R)P乛Q乛R）∧（乛PQ∨∧(乛P∨R∧PQ乛P∨Q∨R）－30－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院(P∨QR)∧P∨乛R）∧P乛Q∨R）∧P乛Q乛∧(乛P∨Q∨R)∨（乛P∨Q∨乛R）?主合取范式22 2G（P，Q）（P→Q）∧（P∧Q）（乛P∨Q）∧P∧Q（P∧Q）?主析取范式GPQ）乛（乛GP，Q）（P乛Q)∨乛P∨Q∨(乛P乛Q22 2（乛PQ）∧P乛Q（P）（P∨Q）∧（乛P∨Q）∧（P∨乛Q）?主合取范式兩范。例35 ）（1P）→乛Q乛P）（2PQ）→PQ）北大200）解判斷一個(gè)公式是否是重方式、矛盾式，可滿足公式，可采用三種方式：(1)真值表技術(shù)；，主合取范式。下面分別采用三種方：方法1 。建立式(1)，表如表．6。表26P Q P）（乛Q→乛P）（P→Q）→乛PQ）001 1 1 1 1 10 1 1 1 1 0 1 01 0 0 1 0 0 1 01 1 1 1 1 1 0 0由上述真值可知，公式(1言，式足。方法2 。①PQ）乛Q乛PPQ）→乛P∨）乛（乛P（乛PQ1公永重。方法3 。P→Q）→乛PQ乛PQ）∨乛QPQ）（P）乛P∧乛Q）乛P乛QP）∨（乛P乛Q）（P∧乛Q）∨（乛P∧Q）∨（乛P∧乛Q）?主析取范式乛（乛PQ)乛(P∨Q)）乛（P∧Q）（乛P∨乛Q）?主合取范式對(duì)包式應(yīng)包是足。例36 符公一：（1）；（2）；（3）；（4）若王磊的；（5。計(jì)磊？－1－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院分析：設(shè)P：張計(jì)算；；；S：王磊的證詞正；T：午夜時(shí)燈。提號(hào)：PQP→乛RS→乛，乛S→，T證明的為P或Q。明（）TP（2S→乛TP（3乛S（4乛S→R（5R

T，(1)，(2)，IPT，(3)，(4)，I（6P→乛R P（7乛P T，(5)，(6)，I（8PQ P（9Q T，(7)，(8)，I說盜計(jì)。例3.7符號(hào)化下列命果6是偶數(shù)，則2不除7；或者5不是或2除7；5，6是數(shù)。解首先化設(shè)P6數(shù)：2除7：5數(shù)符為P→乛Q乛R∨Q，R乛P證明（）乛RQ P（2R（3Q（4P乛Q（5乛P

PT，(1)，(2)，IPT，(3)，(4)，I明但：的一誤不錯(cuò)該不邏的出結(jié)論。一在前如6是偶則2不能整除7它。例38 。（1）如果A考；（2）如果A；（3）如果A。（4A。－32－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院解：設(shè)PA；Q：他中；R；S：他讀了許多書。述號(hào)：P→乛Q，乛Q→乛R，→R乛P∨乛S明采用歸謬法就是將結(jié)論的否定作為附加前提加入到前提集合之中致條件矛盾。（1）乛P∨乛S）（2P∧S（3P（4S（5P乛Q（6乛Q（7SR（8R（9）乛Q乛R（10Q

P提)T，(1)，)EPPP（Q乛Q 所以，謬法知P→乛Q，乛Q→乛，S→R乛P∨乛。例9 為PP∨Q，PR，Q→S}GS∨R明PG。解。證法1。（1PQ（2乛P→Q（3→S（4乛P→S（5乛P（6PR（7乛→R（8SR

PT，(1)EPT，(4)EPT，(7)E法2帶P規(guī)。因GSR乛R，為乛S作為附加前提加入前提集合中，如能證明P，乛SR，則由P規(guī)則知：P乛→R即PS∨R。（1乛S（2→S（3乛Q（4PQ（5P（6PR（7R（8乛→R（9SR

P前提)PPPP，，(7)T，(8)E－33－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院證法3。（1）乛SR）（2乛乛R（3乛S（4乛R（5PR（6乛P（7→S（8乛Q（9乛P乛Q（10）乛P）（P∨Q（12P∨Q乛P∨)

P前提)T，(1)EPPT，(9)EP例3.0 明P→Q→S是P→QR)→(→的邏。析對(duì)題蘊(yùn)式)帶P規(guī)。（1P（2P（Q→）（3→R（4RQ→）（5→QS）（6Q（7→S（8P（Q→）

P前提)PPP前提)P，，(7)例1一入為ABC，為，，C，在同一時(shí)間內(nèi)按AC的輸，例如ABC能A出AC功集{↓中的表達(dá)式。解設(shè)PA輸入B入：C入由提出，，C的表表27。－34－離散數(shù)學(xué)講義 武漢技大計(jì)算學(xué)院表2.7P Q R A B C0000000 0 1 0 0 10 1 0 0 1 00 1 1 0 1 01 0 0 1 0 01 0 1 1 0 01 1 0 1 0 01 1 1 1 0 0表的分：AF（PQR）∨PQ乛R）∨P乛QR）P乛Q乛）P∧Q）（乛RP乛Q）∧乛R）PQP乛QP（乛Q）P∧1PA（P∨P）（PP）PPPP）BF＝（乛PQ乛R）∨乛PQR乛PQ）乛R∨R）乛P∧Q乛P∧Q）P乛Q）P乛QP（Q）BCF乛P乛Q∧）（PQ∧RP∧R乛乛PQ乛乛RP乛P乛R↓QPQ↓R）C例3.2 有3名隊(duì)員，有一天取得一塊礦