數(shù)理邏輯-命題邏輯

1、命題邏輯馬殿富馬殿富北航計(jì)算機(jī)學(xué)院北航計(jì)算機(jī)學(xué)院202010-910-9計(jì)算機(jī)學(xué)院2計(jì)算機(jī)學(xué)院2集合論集合論 定義：定義：一些對(duì)象聚集為一個(gè)整體，稱為一些對(duì)象聚集為一個(gè)整體，稱為集合集合。這些。這些對(duì)象稱為集合的對(duì)象稱為集合的元素元素。 元素與集合的關(guān)系元素與集合的關(guān)系 a a是集合是集合S S的元素，記為的元素，記為a aS a a不是集合不是集合S S的元素，記為的元素，記為a aS 集合的表示法集合的表示法 空集：空集： 有窮集合：枚舉法，有窮集合：枚舉法，S=xS=x1 1,x ,x2 2, ,x ,xn n 無(wú)窮集合：描述法無(wú)窮集合：描述法x|xx|x是自然數(shù)是自然數(shù) 計(jì)算機(jī)學(xué)院3計(jì)

2、算機(jī)學(xué)院3集合外延、內(nèi)涵集合外延、內(nèi)涵 外延原則與概括原則外延原則與概括原則 外延原則：一個(gè)集合由它的元素唯一地確定。外延原則：一個(gè)集合由它的元素唯一地確定。 概括原則：每一性質(zhì)概括原則：每一性質(zhì)( (或謂詞或謂詞) )產(chǎn)生一個(gè)集合。產(chǎn)生一個(gè)集合。 集合外延集合外延 集合所包含的元素全體。集合所包含的元素全體。 集合內(nèi)涵集合內(nèi)涵 集合元素所共有的性質(zhì)。集合元素所共有的性質(zhì)。 非負(fù)偶數(shù)集合非負(fù)偶數(shù)集合 外延外延0,2,4,0,2,4, , 內(nèi)涵內(nèi)涵x|xx|x是被是被2 2整除的自然數(shù)整除的自然數(shù) 計(jì)算機(jī)學(xué)院4計(jì)算機(jī)學(xué)院4集合的關(guān)系集合的關(guān)系 集合的關(guān)系集合的關(guān)系 包含關(guān)系：包含關(guān)系：如果集合如

3、果集合A A的元素都是集合的元素都是集合B B的元素，則稱的元素，則稱A A為為B B的子集，記為的子集，記為A AB 真包含關(guān)系：真包含關(guān)系：A AB 不包含關(guān)系不包含關(guān)系:A:AB 等關(guān)系：等關(guān)系：如果集合如果集合A A和集合和集合B B包含相同元素，則稱包含相同元素，則稱A A和和B B相等，記為相等，記為A=BA=B計(jì)算機(jī)學(xué)院5計(jì)算機(jī)學(xué)院5函數(shù)函數(shù) A An n=A=AA AA A A An n=(x=(x1 1,x ,x2 2, ,x ,xn n)|x)|xi iAA A=0, 1A=0, 1 A A3 3 =0, 1=0, 13 3=(0,0,0),(0,0,1),(0,1,0),

4、(0,1,1)=(0,0,0),(0,0,1),(0,1,0),(0,1,1) (1,0,0),(1,0,1),(1,1,0),(1,1,1) (1,0,0),(1,0,1),(1,1,0),(1,1,1) 設(shè)設(shè)A A和和B B是集合，如果對(duì)于集合是集合，如果對(duì)于集合A A中每個(gè)元素中每個(gè)元素x x，都有，都有集合集合B B中唯一元素中唯一元素f(x)f(x)與之對(duì)應(yīng)，則稱與之對(duì)應(yīng)，則稱f f是是函數(shù)函數(shù)。 若若f f是從是從A An n到到B B的函數(shù)，則稱的函數(shù)，則稱f(xf(x1 1,x ,x2 2, ,x ,xn n) )為為A A上的上的n n元元函數(shù)，也稱函數(shù)，也稱 f(x f(x

5、1 1,x ,x2 2, ,x ,xn n) )為為A A上的上的n n元運(yùn)算。元運(yùn)算。 f f：A AA AA AA A計(jì)算機(jī)學(xué)院6計(jì)算機(jī)學(xué)院6歸納定義歸納定義歸納定義歸納定義自然數(shù)集合：自然數(shù)集合：n n是是n n的后繼（函數(shù)），的后繼（函數(shù)），N N是滿足以下是滿足以下條件的條件的S S中的最小集合中的最小集合 0 0S S對(duì)于任何對(duì)于任何n n，如果，如果n nS S，則，則nS S。計(jì)算機(jī)學(xué)院7計(jì)算機(jī)學(xué)院7歸納證明歸納證明 歸納證明歸納證明 設(shè)設(shè)R R是一個(gè)性質(zhì)，是一個(gè)性質(zhì)，R(x)R(x)表示表示x x有有R R性質(zhì)。性質(zhì)。 定理證明定理證明歸納基礎(chǔ)歸納基礎(chǔ) R(0)R(0)歸納假

6、設(shè)歸納假設(shè) 對(duì)于任何對(duì)于任何k kN,R(k);N,R(k);證明證明 R(kR(k); );歸納結(jié)論歸納結(jié)論 對(duì)于任何對(duì)于任何n nN，R(n)。排序概念排序概念計(jì)算機(jī)學(xué)院8計(jì)算機(jī)學(xué)院8數(shù)理邏輯基本概念數(shù)理邏輯基本概念真真可證性可證性計(jì)算機(jī)學(xué)院9計(jì)算機(jī)學(xué)院9數(shù)理邏輯數(shù)理邏輯 數(shù)理邏輯是用數(shù)學(xué)語(yǔ)言表述的推理形式有效性的學(xué)問(wèn)。數(shù)理邏輯是用數(shù)學(xué)語(yǔ)言表述的推理形式有效性的學(xué)問(wèn)。 命題邏輯、謂詞邏輯命題邏輯、謂詞邏輯 數(shù)理邏輯使用特制的表意符號(hào)，亦稱為符號(hào)邏輯。數(shù)理邏輯使用特制的表意符號(hào)，亦稱為符號(hào)邏輯。 邏輯研究對(duì)象邏輯研究對(duì)象邏輯真值邏輯真值 真，表示為真，表示為T(mén) T或或1 1 假，表示為假，表

7、示為F F或或0 0 正確的推理正確的推理形式形式 正確前提正確前提 正確的推理形式正確的推理形式 必然得出正確的結(jié)論必然得出正確的結(jié)論計(jì)算機(jī)學(xué)院10計(jì)算機(jī)學(xué)院101.11.1命題和聯(lián)結(jié)詞命題和聯(lián)結(jié)詞 什么是命題？什么是命題？命題的運(yùn)算符是什么？命題的運(yùn)算符是什么？如何表示命題？如何表示命題？有多少種命題的運(yùn)算符？有多少種命題的運(yùn)算符？計(jì)算機(jī)學(xué)院11計(jì)算機(jī)學(xué)院11語(yǔ)句表達(dá)語(yǔ)句表達(dá)陳述句陳述句疑問(wèn)句疑問(wèn)句祈使句祈使句感嘆句感嘆句 雪是白的。雪是白的。 2 2是奇數(shù)。是奇數(shù)。 X+Y5X+Y5。 你是誰(shuí)？你是誰(shuí)？ 我正在說(shuō)謊。我正在說(shuō)謊。 北京是中國(guó)的首都。北京是中國(guó)的首都。 前進(jìn)！前進(jìn)！ 天空多

