邏輯推理與永真公式的1省公開課一等獎全國示范課微課金獎?wù)n件

第三章邏輯推理與永真公式公理系統(tǒng)3.1邏輯推理基本思想3.2邏輯推理公理系統(tǒng)

習(xí)題及參考答案4/13/20241第1頁§3.1邏輯推理基本思想在數(shù)學(xué)中和其它自然科學(xué)中，經(jīng)常要考慮從一些前提A1，A2…An能夠推導(dǎo)出什么結(jié)論。比如從分子學(xué)、原子學(xué)，能夠得到什么結(jié)論等等。我們普通地要對“假設(shè)”內(nèi)容作深入分析，并研究其間關(guān)系，從而得到結(jié)論。在數(shù)學(xué)及日常生活中，我們經(jīng)常要決定一個陳說是否能夠從另一個陳說推出，這就是“邏輯推理”問題，在給定這個概念形式定義之前，我們先舉一些例子進(jìn)行說明。4/13/20242第2頁比如：假如天氣干旱則糧食欠收。又設(shè)；當(dāng)糧食欠收時大多數(shù)人是不幸。再設(shè)；天氣干旱。那么能夠指出大多數(shù)人是不幸。

解：為了指出上述結(jié)論，現(xiàn)將陳說句表示以下：P：表示天氣干旱，S：表示糧食豐收，U：表示大多數(shù)人是幸運(yùn)。例子中有四個陳說句，它們是：假如天氣干旱，則糧食欠收；假如糧食欠收，則大多數(shù)人是不幸；天氣是干旱；大多數(shù)人是不幸；將它們符號化成為：P→┐S┐S→┐UP┐U4/13/20243第3頁現(xiàn)在我們指出當(dāng)P→┐S，┐S→┐U，P均為真時┐U為真，即（P→┐S）∧（┐S→┐U）∧P為真時，┐U為真，我們將其化為范式：（（P→┐S）∧（┐S→┐U）∧P）=（P∧（┐P∨┐S）∧（S∨┐U）依據(jù)等價公式=（（（P∧┐P）∨（P∨┐S））∧（S∨┐U））依據(jù)分配律及結(jié)合律=（（F∨（P∨┐S））∧（S∨┐U））=（P∧┐S）∧（S∨┐U）=（P∧┐S∧S）∨（P∧┐S∧┐U）=P∧┐S∧┐U4/13/20244第4頁

故有以下邏輯結(jié)論，（（P→┐S）∧（┐S→┐U）∧P）為真，那么（P∧┐S∧┐U）為真，而（P∧┐S∧┐U）為真時，必須P，┐S，┐U均為真，所以我們得到U是假，此時，邏輯上稱┐U是（P→S），（S→┐U），與P邏輯結(jié)果，其形式定義以下：4/13/20245第5頁

定義：設(shè)A和C是兩個命題公式，當(dāng)且僅當(dāng)A→C為一重言式，即AC，稱C是A有效結(jié)論。或C可由A邏輯地推出。這個定義能夠推廣到有n個前提情況

定義：設(shè)有命題公式序列A1…An及命題公式，假如對任何使A1…An為成真指派，B也為真，則稱B為A1…An邏輯推論，或稱B是A1…An一個邏輯結(jié)果，記為A1…AnB，其中A1…An叫做B前提或假設(shè)。4/13/20246第6頁判別有效結(jié)論過程就是論證過程，論證方法千變?nèi)f化，但基本方法只有三種：即真值表法、直接證法和間接證法。下面分別舉例說明：（1）真值表法比如：假如張老師來了，這個問題能夠得到解答。假如李老師來了，這個問題也能夠得到解答，總之，張老師或李老師來了這個問題都能夠得到解答。

