第一章 命題邏輯的基本概念

1、離散數(shù)學(xué)及其應(yīng)用離散數(shù)學(xué)及其應(yīng)用引言離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專業(yè)的一門重要基礎(chǔ)課。離散數(shù)學(xué)是計(jì)算機(jī)及相關(guān)專業(yè)的一門重要基礎(chǔ)課。學(xué)習(xí)方法n 精確嚴(yán)格地掌握好概念和術(shù)語(yǔ)，正確理解它們的內(nèi)涵和外延；n 獨(dú)立完成作業(yè)，自覺(jué)歸納基本解題方法；n 閱讀和復(fù)習(xí)時(shí)，隨時(shí)備好紙筆，以便進(jìn)行詳細(xì)的推導(dǎo)和計(jì)算；n 學(xué)習(xí)和理解術(shù)語(yǔ)，給術(shù)語(yǔ)賦予特殊的含義，加深理解。n 多做習(xí)題，加深理解。內(nèi)容框架內(nèi)容框架第一部分：數(shù)理邏輯第一部分：數(shù)理邏輯第二部分：集合論第二部分：集合論第三部分：圖論第三部分：圖論第四部分：組合數(shù)學(xué)第四部分：組合數(shù)學(xué)第五部分：代數(shù)系統(tǒng)簡(jiǎn)介第五部分：代數(shù)系統(tǒng)簡(jiǎn)介 你好，我是大白，你的私人健康顧問(wèn)。你好，我

2、是大白，你的私人健康顧問(wèn)。 超能陸戰(zhàn)隊(duì)超能陸戰(zhàn)隊(duì)第一部分第一部分 數(shù)理邏輯數(shù)理邏輯第一章第一章 命題邏輯的基本概念命題邏輯的基本概念第二章第二章 命題邏輯等值演算命題邏輯等值演算第三章第三章 命題邏輯的推理理論命題邏輯的推理理論第四章第四章 一階邏輯（謂詞邏輯）的基本概念一階邏輯（謂詞邏輯）的基本概念第五章第五章 一階邏輯（謂詞邏輯）等值演算一階邏輯（謂詞邏輯）等值演算什么是數(shù)理邏輯？數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科。所謂數(shù)學(xué)方法是指:用一套數(shù)學(xué)的符號(hào)系統(tǒng)來(lái)描述和處理思維的形式與規(guī)律。因此，數(shù)理邏輯又稱為符號(hào)邏輯。什么是數(shù)理邏輯？數(shù)理邏輯的創(chuàng)始人-萊布尼茨n 萊布尼茨(Leibniz

3、, Gottfried Wilhelm) 1646.7.1-1716.11.14n 德國(guó)數(shù)學(xué)家、物理學(xué)家、哲學(xué)家等，一個(gè)舉世罕見(jiàn)的科學(xué)天才。研究領(lǐng)域涉及到邏輯學(xué)、數(shù)學(xué)、力學(xué)、地質(zhì)學(xué)、法學(xué)、歷史學(xué)、語(yǔ)言學(xué)、生物學(xué)以及外交、神學(xué)等諸多方面.n 出生于德國(guó)東部萊比錫的一個(gè)書香之家，父親是萊比錫大學(xué)的道德哲學(xué)教授，母親出生在一個(gè)教授家庭。萊布尼茲的父親在他年僅6歲時(shí)便去世了，給他留下了豐富的藏書。什么是數(shù)理邏輯？數(shù)理邏輯的創(chuàng)始人-萊布尼茨n 15歲時(shí)，進(jìn)了萊比錫大學(xué)學(xué)習(xí)法律，一進(jìn)校便跟上了大學(xué)二年級(jí)標(biāo)準(zhǔn)的人文學(xué)科的課程，還廣泛閱讀了培根、開(kāi)普勒、伽利略等人的著作，并對(duì)他們的著述進(jìn)行深入的思考和評(píng)價(jià)。在

