逻辑推理与永真公式的1省公开课一等奖全国示范课微课金奖课件

第三章逻辑推理与永真公式公理系统3.1逻辑推理基本思想3.2逻辑推理公理系统

习题及参考答案4/13/20241第1页§3.1逻辑推理基本思想在数学中和其它自然科学中，经常要考虑从一些前提A1，A2…An能够推导出什么结论。比如从分子学、原子学，能够得到什么结论等等。我们普通地要对“假设”内容作深入分析，并研究其间关系，从而得到结论。在数学及日常生活中，我们经常要决定一个陈说是否能够从另一个陈说推出，这就是“逻辑推理”问题，在给定这个概念形式定义之前，我们先举一些例子进行说明。4/13/20242第2页比如：假如天气干旱则粮食欠收。又设；当粮食欠收时大多数人是不幸。再设；天气干旱。那么能够指出大多数人是不幸。

解：为了指出上述结论，现将陈说句表示以下：P：表示天气干旱，S：表示粮食丰收，U：表示大多数人是幸运。例子中有四个陈说句，它们是：假如天气干旱，则粮食欠收；假如粮食欠收，则大多数人是不幸；天气是干旱；大多数人是不幸；将它们符号化成为：P→┐S┐S→┐UP┐U4/13/20243第3页现在我们指出当P→┐S，┐S→┐U，P均为真时┐U为真，即（P→┐S）∧（┐S→┐U）∧P为真时，┐U为真，我们将其化为范式：（（P→┐S）∧（┐S→┐U）∧P）=（P∧（┐P∨┐S）∧（S∨┐U）依据等价公式=（（（P∧┐P）∨（P∨┐S））∧（S∨┐U））依据分配律及结合律=（（F∨（P∨┐S））∧（S∨┐U））=（P∧┐S）∧（S∨┐U）=（P∧┐S∧S）∨（P∧┐S∧┐U）=P∧┐S∧┐U4/13/20244第4页

故有以下逻辑结论，（（P→┐S）∧（┐S→┐U）∧P）为真，那么（P∧┐S∧┐U）为真，而（P∧┐S∧┐U）为真时，必须P，┐S，┐U均为真，所以我们得到U是假，此时，逻辑上称┐U是（P→S），（S→┐U），与P逻辑结果，其形式定义以下：4/13/20245第5页

定义：设A和C是两个命题公式，当且仅当A→C为一重言式，即AC，称C是A有效结论。或C可由A逻辑地推出。这个定义能够推广到有n个前提情况

定义：设有命题公式序列A1…An及命题公式，假如对任何使A1…An为成真指派，B也为真，则称B为A1…An逻辑推论，或称B是A1…An一个逻辑结果，记为A1…AnB，其中A1…An叫做B前提或假设。4/13/20246第6页判别有效结论过程就是论证过程，论证方法千变万化，但基本方法只有三种：即真值表法、直接证法和间接证法。下面分别举例说明：（1）真值表法比如：假如张老师来了，这个问题能够得到解答。假如李老师来了，这个问题也能够得到解答，总之，张老师或李老师来了这个问题都能够得到解答。

解：设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）直接证实法

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

证实：┐（┐P∧（┐Q∨┐R））=┐（┐P∧┐（Q∧R））

依据┐（P∧Q）=┐Q∨┐P=P∨（Q∧R）同上=（P∨Q）∧（P∨R）

依据P∨（Q∧R）=（P∨Q）∧（P∨R）又例：P→Q=┐Q→┐P

证：P→Q=┐P∨Q依据P→Q=┐P∨Q=┐P∨┐┐Q依据┐┐P=P=┐┐Q∨┐P依据P∨Q=Q∨P=┐Q→┐P依据P→Q=┐P∨Q4/13/202410第10页

