第一章命題邏輯

1、2022-3-291l命題邏輯，也稱(chēng)命題演算，記為命題邏輯，也稱(chēng)命題演算，記為L(zhǎng)sLs。它與。它與謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏輯又是謂詞邏輯的基礎(chǔ)。數(shù)理邏輯是用數(shù)輯又是謂詞邏輯的基礎(chǔ)。數(shù)理邏輯是用數(shù)學(xué)方法即通過(guò)引入表意符號(hào)研究推理的學(xué)學(xué)方法即通過(guò)引入表意符號(hào)研究推理的學(xué)問(wèn)。因此，數(shù)理邏輯又名為符號(hào)邏輯。問(wèn)。因此，數(shù)理邏輯又名為符號(hào)邏輯。l命題邏輯是研究由命題為基本單位構(gòu)成的命題邏輯是研究由命題為基本單位構(gòu)成的前提和結(jié)論之間的可推導(dǎo)關(guān)系。前提和結(jié)論之間的可推導(dǎo)關(guān)系。2022-3-292 1.1 命題與聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 1.2 命題變?cè)秃鲜焦矫}變

2、元和合式公式 1.3 公式分類(lèi)與等價(jià)公式公式分類(lèi)與等價(jià)公式 1.4 對(duì)偶式與蘊(yùn)涵式對(duì)偶式與蘊(yùn)涵式 1.5 聯(lián)結(jié)詞的擴(kuò)充與功能完全組聯(lián)結(jié)詞的擴(kuò)充與功能完全組 1.6 公式標(biāo)準(zhǔn)型公式標(biāo)準(zhǔn)型范式范式 1.7 公式的主范式公式的主范式 1.8 命題邏輯的推理理論命題邏輯的推理理論2022-3-293. . 命題的概念命題的概念l所謂命題，是指具有非真必假的陳述句。所謂命題，是指具有非真必假的陳述句。而疑問(wèn)句、祈使句和感嘆句等因都不能而疑問(wèn)句、祈使句和感嘆句等因都不能判斷其真假，故都不是命題。命題僅有判斷其真假，故都不是命題。命題僅有兩種可能的真值兩種可能的真值真和假，且二者只能居真和假，且二者只能居其

3、一。真用其一。真用1 1或或T T表示，假用表示，假用0 0或或F F表示。表示。由于命題只有兩種真值，所以稱(chēng)這種邏由于命題只有兩種真值，所以稱(chēng)這種邏輯為二值邏輯。命題的真值是具有客觀輯為二值邏輯。命題的真值是具有客觀性質(zhì)的，而不是由人的主觀決定的。性質(zhì)的，而不是由人的主觀決定的。2022-3-294l如果一陳述句再也不能分解成更為簡(jiǎn)單的語(yǔ)句，如果一陳述句再也不能分解成更為簡(jiǎn)單的語(yǔ)句，由它構(gòu)成的命題稱(chēng)為原子命題。原子命題是命題由它構(gòu)成的命題稱(chēng)為原子命題。原子命題是命題邏輯的基本單位。邏輯的基本單位。l命題分為兩類(lèi)，第一類(lèi)是原子命題，原子命題用命題分為兩類(lèi)，第一類(lèi)是原子命題，原子命題用大寫(xiě)英文字

4、母大寫(xiě)英文字母P，Q，R或帶下標(biāo)的或帶下標(biāo)的Pi，Qi，Ri，及其數(shù)字表示。其中及其數(shù)字表示。其中P,Q,R Pi，Qi，Ri，及其數(shù)字稱(chēng)為命題標(biāo)識(shí)符及其數(shù)字稱(chēng)為命題標(biāo)識(shí)符.l第二類(lèi)是復(fù)合命題，它由原子命題、命題聯(lián)結(jié)詞第二類(lèi)是復(fù)合命題，它由原子命題、命題聯(lián)結(jié)詞和圓括號(hào)組成。下面給出實(shí)例和圓括號(hào)組成。下面給出實(shí)例,說(shuō)明命題的概念說(shuō)明命題的概念.2022-3-2951.中國(guó)人民是偉大的中國(guó)人民是偉大的.2.雪是黑的雪是黑的.3. 別的星球上有生物別的星球上有生物.4. 我學(xué)英語(yǔ)我學(xué)英語(yǔ),或者我學(xué)日語(yǔ)或者我學(xué)日語(yǔ).5.如果天氣好如果天氣好,那么我去散步那么我去散步.6.今天下雨今天下雨.7.全體起立

5、全體起立!8.明天是否開(kāi)大會(huì)明天是否開(kāi)大會(huì)?9.天氣多好啊天氣多好啊!10.我正在說(shuō)謊我正在說(shuō)謊.2022-3-296 . 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞l定義定義1.1.1設(shè)設(shè)P表示一個(gè)命題，由命題表示一個(gè)命題，由命題聯(lián)結(jié)詞聯(lián)結(jié)詞l l和命題和命題P連接成連接成l lP，稱(chēng)，稱(chēng)l lP為為P的的否定式復(fù)合命題，否定式復(fù)合命題， l lP讀讀“非非P”。稱(chēng)。稱(chēng)l l為為否定聯(lián)結(jié)詞。否定聯(lián)結(jié)詞。l lP是真，當(dāng)且僅當(dāng)是真，當(dāng)且僅當(dāng)P為假；為假；l lP是假，當(dāng)且僅當(dāng)是假，當(dāng)且僅當(dāng)P為真。否定聯(lián)結(jié)詞為真。否定聯(lián)結(jié)詞“l(fā) l”的定義可由表的定義可由表1.1.1表示之。表示之。 2022-3-297表1.1.1

6、 的定義 P P 1 0 0 1l由于否定由于否定 修改了命題，它是對(duì)單個(gè)命題進(jìn)行操作，修改了命題，它是對(duì)單個(gè)命題進(jìn)行操作，稱(chēng)它為一元聯(lián)結(jié)詞。稱(chēng)它為一元聯(lián)結(jié)詞。例例 P : 上海是一個(gè)大城市上海是一個(gè)大城市. P: 上海并不是一個(gè)大城市上海并不是一個(gè)大城市.或或 P: 上海是一個(gè)不大城市上海是一個(gè)不大城市.2022-3-298l定義定義1.1.2 設(shè)設(shè)P和和Q為兩個(gè)命題，由為兩個(gè)命題，由命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞將將P和和Q連接成連接成PQ，稱(chēng)，稱(chēng)PQ為命題為命題P和和Q的合取式復(fù)合命題，的合取式復(fù)合命題，PQ讀做讀做“P與與Q”，或，或“P且且Q”。稱(chēng)。稱(chēng)為合取聯(lián)結(jié)詞。為合取聯(lián)結(jié)詞。l當(dāng)且僅當(dāng)當(dāng)且

7、僅當(dāng)P和和Q的真值同為真，命題的真值同為真，命題PQ的真值才為真；否則，的真值才為真；否則，PQ的真的真值為假。合取聯(lián)結(jié)詞值為假。合取聯(lián)結(jié)詞的定義由表的定義由表1.1.2表示之。表示之。2022-3-299表表1.1.2 的定義的定義 P QP Q 0 00 0 10 1 00 1 112022-3-2910例例1 P: 今天下雨今天下雨. Q: 明天下雨明天下雨.上述命題的合取為上述命題的合取為 P Q: 今天下雨而且明天下雨今天下雨而且明天下雨. P Q: 今天與明天都下雨今天與明天都下雨. P Q: 這兩天都下雨這兩天都下雨.例例2 P:我們?nèi)タ措娪拔覀內(nèi)タ措娪? Q:房間里有十張桌子房

