離散數(shù)學(xué)-第三章(上)

2023/2/2計算機應(yīng)用技術(shù)研究所11離散數(shù)學(xué)DiscreteMathematics

汪榮貴教授合肥工業(yè)大學(xué)計算機與信息學(xué)院2023/2/2計算機應(yīng)用技術(shù)研究所2第三章命題邏輯

（上）2023/2/2計算機應(yīng)用技術(shù)研究所3

命題邏輯（上）

邏輯與數(shù)理邏輯

命題與連接詞命題公式與真值表2023/2/2計算機應(yīng)用技術(shù)研究所4邏輯與數(shù)理邏輯2023/2/2計算機應(yīng)用技術(shù)研究所5邏輯與數(shù)理邏輯邏輯的基本知識

數(shù)理邏輯及其發(fā)展歷程邏輯與計算機2023/2/2計算機應(yīng)用技術(shù)研究所6邏輯學(xué)邏輯學(xué)--是一門研究思維形式和思維規(guī)律的科學(xué)，包含：辯證邏輯：研究人的思維中的辯證法。例如：用全面的和發(fā)展的觀點觀察事物；具體問題具體分析；實踐是檢查事物正誤的唯一標(biāo)準(zhǔn)；等等。形式邏輯：研究人的思維的形式和一般規(guī)律。本課程只關(guān)心形式邏輯。2023/2/2計算機應(yīng)用技術(shù)研究所7人類的思維規(guī)律人類的思維過程：通過學(xué)習(xí)掌握概念和判斷，然后進行推理，即：

概念判斷推理

推理：由若干個已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。正確的思維：概念清楚，判斷正確，推理合乎邏輯2023/2/2計算機應(yīng)用技術(shù)研究所8邏輯推理類比推理：由個別事實推出個別結(jié)論。如：地球上有空氣、水，地球上有生物?；鹦巧嫌锌諝?、水火星上有生物。歸納推理：由若干個別事實推出一般結(jié)論。如：銅能導(dǎo)電、鐵能導(dǎo)電、錫能導(dǎo)電、鉛能導(dǎo)電、……

一切金屬都導(dǎo)電。演繹推理：由一般規(guī)律推出個別事實。

2023/2/2計算機應(yīng)用技術(shù)研究所9邏輯推理實例公安人員審查一件盜竊案，已知的事實如下：甲或乙盜竊了錄音機；若甲盜竊者，則作案時間不會發(fā)生在午夜前；若乙的證詞正確，則午夜時屋里的燈光未滅；若乙的證詞不正確，則作案時間發(fā)生在午夜前；午夜時屋里的燈光滅了。問：盜竊者是誰？2023/2/2計算機應(yīng)用技術(shù)研究所10邏輯推理實例2023/2/2計算機應(yīng)用技術(shù)研究所11為何要學(xué)邏輯各門科學(xué)都是在特殊領(lǐng)域的思維推理活動,故邏輯是一切科學(xué)的公共基礎(chǔ).邏輯思維能力是學(xué)習(xí)、工作乃至日常生活中的重要能力.2023/2/2計算機應(yīng)用技術(shù)研究所12為何要學(xué)邏輯思維必須符合規(guī)律才不會導(dǎo)致謬妄.推理是獲得知識的一種途徑

2023/2/2計算機應(yīng)用技術(shù)研究所13邏輯與數(shù)理邏輯邏輯的基本知識數(shù)理邏輯及其發(fā)展歷程邏輯與計算機2023/2/2計算機應(yīng)用技術(shù)研究所14古典邏輯亞里士多德的三段論(syllogism)

從兩個前提推出一個結(jié)論的邏輯論證形式:

1.大前提(majorpremise)

人都是兩足動物

2.小前提(minorpremise)

希臘人都是人

3.結(jié)論(conclusion)

希臘人都是兩足動物2023/2/2計算機應(yīng)用技術(shù)研究所15古典邏輯斯多葛學(xué)派(Stoics)的命題邏輯

芝諾(ZenoofCitium)于301BC創(chuàng)立

克呂希波(Chrysippus)大大發(fā)展了Stoiclogic2023/2/2計算機應(yīng)用技術(shù)研究所16數(shù)理邏輯數(shù)理邏輯的創(chuàng)始人德國數(shù)學(xué)家萊布尼茨1646-1716英國數(shù)學(xué)家布爾1815-1864德國數(shù)學(xué)家弗雷格1848-19252023/2/2計算機應(yīng)用技術(shù)研究所17萊布尼茨GottfriedWilhelmLeibniz(1646-1716)

首先使用“數(shù)理邏輯”這個術(shù)語

