真值表、公式分類(lèi)、命題定律、代入置換.ppt

1、符號(hào)化、公式分類(lèi)命題定律、代入置換,授課教師：程文剛 ,復(fù)習(xí),引論：離散數(shù)學(xué)、數(shù)理邏輯 命題 聯(lián)結(jié)詞,復(fù)習(xí)題：,本命題是假的。 我不給所有自己給自己理發(fā)的人理發(fā)，但是卻會(huì)給所有自己不給自己理發(fā)的人理發(fā)。,本節(jié)內(nèi)容,命題符號(hào)化,命題分類(lèi)與命題變?cè)?命題 原子命題：不包含任何聯(lián)結(jié)詞的命題 復(fù)合命題：至少包含一個(gè)聯(lián)結(jié)詞的命題 命題變?cè)?一個(gè)不確定的泛指的任意命題 定義： 以真(1)、假(0)為其變域的變?cè)?注意：命題變?cè)皇敲}，只有用一個(gè)特定的命題取代才能確定它的真值：真或假（對(duì)該命題變?cè)概烧嬷担?命題公式 含有命題變?cè)臄嘌苑Q(chēng)為命題公式 注意：不是所有由命題變?cè)?、?lián)結(jié)詞和括號(hào)所組成的字符串都能

2、成為命題公式。,合式公式,原子公式 定義：?jiǎn)蝹€(gè)命題變?cè)兔}常元稱(chēng)為原子命題公式，簡(jiǎn)稱(chēng)原子公式。 合式公式 合式公式是由下列規(guī)則生成的公式： 單個(gè)原子公式是合式公式。 若A是一個(gè)合式公式，則(lA)也是一個(gè)合式公式。 若A、B是合式公式，則(AB)、(AB)、(AB)和(A B)都是合式公式。 只有有限次使用、和生成的公式才是合式公式。,合式公式(Cont.),例：下列符號(hào)串是否為命題公式。 （1） P(QPR）； （2）（PQ）（QR）,合式公式(Cont.),當(dāng)合式公式比較復(fù)雜時(shí)，常常使用很多圓括號(hào)，為了減少圓括號(hào)的使用量，可作以下約定： 優(yōu)先級(jí)由高到低的次序?yàn)椋簂、 相同的聯(lián)結(jié)詞按從左至

3、右次序計(jì)算時(shí)，圓括號(hào)可省略。 最外層的圓括號(hào)可以省略。,合式公式(Cont.),例子 PPQSQR 與 (P)(P)(Q(S)(Q)R) 運(yùn)算順序完全一樣,前者不加一個(gè)括號(hào). 請(qǐng)大家特別注意先后的習(xí)慣.,命題符號(hào)化,有了聯(lián)結(jié)詞的合式公式概念，我們可以把自然語(yǔ)言中的有些語(yǔ)句，翻譯成數(shù)理邏輯中的符號(hào)形式,命題的符號(hào)化,把一個(gè)用文字?jǐn)⑹龅拿}相應(yīng)地寫(xiě)成由命題標(biāo)識(shí)符、聯(lián)結(jié)詞和圓括號(hào)表示的合式公式，稱(chēng)為命題的符號(hào)化。 符號(hào)化應(yīng)注意以下幾點(diǎn)： 確定句子是否為命題.不是就不必翻譯. 確定句中連接詞是否能對(duì)應(yīng)于并且對(duì)應(yīng)于哪一個(gè)命題連接詞. 正確表示原子命題和選擇命題連接詞. 要按邏輯關(guān)系翻譯而不能憑字面翻譯.

4、,命題的符號(hào)化(Cont.),例：試以符號(hào)形式寫(xiě)出命題: 我們要做到身體好,學(xué)習(xí)好,工作好,為祖國(guó)四化建設(shè)而奮斗. 解: A:我們要做到身體好 B:我們要做到學(xué)習(xí)好 C:我們要做到工作好 P:我們要為祖國(guó)四化建設(shè)而奮斗 故命題可以表示為:,命題的符號(hào)化(Cont.),張三和李四同在做作業(yè) P:張三做作業(yè) Q:李四做作業(yè) 可譯為PQ; 張三和李四是兄弟,命題的符號(hào)化(Cont.),“這盆花盛開(kāi)，促使那些蜜蜂來(lái)采蜜”不可以符號(hào)化,為什么呢？ 因?yàn)檫B接詞促使不是命題連接詞.根據(jù)是由它構(gòu)成的復(fù)合命題的真值不能完全由構(gòu)成它的原子命題的真值來(lái)確定. 例如令 P:這盆花盛開(kāi),值為1，Q:那些蜜蜂來(lái)采蜜,其值

