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

關(guān)于真值表公式分類命題定律代入置換復(fù)習(xí)引論：離散數(shù)學(xué)、數(shù)理邏輯命題聯(lián)結(jié)詞第2頁,共39頁，2024年2月25日，星期天復(fù)習(xí)題：本命題是假的。我不給所有自己給自己理發(fā)的人理發(fā)，但是卻會給所有自己不給自己理發(fā)的人理發(fā)。第3頁,共39頁，2024年2月25日，星期天本節(jié)內(nèi)容命題符號化第4頁,共39頁，2024年2月25日，星期天命題分類與命題變元命題原子命題：不包含任何聯(lián)結(jié)詞的命題復(fù)合命題：至少包含一個聯(lián)結(jié)詞的命題命題變元一個不確定的泛指的任意命題定義：以真(1)、假(0)為其變域的變元注意：命題變元不是命題，只有用一個特定的命題取代才能確定它的真值：真或假（對該命題變元指派真值）命題公式含有命題變元的斷言稱為命題公式注意：不是所有由命題變元、聯(lián)結(jié)詞和括號所組成的字符串都能成為命題公式。第5頁,共39頁，2024年2月25日，星期天合式公式原子公式定義：單個命題變元和命題常元稱為原子命題公式，簡稱原子公式。合式公式合式公式是由下列規(guī)則生成的公式：①單個原子公式是合式公式。②若A是一個合式公式，則(lA)也是一個合式公式。③若A、B是合式公式，則(A∧B)、(A∨B)、(A→B)和(A

B)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。第6頁,共39頁，2024年2月25日，星期天合式公式(Cont.)例：下列符號串是否為命題公式。（1）P→(Q∧PR）；

（2）（P∨Q）→（?（Q∧R））第7頁,共39頁，2024年2月25日，星期天合式公式(Cont.)當(dāng)合式公式比較復(fù)雜時，常常使用很多圓括號，為了減少圓括號的使用量，可作以下約定：①優(yōu)先級由高到低的次序為：l、∧、∨、→、

②相同的聯(lián)結(jié)詞按從左至右次序計算時，圓括號可省略。③最外層的圓括號可以省略。

第8頁,共39頁，2024年2月25日，星期天合式公式(Cont.)例子

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

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

運算順序完全一樣,前者不加一個括號.

請大家特別注意先∧后∨的習(xí)慣.第9頁,共39頁，2024年2月25日，星期天命題符號化

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

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

C:我們要做到工作好

P:我們要為祖國四化建設(shè)而奮斗故命題可以表示為:第12頁,共39頁，2024年2月25日，星期天命題的符號化(Cont.)張三和李四同在做作業(yè)

P:張三做作業(yè)

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

第13頁,共39頁，2024年2月25日，星期天命題的符號化(Cont.)“這盆花盛開，促使那些蜜蜂來采蜜”不可以符號化,為什么呢？ 因為連接詞‘促使’不是命題連接詞.根據(jù)是由它構(gòu)成的復(fù)合命題的真值不能完全由構(gòu)成它的原子命題的真值來確定.例如令P:這盆花盛開,值為1，Q:那些蜜蜂來采蜜,其值為1,則‘這盆花盛開促使那些蜜蜂來采蜜’值為1.又令P:海水是咸的,其值為1,Q:那些蜜蜂來采蜜值為1,則‘海水是咸的促使那些蜜蜂來采蜜’值為0.

由此可見,兩組原命題都為真,但由‘促使’構(gòu)成的復(fù)合命題的值一為真一為假,這不符合定義.第14頁,共39頁，2024年2月25日，星期天注意

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

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

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

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

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

B，讀作A等價B，稱A

B為等價式。

若公式A和B的真值表是相同的，則A和B等價。因此，驗證兩公式是否等價，只需做出它們的真值表即可。第23頁,共39頁，2024年2月25日，星期天

和

的區(qū)別與聯(lián)系區(qū)別：

是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語言中的符號，它出現(xiàn)在命題公式中；

不是邏輯聯(lián)結(jié)詞，屬于元語言中的符號，表示兩個命題公式的一種關(guān)系，不屬于這兩個公式的任何一個公式中的符號。聯(lián)系：定理：

A

B當(dāng)且僅當(dāng)A

B是永真式。第24頁,共39頁，2024年2月25日，星期天等價公式的性質(zhì)①自反性，即對任意公式A，有A

A。②對稱性，即對任意公式A和B，若A

B，則B

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

B、B

C，則A

C。第25頁,共39頁，2024年2月25日，星期天基本等價式——命題定律在判定公式間是否等價，有一些簡單而又經(jīng)常使用的等價式，稱為基本等價式或稱命題定律。牢固地記住它并能熟練運用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一。第26頁,共39頁，2024年2月25日，星期天(1)雙否定：

A

A。(2)交換律：A∧B

B∧A，A∨B

B∨A，A

B

B

A。第27頁,共39頁，2024年2月25日，星期天(3)結(jié)合律：(A∧B)∧C

A∧(B∧C)，(A∨B)∨C

A∨(B∨C)，(A

B)

C

A

(B

C)。(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∧A

A，A∨A

A。第28頁,共39頁，2024年2月25日，星期天(7)同一律：A∧T

A，A∨F

A。(8)零律：A∧F

F，A∨T

T。(9)吸收律：A∧(A∨B)

A，A∨(A∧B)

A。(10)互補律：A∧

A

F，(矛盾律) A∨

A

T。(排中律)(11)條件式轉(zhuǎn)化律：A→B

A∨B，A→B

B→

A。第29頁,共39頁，2024年2月25日，星期天(12)雙條件式轉(zhuǎn)化律：A

B

(A→B)∧(B→A)

(A∧B)∨(

A∧

B)

A

B

(A

B)(13)輸出律：(A∧B)→C

A→(B→C)。(14)歸謬律：(A→B)∧(A→

B)

A。上面這些定律，即是通常所說的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。第30頁,共39頁，2024年2月25日，星期天代入規(guī)則和替換規(guī)則

在定義合成公式時，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這個意義上可把邏輯聯(lián)結(jié)詞看成運算。除邏輯聯(lián)結(jié)詞外，還要介紹“代入”和“替換”，它們也有從已知公式得到新的公式的作用。第31頁,共39頁，2024年2月25日，星期天代入規(guī)則定理1.3.2

在一個永真式A中，任何一個原子命題變元R出現(xiàn)的每一處，用另一個公式代入，所得公式B仍是永真式。本定理稱為代入規(guī)則。例子：課本例1.3.4第32頁,共39頁，2024年2月25日，星期天替換規(guī)則定理1.3.3

設(shè)A1是合式公式A的子公式，若A1

B1，并且將A中的A1用B1替換得到