Leibniz’sDream:把推理歸結(jié)為(符號)計算.提出“思維演算”的思想：

“發(fā)生爭論時我們可以簡單地說:讓我們計算一下吧,看誰正確.”2023/2/2計算機應(yīng)用技術(shù)研究所18

布爾GeorgeBoole(1815-1864)1847年的論文:

邏輯的數(shù)學(xué)分析:論演繹推理的演算法.

發(fā)明了布爾代數(shù)(邏輯代數(shù),命題代數(shù),布爾邏輯)，初步實現(xiàn)了Leibniz夢想。

布爾代數(shù)亦可解釋成集合代數(shù),開關(guān)代數(shù)，是計算機數(shù)字邏輯的基礎(chǔ)。附注:AugustusdeMorgan(1806-1871)幾乎同時獨立地做出重要貢獻(xiàn).2023/2/2計算機應(yīng)用技術(shù)研究所19弗雷格FriedrichLudwigGottlobFrege(1848-1925)1879年的重要著作：

概念文字:一種模仿算術(shù)語言構(gòu)造的純思維的形式語言是第一個公理化謂詞邏輯系統(tǒng)是自Aristotle以來邏輯的最重要進展基本實現(xiàn)了Leibniz夢想2023/2/2計算機應(yīng)用技術(shù)研究所20數(shù)理邏輯用數(shù)學(xué)方法研究演繹推理的一門數(shù)學(xué)學(xué)科數(shù)學(xué)方法——通過引進一整套形式化符號系統(tǒng)的方法。因此，數(shù)理邏輯有時候也稱為符號邏輯數(shù)理邏輯的構(gòu)成

——一套符號體系+一組運算規(guī)則2023/2/2計算機應(yīng)用技術(shù)研究所21數(shù)理邏輯數(shù)理邏輯的內(nèi)容：命題邏輯、謂詞邏輯、公理化集合論、遞歸論、模型論、證明論本課程只討論“命題邏輯”和“謂詞邏輯”2023/2/2計算機應(yīng)用技術(shù)研究所22命題邏輯命題邏輯也稱命題演算，或語句邏輯。研究內(nèi)容：（1）研究以命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系

（2）研究什么是命題？（3）研究如何表示命題？（4）研究如何由一組前提推導(dǎo)一些結(jié)論？2023/2/2計算機應(yīng)用技術(shù)研究所23邏輯與數(shù)理邏輯邏輯的基本知識數(shù)理邏輯及其發(fā)展歷程邏輯與計算機2023/2/2計算機應(yīng)用技術(shù)研究所24數(shù)理邏輯與軟件程序＝算法＋數(shù)據(jù)算法＝邏輯＋控制2023/2/2計算機應(yīng)用技術(shù)研究所25數(shù)理邏輯與硬件命題邏輯數(shù)字邏輯與門電路

計算機組成原理2023/2/2計算機應(yīng)用技術(shù)研究所26本節(jié)內(nèi)容到此結(jié)束謝謝大家！2023/2/2計算機應(yīng)用技術(shù)研究所27

命題邏輯（上）

邏輯與數(shù)理邏輯命題與連接詞命題公式與真值表2023/2/2計算機應(yīng)用技術(shù)研究所28命題與連接詞2023/2/2計算機應(yīng)用技術(shù)研究所29命題與聯(lián)結(jié)詞命題的概念命題的運算聯(lián)結(jié)詞命題的符合化與應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所30命題的概念命題是一個或真或假的陳述句，但不能既真又假。確定命題語句真值的幾點說明：

1、時間性

2、區(qū)域性

3、標(biāo)準(zhǔn)性2023/2/2計算機應(yīng)用技術(shù)研究所31命題的概念（1）太陽是圓的；（2）成都是一個旅游城市；（3）北京是中國的首都；（4）這個語句是假的；（5）1＋1＝10；（6）ｘ+y>０；（7）我喜歡踢足球；（8）3能被2整除；（9）地球外的星球上也有人；（10）中國是世界上人口最多的國家；2023/2/2計算機應(yīng)用技術(shù)研究所32命題的概念（12）把門關(guān)上；（13）滾出去?。?4）你要出去嗎？（15）今天天氣真好??！【注意】一切沒有判斷內(nèi)容的句子都不能作為命題，如命令句、感嘆句、疑問句、祈使句、二義性的陳述句等。2023/2/2計算機應(yīng)用技術(shù)研究所33命題的概念【結(jié)論】命題一定是陳述句，但并非一切陳述句都是命題。命題的真值有時可明確給出，有時還需要依靠環(huán)境、條件、時間、實際情況才能確定其真值。2023/2/2計算機應(yīng)用技術(shù)研究所34命題真值（TruthValues）的表示：真：T、1；假：F、0命題的符號表示：大寫英文字母：P、Q、R、…