解：設(shè)P：張老師來了。Q：李老師來了。R：這個問題能夠得到解答。上述語句能夠表述命題以下：（P→R）∧（Q→R）∧（P∨Q）R4/13/20247第7頁列出真值表以下：PQRP→RQ→RP∨QTTTTTTTTFFFTTFTTTTTFFFTTFTTTTTFTFTFTFFTTTFFFFTTF4/13/20248第8頁從真值表看到，P→R、Q→R、P∨Q真值都為T情況為第一行，第三行和第五行，而在這三行中R真值均為T。故：（P→R）∧（Q→R）∧（P∨Q）R4/13/20249第9頁（2）直接證實(shí)法

例：┐（┐P∧（┐Q∨┐R））=（P∨Q）∧（P∨Q）

證實(shí)：┐（┐P∧（┐Q∨┐R））=┐（┐P∧┐（Q∧R））

依據(jù)┐（P∧Q）=┐Q∨┐P=P∨（Q∧R）同上=（P∨Q）∧（P∨R）

依據(jù)P∨（Q∧R）=（P∨Q）∧（P∨R）又例：P→Q=┐Q→┐P

證：P→Q=┐P∨Q依據(jù)P→Q=┐P∨Q=┐P∨┐┐Q依據(jù)┐┐P=P=┐┐Q∨┐P依據(jù)P∨Q=Q∨P=┐Q→┐P依據(jù)P→Q=┐P∨Q4/13/202410第10頁

在這個證實(shí)過程中首先需要要用到一些已知等價公式（已知重言式）。由這一點(diǎn)我們可知，要證實(shí)一個未知重言式必需要用到些已知重言式，因而，要證實(shí)命題演算中全部重言式在命題演算中必需要有一些基本，不需推導(dǎo)重言式，由這些重言式出發(fā)可推得其余重言式。這里（1）—（39）視為基本重言式。這類重言式也可稱為公理。其次，在證實(shí)過程中我們發(fā)覺，僅僅使用一些已知重言式是不夠。下面所用到代入與替換方法均是推理過程中所需要使用一些規(guī)則。這種規(guī)則我們稱為推理規(guī)則。在命題演算中重言式推理過程中需要一些基本重言式及一些基本推理規(guī)則，由它們而可推得其余重言式。4/13/202411第11頁§3.2邏輯推理公理系統(tǒng)所謂命題演算永真公理系統(tǒng)就是給出若干條命題演算永真公式（稱為公理），再給出若干條由永真公式推出永真公式規(guī)則（稱為推理規(guī)則），使得一切永真公式均能由這些公理出發(fā)，利用這些推理規(guī)則一步步地推出。現(xiàn)在問題是這么，永真公式和推理規(guī)則能不能找到回答是必定，下面將給出命題演算永真公式公理系統(tǒng)，首先，我們對普通公理系統(tǒng)作一簡單介紹。每一公理系統(tǒng)都包含兩大部分，第一部分是組成部分，它是公理系統(tǒng)概念部分，用以指明該系統(tǒng)所討論對象，即：指明該系統(tǒng)中項(xiàng)和公式。第二部分是推理部分，用以指明什么樣公式被認(rèn)為是該系統(tǒng)中定理。4/13/202412第12頁1.組成部分由§2.2節(jié)中所給出定義，即：命題演算可按以下規(guī)則生成，該定義共分為：定義：命題演算公式可按下以下規(guī)則生成：(1)變元均是公式。(2)假如P是公式則┐P也是公式。(3)假如P，Q是公式則（P∧Q），（P∨Q），（P→Q），（P←→Q）是公式。(4)有限步使用上述法則（規(guī)則）所得到結(jié)果均是公式。(5)公式僅限于此。4/13/202413第13頁2.推理部分公理下面15種公式模式均為公理，其中A，B，C為任何公式。（40）A→A（41）（A→（B→C））→（B→（A→C））（42）（A→B）→（（B→C）→A→C））（43）（A→（A→B））→（A→B）（44）（AB）→（A→B）4/13/202414第14頁（45）（AB）→（B→A）（46）（A→B）→（（B→A）→（A≡B））（47）（A∧B）→A（48）（A∧B）→B（49）A→（B→（A∧B））（50）A→（A∨B）（51）B→（A∨B）（52）（B→A）→（（C→A）→（B∨C）→A））（53）（A→┐B）→（B→┐A）（54）┐┐A→A4/13/202415第15頁二.推理規(guī)則本系統(tǒng)中只有一條推理規(guī)則，稱為分離規(guī)則我們（簡記為“分”）比如：A→B，A├B（讀為：對A→B，A實(shí)施分離規(guī)則可得B）4/13/202416第16頁三.定理（1）公理為定理；（2）假如A→B，A為定理，則由它們實(shí)施分離規(guī)則所得到B也是定理。（3）定理僅限于此。在本系統(tǒng)中我們一定要注意以下幾點(diǎn)：