4、聽(tīng)了教授講授歐幾里德的幾何原本的課程后，萊布尼茲對(duì)數(shù)學(xué)產(chǎn)生了濃厚的興趣。17歲時(shí)他在耶拿大學(xué)學(xué)習(xí)了短時(shí)期的數(shù)學(xué)，并獲得了哲學(xué)碩士學(xué)位 。n 19歲設(shè)計(jì)出世界第一臺(tái)乘法器，被認(rèn)為是現(xiàn)代機(jī)器數(shù)學(xué)的先驅(qū)者。n Leibniz(16461716年) 之夢(mèng)：有一天所有的知識(shí)，包括精神和無(wú)形的真理，能夠通過(guò)通用的代數(shù)演算放入一個(gè)單一的演繹系統(tǒng)。n 1693年，發(fā)現(xiàn)了機(jī)械能的能量守恒定律。n 與牛頓并稱為微積分的創(chuàng)立者。n 系統(tǒng)闡述了二進(jìn)制記數(shù)法，并把它和中國(guó)的八卦聯(lián)系起來(lái)。第一章第一章 命題邏輯的基本概念命題邏輯的基本概念11第一章第一章 命題邏輯基本概念命題邏輯基本概念主要內(nèi)容主要內(nèi)容l 1.1 命題與

5、聯(lián)結(jié)詞命題與聯(lián)結(jié)詞 命題及其分類命題及其分類 聯(lián)結(jié)詞與復(fù)合命題聯(lián)結(jié)詞與復(fù)合命題l 1.2 命題公式及其賦值命題公式及其賦值1.1 命題和聯(lián)結(jié)詞現(xiàn)實(shí)語(yǔ)言判定推理翻譯應(yīng)用：p計(jì)算機(jī)電路設(shè)計(jì) p計(jì)算機(jī)程序構(gòu)造 p程序正確性證明1.1 命題和聯(lián)結(jié)詞命題的定義：非真即假的陳述句。n 作為命題的陳述句所表達(dá)的判斷結(jié)果稱作命題的真值，真值只能取兩個(gè)值：真或假。真值為真的命題稱為真命題，真值為假的命題稱為假命題。注意：任何命題的真值都是唯一的。n 如果一個(gè)命題的真值是真，則用1或T(Ture)來(lái)表示；如果一個(gè)命題的真值是假，則用0或F（False）來(lái)表示。n 本書用命題用英文字母，如p，q，r來(lái)表示。命題的概

6、念n 判斷給定句子是否為命題分為兩步：首先判斷該句子是否為陳述句，其次判斷它是否有唯一的一個(gè)真值。15例例1 1 下列句子中那些是命題？下列句子中那些是命題？ (1) 是有理數(shù)是有理數(shù). (2) 2 + 5 = 7. (3) x + 5 3. (4) 你去教室嗎？你去教室嗎？ (5) 這個(gè)蘋果真大呀！這個(gè)蘋果真大呀！ (6) 請(qǐng)不要講話！請(qǐng)不要講話！ (7) 2050年元旦下大雪年元旦下大雪. （8 8）我正在說(shuō)假話。）我正在說(shuō)假話。2 假命題假命題命題概念命題概念 真命題真命題不是命題不是命題 不是命題不是命題 不是命題不是命題不是命題不是命題命題，但真值現(xiàn)在不知道命題，但真值現(xiàn)在不知道16

7、簡(jiǎn)單命題簡(jiǎn)單命題（也稱原子命題）（也稱原子命題）：不能被分解成更簡(jiǎn)單的命題不能被分解成更簡(jiǎn)單的命題復(fù)合命題：復(fù)合命題：由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。由簡(jiǎn)單命題通過(guò)聯(lián)結(jié)詞聯(lián)結(jié)而成的命題。簡(jiǎn)單命題符號(hào)化簡(jiǎn)單命題符號(hào)化l 用小寫英文字母用小寫英文字母 p, q, r, , pi, qi, ri (i 1)表示簡(jiǎn)單命題表示簡(jiǎn)單命題l 用用“1”表示真，用表示真，用“0”表示假表示假 例如，令例如，令 p： 是有理數(shù)，則是有理數(shù)，則 p 的真值為的真值為0， q：2 + 5 = 7，則，則 q 的真值為的真值為12命題分類命題分類聯(lián)結(jié)詞是邏輯聯(lián)結(jié)詞或者命題聯(lián)結(jié)詞的簡(jiǎn)稱，它是自然語(yǔ)言中連詞的邏輯抽象

