數(shù)理邏輯課件(離散數(shù)學(xué))

1、第一部分 數(shù)理邏輯1數(shù)理邏輯部分主要內(nèi)容：數(shù)理邏輯部分主要內(nèi)容：命題邏輯命題邏輯1.1 命題符號(hào)化及聯(lián)結(jié)詞命題符號(hào)化及聯(lián)結(jié)詞1.2 命題公式及分類命題公式及分類2.1 等值演算等值演算2.2 范式范式2.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集3.1-3.2 推理理論推理理論一階邏輯一階邏輯（謂詞邏輯）（謂詞邏輯）4.1一階邏輯命題符號(hào)化一階邏輯命題符號(hào)化4.2 一階邏輯公式及解釋一階邏輯公式及解釋5.1一階邏輯等值式與置換一階邏輯等值式與置換規(guī)則規(guī)則5.2一階邏輯前束范式一階邏輯前束范式5.3一階邏輯的推理理論一階邏輯的推理理論2第一章第一章 命題邏輯基本概念命題邏輯基本概念3 1.1 命題與聯(lián)結(jié)詞

2、命題與聯(lián)結(jié)詞 l命題與真值命題與真值l原子命題的符號(hào)化原子命題的符號(hào)化l復(fù)合命題復(fù)合命題l聯(lián)結(jié)詞聯(lián)結(jié)詞 重點(diǎn)內(nèi)容：重點(diǎn)內(nèi)容：命題的符號(hào)化命題的符號(hào)化4 例例1 1： 下列句子中哪些是命題？并判斷真值下列句子中哪些是命題？并判斷真值 (1) 清華大學(xué)是一所全國(guó)重點(diǎn)大學(xué)清華大學(xué)是一所全國(guó)重點(diǎn)大學(xué). (2) 2 + 5 8. (3) 你有鉛筆嗎？你有鉛筆嗎？ (4) 這只兔子跑得真快呀！這只兔子跑得真快呀！ (5) 請(qǐng)不要講話！請(qǐng)不要講話！真命題真命題假命題假命題疑問句疑問句感嘆句感嘆句祈使句祈使句一、命題與真值（例題）一、命題與真值（例題） 5一、命題與真值一、命題與真值l命題命題: 判斷結(jié)果惟一

3、的陳述句判斷結(jié)果惟一的陳述句l命題的真值命題的真值: 判斷的結(jié)果判斷的結(jié)果l真值的取值真值的取值: 真、假真、假l真命題真命題: 真值為真的命題真值為真的命題l假命題假命題: 真值為假的命題真值為假的命題6一、命題與真值（例題）一、命題與真值（例題）例例2：判斷下列語句是否是命題：判斷下列語句是否是命題l明年我將去歐洲明年我將去歐洲l下個(gè)月十五號(hào)是晴天下個(gè)月十五號(hào)是晴天lxy2是命題是命題不是命題不是命題不確定真值不確定真值不知道真值不知道真值7一、命題與真值（例題）一、命題與真值（例題）例例3：“我正在說假話我正在說假話”，這句話是命題嗎？，這句話是命題嗎？如果這句話如果這句話是是“真真”的

4、的如果這句話如果這句話是是“假假”的的根據(jù)這句話的意義推根據(jù)這句話的意義推得這句話是得這句話是“假假”的的這句話是這句話是“真真”的的該陳述句為該陳述句為悖論悖論該陳述句不是命題該陳述句不是命題8一、命題與真值（小結(jié)）一、命題與真值（小結(jié)）1.感嘆句、祈使句、疑問句屬于感嘆句、祈使句、疑問句屬于非陳述非陳述句句，所以都不是命題；，所以都不是命題；2.如果陳述句的如果陳述句的判斷結(jié)果不惟一確定判斷結(jié)果不惟一確定，那么該陳述句也不是命題；那么該陳述句也不是命題；3.陳述句中的陳述句中的悖論悖論也不是命題。也不是命題。 9二、命題符號(hào)化二、命題符號(hào)化“ 是有理數(shù)是有理數(shù)”，是命題，且真值為，是命題，

