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

1、命題邏輯馬殿富馬殿富北航計算機學(xué)院北航計算機學(xué)院202010-910-9計算機學(xué)院2計算機學(xué)院2集合論集合論 定義：定義：一些對象聚集為一個整體，稱為一些對象聚集為一個整體，稱為集合集合。這些。這些對象稱為集合的對象稱為集合的元素元素。 元素與集合的關(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 無窮集合：描述法無窮集合：描述法x|xx|x是自然數(shù)是自然數(shù) 計算機學(xué)院3計

2、算機學(xué)院3集合外延、內(nèi)涵集合外延、內(nèi)涵 外延原則與概括原則外延原則與概括原則 外延原則：一個集合由它的元素唯一地確定。外延原則：一個集合由它的元素唯一地確定。 概括原則：每一性質(zhì)概括原則：每一性質(zhì)( (或謂詞或謂詞) )產(chǎn)生一個集合。產(chǎn)生一個集合。 集合外延集合外延 集合所包含的元素全體。集合所包含的元素全體。 集合內(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ù) 計算機學(xué)院4計算機學(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計算機學(xué)院5計算機學(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是集合，如果對于集合是集合，如果對于集合A A中每個元素中每個元素x x，都有，都有集合集合B B中唯一元素中唯一元素f(x)f(x)與之對應(yīng)，則稱與之對應(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元運算。元運算。 f f：A AA AA AA A計算機學(xué)院6計算機學(xué)院6歸納定義歸納定義歸納定義歸納定義自然數(shù)集合：自然數(shù)集合：n n是是n n的后繼（函數(shù)），的后繼（函數(shù)），N N是滿足以下是滿足以下條件的條件的S S中的最小集合中的最小集合 0 0S S對于任何對于任何n n，如果，如果n nS S，則，則nS S。計算機學(xué)院7計算機學(xué)院7歸納證明歸納證明 歸納證明歸納證明 設(shè)設(shè)R R是一個性質(zhì)，是一個性質(zhì)，R(x)R(x)表示表示x x有有R R性質(zhì)。性質(zhì)。 定理證明定理證明歸納基礎(chǔ)歸納基礎(chǔ) R(0)R(0)歸納假

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

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

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

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

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

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

12、僅僅關(guān)注語句能夠為真或假。 命題的命題的抽象抽象 用小寫字母表示命題，取值為用小寫字母表示命題，取值為0,10,1。 命題命題真值真值 陳述句的意義為真，稱為陳述句的意義為真，稱為真命題真命題，真值為，真值為1 1。 陳述句的意義為假，稱為陳述句的意義為假，稱為假命題假命題，真值為，真值為0 0。 命題邏輯的研究對象命題邏輯的研究對象命題。命題。 數(shù)理邏輯從數(shù)理邏輯從形式結(jié)構(gòu)形式結(jié)構(gòu)方面研究命題。方面研究命題。計算機學(xué)院17計算機學(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) 異或異或 真值真值表表 真值形式可以用圖真值形式可以用圖表來說明。這種表表來說明。這種表稱為稱為真值真值圖表。圖表。0 0元函數(shù)元函數(shù) 0 0，1 11 1元函數(shù)元函數(shù) 2 2元函數(shù)元函數(shù) 、 、 、 計算機學(xué)院18計算機學(xué)院18邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 0110pp 命題p的否定記為p,讀作非p真值表真值表 邏輯聯(lián)接詞的含義 自然語言中，并非的含義計算機學(xué)院19計算機學(xué)院19邏輯聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞 111001010000qpqp真值表

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

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

16、pF1F2F3F40001110101pqpqpqpqpqpq0000110010110110010011111110計算機學(xué)院26計算機學(xué)院26命題邏輯函數(shù)數(shù)目命題邏輯函數(shù)數(shù)目 變量數(shù)為變量數(shù)為n n 變量組合數(shù)變量組合數(shù) 運算符數(shù)運算符數(shù) pqF1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16000101010101010101010011001100110011100000111100001111110000000011111111n2n22 Fi(p,q)=？計算機學(xué)院27計算機學(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) 六個真假形式最基本的，或最簡單的形式，稱六個真假形式最基本的，或最簡單的形式，稱為為簡單命題簡單命題。 由這六個真假形式，經(jīng)過各種各種的互相組合，由這六個真假形式，經(jīng)過各種各種的互相組合，還可以變成更多的各種復(fù)雜真值形式。還可以變成更多的各種復(fù)雜真值形式。 真值形式數(shù)量無窮無盡。真值形式數(shù)量無窮無盡。 示例示例 并非并非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計算機學(xué)院28計算機學(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計算機學(xué)院29計算機學(xué)院29命題命題形式結(jié)構(gòu)形式結(jié)構(gòu) 例例1 1： 角角A A和角和角B B或相等或互補?；蛳嗟然蚧パa。 角角A A與角與角B B不相等不相等 所以角所以角A A與角與角B

19、 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計算機學(xué)院30計算機學(xué)院301.21.2公式和真值賦值公式和真值賦值 合式公式合式公式 真值表計算真值表計算 語義語義 可滿足性可滿足性計算機學(xué)院31計算機學(xué)院31合式公式合式公式 命題邏輯中命題邏輯中 0 0和和1 1是常元。是常元。 變元是命題變元，其值取為真值。變元是命題變

20、元，其值取為真值。 用小寫英文字母用小寫英文字母p p，q q，r r，s s，t t等表示命題等表示命題變元。變元。 定義：命題變元稱為定義：命題變元稱為原子公式原子公式。計算機學(xué)院32計算機學(xué)院32合式公式（命題形式）合式公式（命題形式） 定義：定義： (1).(1).符號符號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)成的公式是合式公式。式公式。計算機學(xué)院33計算機學(xué)院33 合式公式是命題邏輯的語法概念，它僅僅是合式公式是命題邏輯的語法概念，它僅僅是符合語法結(jié)構(gòu)的公式，是一個沒有任何意義符合語法結(jié)構(gòu)的公式，是一個沒有任何意義的符號串。的符號串。 0 0和和1 1是符號，沒有表示邏輯真值的意思；是符號，沒有表示邏輯真值的意思； 、 、 、和和 是邏輯運算符號，是邏輯運算符號，也沒有表示邏輯運算的意思；也沒有表示邏輯運算的意思； 命題變元也是符號。命題變元也是符號。 由于合式公式的定義具有抽象性和嚴(yán)格性，由于合式公式的定義具有抽象性

22、和嚴(yán)格性，人們對于一個合式公式的理解是相同的，不人們對于一個合式公式的理解是相同的，不會產(chǎn)生二義性。會產(chǎn)生二義性。計算機學(xué)院34計算機學(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é)詞寫在運算對象的前面即把聯(lián)結(jié)詞寫在運算對象的前面 如如pqpq。采用前綴記法不需要用括號也不會引起。采用前綴記法不需要用括號也不會引起歧義。歧義。 計算機學(xué)院35計算機學(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)是是合式合式公式公式計算機學(xué)院36計算機學(xué)院36命題邏輯語言命題邏輯語言 定義：所有的命題合式公式集合構(gòu)成了定義：所有的命題合式公式集合構(gòu)成了命題邏輯語言，記為命題邏輯語言，記為L L 。 一般來說，命題邏輯語言一般來說，命題邏輯語言L L 是無窮集合是無窮集合，也就是說合式公式有無窮多個。，也就是說合式公式有無窮多個。計算機學(xué)院37計算機學(xué)院37公式復(fù)雜度公式復(fù)雜度 公式公式A A的復(fù)雜度表示為的復(fù)雜度表示為FC(A)FC

25、(A) 常元復(fù)雜度為常元復(fù)雜度為0 0。 命題變元復(fù)雜度為命題變元復(fù)雜度為0 0，如果，如果P是命題變元，則是命題變元，則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。計算機學(xué)院38計算機學(xué)院38聯(lián)結(jié)詞的優(yōu)先級聯(lián)結(jié)詞的優(yōu)先級 聯(lián)結(jié)詞的優(yōu)先級聯(lián)結(jié)詞的優(yōu)先級 從高到低的順序排列為：從高到低的順序排列為：、 、 同一個聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無括號，同一個聯(lián)結(jié)詞連續(xù)多次出現(xiàn)且無括

26、號，則按從左至右的順序運算則按從左至右的順序運算 在滿足運算次序不變的情況下，運用聯(lián)在滿足運算次序不變的情況下，運用聯(lián)結(jié)詞的優(yōu)先級規(guī)則可以結(jié)詞的優(yōu)先級規(guī)則可以減少合適公式括減少合適公式括號號。計算機學(xué)院39計算機學(xué)院39聯(lián)結(jié)詞的優(yōu)先級聯(lián)結(jié)詞的優(yōu)先級(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計算機學(xué)院40計算機學(xué)院40真值表計算真值表計算 命題邏輯語言命題邏輯語言L L的合式公式僅僅是一個的合式公式僅僅是一個符號串。符號串。 對于一個合式公式，我們關(guān)注點之一對于一個合式公式，我們關(guān)注

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

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

29、式所取真值的規(guī)定稱為語義。結(jié)構(gòu)連同該結(jié)構(gòu)下公式所取真值的規(guī)定稱為語義。 數(shù)理邏輯的語義研究合式公式與真值的關(guān)系。數(shù)理邏輯的語義研究合式公式與真值的關(guān)系。計算機學(xué)院43計算機學(xué)院43常元和運算符語義常元和運算符語義 合式公式的常元合式公式的常元0 0和和1 1的語義分別對應(yīng)邏的語義分別對應(yīng)邏輯真值輯真值0 0和和1 1； 合式公式中的合式公式中的 、 、 、或或 等等邏輯運算符的語義分別是邏輯真值集合邏輯運算符的語義分別是邏輯真值集合上的上的 、 、 、或或 運算等。運算等。 合式公式的語義是邏輯真值。合式公式的語義是邏輯真值。計算機學(xué)院44計算機學(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賦給命賦給命題變元題變元p p的真值。的真值。 盧卡西維茨運算符表示法盧卡西維茨運算符表示法前綴表示，前綴表示，F(xiàn)A A1 1,A,An n; ;中綴表示，中綴表示，A A1 1FA A2 2; ;后綴表示，后綴表示，A A1 1,A,An nF計算機學(xué)院45計算機學(xué)院45合式公式語義合式公式語義 設(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是命題變元是命題變元p 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) )計算機學(xué)院46計算機學(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是是命題變元命題變元p 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) )。計算機學(xué)院47計算機學(xué)院47語義方法的計算語義方法的計算 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計算機學(xué)院48計算機學(xué)院48簡化計算簡化計算 (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計算機學(xué)院49計算機學(xué)院49簡化計算（續(xù)）簡化計算（續(xù)） v(p)=1并且v(q)=1 v(pq)pq) = (v(p)v(q)v(p)v(q) = 100 1計算機學(xué)院50計算機學(xué)院50 定理定理1.11.1設(shè)設(shè)A A是公式，是公式，v v1 1和和v v2 2是真值賦值，對于是真值賦值，對于A A中出現(xiàn)的每個命題變元中出現(xiàn)的每個命題變元p p， ；則；則v v1 1(A)=v(A)=v2 2(A)(A)。 證明證明 對對A A的的長度長度( (復(fù)雜度復(fù)雜度) )進行歸納。進行歸納。 若若A A的長度是的長度是0 0，則，則A A是命

36、題變元或是命題變元或0 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是命題變元是命題變元p p ， 則則v v1 1(A) = =v(A) = =v2 2(A)(A)。21vvpp21vvpp計算機學(xué)院51計算機學(xué)院51 設(shè)設(shè)m m大于大于1 1，對于每個復(fù)雜度小于，對于每個復(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 ) 證畢證畢計算機學(xué)院52計算機學(xué)院52定理定理1.11.1的涵義的涵義 若公式若公式

38、A A中出現(xiàn)的命題變元為中出現(xiàn)的命題變元為p 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計算機學(xué)院53計算機學(xué)院53 如果對公式中出現(xiàn)的每個命題變元都指派了確定的如果對公式中出現(xiàn)的每個命題

39、變元都指派了確定的真值，則該公式的真值也就唯一確定了。因此，可真值，則該公式的真值也就唯一確定了。因此，可將公式看做真值函數(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計算機學(xué)院54計算機學(xué)院54可滿足式可滿足式 定義定義1.7 1.7 設(shè)設(shè)A A是公式。是公式。 如果真值賦值如果真值賦值v v使得使得v(A)=1v(A)=1，則

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

41、產(chǎn)生新的公式替換產(chǎn)生新的公式npp ,.,1nnppBBA,.,.,11nBB ,.,1qprprqpp,)( = (r p)(r p) r (p/r p, q/r)計算機學(xué)院56計算機學(xué)院56 定理定理1.2 1.2 設(shè)設(shè) 是不同命題變元，是不同命題變元， 是公式。則對是公式。則對于每個真值賦值于每個真值賦值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計算機學(xué)院57計算機學(xué)院57 證明：對證明：對A進行歸納。進行歸納。 若若A是是pi，其中，其中1in，則，則 是是Bi， 若若A A是除是除 之外的命題變元之外的命題變元p 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計算機學(xué)院58計算機學(xué)院58 (4)(4)設(shè)設(shè)A A1 1, ,A,Ak k是長度小于是長度小于m m的公式，并且的公式，并且 若若A A是是F A A1 1, ,A,Ak k，其中，其中F是是k k元聯(lián)結(jié)詞，是元聯(lián)結(jié)詞，是長度等于長度等于m m的公式的公式, ,則是則是 )( )(.,., 11ippBBiAvAvnn)( )( ),.,( ()(),.,)()(1.,.,1.,.,1,.,., 11, 1111AvAvAvFAvAvFAvkppBBkppBBppBBnnnnnn計算機學(xué)院59計算機學(xué)院59 定理定理1.31.3設(shè)設(shè)A A是公式。是公式

44、。 若若A A是永真式，則是永真式，則A A的每個替換實例都是的每個替換實例都是永真式永真式。 若若A A是永假式，則是永假式，則A A的每個替換實例都是的每個替換實例都是永假式永假式。 證明證明 任取永真式任取永真式A A的替換實例的替換實例 ，對于每個真值，對于每個真值賦值賦值v v， 所以所以 是永真式。是永真式。 可同樣證明?？赏瑯幼C明。 證畢證畢nnppBBA,.,.,111)(/),.(/)(11,.,.,11ABvpBvpvAvnnppBBnnnnppBBA,.,.,11計算機學(xué)院60計算機學(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 ) )是永真式是永真式計算機學(xué)院61計算機學(xué)院611.31.3等值演算等值演算 定義定義1.9 1.9 設(shè)設(shè)A,BA,B是公式，如果對于每個真值賦是公式，如果對于每個真值賦值值v v，v(A)=v(B)v(A)=v(B)，則稱，則稱A A和和B B等值，也稱等值，也稱A A與與B B邏輯等價，記為邏輯等價，記為A AB B。 判斷判斷(pq)(pq)和和ppq q是否等值。是否等值。 pqp q (p q) p q p q0001111011010010100101110000計算機學(xué)院62計算機學(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 計算機學(xué)院63計算機學(xué)院63等值式模式等值式模式 德德 摩根律摩根律 (AB)(AB) AA B B (AB)(AB) AA B B 交換律交換律ABABBABAABABBABAA AB BB BA A 計算機學(xué)院64計算機學(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) 計算機學(xué)院65計算機學(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)計算機學(xué)院66計算機學(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。 證明：證明： 因為因為R R1 1R R2 2，所以，所以，v(Rv(R1 1)= v(R)= v(R2 2) ) 。 首先選擇一個不是公式首先選擇一個不是公式Q Q中的命題變元中的命題變元p p。不。不妨設(shè)命題變元妨設(shè)命題變元p p取代公式取代公式Q Q中的一個中的一個R R1 1而得公而得公式為式為QQ。 因此，有因此，有 p/R p/R1 1Q=QQ=Q， p/R p/R2 2Q= RQ= R1 1/R/R2 2QQ。計算機

49、學(xué)院67計算機學(xué)院67 又因為又因為v 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計算機學(xué)院68計算機學(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計算機學(xué)院69計算機學(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計算機學(xué)院70計算機學(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計算機學(xué)院71計算機學(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計算機學(xué)院72計算機學(xué)院721.41.4對偶

53、定理對偶定理 (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互為互為對偶式。對偶式。 定義定義1.111.11 如果真值賦值如果真值賦值v v1 1和和v v2 2滿足對每個命題變元滿足對每個命題變元p p， ， 則稱則稱v v1 1和和v v2 2是相反的。是相反的。 (pq)rq)r互為對偶互為對偶(pq)rq)r (p0) 1互為對偶互為對偶 (p1)021vvpp計算機學(xué)院73計算

54、機學(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計算機學(xué)院74計算機學(xué)院74對偶定理對偶定理 定理定理1.141.14設(shè)設(shè)A A是由是由0,1,0,1,生成的公式，生成的公式，A A* *與與A A互為對偶式，互為對偶式，v v和和v v是相反的真值賦值，是相反的真值賦值，則則v(Av(A* *)=)=v(A)v(A)。 證明：證明： 1.A1.A的的復(fù)雜度為復(fù)雜度為0 0，定理成立，定理成立 若若A A為命題變元為命題變元p 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)。計算機學(xué)院75計算機學(xué)院75 2. 2.假設(shè)對于復(fù)雜度不超過假設(shè)對于復(fù)雜度不超過n n的每個公式的每個公式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)計算機學(xué)院76計算機學(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)計算機學(xué)院77計算機學(xué)院77 定理定理1.51.5（對偶定理）（對偶定理） 設(shè)設(shè)A,BA,B是由是由0,1,0,1,生成的公式，生成的公式，A A* *與與A A互互為對偶式，為對偶式，B B* *與與B B互為對偶式。如果互為對偶式。如果A A B B，則則A A* * B B* *。 證明：證明： 任取真值賦

59、值任取真值賦值v v，令，令v v是與是與v v相反的真值賦值，相反的真值賦值，因為因為A 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* *。 證畢證畢計算機學(xué)院78計算機學(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) 對偶定理對偶定理計算機學(xué)院79計算機學(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é)論： ，不是獨立的不是獨立的 邏輯的最少聯(lián)接詞是什么？邏輯的最少聯(lián)接詞是什么？計算機學(xué)院80計算機學(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是不同的命是不同的命題變元。如果公式題變元。如果公式A A中不出現(xiàn)除中不出現(xiàn)除p p1