帶下標(biāo)的大寫字母：A1、A2、A3、…

數(shù)字：［1］、［2］、［3］、…命題的概念2023/2/2計算機應(yīng)用技術(shù)研究所35簡單命題(原子命題)：由最簡單的陳述句構(gòu)成的命題(該句不能再分解成更簡單的句子)。

【例】2是個素數(shù)。

復(fù)合命題(分子命題)：由若干個原子命題構(gòu)成的命題。

【例】四川不是一個國家命題的概念2023/2/2計算機應(yīng)用技術(shù)研究所36命題與聯(lián)結(jié)詞命題的概念命題的運算聯(lián)結(jié)詞命題的符號化與應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所37命題運算聯(lián)結(jié)詞

命題可以通過邏輯聯(lián)結(jié)詞(邏輯運算)構(gòu)成新的命題——復(fù)合命題。復(fù)合命題的真值依賴于其中簡單命題的真值。2023/2/2計算機應(yīng)用技術(shù)研究所38命題運算聯(lián)結(jié)詞

【例】（1）期中考試，張三沒有考及格。（2）其中考試，張三和李四都考及格了。（3）其中考試，張三和李四中有人考了90分。（4）如果張三能考90分，那么李四也能考90分。（5）張三能考90分，當(dāng)且僅當(dāng)李四也能考90分。2023/2/2計算機應(yīng)用技術(shù)研究所39命題運算聯(lián)結(jié)詞：Negation

(NOT)否定詞

∧：Conjunction(AND)合取詞

∨：Disjunction(OR)析取詞：Implication(if–then)蘊涵詞

：Biconditional

(ifandonlyif)等價詞2023/2/2計算機應(yīng)用技術(shù)研究所40402023/2/2

聯(lián)結(jié)詞“

”稱為否定詞，表示“…不成立”

P：今天是星期二P：今天不是星期二

P讀著：“非P”

當(dāng)P為假時，非P為真；當(dāng)P為真時，非P為假“非”運算2023/2/2計算機應(yīng)用技術(shù)研究所41412023/2/2命題否定的真值表如下：P?PTFFT“非”運算2023/2/2計算機應(yīng)用技術(shù)研究所42422023/2/2“與”運算

聯(lián)結(jié)詞“”稱為合取詞，表示邏輯“與”運算；

“”相當(dāng)于自然語言中的“并且”，“與”的含義，但是又和自然語言中的“與”有所不同。

P：小王能唱歌；Q：小王能跳舞。

P∧Q：小王能歌善舞。當(dāng)且僅當(dāng)P和Q都為真時，PQ才為真2023/2/2計算機應(yīng)用技術(shù)研究所43432023/2/2當(dāng)且僅當(dāng)P和Q都為真時，PQ才為真PQPQTTTTFFFTFFFF“與”運算2023/2/2計算機應(yīng)用技術(shù)研究所44“(可兼)或”運算聯(lián)結(jié)詞“

”稱為析取詞，表示可兼或當(dāng)且僅當(dāng)P和Q都為假，PQ為假P:李明在教室。Q:米盧是個好教練。P∨Q:

李明在教室或米盧是個好教練。2023/2/2計算機應(yīng)用技術(shù)研究所45P∨Q的真值為F，當(dāng)且僅當(dāng)P與Q均為FPQPQTTTTFTFTTFFF“(可兼)或”運算2023/2/2計算機應(yīng)用技術(shù)研究所46“蘊涵”運算蘊涵(條件)“”:若P則Q例：P表示：缺少水分。Q表示：植物會死亡。PQ：如果缺少水分，植物就會死亡。P是前提，Q是結(jié)論2023/2/2計算機應(yīng)用技術(shù)研究所47當(dāng)且僅當(dāng)P為真且Q為假時，PQ為假PQPQTTTTFFFTTFFT“蘊涵”運算2023/2/2計算機應(yīng)用技術(shù)研究所48【注意】“”既表示充分條件也表示必要條件，它決定了哪個作為前件，哪個作為后件?！纠苛睿篜：天氣好。Q：我去公園。1.如果天氣好，我就去公園。（充分）2.只要天氣好，我就去公園。（充分）3.僅當(dāng)天氣好，我才去公園。（必要）4.只有天氣好，我才去公園。（必要）命題1、2寫成：PQ命題3、4寫成：QP“蘊涵”運算2023/2/2計算機應(yīng)用技術(shù)研究所49492023/2/2“”:等價聯(lián)結(jié)詞PQ（P當(dāng)且僅當(dāng)Q）：當(dāng)p和q有著相同的真值時，pq

