1、,離散數(shù)學(xué)是現(xiàn)代數(shù)學(xué)的一個(gè)重要分支 隨著計(jì)算機(jī)科學(xué)的發(fā)展逐步建立 以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標(biāo)。 與連續(xù)性數(shù)學(xué)的區(qū)別與聯(lián)系 參考文獻(xiàn)：,教材與參考書(shū),屈婉玲、耿素云、張立昂，離散數(shù)學(xué)及其應(yīng)用，高等教育出版社。 左孝陵、李為鑑、劉永才，離散數(shù)學(xué)，上?？茖W(xué)技術(shù)文獻(xiàn)出版社。 耿素云、屈婉玲、張立昂，離散數(shù)學(xué)（第五版），清華大學(xué)出版社。 屈婉玲、耿素云、張立昂，離散數(shù)學(xué)學(xué)習(xí)指導(dǎo)與習(xí)題解析，高等教育出版社。,數(shù)理邏輯（命題邏輯與謂詞邏輯） 集合論（函數(shù)與關(guān)系） 圖論 組合數(shù)學(xué) 代數(shù)結(jié)構(gòu) 格和布爾代數(shù),用數(shù)學(xué)方法（符號(hào)體系）來(lái)研究推理的規(guī)律 1847年， 邏輯的數(shù)學(xué)分析； 在自動(dòng)控制、程序設(shè)

2、計(jì)、人工智能、計(jì)算機(jī)科學(xué)等領(lǐng)域有廣泛應(yīng)用 兩個(gè)最基本內(nèi)容命題邏輯和謂詞邏輯,第一章 命題邏輯基本概念,命題：能表達(dá)判斷，具有確定真值的陳述句。 （1）6是質(zhì)數(shù)。 （2）如果6是偶數(shù)，那么3是奇數(shù)。 命題的真值: 判斷的結(jié)果 真值的取值: 真與假 真命題: 真值為真的命題 假命題: 真值為假的命題,注意: 任何命題的真值都是唯一的。 感嘆句、祈使句、疑問(wèn)句都不是命題。 陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題。,9,例 下列句子中那些是命題？ (1) 是無(wú)理數(shù). (2) 2 + 5 8. (3) x + 5 3. (4) 你有鉛筆嗎？ (5) 這只兔子跑得真快呀！ (6) 請(qǐng)不要講話！

3、(7) 我正在說(shuō)謊話.,真命題,假命題,真值不確定,疑問(wèn)句,感嘆句,祈使句,悖論,(3)(7)都不是命題,命題的類型 原子命題（簡(jiǎn)單命題）：不能分解為更簡(jiǎn)單的陳述句 復(fù)合命題：由聯(lián)結(jié)詞，標(biāo)點(diǎn)符號(hào)和原子命題復(fù)合構(gòu)成 命題的表示命題標(biāo)識(shí)符 用英文字母A, B, 或p, q, r 表示簡(jiǎn)單命題 用數(shù)字表示表示命題，如12 例如 p：2是素?cái)?shù)。 1: 雪是黑色的。 命題的真值：用“1”或“T”表示真，用“0”或“F”表示假,命題常量與命題變?cè)?命題常量：表示確定命題的命題標(biāo)識(shí)符 命題變?cè)罕硎救我饷}的位置標(biāo)志 命題變?cè)皇敲} 因?yàn)槊}變?cè)梢员硎救我饷}，所以不能確定真值。 當(dāng)命題變?cè)狿用一個(gè)特定

4、命題取代時(shí)，P才能確定真值。這時(shí)也稱對(duì)命題變?cè)狿進(jìn)行指派。,在數(shù)理邏輯中，復(fù)合命題是由原子命題 與邏輯聯(lián)結(jié)詞組合而成的。,例如： 3不是偶數(shù)。 如果今天天氣好，我就去散步。 2是素?cái)?shù)和偶數(shù)。 林芳學(xué)過(guò)英語(yǔ)或日語(yǔ)。,數(shù)理邏輯中的聯(lián)結(jié)詞要求精確嚴(yán)格， 沒(méi)有二義性。,否定聯(lián)結(jié)詞,否定：設(shè)P為一命題，P的否定是一個(gè)新命題，記為P。讀作“非P”。 真值：若P為真， P為假； 若P為假， P為真。 “”為一元運(yùn)算符。 例 P：今天是星期五。 P：今天不是星期五。,合取聯(lián)結(jié)詞,合?。簝擅}P和Q的合取是一個(gè)復(fù)合命題，記作P Q。讀作“與”。 真值：當(dāng)且僅當(dāng)P，Q同時(shí)為真時(shí)， P Q為真，否則為假。 是二元運(yùn)

