關(guān)于真值表公式分類命題定律代入置換第1頁，課件共39頁，創(chuàng)作于2023年2月復(fù)習(xí)引論：離散數(shù)學(xué)、數(shù)理邏輯命題聯(lián)結(jié)詞第2頁，課件共39頁，創(chuàng)作于2023年2月復(fù)習(xí)題：本命題是假的。我不給所有自己給自己理發(fā)的人理發(fā)，但是卻會(huì)給所有自己不給自己理發(fā)的人理發(fā)。第3頁，課件共39頁，創(chuàng)作于2023年2月本節(jié)內(nèi)容命題符號(hào)化第4頁，課件共39頁，創(chuàng)作于2023年2月命題分類與命題變?cè)}原子命題：不包含任何聯(lián)結(jié)詞的命題復(fù)合命題：至少包含一個(gè)聯(lián)結(jié)詞的命題命題變?cè)粋€(gè)不確定的泛指的任意命題定義：以真(1)、假(0)為其變域的變?cè)⒁猓好}變?cè)皇敲}，只有用一個(gè)特定的命題取代才能確定它的真值：真或假（對(duì)該命題變?cè)概烧嬷担┟}公式含有命題變?cè)臄嘌苑Q為命題公式注意：不是所有由命題變?cè)?、?lián)結(jié)詞和括號(hào)所組成的字符串都能成為命題公式。第5頁，課件共39頁，創(chuàng)作于2023年2月合式公式原子公式定義：?jiǎn)蝹€(gè)命題變?cè)兔}常元稱為原子命題公式，簡(jiǎn)稱原子公式。合式公式合式公式是由下列規(guī)則生成的公式：①單個(gè)原子公式是合式公式。②若A是一個(gè)合式公式，則(lA)也是一個(gè)合式公式。③若A、B是合式公式，則(A∧B)、(A∨B)、(A→B)和(AB)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。第6頁，課件共39頁，創(chuàng)作于2023年2月合式公式(Cont.)例：下列符號(hào)串是否為命題公式。（1）P→(Q∧PR）；

（2）（P∨Q）→（?（Q∧R））第7頁，課件共39頁，創(chuàng)作于2023年2月合式公式(Cont.)當(dāng)合式公式比較復(fù)雜時(shí)，常常使用很多圓括號(hào)，為了減少圓括號(hào)的使用量，可作以下約定：①優(yōu)先級(jí)由高到低的次序?yàn)椋簂、∧、∨、→、②相同的聯(lián)結(jié)詞按從左至右次序計(jì)算時(shí)，圓括號(hào)可省略。③最外層的圓括號(hào)可以省略。

第8頁，課件共39頁，創(chuàng)作于2023年2月合式公式(Cont.)例子

?P∨?P∨Q∧?S∨?Q∧R

與(((?(P)∨?(P))∨(Q∧?(S))∨(?(Q)∧R))

運(yùn)算順序完全一樣,前者不加一個(gè)括號(hào).

請(qǐng)大家特別注意先∧后∨的習(xí)慣.第9頁，課件共39頁，創(chuàng)作于2023年2月命題符號(hào)化

有了聯(lián)結(jié)詞的合式公式概念，我們可以把自然語言中的有些語句，翻譯成數(shù)理邏輯中的符號(hào)形式第10頁，課件共39頁，創(chuàng)作于2023年2月命題的符號(hào)化把一個(gè)用文字?jǐn)⑹龅拿}相應(yīng)地寫成由命題標(biāo)識(shí)符、聯(lián)結(jié)詞和圓括號(hào)表示的合式公式，稱為命題的符號(hào)化。符號(hào)化應(yīng)注意以下幾點(diǎn)：①確定句子是否為命題.不是就不必翻譯.②確定句中連接詞是否能對(duì)應(yīng)于并且對(duì)應(yīng)于哪一個(gè)命題連接詞.③正確表示原子命題和選擇命題連接詞.④要按邏輯關(guān)系翻譯而不能憑字面翻譯.第11頁，課件共39頁，創(chuàng)作于2023年2月命題的符號(hào)化(Cont.)例：試以符號(hào)形式寫出命題:我們要做到身體好,學(xué)習(xí)好,工作好,為祖國(guó)四化建設(shè)而奮斗.解:A:我們要做到身體好

B:我們要做到學(xué)習(xí)好

C:我們要做到工作好

P:我們要為祖國(guó)四化建設(shè)而奮斗故命題可以表示為:第12頁，課件共39頁，創(chuàng)作于2023年2月命題的符號(hào)化(Cont.)張三和李四同在做作業(yè)