5、且真值為 0或或F；2 + 5 = 7，是命題，且真值為，是命題，且真值為 1或或T；2上述命題不能再分解為更簡(jiǎn)單的命題。上述命題不能再分解為更簡(jiǎn)單的命題。 定義：定義：一個(gè)命題不能再分解為更簡(jiǎn)單的命題，一個(gè)命題不能再分解為更簡(jiǎn)單的命題，則稱該命題為則稱該命題為原子命題原子命題，也稱簡(jiǎn)單命題。，也稱簡(jiǎn)單命題。命題邏輯中研究命題邏輯中研究的最基本單位的最基本單位10二、命題符號(hào)化二、命題符號(hào)化l用小寫英文字母用小寫英文字母 p，q，r， ，pi，qi，ri (i1）等表示簡(jiǎn)單命題（原子命題）。）等表示簡(jiǎn)單命題（原子命題）。 例：例： 令令p: 2 + 5 = 7l用用“1”或或“T”表示真，用表

6、示真，用“0”或或“F”表表示假。示假。11二、命題符號(hào)化二、命題符號(hào)化令令 t：我來自西安，：我來自西安， s：我是一名教師。：我是一名教師。問題：?jiǎn)栴}：如何表示如何表示“我是一名教師，并且我是一名教師，并且我來自西安我來自西安”？復(fù)合命題復(fù)合命題 定義：定義：由簡(jiǎn)單命題與聯(lián)結(jié)詞按一定規(guī)則由簡(jiǎn)單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題。復(fù)合而成的命題。12三、復(fù)合命題及聯(lián)結(jié)詞三、復(fù)合命題及聯(lián)結(jié)詞 1.否定式與否定聯(lián)結(jié)詞否定式與否定聯(lián)結(jié)詞“ ”定義：定義：設(shè)設(shè)p為命題，復(fù)為命題，復(fù)合命題合命題 “非非p”（或（或 “p的否定的否定”）稱為）稱為p的的否否定式定式，記作，記作 p，符號(hào)，符號(hào) 稱作否

7、定聯(lián)結(jié)詞。稱作否定聯(lián)結(jié)詞。 p真值表真值表p p011013三、復(fù)合命題及聯(lián)結(jié)詞三、復(fù)合命題及聯(lián)結(jié)詞例如：例如：p:上海是一個(gè)城市。上海是一個(gè)城市。 p:上海不是一個(gè)城市。上海不是一個(gè)城市。規(guī)則：規(guī)則： ( p)等價(jià)于等價(jià)于pp:上海是一個(gè)大城市。上海是一個(gè)大城市。 p:上海是一個(gè)小城市。上海是一個(gè)小城市。 p:上海不是一個(gè)大城市。上海不是一個(gè)大城市。14三、復(fù)合命題及聯(lián)結(jié)詞三、復(fù)合命題及聯(lián)結(jié)詞 “p與與q”記作記作pq 稱為稱為p、q的的合取式合取式 為合取聯(lián)結(jié)詞為合取聯(lián)結(jié)詞2. 合取式與合取聯(lián)結(jié)詞合取式與合取聯(lián)結(jié)詞“”pqp q00001010011115三、復(fù)合命題及聯(lián)結(jié)詞（例題）三、復(fù)