5、算符。 與自然語(yǔ)言中的“與”，“既又”，“不僅而且”等意思相近。 例 P：今天是星期五。 Q：今天是9月1日。 P Q ：今天是9月1日并且是星期五。,析取聯(lián)結(jié)詞,析取：兩命題P和Q的合取是一個(gè)復(fù)合命題，記作P Q。讀作“或 ”。 真值：當(dāng)且僅當(dāng)P，Q同時(shí)為假時(shí)， P Q為假，否則為真。 是二元運(yùn)算符。 析取式P Q表示的是一種相容性或。即允許P與Q同時(shí)為真。 例 P：今天是星期五。 Q：今天是9月1日。 P Q ：今天是9月1日或者是星期五。,析取聯(lián)結(jié)詞,與自然語(yǔ)言中的“或”意思有區(qū)別。 今天晚上我在家看電視或者去劇場(chǎng)看戲。（排斥或） 他學(xué)過(guò)英語(yǔ)或法語(yǔ)。（可兼或） 他昨天做了二十或三十道習(xí)題

6、。（原子命題）,數(shù)理邏輯中的“或”， P Q，是可兼或。 允許P與Q同時(shí)為真。,將下列命題符號(hào)化,李萍要么聰明，要么用功。 李萍雖然聰明，但是不用功。 李萍不但聰明而且用功。 李萍不是不聰明，而是不用功。 張帆和李萍是好朋友。,條件：當(dāng)且僅當(dāng)P的真值為T(mén)，Q的真值為F時(shí)，P Q的真值為F，否則P Q的真值為T(mén)。 P Q讀作“若P則Q”或“如果P，那么Q” 稱P為前件（前提），Q為后件（結(jié)論）。 P Q表示的邏輯關(guān)系是，Q是P的必要條件，或P是Q的充分條件。 例 P：今天是星期五。 Q：今天是9月1日。 QP：如果今天是9月1日那么是星期五。 注意：數(shù)理邏輯中P和Q不一定有內(nèi)在聯(lián)系，當(dāng)前件P為假

7、時(shí)， P Q為真。,等價(jià)聯(lián)結(jié)詞,雙條件：讀作“當(dāng)且僅當(dāng)”； 當(dāng)P和Q的真值相同時(shí)，P Q的真值為T(mén)，否則P Q的真值為F。 P與Q互為充分必要條件。 例 P：今天是星期五。 Q：今天是9月1日。 P Q ：今天是9月1日當(dāng)且僅當(dāng)今天是星期五。 不顧P與Q的因果關(guān)系，只要P與Q的值同真或同假， PQ的值就為真，否則為假。,命題演算的合式公式（wff），規(guī)定為 （1）單個(gè)命題變?cè)旧硎且粋€(gè)合式公式。 （2）如果A是合式公式，那么A是合式公式。 （3）如果A和B是合式公式，那么(AB),(AB),(AB)和(AB)都是合式公式。 （4）當(dāng)且僅當(dāng)能夠有限次地應(yīng)用(1),(2),(3)所得到的包含命題變

8、元，聯(lián)結(jié)詞和括號(hào)的符號(hào)串是合式公式。,命題公式與翻譯,命題公式?jīng)]有真假值，不是命題。 不是由命題變?cè)⒙?lián)結(jié)詞、括號(hào)組成的字符串都能成為命題公式。 自然語(yǔ)言中的聯(lián)結(jié)詞要根據(jù)具體含義翻譯。 符號(hào)化表示不是唯一的。 列出真值表來(lái)進(jìn)一步分析檢驗(yàn)。,符號(hào)化復(fù)合命題的步驟,1. 分析出各簡(jiǎn)單命題，將其符號(hào)化。 2. 使用合適的聯(lián)結(jié)詞，把簡(jiǎn)單命題逐個(gè)聯(lián)結(jié)起來(lái)。必要時(shí)可使用括號(hào)。括號(hào)一定要成對(duì)出現(xiàn)。 運(yùn)算優(yōu)先級(jí)： ；，；， ； 有括號(hào)先算括號(hào)， 相同聯(lián)結(jié)詞按從左到右順序計(jì)算,將下列命題符號(hào)化（翻譯）,小王是游泳冠軍或百米賽跑冠軍。 小王現(xiàn)在在宿舍或者在圖書(shū)館。 我騎自行車(chē)上班，除非天下雨。 如果天下雨，我就不

