第一命題邏輯

第一命題邏輯1第一頁，共一百九十七頁，2022年，8月28日目錄數(shù)理邏輯引言1-1命題與命題的真值1-2聯(lián)結(jié)詞1-3命題公式及翻譯1-4真值表與等價(jià)公式1-5重言式與重言蘊(yùn)涵式1-6其它聯(lián)結(jié)詞1-7對偶與范式1-8命題推理理論小結(jié)

習(xí)題

2第二頁，共一百九十七頁，2022年，8月28日第一篇數(shù)理邏輯邏輯--是研究人的思維形式及思維規(guī)律的科學(xué)。它包含：

1.辯證邏輯：是研究人的思維中的辯證法。

例如：用全面的和發(fā)展的觀點(diǎn)觀察事物；具體問題具體分析；實(shí)踐是檢查事物正誤的唯一標(biāo)準(zhǔn)；等等。

2.形式邏輯：是研究人的思維的形式和一般規(guī)律。類似于語法的一門工具性學(xué)科。3第三頁，共一百九十七頁，2022年，8月28日一.形式邏輯人的思維過程：概念判斷推理正確的思維：概念清楚，判斷正確，推理合乎邏輯。人們是通過各種各樣的學(xué)習(xí)(理論學(xué)習(xí)和從實(shí)踐中學(xué)習(xí))來掌握許多概念和判斷。形式邏輯主要是研究推理的。4第四頁，共一百九十七頁，2022年，8月28日推理方法推理：是由若干個(gè)已知的判斷(前提)，推出新的判斷(結(jié)論)的思維過程。類比推理：由個(gè)別事實(shí)推出個(gè)別結(jié)論。如：地球上有空氣、水，地球上有生物?；鹦巧嫌锌諝?、水。

火星上有生物。歸納推理：由若干個(gè)別事實(shí)推出一般結(jié)論。

5第五頁，共一百九十七頁，2022年，8月28日推理方法如：銅能導(dǎo)電。鐵能導(dǎo)電。錫能導(dǎo)電。鉛能導(dǎo)電?！磺薪饘俣紝?dǎo)電。演繹推理：由一般規(guī)律推出個(gè)別事實(shí)。

形式邏輯主要是研究演繹推理的。6第六頁，共一百九十七頁，2022年，8月28日演繹推理舉例例1：如果天下雨，則路上有水。(一般規(guī)律)

天下雨了。(個(gè)別事實(shí))

推出結(jié)論：路上有水。(個(gè)別結(jié)論)例2：

(大前提)：所有金屬都導(dǎo)電。(一般規(guī)律)(小前提)：銅是金屬。(個(gè)別事實(shí))

推出結(jié)論：銅能導(dǎo)電。(個(gè)別結(jié)論)7第七頁，共一百九十七頁，2022年，8月28日二.數(shù)理邏輯數(shù)理邏輯是用數(shù)學(xué)的方法研究形式邏輯。所謂“數(shù)學(xué)方法”：是建立一套有嚴(yán)格定義的符號，即建立一套形式語言，來研究形式邏輯。所以數(shù)理邏輯也稱為“符號邏輯”。它與數(shù)學(xué)的其它分支、計(jì)算機(jī)科學(xué)、人工智能、語言學(xué)等學(xué)科均有密切聯(lián)系。數(shù)理邏輯可分為：證明論、模型論、遞歸論、公理化集合論、邏輯演算，這里只討論“命題邏輯”和“謂詞邏輯”。8第八頁，共一百九十七頁，2022年，8月28日數(shù)理邏輯把推理符號化之一下面就前面兩個(gè)例子，說明如何將推理符號化。設(shè)P表示：天下雨。設(shè)Q表示：路上有水。設(shè)表示：如果…則…例1的推理過程表示為：前提1:PQ(如果天下雨,則路上有水。)前提2：P(天下雨了。)結(jié)論：Q(路上有水。)9第九頁，共一百九十七頁，2022年，8月28日數(shù)理邏輯把推理符號化之二設(shè)M(x):x是金屬.設(shè)C(x):x能導(dǎo)電.設(shè)x表示:所有的x.設(shè)

a表示銅.例2的推理過程表示為：

