第一章命題邏輯

1、2022-3-291l命題邏輯，也稱命題演算，記為命題邏輯，也稱命題演算，記為LsLs。它與。它與謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏謂詞邏輯構(gòu)成數(shù)理邏輯的基礎(chǔ)，而命題邏輯又是謂詞邏輯的基礎(chǔ)。數(shù)理邏輯是用數(shù)輯又是謂詞邏輯的基礎(chǔ)。數(shù)理邏輯是用數(shù)學(xué)方法即通過引入表意符號研究推理的學(xué)學(xué)方法即通過引入表意符號研究推理的學(xué)問。因此，數(shù)理邏輯又名為符號邏輯。問。因此，數(shù)理邏輯又名為符號邏輯。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 命題變元和合式公式命題變

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

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

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

5、全體起立!8.明天是否開大會明天是否開大會?9.天氣多好啊天氣多好啊!10.我正在說謊我正在說謊.2022-3-296 . 命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞l定義定義1.1.1設(shè)設(shè)P表示一個命題，由命題表示一個命題，由命題聯(lián)結(jié)詞聯(lián)結(jié)詞l l和命題和命題P連接成連接成l lP，稱，稱l lP為為P的的否定式復(fù)合命題，否定式復(fù)合命題， l lP讀讀“非非P”。稱。稱l l為為否定聯(lián)結(jié)詞。否定聯(lián)結(jié)詞。l lP是真，當且僅當是真，當且僅當P為假；為假；l lP是假，當且僅當是假，當且僅當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由于否定由于否定 修改了命題，它是對單個命題進行操作，修改了命題，它是對單個命題進行操作，稱它為一元聯(lián)結(jié)詞。稱它為一元聯(lián)結(jié)詞。例例 P : 上海是一個大城市上海是一個大城市. P: 上海并不是一個大城市上海并不是一個大城市.或或 P: 上海是一個不大城市上海是一個不大城市.2022-3-298l定義定義1.1.2 設(shè)設(shè)P和和Q為兩個命題，由為兩個命題，由命題聯(lián)結(jié)詞命題聯(lián)結(jié)詞將將P和和Q連接成連接成PQ，稱，稱PQ為命題為命題P和和Q的合取式復(fù)合命題，的合取式復(fù)合命題，PQ讀做讀做“P與與Q”，或，或“P且且Q”。稱。稱為合取聯(lián)結(jié)詞。為合取聯(lián)結(jié)詞。l當且僅當當且

7、僅當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為兩個命題，由命為兩個命題，由命題聯(lián)結(jié)詞題聯(lián)結(jié)詞把把P和和Q連接成連接成PQ，稱，稱PQ為命題為命題P和和Q的析取式復(fù)合命題，的析取式復(fù)合命題，PQ讀做讀做“P或或Q”。稱。稱為析取聯(lián)結(jié)詞。為析取聯(lián)結(jié)詞。l當且僅當當且僅當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é)詞時，也不與合取聯(lián)結(jié)詞一樣，使用析取聯(lián)結(jié)詞時，也不要求兩命題間一定有任何關(guān)系要求兩命題間一定有任何關(guān)系.例例1 P:他是他是100米賽跑冠軍米賽跑冠軍. Q:他是他是400米賽跑冠軍米賽跑冠軍.上述命題的析取為上述命題的析取為 P Q:他是他是100米或米或400米賽跑冠軍米賽跑冠軍.2022-3-2914l定義定義1.1.4 設(shè)設(shè)P和和Q為兩個命題，由命題為兩

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

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

12、2-3-2918l定義定義1.1.5 令令P、Q是兩個命題，由命題聯(lián)是兩個命題，由命題聯(lián)結(jié)詞結(jié)詞把把P和和Q連接成連接成P Q，稱，稱P Q為命題為命題P和和Q的雙條件式復(fù)合命題，簡稱的雙條件式復(fù)合命題，簡稱雙條件命題，雙條件命題，P Q讀做讀做“P當且僅當當且僅當Q”，或或“P等價等價Q”。稱。稱為雙條件聯(lián)結(jié)為雙條件聯(lián)結(jié)l當當P和和Q的真值相同時，的真值相同時，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:春天來了春天來了. P Q:燕子飛回南方燕子飛回南方,當且僅當春天來了當且僅當春天來了.例例2 P:2+2=4. Q:雪是黑的雪是黑的. P Q:2+2=4,當且僅當雪是黑的當且僅當雪是黑的.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é)束時，應(yīng)強調(diào)指出的是：復(fù)合在本節(jié)結(jié)束時，應(yīng)強調(diào)指出的是：復(fù)合命題的真

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

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