8、間里有十張桌子.上述命題的合取為上述命題的合取為 P Q:我們?nèi)タ措娪芭c房間里有十張桌子我們?nèi)タ措娪芭c房間里有十張桌子.2022-3-2911l定義定義1.1.3 設(shè)設(shè)P和和Q為兩個(gè)命題，由命為兩個(gè)命題，由命題聯(lián)結(jié)詞題聯(lián)結(jié)詞把把P和和Q連接成連接成PQ，稱(chēng)，稱(chēng)PQ為命題為命題P和和Q的析取式復(fù)合命題，的析取式復(fù)合命題，PQ讀做讀做“P或或Q”。稱(chēng)。稱(chēng)為析取聯(lián)結(jié)詞。為析取聯(lián)結(jié)詞。l當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)P和和Q的真值同為假，的真值同為假，PQ的真值為假；否則，的真值為假；否則，PQ的真值為真。的真值為真。析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞的定義由表的定義由表1.1.3表示之。表示之。2022-3-2912表表 1.

9、1.3 的定義的定義PQP Q0000111011112022-3-2913l由定義可知，析取聯(lián)結(jié)詞表示由定義可知，析取聯(lián)結(jié)詞表示“可兼或可兼或”，“不可兼或不可兼或”另有別的聯(lián)結(jié)詞定義另有別的聯(lián)結(jié)詞定義l與合取聯(lián)結(jié)詞一樣，使用析取聯(lián)結(jié)詞時(shí)，也不與合取聯(lián)結(jié)詞一樣，使用析取聯(lián)結(jié)詞時(shí)，也不要求兩命題間一定有任何關(guān)系要求兩命題間一定有任何關(guān)系.例例1 P:他是他是100米賽跑冠軍米賽跑冠軍. Q:他是他是400米賽跑冠軍米賽跑冠軍.上述命題的析取為上述命題的析取為 P Q:他是他是100米或米或400米賽跑冠軍米賽跑冠軍.2022-3-2914l定義定義1.1.4 設(shè)設(shè)P和和Q為兩個(gè)命題，由命題為兩

10、個(gè)命題，由命題聯(lián)結(jié)詞聯(lián)結(jié)詞把把P和和Q連接成連接成PQ，稱(chēng)，稱(chēng)PQ為命題為命題P和和Q的條件式復(fù)合命題，簡(jiǎn)稱(chēng)條的條件式復(fù)合命題，簡(jiǎn)稱(chēng)條件命題。件命題。PQ讀做讀做“P條件條件Q”或者或者“若若P則則Q”。稱(chēng)。稱(chēng)為條件聯(lián)結(jié)詞。為條件聯(lián)結(jié)詞。當(dāng)當(dāng)P的真值為真而的真值為真而Q的真值為假時(shí)，命題的真值為假時(shí)，命題PQ的真值為假；否則，的真值為假；否則，PQ的真值的真值為真。條件聯(lián)結(jié)詞為真。條件聯(lián)結(jié)詞的定義由表的定義由表1.1.4表表示之。示之。2022-3-2915表表 1.1.4 的定義的定義PQP Q0010111001112022-3-2916l在條件命題在條件命題PQ中，命題中，命題P稱(chēng)為稱(chēng)為

11、PQ的前件或的前件或前提，命題前提，命題Q稱(chēng)為稱(chēng)為PQ的后件或結(jié)論。條件命的后件或結(jié)論。條件命題題PQ有多種方式陳述：有多種方式陳述：l“如果如果P，那么，那么Q”；“P僅當(dāng)僅當(dāng)Q”；“Q每當(dāng)每當(dāng)P”；“P是是Q的充分條件的充分條件”；“Q是是P的必要條件的必要條件”等。等。2022-3-2917例例1 P:某動(dòng)物為哺乳動(dòng)物某動(dòng)物為哺乳動(dòng)物. Q:哺乳動(dòng)物必胎生哺乳動(dòng)物必胎生. P Q:如果某動(dòng)物為哺乳動(dòng)物如果某動(dòng)物為哺乳動(dòng)物,則它必胎生則它必胎生.例例2 P:雪是黑的雪是黑的. Q:太陽(yáng)從西邊出來(lái)太陽(yáng)從西邊出來(lái). P Q:如果雪是黑的如果雪是黑的,那么太陽(yáng)從西邊出來(lái)那么太陽(yáng)從西邊出來(lái).202

12、2-3-2918l定義定義1.1.5 令令P、Q是兩個(gè)命題，由命題聯(lián)是兩個(gè)命題，由命題聯(lián)結(jié)詞結(jié)詞把把P和和Q連接成連接成P Q，稱(chēng)，稱(chēng)P Q為命題為命題P和和Q的雙條件式復(fù)合命題，簡(jiǎn)稱(chēng)的雙條件式復(fù)合命題，簡(jiǎn)稱(chēng)雙條件命題，雙條件命題，P Q讀做讀做“P當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)Q”，或或“P等價(jià)等價(jià)Q”。稱(chēng)。稱(chēng)為雙條件聯(lián)結(jié)為雙條件聯(lián)結(jié)l當(dāng)當(dāng)P和和Q的真值相同時(shí)，的真值相同時(shí)，P Q的真值為的真值為真；否則，真；否則，P Q的真值為假。雙條件聯(lián)的真值為假。雙條件聯(lián)結(jié)詞結(jié)詞的定義由表的定義由表1.1.5表示之。表示之。2022-3-2919表表 1.1.5 的定義的定義PQP Q001010100111202

13、2-3-2920例例1 P:燕子飛回南方燕子飛回南方. Q:春天來(lái)了春天來(lái)了. P Q:燕子飛回南方燕子飛回南方,當(dāng)且僅當(dāng)春天來(lái)了當(dāng)且僅當(dāng)春天來(lái)了.例例2 P:2+2=4. Q:雪是黑的雪是黑的. P Q:2+2=4,當(dāng)且僅當(dāng)雪是黑的當(dāng)且僅當(dāng)雪是黑的.2022-3-2921l命題命題 1) 命題的概念命題的概念 2) 命題的判斷命題的判斷 3) 命題的表示命題的表示 4) 原子命題及復(fù)合命題原子命題及復(fù)合命題l聯(lián)結(jié)詞聯(lián)結(jié)詞 1)否定否定 2)合取合取 3)析取析取 4)條件條件 5)雙雙條件條件2022-3-2922l在本節(jié)結(jié)束時(shí)，應(yīng)強(qiáng)調(diào)指出的是：復(fù)合在本節(jié)結(jié)束時(shí)，應(yīng)強(qiáng)調(diào)指出的是：復(fù)合命題的真

14、值只取決于各原子命題的真值，命題的真值只取決于各原子命題的真值，而與它們的內(nèi)容、含義無(wú)關(guān)，與原子命而與它們的內(nèi)容、含義無(wú)關(guān)，與原子命題之間是否有關(guān)系無(wú)關(guān)。理解和掌握這題之間是否有關(guān)系無(wú)關(guān)。理解和掌握這一點(diǎn)是至關(guān)重要的，請(qǐng)讀者認(rèn)真去領(lǐng)會(huì)。一點(diǎn)是至關(guān)重要的，請(qǐng)讀者認(rèn)真去領(lǐng)會(huì)。2022-3-29231.指出下列語(yǔ)句那些是命題指出下列語(yǔ)句那些是命題,那些不是那些不是,若是命題若是命題,指出它的真值指出它的真值.(1)離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)系的一門(mén)必修課離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)系的一門(mén)必修課.(2)計(jì)算機(jī)有空嗎計(jì)算機(jī)有空嗎?(3)明天我去看電影明天我去看電影.(4)請(qǐng)勿隨地吐痰請(qǐng)勿隨地吐痰!(5)不存在最大質(zhì)