前提:x(M(x)C(x))(所有金屬都導(dǎo)電.)前提:M(a)(銅是金屬.)結(jié)論:C(a)(銅能導(dǎo)電.)(其中符號M(x)是謂詞，所以這就是第二章“謂詞邏輯”中所討論的內(nèi)容.）10第十頁，共一百九十七頁，2022年，8月28日第一章命題邏輯知識點(diǎn)：命題的表示、命題的演算命題演算中的公式，及其應(yīng)用命題邏輯推理11第十一頁，共一百九十七頁，2022年，8月28日1-1.命題與命題的真值本節(jié)主要討論三個(gè)問題：命題的概念命題的真值原子命題與復(fù)合命題命題的表示12第十二頁，共一百九十七頁，2022年，8月28日一.命題的概念命題：是一個(gè)能確定是真的或是假的判斷。（判斷都是用陳述句表示）例1-1.1判定下面這些句子哪些是命題。⑴2是個(gè)素?cái)?shù)。⑵雪是黑色的。⑶2015年人類將到達(dá)火星。⑷如果a>b且b>c，則a>c。⑸x+y<5⑹請打開書?、四?？13第十三頁，共一百九十七頁，2022年，8月28日⑴⑵⑶⑷是命題悖論1、我正在說謊2、一個(gè)城市里唯一的理發(fā)師只給所有不給自己理發(fā)的人理發(fā)14第十四頁，共一百九十七頁，2022年，8月28日二.命題的真值一個(gè)命題所作的判斷有兩種可能：是正確的判斷或者是錯(cuò)誤的判斷。一個(gè)命題的真值有兩個(gè)：“真”或“假”真值為真:一個(gè)命題所作的判斷與客觀一致,則稱該命題的真值為真,記作T(True)。真值為假:一個(gè)命題所作的判斷與客觀不一致,則稱該命題的真值為假,記作F(False)。例1-1.1中(1)(4)的真值為真,(2)的真值為假,(3)暫時(shí)不能定，等到2005年確定。15第十五頁，共一百九十七頁，2022年，8月28日三.原子命題與復(fù)合命題簡單命題(原子命題)：由最簡單的陳述句構(gòu)成的命題(該句再不能分解成更簡單的句子了)。復(fù)合命題(分子命題)：由若干個(gè)原子命題構(gòu)成的命題。16第十六頁，共一百九十七頁，2022年，8月28日四命題的表示表示：大寫字母、帶下標(biāo)的大寫字母或數(shù)字如：A,A3,[12],P命題標(biāo)識符：表示命題的符號命題常量：一個(gè)命題標(biāo)識符如表示確定的命題命題變元：命題標(biāo)識符只表示任意命題的位置標(biāo)志。不確定其真值，不是命題對命題變元的指派：命題變元P用一個(gè)特定命題取代時(shí)，P才能確定真值原子變元：當(dāng)命題變元表示原子命題時(shí)的變元17第十七頁，共一百九十七頁，2022年，8月28日1-2聯(lián)結(jié)詞復(fù)合命題的構(gòu)成：是用“聯(lián)結(jié)詞”將原子命題聯(lián)結(jié)起來構(gòu)成的。歸納自然語言中的聯(lián)結(jié)詞，定義了六個(gè)邏輯聯(lián)結(jié)詞，分別是：(1)否定“”(2)合取“∧”(3)析取“∨”(4)異或“”

(5)蘊(yùn)涵“”(6)等價(jià)“”18第十八頁，共一百九十七頁，2022年，8月28日一.否定“”表示：“…不成立”，“不…”。用于：對一個(gè)命題P的否定，寫成P，并讀成“非P”。P的真值：與P真值相反。例1-2.1P：2是素?cái)?shù)。P：2不是素?cái)?shù)。P：上海是一個(gè)大城市PPTFFT19第十九頁，共一百九十七頁，2022年，8月28日二.合取“∧”二元運(yùn)算表示：“并且”、“不但…而且...”、“既…又

...”“盡管…還…”例1-2.2P：小王能唱歌。

Q：小王能跳舞。P∧Q：小王能歌善舞。P∧Q讀成P合取Q。P∧Q的真值為真，當(dāng)且僅當(dāng)P和Q的真值均為真。PQP∧QFFFFTFTFFTTT20第二十頁，共一百九十七頁，2022年，8月28日三.析取“∨”、異或“

”表示“或者”“或者”有二義性，看下面兩個(gè)例子：例1-2.3.燈泡或者線路有故障。例1-2.4.第一節(jié)課上數(shù)學(xué)或者上英語。例3中的或者是可兼取的或。即析取“∨”例4中的或者是不可兼取的或，也稱之為異或、排斥或。即“”.21第二十一頁，共一百九十七頁，2022年，8月28日1.析取“∨”P：燈泡有故障。Q：線路有故障。例3中的復(fù)合命題可表示為：P∨Q，讀成P析取Q，P或者Q。P∨Q的真值為F，當(dāng)且僅當(dāng)P與Q均為F。PQP∨QFFFFTTTFTTTT22第二十二頁，共一百九十七頁，2022年，8月28日2.異或“

”P：第一節(jié)上數(shù)學(xué)。Q：第一節(jié)上英語。例4中的復(fù)合命題可寫成PQ，讀成P異或Q。PQ的真值為F，當(dāng)且僅當(dāng)P與Q的真值相同F(xiàn)FFFTTTFTTTFPQPQ23第二十三頁，共一百九十七頁，2022年，8月28日3.異或的另一種表示異或是表示兩個(gè)命題不可能同時(shí)都成立。命題“第一節(jié)課上數(shù)學(xué)或者上英語?！笨梢越忉尀椋骸暗谝还?jié)課上數(shù)學(xué)而沒有上英語或者第一節(jié)課上英語而沒有上數(shù)學(xué)?！庇谑怯?/p>

PQ與(P∧Q)∨(Q∧P)是一樣的。實(shí)際應(yīng)用中必須注意“或者”的二義性。24第二十四頁，共一百九十七頁，2022年，8月28日四.條件

(蘊(yùn)涵)“”表示“如果…則…”，例1-2.5：P表示：缺少水分。Q表示：植物會死亡。PQ：如果缺少水分，植物就會死亡。PQ：也稱之為蘊(yùn)涵式，讀成“P蘊(yùn)涵Q”，“如果P則Q”。也說成P是PQ的前件，Q是PQ的后件。還可以說P是Q的充分條件，Q是P的必要條件。

25第二十五頁，共一百九十七頁，2022年，8月28日PQ的真值PQ的真值為假，當(dāng)且僅當(dāng)P為真，Q為假。注意：當(dāng)前件P為假時(shí)，PQ為T。

PQ

PQ小王借錢不還我替他還（我給小王擔(dān)保）

FFT

FTT

TFF

TTT

26第二十六頁，共一百九十七頁，2022年，8月28日書例：如果某動(dòng)物為哺乳動(dòng)物，則它必胎生如果我得到這本小說，那么我今夜就讀完它如果雪是黑的，那么太陽從西方出來。27第二十七頁，共一百九十七頁，2022年，8月28日關(guān)于充分條件和必要條件的說明：充分條件：就是只要條件成立，結(jié)論就成立，則該條件就是充分條件。上例中，“缺少水分”就是“植物會死亡”的充分條件。在自然語言中表示充分條件的詞有：如果…則…，只要…就…，若…則…必要條件：就是如果該條件不成立，那么結(jié)論就不成立,則該條件就是必要條件。