8、漂亮天空多漂亮! !特點(diǎn)：有的語(yǔ)句可以特點(diǎn)：有的語(yǔ)句可以判斷真假。判斷真假。計(jì)算機(jī)學(xué)院12計(jì)算機(jī)學(xué)院12自然語(yǔ)言、命題自然語(yǔ)言、命題語(yǔ)言是人們思維和交際的工具，也是一種語(yǔ)言是人們思維和交際的工具，也是一種表達(dá)觀念的符號(hào)系統(tǒng)。表達(dá)觀念的符號(hào)系統(tǒng)。自然語(yǔ)言由各種句式組成，如陳述句、疑自然語(yǔ)言由各種句式組成，如陳述句、疑問(wèn)句、感嘆句、祈使句等等。問(wèn)句、感嘆句、祈使句等等。陳述句是陳述一個(gè)事實(shí)或者說(shuō)話人的看法，陳述句是陳述一個(gè)事實(shí)或者說(shuō)話人的看法，它包括肯定句和否定句兩種。一般來(lái)說(shuō)，它包括肯定句和否定句兩種。一般來(lái)說(shuō)，僅有陳述句能夠確定句子的意義是真還是僅有陳述句能夠確定句子的意義是真還是假。假。命題

9、表達(dá)為具有命題表達(dá)為具有確定真假意義確定真假意義的的陳述句陳述句。計(jì)算機(jī)學(xué)院13計(jì)算機(jī)學(xué)院13命題示例命題示例 雪是白的。雪是白的。 2 2是奇數(shù)。是奇數(shù)。 X+Y5X+Y5。 你是誰(shuí)？你是誰(shuí)？ 我正在說(shuō)謊。我正在說(shuō)謊。 北京是中國(guó)的首都。北京是中國(guó)的首都。 每個(gè)不小于每個(gè)不小于6 6的偶數(shù)都是兩個(gè)的偶數(shù)都是兩個(gè)奇素?cái)?shù)之和（歌德巴赫猜想）奇素?cái)?shù)之和（歌德巴赫猜想） 2121世紀(jì)有人住在月球上。世紀(jì)有人住在月球上。 他很高。他很高。 一個(gè)自然數(shù)不是合數(shù)就是素?cái)?shù)一個(gè)自然數(shù)不是合數(shù)就是素?cái)?shù) 命題，真命題，真 命題，假命題，假 不確定，非命題不確定，非命題 疑問(wèn)句，非命題疑問(wèn)句，非命題 悖論，非命題悖

10、論，非命題 命題，真命題，真 命題，真，有唯一真假值。命題，真，有唯一真假值。 命題，真，有唯一真假值。命題，真，有唯一真假值。 無(wú)法確定，非命題無(wú)法確定，非命題 命題，假，命題，假，1 1不是合數(shù)和素?cái)?shù)不是合數(shù)和素?cái)?shù)計(jì)算機(jī)學(xué)院14計(jì)算機(jī)學(xué)院14簡(jiǎn)單命題與復(fù)合命題簡(jiǎn)單命題與復(fù)合命題 簡(jiǎn)單命題簡(jiǎn)單命題 由簡(jiǎn)單陳述句表述的命由簡(jiǎn)單陳述句表述的命題稱為簡(jiǎn)單命題。題稱為簡(jiǎn)單命題。 命題邏輯不再進(jìn)一步分命題邏輯不再進(jìn)一步分析簡(jiǎn)單命題的內(nèi)部結(jié)構(gòu)析簡(jiǎn)單命題的內(nèi)部結(jié)構(gòu)p: p:孔子是圣人孔子是圣人語(yǔ)句聯(lián)接詞語(yǔ)句聯(lián)接詞并且并且或或否定否定如果如果, ,則則。當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)既不既不，也，也不不。 復(fù)合命題復(fù)合命

11、題 用聯(lián)接詞可以將若干個(gè)用聯(lián)接詞可以將若干個(gè)簡(jiǎn)單句組合成復(fù)合句。簡(jiǎn)單句組合成復(fù)合句。 子命題子命題計(jì)算機(jī)學(xué)院15計(jì)算機(jī)學(xué)院15命題邏輯如何運(yùn)算？命題邏輯如何運(yùn)算？ 數(shù)計(jì)算啟示數(shù)計(jì)算啟示自然數(shù)自然數(shù)運(yùn)算：運(yùn)算：+ +、* *整數(shù)整數(shù)運(yùn)算：運(yùn)算：+ +、- -、* *有理數(shù)有理數(shù)運(yùn)算：運(yùn)算：+ +、- -、* *、/ / 命題邏輯命題小寫(xiě)字母表示真1，假0運(yùn)算：？計(jì)算機(jī)學(xué)院16計(jì)算機(jī)學(xué)院16命題的抽象表示命題的抽象表示 自然語(yǔ)言具有自然語(yǔ)言具有二義性二義性 命題邏輯不關(guān)注語(yǔ)句的內(nèi)容，也不關(guān)注語(yǔ)句為何是命題邏輯不關(guān)注語(yǔ)句的內(nèi)容，也不關(guān)注語(yǔ)句為何是真或?yàn)榧?，而是僅僅關(guān)注語(yǔ)句能夠?yàn)檎婊蚣?。真或?yàn)榧伲?/p>

12、僅僅關(guān)注語(yǔ)句能夠?yàn)檎婊蚣佟?命題的命題的抽象抽象 用小寫(xiě)字母表示命題，取值為用小寫(xiě)字母表示命題，取值為0,10,1。 命題命題真值真值 陳述句的意義為真，稱為陳述句的意義為真，稱為真命題真命題，真值為，真值為1 1。 陳述句的意義為假，稱為陳述句的意義為假，稱為假命題假命題，真值為，真值為0 0。 命題邏輯的研究對(duì)象命題邏輯的研究對(duì)象命題。命題。 數(shù)理邏輯從數(shù)理邏輯從形式結(jié)構(gòu)形式結(jié)構(gòu)方面研究命題。方面研究命題。計(jì)算機(jī)學(xué)院17計(jì)算機(jī)學(xué)院17邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 定義定義 0 0和和1 1稱為稱為0 0元函數(shù)。設(shè)元函數(shù)。設(shè)n0,n0,稱為稱為0,10,1n n到到0,10,1的函數(shù)為的函數(shù)為n n

13、元函數(shù)，真值函數(shù)也稱為元函數(shù)，真值函數(shù)也稱為聯(lián)結(jié)詞聯(lián)結(jié)詞。 命題的操作符（聯(lián)結(jié)詞）命題的操作符（聯(lián)結(jié)詞） 非非 與與 或或 如果如果, ,則則。 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 異或異或 真值真值表表 真值形式可以用圖真值形式可以用圖表來(lái)說(shuō)明。這種表表來(lái)說(shuō)明。這種表稱為稱為真值真值圖表。圖表。0 0元函數(shù)元函數(shù) 0 0，1 11 1元函數(shù)元函數(shù) 2 2元函數(shù)元函數(shù) 、 、 、 計(jì)算機(jī)學(xué)院18計(jì)算機(jī)學(xué)院18邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 0110pp 命題p的否定記為p,讀作非p真值表真值表 邏輯聯(lián)接詞的含義 自然語(yǔ)言中，并非的含義計(jì)算機(jī)學(xué)院19計(jì)算機(jī)學(xué)院19邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 111001010000qpqp真值表