8、。有了聯(lián)結(jié)詞，就可以通過(guò)它和原子命題構(gòu)成復(fù)合命題。常用的邏輯聯(lián)結(jié)詞主要包括以下幾種。n（1）聯(lián)結(jié)詞“非”，記為“ p ”，表示“否定”的意思。n（2）聯(lián)結(jié)詞“合取”，記為“”，表示“且”的意思。n（3）聯(lián)結(jié)詞“析取”，記為“”，表示“或”的意思。n（4）聯(lián)結(jié)詞“蘊(yùn)涵”，記為“”，表示“如果，則”的意思。n（5）聯(lián)結(jié)詞“等價(jià)”，記為“”，表示“當(dāng)且僅當(dāng)”的意思。聯(lián)結(jié)詞 定義定義1.1 設(shè)設(shè) p為命題，復(fù)合命題為命題，復(fù)合命題“非非p”(或或“p的否定的否定”)稱稱為為p的的否定式否定式，記作，記作 p，讀作“非p”符號(hào)符號(hào) 稱作稱作否定聯(lián)結(jié)否定聯(lián)結(jié)詞詞. 規(guī)定規(guī)定 p 為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p

9、為假為假. 聯(lián)結(jié)詞是自然語(yǔ)言中的“非”、“不”和“沒(méi)有”等的邏輯抽象 注意：邏輯聯(lián)結(jié)詞否定是個(gè)注意：邏輯聯(lián)結(jié)詞否定是個(gè)一元運(yùn)算符一元運(yùn)算符。 真值定義如下：真值定義如下：邏輯聯(lián)結(jié)詞否定“ ”pp0110n例: 給出下列命題的否定。（1）令p表示：大連是北方香港。 于是 p表示：大連不是北方香港。 （2）令q表示：所有的素?cái)?shù)都是奇數(shù)。 于是 q表示：并非所有的素?cái)?shù)都是奇數(shù)。 注意：翻譯成“所有的素?cái)?shù)都不是奇數(shù)”是錯(cuò)誤的。因?yàn)榉穸ㄊ菍?duì)整個(gè)命題進(jìn)行的。邏輯聯(lián)結(jié)詞否定“ ”定義定義1.21.2 設(shè)設(shè)p,qp,q為兩個(gè)命題，復(fù)合命題為兩個(gè)命題，復(fù)合命題“p p并且并且q”(q”(或或“p p與與 q”)

10、q”)稱為稱為p p與與q q的的合取式合取式，記作記作pqpq，稱作稱作合取聯(lián)結(jié)詞合取聯(lián)結(jié)詞. . pq讀作“p與q”或者“p合取q”。 邏輯聯(lián)結(jié)詞“”是個(gè)二元運(yùn)算符，是“并且”的邏輯抽象。邏輯聯(lián)結(jié)詞合取“”1.1 命題和聯(lián)結(jié)詞n它的真值是這樣定義的：當(dāng)且僅當(dāng)p和q的真值都為1時(shí)，pq的真值才為1，否則pq的真值為0。邏輯聯(lián)結(jié)詞“”的定義如下表所示：邏輯聯(lián)結(jié)詞合取“”pqp pq qFFFFTFTFFTTTpqp pq q00001010011122例例 將下列命題符號(hào)化將下列命題符號(hào)化. (1) 吳穎既用功又聰明吳穎既用功又聰明. p q (2) 吳穎不僅用功而且聰明吳穎不僅用功而且聰明.

11、 p q (3) 吳穎雖然聰明，但不用功吳穎雖然聰明，但不用功. p q (4) 張輝與王麗都是三好生張輝與王麗都是三好生. p q (5) 張輝與張輝與王麗是同學(xué)王麗是同學(xué). p解解: (1)(2)(3)令令p:吳穎用功吳穎用功, q:吳穎聰明吳穎聰明(4)設(shè)設(shè)p:張輝是三好生張輝是三好生, q:王麗是三好生王麗是三好生(5)p:張輝與張輝與王麗是同學(xué)王麗是同學(xué)(1)(3) 說(shuō)明描述合取式的靈活性與多樣性說(shuō)明描述合取式的靈活性與多樣性(4)(5) 要求分清要求分清 “與與” 所聯(lián)結(jié)的成分所聯(lián)結(jié)的成分合取聯(lián)結(jié)詞的實(shí)例合取聯(lián)結(jié)詞的實(shí)例1.1 命題和聯(lián)結(jié)詞n 例 令p表示：外面正在下雪。 令q表示