上例中，“植物死亡”就是“缺少水分”的必要條件(植物未死亡，一定不缺少水分)。在自然語言中表示必要條件的詞有：

只有…才…；僅當(dāng)…，…;…,僅當(dāng)…。28第二十八頁，共一百九十七頁，2022年，8月28日舉例：令：P：天氣好。Q：我去公園。1.如果天氣好，我就去公園。2.只要天氣好，我就去公園。3.天氣好，我就去公園。4.僅當(dāng)天氣好，我才去公園。5.只有天氣好，我才去公園。6.我去公園，僅當(dāng)天氣好。命題1.、2.、3.寫成：PQ命題4.、5.、6.寫成：QP29第二十九頁，共一百九十七頁，2022年，8月28日舉例：可見“”既表示充分條件（即前件是后件的充分條件）；也表示必要條件（即后件是前件的必要條件）。這一點(diǎn)要特別注意!!!它決定了哪個(gè)作為前件，哪個(gè)作為后件。30第三十頁，共一百九十七頁，2022年，8月28日五.等價(jià)(雙條件）“”表示“當(dāng)且僅當(dāng)”、“充分且必要”例1-2.6：P：⊿ABC是等邊三角形。Q：⊿ABC是等角三角形。PQ：⊿ABC是等邊三角形當(dāng)且僅當(dāng)它是等角三角形。31第三十一頁，共一百九十七頁，2022年，8月28日PQ的真值：PQ的真值為真，當(dāng)且僅當(dāng)P與Q的真值相同。

PQPQ

FFT

FTF

TFF

TTT

32第三十二頁，共一百九十七頁，2022年，8月28日本節(jié)小結(jié)：要熟練掌握這五個(gè)聯(lián)結(jié)詞在自然語言中所表示的含義以及它們的真值表的定義。

PQP∧QP∨QPQPQ

FFFFTT

FTFTTF

TFFTFFTTTTTT33第三十三頁，共一百九十七頁，2022年，8月28日本節(jié)小結(jié)特別要注意“或者”的二義性，即要區(qū)分給定的“或”是“可兼取的或”還是“不可兼取的或”。特別要注意“”的用法，它既表示“充分條件”也表示“必要條件”，即要弄清哪個(gè)作為前件，哪個(gè)作為后件。作業(yè)：p83，4，534第三十四頁，共一百九十七頁，2022年，8月28日本節(jié)小結(jié)練習(xí)：填空已知P∧Q為T，則P為()，Q為()。已知P∨Q為F，則P為()，Q為()。已知P為F，則P∧Q為()。已知P為T，則P∨Q為()。已知P∨Q為T，且P為F，則Q為()。已知PQ為F，則P為()，Q為()。已知P為F，則PQ為()。已知Q為T，則PQ為()。已知PQ為F，則P為()，Q為()。35第三十五頁，共一百九十七頁，2022年，8月28日本節(jié)小結(jié)已知P為T，PQ為T，則Q為()。已知Q為T,PQ為T，則P為()。已知PQ為T，P為T,則Q為().已知PQ為F，P為T,則Q為().PP的真值為().PP的真值為()。36第三十六頁，共一百九十七頁，2022年，8月28日1-3命題公式及翻譯一.命題常量與命題變元命題常量：確定的命題。它是有具體含義(真值)的。例如：“3是素?cái)?shù)?！本褪敲}常量，也稱常值命題。命題變元：用大寫的英字母如P、Q等表示任何命題。稱這些字母為命題變元。對命題變元作指派(給命題變元一個(gè)解釋)：將一個(gè)命題常量賦予命題變元的過程，或者是直接賦給命題變元真值“T”或“F”的過程。注意：命題變元本身不是命題，只有給它一個(gè)指派，才變成命題。37第三十七頁，共一百九十七頁，2022年，8月28日命題公式設(shè)P和Q是任意兩個(gè)命題，則P,P∧Q,P∨Q,(P∨Q)∨(PQ),P(Q∨P)等都是復(fù)合命題若P和Q是命題變元，則上述積各式均稱作命題公式。P和Q稱作是命題公式的分量。注：命題公式?jīng)]有真假，僅當(dāng)在一個(gè)公式中命題變元用確定的命題代入時(shí)，才得到一命題；該命題的真值依賴于代換變元的那些命題的真值；并不是則命題變元，聯(lián)結(jié)詞和一些括號組成的字符串都能成為命題公式38第三十八頁，共一百九十七頁，2022年，8月28日命題公式.二.命題演算合式公式(wff)(wellformedformulas)定義1-3.1：⑴單個(gè)命題變元是個(gè)合式公式。⑵若A是合式公式，則A是合式公式。⑶若A和B是合式公式，則(A∧B)，(A∨B)，(AB)和(AB)都是合式公式。⑷當(dāng)且僅當(dāng)有限次地應(yīng)用⑴，⑵，⑶所得到的含有命題變元、聯(lián)結(jié)詞和括號的符號串是合式公式。39第三十九頁，共一百九十七頁，2022年，8月28日命題公式注意這個(gè)定義是遞歸的。(1)是遞歸的基礎(chǔ)，由(1)開始，使用(2)(3)規(guī)則，（4）是界限，可以得到任意的合式公式。這里所謂的合式公式可以解釋為合法的命題公式之意，也稱之為命題公式，有時(shí)也簡稱公式。下面的式子不是合式公式：