P:張三做作業(yè)

Q:李四做作業(yè) 可譯為P∧Q;張三和李四是兄弟

第13頁，課件共39頁，創(chuàng)作于2023年2月命題的符號(hào)化(Cont.)“這盆花盛開，促使那些蜜蜂來采蜜”不可以符號(hào)化,為什么呢？ 因?yàn)檫B接詞‘促使’不是命題連接詞.根據(jù)是由它構(gòu)成的復(fù)合命題的真值不能完全由構(gòu)成它的原子命題的真值來確定.例如令P:這盆花盛開,值為1，Q:那些蜜蜂來采蜜,其值為1,則‘這盆花盛開促使那些蜜蜂來采蜜’值為1.又令P:海水是咸的,其值為1,Q:那些蜜蜂來采蜜值為1,則‘海水是咸的促使那些蜜蜂來采蜜’值為0.

由此可見,兩組原命題都為真,但由‘促使’構(gòu)成的復(fù)合命題的值一為真一為假,這不符合定義.第14頁，課件共39頁，創(chuàng)作于2023年2月注意

自然語言中的一些聯(lián)結(jié)詞,如與”,“且”,“或”,“除非…則…”等等都各有其具體含義,需分別不同情況翻譯成合適的邏輯聯(lián)結(jié)詞.

有時(shí)可以采用真值表的方式,來尋找合適的邏輯聯(lián)結(jié)詞第15頁，課件共39頁，創(chuàng)作于2023年2月練習(xí)題派小王或小李出差；我們不能既劃船又跑步；如果你來了，那么他唱不唱歌將看你是否伴奏而定；如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者；假如上午不下雨，我去看電影，否則就在家里看書。辱罵和恐嚇決不是戰(zhàn)斗除非天氣好，否則我是不會(huì)去公園的第16頁，課件共39頁，創(chuàng)作于2023年2月幾個(gè)例子‘除非你努力，否則你將失敗’可以符號(hào)化為：

?P→Q,其中P:你努力，Q:你將失敗.‘只有睡好覺才能恢復(fù)疲勞’可以符號(hào)化為：Q→P,其中P:睡好覺，Q:恢復(fù)疲勞.(Q是P的必要條件)第17頁，課件共39頁，創(chuàng)作于2023年2月公式真值表真值指派為含有命題變?cè)狿1，P2，…,Pn的命題公式，對(duì)P1，P2，…,Pn分別指定一個(gè)真值，稱為對(duì)公式的一組真值指派。在公式中，對(duì)于命題變?cè)概烧嬷档母鞣N可能組合，就確定了這個(gè)命題的各種真值情況，把它匯列成表，就是命題公式的真值表公式真值表構(gòu)造方法：（1）找出公式中的全部命題變?cè)?，并按一定的順序排列成P1，P2，…,Pn。（2）列出的2n個(gè)解釋，賦值從00…0（n個(gè)）開始，按二進(jìn)制遞加順序依次寫出各賦值，直到11…1為止（或從11…1開始，按二進(jìn)制遞減順序?qū)懗龈髻x值，直到00…0為止），然后從低到高的順序列出的層次。（3）根據(jù)賦值依次計(jì)算各層次的真值并最終計(jì)算出的真值。第18頁，課件共39頁，創(chuàng)作于2023年2月公式真值表(Cont.)例1：構(gòu)造PQ的真值表例2：構(gòu)造?P∨Q的真值表第19頁，課件共39頁，創(chuàng)作于2023年2月公式分類定義：設(shè)A為任意公式，則①對(duì)應(yīng)每一個(gè)指派，公式A均相應(yīng)確定真值為真，稱A

為重言式，或永真式。②對(duì)應(yīng)每一個(gè)指派，公式A均相應(yīng)確定真值為假，稱A