12、：3小于5。 于是pq表示 ：外面正在下雪并且3小于5。n 從自然語(yǔ)言看，上述命題是不合理的、沒(méi)有意義的，因?yàn)閜和q毫不相關(guān)。但是，在數(shù)理邏輯中是被允許的，也是正確的。p和q再合取pq仍可成為一個(gè)新的命題。只要p和q的真值給定，pq的真值即可確定。n 邏輯聯(lián)結(jié)詞“”具有對(duì)稱性，即pq和qp具有相同真值。邏輯聯(lián)結(jié)詞合取“” 定義定義1.3 設(shè)設(shè)p, q為兩個(gè)命題，復(fù)合命題為兩個(gè)命題，復(fù)合命題“p或或q”稱作稱作p與與q的的析析取式取式，記作，記作pq，稱作稱作析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞. 讀作讀作“p或或q”，或，或“p析取析取q”。 邏輯聯(lián)結(jié)詞析取也是個(gè)二元運(yùn)算符邏輯聯(lián)結(jié)詞析取也是個(gè)二元運(yùn)算符。 聯(lián)

13、結(jié)詞聯(lián)結(jié)詞是自然語(yǔ)言中是自然語(yǔ)言中“或或”、“或者或者”的邏輯抽象的邏輯抽象。邏輯聯(lián)結(jié)詞析取“”1.1 命題和聯(lián)結(jié)詞n 其真值是這樣的定義的：當(dāng)且僅當(dāng)p和q的真值均為0時(shí)，pq的真值為0，其余情況均為1。邏輯聯(lián)結(jié)詞“”的定義如下表所示：邏輯聯(lián)結(jié)詞析取“”pqpqFFFFTTTFTTTTpqpq000011101111 注意：注意： 在自然語(yǔ)言中，在自然語(yǔ)言中，“或或”是多義的。從析取的定義不難看出是多義的。從析取的定義不難看出，邏輯聯(lián)結(jié)詞，邏輯聯(lián)結(jié)詞“”“”和自然漢語(yǔ)中的和自然漢語(yǔ)中的“或或”的意義并不完的意義并不完全相同。因?yàn)闈h語(yǔ)中的全相同。因?yàn)闈h語(yǔ)中的“或或”可表示可表示“排斥或排斥或”，

14、亦可表，亦可表示示“可兼或可兼或( (又稱相容或又稱相容或) )”，而邏輯聯(lián)結(jié)詞，而邏輯聯(lián)結(jié)詞“析取析取”指的指的僅僅是僅僅是“相容或相容或”，并不表示其他意義的，并不表示其他意義的“或或”。27例例 將下列命題符號(hào)化將下列命題符號(hào)化(1) 2 或或 4 是素?cái)?shù)是素?cái)?shù).(2) 2 或或 3 是素?cái)?shù)是素?cái)?shù).(3) 4 或或 6 是素?cái)?shù)是素?cái)?shù).(4) 小元元只能拿一個(gè)蘋果或一個(gè)梨小元元只能拿一個(gè)蘋果或一個(gè)梨.(5) 王小紅生于王小紅生于 1975 年或年或 1976 年年.解：解：(1) 令令p:2是素?cái)?shù)是素?cái)?shù), q:4是素?cái)?shù)是素?cái)?shù), p q(2) 令令p:2是素?cái)?shù)是素?cái)?shù), q:3是素?cái)?shù)是素?cái)?shù),

15、p q(3) 令令p:4是素?cái)?shù)是素?cái)?shù), q:6是素?cái)?shù)是素?cái)?shù), p q析取聯(lián)結(jié)詞析取聯(lián)結(jié)詞28(4) 令令p:小元元拿一個(gè)蘋果小元元拿一個(gè)蘋果, q:小元元拿一個(gè)梨小元元拿一個(gè)梨 (pq) ( p q)(5) p:王小紅生于王小紅生于 1975 年年, q:王小紅生于王小紅生于1976 年年, (pq) ( p q) 或或 p q(1)(3) 為相容或?yàn)橄嗳莼?4)(5) 為排斥或?yàn)榕懦饣? 符號(hào)化時(shí)符號(hào)化時(shí)(5)可有兩種形式，而可有兩種形式，而(4)則不能則不能注：注：p與與q不能同時(shí)為真的條件下，不能同時(shí)為真的條件下， p與與q的排斥或也可以寫的排斥或也可以寫成成p與與q的相容或。的相容或。