(PQ)(∨Q)，PR，((P∨Q)∧R下面的式子才是合式公式：

(P∧Q)，(PR)，((P∨Q)∧R)40第四十頁，共一百九十七頁，2022年，8月28日命題公式按照合式公式定義最外層括號必須寫。約定：（1）為方便，最外層括號可以不寫，上面的合式公式可以寫成：

P∧Q，PR，(P∨Q)∧R例：(((P∧(Q))∨R)((R∨P)∨Q))41第四十一頁，共一百九十七頁，2022年，8月28日命題公式（2）五個(gè)聯(lián)結(jié)詞的優(yōu)先次序：、∧、∨、、，凡符合此優(yōu)先次序的，括號可省略（3）相同的聯(lián)結(jié)詞按出現(xiàn)的先后次序運(yùn)算，凡符合此要求的，括號可省去。例：(((P∧(Q))∨R)((R∨P)∨Q))(P∧Q∨R)R∨P∨Q42第四十二頁，共一百九十七頁，2022年，8月28日命題公式判斷下列公式哪些是合式公式，哪些不是合式公式？(QR∧S)(P(RS))((PQ)(QP)))(RST)((P(QR))((PQ)(PR)))43第四十三頁，共一百九十七頁，2022年，8月28日三.命題符號化所謂命題符號化，就是用命題公式的符號串來表示給定的命題。命題符號化的方法（1）.首先要明確給定命題的含義。（2）.對于復(fù)合命題，找聯(lián)結(jié)詞，用聯(lián)結(jié)詞斷句，分解出各個(gè)原子命題。（3）.設(shè)原子命題符號，并用邏輯聯(lián)結(jié)詞聯(lián)結(jié)原子命題符號，構(gòu)成給定命題的符號表達(dá)式。44第四十四頁，共一百九十七頁，2022年，8月28日三.命題符號化例1.說離散數(shù)學(xué)無用且枯燥無味是不對的。

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

Q：離散數(shù)學(xué)是枯燥無味的。該命題可寫成：

(P∧Q)例2.如果小張與小王都不去，則小李去。

P：小張去。Q：小王去。R：小李去。該命題可寫成：(P∧Q)R

45第四十五頁，共一百九十七頁，2022年，8月28日三.命題符號化例3.僅當(dāng)天不下雨且我有時(shí)間，才上街。P：天下雨。Q：我有時(shí)間。R：我上街。

分析：由于“僅當(dāng)”是表示“必要條件”的，既“天不下雨且我有時(shí)間”，是“我上街”的必要條件。所以該命題可寫成：R(P∧Q)46第四十六頁，共一百九十七頁，2022年，8月28日三.命題符號化例4.人不犯我，我不犯人；人若犯我，我必犯人。P：人犯我。Q：我犯人。該命題可寫成：(PQ)∧(PQ)

或?qū)懗桑篜QP是Q的充分條件P是Q的必要條件P是Q的充分且必要條件47第四十七頁，共一百九十七頁，2022年，8月28日三.命題符號化例5.若天不下雨，我就上街；否則在家。P：天下雨。Q：我上街。R：我在家。該命題可寫成：(PQ)∧(P

R).

注意：中間的聯(lián)結(jié)詞一定是“∧”，而不是“∨”，也不是“”。因?yàn)樵}表示：“天不下雨時(shí)我做什么，天下雨我又做什么”的兩種作法，其中有一種作法是假的，則我說的就是假話，所以中間的聯(lián)結(jié)詞一定是“∧”。48第四十八頁，共一百九十七頁，2022年，8月28日三.命題符號化如果寫成(PQ)∨(P

R)，就表明兩種作法都是假的時(shí)候，我說的才是假話。這顯然不對。若寫成(PQ)(P

R)時(shí)，當(dāng)P為F，Q為F時(shí)，即天沒下雨而我沒上街，此時(shí)我說的是假話，但是表達(dá)式(PQ)(P

R)的真值卻是“T”，因?yàn)榇藭r(shí)(P

R)的真值是“T”。所以這個(gè)表達(dá)式也不對。49第四十九頁，共一百九十七頁，2022年，8月28日練習(xí)上海到北京的14次列車是下午五點(diǎn)半或六點(diǎn)半開除非你努力，否則你將失敗異或PQ50第五十頁，共一百九十七頁，2022年，8月28日1-4真值表與等價(jià)公式一.命題公式的真值表定義1-4.1

在命題公式中，由對所含命題變元的所有可能指派和在此指派下公式的真值構(gòu)成的表。

(PQ)∨Q的真值表：

PQPPQ(PQ)∨QFFTFFFTTTTTFFTTTTFTT51第五十一頁，共一百九十七頁，2022年，8月28日1-4真值表與等價(jià)公式命題變元PTFN個(gè)命題變元P1,P2,…,PnTT

,…,TFF

,…,F命題公式A(P1,P2,…,Pn)真值表有2n行有一類公式不論變元做何種指派，其真值永為真（假），可將此類公式記為T(F)52第五十二頁，共一百九十七頁，2022年，8月28日關(guān)于二進(jìn)制數(shù)簡介：為了有序地列出A(P1,P2,…,Pn)的真值表，可以將F看成0，將T看成1，按照二進(jìn)制數(shù)00…0,00…01,00…010,…,11…10,11…1(即十進(jìn)制的0,1,2,….,2n-1)的次序進(jìn)行指派列真值表。十進(jìn)制數(shù)0123456789二進(jìn)制數(shù)01101110010111011110001001注:有效數(shù)字前加0不影響數(shù)值，如000=0，001=1，010=10，011=1153第五十三頁，共一百九十七頁，2022年，8月28日關(guān)于二進(jìn)制數(shù)簡介：例如列出P(QR)的真值表