15、數(shù)不存在最大質(zhì)數(shù).(6)9+5 12.2022-3-2924 2. P: 天下雪天下雪. Q: 我將去鎮(zhèn)上我將去鎮(zhèn)上. R: 我有時(shí)間我有時(shí)間. 以符號(hào)形式寫(xiě)出下列命題以符號(hào)形式寫(xiě)出下列命題 a) 如果天不下雨和我有時(shí)間如果天不下雨和我有時(shí)間,那么我將去鎮(zhèn)上那么我將去鎮(zhèn)上. b) 我將去鎮(zhèn)上我將去鎮(zhèn)上,僅當(dāng)我有時(shí)間時(shí)僅當(dāng)我有時(shí)間時(shí). c) 天不下雪天不下雪. d) 天下雪天下雪,那么我不去鎮(zhèn)上那么我不去鎮(zhèn)上.2022-3-2925 . 命題變?cè)}變?cè)猯在命題邏輯中，命題又有命題常元和命題在命題邏輯中，命題又有命題常元和命題變?cè)?。一個(gè)確定的具體的命題，稱(chēng)為變?cè)?。一個(gè)確定的具體的命題，稱(chēng)

16、為命題常元；一個(gè)不確定的泛指的任意命題，命題常元；一個(gè)不確定的泛指的任意命題，稱(chēng)為命題變?cè)ｏ@然，命題變?cè)皇敲}，稱(chēng)為命題變?cè)?。顯然，命題變?cè)皇敲}，只有用一個(gè)特定的命題取代才能確定它的只有用一個(gè)特定的命題取代才能確定它的真值：真或假。這時(shí)也說(shuō)對(duì)該命題變?cè)刚嬷担赫婊蚣?。這時(shí)也說(shuō)對(duì)該命題變?cè)概烧嬷?。派真值?022-3-2926l命題常元和命題變?cè)捎米帜该}常元和命題變?cè)捎米帜窹等表示。等表示。由于在命題邏輯中并不關(guān)心具體命題的由于在命題邏輯中并不關(guān)心具體命題的涵義，只關(guān)心其真值，因此，可以形式涵義，只關(guān)心其真值，因此，可以形式地定義它們?nèi)缦拢旱囟x它們?nèi)缦拢?l定義定義1.2.

17、1以真或以真或1、假或、假或0為其變域?yàn)槠渥冇虻淖冊(cè)?，稱(chēng)為命題變?cè)?；真或的變?cè)?，稱(chēng)為命題變?cè)?；真?、假或、假或0稱(chēng)為命題常元。稱(chēng)為命題常元。2022-3-2927l2. 合式公式合式公式l通常把含有命題變?cè)臄嘌苑Q(chēng)為命題公通常把含有命題變?cè)臄嘌苑Q(chēng)為命題公式。但這沒(méi)能指出命題公式的結(jié)構(gòu)，因式。但這沒(méi)能指出命題公式的結(jié)構(gòu)，因?yàn)椴皇撬杏擅}變?cè)?、?lián)結(jié)詞和括號(hào)為不是所有由命題變?cè)⒙?lián)結(jié)詞和括號(hào)所組成的字符串都能成為命題公式。為所組成的字符串都能成為命題公式。為此常使用歸納定義命題公式，以便構(gòu)成此常使用歸納定義命題公式，以便構(gòu)成的公式有規(guī)則可循。由這種定義產(chǎn)生的的公式有規(guī)則可循。由這種定義產(chǎn)生的公

18、式稱(chēng)為合式公式。公式稱(chēng)為合式公式。l定義定義1.2.2單個(gè)命題變?cè)兔}常元單個(gè)命題變?cè)兔}常元稱(chēng)為原子命題公式，簡(jiǎn)稱(chēng)原子公式。稱(chēng)為原子命題公式，簡(jiǎn)稱(chēng)原子公式。2022-3-2928l定義定義1.2.3合式公式是由下列規(guī)則生合式公式是由下列規(guī)則生成的公式：成的公式：l單個(gè)原子公式是合式公式。單個(gè)原子公式是合式公式。l若若A是一個(gè)合式公式，則是一個(gè)合式公式，則(lA)也是一個(gè)也是一個(gè)合式公式。合式公式。l若若A、B是合式公式，則是合式公式，則(AB)、(AB)、(AB)和和(A B)都是合式公都是合式公式。式。l只有有限次使用、和生成的公只有有限次使用、和生成的公式才是合式公式。式才是合式公式

19、。2022-3-2929l當(dāng)合式公式比較復(fù)雜時(shí)，常常使用很多當(dāng)合式公式比較復(fù)雜時(shí)，常常使用很多圓括號(hào)，為了減少圓括號(hào)的使用量，可圓括號(hào)，為了減少圓括號(hào)的使用量，可作以下約定：作以下約定：l規(guī)定聯(lián)結(jié)詞的優(yōu)先級(jí)由高到低的次序規(guī)定聯(lián)結(jié)詞的優(yōu)先級(jí)由高到低的次序?yàn)椋簽椋簂 l、 l相同的聯(lián)結(jié)詞按從左至右次序計(jì)算時(shí)，相同的聯(lián)結(jié)詞按從左至右次序計(jì)算時(shí)，圓括號(hào)可省略。圓括號(hào)可省略。l最外層的圓括號(hào)可以省略。最外層的圓括號(hào)可以省略。l為了方便計(jì)，合式公式也簡(jiǎn)稱(chēng)公式。為了方便計(jì)，合式公式也簡(jiǎn)稱(chēng)公式。2022-3-2930 .公式真值表公式真值表l定義定義1.2.4對(duì)于公式中命題變?cè)拿繉?duì)于公式中命題變?cè)拿恳环N可

20、能的真值指派，以及由它們確定一種可能的真值指派，以及由它們確定出的公式真值所列成的表，稱(chēng)為該公式出的公式真值所列成的表，稱(chēng)為該公式的真值表。的真值表。l定義定義1.2.5如果如果B是公式是公式A中的一部分，中的一部分，且且B為公式，則稱(chēng)為公式，則稱(chēng)B是公式是公式A的子公式。的子公式。2022-3-2931l用歸納法不難證明，對(duì)于含有用歸納法不難證明，對(duì)于含有n個(gè)命題變個(gè)命題變?cè)墓剑性墓?，?n個(gè)真值指派，即在該公個(gè)真值指派，即在該公式的真值表中有式的真值表中有2n行。行。l為方便構(gòu)造真值表，為方便構(gòu)造真值表，l特約定如下：特約定如下：l 命題變?cè)醋值湫蚺帕小Ｃ}變?cè)醋值湫蚺帕?。l

21、 對(duì)每個(gè)指派，以二進(jìn)制數(shù)從小到大或?qū)γ總€(gè)指派，以二進(jìn)制數(shù)從小到大或從大到小順序列出。從大到小順序列出。l 若公式較復(fù)雜，可先列出各子公式的若公式較復(fù)雜，可先列出各子公式的真值真值(若有括號(hào)，則應(yīng)從里層向外層展開(kāi)若有括號(hào)，則應(yīng)從里層向外層展開(kāi))，最后列出所求公式的真值。最后列出所求公式的真值。2022-3-2932 4.命題的符號(hào)化命題的符號(hào)化l把一個(gè)用文字?jǐn)⑹龅拿}相應(yīng)地寫(xiě)成由把一個(gè)用文字?jǐn)⑹龅拿}相應(yīng)地寫(xiě)成由命題標(biāo)識(shí)符、聯(lián)結(jié)詞和圓括號(hào)表示的合命題標(biāo)識(shí)符、聯(lián)結(jié)詞和圓括號(hào)表示的合式公式，稱(chēng)為式公式，稱(chēng)為l命題的符號(hào)化。符號(hào)化應(yīng)該注意下列事命題的符號(hào)化。符號(hào)化應(yīng)該注意下列事項(xiàng)項(xiàng):l 確定給定句子是