16、析取聯(lián)結(jié)詞的實(shí)例析取聯(lián)結(jié)詞的實(shí)例29定義定義1.4 設(shè)設(shè)p, q為兩個(gè)命題，復(fù)合命題為兩個(gè)命題，復(fù)合命題“如果如果p, 則則q”稱作稱作p與與q的的蘊(yùn)涵式蘊(yùn)涵式，記作，記作pq，并稱，并稱p是蘊(yùn)涵式的是蘊(yùn)涵式的前件前件，q為蘊(yùn)涵式的為蘊(yùn)涵式的后后件件，稱作稱作蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞. pq讀作讀作“如果如果p則則q”或或“如果如果p那么那么q”。蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞蘊(yùn)涵“”1.1 命題和聯(lián)結(jié)詞邏輯聯(lián)結(jié)詞“”的定義如下表所示：邏輯聯(lián)結(jié)詞蘊(yùn)涵“”pqpqFFTFTTTFFTTTpqpq001011100111邏輯聯(lián)結(jié)詞“”的定義(1) pq 的邏輯關(guān)系：的邏輯關(guān)系：q為為 p 的必要條件的

17、必要條件, p是是q的充分條件的充分條件.(2) “如果如果 p, 則則 q” 有很多不同的表述方法：有很多不同的表述方法：p 若p，就qp 只要p，就qp p僅當(dāng)qp 只有q 才pp 除非q, 才p 或 除非q，否則非p， (3) 當(dāng)當(dāng) p 為假時(shí)，為假時(shí)，pq恒為真，稱為空證明恒為真，稱為空證明 (4) 常出現(xiàn)的錯(cuò)誤：分不清充分條件與必要條件常出現(xiàn)的錯(cuò)誤：分不清充分條件與必要條件32例例4 設(shè)設(shè) p：天冷，：天冷，q：小王穿羽絨服，將下列命題符號(hào)化：小王穿羽絨服，將下列命題符號(hào)化(1) 只要天冷，小王就穿羽絨服只要天冷，小王就穿羽絨服.(2) 因?yàn)樘炖?，所以小王穿羽絨服因?yàn)樘炖?，所以小王?/p>

18、羽絨服.(3) 若小王不穿羽絨服，則天不冷若小王不穿羽絨服，則天不冷.(4) 只有只有天冷，小王天冷，小王才才穿羽絨服穿羽絨服.(5) 除非除非天冷，小王天冷，小王才才穿羽絨服穿羽絨服.(6) 除非除非小王穿羽絨服，小王穿羽絨服，否則否則天天不不冷冷.(7) 如果天不冷，則小王不穿羽絨服如果天不冷，則小王不穿羽絨服.(8) 小王穿羽絨服小王穿羽絨服僅當(dāng)僅當(dāng)天冷的時(shí)候天冷的時(shí)候.蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例蘊(yùn)涵聯(lián)結(jié)詞的實(shí)例pq注意：注意： p q 與與 qp 等值（真值相同）等值（真值相同）pq q p, pqqpqppq pqqp定義定義1.5 設(shè)設(shè) p, q為兩個(gè)命題，復(fù)合命題為兩個(gè)命題，復(fù)合命題“p當(dāng)

19、且僅當(dāng)當(dāng)且僅當(dāng)q”稱作稱作p與與q的的等價(jià)式等價(jià)式，記作，記作pq，稱作稱作等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞. 讀作讀作“p當(dāng)且當(dāng)且僅當(dāng)僅當(dāng)q”規(guī)定規(guī)定pq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同時(shí)為真或同時(shí)為假同時(shí)為真或同時(shí)為假.pq 的邏的邏輯關(guān)系：輯關(guān)系：p與與q互為充分必要條件互為充分必要條件邏輯聯(lián)結(jié)詞等價(jià)“”1.1 命題和聯(lián)結(jié)詞pq的運(yùn)算表如下表所示。 pqpqFFTFTFTFFTTTpqpq001010100111邏輯聯(lián)結(jié)詞“”的定義1.1 命題和聯(lián)結(jié)詞n例 使用聯(lián)結(jié)詞翻譯一下命題：（1）三角形是等邊的，當(dāng)且僅當(dāng)它的3個(gè)內(nèi)角相等。（2）電燈不亮，當(dāng)且僅當(dāng)燈泡發(fā)生故障或開(kāi)關(guān)發(fā)生故障。（3）2 + 2