為真）PQPQTTTTFFFTFFFT“等價”運算2023/2/2計算機應(yīng)用技術(shù)研究所50502023/2/2總結(jié)設(shè)命題P,Q表示任意兩個命題,則最常見的命題聯(lián)結(jié)詞有：聯(lián)接詞記號復(fù)合命題讀法

記法真值結(jié)果

3.析取

P或者QP與Q的析取PQP∨Q=1P=1或Q=12.合取

∧P并且QP與Q的合取P∧QP∧Q=1P=1且Q=11.否定

┐非PP的否定┐P┐P=1

P=04.蘊涵→若P,則QP蘊涵QP→QP→Q=0

P=1,Q=0?5.等價

P當(dāng)且僅當(dāng)QP等價于QP?QPQ=1P=1,Q=1或

P=0,Q=02023/2/2計算機應(yīng)用技術(shù)研究所51512023/2/2總結(jié)PQ┐PP∧QP∨QP→QP?Q0010011011011010001001101111設(shè)命題P,Q表示任意兩個命題,則有：2023/2/2計算機應(yīng)用技術(shù)研究所52命題與聯(lián)結(jié)詞命題的概念

命題的運算聯(lián)結(jié)詞命題的符號化與應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所53命題的符號化

1.首先要明確給定命題的含義。

2.對于復(fù)合命題，找聯(lián)結(jié)詞，用聯(lián)結(jié)詞斷句，分解出各個原子命題。

3.設(shè)原子命題符號，并用邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題符號，構(gòu)成給定命題的符號表達(dá)式。2023/2/2計算機應(yīng)用技術(shù)研究所54命題的符號化聯(lián)結(jié)詞與自然語言之間的對應(yīng)并非一一對應(yīng)2023/2/2計算機應(yīng)用技術(shù)研究所55命題的符號化【例】符號化下列命題說離散數(shù)學(xué)無用且枯燥無味是不對的。

P：離散數(shù)學(xué)是有用的。

Q：離散數(shù)學(xué)是枯燥無味的。

該命題可寫成：

(P∧Q)

人不犯我，我不犯人；人若犯我，我必犯人。

P：人犯我。Q：我犯人。

該命題可寫成：(PQ)∧(PQ)

或?qū)懗桑篜Q2023/2/2計算機應(yīng)用技術(shù)研究所56562023/2/2命題的符號化【例】符號化下列命題（1）四川不是人口最多的省份；（2）王超是一個德智體全面發(fā)展的好學(xué)生；（3）教室的燈不亮可能是燈管壞了或者是停電了；（4）如果周末天氣晴朗，那么學(xué)院將組織我們到石象湖春游；（5）兩個三角形全等當(dāng)且僅當(dāng)三角形三邊對應(yīng)相等。2023/2/2計算機應(yīng)用技術(shù)研究所57572023/2/2命題的符號化【例】符號化下列命題（1）除非明天不下雨且不下雪，否則我將不去學(xué)校；（2）只要明天不下雨或不下雪，我就去學(xué)校；（3）只有明天不是雨夾雪，我才去學(xué)校；（4）明天上午我將雨雪無阻一定去學(xué)校。2023/2/2計算機應(yīng)用技術(shù)研究所58582023/2/2命題的符號化【例】符號化下列命題

⑴

除非你陪伴我或代我叫車子，否則我將不出去

⑵

如果你陪伴我并且代我叫輛車子，那么我將出去

⑶

如果你不陪伴我或不代我叫輛車子，那么我將不出去2023/2/2計算機應(yīng)用技術(shù)研究所59592023/2/2聯(lián)結(jié)詞的應(yīng)用

聯(lián)結(jié)詞“∧”、“∨”、“┐”同構(gòu)成計算機的與門、或門和非門電路是相對應(yīng)的，從而命題邏輯是計算機硬件電路的表示、分析和設(shè)計的重要工具。2023/2/2計算機應(yīng)用技術(shù)研究所60602023/2/2【例】

用復(fù)合命題表示如下圖所示的開關(guān)電路：

設(shè)P:開關(guān)Ｐ閉合；Q:開關(guān)Ｑ閉合。P∧QP∨QP聯(lián)結(jié)詞的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所61612023/2/2【例】用復(fù)合命題表示如下圖所示的邏輯電路P

QP

QP【解】設(shè)P：輸入端Ｐ為高電位，Q：輸入端Ｑ為高電位,則

“與門”