16、為命題常元；一個不確定的泛指的任意命題，命題常元；一個不確定的泛指的任意命題，稱為命題變元。顯然，命題變元不是命題，稱為命題變元。顯然，命題變元不是命題，只有用一個特定的命題取代才能確定它的只有用一個特定的命題取代才能確定它的真值：真或假。這時也說對該命題變元指真值：真或假。這時也說對該命題變元指派真值。派真值。2022-3-2926l命題常元和命題變元均可用字母命題常元和命題變元均可用字母P等表示。等表示。由于在命題邏輯中并不關(guān)心具體命題的由于在命題邏輯中并不關(guān)心具體命題的涵義，只關(guān)心其真值，因此，可以形式涵義，只關(guān)心其真值，因此，可以形式地定義它們?nèi)缦拢旱囟x它們?nèi)缦拢?l定義定義1.2.

17、1以真或以真或1、假或、假或0為其變域為其變域的變元，稱為命題變元；真或的變元，稱為命題變元；真或1、假或、假或0稱為命題常元。稱為命題常元。2022-3-2927l2. 合式公式合式公式l通常把含有命題變元的斷言稱為命題公通常把含有命題變元的斷言稱為命題公式。但這沒能指出命題公式的結(jié)構(gòu)，因式。但這沒能指出命題公式的結(jié)構(gòu)，因為不是所有由命題變元、聯(lián)結(jié)詞和括號為不是所有由命題變元、聯(lián)結(jié)詞和括號所組成的字符串都能成為命題公式。為所組成的字符串都能成為命題公式。為此常使用歸納定義命題公式，以便構(gòu)成此常使用歸納定義命題公式，以便構(gòu)成的公式有規(guī)則可循。由這種定義產(chǎn)生的的公式有規(guī)則可循。由這種定義產(chǎn)生的公

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

19、。2022-3-2929l當合式公式比較復(fù)雜時，常常使用很多當合式公式比較復(fù)雜時，常常使用很多圓括號，為了減少圓括號的使用量，可圓括號，為了減少圓括號的使用量，可作以下約定：作以下約定：l規(guī)定聯(lián)結(jié)詞的優(yōu)先級由高到低的次序規(guī)定聯(lián)結(jié)詞的優(yōu)先級由高到低的次序為：為：l l、 l相同的聯(lián)結(jié)詞按從左至右次序計算時，相同的聯(lián)結(jié)詞按從左至右次序計算時，圓括號可省略。圓括號可省略。l最外層的圓括號可以省略。最外層的圓括號可以省略。l為了方便計，合式公式也簡稱公式。為了方便計，合式公式也簡稱公式。2022-3-2930 .公式真值表公式真值表l定義定義1.2.4對于公式中命題變元的每對于公式中命題變元的每一種可

20、能的真值指派，以及由它們確定一種可能的真值指派，以及由它們確定出的公式真值所列成的表，稱為該公式出的公式真值所列成的表，稱為該公式的真值表。的真值表。l定義定義1.2.5如果如果B是公式是公式A中的一部分，中的一部分，且且B為公式，則稱為公式，則稱B是公式是公式A的子公式。的子公式。2022-3-2931l用歸納法不難證明，對于含有用歸納法不難證明，對于含有n個命題變個命題變元的公式，有元的公式，有2n個真值指派，即在該公個真值指派，即在該公式的真值表中有式的真值表中有2n行。行。l為方便構(gòu)造真值表，為方便構(gòu)造真值表，l特約定如下：特約定如下：l 命題變元按字典序排列。命題變元按字典序排列。l

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

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

23、均相應(yīng)確定均相應(yīng)確定真值為真，稱真值為真，稱 A 為重言式，或永真式。為重言式，或永真式。l 對應(yīng)每一個指派，公式對應(yīng)每一個指派，公式 A 均相應(yīng)確定均相應(yīng)確定真值為假，稱真值為假，稱 A 為矛盾式，或永假式。為矛盾式，或永假式。l 至少存在一個指派，公式至少存在一個指派，公式 A 相應(yīng)確定相應(yīng)確定真值為真，稱真值為真，稱 A 為可滿足式。為可滿足式。2022-3-2935l由定義可知，重言式必是可滿足式，反由定義可知，重言式必是可滿足式，反之一般不真。之一般不真。l重點將研究重言式，它最有用，因為它重點將研究重言式，它最有用，因為它有以下特點：有以下特點：l重言式的否定是矛盾式，矛盾式的否重

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

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

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

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