8、合命題及聯(lián)結(jié)詞（例題）例例4： 將下列命題符號(hào)化。將下列命題符號(hào)化。 (1) 王曉王曉既既用功用功又又聰明。聰明。(2) 王曉王曉不僅不僅聰明，聰明，而且而且用功。用功。(3) 王曉王曉雖然雖然聰明，聰明，但但不用功。不用功。(4) 張輝張輝與與王麗都是三好生。王麗都是三好生。(5) 張輝與王麗是同學(xué)。張輝與王麗是同學(xué)。簡(jiǎn)單命題簡(jiǎn)單命題pqpqp( q)rs令令 p：王曉用功；：王曉用功；q：王曉聰明；：王曉聰明； r : 張輝是三好學(xué)生張輝是三好學(xué)生 s : 王麗是三好學(xué)生王麗是三好學(xué)生16三、復(fù)合命題及聯(lián)結(jié)詞三、復(fù)合命題及聯(lián)結(jié)詞p pp 1p 0p ( p)等價(jià)于等價(jià)于 p等價(jià)于等價(jià)于p等

9、價(jià)于等價(jià)于0等價(jià)于等價(jià)于 0關(guān)于關(guān)于“合取合取”的相關(guān)規(guī)則的相關(guān)規(guī)則 例例5：計(jì)算下列：計(jì)算下列命題的真值命題的真值 ( 1 0 )1( p 0 )( ( p 0 ) ) 100117三、復(fù)合命題及聯(lián)結(jié)詞三、復(fù)合命題及聯(lián)結(jié)詞合取滿足交換律。合取滿足交換律。p q 等價(jià)于等價(jià)于q p 合取滿足結(jié)合律。合取滿足結(jié)合律。p (q r) 等價(jià)于等價(jià)于(pq) r 18三、復(fù)合命題及聯(lián)結(jié)詞三、復(fù)合命題及聯(lián)結(jié)詞 “p或或q”記作記作pq稱作稱作p與與q的的析取式析取式稱作析取聯(lián)結(jié)詞稱作析取聯(lián)結(jié)詞3.析取式與析取聯(lián)結(jié)詞析取式與析取聯(lián)結(jié)詞pqp q00001110111119三、復(fù)合命題及聯(lián)結(jié)詞（例題）三、復(fù)

10、合命題及聯(lián)結(jié)詞（例題） 例例6 6：將命題：將命題“2或或4”是素?cái)?shù)符號(hào)化是素?cái)?shù)符號(hào)化 pq令令p:2是素?cái)?shù)是素?cái)?shù);q:4是素?cái)?shù)；是素?cái)?shù)；例例7：將下列命題符號(hào)化：將下列命題符號(hào)化l小元元只能拿一個(gè)蘋果或一個(gè)梨。小元元只能拿一個(gè)蘋果或一個(gè)梨。l王曉紅生于王曉紅生于1975年或年或1976年。年。 t :小元元拿一個(gè)蘋果小元元拿一個(gè)蘋果;u:小元元拿一個(gè)梨；小元元拿一個(gè)梨； v :王曉紅生于王曉紅生于1975年年;w:王曉紅生于王曉紅生于1976年。年。20三、復(fù)合命題及聯(lián)結(jié)詞（例題續(xù)）三、復(fù)合命題及聯(lián)結(jié)詞（例題續(xù)） 分析：分析：在例在例6中，構(gòu)成復(fù)合命題的兩個(gè)中，構(gòu)成復(fù)合命題的兩個(gè)原子命題之間

11、沒有排斥性，即兩個(gè)原子原子命題之間沒有排斥性，即兩個(gè)原子命題有同時(shí)為真的可能性。命題有同時(shí)為真的可能性。 例例7中，構(gòu)成復(fù)合命題的兩個(gè)原子命題之中，構(gòu)成復(fù)合命題的兩個(gè)原子命題之間間存在排斥性。存在排斥性。相容或相容或排斥或排斥或21三三、復(fù)合命題及聯(lián)結(jié)詞（例題續(xù)）、復(fù)合命題及聯(lián)結(jié)詞（例題續(xù)）“排斥或排斥或”的復(fù)合命題該如何符號(hào)化呢？的復(fù)合命題該如何符號(hào)化呢？l小元元只能拿一個(gè)蘋果或一個(gè)梨。小元元只能拿一個(gè)蘋果或一個(gè)梨。 符號(hào)化為符號(hào)化為 (t u) ( tu)l王曉紅生于王曉紅生于1975年或年或1976年。年。 符號(hào)化為符號(hào)化為 (v w) ( vw) 也可以表示成：也可以表示成：v w可以