對應(yīng)于P∧Q

“或門”

對應(yīng)于

P∨Q“非門”對應(yīng)于P聯(lián)結(jié)詞的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所62622023/2/2【例】邏輯難題一個島上住著兩類人：騎士和流氓。騎士說的話都是實話，而流氓只會說謊。如果碰到兩個人A和B，如果A說：“B是騎士”，B說:”我們兩個不是一類人”。請判斷：A、B兩人到底是流氓還是騎士？聯(lián)結(jié)詞的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所63632023/2/2【例】泥巴孩子難題

父親讓兩個孩子（一個男孩，一個女孩）在后院玩耍，并讓他們不要把身上搞臟。然而，在玩的過程中，兩個孩子都在額頭上沾了泥。孩子們回來后，父親說“你們當(dāng)中至少有一個人額頭上有泥”，然后他問每一個孩子“你知道你額頭上有沒有泥嗎？”同樣的問題問兩遍。假設(shè)每個孩子都可以看到對方的額頭上是否有泥，但不能看見自己的額頭，孩子們將會怎樣回答呢？假設(shè)兩個孩子都很誠實并且都同時回答每一次提問。聯(lián)結(jié)詞的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所64本節(jié)內(nèi)容到此結(jié)束謝謝大家！2023/2/2計算機應(yīng)用技術(shù)研究所65

命題邏輯（上）

邏輯與數(shù)理邏輯

命題與連接詞命題公式與真值表2023/2/2計算機應(yīng)用技術(shù)研究所66命題公式與真值表2023/2/2計算機應(yīng)用技術(shù)研究所67命題公式與真值表命題公式的基本概念命題公式的基本類型

命題公式的等值演算命題公式的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所68682023/2/2命題變元如果命題標(biāo)識符表示一個具體、確定的命題，稱為命題常元。如果命題標(biāo)識符表示任意一個命題，稱為命題變元。

命題是能判斷真假的陳述句。命題變元代表任意的命題，其真值是不確定的，它的變域是集合{T，F(xiàn)}(或{0，1})。2023/2/2計算機應(yīng)用技術(shù)研究所69692023/2/2命題公式

把命題常元，命題變元按照一定的邏輯順序和規(guī)則，用命題聯(lián)結(jié)詞連接起來就構(gòu)成了命題演算的合式公式，也叫命題公式。2023/2/2計算機應(yīng)用技術(shù)研究所70702023/2/2命題公式

按下列規(guī)則構(gòu)成的符號串稱為命題演算的合式公式，也稱為命題公式，簡稱公式。⑴單個命題變元和常元是合式公式。⑵如果A是合式公式，那么?A是合式公式。⑶如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A?B)是合式公式。⑷當(dāng)且僅當(dāng)有限次地應(yīng)用了⑴、⑵、⑶所得到的符號串是合式公式。2023/2/2計算機應(yīng)用技術(shù)研究所71712023/2/2命題公式

上面的定義給出合式公式定義的方法稱為歸納定義，它包括三部分：

基礎(chǔ)、歸納、界限其中⑴是基礎(chǔ)，⑵和⑶是歸納，⑷是界限。以后將多次出現(xiàn)這種形式的定義。2023/2/2計算機應(yīng)用技術(shù)研究所72722023/2/2命題公式【例】下列符號串是合式公式：

?(p∨q)，?(p∨q)，(p→(p∨?q))，

(((p→q)∧(q→r))?(s?t))

【例】下列符號串不是合式公式：

(p→q)→(∧q)，(p→q，(p∧q)→q)2023/2/2計算機應(yīng)用技術(shù)研究所73732023/2/2命題公式【約定】為方便，最外層括號可以不寫，合式公式可以寫成：

P∧Q，PR，(P∨Q)∧R【約定】邏輯聯(lián)接詞優(yōu)先級：

?、∧、∨、→、此時P∧QR也是合式公式2023/2/2計算機應(yīng)用技術(shù)研究所74742023/2/2命題公式【例】試用符號形式寫出下列命題：（1）雖然今天天氣晴朗，老陳還是不來；【解】

設(shè)P：今天天氣晴朗,Q：老陳要來,則有：

P∧┐Q；（2）除非你陪伴我或代我叫車子，否則我將不出去；【解】

設(shè)P:你陪伴我;Q:你代我叫車子;R:我出去。則有：R→P∨Q或┐P∧┐Q→┐R；2023/2/2計算機應(yīng)用技術(shù)研究所75752023/2/2命題公式（3）停機的原因在于語法錯誤或者程序錯誤；

【解】設(shè)P：停機的原因在于語法錯誤，

