逻辑推理与永真公式的.ppt

2019/11/10,1,第三章 逻辑推理与永真公 式的公理系统,3.1 逻辑推理的基本思想 3.2 逻辑推理的公理系统 习题及参考答案,2019/11/10,2,3.1 逻辑推理的基本思想 在数学中和其他自然科学中，经常要考虑从某些前提A1，A2An能够推导出什么结论。 例如从分子学、原子学，能够得到什么结论等等。我们一般地要对“假设”的内容作深入分析，并研究其间的关系，从而得到结论。在数学及日常生活中，我们常常要决定一个陈述是否可以从另一个陈述推出，这就是“逻辑推理”问题，在给定这个概念形式定义之前，我们先举一些例子进行说明。,2019/11/10,3,例如：如果天气干旱则粮食欠收。 又设；当粮食欠收时大多数人是不幸的。 再设；天气干旱。 那么可以指出大多数人是不幸的。 解：为了指出上述结论，现将陈述句表示如下： P：表示天气干旱， S：表示粮食丰收， U：表示大多数人是幸运的。 例子中有四个陈述句，它们是： 如果天气干旱，则粮食欠收； 如果粮食 欠收，则大多数人是不幸的； 天气是干旱； 大多数人是不幸的； 将它们符号化成为： P S S U P U,2019/11/10,4,现在我们指出当PS，SU，P均为真时U为真，即（PS）（SU）P为真时，U为真，我们将其化为范式： （PS）（SU）P） =（P（PS）（SU） 根据等价公式 =（PP）（PS）（SU） 根据分配律及结合律 =（F（PS）（SU） =（PS）（SU） =（PSS）（PSU） = PSU,2019/11/10,5,故有如下逻辑结论，（PS）（SU）P）为真，那么（PSU）为真，而（PSU）为真时，必须P，S，U均为真，因此我们得到U是假的，此时，逻辑上称U是（PS），（SU），与P的逻辑结果，其形式定义如下：,2019/11/10,6,定义：设A和C是两个命题公式，当且仅当 AC为一重言式，即A C，称C是A的有效结论。或C可由A逻辑地推出。 这个定义可以推广到有n个前提的情况,定义：设有命题公式序列A1An及命题公式，如果对任何使A1An为成真的指派，B也为真，则称B为A1An的逻辑推论，或称B是A1An的一个逻辑结果，记为A1An B，其中A1An叫做B的前提或假设。,2019/11/10,7,判别有效结论的过程就是论证过程，论证的方法千变万化，但基本方法只有三种：即真值表法、直接证法和间接证法。 下面分别举例说明： （1）真值表法 例如：如果张老师来了，这个问题可以得到解答。 如果李老师来了，这个问题也可以得到解答，总之，张老师或李老师来了这个问题都可以得到解答。 解：设P：张老师来了。 Q：李老师来了。 R：这个问题可以得到解答。 上述语句可以表述命题如下： （PR）（QR）（PQ） R,2019/11/10,8,列出真值表如下：,2019/11/10,9,从真值表看到，PR、QR、PQ的真值都为T的情况为第一行，第三行和第五行，而在这三行中R的真值均为T。故： （ PR）（QR）（PQ） R,2019/11/10,10,（2）直接证明法 例：（P（QR）=（PQ）（PQ） 证明：（P（QR） =（P（QR） 根据（PQ）=QP = P（QR）同上 =（PQ）（PR） 根据P（QR）=（PQ）（PR） 又例： PQ=QP 证：PQ=PQ 根据PQ=PQ =PQ 根据P=P =QP 根据PQ= QP =QP 根据PQ=PQ,2019/11/10,11,在这个证明过程中首先需要要用到一些已知的等价公式（已知的重言式）。由这一点我们可知，要证明一个未知的重言式必需要用到些已知的重言式，因而，要证明命题演算中所有重言式在命题演算中必需要有一些基本的，不需推导的重言式，由这些重言式出发可推得其余重言式。这里（1）（39）视为基本重言式。这类重言式也可称为公理。其次，在证明过程中我们发现，仅仅使用一些已知的重言式是不够的。 下面所用到的代入与替换的方法均是推理过程中所需要使用的一些规则。这种规则我们称为推理规则。在命题演算中重言式的推理过程中需要一些基本的重言式及一些基本推理规则，由它们而可推得其余重言式。,2019/11/10,12,3.2 逻辑推理的公理系统 所谓命题演算永真的公理系统就是给出若干条命题演算永真公式（称为公理），再给出若干条由永真公式推出永真公式的规则（称为推理规则），使得一切永真公式均能由这些公理出发，利用这些推理规则一步步地推出。 现在问题是这样的，永真公式和推理规则能不能找到回答是肯定的，下面将给出命题演算永真公式公理系统，首先，我们对一般公理系统作一简单介绍。每一公理系统都包括两大部分，第一部分是组成部分，它是公理系统的概念部分，用以指明该系统所讨论的对象，即：指明该系统中的项和公式。第二部分是推理部分，用以指明什么样的公式被认为是该系统中的定理。,2019/11/10,13,1.组成部分 由2.2节中所给出的定义，即：命题演算可按如下规则生成，该定义共分为：定义：命题演算公式可按下如下规则生成： (1)变元均是公式。 (2)如果P是公式则P也是公式。 (3)如果P，Q是公式则（PQ），（PQ）， （PQ），（P Q）是公式。 (4)有限步使用上述法则（规则）所得到的结果均是公式。 (5)公式仅限于此。,2019/11/10,14,2.推理部分 公理 下面15种公式模式均为公理，其中A，B，C为任何公式。 （40） AA （41）（A（BC）（B（AC） （42）（AB）（B C）AC） （43）（A（AB）（AB） （44）（A B）（AB）,2019/11/10,15,（45）（A B）（BA） （46）（AB）（BA）（AB） （47）（AB）A （48）（AB）B （49） A（B（AB） （50） A（AB） （51） B（AB） （52）（BA）（CA）（BC）A） （53）（AB）（BA） （54） AA,2019/11/10,16,二.推理规则 本系统中只有一条推理规则，称为分离规则我们（简记为“分”） 例如： AB， AB （读为：对AB，A实施分离规则可得B）,2019/11/10,17,三.定理 （1）公理为定理； （2）如果AB，A为定理，则由它们实施分离规则所得到的B也是定理。 （3）定理仅限于此。 在本系统中我们一定要注意以下几点： 第一.（40）（54）中任何一条，均是无穷条公式的集合。 例如：AA，BB，（AB）（AB），（PQ）（PQ）等等均是公理（40）。 第二.要证明一公式是定理，必须给出它的证明过程？设有一系列公式A1，A2An，如果每一个Ai（1in） （1）或者是公理之一； （2）或者是由前面的Ah，Ak，（h，k,I）实施分离规则而得； （3）An即B则说公式序列A1，A2An是定理B的永真证明过程。B便是一个定理，各个A叫做在B的证明过程中间结果。一般除要求给出证明过程外还要求同时给出证明根据，所谓证明根据是：当某个Ai是公理时，便在它旁边注明“分Ah Ak”按上面的定义要求，永真证明过程根据都是详尽的。,2019/11/10,18,举例：证明（AB）（BA）为定理 证 公理（50）=（1）：B（BA） 公理（51）=（2）：A（BA） 公理（52）=（3）：（A（BA）（B（BA）（AB）（BA） 分（3）（2）=（4）：（B（BA）（AB）（BA） 分（4）（1）=（5）：（AB）（BA） （5）即为所要证明的定理。,2019/11/10,19,第三.虽然本系统只用一条分离规则就足够了，但是对于今后的推导是不够方便，为了方便起见，我们将从这条基本规则出发。如何引出规则呢？假设我们已证明了一条定理AB，编号为（a），又证明了一条定理A，编号为（b），由此可得 分（a）（b）=（c） B 这里分（a）（b）称为B的证明根据，（c）称为编号，“B”这条定理应看作对（a）（b）实施分离规则的结果，即： 分（a）规则 AB 也就是说，每逢我们有一条定理（a）：AB，我们便有一条相应的分（a）规则AB 。即由（a）的前件A可以得出（a）的后件B。,2019/11/10,20,同理，假定我们证明了一条定理A（BC）编号为（ 又假定我们证明了两条定理： （b）：A，（c）：B 虽然可作如下推理 分（a）（b）=（d） BC 分（d）（C）= （e） C， 将（d）代入得 分分（a）（b）（c）=（e） C 这里我们可以把C看作两次实施分离规则的结果，即 分分（a）：A，BC 同理，如果我们有定理（a）：A（B（CD） 则我们可有如下规则： 分分分（a）规则：A，B ，CD 即由（a）的三个前件A，B，C可得出（a）的后件D。,2019/11/10,21,当然这里可以推广到一般情况，这里就不去详述。我们熟悉这种导出规则，对今后的学习将有很大的帮助。为了更进一步讨论我们再给出一些推理规则，这