9、騎自行車(chē)上班。 如果我上街我就去書(shū)店看看，除非我很累。 張三或李四都會(huì)做這件事。 選修過(guò)“高等數(shù)學(xué)”或“微積分”的學(xué)生才可以選本課。 不經(jīng)一事不長(zhǎng)一智。,設(shè)p1, p2, pn是出現(xiàn)在命題公式A中的全部命題變?cè)op1, p2, pn各指定一個(gè)真值，稱為A的一個(gè)賦值或解釋。 若指定的一組值使得命題公式A的值為真，則稱這組值為A的成真賦值。若A的值為假，則稱這組值為A的成假賦值。 將命題公式A在所有賦值下取值情況匯列成表，就是命題公式的真值表。 n個(gè)命題變?cè)M成的命題公式共有2n種真值情況。,給定一命題公式，若無(wú)論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為T(mén)，則稱該命題公式為重言式或永真公式。 給定一

10、命題公式，若無(wú)論對(duì)分量作怎樣的指派，其對(duì)應(yīng)的真值永為F，則稱該命題公式為矛盾式或永假公式。 給定一命題公式，若至少存在一組指派，使得其對(duì)應(yīng)的真值為T(mén)，則稱該命題公式為可滿足式。 重言式一定是可滿足式，但反之不真。,命題公式的分類,第二章 命題邏輯等值驗(yàn)算,等價(jià)公式,判斷等價(jià)式的方法真值表法、等價(jià)代換法,命題定律,命題定律,命題定律： 其中的A、B、C為任意命題或命題公式； 用真值表驗(yàn)證。,例 判斷下列公式的類型,定義： PQ 不是對(duì)稱的。稱Q P為其逆換式， P Q 為其反換式， Q P為其逆反式。 等價(jià)式與蘊(yùn)含式之間的關(guān)系,不可兼析取 條件否定 與非 或非,最小聯(lián)結(jié)詞組,設(shè)S是一個(gè)聯(lián)結(jié)詞集合

11、，如果任一命題公式 都可以用僅含S中的聯(lián)結(jié)詞的命題公式等價(jià) 代換，則稱S為最小聯(lián)結(jié)詞組。,簡(jiǎn)單析取式：僅由有限個(gè)命題變?cè)蚱浞穸?構(gòu)成的析取式，稱為簡(jiǎn)單析取式。,簡(jiǎn)單合取式：僅由有限個(gè)命題變?cè)蚱浞穸?構(gòu)成的合取式，稱為簡(jiǎn)單合取式。,性質(zhì),一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng) 它同時(shí)含一個(gè)命題變?cè)捌浞穸ā?2. 一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng) 它同時(shí)含一個(gè)命題變?cè)捌浞穸ā?析取范式：僅由有限個(gè)簡(jiǎn)單合取式構(gòu)成的 析取式，稱為析取范式。,合取范式：僅由有限個(gè)簡(jiǎn)單析取式構(gòu)成的 合取式，稱為合取范式。,性質(zhì),一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng) 它的每個(gè)簡(jiǎn)單合取式都是矛盾式。,2. 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)

12、 它的每個(gè)簡(jiǎn)單析取式都是重言式 。,1 消去和，將公式中的聯(lián)結(jié)詞化歸成，及。 2 利用德摩根定律將向內(nèi)移。 3 利用分配律，結(jié)合律將公式歸約為合取范式或析取范式。 定理：任意命題公式都存在與之等值的析取范式和合取范式。 析取范式或合取范式不是唯一的。,主析取范式,設(shè)有n個(gè)命題變?cè)?，若在?jiǎn)單合取式中每個(gè)命題變?cè)c其否定有且僅有一個(gè)出現(xiàn)一次，則這樣的簡(jiǎn)單合取式稱為極小項(xiàng)。 一般地，n個(gè)命題變?cè)僧a(chǎn)生2n個(gè)極小項(xiàng)。 思考：若要使極小項(xiàng)的賦值為真，應(yīng)對(duì)各命題變?cè)鯓又概桑?主析取范式,如果公式A的析取范式中的簡(jiǎn)單合取式全是極小項(xiàng)，則稱該析取范式為A的主析取范式。 任何命題公式都有唯一的主析取范式。 主