14、 pq稱為p和q的合取 讀作p且q 邏輯聯(lián)接詞的含義 自然語(yǔ)言中，并且的含義計(jì)算機(jī)學(xué)院20計(jì)算機(jī)學(xué)院20邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 111101110000qpqp真值表 pq稱為p和q的析取，讀作p或q 邏輯聯(lián)接詞的含義 自然語(yǔ)言中，或的含義計(jì)算機(jī)學(xué)院21計(jì)算機(jī)學(xué)院21邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 111001110100qpqp真值表 邏輯聯(lián)接詞的含義 自然語(yǔ)言中，如果,則.的含義 pq稱為p蘊(yùn)涵q 讀作p則q p稱為前件 q稱為后件計(jì)算機(jī)學(xué)院22計(jì)算機(jī)學(xué)院22邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 111001010100qpqp真值表 p q稱為p與q等值，讀作p當(dāng)且僅當(dāng)q, p與q互蘊(yùn)含。 pq=(pq)(qp)

15、邏輯聯(lián)接詞的含義 自然語(yǔ)言中，當(dāng)且僅當(dāng)?shù)暮x計(jì)算機(jī)學(xué)院23計(jì)算機(jī)學(xué)院23邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 北航在海淀區(qū)或北航在西城區(qū)。 比較 李明學(xué)習(xí)英語(yǔ)或?qū)W習(xí)法語(yǔ)011101110000qpqp真值表 p q稱為p與q異或，讀作p異或q。 pq= (pq)(qp)計(jì)算機(jī)學(xué)院24計(jì)算機(jī)學(xué)院24邏輯域、邏輯運(yùn)算邏輯域、邏輯運(yùn)算邏輯域邏輯域 00，11 運(yùn)算運(yùn)算 ， ， ， 定義域定義域 0, 10, 1 值域值域 0,10,1計(jì)算機(jī)學(xué)院25計(jì)算機(jī)學(xué)院25命題邏輯運(yùn)算符數(shù)目命題邏輯運(yùn)算符數(shù)目 運(yùn)算符變量數(shù)為運(yùn)算符變量數(shù)為1 1個(gè)變量，個(gè)變量，2 2個(gè)變量，個(gè)變量，,n ,n個(gè)變量的運(yùn)算符數(shù)目個(gè)變量的運(yùn)算符數(shù)目

16、pF1F2F3F40001110101pqpqpqpqpqpq0000110010110110010011111110計(jì)算機(jī)學(xué)院26計(jì)算機(jī)學(xué)院26命題邏輯函數(shù)數(shù)目命題邏輯函數(shù)數(shù)目 變量數(shù)為變量數(shù)為n n 變量組合數(shù)變量組合數(shù) 運(yùn)算符數(shù)運(yùn)算符數(shù) pqF1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16000101010101010101010011001100110011100000111100001111110000000011111111n2n22 Fi(p,q)=？計(jì)算機(jī)學(xué)院27計(jì)算機(jī)學(xué)院27命題形式結(jié)構(gòu)命題形式結(jié)構(gòu) 復(fù)合命題復(fù)合命題是命題及真值聯(lián)結(jié)詞構(gòu)成的形式是

17、命題及真值聯(lián)結(jié)詞構(gòu)成的形式結(jié)構(gòu)結(jié)構(gòu) 六個(gè)真假形式最基本的，或最簡(jiǎn)單的形式，稱六個(gè)真假形式最基本的，或最簡(jiǎn)單的形式，稱為為簡(jiǎn)單命題簡(jiǎn)單命題。 由這六個(gè)真假形式，經(jīng)過(guò)各種各種的互相組合，由這六個(gè)真假形式，經(jīng)過(guò)各種各種的互相組合，還可以變成更多的各種復(fù)雜真值形式。還可以變成更多的各種復(fù)雜真值形式。 真值形式數(shù)量無(wú)窮無(wú)盡。真值形式數(shù)量無(wú)窮無(wú)盡。 示例示例 并非并非p p并且并且q q。(p(pq q) ) 如果非如果非p p，那么非，那么非q q。 p p q q 如果如果p p或或q, q,那么那么r r。p pq qr r計(jì)算機(jī)學(xué)院28計(jì)算機(jī)學(xué)院28命題命題形式結(jié)構(gòu)形式結(jié)構(gòu) 例例1 1： 如果如果

18、n n是奇數(shù)，那么是奇數(shù)，那么n n2 2也是也是奇數(shù)。奇數(shù)。 n n是奇數(shù)是奇數(shù) 所以所以n n2 2也是奇數(shù)。也是奇數(shù)。 例例2 2： 如果如果ABCDABCD是平行四邊形，是平行四邊形，那么那么AD=BCAD=BC。 ABCDABCD是平行四邊形是平行四邊形 所以所以AD=BCAD=BC。 邏輯形式結(jié)構(gòu)邏輯形式結(jié)構(gòu) 如果如果A A，那么，那么B B。 并且并且A A 所以所以B B。 (A B) A B計(jì)算機(jī)學(xué)院29計(jì)算機(jī)學(xué)院29命題命題形式結(jié)構(gòu)形式結(jié)構(gòu) 例例1 1： 角角A A和角和角B B或相等或互補(bǔ)。或相等或互補(bǔ)。 角角A A與角與角B B不相等不相等 所以角所以角A A與角與角B

19、 B互補(bǔ)?；パa(bǔ)。 例例2 2： 函數(shù)函數(shù)y=f(x)y=f(x)或是奇函數(shù)或是或是奇函數(shù)或是偶函數(shù)。偶函數(shù)。 函數(shù)函數(shù)y=f(x)y=f(x)不是奇函數(shù)不是奇函數(shù) 所以函數(shù)所以函數(shù)y=f(x)y=f(x)是偶函數(shù)。是偶函數(shù)。 邏輯形式結(jié)構(gòu)邏輯形式結(jié)構(gòu)A A或或B B。并且非并且非A A所以所以B B。 (AB) A B計(jì)算機(jī)學(xué)院30計(jì)算機(jī)學(xué)院301.21.2公式和真值賦值公式和真值賦值 合式公式合式公式 真值表計(jì)算真值表計(jì)算 語(yǔ)義語(yǔ)義 可滿足性可滿足性計(jì)算機(jī)學(xué)院31計(jì)算機(jī)學(xué)院31合式公式合式公式 命題邏輯中命題邏輯中 0 0和和1 1是常元。是常元。 變?cè)敲}變?cè)?，其值取為真值。變?cè)敲}變