PQRQRP(QR)000FFFTT001FFTTT010FTFFT011FTTTT100TFFTT101TFTTT110TTFFF111TTTTT54第五十四頁，共一百九十七頁，2022年，8月28日二、等價(jià)公式

PQPQP∨QQPFFTTTFTTTTTFFFFTTTTT定義1-4.2A、B是含有命題變元P1,P2,…,Pn的命題公式，如不論對P1,P2,…,Pn作任何指派，都使得A和B的真值相同，則稱之為A與B等價(jià)，記作AB。55第五十五頁，共一百九十七頁，2022年，8月28日二、等價(jià)公式重要的等價(jià)公式⑴對合律PP(雙否律)⑵冪等律P∨PPP∧PP⑶結(jié)合律P∨(Q∨R)(P∨Q)∨RP∧(Q∧R)(P∧Q)∧R⑷交換律P∨QQ∨PP∧QQ∧P56第五十六頁，共一百九十七頁，2022年，8月28日二、等價(jià)公式⑸分配律P∨(Q∧R)(P∨Q)∧(P∨R)P∧(Q∨R)(P∧Q)∨(P∧R)⑹吸收律P∨(P∧Q)PP∧(P∨Q)P⑺德-摩根定律(P∨Q)P∧Q

(P∧Q)P∨Q⑻同一律P∨FPP∧TP⑼零律P∨TTP∧FF⑽互補(bǔ)律P∨PTP∧PF57第五十七頁，共一百九十七頁，2022年，8月28日二、等價(jià)公式⑾PQP∨Q⑿PQQP⒀PQ(PQ)∧(QP)⒁PQ(P∨Q)∧(P∨Q)⒂PQ(P∧Q)∨(P∧Q)⒃(PQ)R(PQ)(PR)(P∧Q)R58第五十八頁，共一百九十七頁，2022年，8月28日二、等價(jià)公式⑴對合律~~AA~A表示A的絕對補(bǔ)集⑵冪等律A∪AAA∩AA⑶結(jié)合律A∪(B∪C)(A∪B)∪CA∩(B∩C)(A∩B)∩C⑷交換律A∪BB∪AA∩BB∩A⑸分配律A∪(B∩C)(A∪B)∩(A∪C)A∩(B∪C)(A∩B)∪(A∩C)59第五十九頁，共一百九十七頁，2022年，8月28日二、等價(jià)公式⑹吸收律A∪(A∩B)AA∩(A∪B)A⑺底-摩根定律~(A∪B)~A∩~B~(A∩B)~A∪~B⑻同一律A∪ΦA(chǔ)A∩EAE表示全集⑼零律A∪EEA∩ΦΦ⑽否定律A∪~AEA∩~AΦ60第六十頁，共一百九十七頁，2022年，8月28日4.等價(jià)公式的證明方法方法1：用列真值表。方法2：用公式的等價(jià)變換.(用置換定律)定義1-4.3

如果X是合式公式A的一部分，且X本身也是一合式公式，則稱X為公式A的子公式。定理1-4.1(置換定律)設(shè)X是合式公式A的子公式，若XY，如果將A中的X用Y來置換，則所得到公式B與公式A等價(jià)，即AB。61第六十一頁，共一百九十七頁，2022年，8月28日4.等價(jià)公式的證明方法例題1.求證吸收律P∧(P∨Q)P證明P∧(P∨Q)

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

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

P∨F(零律)

P(同一律)62第六十二頁，共一百九十七頁，2022年，8月28日4.等價(jià)公式的證明方法例題2.求證(P∨Q)→(P∧Q)P證明(P∨Q)→(P∧Q)

(P∨Q)∨(P∧Q)(公式E16)(P∧Q)∨(P∧Q)(摩根定律)(P∧Q)∨(P∧Q)(對合律)

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

P∧T(互補(bǔ)律)

P(同一律)公式E16：PQP∨Q63第六十三頁，共一百九十七頁，2022年，8月28日4.等價(jià)公式的證明方法例題3.化簡(P∧Q)→(P∨(P∨Q))解原公式(P∧Q)∨((P∨P)∨Q)(E16,結(jié)合)(P∧Q)∨(P∨Q)(對合律，冪等律)(P∧Q)∨(Q∨P)(交換律)((P∧Q)∨Q)∨P(結(jié)合律)Q∨P(吸收律)公式E16：PQP∨Q64第六十四頁，共一百九十七頁，2022年，8月28日5.等價(jià)性質(zhì)1).有自反性：任何命題公式A，有AA。2).有對稱性：若AB，則BA3).有傳遞性：若AB且BC，則AC4).如果A(P1,P2,…,Pn)B(P1,P2,…,Pn)，則A(P1,P2,…,Pn)B(P1,P2,…,Pn)例A(P,Q)P→QB(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)65第六十五頁，共一百九十七頁，2022年，8月28日5等價(jià)性質(zhì)試證語句：“不會休息的人也不會工作，沒有豐富知識的人也不會工作”，與語句“工作得好的人一定會休息并且有豐富的知識”，具有相同的邏輯含義。證明：設(shè)P：某人會工作

Q：某人會休息R：某人有豐富的知識

(Q→P)∧(R→P)P→(Q∧R)66第六十六頁，共一百九十七頁，2022年，8月28日1-5重言式與重言蘊(yùn)涵式

PP∨PP∧PFTFTTF

可見不論P(yáng)取什么真值P∨P

的真值總是為真，P∧P的真值總是為假。P∨P為重言式(永真式)，稱P∧P為矛盾式(永假式)。67第六十七頁，共一百九十七頁，2022年，8月28日例：

PQ(P∧Q)P∨Q(P∧Q)P∨QFFTTTFTTTTTFTTT