第一.（40）—（54）中任何一條，均是無窮條公式集合。比如：A→A，B→B，（A→B）→（A→B），（P∧Q）→（P∧Q）等等均是公理（40）。

第二.要證實(shí)一公式是定理，必須給出它證實(shí)過程？設(shè)有一系列公式A1，A2…An，假如每一個Ai（1≤i≤n）（1）或者是公理之一；（2）或者是由前面Ah，Ak，（h，k,<I）實(shí)施分離規(guī)則而得；（3）An即B則說公式序列A1，A2…An是定理B永真證實(shí)過程。B便是一個定理，各個A叫做在B證實(shí)過程中間結(jié)果。普通除要求給出證實(shí)過程外還要求同時給出證實(shí)依據(jù)，所謂證實(shí)依據(jù)是：當(dāng)某個Ai是公理時，便在它旁邊注明“分AhAk”按上面定義要求，永真證實(shí)過程依據(jù)都是詳盡。4/13/202417第17頁

舉例：證實(shí)（A∨B）→（B∨A）為定理

證公理（50）=（1）：B→（B∨A）

公理（51）=（2）：A→（B∨A）公理（52）=（3）：（A→（B∨A））→（（B→（B∨A））→（（A∨B）→（B∨A）））

分（3）（2）=（4）：（B→（B∨A））→（（A∨B）→（B∨A））

分（4）（1）=（5）：（A∨B）→（B∨A）

（5）即為所要證實(shí)定理。4/13/202418第18頁

第三.即使本系統(tǒng)只用一條分離規(guī)則就足夠了，不過對于今后推導(dǎo)是不夠方便，為了方便起見，我們將從這條基本規(guī)則出發(fā)。怎樣引出規(guī)則呢？假設(shè)我們已證實(shí)了一條定理A→B，編號為（a），又證實(shí)了一條定理A，編號為（b），由此可得分（a）（b）=（c）B這里分（a）（b）稱為B證實(shí)依據(jù)，（c）稱為編號，“B”這條定理應(yīng)看作對（a）（b）實(shí)施分離規(guī)則結(jié)果，即：分（a）規(guī)則A├B也就是說，每逢我們有一條定理（a）：A→B，我們便有一條對應(yīng)分（a）規(guī)則A├B。即由（a）前件A能夠得出（a）后件B。4/13/202419第19頁同理，假定我們證實(shí)了一條定理A→（B→C）編號為（又假定我們證實(shí)了兩條定理：（b）：A，（c）：B即使可作以下推理分（a）（b）=（d）B→C分（d）（C）=（e）C，將（d）代入得分分（a）（b）（c）=（e）C這里我們能夠把C看作兩次實(shí)施分離規(guī)則結(jié)果，即分分（a）：A，B├C同理，假如我們有定理（a）：A→（B→（C→D））則我們可有以下規(guī)則：分分分（a）規(guī)則：A，B，C├D即由（a）三個前件A，B，C可得出（a）后件D。4/13/202420第20頁當(dāng)然這里能夠推廣到普通情況，這里就不去詳述。我們熟悉這種導(dǎo)出規(guī)則，對今后學(xué)習(xí)將有很大幫助。為了更深入討論我們再給出一些推理規(guī)則，這些規(guī)則可用真值表方法證實(shí)這些重言式，這些也均稱為規(guī)則。

（55）A∧B├A（56）A