22、否為命題。確定給定句子是否為命題。l 句子中連詞是否為命題聯(lián)結(jié)詞。句子中連詞是否為命題聯(lián)結(jié)詞。l 要正確地表示原子命題和適當(dāng)選擇命要正確地表示原子命題和適當(dāng)選擇命題聯(lián)結(jié)詞。題聯(lián)結(jié)詞。2022-3-2933l 命題符號(hào)化是很重要的，一定要掌命題符號(hào)化是很重要的，一定要掌握好，在命題推理中常常最先遇到握好，在命題推理中常常最先遇到的就是符號(hào)化一個(gè)問(wèn)題，解決不好，的就是符號(hào)化一個(gè)問(wèn)題，解決不好，等于說(shuō)推理的首要前提沒(méi)有了。等于說(shuō)推理的首要前提沒(méi)有了。2022-3-2934 . 公式分類(lèi)公式分類(lèi)l定義定義1.3.1設(shè)設(shè) A 為任意公式，則為任意公式，則l 對(duì)應(yīng)每一個(gè)指派，公式對(duì)應(yīng)每一個(gè)指派，公式 A

23、均相應(yīng)確定均相應(yīng)確定真值為真，稱(chēng)真值為真，稱(chēng) A 為重言式，或永真式。為重言式，或永真式。l 對(duì)應(yīng)每一個(gè)指派，公式對(duì)應(yīng)每一個(gè)指派，公式 A 均相應(yīng)確定均相應(yīng)確定真值為假，稱(chēng)真值為假，稱(chēng) A 為矛盾式，或永假式。為矛盾式，或永假式。l 至少存在一個(gè)指派，公式至少存在一個(gè)指派，公式 A 相應(yīng)確定相應(yīng)確定真值為真，稱(chēng)真值為真，稱(chēng) A 為可滿足式。為可滿足式。2022-3-2935l由定義可知，重言式必是可滿足式，反由定義可知，重言式必是可滿足式，反之一般不真。之一般不真。l重點(diǎn)將研究重言式，它最有用，因?yàn)樗攸c(diǎn)將研究重言式，它最有用，因?yàn)樗幸韵绿攸c(diǎn)：有以下特點(diǎn)：l重言式的否定是矛盾式，矛盾式的否重

24、言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。定是重言式，這樣只研究其一就可以了。l兩重言式的合取式、析取式、條件式兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由和雙條件式等都仍是重言式。于是，由簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。l由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價(jià)式和蘊(yùn)涵式。多有用等價(jià)式和蘊(yùn)涵式。2022-3-2936l判定給定公式是否為永真式、永假式或判定給定公式是否為永真式、永假式或可滿足式的問(wèn)題，稱(chēng)為給定公式的判定可滿足式的問(wèn)題，稱(chēng)為給定公式的判定問(wèn)題。問(wèn)題。l在在Ls中，

25、由于任何一個(gè)命題公式的指派中，由于任何一個(gè)命題公式的指派數(shù)目總是有限的，所以數(shù)目總是有限的，所以Ls的判定問(wèn)題是的判定問(wèn)題是可解的。其判定方法有真值表法和公式可解的。其判定方法有真值表法和公式推演法。推演法。2022-3-2937 .等價(jià)公式等價(jià)公式l定義定義1.3.2設(shè)設(shè)A和和B是兩個(gè)命題公式，是兩個(gè)命題公式，如果如果A、B在其任意指派下，其真值都是在其任意指派下，其真值都是相同的，則稱(chēng)相同的，則稱(chēng)A和和B是等價(jià)的，或邏輯相是等價(jià)的，或邏輯相等，記作等，記作AB，讀作，讀作A等價(jià)等價(jià)B，稱(chēng)，稱(chēng)AB為等價(jià)式。為等價(jià)式。l顯然，若公式顯然，若公式A和和B的真值表是相同的，的真值表是相同的，則則A

26、和和B等價(jià)。因此，驗(yàn)證兩公式是否等等價(jià)。因此，驗(yàn)證兩公式是否等價(jià)，只需做出它們的真值表即可。價(jià)，只需做出它們的真值表即可。2022-3-2938l在這里，請(qǐng)讀者注意在這里，請(qǐng)讀者注意和和的區(qū)別與聯(lián)的區(qū)別與聯(lián)系。系。l區(qū)別：區(qū)別：是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語(yǔ)言是邏輯聯(lián)結(jié)詞，屬于目標(biāo)語(yǔ)言中的符號(hào)，它出現(xiàn)在命題公式中；中的符號(hào)，它出現(xiàn)在命題公式中；不不是邏輯聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，是邏輯聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，表示兩個(gè)命題公式的一種關(guān)系，不屬于表示兩個(gè)命題公式的一種關(guān)系，不屬于這兩個(gè)公式的任何一個(gè)公式中的符號(hào)這兩個(gè)公式的任何一個(gè)公式中的符號(hào)l聯(lián)系：可用下面定理表明之。聯(lián)系：可用下面定理表明之。2

27、022-3-2939l定理定理1.3.1A B當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)AB是永是永真式真式.有時(shí)也稱(chēng)有時(shí)也稱(chēng)A B是永真雙條件式是永真雙條件式l等價(jià)式有下列性質(zhì)：等價(jià)式有下列性質(zhì)：l 自反性，即對(duì)任意公式自反性，即對(duì)任意公式A，有，有A A。l 對(duì)稱(chēng)性，即對(duì)任意公式對(duì)稱(chēng)性，即對(duì)任意公式A和和B，若，若A B，則，則B A。l 傳遞性，即對(duì)任意公式傳遞性，即對(duì)任意公式A、B和和C，若，若A B、B C，則，則A C。2022-3-2940. .基本等價(jià)式基本等價(jià)式命題定律命題定律l在判定公式間是否等價(jià)，有一些簡(jiǎn)單而在判定公式間是否等價(jià)，有一些簡(jiǎn)單而又經(jīng)常使用的等價(jià)式，稱(chēng)為基本等價(jià)式又經(jīng)常使用的等價(jià)式，稱(chēng)

28、為基本等價(jià)式或稱(chēng)命題定律。牢固地記住它并能熟練或稱(chēng)命題定律。牢固地記住它并能熟練運(yùn)用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一，讀運(yùn)用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一，讀者應(yīng)該注意到這一點(diǎn)。現(xiàn)將這些命題定者應(yīng)該注意到這一點(diǎn)?，F(xiàn)將這些命題定律列出如下：律列出如下：l(1)(1)雙否定：雙否定： A AA A。l(2)(2)交換律：交換律：A AB BB BA A，A AB BB BA A，A AB BB BA A。2022-3-2941l(3) (3) 結(jié)合律：結(jié)合律：( (A AB B)C CA A(B BC C) )，( (A AB B)C CA A(B BC C) )，( (A AB B) )C CA A( (

29、B BC C) )。l(4) (4) 分配律：分配律：A A(B BC C) )( (A AB B)()(A AC C) )，A A(B BC C) )( (A AB B)()(A AC C) )。l(5) (5) 德德摩根律：摩根律： ( (A AB B) )A A B B， ( (A AB B) )A A B B。l(6) (6) 等冪律：等冪律：A AA AA A，A AA AA A。2022-3-2942l(7) (7) 同一律：同一律：A AT TA A，A AF FA A。l(8) (8) 零零 律：律：A AF FF F，A AT TT T。l(9) (9) 吸收律：吸收律：A

30、A(A AB B) )A A，A A(A AB B) )A A。l(10) (10) 互補(bǔ)律：互補(bǔ)律：A A A AF F，( (矛盾律矛盾律) )lA A A AT T。( (排中律排中律) )l(11) (11) 條件式轉(zhuǎn)化律：條件式轉(zhuǎn)化律：A AB BA AB B，A AB BB B A A。2022-3-2943l(12) (12) 雙條件式轉(zhuǎn)化律：雙條件式轉(zhuǎn)化律：A AB B( (A AB B)()(B BA A) )( (A AB B)()( A A B B) )l A AB B( (A AB B) )l(13) (13) 輸出律：輸出律：( (A AB B)C CA A(B BC

31、 C) )。l(14) (14) 歸謬律：歸謬律：( (A AB B)()(A A B B) )A A。l上面這些定律，即是通常所說(shuō)的布爾代上面這些定律，即是通常所說(shuō)的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。正確性利用真值表是不難給出證明的。2022-3-2944. .代入規(guī)則和替換規(guī)則代入規(guī)則和替換規(guī)則l在定義合成公式時(shí)，已看到了邏輯聯(lián)結(jié)在定義合成公式時(shí)，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這詞能夠從已知公式形成新的公式，從這個(gè)意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除個(gè)意義上可把邏輯聯(lián)結(jié)詞看成運(yùn)算。除邏輯聯(lián)結(jié)詞外，還要介