12、用可以用異異或或來表示來表示注意對(duì)比這注意對(duì)比這兩個(gè)兩個(gè)“排斥排斥或或”的不同的不同注意對(duì)比這注意對(duì)比這兩個(gè)兩個(gè)“排斥排斥或或”的不同的不同22三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞 小結(jié)：小結(jié)：自然語言中的自然語言中的“或或”是多義的，主是多義的，主要有以下兩種情況：要有以下兩種情況：l可兼或（相容或）可兼或（相容或）：二者至少有一個(gè)發(fā)生，：二者至少有一個(gè)發(fā)生，不排斥二者都發(fā)生的情況。同析取聯(lián)結(jié)詞不排斥二者都發(fā)生的情況。同析取聯(lián)結(jié)詞的含義完全相同。的含義完全相同。l排斥或排斥或：非此即彼，二者不可兼得。：非此即彼，二者不可兼得。23三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞p pp 1p 0

13、p ( p)等價(jià)于等價(jià)于p等價(jià)于等價(jià)于1等價(jià)于等價(jià)于p等價(jià)于等價(jià)于1關(guān)于關(guān)于“析取析取”的相關(guān)規(guī)則的相關(guān)規(guī)則析取也滿足析取也滿足交換律交換律合合結(jié)合律結(jié)合律。24三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞 例例8：假設(shè)：假設(shè)e表示表示“Alice高興高興”，r表示表示“Tom高興高興”，那么將下列自然語言的，那么將下列自然語言的陳述轉(zhuǎn)換成邏輯命題。陳述轉(zhuǎn)換成邏輯命題。如果如果Alice高興，高興，那么那么Tom高興；高興；除非除非Alice 高興，高興， Tom 才才高興；高興；25三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞 4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“” “如果如果p,則則q” 稱

14、作稱作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é)詞，或條件聯(lián)結(jié)詞。，或條件聯(lián)結(jié)詞。26三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞pqp q001011100111p q真值表真值表善意的善意的推定推定27三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞lp q 的邏輯關(guān)系：的邏輯關(guān)系： p是是q的充分條件；的充分條件；q 為為 p 的必要條件。的必要條件。l“如果如果則則 ” 的不同表述法有：的不同表述法有：“只只要要 就就”，“僅當(dāng)僅當(dāng)”，“除非除非才才 ”等。等。28三三、復(fù)合命題及聯(lián)結(jié)詞（例題）、復(fù)合

15、命題及聯(lián)結(jié)詞（例題） 例例9：將下列命題符號(hào)化：將下列命題符號(hào)化（1）只有努力才能取得成功）只有努力才能取得成功（2）只要努力過就不后悔）只要努力過就不后悔設(shè)：設(shè)： p p: :努力努力 q q: :成功成功 s：努力過：努力過 t：不后悔：不后悔qpst29三三、復(fù)合命題及聯(lián)結(jié)詞（例題）、復(fù)合命題及聯(lián)結(jié)詞（例題） 例例10：設(shè)：設(shè) p p: :天冷，天冷，q q: :小王穿羽絨服，小王穿羽絨服， 將下列命題符號(hào)化將下列命題符號(hào)化 (1) 只要只要天冷，小王天冷，小王就就穿羽絨服。穿羽絨服。 (2) 因?yàn)橐驗(yàn)樘炖洌炖?，所以所以小王穿羽絨服。小王穿羽絨服。 (3) 若小王不穿羽絨服，則天不冷。

