离散数学推理的三要素

离散数学数理逻辑部分定义与概念命题逻辑1.（论域）定义：论域是一个数学系统，记为D。

它由三部分组成：(1)一个非空对象集合S，每个对象也称为个体；(2)一个关于D的函数集合F；(3)一个关于D的关系集合R。

2.（逻辑连接词）定义设n > 0，称{0, 1}n到{0, 1}的函数为n元函数，真值函数也称为联结词。

若n = 0，则称为0元函数。

3.（命题合式公式）定义(1)常元0和1是合式公式；(2)命题变元是合式公式；(3)若Q, R是合式公式，则(?Q)、(Q∧R)、(Q∨R)、(Q→R)、(Q?R)、(Q⊕R)是合式公式；(4)只有有限次应用(1)-(3)构成的公式是合式公式。

4.（生成公式）定义：设S是联结词的集合。

由S生成的公式定义如下：⑴若c是S中的0元联结词，则c是由S生成的公式。

⑵原子公式是由S生成的公式。

⑶若n≥1，F是S中的n元联结词，A1, …, A n是由S生成的公式，则F A1…A n是由S生成的公式。

5.（复杂度）公式A的复杂度表示为FC(A)常元复杂度为0。

命题变元复杂度为0，如果P是命题变元，则FC(P) = 0。

如果公式A = ?B，则FC(A) = FC(B)+ 1。

如果公式A = B1∧B2，或A = B1∨B2，或A = B1→B2，或A = B1?B2，或A = B1⊕B2，或则FC(A) = max{FC(B1), FC(B2)} + 1。

6.命题合式公式语义论域：研究对象的集合。

解释：用论域的对象对应变元。

结构：论域和解释称为结构。

语义：符号指称的对象。

公式所指称对象。

合式公式的语义是其对应的逻辑真值。

7.（合式公式语义）设S是联结词的集合是{?，∧，∨，⊕，→，?}。

由S生成的合式公式Q在真值赋值v下的真值指派v(Q)定义如下：⑴v(0) = 0, v(1) = 1。

⑵若Q是命题变元p，则v(Q) = pv。

⑶若Q1, Q2是合式公式若Q = ?Q1，则v(Q) = ?v(Q1)若Q = Q1∧Q2，则v(Q) = v(Q1) ∧v(Q2)若Q = Q1∨ Q2，则v(Q) = v(Q1) ∨v(Q2)若Q = Q1→Q2，则v(Q) = v(Q1) →v(Q2)若Q = Q1?Q2，则v(Q) = v(Q1) ?v(Q2)若Q = Q1⊕Q2，则v(Q) = v(Q1) ⊕v(Q2)8.（真值赋值）由S生成的公式Q在真值赋值v下的真值v(Q)定义如下：⑴若Q是S中的0元联结词c，则v(Q) = c。

第三章 命题逻辑的推理理论§1 推理的形式结构推理：从前提出发推出结论的思维过程。

前提：已知命题公式集合。

结论：从前提出发应用推理规则推出的命题公式。

定义设A1, A2, …, A k, B都是命题公式，若命题公式A1∧A2∧…∧A k→B是重言式，则称由前提A1, A2, …, A k推出结论B的推理是有效的或正确的，并称B是有效的结论。

推理的形式结构记为{A1,A2,…,A k}A B推理正确，记为{ A1,A2,…,A k }⊨B推理无效，记为{ A1,A2,…,A k }⊭B注①推理正确，结论未必为真。

②推理只注重结构。

例判断下述推理的正确性。

(1) {p, p→q}⊢ q(2) {p, q→p}⊢ q解 (1) p∧(p→q)→q⇔p∧(¬p∨q)→q⇔(p∧¬p)∨(p∧q)→q⇔p∧q→q⇔¬ (p∧q)∨q⇔¬p∨(¬q∨q)⇔¬p∨1⇔1故{p, p→q }⊨ q(2) p∧(q→p)→q让q =0，可得q→p =1，再取p =1可得p∧(q→p)=1 由此得p∧(q→p)→q有成假赋值1 0，故{ p, q→p }⊭ q判断推理正确性：1．真值表法。

2．等值演算法。

3．主析取范式法。

4．构造证明。

例判断下述推理是否正确？（1）若a能被4整除，则a能被2整除。

a能被4整除。

所以a能被2整除。

（2）若下午气温超过30℃，则王小燕必去游泳。

若她去游泳，则她就不去看电影了。

所以，若王小燕没去看电影，则下午气温必超过了30℃。

解(1) p：a能被4整除q：a能被2整除前提：p→q，p结论：q推理的形式结构：{p→q，p} A q前面已证此推理正确。

(2) p：下午气温超过30℃q：王小燕去游泳r：王小燕去看电影前提：p→q, q→¬r结论：¬ r→p推理的形式结构：{p→q，q→¬r} A(¬r→p)因为，(p→q)∧(q→¬ r)→(¬r→p)⇔m1∨m3∨m4∨m5∨m6∨m7主析取范式显然不是重言式，故推理不正确。

离散数学的基础知识点总结离散数学是研究离散结构和离散对象的数学分支。