13、析取范式可以判斷兩命題公式是否等價(jià)。 求主析取范式的方法：真值表法，等價(jià)公式法 真值表法：在真值表中，一個(gè)公式的真值為T(mén)的指派所對(duì)應(yīng)的的極小項(xiàng)的析取，即為此公式的主析取范式。,推演主析取范式的步驟,化歸為析取范式 除去析取范式中所有永假的析取項(xiàng)。 將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變?cè)喜ⅰ?對(duì)合取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添?P P)式。然后應(yīng)用分配律展開(kāi)公式。,極大項(xiàng),設(shè)有n個(gè)命題變?cè)?，若在?jiǎn)單析取式中每個(gè)命題變?cè)c其否定有且僅有一個(gè)出現(xiàn)一次，則這樣的簡(jiǎn)單析取式稱為極大項(xiàng)。 一般地，n個(gè)命題變?cè)僧a(chǎn)生2n個(gè)極大項(xiàng)。 思考：若要使極大項(xiàng)的賦值為假，應(yīng)對(duì)各命題變?cè)鯓又概桑?主合取范式,如

14、果公式A的合取范式中的簡(jiǎn)單析取式全是極大項(xiàng)，則稱該合取范式為A的主合取范式。 任何命題公式都有唯一的主合取范式。 主合取范式可以判斷兩命題公式是否等價(jià)。 求合析取范式的方法：真值表法，等價(jià)公式法 真值表法：在真值表中，一個(gè)公式的真值為F的指派所對(duì)應(yīng)的的極大項(xiàng)的合取，即為此公式的主合取范式。,推演主合取范式的步驟,化歸為合取范式 除去合取范式中所有永真的合取項(xiàng)。 合并相同的析取項(xiàng)和相同的變?cè)?對(duì)析取項(xiàng)補(bǔ)入沒(méi)有出現(xiàn)的命題變?cè)?，即添?P P)式。然后應(yīng)用分配律展開(kāi)公式。 按字母順序排列,第三章 推理理論,推理理論,推理是從前提推出結(jié)論的思維過(guò)程。 前提是指已知的命題公式，結(jié)論是指從前提出發(fā)應(yīng)用推

15、理規(guī)則推出的命題公式。,推理的形式結(jié)構(gòu),推廣到n個(gè)前提的情況。,推理的形式結(jié)構(gòu),注,推理是否正確與諸前提的排列次序無(wú)關(guān)。 推理正確不能保證結(jié)論一定正確，因?yàn)榍疤峥赡苁清e(cuò)誤的。 只有在推理正確且前提也正確時(shí)，才能保證結(jié)論正確。 推理論證方法：真值表法 直接證法（等值演算法、主析取范式法） 間接證法（附加前提法、歸謬法）,真值表法,例題：判斷下列推理是否正確：,一份統(tǒng)計(jì)表格的錯(cuò)誤或者是由于材料不可靠， 或者是由于計(jì)算有錯(cuò)誤；這份統(tǒng)計(jì)表格的錯(cuò)誤 不是由于材料不可靠。所以這份統(tǒng)計(jì)表格計(jì)算 有錯(cuò)誤。,2. 如果我上街，我一定去書(shū)店；我沒(méi)上街。 所以我沒(méi)去書(shū)店,推理理論直接證法,直接證法就是由一組前提，根

16、據(jù)已知的等價(jià)公式，推演得到有效的結(jié)論。 等值演算法； 例：下午馬芳或者去看電影，或者去游泳。她沒(méi)去看電影，所以她去游泳了。 主析取范式法； 例：若下午氣溫超過(guò)30度，則馬芳必去游泳。若她去游泳，她就不去看電影了。所以若馬芳沒(méi)去看電影，下午氣溫必超過(guò)30度。,推理理論間接證法,從假設(shè)前提出發(fā)，使用一些公認(rèn)的規(guī)則，得到另外的命題，最終形成結(jié)論，這一過(guò)程就是論證。 證明是一個(gè)描述推理過(guò)程的命題公式序列，其中的每個(gè)公式或者是已知前提，或者是由前面的公式應(yīng)用推理規(guī)則得到的結(jié)論。 P規(guī)則（前提引入規(guī)則） 在證明的任何步驟都可以引入前提。 T規(guī)則（結(jié)論引入規(guī)則） 在證明的任何步驟所得到的結(jié)論都可以作為后繼證