20、元，其值取為真值。 用小寫(xiě)英文字母用小寫(xiě)英文字母p p，q q，r r，s s，t t等表示命題等表示命題變?cè)?。變?cè)?定義：命題變?cè)Q為定義：命題變?cè)Q為原子公式原子公式。計(jì)算機(jī)學(xué)院32計(jì)算機(jī)學(xué)院32合式公式（命題形式）合式公式（命題形式） 定義：定義： (1).(1).符號(hào)符號(hào)0 0和和1 1是合式公式；是合式公式； (2).(2).原子公式是合式公式；原子公式是合式公式； (3).(3).若若Q,RQ,R是合式公式，則是合式公式，則( ( Q)Q)、(Q(Q R) R) 、(Q(Q R) R) 、(Q(QR) R) 、(Q(QR) R) 、(Q(Q R)R)是合式是合式公式；公式； (4

21、).(4).只有有限次應(yīng)用只有有限次應(yīng)用(1)(1)(3)(3)構(gòu)成的公式是合構(gòu)成的公式是合式公式。式公式。計(jì)算機(jī)學(xué)院33計(jì)算機(jī)學(xué)院33 合式公式是命題邏輯的語(yǔ)法概念，它僅僅是合式公式是命題邏輯的語(yǔ)法概念，它僅僅是符合語(yǔ)法結(jié)構(gòu)的公式，是一個(gè)沒(méi)有任何意義符合語(yǔ)法結(jié)構(gòu)的公式，是一個(gè)沒(méi)有任何意義的符號(hào)串。的符號(hào)串。 0 0和和1 1是符號(hào)，沒(méi)有表示邏輯真值的意思；是符號(hào)，沒(méi)有表示邏輯真值的意思； 、 、 、和和 是邏輯運(yùn)算符號(hào)，是邏輯運(yùn)算符號(hào)，也沒(méi)有表示邏輯運(yùn)算的意思；也沒(méi)有表示邏輯運(yùn)算的意思； 命題變?cè)彩欠?hào)。命題變?cè)彩欠?hào)。 由于合式公式的定義具有抽象性和嚴(yán)格性，由于合式公式的定義具有抽象性

22、和嚴(yán)格性，人們對(duì)于一個(gè)合式公式的理解是相同的，不人們對(duì)于一個(gè)合式公式的理解是相同的，不會(huì)產(chǎn)生二義性。會(huì)產(chǎn)生二義性。計(jì)算機(jī)學(xué)院34計(jì)算機(jī)學(xué)院34合式公式合式公式 定義定義1.5 1.5 設(shè)設(shè)S S是聯(lián)結(jié)詞的集合。由是聯(lián)結(jié)詞的集合。由S S生成的公式定生成的公式定義如下：義如下： 若若c c是是S S中的中的0 0元聯(lián)結(jié)詞元聯(lián)結(jié)詞，則，則c c是由是由S S生成的公式。生成的公式。 原子公式原子公式是由是由S S生成的公式。生成的公式。 若若n1n1，F(xiàn)是是S S中的中的n n元聯(lián)結(jié)詞，元聯(lián)結(jié)詞，A A1 1, ,A,An n是由是由S S生成的公式，則生成的公式，則FA A1 1A An n是由

23、是由S S生成的公式。生成的公式。 上面采用了上面采用了前綴記法前綴記法 即把聯(lián)結(jié)詞寫(xiě)在運(yùn)算對(duì)象的前面即把聯(lián)結(jié)詞寫(xiě)在運(yùn)算對(duì)象的前面 如如pqpq。采用前綴記法不需要用括號(hào)也不會(huì)引起。采用前綴記法不需要用括號(hào)也不會(huì)引起歧義。歧義。 計(jì)算機(jī)學(xué)院35計(jì)算機(jī)學(xué)院35合式公式合式公式 設(shè)設(shè)S S是聯(lián)結(jié)詞的集合是是聯(lián)結(jié)詞的集合是 ， ， 。 合式公式：合式公式： (p q q) ( ( p q q ) ) (p q q)， ( ( p q q ) )是是合式合式公式公式 p， q q ，p q q是是合式合式公式公式 p, q是是合式合式公式公式 (p q q) ( ( p q q ) )是是合式合式公式

24、公式 (p 0) (q 1)是合是合式式公式公式 0,1合式合式公式公式 p, q是是合式合式公式公式 (p 0)， (q 1)是是合式合式公式公式 (p 0) (q 1)是是合式合式公式公式計(jì)算機(jī)學(xué)院36計(jì)算機(jī)學(xué)院36命題邏輯語(yǔ)言命題邏輯語(yǔ)言 定義：所有的命題合式公式集合構(gòu)成了定義：所有的命題合式公式集合構(gòu)成了命題邏輯語(yǔ)言，記為命題邏輯語(yǔ)言，記為L(zhǎng) L 。 一般來(lái)說(shuō)，命題邏輯語(yǔ)言一般來(lái)說(shuō)，命題邏輯語(yǔ)言L L 是無(wú)窮集合是無(wú)窮集合，也就是說(shuō)合式公式有無(wú)窮多個(gè)。，也就是說(shuō)合式公式有無(wú)窮多個(gè)。計(jì)算機(jī)學(xué)院37計(jì)算機(jī)學(xué)院37公式復(fù)雜度公式復(fù)雜度 公式公式A A的復(fù)雜度表示為的復(fù)雜度表示為FC(A)FC

25、(A) 常元復(fù)雜度為常元復(fù)雜度為0 0。 命題變?cè)獜?fù)雜度為命題變?cè)獜?fù)雜度為0 0，如果，如果P是命題變?cè)?，則是命題變?cè)?，則FC (P)=0。 如果公式如果公式A=B，則，則FC (A)=FC(B)+1。 如果公式如果公式A=B1 B2，或，或 A=B1 B2，或，或 A=B1B2，或，或 A=B1 B2，或，或 A=B1 B2，或，或 則則FC (A)=maxFC(B1), FC(B2)+1。計(jì)算機(jī)學(xué)院38計(jì)算機(jī)學(xué)院38聯(lián)結(jié)詞的優(yōu)先級(jí)聯(lián)結(jié)詞的優(yōu)先級(jí) 聯(lián)結(jié)詞的優(yōu)先級(jí)聯(lián)結(jié)詞的優(yōu)先級(jí) 從高到低的順序排列為：從高到低的順序排列為：、 、 同一個(gè)聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無(wú)括號(hào)，同一個(gè)聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無(wú)括

26、號(hào)，則按從左至右的順序運(yùn)算則按從左至右的順序運(yùn)算 在滿足運(yùn)算次序不變的情況下，運(yùn)用聯(lián)在滿足運(yùn)算次序不變的情況下，運(yùn)用聯(lián)結(jié)詞的優(yōu)先級(jí)規(guī)則可以結(jié)詞的優(yōu)先級(jí)規(guī)則可以減少合適公式括減少合適公式括號(hào)號(hào)。計(jì)算機(jī)學(xué)院39計(jì)算機(jī)學(xué)院39聯(lián)結(jié)詞的優(yōu)先級(jí)聯(lián)結(jié)詞的優(yōu)先級(jí)(pq)r)q)p) q)r= (p q r) q)p) q)r= (p q r q)p) q)r=(p q r qp) q)r=(p q r qp) qr計(jì)算機(jī)學(xué)院40計(jì)算機(jī)學(xué)院40真值表計(jì)算真值表計(jì)算 命題邏輯語(yǔ)言命題邏輯語(yǔ)言L L的合式公式僅僅是一個(gè)的合式公式僅僅是一個(gè)符號(hào)串。符號(hào)串。 對(duì)于一個(gè)合式公式，我們關(guān)注點(diǎn)之一對(duì)于一個(gè)合式公式，我們關(guān)注

27、點(diǎn)之一是它在什么情況下為真？在什么情況是它在什么情況下為真？在什么情況下為假？即一個(gè)合式公式的邏輯真值下為假？即一個(gè)合式公式的邏輯真值是什么？。是什么？。 一個(gè)合式公式與邏輯真值之間的對(duì)應(yīng)一個(gè)合式公式與邏輯真值之間的對(duì)應(yīng)關(guān)系。關(guān)系。計(jì)算機(jī)學(xué)院41計(jì)算機(jī)學(xué)院41真值表計(jì)算真值表計(jì)算 (p q q) ( ( p q q ) ) pqp q(pq)pq pq(pq)pq00011111010110111001011111100001 (pq) (pq) p q pq (pq) (pq ) 求一個(gè)公式值，一個(gè)公式與另一個(gè)公式求一個(gè)公式值，一個(gè)公式與另一個(gè)公式是否是否等值等值等等等等 真值表的方法不適應(yīng)

