离散数学---推理理论

推理理论----直接证法一、推理理论1.定义1-8.1 设A和C两个命题公式，当且仅当A→C为重言式，即A ⇒ C.称C是A的有效结论，或C可由A 逻辑地推出.称已知的A为前提。

得到的C为前提的有效结论.实际上，推理的过程就是证明蕴含式的过程，即令H 1，H 2，…，H m 是已知的命题公式(前提)，若有H 1∧H 2∧....∧H m C ，则称C 是一组前提H 1，H 2，…H m 的有效结论，简称结论.1、真值表法（1）检查真值表中H1，H2,…Hm全部为“T”的所有行，看结论C是否也均为“T”，若C均为“T”，则结论有效.否则结论无效.（2）看结论C为“F”的所有行，检查每行前提H1，H2,…H m中是否至少有一个为F，若有“F”，则结论有效；若有均为“T”的行，则结论无效.二、推理方法例1 求证⌝P ∧ (P∨Q) ⇒Q.证明考察真值表P Q ⌝P P∨Q QF F T F FF T T T TT F F T FT T F T T 由真值表可以看出⌝P ∧ (P∨Q) ⇒Q.2、直接证法由一组前提，利用一些公认的推理规则，根据已知的等价或者蕴含公式，推演得到有效的结论.•规则P(引入前提规则)：前提在推导过程中的任何时候都可以引入使用.•规则T(引入结论规则)：在推导中，如果有一个或多个公式、重言蕴涵公式S，则公式S可以引入推导中.重要的重言蕴涵式(如教材第43页所示)I1.P∧Q⇒P I2. P∧Q⇒QI3. P⇒P∨Q I4. Q⇒P∨QI5. ⌝P⇒P→Q I6. Q⇒P→QI7. ⌝(P→Q)⇒P I8. ⌝(P→Q)⇒⌝QI9. P,Q ⇒P∧Q I10. ⌝P∧(P∨Q)⇒Q I11. P∧(P→Q)⇒Q I12. ⌝Q∧(P→Q)⇒⌝P I13. (P→Q)∧(Q→R)⇒P→RI14. (P∨Q)∧(P→R)∧(Q→R)⇒RI15. A→B ⇒(A∨C)→(B∨C)I16. A→B ⇒(A∧C)→(B∧C)重要的等价公式:⌝⌝P⇔P对合律 E1P∧Q⇔Q∧P E3 P∨Q⇔Q∨P 交换律 E2结合律 EP∧(Q∧R)⇔(P∧Q)∧R4E5 P∨(Q∨R)⇔(P∨Q)∨RP∧(Q∨R)⇔(P∧Q)∨(P∧R)分配律 E6E7 P∨(Q∧R)⇔(P∨Q)∧(P∨R)德-摩根定律 E⌝(P∧Q)⇔⌝P∨⌝Q8E9⌝(P∨Q)⇔⌝P∧⌝QP∨P⇔P E11 P∧P⇔P幂等律 E10P∨F⇔P E13 P∧T⇔P同一律 E12零律 EP∨T⇔T E15 P∧F⇔F14E16 P→Q⇔⌝P∨Q E17 ⌝(P→Q)⇔P∧⌝QE18 P→Q⇔⌝Q→⌝P E19 P→(Q→R)⇔(P∧Q)→R E20 P ∆ Q ⇔(P→Q)∧(Q→P)E21 P ∆ Q ⇔(P∧Q)∨(⌝P∧⌝Q )E22 ⌝(P ∆ Q)⇔ P↔⌝Q吸收律 P∨(P∧Q)⇔P P∧(P∨Q)⇔P互补律 P∨⌝P⇔T P∧⌝P⇔FP ∆ Q ⇔(⌝P∨Q)∧(P∨⌝Q)例2 求证（P→Q）∧（Q→R）∧P ⇒ R.证明序号前提或结论所用规则（从哪几步得到）所用公式(1) P P(2) P→Q P(3) Q T (1)(2) I11(4) Q→R P(5) R T (3)(4) I11 •（注公式I11为： P ∧（P→Q）⇒ Q ）。

推理理论中的推理规则（离散数学）推理理论是一个研究推理方法与规则的学问，其中推理规则是重要的一部分。

推理规则是指在一定的条件下，由一个或多个命题出发，推出另一个命题的规则。

在离散数学中，推理规则包括一些基础的规则和一些复杂的规则。

1. 充分必要条件充分必要条件是指一个命题P能成立的充分必要条件是命题Q 成立。

即P⇔Q。

这里的充分必要条件是指两个命题是等价的，即当且仅当P成立时Q成立，Q成立时P也成立。

例如，一个三角形是等腰三角形的充分必要条件是它有两个相等的角。

2. 反证法反证法是一种常用的推理规则，它常用于证明一个命题的反命题成立。

即假设命题P不成立，通过推理得到矛盾，从而证明了P成立。

例如，证明“所有偶数都不是素数”这个命题可以采用反证法，假设有一个偶数是素数，然后推导出矛盾，从而证明“所有偶数都不是素数”。

3. 等价变形等价变形是指在推理过程中将命题变形成等价的命题。

例如，将P∧Q推导为Q∧P是一种等价变形。

等价变形可以通过逻辑符号的转换、语法规则的变换等方式实现。

4. 全称推理全称推理是指从一个全称命题出发，推出另一个全称命题。

例如，从“对于任意一个自然数n，n+1>n”这个全称命题可以推出“对于任意一个自然数m，m+2>m”。