Q：停機的原因在于程序錯誤，

則有：P∨Q；（4）若a和b是偶數(shù)，則a+b是偶數(shù)；

【解】設(shè)P：a是偶數(shù)；Q：b是偶數(shù)，R：a+b是偶數(shù)，則有：P∧Q→R；2023/2/2計算機應(yīng)用技術(shù)研究所76762023/2/2公式的解釋【定義】設(shè)P1,P2,…,Pn是出現(xiàn)在公式G中的所有命題變元，指定P1,P2,…,Pn一組真值，例如(0,1,…,1)，則稱這組真值為對公式G的一個解釋或賦值,

記為Ｉ2023/2/2計算機應(yīng)用技術(shù)研究所77772023/2/2公式的解釋

若指定的賦值使G的真值為T，則稱這個賦值為G的成真賦值，若指定的賦值使G的真值為F，則稱這個賦值為G的成假賦值。

【例】給公式(p∨q→r)的賦值賦值011是指p=0，q=1，r=1，它是該公式的成真賦值；賦值110是指p=1，q=1，r=0，它是該公式的成假賦值。2023/2/2計算機應(yīng)用技術(shù)研究所78782023/2/2公式的解釋

一般來說，若公式G中有ｎ個不同的命題變元，則該公式應(yīng)有2n個不同的解釋。

將公式G在其所有可能解釋下的真值情況列成的表，稱為G的真值表。2023/2/2計算機應(yīng)用技術(shù)研究所79792023/2/2真值表

在命題公式G中，對G的每一個賦值，就確定了G的一個真值，把這些所有的真值匯列成表，稱該表為命題公式G的真值表。PQPPQ(PQ)∨QTTFTTTFFTTFTTTTFFTFF2023/2/2計算機應(yīng)用技術(shù)研究所80802023/2/2真值表【例】求下面公式真值表：Ｇ＝(P→(PQ)∧R)∨Q

其中，Ｐ、Ｑ、Ｒ是Ｇ的所有命題變元。2023/2/2計算機應(yīng)用技術(shù)研究所81812023/2/2真值表【說明】設(shè)P1，P2,…,Pn為命題公式P中的命題變量，對于命題變元每一種真值指派的可能組合，都能唯一確定P的真值（即有2的n次冪種分布）。為了有序地列出公式的真值表，在對命題變元做指派時，可以按照二進制數(shù)的次序列表。2023/2/2計算機應(yīng)用技術(shù)研究所82822023/2/2真值表【例】構(gòu)造命題公式?p∨q的真值表，并求成真賦值和成假賦值。【解】命題公式?p∨q的真值表下表所示。00，01，11是成真賦值，10是成假賦值。?ppq?p∨q00110111100011012023/2/2計算機應(yīng)用技術(shù)研究所83832023/2/2真值表【例】構(gòu)造命題公式(p∧q)∨(?p∧?q)的真值表，并求成真賦值和成假賦值。解：命題公式(p∧q)∨(?p∧?q)的真值表如下表所示。00，11是成真賦值，01，10是成假賦值。

pqp∧q?p?q?p∧?q(p∧q)∨(?p∧?q)00011110101000100010011100012023/2/2計算機應(yīng)用技術(shù)研究所84842023/2/2真值表為了有序地列出G(P1,P2,…,Pn)的真值表，可以將F看成0，將T看成1，按照二進制數(shù)00…0,00…01,00…010,…,11…10,11…1(即十進制的0,1,2,….,2n-1)的次序進行指派列真值表。如G(P,Q)的真值表可按照如下次序指派：

00(F,F)，01(F,T)，10(T,F)，11(T,T)如G(P,Q,R)的真值表可按照如下次序指派：

000(F,F,F),001(F,F,T),010(F,T,F),011(F,T,T)100(T,F,F),101(T,F,T),110(T,T,F),111(T,T,T)2023/2/2計算機應(yīng)用技術(shù)研究所85852023/2/2真值表【例】列出P(QR)的真值表

PQRQRP(QR)000FFFTT001FFTTT010FTFFT011FTTTT100TFFTT101TFTTT110TTFFF111TTTTT2023/2/2計算機應(yīng)用技術(shù)研究所86命題公式與真值表命題公式的基本概念命題公式的基本類型