17、明的前提 置換規(guī)則 在證明的任何步驟，命題公式都可以用等值的公式置換。,推理規(guī)則,假言推理規(guī)則,附加規(guī)則,化簡(jiǎn)規(guī)則,拒取式規(guī)則,假言三段論規(guī)則,推理規(guī)則,構(gòu)造性推理規(guī)則,合取引入規(guī)則,析取三段論規(guī)則,破壞性推理規(guī)則,推理理論間接證法,附加前提證明法,間接證法附加前提證明法,即將原來(lái)結(jié)論中的前件R變成附加前提引入。,例：如果小張和小王去看電影，則小李也去看電影,間接證法歸謬法,第四章 謂詞邏輯（一階邏輯）,命題邏輯的局限性,蘇格拉底三段論： 凡是人都要死的. 蘇格拉底是人. 所以蘇格拉底是要死的. 在命題邏輯中，只能用p、q、r表示以上3個(gè)命題， 上述推理可表成 (pq)r,57,這不是重言式，

18、推理不正確。,命題邏輯局限性：沒(méi)有表達(dá)出總體與個(gè)體之間的聯(lián)系。,58,基本概念個(gè)體詞、謂詞、量詞,個(gè)體詞（個(gè)體）: 所研究對(duì)象中可以獨(dú)立存在的具體或抽象的客體。 個(gè)體詞一般是原子命題中的主語(yǔ)或賓語(yǔ)。 個(gè)體常項(xiàng)：具體的事物，用a, b, c表示 個(gè)體變項(xiàng)：抽象的事物，用x, y, z表示 個(gè)體域（論域）: 個(gè)體變項(xiàng)的取值范圍 有限個(gè)體域，如a, b, c, 1, 2 無(wú)限個(gè)體域，如N, Z, R, 全總個(gè)體域: 宇宙間一切事物組成 若沒(méi)有特別說(shuō)明，約定個(gè)體域是全總個(gè)體域。,基本概念 (續(xù)),謂詞: 表示個(gè)體詞性質(zhì)或相互之間關(guān)系的詞 謂詞一般是原子命題中的謂語(yǔ)。 謂詞常項(xiàng)：F(a)：a是人 謂詞變

19、項(xiàng)：F(x)：x具有性質(zhì)F 含有n個(gè)個(gè)體變?cè)闹^詞，稱為n元謂詞。,也稱為n元命題函數(shù)。,其實(shí)質(zhì)是：以個(gè)體域 為定義域，以0,1為值域的n元函數(shù)。,一元謂詞: 表示事物的性質(zhì) 如 F(x)：x是偶數(shù)， 多元謂詞(n元謂詞, n2): 表示事物之間的關(guān)系 如 L(x,y)：xy， 0元謂詞: 不含個(gè)體變項(xiàng)的謂詞。 如 F(2), L(a,2), 命題都可以表示成0元謂詞.命題是特殊的謂詞。,例 分析語(yǔ)句中的個(gè)體詞和謂詞,2是偶數(shù)。x是偶數(shù)。 2是個(gè)體常元， x是個(gè)體變?cè)?“是偶數(shù)”是謂詞，表示個(gè)體的性質(zhì)。 2整除3. x整除y. 2，3是個(gè)體常元， x， y是個(gè)體變?cè)?“整除”是謂詞，表示個(gè)