32、紹邏輯聯(lián)結(jié)詞外，還要介紹“代入代入”和和“替換替換”，它們也有從已知公式得到新，它們也有從已知公式得到新的公式的作用，因此有人也將它們看成的公式的作用，因此有人也將它們看成運(yùn)算，這不無(wú)道理，而且在今后討論中，運(yùn)算，這不無(wú)道理，而且在今后討論中，它的作用也是不容忽視的。它的作用也是不容忽視的。2022-3-2945 (1)代入規(guī)則代入規(guī)則l定理定理1.3.2 在一個(gè)永真式在一個(gè)永真式A A中，任何一個(gè)中，任何一個(gè)原子命題變?cè)用}變?cè)猂出現(xiàn)的每一處，出現(xiàn)的每一處， 用另一用另一個(gè)公式代入，所得公式個(gè)公式代入，所得公式B仍是永真式。本仍是永真式。本定理稱(chēng)為代入規(guī)則。定理稱(chēng)為代入規(guī)則。 (2)替換

33、規(guī)則替換規(guī)則l定理定理1.3.3 設(shè)設(shè)A1是合式公式是合式公式A的子公式，的子公式，若若A1B1，并且將，并且將A中的中的A1用用B1 替換得替換得到公式到公式B，則，則AB。稱(chēng)該定理為替換規(guī)。稱(chēng)該定理為替換規(guī)則。則。l滿足定理滿足定理1.3.3條件的替換，稱(chēng)為等價(jià)替條件的替換，稱(chēng)為等價(jià)替換。換。2022-3-2946l代入和替換有兩點(diǎn)區(qū)別：代入和替換有兩點(diǎn)區(qū)別：l 代入是對(duì)原子命題變?cè)缘?，而替代入是?duì)原子命題變?cè)缘?，而替換可對(duì)命題公式實(shí)行。換可對(duì)命題公式實(shí)行。l 代入必須是處處代入，替換則可部分代入必須是處處代入，替換則可部分替換，亦可全部替換。替換，亦可全部替換。2022-3-29

34、47 .對(duì)偶式對(duì)偶式l在上節(jié)介紹的命題定律中，多數(shù)是成對(duì)在上節(jié)介紹的命題定律中，多數(shù)是成對(duì)出現(xiàn)的，這些成對(duì)出現(xiàn)的定律就是對(duì)偶出現(xiàn)的，這些成對(duì)出現(xiàn)的定律就是對(duì)偶性質(zhì)的反映，即對(duì)偶式。利用對(duì)偶式的性質(zhì)的反映，即對(duì)偶式。利用對(duì)偶式的命題定律，可以擴(kuò)大等價(jià)式的個(gè)數(shù)，也命題定律，可以擴(kuò)大等價(jià)式的個(gè)數(shù)，也可減少證明的次數(shù)?？蓽p少證明的次數(shù)。2022-3-2948l定義定義1.4.1 在給定的僅使用聯(lián)結(jié)詞在給定的僅使用聯(lián)結(jié)詞 、和和的命題公式的命題公式A中，若把中，若把和和互換，互換，F(xiàn)和和T互換而得到一個(gè)命題公式互換而得到一個(gè)命題公式A*，則稱(chēng)，則稱(chēng)A*為為A的對(duì)偶式。的對(duì)偶式。l顯然，顯然，A也是也是A

35、*的對(duì)偶式?？梢?jiàn)的對(duì)偶式?？梢?jiàn)A與與A*互互為對(duì)偶式。為對(duì)偶式。2022-3-2949l定理定理1.4.1(對(duì)偶定理對(duì)偶定理) 設(shè)設(shè)A和和A*互為對(duì)偶互為對(duì)偶式，式，P1，P2，Pn是出現(xiàn)是出現(xiàn)A和和A* 中的中的原子命題變?cè)瑒t原子命題變?cè)?，則l A(P1，P2，Pn)A*( P1， P2， Pn)l A( P1， P2， Pn)A*(P1，P2，Pn)l表明，公式表明，公式A的否定等價(jià)于其命題變?cè)姆穸ǖ葍r(jià)于其命題變?cè)穸ǖ膶?duì)偶式；表明，命題變?cè)穸ǚ穸ǖ膶?duì)偶式；表明，命題變?cè)穸ǖ墓降葍r(jià)于對(duì)偶式之否定。的公式等價(jià)于對(duì)偶式之否定。2022-3-2950l定理定理1.4.2 設(shè)設(shè)A和和B為

36、兩個(gè)命題公式，若為兩個(gè)命題公式，若AB則則A*B*。l有了等價(jià)式、代入規(guī)則、替換規(guī)則和對(duì)有了等價(jià)式、代入規(guī)則、替換規(guī)則和對(duì)偶定理，便可以得到更多的永真式，證偶定理，便可以得到更多的永真式，證明更多的等價(jià)式，使化簡(jiǎn)命題公式更為明更多的等價(jià)式，使化簡(jiǎn)命題公式更為方便。方便。2022-3-2951 .蘊(yùn)涵式蘊(yùn)涵式l定義定義1.4.2 設(shè)設(shè)A和和B是兩個(gè)命題公式，若是兩個(gè)命題公式，若AB是永真式，則稱(chēng)是永真式，則稱(chēng)A蘊(yùn)涵蘊(yùn)涵B，記作，記作AB，稱(chēng)，稱(chēng)AB為蘊(yùn)涵式或永真條件式。為蘊(yùn)涵式或永真條件式。l符號(hào)符號(hào)和和的區(qū)別與聯(lián)系類(lèi)似于的區(qū)別與聯(lián)系類(lèi)似于和和的關(guān)系。區(qū)別：的關(guān)系。區(qū)別：是邏輯聯(lián)結(jié)詞，屬于是邏輯

37、聯(lián)結(jié)詞，屬于對(duì)象語(yǔ)言中的符號(hào)，是公式中的符號(hào)；對(duì)象語(yǔ)言中的符號(hào)，是公式中的符號(hào)；而而不是聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，不是聯(lián)結(jié)詞，屬于元語(yǔ)言中的符號(hào)，表示兩個(gè)公式之間的關(guān)系，不是兩公式表示兩個(gè)公式之間的關(guān)系，不是兩公式中符號(hào)。聯(lián)系：中符號(hào)。聯(lián)系：AB成立，其充要條件成立，其充要條件AB是永真式。是永真式。2022-3-2952l蘊(yùn)涵式有下列性質(zhì)：蘊(yùn)涵式有下列性質(zhì)：l 自反性，即對(duì)任意公式自反性，即對(duì)任意公式A，有，有AA。l 傳遞性，即對(duì)任意公式傳遞性，即對(duì)任意公式A、B和和C，若，若AB，BC，則，則AC。l 對(duì)任意公式對(duì)任意公式A、B和和C，若，若AB，AC，則，則A(BC)。l 對(duì)任意公式

38、對(duì)任意公式A、B和和C，若，若AC，BC，則，則ABC。2022-3-2953l這些性質(zhì)的正確性，請(qǐng)讀者自己驗(yàn)證。這些性質(zhì)的正確性，請(qǐng)讀者自己驗(yàn)證。l下面給出等價(jià)式與蘊(yùn)涵式之間的關(guān)系。下面給出等價(jià)式與蘊(yùn)涵式之間的關(guān)系。l定理定理1.4.3 設(shè)設(shè)A和和B是兩命題公式，是兩命題公式，AB的充要條件是的充要條件是AB且且BA。2022-3-2954 .蘊(yùn)涵式證明方法蘊(yùn)涵式證明方法l除真值表外，還有兩種方法：除真值表外，還有兩種方法： 前件真導(dǎo)后件真方法前件真導(dǎo)后件真方法l設(shè)公式的前件為真，若能推導(dǎo)出后件也設(shè)公式的前件為真，若能推導(dǎo)出后件也為真，則條件式是永真式，故蘊(yùn)涵式成為真，則條件式是永真式，故蘊(yùn)