16、若小王不穿羽絨服，則天不冷。 (4) 只有只有天冷，小王天冷，小王才才穿羽絨服。穿羽絨服。pqpq q pqp 30三三、復(fù)合命題及聯(lián)結(jié)詞（例題續(xù)）、復(fù)合命題及聯(lián)結(jié)詞（例題續(xù)） (5) 除非除非天冷，小王天冷，小王才才穿羽絨服。穿羽絨服。 (6) 除非除非小王穿羽絨服，小王穿羽絨服，否則否則天天不不冷。冷。 (7) 如果如果天不冷，天不冷，則則小王不穿羽絨服。小王不穿羽絨服。 (8) 小王穿羽絨服小王穿羽絨服僅當(dāng)僅當(dāng)天冷的時(shí)候。天冷的時(shí)候。pqqp p qqp31三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞 小結(jié)：小結(jié)：l只有只有才、除非才、除非才、僅當(dāng)表達(dá)的是才、僅當(dāng)表達(dá)的是必必要要條件；條件；

17、l只要只要就、如果就、如果就（則）表達(dá)的是就（則）表達(dá)的是充充分分條件；條件；課堂練習(xí)：習(xí)題課堂練習(xí)：習(xí)題832三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞5.等價(jià)式與等價(jià)聯(lián)結(jié)詞等價(jià)式與等價(jià)聯(lián)結(jié)詞“” “p當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)q”記作記作pq 稱作稱作p、q的的等價(jià)式等價(jià)式 也稱作也稱作雙條件式雙條件式稱作稱作等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞。pqp q00101010011133三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞 需要注意以下兩點(diǎn)：需要注意以下兩點(diǎn)：l 等價(jià)聯(lián)結(jié)詞等價(jià)聯(lián)結(jié)詞即通常的即通常的“充分必要條充分必要條件件”;l pq為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p與與q同真或同假，也同真或同假，也稱稱“同或同或”。3

18、4三三、復(fù)合命題及聯(lián)結(jié)詞（例題）、復(fù)合命題及聯(lián)結(jié)詞（例題）例例1111：求下列復(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) 太陽從東方升起。太陽從東方升起。(4) 2 + 2 4 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) 美國(guó)位于非洲美國(guó)位于非洲。1010復(fù)合命題的真值取決于構(gòu)成它的各原子命題復(fù)合命題的真值取決于構(gòu)成它的各原子命題的真值，的真值，而與它們的內(nèi)容、含義無關(guān)。而與它們的內(nèi)容、含義無關(guān)。 35三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞 等價(jià)聯(lián)結(jié)詞具有以下性質(zhì)：等

19、價(jià)聯(lián)結(jié)詞具有以下性質(zhì)：l滿足結(jié)合律滿足結(jié)合律(p q) r等價(jià)于等價(jià)于p (q r)l滿足交換律滿足交換律p q等價(jià)于等價(jià)于 q plp p的真值永遠(yuǎn)為的真值永遠(yuǎn)為“真真”lp p的真值永遠(yuǎn)為的真值永遠(yuǎn)為“假假”36三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞 有關(guān)聯(lián)結(jié)詞優(yōu)先級(jí)如下：有關(guān)聯(lián)結(jié)詞優(yōu)先級(jí)如下：l聯(lián)結(jié)詞的優(yōu)先順序?yàn)椋郝?lián)結(jié)詞的優(yōu)先順序?yàn)椋?, , , , ; l如果出現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無括號(hào)時(shí)，如果出現(xiàn)的聯(lián)結(jié)詞同級(jí)，又無括號(hào)時(shí)，則按從左到右的順序運(yùn)算則按從左到右的順序運(yùn)算; l有括號(hào)時(shí)，應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算有括號(hào)時(shí)，應(yīng)該先進(jìn)行括號(hào)中的運(yùn)算。37三三、復(fù)合命題及聯(lián)結(jié)詞、復(fù)合命題及聯(lián)結(jié)詞（1