20、體之間的關(guān)系。,62,例 用0元謂詞將命題符號(hào)化,要求：先將它們?cè)诿}邏輯中符號(hào)化，再在一階 邏輯中符號(hào)化 (1) 墨西哥位于南美洲,在命題邏輯中, 設(shè) p: 墨西哥位于南美洲 符號(hào)化為 p,在一階邏輯中, 設(shè)a：墨西哥，b：南美洲，F(xiàn)(x,y)：x位于y, 符號(hào)化為F(a,b),63,例(續(xù)),（2）只有2是素?cái)?shù)，4才是素?cái)?shù)。,在一階邏輯中, 設(shè)F(x): x是素?cái)?shù), F(x)是一元謂詞 符號(hào)化為F(4) F(2),在命題邏輯中, 設(shè) p：23，q：3y，G(x,y)：x3，則3y xy(F(x)G(y)L(x,y),(2) 令F(x): x是無(wú)理數(shù), G(y): y是有理數(shù), L(x,y)

21、：xy xy(F(x)G(y)L(x,y),(3).沒(méi)有人登上過(guò)木星。 (4)在美國(guó)留學(xué)的學(xué)生未必都是亞洲人。,72,翻譯中應(yīng)注意的問(wèn)題,1元謂詞與多元謂詞的區(qū)分； 若無(wú)特別要求,應(yīng)使用全總個(gè)體域,引入特性謂詞； 量詞順序一般不能隨便顛倒； 命題符號(hào)化形式不唯一； 兩個(gè)基本形式x (F(x)G(x)和 x (F(x)G(x)的使用； 否定的表示，如 “沒(méi)有不呼吸的人”等同于“所有的人都呼吸” “不是所有的人都喜歡吃糖”等同于“存在不喜歡吃糖的人”,個(gè)體變項(xiàng)的自由出現(xiàn)與約束出現(xiàn),定義 在公式xA和xA中，稱x為指導(dǎo)變?cè)?，A為相 應(yīng)量詞的轄域. 在x和x的轄域中，x的所有出現(xiàn)都 稱為約束變?cè)?，A中

22、不是約束出現(xiàn)的其他變項(xiàng)均稱 為是自由變?cè)? 例如, 在公式 x(F(x,y)G(x,z) 中, A=(F(x,y)G(x,z)為x的轄域， x為指導(dǎo)變?cè)? A中x的兩次出現(xiàn)均為約束出現(xiàn)， y與z均為自由出現(xiàn). 閉式: 不含自由出現(xiàn)的個(gè)體變項(xiàng)的公式.,例,指出下列各公式中的指導(dǎo)變?cè)⒏髁吭~的 轄域、自由變?cè)凹s束變?cè)?兩個(gè)規(guī)則,換名規(guī)則 在謂詞公式中，將某量詞轄域中出現(xiàn)的某個(gè)約束變?cè)约皩?duì)應(yīng)的指導(dǎo)變?cè)?，改成本轄域中未曾出現(xiàn)過(guò)的個(gè)體變?cè)?hào)，公式中的其余部分不變，謂詞公式的等價(jià)性不變。,兩個(gè)規(guī)則,代替規(guī)則 在謂詞公式中，將某個(gè)自由變?cè)乃谐霈F(xiàn)用未曾出現(xiàn)過(guò)的某個(gè)個(gè)體變?cè)?hào)代替，公式的等價(jià)性不變。

23、,謂詞公式的賦值,在謂詞公式中常包含命題變?cè)涂腕w變?cè)?當(dāng)客體變?cè)纱_定的客體所取代，命題變?cè)纱_定的命題所取代，就稱作對(duì)謂詞公式賦值。 一個(gè)謂詞公式經(jīng)過(guò)賦值后，就稱為具有確定真值的命題。,公式的分類,永真式(邏輯有效式):在任何賦值下為真命題 矛盾式(永假式):在任何賦值下為假命題 可滿足式：至少在一種賦值下為真 說(shuō)明： 永真式為可滿足式，但反之不真 在命題邏輯中可以用真值表法判定公式類型 在一階邏輯中任給一謂詞公式其類型不一定能判定,79,代換,定義 設(shè)A0是含命題變項(xiàng)p1, p2, ,pn的命題公式，A1,A2,An是n個(gè)謂詞公式，用Ai處處代替A0中的pi (1in) ，所得公式A稱

24、為A0的代換實(shí)例. 如 F(x)G(x), xF(x)yG(y)是pq的代換實(shí)例 定理 重言式的代換實(shí)例都是永真式，矛盾式的代換實(shí)例都是矛盾式.,例：判斷下列公式的類型,可滿足式,永真式,矛盾式,81,2.3 一階邏輯等值式與前束范式,等值式 基本等值式 量詞否定等值式 量詞轄域收縮與擴(kuò)張等值式 量詞分配等值式 前束范式,等值式與基本等值式,基本等值式: 命題邏輯中16組基本等值式的代換實(shí)例 如，xF(x)yG(y) xF(x)yG(y) (xF(x)yG(y) xF(x)yG(y) 等 消去量詞等值式 設(shè)D=a1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(

25、a2)A(an),定義 若AB為邏輯有效式，則稱A與B是等值的， 記作 AB，并稱AB為等值式.,83,基本等值式(續(xù)),量詞轄域收縮與擴(kuò)張等值式 設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的出現(xiàn) 關(guān)于全稱量詞的： x(A(x)B)xA(x)B x(A(x)B)xA(x)B,關(guān)于存在量詞的: x(A(x)B)xA(x)B x(A(x)B)xA(x)B,84,基本的等值式(續(xù)),量詞否定等值式 設(shè)A(x)是含x自由出現(xiàn)的公式 xA(x) x A(x) xA(x)x A(x) 量詞分配等值式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 注意：對(duì)無(wú)分配律，對(duì)無(wú)分配律, 即 x(A(x)B(x) xA(x)xB(