5、為1,則這盆花盛開(kāi)促使那些蜜蜂來(lái)采蜜值為1.又令 P:海水是咸的,其值為1,Q:那些蜜蜂來(lái)采蜜值為1,則海水是咸的促使那些蜜蜂來(lái)采蜜 值為0. 由此可見(jiàn),兩組原命題都為真,但由促使構(gòu)成的復(fù)合命題的值一為真一為假,這不符合定義.,注意,自然語(yǔ)言中的一些聯(lián)結(jié)詞,如與”,“且”, “或”,“除非 則 ”等等都各有其具體含義, 需分別不同情況翻譯成合適的邏輯聯(lián)結(jié)詞. 有時(shí)可以采用真值表的方式,來(lái)尋找合適的邏輯聯(lián)結(jié)詞,練習(xí)題,派小王或小李出差； 我們不能既劃船又跑步； 如果你來(lái)了，那么他唱不唱歌將看你是否伴奏而定； 如果李明是體育愛(ài)好者，但不是文藝愛(ài)好者，那么李明不是文體愛(ài)好者； 假如上午不下雨，我去看

6、電影，否則就在家里看書(shū)。 辱罵和恐嚇決不是戰(zhàn)斗 除非天氣好，否則我是不會(huì)去公園的,幾個(gè)例子,除非你努力，否則你將失敗 可以符號(hào)化為： PQ,其中 P:你努力，Q:你將失敗. 只有睡好覺(jué)才能恢復(fù)疲勞可以符號(hào)化為：QP,其中 P:睡好覺(jué)，Q:恢復(fù)疲勞.(Q是P的必要條件),公式真值表,真值指派 為含有命題變?cè)狿1，P2，,Pn的命題公式，對(duì)P1，P2，,Pn分別指定一個(gè)真值，稱(chēng)為對(duì)公式的一組真值指派。 在公式中，對(duì)于命題變?cè)概烧嬷档母鞣N可能組合，就確定了這個(gè)命題的各種真值情況，把它匯列成表，就是命題公式的真值表 公式真值表構(gòu)造方法： （1）找出公式中的全部命題變?cè)匆欢ǖ捻樞蚺帕谐蒔1，P2

7、，,Pn 。 （2）列出的2n個(gè)解釋?zhuān)x值從000（n個(gè)）開(kāi)始，按二進(jìn)制遞加順序依次寫(xiě)出各賦值，直到111為止（或從111開(kāi)始，按二進(jìn)制遞減順序?qū)懗龈髻x值，直到000為止），然后從低到高的順序列出的層次。 （3）根據(jù)賦值依次計(jì)算各層次的真值并最終計(jì)算出的真值。,公式真值表(Cont.),例1：構(gòu)造P Q的真值表 例2：構(gòu)造P Q的真值表,公式分類(lèi),定義： 設(shè) A 為任意公式，則 對(duì)應(yīng)每一個(gè)指派，公式 A 均相應(yīng)確定真值為真，稱(chēng) A 為重言式，或永真式。 對(duì)應(yīng)每一個(gè)指派，公式 A 均相應(yīng)確定真值為假，稱(chēng) A 為矛盾式，或永假式。 至少存在一個(gè)指派，公式 A 相應(yīng)確定真值為真，稱(chēng) A 為可滿(mǎn)足式。