TTFFT公式(P∧Q)P∨Q，無論對P和Q的何種指派，其真值均為真68第六十八頁，共一百九十七頁，2022年，8月28日重言式和矛盾式定義1-5.1

A(P1,P2,…,Pn)是含有命題變元P1,P2,…,

Pn的命題公式，如不論對P1,P2,…,

Pn作任何指派，都使得A(P1,P2,…,

Pn)為真(假)，則稱之為重言式(矛盾式),也稱之為永真式(永假式)。定義1-5.2一命題公式若至少存在一個(gè)指派使其取真值為T，則稱此公式為可滿足公式。若至少存在一個(gè)指派使其取真值為假，則稱此公式為非重言式或非永真公式69第六十九頁，共一百九十七頁，2022年，8月28日3.相關(guān)性質(zhì)、定理3.相關(guān)性質(zhì)、定理（1）重言式的否定是矛盾式；矛盾式的否定是重言式。（2）定理1-5.1如果A，B是永真式，則(A∧B)、(A∨B)、(AB)和(AB)也都是永真式。證明：設(shè)A和B為兩個(gè)重言式，則不論A和B分量指派任何真值，總有A為T，B為T，故A∨BT,A∧BT.命題公式重言式可真可假式矛盾式可滿足公式非重言式70第七十頁，共一百九十七頁，2022年，8月28日（3）定理1-5.2

一個(gè)重言式，對同一分量都用任何合式公式置換，其結(jié)果仍為一重言式證明：由于重言式的真值與分量的指派無關(guān)，故對同一分量以任何合式公式置換后，重言式的真值仍永為T.

對于矛盾式也有類似于定理1-5.1和定理1-5.2的結(jié)果3.相關(guān)性質(zhì)、定理71第七十一頁，共一百九十七頁，2022年，8月28日定理1-5.2如果A是永真式，則A的置換例式也是永真式。置換例式：A(P1,P2,…,Pn)是含有命題變元P1,P2,…,

Pn的命題公式，如果用合式公式X替換某個(gè)Pi(如果Pi在A(P1,P2,…,Pn)中多處出現(xiàn)，則各處均用X替換)，其余變元不變，替換后得到新的公式B，則稱B是A(P1,P2,…,Pn)的置換例式。3.相關(guān)性質(zhì)、定理72第七十二頁，共一百九十七頁，2022年，8月28日

A:P∨(P∧((PQ)R))↓(DE)替換P↓置換例式B:(DE)∨((DE)∧(((DE)Q)R))

3.相關(guān)性質(zhì)、定理73第七十三頁，共一百九十七頁，2022年，8月28日（4）若兩個(gè)公式的雙條件是重言式，則此兩公式對任何指派存相同真值。反之亦然。即下面的定理1-5.3

定理1-5.3

設(shè)A、B為兩個(gè)命題公式，

AB當(dāng)且僅當(dāng)AB為一重言式。證明：（1）若AB，則A、B有相同的真值，即AB永為T.2）若AB為重言式，則AB永為T，故A、B的真值相同，即AB3.相關(guān)性質(zhì)、定理74第七十四頁，共一百九十七頁，2022年，8月28日4重言式的證明方法方法1：列真值表。方法2：公式的等價(jià)變換，化簡成“T”。方法3：用公式的主析取范式。75第七十五頁，共一百九十七頁，2022年，8月28日4重言式的證明方法方法1.列真值表。例如，證明(P∧(PQ))Q

為重言式。PQPQP∧(PQ)(P∧(PQ))QFFTFTFTTFTTFFFT

TTTTT76第七十六頁，共一百九十七頁，2022年，8月28日二.重言(永真)蘊(yùn)涵式定義1-5.3：當(dāng)且僅當(dāng)AB是一個(gè)重言式時(shí)，稱A重言(永真)蘊(yùn)涵B，記作AB。上式可以寫成(P∧(PQ))Q注意符號“”不是聯(lián)結(jié)詞，它是表示公式間的“永真蘊(yùn)涵”關(guān)系，也可以看成是“推導(dǎo)”關(guān)系。即AB可以理解成由A可推出B，即由A為真，可以推出B也為真。

77第七十七頁，共一百九十七頁，2022年，8月28日2.重言(永真)蘊(yùn)涵式證明方法方法1.列真值表。(即列永真式的真值表)這里就不再舉例了。

PQPQP∧(PQ)(P∧(PQ))QFFTFTFTTFTTFFFT

TTTTT78第七十八頁，共一百九十七頁，2022年，8月28日2.重言(永真)蘊(yùn)涵式證明方法先看一看AB的真值表，如果AB為永真式，則真值表的第三組指派不會出現(xiàn)。于是有下面兩種證明方法。ABA

BFFTFTTTFFTTT79第七十九頁，共一百九十七頁，2022年，8月28日2.重言(永真)蘊(yùn)涵式證明方法方法2.假設(shè)前件為真，推出后件也為真。求證：((A∧B)C)∧D∧(C∨D)A∨B證明:設(shè)前件((A∧B)C)∧D∧(C∨D)為真。則((A∧B)C)、D、(C∨D)均真，D為T，則D為F(C∨D)為T((A∧B)C為T得C為F得A∧B為F80第八十頁，共一百九十七頁，2022年，8月28日2.重言(永真)蘊(yùn)涵式證明方法如果A為F，則A為T，所以A∨B為T。如果B為F，則B為T，所以A∨B為T。((A∧B)C)∧D∧(C∨D)A∨B

81第八十一頁，共一百九十七頁，2022年，8月28日2.重言(永真)蘊(yùn)涵式證明方法方法3.假設(shè)后件為假，推出前件也為假。求證：((A∧B)C)∧D∧(C∨D)A∨B證明:假設(shè)后件A∨B為F,則A與B均為T。1.如C為F，則(A∧B)C為F，所以前件

((A∧B)C)∧D∧(C∨D)為F2.如C為T，則⑴若D為T，則D為F，所以前件((A∧B)C)∧D∧(C∨D)為假

⑵若D為F，則C∨D為F，所以前件((A∧B)C)∧D∧(C∨D)為假。((A∧B)C)∧D∧(C∨D)A∨B82第八十二頁，共一百九十七頁，2022年，8月28日（P∨Q)∧(PR)∧(QR)