命題公式的等值演算命題公式的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所87872023/2/2公式的分類【例】求列公式的真值表： Ｇ1＝(Ｐ→Ｑ)→Ｐ；Ｇ2＝(Ｐ→Ｑ)∧Ｐ；Ｇ3＝(Ｐ∧Ｑ)(Ｐ→Q)。2023/2/2計算機應(yīng)用技術(shù)研究所88882023/2/2公式的分類從這三個真值表可以看到：公式G1對所有可能的解釋具有“真”值公式G3對所有可能的解釋均具有“假”值公式G2則具有“真”和“假”值2023/2/2計算機應(yīng)用技術(shù)研究所89892023/2/2公式的分類公式G稱為永真公式(重言式)，如果在它的所有解釋之下都為“真”。公式G稱為永假公式(矛盾式),

如果在它的所有解釋之下都為“假”。公式G稱為可滿足式，如果它不是永假的。2023/2/2計算機應(yīng)用技術(shù)研究所90902023/2/2公式的分類如果A，B是永真式(永假式)，則(A∧B)、(A∨B)、(AB)和(AB)也都是永真式(永假式)

。2023/2/2計算機應(yīng)用技術(shù)研究所91912023/2/2公式的分類永真式G的否定G是矛盾式；

矛盾式G的否定G是永真式。永真式一定是可滿足式;

可滿足式不一定是永真式可滿足式的否定不一定是矛盾式三種特殊公式之間的關(guān)系：2023/2/2計算機應(yīng)用技術(shù)研究所92922023/2/2公式的分類三種特殊公式之間的關(guān)系：2023/2/2計算機應(yīng)用技術(shù)研究所93932023/2/2公式的分類【例】寫出下列公式的真值表，并驗證其公式是永真式、永假式、可滿足公式。（1）G1=(Ｐ→Ｑ)(Ｐ∨Ｑ)；（2）G2=(ＰQ)((Ｐ→Q)∨(Q→Ｐ))；（3）G3=(P→Q)∨Q。2023/2/2計算機應(yīng)用技術(shù)研究所94942023/2/2公式的分類2023/2/2計算機應(yīng)用技術(shù)研究所95命題公式與真值表

命題公式的基本概念命題公式的基本類型命題公式的等值演算命題公式的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所96觀察下列真值表PQ?P∨QPQ（P∧

Q）∨（?P

∧

?Q）PQ

FFTTTTFTTTFFTFFFFFTTTTTT是否發(fā)現(xiàn)什么問題？?P∨Q＝P

Q？（P∧

Q）∨（?P

∧

?Q）

＝PQ

？公式的等值關(guān)系2023/2/2計算機應(yīng)用技術(shù)研究所97公式的等值關(guān)系

【定義】A、B是含有命題變元P1,P2,…,Pn的命題公式，如不論對P1,P2,…,Pn作任何指派，都使得A和B的真值相同，則稱之為命題公式A與B等價或等值，記作AB。顯然有：

?P∨QPQ(P∧Q)∨(?P∧?Q)PQ2023/2/2計算機應(yīng)用技術(shù)研究所98公式的等值關(guān)系可以證明，命題公式的等值關(guān)系有如下性質(zhì)：

(1)自反性，即對任意命題公式A，AA(2)對稱性，即對任意命題公式A和B，若AB，則BA(3)傳遞性，即對任意命題公式A，B和C，若AB，BC，則AC(4)如果A(P1,P2,…,Pn)B(P1,P2,…,Pn)，則

A(P1,P2,…,Pn)B(P1,P2,…,Pn)2023/2/2計算機應(yīng)用技術(shù)研究所99公式的等值關(guān)系【例】A(P,Q)P→Q;B(P,Q)P∨Q

則有：A(P,Q)B(P,Q)A(P,Q)P→QB(P,Q)P∨Q

可見：A(P,Q)B(P,Q)2023/2/2計算機應(yīng)用技術(shù)研究所100公式的等值關(guān)系【例】根據(jù)等值關(guān)系的定義，用真值表證明

p→(q→p)?p→(p→?q)pq?p?qq→pp→(q→p)p→?q?p→(p→?q)001111110110011110011111110011012023/2/2計算機應(yīng)用技術(shù)研究所101公式的等值關(guān)系【定理】

命題公式A、B具有等值關(guān)系的充分必要條件是命題公式AB是永真式?！咀C明】（1）若AB，則A、B有相同的真值，即AB永為T.（2）若AB為重言式，則AB永為T，故A、B的真值相同，即AB2023/2/2計算機應(yīng)用技術(shù)研究所102與的區(qū)別

“”是一種邏輯運算，命題公式GH

的結(jié)果仍是一個命題公式?！啊北硎緝蓚€命題公式之間的邏輯等值關(guān)系，GH表示“命題公式G與命題公式H等值”，GH不是命題公式。

此外，如果用計算機直接判斷命題公式G、H是否邏輯等價或等值(即GH)，是辦不到的。但是，計算機可通過“計算”公式GH是否為永真式，來判別是否有:GH