20、= 4，當(dāng)且僅當(dāng)今天天晴。邏輯聯(lián)結(jié)詞等價(jià)“”解：令p：三角形是等邊的。 q：三角形3個(gè)內(nèi)角相等。于是（1）可表示為：pq令r：電燈不亮。 s：燈泡發(fā)生故障。 t：開(kāi)關(guān)發(fā)生故障。于是（2）可表示成：r(st)。令a：2 + 2 = 4。 b：今天天晴。于是（3）可表示為：ab36等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞例例5 求下列復(fù)合命題的真值求下列復(fù)合命題的真值(1) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 3 + 3 6. (2) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 3 是偶數(shù)是偶數(shù).(3) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 太陽(yáng)從東方升起太陽(yáng)從東方升起.(4) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 美國(guó)位于非洲美國(guó)位于

21、非洲.1010l 聯(lián)結(jié)詞的運(yùn)算順序：聯(lián)結(jié)詞的運(yùn)算順序： , , , , , , , , , , 同級(jí)從同級(jí)從左到右順序進(jìn)行左到右順序進(jìn)行. ( ). ( )最先最先, , 按從內(nèi)到外順序進(jìn)行按從內(nèi)到外順序進(jìn)行. .38l 本小節(jié)中本小節(jié)中p, q, r, 均表示命題均表示命題.l 聯(lián)結(jié)詞集為聯(lián)結(jié)詞集為 , , , , ， p, p q, p q, pq, pq為為基本復(fù)合命題基本復(fù)合命題. 其中要特別注意理解其中要特別注意理解pq的涵義的涵義. 多次使用多次使用 , , , , 中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題中的聯(lián)結(jié)詞組成更為復(fù)雜的復(fù)合命題.小結(jié)小結(jié)l 聯(lián)結(jié)詞的運(yùn)算順序：聯(lián)結(jié)詞的運(yùn)算順序：

22、, , , , , 同級(jí)從左到右順序進(jìn)行同級(jí)從左到右順序進(jìn)行. ( )最先最先, 按從內(nèi)到外順序進(jìn)行按從內(nèi)到外順序進(jìn)行.391.2 命題公式及其賦值命題公式及其賦值命題變項(xiàng)與合式公式命題變項(xiàng)與合式公式l 命題變項(xiàng)命題變項(xiàng)l 合式公式合式公式l 合式公式的層次合式公式的層次公式的賦值公式的賦值l 公式賦值公式賦值l 公式類型公式類型l 真值表真值表40命題變項(xiàng)與合式公式命題變項(xiàng)與合式公式 命題常項(xiàng)：命題常項(xiàng)：簡(jiǎn)單命題是命題邏輯中最基本的研究單元，其真值簡(jiǎn)單命題是命題邏輯中最基本的研究單元，其真值是確定的，又稱作命題常項(xiàng)或命題常元。是確定的，又稱作命題常項(xiàng)或命題常元。 命題變項(xiàng)（命題變?cè)┟}變項(xiàng)