8、,公式分類(lèi)(Cont.),由定義可知，重言式必是可滿(mǎn)足式，反之一般不真。 重點(diǎn)將研究重言式，它最有用，因?yàn)樗幸韵绿攸c(diǎn)： 重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。 兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。 由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價(jià)式和蘊(yùn)涵式。,公式分類(lèi)(Cont.),判定給定公式是否為永真式、永假式或可滿(mǎn)足式的問(wèn)題，稱(chēng)為給定公式的判定問(wèn)題。 在Ls中，由于任何一個(gè)命題公式的指派數(shù)目總是有限的，所以Ls的判定問(wèn)題是可解的。其判定方法有真值表法和公式推演法。,等價(jià)公式,定義：設(shè)A和B是兩個(gè)命題

9、公式，設(shè)P1,P2, ,Pn為所有出現(xiàn)于A和B中的命題變?cè)? 若給P1,P2, ,Pn任一組真值指派, A和B的真值都是相同的，則稱(chēng)A和B是等價(jià)的，或邏輯相等，記作AB，讀作A等價(jià)B，稱(chēng)AB為等價(jià)式。 若公式A和B的真值表是相同的，則A和B等價(jià)。因此，驗(yàn)證兩公式是否等價(jià)，只需做出它們的真值表即可。,和的區(qū)別與聯(lián)系,區(qū)別：是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語(yǔ)言中的符號(hào)，它出現(xiàn)在命題公式中；不是邏輯聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，表示兩個(gè)命題公式的一種關(guān)系，不屬于這兩個(gè)公式的任何一個(gè)公式中的符號(hào)。 聯(lián)系： 定理： A B當(dāng)且僅當(dāng)AB是永真式。,等價(jià)公式的性質(zhì), 自反性，即對(duì)任意公式A，有A A。 對(duì)稱(chēng)性，即對(duì)任意

10、公式A和B，若A B，則B A。 傳遞性，即對(duì)任意公式A、B和C，若A B、B C，則A C。,基本等價(jià)式命題定律,在判定公式間是否等價(jià)，有一些簡(jiǎn)單而又經(jīng)常使用的等價(jià)式，稱(chēng)為基本等價(jià)式或稱(chēng)命題定律。牢固地記住它并能熟練運(yùn)用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一。,(1)雙否定：AA。 (2)交換律：ABBA，ABBA，ABBA。,(3) 結(jié)合律：(AB)CA(BC)，(AB)CA(BC)，(AB)CA(BC)。 (4) 分配律：A(BC)(AB)(AC)，A(BC)(AB)(AC)。 (5) 德摩根律：(AB)AB，(AB)AB。 (6) 等冪律：AAA，AAA。,(7) 同一律：ATA，AFA。 (8)

11、 零 律：AFF，ATT。 (9) 吸收律：A(AB)A，A(AB)A。 (10) 互補(bǔ)律：AAF，(矛盾律) AAT。(排中律) (11) 條件式轉(zhuǎn)化律：ABAB，ABBA。,(12) 雙條件式轉(zhuǎn)化律：AB(AB)(BA)(AB)(AB) AB(AB) (13) 輸出律：(AB)CA(BC)。 (14) 歸謬律：(AB)(AB)A。 上面這些定律，即是通常所說(shuō)的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。,代入規(guī)則和替換規(guī)則,在定義合成公式時(shí)，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個(gè)意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替

12、換”，它們也有從已知公式得到新的公式的作用。,代入規(guī)則,定理1.3.2 在一個(gè)永真式A中，任何一個(gè)原子命題變?cè)猂出現(xiàn)的每一處， 用另一個(gè)公式代入，所得公式B仍是永真式。本定理稱(chēng)為代入規(guī)則。 例子 ：課本例1.3.4,替換規(guī)則,定理1.3.3 設(shè)A1是合式公式A的子公式，若A1B1，并且將A中的A1用B1 替換得到公式B，則AB。稱(chēng)該定理為替換規(guī)則。 滿(mǎn)足定理1.3.3條件的替換，稱(chēng)為等價(jià)替換。 例子：課本 例1.3.5 & 例1.3.6,代入和替換有兩點(diǎn)區(qū)別： 代入是對(duì)原子命題變?cè)缘?，而替換可對(duì)命題公式實(shí)行。 代入必須是處處代入，替換則可部分替換，亦可全部替換。,總結(jié),真值表 公式分類(lèi)、等價(jià)公式 命題