39、涵式成立。立。l因?yàn)橛C因?yàn)橛CAB，即證，即證AB是永真式。是永真式。對(duì)于對(duì)于AB，除在，除在A取真和取真和B取假時(shí)，取假時(shí)，AB為假外，余下為假外，余下AB皆為真。所以，皆為真。所以，若若AB的前件的前件A為真，由此可推出為真，由此可推出B亦亦為真，則為真，則AB是永真式，即是永真式，即AB。2022-3-2955 后件假導(dǎo)前件假方法后件假導(dǎo)前件假方法l設(shè)條件式后件為假，若能推導(dǎo)出前件也設(shè)條件式后件為假，若能推導(dǎo)出前件也為假，則條件式是永真式，即蘊(yùn)涵式成為假，則條件式是永真式，即蘊(yùn)涵式成立。立。l因?yàn)槿粢驗(yàn)槿鬉B的后件的后件B取假，由此可推出取假，由此可推出A取假，即推證了：取假，即推證了

40、： BA。又因。又因ABB A，故，故AB成立。成立。2022-3-2956 . 聯(lián)結(jié)詞的擴(kuò)充聯(lián)結(jié)詞的擴(kuò)充l定義定義1.5.1 設(shè)設(shè)P和和Q是任兩個(gè)原子命題，是任兩個(gè)原子命題，l由合取非聯(lián)結(jié)詞由合取非聯(lián)結(jié)詞和和P，Q連接成連接成PQ，稱(chēng)它為稱(chēng)它為P和和Q的合取非式復(fù)合命題，讀作的合取非式復(fù)合命題，讀作“P合取非合取非Q”。PQ的真值由命題的真值由命題P和和Q的真值確定：當(dāng)且僅當(dāng)?shù)恼嬷荡_定：當(dāng)且僅當(dāng)P和和 Q均為均為時(shí)，時(shí)，PQ為為，否則，否則PQ為為?！昂先》呛先》恰庇殖７Q(chēng)為又常稱(chēng)為“與非與非”。2022-3-2957l由析取非聯(lián)結(jié)詞由析取非聯(lián)結(jié)詞和和P，Q連接成連接成PQ，稱(chēng)它為稱(chēng)它為P和和

41、Q的析取非式復(fù)合命題，讀作的析取非式復(fù)合命題，讀作“P析取非析取非Q”。PQ的真值由的真值由P和和Q的真的真值確定：當(dāng)且僅當(dāng)值確定：當(dāng)且僅當(dāng)P和和Q均為均為時(shí)，時(shí)，PQ為為，否則，否則PQ為為。“析取非析取非”又常又常稱(chēng)為稱(chēng)為“或非或非”。l由條件非聯(lián)結(jié)詞由條件非聯(lián)結(jié)詞 和和P，Q連接成連接成P Q，稱(chēng)它為稱(chēng)它為P和和Q的條件非式復(fù)合命題，讀作的條件非式復(fù)合命題，讀作“P條件非條件非Q”。P Q的真值由的真值由P和和Q的真的真值確定：當(dāng)且僅當(dāng)值確定：當(dāng)且僅當(dāng)P為為而而Q為為時(shí)，時(shí)，P Q為為；否則；否則P Q為為。2022-3-2958l由雙條件非聯(lián)結(jié)詞由雙條件非聯(lián)結(jié)詞 把把P，Q連接成連接成

42、P Q，稱(chēng)它為，稱(chēng)它為P和和Q的雙條件非式復(fù)合命的雙條件非式復(fù)合命題，讀作題，讀作“P雙條件非雙條件非Q”。P Q的真值的真值由由P和和 Q的真值確定：當(dāng)且僅當(dāng)?shù)恼嬷荡_定：當(dāng)且僅當(dāng)P和和Q的的真值不同時(shí)，真值不同時(shí)，P Q為為，否則，否則P Q為為?！半p條件非雙條件非”又常稱(chēng)為又常稱(chēng)為“異或異或”，也常，也常用符號(hào)用符號(hào) 表示之。表示之。l上面上面4個(gè)聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，其真值個(gè)聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，其真值表如下：表如下：2022-3-2959PQP QP QP QP Q0011000110011010111100002022-3-2960l由表可知，由表可知，P Q(P Q)l P Q(P

43、 Q)l P Q(PQ)l P Q(PQ)2022-3-2961 .與非、或非和異或的性質(zhì)與非、或非和異或的性質(zhì)l與非、或非以及異或在計(jì)算機(jī)科學(xué)中是與非、或非以及異或在計(jì)算機(jī)科學(xué)中是經(jīng)常使用的經(jīng)常使用的3個(gè)聯(lián)結(jié)詞，因此，掌握它們個(gè)聯(lián)結(jié)詞，因此，掌握它們的性質(zhì)是十分必要的。令的性質(zhì)是十分必要的。令P、Q和和R是原是原子命題變?cè)?。子命題變?cè)?與非的性質(zhì)與非的性質(zhì)l(a)PQQPl(b) PPPl(c) (PQ)(PQ)PQl(d) (PP)(QQ)PQ2022-3-2962 或非的性質(zhì)或非的性質(zhì)l(a) PQQPl(b) PPPl(c)(PQ)(PQ)PQl(d) (PP)(QQ)PQl從上述的

44、性質(zhì)可知，聯(lián)結(jié)詞從上述的性質(zhì)可知，聯(lián)結(jié)詞 、 和和 可分可分別用聯(lián)結(jié)詞別用聯(lián)結(jié)詞 或者或者 取代，讀者可以自行取代，讀者可以自行驗(yàn)證，驗(yàn)證， 和和 都不滿足結(jié)合律。都不滿足結(jié)合律。2022-3-2963 異或的性質(zhì)異或的性質(zhì)l(a)P QQ Pl(b) P (Q R)(P Q) Rl(c) P(Q R)(PQ) (PR)l(d) P PF，F(xiàn) PP，T PPl(e) 若若P QR，則，則Q RP，P PQ，且且P Q RF。2022-3-2964l以上所有性質(zhì)，用真值表或命題定律都以上所有性質(zhì)，用真值表或命題定律都是不難證明的。是不難證明的。l至此，已有了至此，已有了9個(gè)聯(lián)結(jié)詞，是否還需要擴(kuò)個(gè)

45、聯(lián)結(jié)詞，是否還需要擴(kuò)充呢？事實(shí)上，兩上命題變無(wú)充呢？事實(shí)上，兩上命題變無(wú)P和和Q，與，與9個(gè)聯(lián)結(jié)詞一共可構(gòu)成個(gè)聯(lián)結(jié)詞一共可構(gòu)成 類(lèi)命題公式，類(lèi)命題公式，如下表示之：如下表示之：2222022-3-2965PQF TP Q P Q P Q P Q P Q P Q000 100 110101010 101 100110100 110 010110110 111 001010所用的所用的聯(lián)結(jié)詞聯(lián)結(jié)詞序號(hào)序號(hào)1 234 56789102022-3-2966PQP Q P Q P Q P Q P Q P Q00101010011001011001011011101010所用聯(lián)結(jié)所用聯(lián)結(jié)詞詞序號(hào)序號(hào)111

