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

關于真值表公式分類命題定律代入置換復習引論：離散數(shù)學、數(shù)理邏輯命題聯(lián)結(jié)詞第2頁,共39頁，2024年2月25日，星期天復習題：本命題是假的。我不給所有自己給自己理發(fā)的人理發(fā)，但是卻會給所有自己不給自己理發(fā)的人理發(fā)。第3頁,共39頁，2024年2月25日，星期天本節(jié)內(nèi)容命題符號化第4頁,共39頁，2024年2月25日，星期天命題分類與命題變元命題原子命題：不包含任何聯(lián)結(jié)詞的命題復合命題：至少包含一個聯(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.)當合式公式比較復雜時，常常使用很多圓括號，為了減少圓括號的使用量，可作以下約定：①優(yōu)先級由高到低的次序為：l、∧、∨、→、

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

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

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

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

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

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

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

B:我們要做到學習好

C:我們要做到工作好

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

P:張三做作業(yè)

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

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

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

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

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

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

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

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

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

A

B當且僅當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)常使用的等價式，稱為基本等價式或稱命題定律。牢固地記住它并能熟練運用，是學好數(shù)理邏輯的關鍵之一。第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

設A1是合式公式A的子公式，若A1

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