28、對(duì)命題演算進(jìn)行整真值表的方法不適應(yīng)對(duì)命題演算進(jìn)行整體的討論或探究命題之間的邏輯關(guān)系。體的討論或探究命題之間的邏輯關(guān)系。真值表優(yōu)缺點(diǎn)真值表優(yōu)缺點(diǎn) 容易、直觀容易、直觀 多變量及公式復(fù)雜難易操作多變量及公式復(fù)雜難易操作計(jì)算機(jī)學(xué)院42計(jì)算機(jī)學(xué)院42命題合式公式語(yǔ)義命題合式公式語(yǔ)義 語(yǔ)義：研究公式與所指稱對(duì)象的關(guān)系。語(yǔ)義：研究公式與所指稱對(duì)象的關(guān)系。 論域：研究對(duì)象的集合。論域：研究對(duì)象的集合。 解釋解釋 用論域的對(duì)象、對(duì)象的運(yùn)算對(duì)應(yīng)形式系統(tǒng)的抽象用論域的對(duì)象、對(duì)象的運(yùn)算對(duì)應(yīng)形式系統(tǒng)的抽象符號(hào)。符號(hào)。 結(jié)構(gòu)結(jié)構(gòu) 論域和解釋稱為形式系統(tǒng)的結(jié)構(gòu)。論域和解釋稱為形式系統(tǒng)的結(jié)構(gòu)。 語(yǔ)義語(yǔ)義 結(jié)構(gòu)連同該結(jié)構(gòu)下公

29、式所取真值的規(guī)定稱為語(yǔ)義。結(jié)構(gòu)連同該結(jié)構(gòu)下公式所取真值的規(guī)定稱為語(yǔ)義。 數(shù)理邏輯的語(yǔ)義研究合式公式與真值的關(guān)系。數(shù)理邏輯的語(yǔ)義研究合式公式與真值的關(guān)系。計(jì)算機(jī)學(xué)院43計(jì)算機(jī)學(xué)院43常元和運(yùn)算符語(yǔ)義常元和運(yùn)算符語(yǔ)義 合式公式的常元合式公式的常元0 0和和1 1的語(yǔ)義分別對(duì)應(yīng)邏的語(yǔ)義分別對(duì)應(yīng)邏輯真值輯真值0 0和和1 1； 合式公式中的合式公式中的 、 、 、或或 等等邏輯運(yùn)算符的語(yǔ)義分別是邏輯真值集合邏輯運(yùn)算符的語(yǔ)義分別是邏輯真值集合上的上的 、 、 、或或 運(yùn)算等。運(yùn)算等。 合式公式的語(yǔ)義是邏輯真值。合式公式的語(yǔ)義是邏輯真值。計(jì)算機(jī)學(xué)院44計(jì)算機(jī)學(xué)院44真值賦值函數(shù)真值賦值函數(shù) 定義定義1.6

30、1.6從合式公式從合式公式集合集合到邏輯到邏輯集合集合0,10,1的函數(shù)稱為的函數(shù)稱為真值賦值函數(shù)真值賦值函數(shù)。 V V：A A 0,10,1 設(shè)設(shè)v是真值賦值函數(shù)，用是真值賦值函數(shù)，用p pv表示表示v v賦給命賦給命題變?cè)}變?cè)猵 p的真值。的真值。 盧卡西維茨運(yùn)算符表示法盧卡西維茨運(yùn)算符表示法前綴表示，前綴表示，F(xiàn)A A1 1,A,An n; ;中綴表示，中綴表示，A A1 1FA A2 2; ;后綴表示，后綴表示，A A1 1,A,An nF計(jì)算機(jī)學(xué)院45計(jì)算機(jī)學(xué)院45合式公式語(yǔ)義合式公式語(yǔ)義 設(shè)設(shè)S S是聯(lián)結(jié)詞的集合是是聯(lián)結(jié)詞的集合是 ， ， ， ， 。由由S S生生成的合式公式成的

