真值表公式分類命題定律代入置換

1、符號化、公式分類命題定律、代入置換授課教師：程文剛 1復(fù)習(xí)引論：離散數(shù)學(xué)、數(shù)理邏輯命題聯(lián)結(jié)詞2復(fù)習(xí)題：本命題是假的。我不給所有自己給自己理發(fā)的人理發(fā)，但是卻會給所有自己不給自己理發(fā)的人理發(fā)。3本節(jié)內(nèi)容命題符號化4命題分類與命題變元命題原子命題：不包含任何聯(lián)結(jié)詞的命題復(fù)合命題：至少包含一個聯(lián)結(jié)詞的命題命題變元一個不確定的泛指的任意命題定義：以真(1)、假(0)為其變域的變元注意：命題變元不是命題，只有用一個特定的命題取代才能確定它的真值：真或假（對該命題變元指派真值）命題公式含有命題變元的斷言稱為命題公式注意：不是所有由命題變元、聯(lián)結(jié)詞和括號所組成的字符串都能成為命題公式。5合式公式原子公式定義

2、：單個命題變元和命題常元稱為原子命題公式，簡稱原子公式。合式公式合式公式是由下列規(guī)則生成的公式：單個原子公式是合式公式。若A是一個合式公式，則(lA)也是一個合式公式。若A、B是合式公式，則(AB)、(AB)、(AB)和(A B)都是合式公式。只有有限次使用、和生成的公式才是合式公式。6合式公式(Cont.)例：下列符號串是否為命題公式。 （1） P(QPR）； （2）（PQ）（QR）7合式公式(Cont.)當合式公式比較復(fù)雜時，常常使用很多圓括號，為了減少圓括號的使用量，可作以下約定：優(yōu)先級由高到低的次序為：l、 相同的聯(lián)結(jié)詞按從左至右次序計算時，圓括號可省略。最外層的圓括號可以省略。8合式

3、公式(Cont.)例子 PPQSQR 與 (P)(P)(Q(S)(Q)R) 運算順序完全一樣,前者不加一個括號. 請大家特別注意先后的習(xí)慣.9命題符號化有了聯(lián)結(jié)詞的合式公式概念，我們可以把自然語言中的有些語句，翻譯成數(shù)理邏輯中的符號形式10命題的符號化把一個用文字敘述的命題相應(yīng)地寫成由命題標識符、聯(lián)結(jié)詞和圓括號表示的合式公式，稱為命題的符號化。符號化應(yīng)注意以下幾點： 確定句子是否為命題.不是就不必翻譯. 確定句中連接詞是否能對應(yīng)于并且對應(yīng)于哪一個命題連接詞. 正確表示原子命題和選擇命題連接詞. 要按邏輯關(guān)系翻譯而不能憑字面翻譯.11命題的符號化(Cont.)例：試以符號形式寫出命題: 我們要做

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

5、Q:那些蜜蜂來采蜜值為1,則海水是咸的促使那些蜜蜂來采蜜 值為0. 由此可見,兩組原命題都為真,但由促使構(gòu)成的復(fù)合命題的值一為真一為假,這不符合定義.14注意自然語言中的一些聯(lián)結(jié)詞,如與”,“且”, “或”,“除非 則 ”等等都各有其具體含義, 需分別不同情況翻譯成合適的邏輯聯(lián)結(jié)詞.有時可以采用真值表的方式,來尋找合適的邏輯聯(lián)結(jié)詞15練習(xí)題派小王或小李出差；我們不能既劃船又跑步；如果你來了，那么他唱不唱歌將看你是否伴奏而定；如果李明是體育愛好者，但不是文藝愛好者，那么李明不是文體愛好者；假如上午不下雨，我去看電影，否則就在家里看書。辱罵和恐嚇決不是戰(zhàn)斗除非天氣好，否則我是不會去公園的16幾個例

6、子除非你努力，否則你將失敗 可以符號化為： PQ,其中 P:你努力，Q:你將失敗.只有睡好覺才能恢復(fù)疲勞可以符號化為：QP,其中 P:睡好覺，Q:恢復(fù)疲勞.(Q是P的必要條件)17公式真值表真值指派為含有命題變元P1，P2，,Pn的命題公式，對P1，P2，,Pn分別指定一個真值，稱為對公式的一組真值指派。在公式中，對于命題變元指派真值的各種可能組合，就確定了這個命題的各種真值情況，把它匯列成表，就是命題公式的真值表公式真值表構(gòu)造方法：（1）找出公式中的全部命題變元，并按一定的順序排列成P1，P2，,Pn 。（2）列出的2n個解釋，賦值從000（n個）開始，按二進制遞加順序依次寫出各賦值，直到1

7、11為止（或從111開始，按二進制遞減順序?qū)懗龈髻x值，直到000為止），然后從低到高的順序列出的層次。（3）根據(jù)賦值依次計算各層次的真值并最終計算出的真值。18公式真值表(Cont.)例1：構(gòu)造P Q的真值表例2：構(gòu)造P Q的真值表19公式分類定義： 設(shè) A 為任意公式，則 對應(yīng)每一個指派，公式 A 均相應(yīng)確定真值為真，稱 A 為重言式，或永真式。 對應(yīng)每一個指派，公式 A 均相應(yīng)確定真值為假，稱 A 為矛盾式，或永假式。 至少存在一個指派，公式 A 相應(yīng)確定真值為真，稱 A 為可滿足式。20公式分類(Cont.)由定義可知，重言式必是可滿足式，反之一般不真。重點將研究重言式，它最有用，因為它