它以集合论、图论和逻辑等为基础，涉及了许多重要的基础知识点。

下面是对离散数学的基础知识点进行的总结。

1. 集合论（Set theory）：集合论是离散数学的基础，涉及了集合的概念、运算和恒等关系，以及集合的分类、子集、幂集和笛卡尔积等基本概念和性质。

2. 逻辑（Logic）：逻辑是离散数学的重要组成部分，涉及了命题逻辑和谓词逻辑的基本概念和推理规则，包括命题的真值表、谓词的量化、逻辑等价和逻辑蕴含等概念。

3. 函数（Functions）：函数是离散数学中的核心概念之一，涉及了函数的定义、域和值域、函数的性质、特殊的函数（如恒等函数、常值函数、单射函数和满射函数等）以及函数的复合和逆函数等。

4. 关系（Relations）：关系是离散数学中的另一个核心概念，涉及了关系的定义、关系的特性（如自反性、对称性、传递性和等价关系等）、关系的闭包和自反闭包、关系的图示表示和矩阵表示、等价关系和偏序关系等。

5. 图论（Graph theory）：图论是离散数学的重要分支，涉及了图的基本概念（如顶点、边、路径和圈等）、图的表示方法（如邻接矩阵和邻接表等）、图的遍历算法（如深度优先和广度优先等）、图的连通性和可达性、最小生成树和最短路径等基础知识。

7. 代数结构（Algebraic structures）：代数结构是离散数学的一个重要方向，涉及了群、环、域和格等基本代数结构的定义、性质和分类，以及同态映射和同构等概念。

8. 数论（Number theory）：数论是离散数学的一个重要分支，涉及了自然数的性质和结构，包括质数和素数、最大公因数和最小公倍数、同余和模运算、欧几里得算法和扩展欧几里得算法、费马小定理和欧拉函数等。

9. 排序和选择（Sorting and selection）：排序和选择是离散数学中的一类重要问题，涉及了各种排序算法（如冒泡排序、插入排序、快速排序和归并排序等）和选择算法（如选择排序和堆排序等），以及它们的复杂度分析和应用。

离散数学推理规则公式
离散数学的推理规则包括以下几种：
1. 前提引入规则（P规则）：可以在证明的任何时候引入前提。

2. 结论引入规则（T规则）：在证明的任何时候，已证明的结论都可以作为后续证明的前提。

3. 置换规则：在证明的任何时候，命题公式中的任何子命题公式都可以用与之等价的命题公式置换。

4. 假言推理规则（P∧ (P→Q) ⇒ Q）。

5. 附加规则（P ⇒ P∨Q）。

6. 化简规则（P∧ Q ⇒ P）。

7. 拒收式规则（¬Q∧(P→Q) ⇒ ¬P）。

8. 假言三段论规则((P→Q)∧(Q→R) ⇒ P→R）。

9. 析取三段论规则（¬P∧(P∨Q) ⇒ Q）。

10. 构造性二难规则((P∨Q)∧(P→R)∧(Q→S) ⇒ (S∨R))。

以上内容仅供参考，建议查阅离散数学书籍或咨询数学领域专业人士获取更多专业信息。

离散数学逻辑推理条件离散数学逻辑推理条件离散数学是计算机科学中的一门核心课程，其中逻辑推理是其中关键领域之一。

逻辑推理是一种基于规则和条件的推导过程，它将给定的假设和已知条件进行比较，形成结论。

在逻辑推理中，条件是至关重要的，下面将分为三类讨论条件在逻辑推理中的重要性。

1.逆否命题逆否命题是逻辑推理中最常用的一个条件。

它的定义是，如果命题P成立，则其逆否命题也成立，即“非Q不成立，P不成立。

”举个例子，对于命题“如果今天下雨，那么地面湿润”，它的逆否命题可以表述为“如果地面没有湿润，那么今天没有下雨”。

也就是说，在逻辑推理中，当我们知道一个命题成立时，我们可以通过其逆否命题来确定其他命题是否成立。

2.充分必要条件充分必要条件是指，在一个条件语句中，如果只满足一个条件，那么另一个条件就不满足。

例如，如果期望获得汉堡，充分必要条件是付款。

也就是说，如果你没有付款，那么你就无法获得汉堡。

在逻辑推理中，充分必要条件可以帮助我们确定命题之间的关系。

3.假设条件假设条件是指对命题进行前提假设，这个假设可以根据实际和已知信息进行结果计算和推理。

例如，“如果这本书可以下载，我就会去下载它。

”假设条件是“这本书可以下载”。

然后，我们可以推断出结果，也就是“我会去下载它”。

在逻辑推理中，假设条件是非常重要的，因为它们帮助我们确定关键因素，并帮助我们了解到达结论的正确路径。

结论以上所述，考虑到逻辑推理的要求，包括逆否命题、充分必要条件和假设条件是其中最核心的条件。

这些条件帮助我们根据已知条件推断出未知情况，并帮助我们验证我们的结论是否正确。

在计算机科学中，这些条件对于算法的正确性检验、软件测试和系统设计都非常重要。

有了这些条件，我们可以进行高效的决策和判断，从而进一步发展计算机科学和其他领域。