在这个证实过程中首先需要要用到一些已知等价公式（已知重言式）。由这一点我们可知，要证实一个未知重言式必需要用到些已知重言式，因而，要证实命题演算中全部重言式在命题演算中必需要有一些基本，不需推导重言式，由这些重言式出发可推得其余重言式。这里（1）—（39）视为基本重言式。这类重言式也可称为公理。其次，在证实过程中我们发觉，仅仅使用一些已知重言式是不够。下面所用到代入与替换方法均是推理过程中所需要使用一些规则。这种规则我们称为推理规则。在命题演算中重言式推理过程中需要一些基本重言式及一些基本推理规则，由它们而可推得其余重言式。4/13/202411第11页§3.2逻辑推理公理系统所谓命题演算永真公理系统就是给出若干条命题演算永真公式（称为公理），再给出若干条由永真公式推出永真公式规则（称为推理规则），使得一切永真公式均能由这些公理出发，利用这些推理规则一步步地推出。现在问题是这么，永真公式和推理规则能不能找到回答是必定，下面将给出命题演算永真公式公理系统，首先，我们对普通公理系统作一简单介绍。每一公理系统都包含两大部分，第一部分是组成部分，它是公理系统概念部分，用以指明该系统所讨论对象，即：指明该系统中项和公式。第二部分是推理部分，用以指明什么样公式被认为是该系统中定理。4/13/202412第12页1.组成部分由§2.2节中所给出定义，即：命题演算可按以下规则生成，该定义共分为：定义：命题演算公式可按下以下规则生成：(1)变元均是公式。(2)假如P是公式则┐P也是公式。(3)假如P，Q是公式则（P∧Q），（P∨Q），（P→Q），（P←→Q）是公式。(4)有限步使用上述法则（规则）所得到结果均是公式。(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页二.推理规则本系统中只有一条推理规则，称为分离规则我们（简记为“分”）比如：A→B，A├B（读为：对A→B，A实施分离规则可得B）4/13/202416第16页三.定理（1）公理为定理；（2）假如A→B，A为定理，则由它们实施分离规则所得到B也是定理。（3）定理仅限于此。在本系统中我们一定要注意以下几点：

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

第二.要证实一公式是定理，必须给出它证实过程？设有一系列公式A1，A2…An，假如每一个Ai（1≤i≤n）（1）或者是公理之一；（2）或者是由前面Ah，Ak，（h，k,<I）实施分离规则而得；（3）An即B则说公式序列A1，A2…An是定理B永真证实过程。B便是一个定理，各个A叫做在B证实过程中间结果。普通除要求给出证实过程外还要求同时给出证实依据，所谓证实依据是：当某个Ai是公理时，便在它旁边注明“分AhAk”按上面定义要求，永真证实过程依据都是详尽。4/13/202417第17页

举例：证实（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）即为所要证实定理。4/13/202418第18页

第三.即使本系统只用一条分离规则就足够了，不过对于今后推导是不够方便，为了方便起见，我们将从这条基本规则出发。怎样引出规则呢？假设我们已证实了一条定理A→B，编号为（a），又证实了一条定理A，编号为（b），由此可得分（a）（b）=（c）B这里分（a）（b）称为B证实依据，（c）称为编号，“B”这条定理应看作对（a）（b）实施分离规则结果，即：分（a）规则A├B也就是说，每逢我们有一条定理（a）：A→B，我们便有一条对应分（a）规则A├B。即由（a）前件A能够得出（a）后件B。4/13/202419第19页同理，假定我们证实了一条定理A→（B→C）编号为（又假定我们证实了两条定理：（b）：A，（c）：B即使可作以下推理分（a）（b）=（d）B→C分（d）（C）=（e）C，将（d）代入得分分（a）（b）（c）=（e）C这里我们能够把C看作两次实施分离规则结果，即分分（a）：A，B├C同理，假如我们有定理（a）：A→（B→（C→D））则我们可有以下规则：分分分（a）规则：A，B，C├D即由（a）三个前件A，B，C可得出（a）后件D。4/13/202420第20页当然这里能够推广到普通情况，这里就不去详述。我们熟悉这种导出规则，对今后学习将有很大帮助。为了更深入讨论我们再给出一些推理规则，这些规则可用真值表方法证实这些重言式，这些也均称为规则。

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