5. 假言推理假言推理是指从一个条件命题和它的前件出发，推出它的后件的命题。

例如，从“如果今天下雨，那么他就不去逛公园。

今天不下雨”这两个命题可以推出“他会去逛公园”。

6. 假命题推理假命题推理是指从一个假命题出发进行推理，最终得到矛盾。

例如，从假设“1=2”出发，我们可以通过推导得到矛盾，并证明1不等于2。

7. 归谬法归谬法是指从前提推导出矛盾的方法，一般用于证明前提错误的情况。

例如，如果要证明“所有汉语拼音都是辅音加韵母”这个命题是错误的，可以通过归谬法证明，即找出一个汉语拼音不符合这个规则。

8. 消解法消解法是推理中常用的一种方法，可用于在两个命题中推导得到新的命题。

数学中的离散数学与逻辑推理数学是一门既严谨又抽象的学科，它在解决实际问题时常常需要运用离散数学与逻辑推理。

离散数学是数学的一个分支，关注的是离散对象及其关系，而逻辑推理是基于定义和规则进行思维的过程。

本文将介绍离散数学和逻辑推理在数学中的重要性，并探讨它们的应用。

1. 离散数学的基本概念离散数学是研究离散对象及其关系的数学学科。

离散对象是离散集合中的元素，常常用来表示有限或可列的对象。

离散数学研究的内容包括图论、递归论、组合数学等，这些内容在现实世界中都有广泛的应用。

2. 离散数学在图论中的应用图论是离散数学的一个重要分支，研究的是图及其性质。

图由节点和边组成，用来表示不同对象之间的关系。

图论在网络规划、路径优化、社交网络分析等领域有着广泛的应用。

例如，在网络规划中，通过构建图模型，可以找到最优的路径，提高网络传输效率。

3. 逻辑推理的基本原理逻辑推理是一种思维过程，通过运用逻辑原理和规则，从前提出发推导出结论。

逻辑推理主要包括命题逻辑和谓词逻辑两个方面。

命题逻辑关注的是命题之间的逻辑关系，谓词逻辑则研究量化的命题。

4. 数学中的逻辑推理数学是严密的推理和证明的学科，逻辑推理在数学中起着至关重要的作用。

数学家通过逻辑推理来建立定理和证明定理的正确性。

数学中的推理过程需要遵循严格的逻辑规则，以确保结论的正确性。

逻辑推理在代数学、分析学、几何学等各个数学分支中都有广泛的应用。

5. 数学中的应用举例离散数学和逻辑推理在数学中有着广泛的应用。

以密码学为例，密码学是研究如何保护信息安全的学科，其中离散数学和逻辑推理起着重要作用。

通过数论和逻辑推理，可以设计出安全性较高的密码算法，以确保信息的机密性。

6. 离散数学与逻辑推理对于数学教育的重要性离散数学和逻辑推理在数学教育中扮演着重要角色。

通过学习离散数学和逻辑推理，学生能够培养严密的思维能力和逻辑思维能力，提升数学解决问题的能力。

离散数学和逻辑推理也有助于学生理解抽象概念和证明思路，为后续学习打下坚实的基础。

数学作为一门科学，是以逻辑思维为基础的。

离散数学作为数学的一个分支，与逻辑推理紧密相关。

离散数学研究的是离散对象和离散结构，而逻辑推理则是运用逻辑规则进行思维和推理的过程。

它们之间的相互影响使得数学在离散领域中能够更好地发展，并为人们的思维方式提供了重要的逻辑基础。

离散数学研究的对象包括集合、序列、关系、函数等。

在这些离散对象中，逻辑推理的运用是不可或缺的。

逻辑推理通过推理规则和推理方法来判断语句的正确性，从而进行问题的分析和解决。

逻辑规则像是思考的引擎，推动着思维的发展。

而离散数学的研究，则为逻辑推理提供了丰富的实例和背景。

通过离散数学的研究，我们可以借助逻辑推理来解决各种离散问题，揭示离散对象的性质和规律。

更具体地说，离散数学通过逻辑推理的方式帮助我们分析和解决一些常见的问题。

例如，在图论中，我们需要研究图的连通性、最短路径等问题。

而在解决这类问题时，离散数学的概念、定理和方法都需要运用到逻辑推理中。

我们可以通过逻辑推理来证明一个图是否连通，通过逻辑推理来寻找图中的最短路径。

逻辑推理帮助我们建立了问题的逻辑模型，而离散数学则为逻辑推理提供了实际问题的具体背景。

此外，离散数学与逻辑推理的结合还在计算机科学中发挥了重要的作用。

计算机科学是一门应用离散数学的学科，而逻辑推理则是计算机中的核心思维方式。

计算机中运行的程序需要经过逻辑推理的分析，才能确保其正确性。

而离散数学所研究的数据结构、算法等概念，也为逻辑推理提供了丰富的实例和应用场景。

通过离散数学和逻辑推理的结合，计算机科学得以高速发展，为我们提供了便捷的计算和处理方式。

总的来说，数学中的离散数学与逻辑推理密不可分。

离散数学为逻辑推理提供了实际问题的具体背景，而逻辑推理则在离散数学的研究和应用中发挥了重要的作用。

它们彼此相互促进，推动着数学领域的发展。

同时，离散数学和逻辑推理的结合也为计算机科学等应用学科提供了强有力的支撑。

因此，深入研究和理解离散数学和逻辑推理的关系，对于我们发展数学思维和解决实际问题有着重要的意义。