23、（命題變?cè)喝≈担喝≈?或或0的變?cè)Q作命題變?cè)?。的變?cè)Q作命題變?cè)?常項(xiàng)與變項(xiàng)均用常項(xiàng)與變項(xiàng)均用 p, q, r, , pi, qi, ri, , 等表示等表示. 定義定義1.6 合式公式合式公式（簡(jiǎn)稱公式）的遞歸定義：（簡(jiǎn)稱公式）的遞歸定義： (1) 單個(gè)命題變項(xiàng)和命題常項(xiàng)是合式公式單個(gè)命題變項(xiàng)和命題常項(xiàng)是合式公式, 稱作稱作原子命題公式原子命題公式 (2) 若若A是合式公式，則是合式公式，則 ( A)也是也是合式公式合式公式 (3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是也是合合式公式式公式 (4) 只有有限次地應(yīng)用只有有限次地應(yīng)

24、用(1)(3) 形成的符號(hào)串是合式公式形成的符號(hào)串是合式公式幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：歸納或遞歸定義歸納或遞歸定義, 外層括號(hào)可以省去外層括號(hào)可以省去41合式公式的層次合式公式的層次定義定義1.7(1) 若公式若公式A是單個(gè)命題變項(xiàng)，則稱是單個(gè)命題變項(xiàng)，則稱A為為0層公式層公式.(2) 稱稱 A 是是 n+1(n0) 層公式是指下面情況之一：層公式是指下面情況之一： (a) A= B, B 是是 n 層公式；層公式； (b) A=B C, 其中其中B,C 分別為分別為 i 層和層和 j 層公式，層公式， 且且 n=max(i,j)； (c) A=B C, 其中其中 B,C 的層次及的層次及 n 同同

25、(b)； (d) A=BC, 其中其中B,C 的層次及的層次及 n 同同(b)； (e) A=BC, 其中其中B,C 的層次及的層次及 n 同同(b). (3) 若公式若公式A的層次為的層次為k, 則稱則稱A為為k層公式層公式.例如例如 公式公式 A=p, B= p, C= pq, D= (pq)r, E=( p q) r) ( r s) 分別為分別為0層，層，1層，層，2層，層，3層，層，4層公式層公式.42定義定義1.8 設(shè)設(shè)p1, p2, , pn是出現(xiàn)在公式是出現(xiàn)在公式A中的全部命題變項(xiàng)中的全部命題變項(xiàng), 給給p1, p2, , pn各指定一個(gè)真值各指定一個(gè)真值, 稱為對(duì)稱為對(duì)A的一個(gè)

26、的一個(gè)賦值賦值或或解釋解釋. 若賦值使若賦值使A為為1, 則稱這組值為則稱這組值為A的的成真賦值成真賦值; 若賦值使若賦值使A為為0, 則稱這組值為則稱這組值為A的的成假賦值成假賦值.幾點(diǎn)說(shuō)明：幾點(diǎn)說(shuō)明：l A中僅出現(xiàn)中僅出現(xiàn) p1, p2, , pn，給，給A賦值賦值 = 1 2 n是指是指 p1= 1, p2= 2, , pn= n, i=0或或1, i之間不加標(biāo)點(diǎn)符號(hào)之間不加標(biāo)點(diǎn)符號(hào)l A中僅出現(xiàn)中僅出現(xiàn) p, q, r, , 給給A賦值賦值 1 2 3是指是指 p= 1, q= 2 , r= 3 l 含含n個(gè)命題變項(xiàng)的公式有個(gè)命題變項(xiàng)的公式有2n個(gè)賦值個(gè)賦值. 如如 000, 010,

27、 101, 110是是 (pq)r的成真賦值的成真賦值 001, 011, 100, 111是成假賦值是成假賦值.公式的賦值公式的賦值43定義定義1.9 將命題公式將命題公式A在所有賦值下取值的情況列成表在所有賦值下取值的情況列成表, 稱作稱作A的的真值表真值表.構(gòu)造真值表的步驟構(gòu)造真值表的步驟:(1) 找出公式中所含的全部命題變項(xiàng)找出公式中所含的全部命題變項(xiàng)p1, p2, , pn(若無(wú)下角標(biāo)若無(wú)下角標(biāo) 則按字母順序排列則按字母順序排列), 列出列出2n個(gè)全部賦值個(gè)全部賦值, 從從000開(kāi)始開(kāi)始, 按按 二進(jìn)制加法二進(jìn)制加法, 每次加每次加1, 直至直至111為止為止. (2) 按從低到高的

28、順序?qū)懗龉降母鱾€(gè)層次按從低到高的順序?qū)懗龉降母鱾€(gè)層次.(3) 對(duì)每個(gè)賦值依次計(jì)算各層次的真值對(duì)每個(gè)賦值依次計(jì)算各層次的真值, 直到最后計(jì)算出公式直到最后計(jì)算出公式 的真值為止的真值為止.真值表真值表44例例6 寫出下列公式的真值表寫出下列公式的真值表, 并求它們的成真賦值和成假并求它們的成真賦值和成假 賦值賦值: (1) (p q) r (2) (qp) qp (3) ( p q) q啞元：?jiǎn)≡篈: (p q) B: r,共含共含p、q 、r三個(gè)命題變項(xiàng)，則三個(gè)命題變項(xiàng)，則r為為A的的啞元；啞元； p、q為為B的啞元的啞元.真值表真值表45(1) A = (p q) r成真賦值成真賦值:

29、000,001,010,100,110; 成假賦值成假賦值:011,101,111 p q rp q r (p q)r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 00111111 10101010 11101010 真值表真值表146(2) B(qp) qp成真賦成真賦值值:00,01,10,11; 無(wú)成假賦值無(wú)成假賦值p q qp(qp) q(qp) qp0 00 11 01 1101100011111真值表真值表247(3) C ( p q) q的真值表的真值表成假賦值成假賦值:00,01,10,11; 無(wú)成真賦值無(wú)成真賦值p q p p q ( p

30、q) ( p q) q0 00 11 01 11100110100100000真值表真值表348公式的類型公式的類型定義定義1.10 (1) 若若A在它的任何賦值下均為真在它的任何賦值下均為真, 則稱則稱A為為重言式重言式或或永真式永真式;(2) 若若A在它的任何賦值下均為假在它的任何賦值下均為假, 則稱則稱A為為矛盾式矛盾式或或永假式永假式;(3) 若若A不是矛盾式不是矛盾式, 則稱則稱A是是可滿足式可滿足式.若若A是可滿足式，且它至少存在一個(gè)成假賦值，則是可滿足式，且它至少存在一個(gè)成假賦值，則A為為非重言式的可滿足非重言式的可滿足式式。由例由例6的（的（1）式：）式：(p q) r為非重言

31、式的可滿足式為非重言式的可滿足式, （2）(qp) qp為重言式為重言式, （3） ( p q) q為矛盾式為矛盾式.注意：重言式是可滿足式，但反之不真注意：重言式是可滿足式，但反之不真.真值表的用途真值表的用途: 求出公式的全部成真賦值與成假賦值求出公式的全部成真賦值與成假賦值, 判斷公式的類型判斷公式的類型49第一章第一章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l 命題、真值、簡(jiǎn)單命題與復(fù)合命題、命題符號(hào)化命題、真值、簡(jiǎn)單命題與復(fù)合命題、命題符號(hào)化l 聯(lián)結(jié)詞聯(lián)結(jié)詞 , , , , 及復(fù)合命題符號(hào)化及復(fù)合命題符號(hào)化l 命題公式及層次命題公式及層次l 公式的類型公式的類型l 真值表及應(yīng)用真值表及應(yīng)用基本

32、要求基本要求l 深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系深刻理解各聯(lián)結(jié)詞的邏輯關(guān)系, 熟練地將命題符號(hào)化熟練地將命題符號(hào)化l 會(huì)求復(fù)合命題的真值會(huì)求復(fù)合命題的真值l 深刻理解合式公式及重言式、矛盾式、可滿足式等概念深刻理解合式公式及重言式、矛盾式、可滿足式等概念l 熟練地求公式的真值表，并用它求公式的成真賦值與成假熟練地求公式的真值表，并用它求公式的成真賦值與成假賦值及判斷公式類型賦值及判斷公式類型第一章作業(yè)第一章作業(yè)補(bǔ)充：填空題補(bǔ)充：填空題（1）公式）公式(pq) ( p q) 的成真賦值為的成真賦值為 。 （2）設(shè)）設(shè)p,r為真命題，為真命題，q,s為假命題，則復(fù)合命題為假命題，則復(fù)合命題 (pq) (

33、 r s)的真值為的真值為 。（3）設(shè)）設(shè)p,q均為命題，在均為命題，在 條件下，條件下，p與與q的排斥或也可的排斥或也可以寫成以寫成p與與q的相容或。的相容或。（4）公式）公式 (pq)與與(pq) ( p q) 共同的成真賦值為共同的成真賦值為 。（5）設(shè)）設(shè)A為任意的公式，為任意的公式，B為重言式，則為重言式，則A B的類型為的類型為 。P14 習(xí)題一習(xí)題一1.(9)(10)(11)(12)(13) 4.(5) 5.(5) 6.(1) 8.(1)(3)(5) 9.(7)10.(4) 15.(3)(4) 19.(1)(3)(5) 20.(4) 21.(3)511. 1. 將下列命題符號(hào)化將下列命題符號(hào)化 (1) (1) 豆沙包是由面粉和紅小豆做成的豆沙包是由面粉和紅小豆做成的. . (2) (2) 蘋果樹和梨樹都是落葉喬木蘋果樹和梨樹都是落葉喬木. . (3) (3) 王小紅或李大明是物理組成