31、合式公式A A在真值賦值在真值賦值v v下的下的真值指派真值指派v(A)v(A)定義如下：定義如下： v(0)=0, v(1)=1v(0)=0, v(1)=1。 若若A A是命題變?cè)敲}變?cè)猵 p，則，則v(A)= pv(A)= pv v。 若若A A1 1,A,A2 2是合式公式是合式公式 若若A= A= A A1 1，則，則v(A)= v(A)= v(Av(A1 1) ) 若若A=AA=A1 1 A A2 2，則，則v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) ) 若若A=AA=A1 1A A2 2，則，則v(A)=v(Av(A)=v(A1 1) )v(Av(A2

32、2) ) 若若A=AA=A1 1 A A2 2，則，則v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) ) 若若A=AA=A1 1 A A2 2，則，則v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) ) 若若A=AA=A1 1 A A2 2，則，則v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) )計(jì)算機(jī)學(xué)院46計(jì)算機(jī)學(xué)院46真值賦值真值賦值 由由S S生成的公式生成的公式A A在真值賦值在真值賦值v v下的真值下的真值v(A)v(A)定義如下：定義如下： 若若A A是是S S中的中的0 0元聯(lián)結(jié)詞元聯(lián)結(jié)詞c c，則，則v(A)=cv(A

33、)=c。 若若A A是是命題變?cè)}變?cè)猵 p，則，則v(A)= pv(A)= pv v。 若若A A是是FA A1 1,A,An n，其中，其中n1n1， F是是S S中中的的n n元聯(lián)結(jié)詞，元聯(lián)結(jié)詞， A Ai i是公式，則是公式，則v(A)=v(v(A)=v(FA A1 1A An n)=)=Fv(Av(A1 1) )v(Av(An n) )。計(jì)算機(jī)學(xué)院47計(jì)算機(jī)學(xué)院47語(yǔ)義方法的計(jì)算語(yǔ)義方法的計(jì)算 p p(q (qr) r) 真值賦值函數(shù)：真值賦值函數(shù)： v(p)=1, v(q)=1, v(r)=0 v(p p(q (qr) r) =v(p) v v(q (qr) r) =v(p) (

34、 (v v(q)(q)v( v(r)r) =1(1 (10) 0) = =10 0 =0=0 p p(q(qr)r) 真值賦值函數(shù)：真值賦值函數(shù)： v(p)=0, v(q)=1, v(r)=0 v(p p(q(qr)r) =v(p) v v(q(qr)r) =v(p) ( (v v(q)(q)v(v(r)r) =0(1(10)0) =0=00 0 =1=1計(jì)算機(jī)學(xué)院48計(jì)算機(jī)學(xué)院48簡(jiǎn)化計(jì)算簡(jiǎn)化計(jì)算 (p(p q) q) p pq q v(p)=0或或v(q)=0 v( (p(p q) q) p pq q) = (v(p)(v(p) v( v(q)q) v( v(p)p)v( v(q) q)

35、= (v(p)(v(p) v( v(q)q)1 1 1 1計(jì)算機(jī)學(xué)院49計(jì)算機(jī)學(xué)院49簡(jiǎn)化計(jì)算（續(xù)）簡(jiǎn)化計(jì)算（續(xù)） v(p)=1并且v(q)=1 v(pq)pq) = (v(p)v(q)v(p)v(q) = 100 1計(jì)算機(jī)學(xué)院50計(jì)算機(jī)學(xué)院50 定理定理1.11.1設(shè)設(shè)A A是公式，是公式，v v1 1和和v v2 2是真值賦值，對(duì)于是真值賦值，對(duì)于A A中出現(xiàn)的每個(gè)命題變?cè)谐霈F(xiàn)的每個(gè)命題變?cè)猵 p， ；則；則v v1 1(A)=v(A)=v2 2(A)(A)。 證明證明 對(duì)對(duì)A A的的長(zhǎng)度長(zhǎng)度( (復(fù)雜度復(fù)雜度) )進(jìn)行歸納。進(jìn)行歸納。 若若A A的長(zhǎng)度是的長(zhǎng)度是0 0，則，則A A是命

36、題變?cè)蚴敲}變?cè)? 0元聯(lián)結(jié)詞。元聯(lián)結(jié)詞。 若若A A是是0 0元聯(lián)結(jié)詞元聯(lián)結(jié)詞c c，則，則v v1 1(A)=c=v(A)=c=v2 2(A)(A)。 若若A A是命題變?cè)敲}變?cè)猵 p ， 則則v v1 1(A) = =v(A) = =v2 2(A)(A)。21vvpp21vvpp計(jì)算機(jī)學(xué)院51計(jì)算機(jī)學(xué)院51 設(shè)設(shè)m m大于大于1 1，對(duì)于每個(gè)復(fù)雜度小于，對(duì)于每個(gè)復(fù)雜度小于m m的由的由S S生生成的公式成的公式B B，v v1 1(B)=v(B)=v2 2(B)(B)。 (3)(3)若若A A是是FA A1 1A An n，其中，其中n1n1，F(xiàn)是是S S中的中的n n元元聯(lián)結(jié)詞

37、，則聯(lián)結(jié)詞，則A A1 1, ,A,An n的復(fù)雜度都小于的復(fù)雜度都小于m m，由歸，由歸納假設(shè)知道，納假設(shè)知道，v v1 1(A(Ai i)=v)=v2 2(A(Ai i) ) i=1, i=1,n ,n v1 1(FA A1 1A An n ) = =F v1 1(A A1 1 )v1 1(A An n) = =F v2 2(A A1 1 )v2 2(A An n) = =v2 2(FA A1 1A An n ) 因此，因此，v1 1(FA A1 1A An n)= v2 2(FA A1 1A An n ) 證畢證畢計(jì)算機(jī)學(xué)院52計(jì)算機(jī)學(xué)院52定理定理1.11.1的涵義的涵義 若公式若公式

38、A A中出現(xiàn)的命題變?cè)獮橹谐霈F(xiàn)的命題變?cè)獮閜 p1 1, ,p ,pn n，v v是真是真值賦值，則值賦值，則v(A)v(A)只與只與 有關(guān)。有關(guān)。 用用 表示滿足表示滿足 的真值賦值的真值賦值v v 例例1 1 設(shè)公式設(shè)公式A A為為p p0q0q1, 1,真值賦值真值賦值v=(p/1,q/0)v=(p/1,q/0) v(A)=v(p0q1) =v(p) v(0)v(q) v(1) = 1 00 1 =10 =0 vnvpp ,.,1)/,./(11nnapapnvnvapap,.,11vkp計(jì)算機(jī)學(xué)院53計(jì)算機(jī)學(xué)院53 如果對(duì)公式中出現(xiàn)的每個(gè)命題變?cè)贾概闪舜_定的如果對(duì)公式中出現(xiàn)的每個(gè)命題

39、變?cè)贾概闪舜_定的真值，則該公式的真值也就唯一確定了。因此，可真值，則該公式的真值也就唯一確定了。因此，可將公式看做真值函數(shù)。將公式看做真值函數(shù)。 (pq) pq v(p)=0,v(q)=0 v(pq) pq) = (v(p)v(q) v(p)v(q) = (00) 00 =0 11 =11 =1 (p/0,q/1) v(pq) pq) =1 (p/1,q/0) v(pq) pq) =1 (p/1,q/1) v(pq) pq) =1計(jì)算機(jī)學(xué)院54計(jì)算機(jī)學(xué)院54可滿足式可滿足式 定義定義1.7 1.7 設(shè)設(shè)A A是公式。是公式。 如果真值賦值如果真值賦值v v使得使得v(A)=1v(A)=1，則

40、稱，則稱v v滿足滿足A A。 如果每個(gè)真值賦值都滿足如果每個(gè)真值賦值都滿足A A，則稱，則稱A A為為永真式永真式，也稱為也稱為重言式重言式。 如果每個(gè)真值賦值都不滿足如果每個(gè)真值賦值都不滿足A A，則稱，則稱A A為為永假永假式式，也稱為，也稱為矛盾式矛盾式，不可滿足式不可滿足式。 如果至少有一個(gè)真值賦值滿足如果至少有一個(gè)真值賦值滿足A A，則稱，則稱A A為為可可滿足式滿足式。計(jì)算機(jī)學(xué)院55計(jì)算機(jī)學(xué)院55替換替換 定義定義1.81.8用用 公式公式分別替換公式分別替換公式A A中的不同中的不同命題變?cè)}變?cè)?得到的公式記為得到的公式記為 ，稱，稱為為A A的替換實(shí)例。的替換實(shí)例。 替換

41、產(chǎn)生新的公式替換產(chǎn)生新的公式npp ,.,1nnppBBA,.,.,11nBB ,.,1qprprqpp,)( = (r p)(r p) r (p/r p, q/r)計(jì)算機(jī)學(xué)院56計(jì)算機(jī)學(xué)院56 定理定理1.2 1.2 設(shè)設(shè) 是不同命題變?cè)遣煌}變?cè)?是公式。則對(duì)是公式。則對(duì)于每個(gè)真值賦值于每個(gè)真值賦值v v， 其中真值賦值其中真值賦值v v=v=vp p1 1/v(B/v(B1 1), ), p, pn n/v(B/v(Bn n) )定義如下：定義如下：npp ,.,1nBBA,.,1)(/),.,(/()(11,.,.,11ABvpBvpvAvnnppBBnn否則是若是若vnnvp

42、ppBvppBvp)(.)(11)( )(,.,.,11AvAvnnppBB計(jì)算機(jī)學(xué)院57計(jì)算機(jī)學(xué)院57 證明：對(duì)證明：對(duì)A進(jìn)行歸納。進(jìn)行歸納。 若若A是是pi，其中，其中1in，則，則 是是Bi， 若若A A是除是除 之外的命題變?cè)獾拿}變?cè)猵 p，則，則 仍是仍是p p， (3)(3)若若A A是是0 0元聯(lián)結(jié)詞元聯(lián)結(jié)詞c c，則，則 仍是仍是c c，)(,.,.,11nnppBBAv)( )()(,.,.,11AvBvAvippBBnnnpp ,.,1)(,.,.,11nnppBBAv)( )()(,.,.,11AvpvAvnnppBB )(,.,.,11nnppBBAv)( )()