28、為基本等價式或稱命題定律。牢固地記住它并能熟練或稱命題定律。牢固地記住它并能熟練運用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一，讀運用，是學(xué)好數(shù)理邏輯的關(guān)鍵之一，讀者應(yīng)該注意到這一點。現(xiàn)將這些命題定者應(yīng)該注意到這一點?，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) 互補律：互補律：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上面這些定律，即是通常所說的布爾代上面這些定律，即是通常所說的布爾代數(shù)或邏輯代數(shù)的重要組成部分，它們的數(shù)或邏輯代數(shù)的重要組成部分，它們的正確性利用真值表是不難給出證明的。正確性利用真值表是不難給出證明的。2022-3-2944. .代入規(guī)則和替換規(guī)則代入規(guī)則和替換規(guī)則l在定義合成公式時，已看到了邏輯聯(lián)結(jié)在定義合成公式時，已看到了邏輯聯(lián)結(jié)詞能夠從已知公式形成新的公式，從這詞能夠從已知公式形成新的公式，從這個意義上可把邏輯聯(lián)結(jié)詞看成運算。除個意義上可把邏輯聯(lián)結(jié)詞看成運算。除邏輯聯(lián)結(jié)詞外，還要介

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

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

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

35、*的對偶式。可見的對偶式。可見A與與A*互互為對偶式。為對偶式。2022-3-2949l定理定理1.4.1(對偶定理對偶定理) 設(shè)設(shè)A和和A*互為對偶互為對偶式，式，P1，P2，Pn是出現(xiàn)是出現(xiàn)A和和A* 中的中的原子命題變元，則原子命題變元，則l A(P1，P2，Pn)A*( P1， P2， Pn)l A( P1， P2， Pn)A*(P1，P2，Pn)l表明，公式表明，公式A的否定等價于其命題變元的否定等價于其命題變元否定的對偶式；表明，命題變元否定否定的對偶式；表明，命題變元否定的公式等價于對偶式之否定。的公式等價于對偶式之否定。2022-3-2950l定理定理1.4.2 設(shè)設(shè)A和和B為

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

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

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

39、涵式成立。立。l因為欲證因為欲證AB，即證，即證AB是永真式。是永真式。對于對于AB，除在，除在A取真和取真和B取假時，取假時，AB為假外，余下為假外，余下AB皆為真。所以，皆為真。所以，若若AB的前件的前件A為真，由此可推出為真，由此可推出B亦亦為真，則為真，則AB是永真式，即是永真式，即AB。2022-3-2955 后件假導(dǎo)前件假方法后件假導(dǎo)前件假方法l設(shè)條件式后件為假，若能推導(dǎo)出前件也設(shè)條件式后件為假，若能推導(dǎo)出前件也為假，則條件式是永真式，即蘊涵式成為假，則條件式是永真式，即蘊涵式成立。立。l因為若因為若AB的后件的后件B取假，由此可推出取假，由此可推出A取假，即推證了：取假，即推證了

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

41、Q的析取非式復(fù)合命題，讀作的析取非式復(fù)合命題，讀作“P析取非析取非Q”。PQ的真值由的真值由P和和Q的真的真值確定：當且僅當值確定：當且僅當P和和Q均為均為時，時，PQ為為，否則，否則PQ為為?！拔鋈》俏鋈》恰庇殖Ｓ殖７Q為稱為“或非或非”。l由條件非聯(lián)結(jié)詞由條件非聯(lián)結(jié)詞 和和P，Q連接成連接成P Q，稱它為稱它為P和和Q的條件非式復(fù)合命題，讀作的條件非式復(fù)合命題，讀作“P條件非條件非Q”。P Q的真值由的真值由P和和Q的真的真值確定：當且僅當值確定：當且僅當P為為而而Q為為時，時，P Q為為；否則；否則P Q為為。2022-3-2958l由雙條件非聯(lián)結(jié)詞由雙條件非聯(lián)結(jié)詞 把把P，Q連接成連接成