為矛盾式，或永假式。③至少存在一個(gè)指派，公式A相應(yīng)確定真值為真，稱A為可滿足式。第20頁，課件共39頁，創(chuàng)作于2023年2月公式分類(Cont.)由定義可知，重言式必是可滿足式，反之一般不真。重點(diǎn)將研究重言式，它最有用，因?yàn)樗幸韵绿攸c(diǎn)：①重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。②兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。③由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價(jià)式和蘊(yùn)涵式。第21頁，課件共39頁，創(chuàng)作于2023年2月公式分類(Cont.)判定給定公式是否為永真式、永假式或可滿足式的問題，稱為給定公式的判定問題。在Ls中，由于任何一個(gè)命題公式的指派數(shù)目總是有限的，所以Ls的判定問題是可解的。其判定方法有真值表法和公式推演法。第22頁，課件共39頁，創(chuàng)作于2023年2月等價(jià)公式定義：設(shè)A和B是兩個(gè)命題公式，設(shè)P1,P2,…,Pn為所有出現(xiàn)于A和B中的命題變?cè)?若給P1,P2,…,Pn任一組真值指派,A和B的真值都是相同的，則稱A和B是等價(jià)的，或邏輯相等，記作AB，讀作A等價(jià)B，稱AB為等價(jià)式。

若公式A和B的真值表是相同的，則A和B等價(jià)。因此，驗(yàn)證兩公式是否等價(jià)，只需做出它們的真值表即可。第23頁，課件共39頁，創(chuàng)作于2023年2月和的區(qū)別與聯(lián)系區(qū)別：是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語言中的符號(hào)，它出現(xiàn)在命題公式中；不是邏輯聯(lián)結(jié)詞，屬于元語言中的符號(hào)，表示兩個(gè)命題公式的一種關(guān)系，不屬于這兩個(gè)公式的任何一個(gè)公式中的符號(hào)。聯(lián)系：定理：

A

B當(dāng)且僅當(dāng)AB是永真式。第24頁，課件共39頁，創(chuàng)作于2023年2月等價(jià)公式的性質(zhì)①自反性，即對(duì)任意公式A，有A

A。②對(duì)稱性，即對(duì)任意公式A和B，若A

B，則B

A。③傳遞性，即對(duì)任意公式A、B和C，若A

B、B

C，則A

C。第25頁，課件共39頁，創(chuàng)作于2023年2月基本等價(jià)式——命題定律在判定公式間是否等價(jià)，有一些簡(jiǎn)單而又經(jīng)常使用的等價(jià)式，稱為基本等價(jià)式或稱命題定律。牢固地記住它并能熟練運(yùn)用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一。第26頁，課件共39頁，創(chuàng)作于2023年2月(1)雙否定：AA。(2)交換律：A∧BB∧A，A∨BB∨A，ABBA。第27頁，課件共39頁，創(chuàng)作于2023年2月(3)結(jié)合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(4)分配律：A∧(B∨C)(A∧B)∨(A∧C)，A∨(B∧C)(A∨B)∧(A∨C)。(5)德·摩根律：(A∧B)A∨B，(A∨B)A∧B。(6)等冪律：A∧AA，A∨AA。第28頁，課件共39頁，創(chuàng)作于2023年2月(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互補(bǔ)律：A∧AF，(矛盾律) A∨AT。(排中律)(11)條件式轉(zhuǎn)化律：A→BA∨B，A→BB→A。第29頁，課件共39頁，創(chuàng)作于2023年2月(12)雙條件式轉(zhuǎn)化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)AB(AB)(13)輸出律：(A∧B)→CA→(B→C)。(14)歸謬律：(A→B)∧(A→B)A。上面這些定律，即是通常所說的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。第30頁，課件共39頁，創(chuàng)作于2023年2月代入規(guī)則和替換規(guī)則

在定義合成公式時(shí)，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個(gè)意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替換”，它們也有從已知公式得到新的公式的作用。第31頁，課件共39頁，創(chuàng)作于2023年2月代入規(guī)則定理1.3.2

在一個(gè)永真式A中，任何一個(gè)原子命題變?cè)猂出現(xiàn)的每一處，用另一個(gè)公式代入，所得公式B仍是永真式。本定理稱為代入規(guī)則。例子：課本例1.3.4第32頁，課件共39頁，創(chuàng)作于2023年2月替換規(guī)則定理1.3.3

設(shè)A1是合式公式A的子公式，若A1B1，并且將A中的A1用B1替換得到公式B，則AB。稱該定理為替換規(guī)則。滿足定理1.3.3條件的替換，稱為等價(jià)替換。例子：課本例1.3.5&例1.3.6第33頁，課件共39頁，創(chuàng)作于2023年2月代入和替換有兩點(diǎn)區(qū)別： ①代入是對(duì)原子命題變?cè)缘?，而替換可對(duì)命題公式實(shí)行。 ②代入必須是處處代入，替換則可部分替換，亦可全部替換。第34頁，課件共39頁，創(chuàng)作于2023年2月總結(jié)真值表公式分類、等價(jià)公式命題定律代入置換第35頁，課件共39頁，創(chuàng)作