8、有以下特點：重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡單的重言式可構(gòu)造出復(fù)雜的重言式。由重言式使用公認的規(guī)則可以產(chǎn)生許多有用等價式和蘊涵式。21公式分類(Cont.)判定給定公式是否為永真式、永假式或可滿足式的問題，稱為給定公式的判定問題。在Ls中，由于任何一個命題公式的指派數(shù)目總是有限的，所以Ls的判定問題是可解的。其判定方法有真值表法和公式推演法。22等價公式定義：設(shè)A和B是兩個命題公式，設(shè)P1,P2, ,Pn為所有出現(xiàn)于A和B中的命題變元, 若給P1,P2, ,Pn任一組真值指派, A和B的真值

9、都是相同的，則稱A和B是等價的，或邏輯相等，記作AB，讀作A等價B，稱AB為等價式。 若公式A和B的真值表是相同的，則A和B等價。因此，驗證兩公式是否等價，只需做出它們的真值表即可。23和的區(qū)別與聯(lián)系區(qū)別：是邏輯聯(lián)結(jié)詞，屬于目標語言中的符號，它出現(xiàn)在命題公式中；不是邏輯聯(lián)結(jié)詞，屬于元語言中的符號，表示兩個命題公式的一種關(guān)系，不屬于這兩個公式的任何一個公式中的符號。聯(lián)系：定理： A B當且僅當AB是永真式。24等價公式的性質(zhì) 自反性，即對任意公式A，有A A。 對稱性，即對任意公式A和B，若A B，則B A。 傳遞性，即對任意公式A、B和C，若A B、B C，則A C。25基本等價式命題定律在判

10、定公式間是否等價，有一些簡單而又經(jīng)常使用的等價式，稱為基本等價式或稱命題定律。牢固地記住它并能熟練運用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一。26(1)雙否定：AA。(2)交換律：ABBA，ABBA，ABBA。27(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。28(7) 同一律：ATA，AFA。(8) 零 律：AFF，ATT。(9) 吸收律：A(AB)A，A(AB)A。(10) 互補律：AAF，(矛盾律)AAT。(排中律)

11、(11) 條件式轉(zhuǎn)化律：ABAB，ABBA。29(12) 雙條件式轉(zhuǎn)化律：AB(AB)(BA)(AB)(AB)AB(AB)(13) 輸出律：(AB)CA(BC)。(14) 歸謬律：(AB)(AB)A。上面這些定律，即是通常所說的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。30代入規(guī)則和替換規(guī)則在定義合成公式時，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個意義上可把邏輯聯(lián)結(jié)詞看成運算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替換”，它們也有從已知公式得到新的公式的作用。31代入規(guī)則定理1.3.2 在一個永真式A中，任何一個原子命題變元R出現(xiàn)的每一處， 用另一個公式代入，所得公式B仍是永真式。本定理稱為代入規(guī)則。例子 ：課本例1.3.432替換規(guī)則定理1.3.3 設(shè)A1是合式公式A的子公式，若A1B1，并且將A中的A1用B1 替換得到公式B，則AB。稱該定理為替換規(guī)則。滿足定理1.3.3條件的替換，稱為等價替換。例子：課本 例1.3.5 & 例1.3.633代入和替換有兩點區(qū)別： 代入是對原子命題變元而言的，而替換可對命題公式實行。 代入必須是處處代入，替換則可部分替換，亦可全部替換。34總結(jié)真值表公式分類、等價公式命題定律代入