20、） 與與 含義相同含義相同（2） 與與 含義相同含義相同（3） 與與 含義相同含義相同qp q)p( rqp r)qp( rqp )rq(p 由聯(lián)結(jié)詞的優(yōu)先級(jí)可得：由聯(lián)結(jié)詞的優(yōu)先級(jí)可得：38例題例題 例例12：利用聯(lián)結(jié)詞，將下述語句符號(hào)化：利用聯(lián)結(jié)詞，將下述語句符號(hào)化：“如果你走路時(shí)看書，那么你一定會(huì)成如果你走路時(shí)看書，那么你一定會(huì)成為近視眼為近視眼”。解：令解：令 p：你走路；：你走路； q：你看書；：你看書； r：你是近視眼。：你是近視眼。 則上述語句可以符號(hào)化為：則上述語句可以符號(hào)化為： (p q) r 39例題例題 例例13：將下列命題符號(hào)化：將下列命題符號(hào)化（1）他努力而且聰明，這不

21、是真的。）他努力而且聰明，這不是真的。 令令 p:他努力；他努力；q:他聰明他聰明)qp( （2）雖然天氣很冷，老王還是來了。）雖然天氣很冷，老王還是來了。 令令 p:天氣很冷；天氣很冷；q:老王來了老王來了qp 40例題例題（3）不經(jīng)一事，不長(zhǎng)一智）不經(jīng)一事，不長(zhǎng)一智 令令 p:經(jīng)一事；經(jīng)一事；q:長(zhǎng)一智長(zhǎng)一智qp （4）若兩個(gè)圓面積相等，那么它們的半）若兩個(gè)圓面積相等，那么它們的半徑相等；徑相等；反之亦然反之亦然。 令令 p:兩個(gè)圓面積相等；兩個(gè)圓面積相等； q:兩個(gè)圓半徑相等兩個(gè)圓半徑相等qp 41例題例題 例例14：符號(hào)化下列兩個(gè)命題：符號(hào)化下列兩個(gè)命題l如果你和他都不固執(zhí)己見的話，那

22、么不如果你和他都不固執(zhí)己見的話，那么不愉快的事也不會(huì)發(fā)生了。愉快的事也不會(huì)發(fā)生了。l如果你和他不都固執(zhí)己見的話，那么不如果你和他不都固執(zhí)己見的話，那么不愉快的事也不會(huì)發(fā)生了。愉快的事也不會(huì)發(fā)生了。r)qp( r)qp( 42例題例題 例例15：將下列命題符號(hào)化，并討論各命：將下列命題符號(hào)化，并討論各命題的真值。題的真值。l若今天是星期一，則明天是星期二若今天是星期一，則明天是星期二l若今天是星期一，則明天是星期三若今天是星期一，則明天是星期三43作業(yè)作業(yè)習(xí)題一：習(xí)題一：14，15441.2 命題公式及其賦值命題公式及其賦值l命題常項(xiàng)和命題變項(xiàng)命題常項(xiàng)和命題變項(xiàng)l合式公式合式公式l公式的賦值公式

23、的賦值l真值表真值表l公式的分類公式的分類45一、命題常項(xiàng)和命題變項(xiàng)一、命題常項(xiàng)和命題變項(xiàng) 命題常項(xiàng)命題常項(xiàng)：一個(gè)確定的具體的簡(jiǎn)單命題稱作命一個(gè)確定的具體的簡(jiǎn)單命題稱作命題常項(xiàng)。也稱命題常元。題常項(xiàng)。也稱命題常元。 命題變項(xiàng)命題變項(xiàng)：當(dāng)：當(dāng)p p所代表的只是一個(gè)抽象的命題，所代表的只是一個(gè)抽象的命題，它可以表示任意的命題，稱它可以表示任意的命題，稱p p為命題變項(xiàng)。也稱為命題變項(xiàng)。也稱命題變?cè)Ｃ}變?cè)?。命題變項(xiàng)不是命題。命題變項(xiàng)不是命題。p:天氣很冷天氣很冷46一、命題常項(xiàng)和命題變項(xiàng)一、命題常項(xiàng)和命題變項(xiàng) 當(dāng)用一個(gè)特定的命題取代命題變?cè)?dāng)用一個(gè)特定的命題取代命題變?cè)獣r(shí)，才能確定其真值：真或假