R證明：利用的定義設(shè)前件：(P∨Q)∧(PR)∧(QR)為T

則P為T，PR為TQ為T，QR為T

都得出R為T即在前件為T的假定下推出后件R為T重言蘊(yùn)含式得證83第八十三頁，共一百九十七頁，2022年，8月28日3.重要的重言蘊(yùn)涵式

I1.P∧QPI2.P∧QQI3.PP∨QI4.QP∨QI5.PPQI6.QPQI7.(PQ)PI8.(PQ)QI9.P,QP∧QI10.P∧(P∨Q)QI11.P∧(PQ)QI12.Q∧(PQ)PI13.(PQ)∧(QR)PRI14.(P∨Q)∧(PR)∧(QR)RI15.AB(A∨C)(B∨C)I16.AB(A∧C)(B∧C)84第八十四頁，共一百九十七頁，2022年，8月28日3.重要的重言蘊(yùn)涵式等價(jià)式與蘊(yùn)含式之間的關(guān)系定理1-5.4

設(shè)P、Q為任意兩個(gè)命題公式，PQ的充分必要條件是PQ且QP。證明：（1）若PQ，則PQ為重言式，因?yàn)镻Q（PQ）∧(QP)，故PQ為T，即PQ，QP成立。（2）若PQ且QP，則PQ為T且QP也為T，因此PQ為T,PQ是重言式，即PQ85第八十五頁，共一百九十七頁，2022年，8月28日4.蘊(yùn)含常見的幾個(gè)性質(zhì)1).設(shè)A、B、C為合式公式，若AB且A重言式，則B必是重言式2).有自反性：對任何命題公式A，有AA3).有傳遞性：若AB且BC，則AC4).有反對稱性：若AB且BA，則AB符號“”表示“等價(jià)”。5)若AB，AC，那末A（B∧C)6)若AB,CB，則A∨CB本節(jié)重點(diǎn)掌握：永真式及永真蘊(yùn)涵式的定義、證明方法、以及常用的公式。作業(yè)：第23頁:(2)b)、(6)、(8)e)86第八十六頁，共一百九十七頁，2022年，8月28日1-6.其它聯(lián)結(jié)詞五個(gè)聯(lián)結(jié)詞：∧∨

其它聯(lián)結(jié)詞：

PQ

：同為假，異為真（異或）

PQ：(PQ)僅當(dāng)P為真，Q為假是為T（條件否定）

PQ：(P∧Q)（與非）

PQ：(P∨Q)（或非）共九個(gè)聯(lián)結(jié)詞c87第八十七頁，共一百九十七頁，2022年，8月28日1-6.其它聯(lián)結(jié)詞PQ聯(lián)1聯(lián)2聯(lián)3聯(lián)4聯(lián)5聯(lián)6聯(lián)7聯(lián)8T

TTFTTFFTFTFTFTFFTFTFTTFFTTFFTFFTFFFTTFT88第八十八頁，共一百九十七頁，2022年，8月28日1-6.其它聯(lián)結(jié)詞PQ聯(lián)9聯(lián)10聯(lián)11聯(lián)12聯(lián)13聯(lián)14聯(lián)15聯(lián)16TTTFTFTFTFTFTFFTFTTFFTTFTFFTFTFFFTTFTFTF89第八十九頁，共一百九十七頁，2022年，8月28日1-6.其它聯(lián)結(jié)詞命題聯(lián)結(jié)詞在命題演算中是通過真值表定義的。對2個(gè)變元，恰可構(gòu)成16個(gè)不等價(jià)的命題公式，n個(gè)變元，可構(gòu)成個(gè)但除常T、F及命題變元本身外，命題聯(lián)結(jié)詞有九個(gè)就夠了，九個(gè)也并非完全必要最小聯(lián)結(jié)詞組：對任何一個(gè)命題公式，都能由僅含這些聯(lián)結(jié)詞的命題公式等價(jià)代換n2290第九十頁，共一百九十七頁，2022年，8月28日1-6.其它聯(lián)結(jié)詞由九個(gè)聯(lián)結(jié)詞組成的命題公式，必可由{，∧}或{,∨}組成的命題公式代替為方便實(shí)用，命題公式常常同時(shí)包含{，∧,∨}91第九十一頁，共一百九十七頁，2022年，8月28日1-7.對偶與范式一、等價(jià)公式的對偶性從前面列出的等價(jià)公式看出，有很多是成對出現(xiàn)的。這就是等價(jià)公式的對偶性。⑴定義1-7.1

對偶式：在一個(gè)只含有聯(lián)結(jié)詞、∨、∧的公式A中，將∨換成∧，∧換成∨，T換成F，F(xiàn)換成T，其余部分不變，得到另一個(gè)公式A*，稱A與A*互為對偶式。92第九十二頁，共一百九十七頁，2022年，8月28日一、對偶例如:：AA*PPQ∧RQ∨R(P∨T)∧Q(P∧F)∨Q⑵用對偶式求公式的否定93第九十三頁，共一百九十七頁，2022年，8月28日一、對偶定理1-7.1

令A(yù)(P1,P2,…,Pn)是一個(gè)只含有聯(lián)結(jié)詞、∨、∧的命題公式，則A(P1,P2,…,Pn)A*(P1,P2,…,Pn)