42、P Q，稱它為，稱它為P和和Q的雙條件非式復(fù)合命的雙條件非式復(fù)合命題，讀作題，讀作“P雙條件非雙條件非Q”。P Q的真值的真值由由P和和 Q的真值確定：當且僅當?shù)恼嬷荡_定：當且僅當P和和Q的的真值不同時，真值不同時，P Q為為，否則，否則P Q為為?！半p條件非雙條件非”又常稱為又常稱為“異或異或”，也常，也常用符號用符號 表示之。表示之。l上面上面4個聯(lián)結(jié)詞構(gòu)成的復(fù)合命題，其真值個聯(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與非、或非以及異或在計算機科學(xué)中是與非、或非以及異或在計算機科學(xué)中是經(jīng)常使用的經(jīng)常使用的3個聯(lián)結(jié)詞，因此，掌握它們個聯(lián)結(jié)詞，因此，掌握它們的性質(zhì)是十分必要的。令的性質(zhì)是十分必要的。令P、Q和和R是原是原子命題變元。子命題變元。 與非的性質(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é)詞 或者或者 取代，讀者可以自行取代，讀者可以自行驗證，驗證， 和和 都不滿足結(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個聯(lián)結(jié)詞，是否還需要擴個

45、聯(lián)結(jié)詞，是否還需要擴充呢？事實上，兩上命題變無充呢？事實上，兩上命題變無P和和Q，與，與9個聯(lián)結(jié)詞一共可構(gòu)成個聯(lián)結(jié)詞一共可構(gòu)成 類命題公式，類命題公式，如下表示之：如下表示之：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é)詞序號序號1 234 56789102022-3-2966PQP Q P Q P Q P Q P Q P Q00101010011001011001011011101010所用聯(lián)結(jié)所用聯(lián)結(jié)詞詞序號序號111

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

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

48、最少的幾個聯(lián)結(jié)詞就能替式?；蛘哒f，用最少的幾個聯(lián)結(jié)詞就能替代所有聯(lián)結(jié)詞的功能。這便是所要定義的代所有聯(lián)結(jié)詞的功能。這便是所要定義的聯(lián)結(jié)詞功能完全組。聯(lián)結(jié)詞功能完全組。2022-3-2970l定義定義1.5.2 稱稱G為聯(lián)結(jié)詞功能完全組，如為聯(lián)結(jié)詞功能完全組，如果果G滿足下列兩條件：由滿足下列兩條件：由G中聯(lián)結(jié)詞構(gòu)中聯(lián)結(jié)詞構(gòu)成的公式能等價表示任意命題公式；成的公式能等價表示任意命題公式；G 中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(jié)詞等價中的任一聯(lián)結(jié)詞不能用其余下聯(lián)結(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.簡單合取式與簡單析取式簡單合取式與簡單析取式l定義定義1.6.1 在一公式中，僅由命題變元及在一公式中，僅由命題變元及其否定構(gòu)成的合取式，其否定構(gòu)成的合取式， 稱該公式為簡單合稱該公式為簡單合取式，其中每個命題變元或其否定，稱為取式，其中每個命題變元或其否定，稱為合取項。合取項。l定義定義1.6.2 在一公式中，僅由命題變元及在一公式中，僅由命題變元及其否定構(gòu)成的析取式，其否定構(gòu)成的析取式， 稱該公式為簡單析稱該公式為簡單析取式，其中每個命題

50、變元或其否定，稱為取式，其中每個命題變元或其否定，稱為析取項。析取項。2022-3-2972l例如，公式例如，公式P， Q，P Q和和 P Q P等都等都是簡單合取式，而是簡單合取式，而P，Q和和 P為相應(yīng)的簡為相應(yīng)的簡單合取式的合取項；公式單合取式的合取項；公式P， Q，P Q， P Q P等都是簡單析取式，而等都是簡單析取式，而P，Q和和 P為相應(yīng)簡單析取式的析取項。為相應(yīng)簡單析取式的析取項。l注意，一個命題變元或其否定既可以是注意，一個命題變元或其否定既可以是簡單合取式，也可是簡單析取式，如例簡單合取式，也可是簡單析取式，如例中中P， Q等。等。2022-3-2973l定理定理1.6.1

51、 簡單合取式為永假式的充要簡單合取式為永假式的充要條件是：它同時含有某個命題變元及其條件是：它同時含有某個命題變元及其否定。否定。l定理定理1.6.2 簡單析取式為永真式的充要簡單析取式為永真式的充要條件是：它同時含有某個命題變元及其條件是：它同時含有某個命題變元及其否定。否定。2022-3-2974 .析取范式與合取范式析取范式與合取范式l定義定義1.6.3 一個命題公式一個命題公式A稱為析取范式，稱為析取范式，當且僅當當且僅當A可表為簡單合取式的析取，即可表為簡單合取式的析取，即AAi；其中；其中Ai為簡單合取式，為簡單合取式，i=1，2，n。l定義定義1.6.4 一個命題公式一個命題公式

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

53、結(jié)合律、分配律等將公式化成析利用結(jié)合律、分配律等將公式化成析取范式或合取范式。取范式或合取范式。2022-3-2976 .范式的應(yīng)用范式的應(yīng)用l利用析取范式和合取范式可對公式進行利用析取范式和合取范式可對公式進行判定。判定。l定理定理1.6.4 公式公式A為永假式的充要條件是為永假式的充要條件是A 的析取范式中每個簡單合取式至少包的析取范式中每個簡單合取式至少包含一個命題變元及其否定。含一個命題變元及其否定。l定理定理1.6.5 公式公式A為永真式的充要條件是為永真式的充要條件是A 的合取范式中每個簡單析取式至少包的合取范式中每個簡單析取式至少包含一個命題變元及其否定。含一個命題變元及其否定。

54、2022-3-2977 .范式不唯一性范式不唯一性2022-3-2978l范式基本解決了公式的判定問題。但由范式基本解決了公式的判定問題。但由于范式不唯一性，對識別公式間是否等于范式不唯一性，對識別公式間是否等價帶來一定困難，而公式的主范式解決價帶來一定困難，而公式的主范式解決了這個問題。下面將分別討論主范式中了這個問題。下面將分別討論主范式中的主析取范式和主合取范式。的主析取范式和主合取范式。2022-3-2979 .主析取范式主析取范式 (1) 小項的概念和性質(zhì)小項的概念和性質(zhì)l定義定義1.7.1 在含有在含有n個命題變元的簡單合個命題變元的簡單合取式中，取式中， 若每個命題變元與其否定不

55、同若每個命題變元與其否定不同時存在，而二者之一出現(xiàn)一次且僅出現(xiàn)時存在，而二者之一出現(xiàn)一次且僅出現(xiàn)一次，則稱該簡單合取式為小項，或布一次，則稱該簡單合取式為小項，或布爾積。爾積。2022-3-2980l例如，兩個命題變元例如，兩個命題變元P和和Q，其構(gòu)成的小，其構(gòu)成的小項有項有P Q，PQ， P Q和和 PQ；而三；而三個命題變元個命題變元P、Q和和R，其構(gòu)成的小項有，其構(gòu)成的小項有P Q R，P QR，PQ R，PQR， P Q R ， P QR， PQ R， PQR。l可以證明，可以證明，n個命題變元共形成個命題變元共形成2n個小項。個小項。2022-3-2981l如果將命題變元按字典序排列

56、，并且把如果將命題變元按字典序排列，并且把命題變元與命題變元與1對應(yīng)，命題變元的否定與對應(yīng)，命題變元的否定與0對應(yīng)，則可對對應(yīng)，則可對2n個小項依二進制數(shù)編碼，個小項依二進制數(shù)編碼，記為記為mi，其下標，其下標i是由二進制數(shù)轉(zhuǎn)化的十是由二進制數(shù)轉(zhuǎn)化的十進制數(shù)。用這種編碼所求得進制數(shù)。用這種編碼所求得2n個小項的個小項的真值表，可明顯地反映出小項的性質(zhì)。真值表，可明顯地反映出小項的性質(zhì)。l表表1.7.1和表和表1.7.2分別給出了分別給出了2個命題變個命題變元元P和和Q、3個命題變元個命題變元P、Q和和R的小項的小項真值表。真值表。2022-3-2982 表表 1.7.1 兩兩個個命命題題變變元

57、元的的小小項項真真值值表表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 個命題變元的小項真值表個命題變元的小項真值表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可看出，小項有如下可看出，小項有如下性質(zhì)：性質(zhì)：l(a)沒有兩個小項是等價的，即是說各沒有兩個小項是等價的，即是說各小項的真值表都是不同的；小項的真值表都是不同的；l(b)任意兩個不同的小項的合取式是永假任意兩個不同的小項的合取式是永假的：的：mimj，ij。l(

59、c)所有小項之析取為永真：所有小項之析取為永真： mi。l(d)每個小項只有一個解釋為真，且其真每個小項只有一個解釋為真，且其真值值1位于主對角線上。位于主對角線上。ni 12022-3-2986 (2) 主析取范式定義與存在定理主析取范式定義與存在定理l定義定義1.7.2 在給定公式的析取范式中，在給定公式的析取范式中，若其簡單合取式都是小項，若其簡單合取式都是小項， 則稱該范式則稱該范式為主析取范式。為主析取范式。l定理定理1.7.1 任意含任意含n個命題變元的非永假個命題變元的非永假命題公式命題公式A 都存在與其等價的主析取范都存在與其等價的主析取范式。式。2022-3-2987 (3)

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