43、(,.,.,11AvcvAvnnppBB計(jì)算機(jī)學(xué)院58計(jì)算機(jī)學(xué)院58 (4)(4)設(shè)設(shè)A A1 1, ,A,Ak k是長(zhǎng)度小于是長(zhǎng)度小于m m的公式，并且的公式，并且 若若A A是是F A A1 1, ,A,Ak k，其中，其中F是是k k元聯(lián)結(jié)詞，是元聯(lián)結(jié)詞，是長(zhǎng)度等于長(zhǎng)度等于m m的公式的公式, ,則是則是 )( )(.,., 11ippBBiAvAvnn)( )( ),.,( ()(),.,)()(1.,.,1.,.,1,.,., 11, 1111AvAvAvFAvAvFAvkppBBkppBBppBBnnnnnn計(jì)算機(jī)學(xué)院59計(jì)算機(jī)學(xué)院59 定理定理1.31.3設(shè)設(shè)A A是公式。是公式

44、。 若若A A是永真式，則是永真式，則A A的每個(gè)替換實(shí)例都是的每個(gè)替換實(shí)例都是永真式永真式。 若若A A是永假式，則是永假式，則A A的每個(gè)替換實(shí)例都是的每個(gè)替換實(shí)例都是永假式永假式。 證明證明 任取永真式任取永真式A A的替換實(shí)例的替換實(shí)例 ，對(duì)于每個(gè)真值，對(duì)于每個(gè)真值賦值賦值v v， 所以所以 是永真式。是永真式。 可同樣證明?？赏瑯幼C明。 證畢證畢nnppBBA,.,.,111)(/),.(/)(11,.,.,11ABvpBvpvAvnnppBBnnnnppBBA,.,.,11計(jì)算機(jī)學(xué)院60計(jì)算機(jī)學(xué)院60 p ( q p)是永真式是永真式 設(shè)設(shè)A,B是任意公式是任意公式 p/A, q/

45、B A= p q , B=(p r) ( p q ) (p r) ( p q ) )是永真式是永真式計(jì)算機(jī)學(xué)院61計(jì)算機(jī)學(xué)院611.31.3等值演算等值演算 定義定義1.9 1.9 設(shè)設(shè)A,BA,B是公式，如果對(duì)于每個(gè)真值賦是公式，如果對(duì)于每個(gè)真值賦值值v v，v(A)=v(B)v(A)=v(B)，則稱，則稱A A和和B B等值，也稱等值，也稱A A與與B B邏輯等價(jià)，記為邏輯等價(jià)，記為A AB B。 判斷判斷(pq)(pq)和和ppq q是否等值。是否等值。 pqp q (p q) p q p q0001111011010010100101110000計(jì)算機(jī)學(xué)院62計(jì)算機(jī)學(xué)院62等值式模式等

46、值式模式 零律零律 A1A11 A01 A00 0 冪等律冪等律 AAAAA A AAAAA A 吸收律吸收律 A(AB)A(AB)A A A(AB)A(AB)A A 同一律同一律 A1A1A A A0A0A A A A0 0A A 雙重否定雙重否定 A AA A 矛盾律矛盾律AA A A0 0 排中律排中律AA A A1 1 假言易位假言易位 ABAB BB A A 計(jì)算機(jī)學(xué)院63計(jì)算機(jī)學(xué)院63等值式模式等值式模式 德德 摩根律摩根律 (AB)(AB) AA B B (AB)(AB) AA B B 交換律交換律ABABBABAABABBABAA AB BB BA A 計(jì)算機(jī)學(xué)院64計(jì)算機(jī)學(xué)院

47、64等值式模式等值式模式 結(jié)合律結(jié)合律 (AB)C(AB)CA(BC)A(BC) (AB)C(AB)CA(BC)A(BC) (A(AB)B)C CA A(B(BC) C) 分配律分配律 A(BC)A(BC)(AB)(AC) (AB)(AC) A(BC)A(BC)(AB)(AC)(AB)(AC) A(BA(BC)C)(AB)(AB)(AC) (AC) 計(jì)算機(jī)學(xué)院65計(jì)算機(jī)學(xué)院65等值式模式等值式模式A AA A0 0A A1 1A AABABABABA AB B(AB)(BA)(AB)(BA)A AB B( (AB)(AAB)(AB)B)A AB B(A(AB)B)計(jì)算機(jī)學(xué)院66計(jì)算機(jī)學(xué)院66

48、定理：設(shè)定理：設(shè)Q Q是合式公式，是合式公式，R R1 1是是Q Q的子公式，若的子公式，若R R1 1R R2 2，則，則Q Q R R1 1/R/R2 2QQ。 證明：證明： 因?yàn)橐驗(yàn)镽 R1 1R R2 2，所以，所以，v(Rv(R1 1)= v(R)= v(R2 2) ) 。 首先選擇一個(gè)不是公式首先選擇一個(gè)不是公式Q Q中的命題變?cè)械拿}變?cè)猵 p。不。不妨設(shè)命題變?cè)猎O(shè)命題變?cè)猵 p取代公式取代公式Q Q中的一個(gè)中的一個(gè)R R1 1而得公而得公式為式為QQ。 因此，有因此，有 p/R p/R1 1Q=QQ=Q， p/R p/R2 2Q= RQ= R1 1/R/R2 2QQ。計(jì)算機(jī)