46、213141516續(xù)表2022-3-2967l從列表可知，除命題常元從列表可知，除命題常元F，T及命題變及命題變?cè)旧硗?，命題聯(lián)結(jié)詞一共有元本身外，命題聯(lián)結(jié)詞一共有9個(gè)就夠了。個(gè)就夠了。為了方便，可規(guī)定其優(yōu)先級(jí)，由高到低為了方便，可規(guī)定其優(yōu)先級(jí)，由高到低次序?yàn)榇涡驗(yàn)?， ， ，等。等。2022-3-2968 .聯(lián)結(jié)詞功能完全組聯(lián)結(jié)詞功能完全組l已知有已知有9個(gè)聯(lián)結(jié)詞就夠用了，能不能少呢？個(gè)聯(lián)結(jié)詞就夠用了，能不能少呢？若能少，表明有些聯(lián)結(jié)詞的邏輯功能可若能少，表明有些聯(lián)結(jié)詞的邏輯功能可由其他聯(lián)結(jié)詞替代。事實(shí)上，也確實(shí)如由其他聯(lián)結(jié)詞替代。事實(shí)上，也確實(shí)如此，因?yàn)橛邢铝械葍r(jià)式：此，因?yàn)橛邢铝械葍r(jià)式：

47、lP Q(P Q)lP Q(P Q)lP Q(PQ)lP Q(PQ)l可見(jiàn)，擴(kuò)充的可見(jiàn)，擴(kuò)充的4個(gè)聯(lián)結(jié)詞個(gè)聯(lián)結(jié)詞 ， ， 和和 能能由原有由原有5個(gè)聯(lián)結(jié)詞分別替代之。個(gè)聯(lián)結(jié)詞分別替代之。2022-3-2969l又由命題定律：又由命題定律：lPQ( P Q) ( Q P)lPQP QlP Q( PQ)lP Q( PQ)l可知，原有可知，原有5個(gè)聯(lián)結(jié)詞個(gè)聯(lián)結(jié)詞 ， ， ，和和又又能由聯(lián)結(jié)詞組能由聯(lián)結(jié)詞組 ， 或或 ， 取代。那么，取代。那么，究竟最少用幾個(gè)聯(lián)結(jié)詞？就是說(shuō)，用最少究竟最少用幾個(gè)聯(lián)結(jié)詞？就是說(shuō)，用最少的幾個(gè)聯(lián)結(jié)詞就能等價(jià)表示所有的命題公的幾個(gè)聯(lián)結(jié)詞就能等價(jià)表示所有的命題公式?；蛘哒f(shuō)，用

48、最少的幾個(gè)聯(lián)結(jié)詞就能替式?；蛘哒f(shuō)，用最少的幾個(gè)聯(lián)結(jié)詞就能替代所有聯(lián)結(jié)詞的功能。這便是所要定義的代所有聯(lián)結(jié)詞的功能。這便是所要定義的聯(lián)結(jié)詞功能完全組。聯(lián)結(jié)詞功能完全組。2022-3-2970l定義定義1.5.2 稱(chēng)稱(chēng)G為聯(lián)結(jié)詞功能完全組，如為聯(lián)結(jié)詞功能完全組，如果果G滿足下列兩條件：由滿足下列兩條件：由G中聯(lián)結(jié)詞構(gòu)中聯(lián)結(jié)詞構(gòu)成的公式能等價(jià)表示任意命題公式；成的公式能等價(jià)表示任意命題公式；G 中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價(jià)中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價(jià)表示。表示。l可以證明，可以證明， ， ， ， ， ， ， ， 都是聯(lián)結(jié)詞功能完全組；而都是聯(lián)結(jié)詞功能完全組；而 ， ， ， ， ， ，

49、 都不是聯(lián)都不是聯(lián)結(jié)詞功能完全組，但為了表示方便，仍經(jīng)結(jié)詞功能完全組，但為了表示方便，仍經(jīng)常使用聯(lián)結(jié)詞組常使用聯(lián)結(jié)詞組 ， ， 。2022-3-2971.簡(jiǎn)單合取式與簡(jiǎn)單析取式簡(jiǎn)單合取式與簡(jiǎn)單析取式l定義定義1.6.1 在一公式中，僅由命題變?cè)霸谝还街校瑑H由命題變?cè)捌浞穸?gòu)成的合取式，其否定構(gòu)成的合取式， 稱(chēng)該公式為簡(jiǎn)單合稱(chēng)該公式為簡(jiǎn)單合取式，其中每個(gè)命題變?cè)蚱浞穸ǎQ(chēng)為取式，其中每個(gè)命題變?cè)蚱浞穸?，稱(chēng)為合取項(xiàng)。合取項(xiàng)。l定義定義1.6.2 在一公式中，僅由命題變?cè)霸谝还街?，僅由命題變?cè)捌浞穸?gòu)成的析取式，其否定構(gòu)成的析取式， 稱(chēng)該公式為簡(jiǎn)單析稱(chēng)該公式為簡(jiǎn)單析取式，其中每個(gè)命題

50、變?cè)蚱浞穸?，稱(chēng)為取式，其中每個(gè)命題變?cè)蚱浞穸?，稱(chēng)為析取項(xiàng)。析取項(xiàng)。2022-3-2972l例如，公式例如，公式P， Q，P Q和和 P Q P等都等都是簡(jiǎn)單合取式，而是簡(jiǎn)單合取式，而P，Q和和 P為相應(yīng)的簡(jiǎn)為相應(yīng)的簡(jiǎn)單合取式的合取項(xiàng)；公式單合取式的合取項(xiàng)；公式P， Q，P Q， P Q P等都是簡(jiǎn)單析取式，而等都是簡(jiǎn)單析取式，而P，Q和和 P為相應(yīng)簡(jiǎn)單析取式的析取項(xiàng)。為相應(yīng)簡(jiǎn)單析取式的析取項(xiàng)。l注意，一個(gè)命題變?cè)蚱浞穸瓤梢允亲⒁?，一個(gè)命題變?cè)蚱浞穸瓤梢允呛?jiǎn)單合取式，也可是簡(jiǎn)單析取式，如例簡(jiǎn)單合取式，也可是簡(jiǎn)單析取式，如例中中P， Q等。等。2022-3-2973l定理定理1.6.1

51、 簡(jiǎn)單合取式為永假式的充要簡(jiǎn)單合取式為永假式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌錀l件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸?。否定。l定理定理1.6.2 簡(jiǎn)單析取式為永真式的充要簡(jiǎn)單析取式為永真式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌錀l件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸?。否定?022-3-2974 .析取范式與合取范式析取范式與合取范式l定義定義1.6.3 一個(gè)命題公式一個(gè)命題公式A稱(chēng)為析取范式，稱(chēng)為析取范式，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A可表為簡(jiǎn)單合取式的析取，即可表為簡(jiǎn)單合取式的析取，即AAi；其中；其中Ai為簡(jiǎn)單合取式，為簡(jiǎn)單合取式，i=1，2，n。l定義定義1.6.4 一個(gè)命題公式一個(gè)命題公式

52、A稱(chēng)為合取范式，稱(chēng)為合取范式，當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A可表為簡(jiǎn)單析取式的合取，即可表為簡(jiǎn)單析取式的合取，即AAi；其中；其中Ai為簡(jiǎn)單析取式，為簡(jiǎn)單析取式，1in。2022-3-2975l定理定理1.6.3 對(duì)于任何一命題公式，都存對(duì)于任何一命題公式，都存在與其等價(jià)的析取范式和合取范式。在與其等價(jià)的析取范式和合取范式。l求范式算法：求范式算法： 使用命題定律，消去公使用命題定律，消去公式中除式中除 、 和和 以外公式中出現(xiàn)的所有聯(lián)以外公式中出現(xiàn)的所有聯(lián)結(jié)詞；結(jié)詞；l 使用使用 ( P)P和德和德摩根律，將公式中摩根律，將公式中出現(xiàn)的聯(lián)結(jié)詞出現(xiàn)的聯(lián)結(jié)詞 都移到命題變?cè)?；都移到命題變?cè)?；l 利用