24、。這種取時(shí)，才能確定其真值：真或假。這種取代稱作對(duì)該命題變?cè)Q作對(duì)該命題變?cè)概烧嬷抵概烧嬷?。p:太陽從東邊升起太陽從東邊升起p:太陽從東邊升起太陽從東邊升起47二、合式公式二、合式公式1.合式公式的一般化定義：合式公式的一般化定義： 將命題變項(xiàng)用聯(lián)結(jié)詞和括號(hào)按一將命題變項(xiàng)用聯(lián)結(jié)詞和括號(hào)按一定邏輯關(guān)系聯(lián)結(jié)起來的定邏輯關(guān)系聯(lián)結(jié)起來的符號(hào)串符號(hào)串稱作稱作合合式公式式公式，也稱，也稱命題公式命題公式，簡(jiǎn)稱，簡(jiǎn)稱公式公式。公式通常用字母公式通常用字母A、B、C等表示。等表示。例：例：( p q) r)( r s)48二、合式公式二、合式公式2.合式公式合式公式 的遞歸定義：的遞歸定義：(1) 單個(gè)命

25、題常項(xiàng)或變項(xiàng)單個(gè)命題常項(xiàng)或變項(xiàng) p,q,r,是合式公式；是合式公式；(2) 若若A是合式公式，則是合式公式，則 ( A)也是合式公式；也是合式公式；(3) 若若A, B是合式公式，則是合式公式，則(A B), (A B), (AB), (AB)也是合式公式；也是合式公式；(4) 只有有限次地應(yīng)用只有有限次地應(yīng)用(1)(3)形成的包含命題變?cè)?、?lián)結(jié)詞形成的包含命題變?cè)?、?lián)結(jié)詞和括號(hào)的符號(hào)串才是合式公式。和括號(hào)的符號(hào)串才是合式公式。此處的此處的A、B等稱等稱作元語言符號(hào)，作元語言符號(hào)，代表抽象的公式代表抽象的公式49二、合式公式二、合式公式3.子公式子公式 定義定義：若：若A為合式公式，為合式公式

26、，B為為A的一部分，且的一部分，且B也是合式公式，則稱也是合式公式，則稱B為為A的子公式。的子公式。例：例：( p q) r是合式公式是合式公式A， p q是合式公式是合式公式B，B是是A的一部分。的一部分。 稱稱B是是A的子公式。的子公式。 50三、公式的賦值三、公式的賦值 p q是一個(gè)合式公式，但是真值是多少呢？是一個(gè)合式公式，但是真值是多少呢？ 若令若令 p:2是偶數(shù)，是偶數(shù)，q：2是素?cái)?shù)，則是素?cái)?shù)，則p q真值為真；真值為真； 若令若令 p:3是偶數(shù)，是偶數(shù)，q：3是素?cái)?shù)，則是素?cái)?shù)，則p q真值為假；真值為假； 定義：定義： 給公式給公式A中的命題變項(xiàng)中的命題變項(xiàng) p1, p2, ,

27、pn給給予一定的解釋，使其獲得一組確定的真值，這予一定的解釋，使其獲得一組確定的真值，這個(gè)過程稱為對(duì)個(gè)過程稱為對(duì)A的一個(gè)的一個(gè)賦值賦值或或解釋。解釋。51三、公式的賦值三、公式的賦值例例1： 公式公式B = ( p q) q 的真值表的真值表 p q p p q ( p q) ( p q) q0 00 11 01 1 110011010010000052 p q r p q r (p q)r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 0 1 1 1 0011111 1 1010101 0 11101010例例2：C= (p q) r 的的真值表真值表含含n個(gè)變項(xiàng)的公式有個(gè)變項(xiàng)的公式有2n個(gè)賦值。個(gè)賦值。成成假假賦賦值值53四、公式的層次四、公式的層次 公式公式( p q) r)( r s) p 0