。2023/2/2計算機應(yīng)用技術(shù)研究所103公式的等值關(guān)系【例】

證明公式G1＝(ＰＱ)與公式G2＝(P→Q)∧(Q→P)之間邏輯等價?！咀C】根據(jù)定理，只需判定公式G3＝(ＰＱ)((P→Q)∧(Q→P))為永真公式。2023/2/2計算機應(yīng)用技術(shù)研究所104等值演算法證明兩個命題公式之間等值或邏輯等價的另外一種方法叫做等值演算法?；舅悸肥牵菏紫扔谜嬷当碜C明一組基本等值式，然后再它們?yōu)榛A(chǔ)進行命題公式之間的等值演算。2023/2/2計算機應(yīng)用技術(shù)研究所105基本等值式2023/2/2計算機應(yīng)用技術(shù)研究所106基本等值式2023/2/2計算機應(yīng)用技術(shù)研究所107基本等值式2023/2/2計算機應(yīng)用技術(shù)研究所108基本等值式

以上共24個等值式都可用真值表證明。下面僅驗證德摩根律：?(A∨B)?A∧?BA∨BAB?A?B?A∧?B?(A∨B)00111010110010100101011000102023/2/2計算機應(yīng)用技術(shù)研究所109命題與集合2023/2/2計算機應(yīng)用技術(shù)研究所110∪、∩與∨、∧2023/2/2計算機應(yīng)用技術(shù)研究所111代入定理2023/2/2計算機應(yīng)用技術(shù)研究所112代入定理【例】設(shè)G(P,Q)=(P∧(P→Q))→Q，證明公式G是一個永真公式。另有兩個公式：H(P,Q)=P∨?Q;S(P,Q)=PQ進一步驗證代入定理的正確性?！窘狻坑烧嬷当硪鬃CG是一個永真公式。將H和S代入G中得到新公式G'為：G'(P,Q)=G(H,S)=(H∧(H→S))→S=((P∨?Q)

∧(P∨?Q))→(PQ)))→(PQ)由真值表易證G'是一個永真公式。2023/2/2計算機應(yīng)用技術(shù)研究所113替換定理【定理】設(shè)G1是G的子公式，H1是任一命題公式，在G中凡出現(xiàn)G1處都以H1替換后得到新的命題公式H，

若G1H1，則GH。

熟記24個基本等值公式理解代入定理

和替換定理2023/2/2計算機應(yīng)用技術(shù)研究所114公式的等值演算利用公式的等值演算，可完成如下工作：2023/2/2計算機應(yīng)用技術(shù)研究所115公式的等值演算利用公式的等值演算，可完成如下工作：2023/2/2計算機應(yīng)用技術(shù)研究所116公式的等值演算利用公式的等值演算，可完成如下工作：2023/2/2計算機應(yīng)用技術(shù)研究所117公式的等值演算【例】

求證吸收律P∧(P∨Q)P【證】(

P∧(P∨Q)

(P∨F)∧(P∨Q)(同一律)

P∨(F∧Q)(分配律)

P∨F(零律)

P(同一律)2023/2/2計算機應(yīng)用技術(shù)研究所118公式的等值演算【例】求證(P∨Q)→(P∧Q)P【證】(P∨Q)→(P∧Q)

(P∨Q)∨(P∧Q)(常用等值式)(P∧Q)∨(P∧Q)(摩根定律)(P∧Q)∨(P∧Q)(對合律)

P∧(Q∨Q)(分配律)

P∧T(互補律)

P(同一律)2023/2/2計算機應(yīng)用技術(shù)研究所119公式的等值演算【例】化簡(P∧Q)→(P∨(P∨Q))【解】

原公式(P∧Q)∨((P∨P)∨Q)(常用等值式)(P∧Q)∨(P∨Q)(對合律，冪等律)(P∧Q)∨(Q∨P)(交換律)((P∧Q)∨Q)∨P(結(jié)合律)Q∨P(吸收律)2023/2/2計算機應(yīng)用技術(shù)研究所120命題公式與真值表

命題公式的基本概念命題公式的基本類型

命題公式的等值演算命題公式的應(yīng)用2023/2/2計算機應(yīng)用技術(shù)研究所1211212023/2/21試證語句：“不會休息的人也不會工作，沒有豐富知識的人也不會工作”，與語句“工作得好的人一定會休息并且有豐富的知識”，具有相同的邏輯含義。分析：設(shè)P：某人會工作；Q：某人會休息；R：某人有豐富的知識，則有：

(Q→P)∧(R→P)