53、結(jié)合律、分配律等將公式化成析利用結(jié)合律、分配律等將公式化成析取范式或合取范式。取范式或合取范式。2022-3-2976 .范式的應(yīng)用范式的應(yīng)用l利用析取范式和合取范式可對(duì)公式進(jìn)行利用析取范式和合取范式可對(duì)公式進(jìn)行判定。判定。l定理定理1.6.4 公式公式A為永假式的充要條件是為永假式的充要條件是A 的析取范式中每個(gè)簡(jiǎn)單合取式至少包的析取范式中每個(gè)簡(jiǎn)單合取式至少包含一個(gè)命題變?cè)捌浞穸ā：粋€(gè)命題變?cè)捌浞穸?。l定理定理1.6.5 公式公式A為永真式的充要條件是為永真式的充要條件是A 的合取范式中每個(gè)簡(jiǎn)單析取式至少包的合取范式中每個(gè)簡(jiǎn)單析取式至少包含一個(gè)命題變?cè)捌浞穸ā：粋€(gè)命題變?cè)捌浞穸ā?/p>

54、2022-3-2977 .范式不唯一性范式不唯一性2022-3-2978l范式基本解決了公式的判定問(wèn)題。但由范式基本解決了公式的判定問(wèn)題。但由于范式不唯一性，對(duì)識(shí)別公式間是否等于范式不唯一性，對(duì)識(shí)別公式間是否等價(jià)帶來(lái)一定困難，而公式的主范式解決價(jià)帶來(lái)一定困難，而公式的主范式解決了這個(gè)問(wèn)題。下面將分別討論主范式中了這個(gè)問(wèn)題。下面將分別討論主范式中的主析取范式和主合取范式。的主析取范式和主合取范式。2022-3-2979 .主析取范式主析取范式 (1) 小項(xiàng)的概念和性質(zhì)小項(xiàng)的概念和性質(zhì)l定義定義1.7.1 在含有在含有n個(gè)命題變?cè)暮?jiǎn)單合個(gè)命題變?cè)暮?jiǎn)單合取式中，取式中， 若每個(gè)命題變?cè)c其否定不

55、同若每個(gè)命題變?cè)c其否定不同時(shí)存在，而二者之一出現(xiàn)一次且僅出現(xiàn)時(shí)存在，而二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱(chēng)該簡(jiǎn)單合取式為小項(xiàng)，或布一次，則稱(chēng)該簡(jiǎn)單合取式為小項(xiàng)，或布爾積。爾積。2022-3-2980l例如，兩個(gè)命題變?cè)纾瑑蓚€(gè)命題變?cè)狿和和Q，其構(gòu)成的小，其構(gòu)成的小項(xiàng)有項(xiàng)有P Q，PQ， P Q和和 PQ；而三；而三個(gè)命題變?cè)獋€(gè)命題變?cè)狿、Q和和R，其構(gòu)成的小項(xiàng)有，其構(gòu)成的小項(xiàng)有P Q R，P QR，PQ R，PQR， P Q R ， P QR， PQ R， PQR。l可以證明，可以證明，n個(gè)命題變?cè)残纬蓚€(gè)命題變?cè)残纬?n個(gè)小項(xiàng)。個(gè)小項(xiàng)。2022-3-2981l如果將命題變?cè)醋值湫蚺帕?/p>

56、，并且把如果將命題變?cè)醋值湫蚺帕?，并且把命題變?cè)c命題變?cè)c1對(duì)應(yīng)，命題變?cè)姆穸ㄅc對(duì)應(yīng)，命題變?cè)姆穸ㄅc0對(duì)應(yīng)，則可對(duì)對(duì)應(yīng)，則可對(duì)2n個(gè)小項(xiàng)依二進(jìn)制數(shù)編碼，個(gè)小項(xiàng)依二進(jìn)制數(shù)編碼，記為記為mi，其下標(biāo)，其下標(biāo)i是由二進(jìn)制數(shù)轉(zhuǎn)化的十是由二進(jìn)制數(shù)轉(zhuǎn)化的十進(jìn)制數(shù)。用這種編碼所求得進(jìn)制數(shù)。用這種編碼所求得2n個(gè)小項(xiàng)的個(gè)小項(xiàng)的真值表，可明顯地反映出小項(xiàng)的性質(zhì)。真值表，可明顯地反映出小項(xiàng)的性質(zhì)。l表表1.7.1和表和表1.7.2分別給出了分別給出了2個(gè)命題變個(gè)命題變?cè)狿和和Q、3個(gè)命題變?cè)獋€(gè)命題變?cè)狿、Q和和R的小項(xiàng)的小項(xiàng)真值表。真值表。2022-3-2982 表表 1.7.1 兩兩個(gè)個(gè)命命題題變變?cè)?/p>

57、元的的小小項(xiàng)項(xiàng)真真值值表表m(二二) m00 m01 m10 m11P Q P Q P Q P Q P Q0 0 1 0 0 00 1 0 1 0 01 0 0 0 1 01 1 0 0 0 1m(+) m0 m1 m2 m32022-3-2983 表表 1.7.2 3 個(gè)命題變?cè)男№?xiàng)真值表個(gè)命題變?cè)男№?xiàng)真值表m(二二)m000m001m010m011P Q R P Q R P Q R P Q R P Q R0 0 010000 0 101000 1 000100 1 100011 0 000001 0 100001 1 000001 1 10000m(+)m0m1m2m32022-3-2

58、984 續(xù)表續(xù)表m(二二)m100m101m110m111P Q RP Q RP Q RP Q RP Q R0 0 000000 0 100000 1 000000 1 100001 0 010001 0 101001 1 000101 1 10001m(+)m4m5m6m72022-3-2985l從表從表1.7.1，表，表1.7.2可看出，小項(xiàng)有如下可看出，小項(xiàng)有如下性質(zhì)：性質(zhì)：l(a)沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，即是說(shuō)各沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，即是說(shuō)各小項(xiàng)的真值表都是不同的；小項(xiàng)的真值表都是不同的；l(b)任意兩個(gè)不同的小項(xiàng)的合取式是永假任意兩個(gè)不同的小項(xiàng)的合取式是永假的：的：mimj，ij。l(

59、c)所有小項(xiàng)之析取為永真：所有小項(xiàng)之析取為永真： mi。l(d)每個(gè)小項(xiàng)只有一個(gè)解釋為真，且其真每個(gè)小項(xiàng)只有一個(gè)解釋為真，且其真值值1位于主對(duì)角線上。位于主對(duì)角線上。ni 12022-3-2986 (2) 主析取范式定義與存在定理主析取范式定義與存在定理l定義定義1.7.2 在給定公式的析取范式中，在給定公式的析取范式中，若其簡(jiǎn)單合取式都是小項(xiàng)，若其簡(jiǎn)單合取式都是小項(xiàng)， 則稱(chēng)該范式則稱(chēng)該范式為主析取范式。為主析取范式。l定理定理1.7.1 任意含任意含n個(gè)命題變?cè)姆怯兰賯€(gè)命題變?cè)姆怯兰倜}公式命題公式A 都存在與其等價(jià)的主析取范都存在與其等價(jià)的主析取范式。式。2022-3-2987 (3)

60、 主析取范式的求法主析取范式的求法l主析取范式求法有兩種：真值表法和公主析取范式求法有兩種：真值表法和公式化歸法。定理式化歸法。定理1.7.1的證明已給出了用的證明已給出了用真值表求主析取范式的方法，而公式化真值表求主析取范式的方法，而公式化歸法給出如下：歸法給出如下：l(a)把給定公式化成析取范式；把給定公式化成析取范式；l(b) 刪除析取范式中所有為永假的簡(jiǎn)單刪除析取范式中所有為永假的簡(jiǎn)單合取式；合取式；2022-3-2988l(c) 用等冪律化簡(jiǎn)簡(jiǎn)單合取式中同一命用等冪律化簡(jiǎn)簡(jiǎn)單合取式中同一命題變?cè)闹貜?fù)出現(xiàn)為一次出現(xiàn)，如題變?cè)闹貜?fù)出現(xiàn)為一次出現(xiàn)，如PPP。l(d) 用同一律補(bǔ)進(jìn)簡(jiǎn)單合