49、學(xué)院67計(jì)算機(jī)學(xué)院67 又因?yàn)橛忠驗(yàn)関 v ( p/R ( p/R1 1 Q)= v(p/v(R Q)= v(p/v(R1 1)Q)Q)， v( p/Rv( p/R2 2Q)= v( p/v(RQ)= v( p/v(R2 2)Q)Q) 因此，有因此，有v( p/v(Rv( p/v(R1 1)Q)= v(p/v(R)Q)= v(p/v(R2 2)Q)Q)。 有有v( p/Rv( p/R1 1Q)= v( p/RQ)= v( p/R2 2Q)Q) 有有v(Q)= v( Rv(Q)= v( R1 1/R/R2 2Q)Q)。 有有Q Q R R1 1/R/R2 2QQ。 因此，若因此，若R R1 1R

50、 R2 2，有，有Q Q R R1 1/R/R2 2QQ計(jì)算機(jī)學(xué)院68計(jì)算機(jī)學(xué)院68 例例1.51.5證明證明p(qr)p(qr)pqrpqr 證明：證明： p(qr)p(qr) p(p(qr) ABqr) ABABAB ( (ppq)r q)r 結(jié)合律結(jié)合律 (pq)r (pq)r 摩根律摩根律 pqr ABpqr ABABAB計(jì)算機(jī)學(xué)院69計(jì)算機(jī)學(xué)院69 (pr) (q r) (p q) r (pr) (q r) ( p r) ( q r) ABABABAB ( p q ) p r q r r r 分配律分配律 ( p q ) p r q r r 同一律同一律 ( p q ) r 吸收律吸

51、收律 (p q) r 摩根律摩根律 (p q) r ABABABAB計(jì)算機(jī)學(xué)院70計(jì)算機(jī)學(xué)院70 p(q r) (p q) (p r) p(q r) p (q r) AB AB p q r AB AB p q (p p ) r 排中律排中律 p q p q p r 分配律分配律 p q p r 吸收律吸收律 q p p r 交換律交換律 ( p q) p r 摩根律摩根律 (p q) (p r) AB AB (p q) (p r) AB AB計(jì)算機(jī)學(xué)院71計(jì)算機(jī)學(xué)院71 例例1.61.6用等值演算證明用等值演算證明p(qr)pqrp(qr)pqr是永真式。是永真式。 p(qr)p(qr)pqr

52、pqr (p(p(qr)pqr(qr)pqr ( (p(p(qr)(qr)(p(qr)p(qr) )pqrpqr (p(p(qr)(qr)( (p(qr)pqrp(qr)pqr ( (pp(qr)(qr)(pp(qr)pqr(qr)pqr ( (p(qr)p(qr)(p(pqqr r)pqr)pqr ( (p p(qr)(qr)p pqr)(pqr)(pqqr rpqpqr r) ) ( (pppp(qr)qr)(p(qr)qr)(pq qppq qrrr r) ) (1(qr)qr)(p(1(qr)qr)(pqpq1)qpq1) 11 11 1 1計(jì)算機(jī)學(xué)院72計(jì)算機(jī)學(xué)院721.41.4對(duì)偶

53、定理對(duì)偶定理 (pq)rq)r (pq)rq)r (p0) 1 (p1)0 定義定義1.101.10 設(shè)設(shè)A A是由是由0,1,0,1,生成的公式，將生成的公式，將A A中的中的和和互換，互換，0 0和和1 1互換得到互換得到A A* *，稱，稱A A* *與與A A互為互為對(duì)偶式。對(duì)偶式。 定義定義1.111.11 如果真值賦值如果真值賦值v v1 1和和v v2 2滿足對(duì)每個(gè)命題變?cè)獫M足對(duì)每個(gè)命題變?cè)猵 p， ， 則稱則稱v v1 1和和v v2 2是相反的。是相反的。 (pq)rq)r互為對(duì)偶互為對(duì)偶(pq)rq)r (p0) 1互為對(duì)偶互為對(duì)偶 (p1)021vvpp計(jì)算機(jī)學(xué)院73計(jì)算

54、機(jī)學(xué)院73 (p(pq0)r1 v(p)=1,v(q)=0,v(r)=1q0)r1 v(p)=1,v(q)=0,v(r)=1 (p(pq1)r0 v(p)=0,v(q)=1,v(r)=0q1)r0 v(p)=0,v(q)=1,v(r)=0 v(pv(pq0)r1)q0)r1) =(v(p)=(v(p) v( v(q)v(0)v(r)v(1)q)v(0)v(r)v(1) =(1=(1 0 00)11=10)11=1 v(pv(pq1)r0 )q1)r0 ) = (v(p)= (v(p) v(v( q)v(1)v(r)v(0) q)v(1)v(r)v(0) = (0= (0 1 10)00=0=

55、0)00=0= 1 1計(jì)算機(jī)學(xué)院74計(jì)算機(jī)學(xué)院74對(duì)偶定理對(duì)偶定理 定理定理1.141.14設(shè)設(shè)A A是由是由0,1,0,1,生成的公式，生成的公式，A A* *與與A A互為對(duì)偶式，互為對(duì)偶式，v v和和v v是相反的真值賦值，是相反的真值賦值，則則v(Av(A* *)=)=v(A)v(A)。 證明：證明： 1.A1.A的的復(fù)雜度為復(fù)雜度為0 0，定理成立，定理成立 若若A A為命題變?cè)獮槊}變?cè)猵 p， 則則A A* *也為也為p p，v(p)=v(p)=v(p)v(p)。 若若A A為為0 0，則，則A A* *為為1 1，v(1)=v(1)=v(0)v(0)。 若若A A為為1 1，則

56、，則A A* *為為0 0，v(0)=v(0)=v(1)v(1)。計(jì)算機(jī)學(xué)院75計(jì)算機(jī)學(xué)院75 2. 2.假設(shè)對(duì)于復(fù)雜度不超過(guò)假設(shè)對(duì)于復(fù)雜度不超過(guò)n n的每個(gè)公式的每個(gè)公式B B，v(Bv(B* *)=)=v v(B)(B)。 3. 3.證明復(fù)雜度等于證明復(fù)雜度等于n n，定理成立。，定理成立。 (1)(1)若若A A為為B B，v(Bv(B* *)=)=v(B)v(B)，并且，并且A A* *為為B B* *。因此，因此，v(Av(A* *)=v()=v(B B* *)=)=v(Bv(B* *)=)=v(B)=v(B)=v(v(B)= B)= v(A)v(A) (2)(2)若若A A為為BC

57、BC，v(Bv(B* *)=)=v(B)v(B)且且v(Cv(C* *)=)=v(C)v(C)，并且，并且A A* *為為B B* *CC* *。因此，因此，v(Av(A* *)=v(B)=v(B* *CC* *)=v(B)=v(B* *)v(C)v(C* *) )= =v(B)v(B)v(C)= v(v(C)= v(BBC)=v(C)=v(BC)(BC)= = v(BC) = v(BC) = v(A)v(A)計(jì)算機(jī)學(xué)院76計(jì)算機(jī)學(xué)院76 (3)(3)若若A A為為BCBC，v(Bv(B* *)=)=v(B)v(B)且且v(Cv(C* *)=)=v(C)v(C)，并且并且A A* *為為B B

58、* *CC* *。 因此，因此，v(Av(A* *)=v(B)=v(B* *CC* *)=v(B)=v(B* *)v(C)v(C* *) ) = =v(B)v(B)v(C)= v(v(C)= v(BBC)=v(C)=v(BC)= (BC)= v(BC)= v(BC)= v(A)v(A)計(jì)算機(jī)學(xué)院77計(jì)算機(jī)學(xué)院77 定理定理1.51.5（對(duì)偶定理）（對(duì)偶定理） 設(shè)設(shè)A,BA,B是由是由0,1,0,1,生成的公式，生成的公式，A A* *與與A A互互為對(duì)偶式，為對(duì)偶式，B B* *與與B B互為對(duì)偶式。如果互為對(duì)偶式。如果A A B B，則則A A* * B B* *。 證明：證明： 任取真值賦

59、值任取真值賦值v v，令，令v v是與是與v v相反的真值賦值，相反的真值賦值，因?yàn)橐驗(yàn)锳 AB B，所以，所以v(A)=v(B)v(A)=v(B)，因此，因此，v(Av(A* *)=)=v(A)= v(A)= v(B)=v(Bv(B)=v(B* *) ) 所以，所以，A A* * B B* *。 證畢證畢計(jì)算機(jī)學(xué)院78計(jì)算機(jī)學(xué)院78 證明等值式：證明等值式： (1) (p q) ( p ( p q) p q (2) (p q) ( p ( p q) p q 證明：等值式證明：等值式(1) (p q) ( p ( p q) (p q) ( p p q) (p q) p q p q 證明：等值式

60、證明：等值式(2) 對(duì)偶定理對(duì)偶定理計(jì)算機(jī)學(xué)院79計(jì)算機(jī)學(xué)院791.51.5聯(lián)結(jié)詞的完全集聯(lián)結(jié)詞的完全集 pq=pq=p pq q p pq=(pq)q=(pq)(qp)=(qp)=(p pq) q)(p(pq) q) p pq=(pq=(pq) q) ( (p pq) q) 結(jié)論：結(jié)論： ，不是獨(dú)立的不是獨(dú)立的 邏輯的最少聯(lián)接詞是什么？邏輯的最少聯(lián)接詞是什么？計(jì)算機(jī)學(xué)院80計(jì)算機(jī)學(xué)院80完全集完全集 定義定義1.121.12設(shè)設(shè)F是是n n元聯(lián)結(jié)詞，元聯(lián)結(jié)詞，p p1 1,p ,p2 2, ,p ,pn n是不同的命是不同的命題變?cè)?。如果公式題變?cè)Ｈ绻紸 A中不出現(xiàn)除中不出現(xiàn)除p p1