此定理可以反復(fù)地使用底-摩根定律得以證明。

證明：令A(yù)(P,Q)P∨QA*(P,Q)P∧Q

A(P,Q)(P∨Q)A*(P,Q)P∧Q94第九十四頁，共一百九十七頁，2022年，8月28日一、對偶可見A(P,Q)A*(P,Q)

推論:A(P1,P2,…,Pn)A*(P1,P2,…,Pn)例1：（1）利用上述求公式的否定公式求(((P∧Q)∨(P∧Q))∨R)((P∨Q)∧(P∨Q))∧R2）求PQ，PQ的對偶式3）設(shè)A*(S,W,R)是S∧(W∨R)，證明A*(S,W,R)

A(S,W,R)95第九十五頁，共一百九十七頁，2022年，8月28日一、對偶⑶對偶原理(定理1-7.2)：令A(yù)(P1,P2,…,Pn)、B(P1,P2,…,Pn)是只含有聯(lián)結(jié)詞、∨、∧的命題公式，則如果A(P1,P2,…,Pn)B(P1,P2,…,Pn)則

A*(P1,P2,…,Pn)B*(P1,P2,…,

Pn)證明：因?yàn)锳(P1,P2,…,Pn)B(P1,P2,…,Pn)故A(P1,P2,…,Pn)B(P1,P2,…,Pn)96第九十六頁，共一百九十七頁，2022年，8月28日一、對偶而A(P1,P2,…,Pn)A*(P1,P2,…,Pn)B(P1,P2,…,Pn)B*(P1,P2,…,Pn)

故A*(P1,P2,…,Pn)B*(P1,P2,…,Pn)所以A*(P1,P2,…,Pn)B*(P1,

P2,…,

Pn)下面我們驗(yàn)證一下對偶原理：P∨(Q∧R)(P∨Q)∧(P∨R)AB97第九十七頁，共一百九十七頁，2022年，8月28日一、對偶P∧(Q∨R)(P∧Q)∨(P∧R)A*B*P∨TTABP∧FFA*B*本節(jié)要求掌握對偶式、及對偶原理的應(yīng)用。作業(yè)：第39頁(6)98第九十八頁，共一百九十七頁，2022年，8月28日二、范式范式就是命題公式形式的規(guī)范形式。這里約定在范式中只含有聯(lián)結(jié)詞、∨和∧。(一)析取范式與合取范式（定義1-7.2/3）1.合取式與析取式

合取式：是用“∧”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。如P、P、P∧Q、P∧Q∧R

析取式：是用“∨”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。99第九十九頁，共一百九十七頁，2022年，8月28日二、范式如P、P、P∨Q、P∨Q∨R注:∵P∨PPP∧PP∴P是合(析)取式.2.析取范式公式A如果寫成如下形式：A1∨A2∨...∨An(n≥1)其中每個(gè)Ai(i=1,2..n)是合取式，稱之為A的析取范式。

100第一百頁，共一百九十七頁，2022年，8月28日二、范式3.合取范式公式A如果寫成如下形式：A1∧A2∧...∧An(n≥1)

其中每個(gè)Ai(i=1,2..n)是析取式，稱之為A的合取范式。例如，PQ的析取范式與合取范式：PQ(P∧Q)∨(P∧Q)----析取范式PQ(P∨Q)∧(P∨Q)----合取范式101第一百零一頁，共一百九十七頁，2022年，8月28日二、范式4.析取范式與合取范式的寫法⑴先用相應(yīng)的公式去掉和；將公式中的聯(lián)結(jié)詞化歸成包含，∧,∨式子公式E16PQP∨Q公式E21PQ(P∧Q)∨(P∧Q)公式E20PQ(PQ)∧(QP)再用E16PQ(P∨Q)∧(P∨Q)102第一百零二頁，共一百九十七頁，2022年，8月28日二、范式⑵用公式的否定公式或摩根定律將后移到命題變元之前。

A(P1,P2,…,Pn)A*(P1,P2,…,Pn)底-摩根定律(P∨Q)P∧Q

(P∧Q)P∨Q⑶用分配律、冪等律等公式進(jìn)行整理，使之成為所要求析取范式與合取范式。

103第一百零三頁，共一百九十七頁，2022年，8月28日二、范式一公式的析取范式與合取范式并不唯一，為使任意一個(gè)命題公式，化成唯一的等價(jià)命題的標(biāo)準(zhǔn)形式，采用主范式來統(tǒng)一例2：求(PQ)R的析取范式與合取范式(PQ)R((P∨Q)∧(P∨Q))∨R(P∧Q)∨(P∧Q)∨R------析取范式(PQ)R((P∧Q)∨(P∧Q))∨R((P∨Q)∧(P∨Q))∨R(P∨Q∨R)∧(P∨Q∨R)---合取范式104第一百零四頁，共一百九十七頁，2022年，8月28日二、范式(二)主析取范式與主合取范式一個(gè)公式的析取范式與合取范式的形式是不唯一的。下面定義形式唯一的主析取范式與主合取范式。㈠主析取范式1.小項(xiàng)(布爾合取)⑴定義1-7.4：在一個(gè)有n個(gè)命題變元的合取式中，每個(gè)變元與其否定不能同時(shí)存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次，稱這個(gè)合取式是個(gè)小項(xiàng)。105第一百零五頁，共一百九十七頁，2022年，8月28日二、范式例如，有兩個(gè)變元的小項(xiàng)：

P∧Q、P∧Q、P∧Q、P∧Q⑵小項(xiàng)的性質(zhì)

m3m2m1

m0PQP∧QP∧QP∧QP∧Q00FFFF