离散数学——公式与解释

基本等值式1.双重否定律 A Û┐┐A2.幂等律 A Û A∨A, A Û A∧A3.交换律A∨B Û B∨A，A∧B Û B∧A4.结合律(A∨B)∨C Û A∨(B∨C) (A∧B)∧C Û A∧(B∧C)5.分配律A∨(B∧C) Û (A∨B)∧(A∨C) （∨对∧的分配律）A∧(B∨C) Û (A∧B)∨(A∧C) （∧对∨的分配律）6.德·摩根律┐(A∨B) Û┐A∧┐B ┐(A∧B) Û┐A∨┐B7.吸收律A∨(A∧B) Û A，A∧(A∨B) Û A8.零律A∨1 Û 1,A∧0 Û 09.同一律A∨0 Û A，A∧1 Û A10.排中律A∨┐A Û 111.矛盾律A∧┐A Û 012.蕴涵等值式A→B Û┐A∨B13.等价等值式A«B Û (A→B)∧(B→A)14.假言易位A→B Û┐B→┐A15.等价否定等值式A«B Û┐A«┐B16.归谬论(A→B)∧(A→┐B) Û┐A求给定公式范式的步骤(1)消去联结词→、«(若存在)。

(2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。

(3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。

推理定律--重言蕴含式(1) A Þ (A∨B) 附加律(2) (A∧B) Þ A化简律(3) (A→B)∧A Þ B假言推理(4) (A→B)∧┐B Þ┐A 拒取式(5) (A∨B)∧┐B Þ A析取三段论(6) (A→B) ∧ (B→C) Þ (A→C) 假言三段论(7) (A«B) ∧ (B«C) Þ (A « C) 等价三段论(8) (A→B)∧(C→D)∧(A∨C) Þ(B∨D) 构造性二难(A→B)∧(┐A→B)∧(A∨┐A) Þ B 构造性二难(特殊形式)(9)(A→B)∧(C→D)∧(┐B∨┐D) Þ(┐A∨┐C) 破坏性二难设个体域为有限集D={a1,a2,…,an},则有（1）"xA(x) Û A(a1)∧A(a2)∧…∧A(an)（2）$xA(x) Û A(a1)∨A(a2)∨…∨A(an)设A(x)是任意的含自由出现个体变项x的公式，则（1）┐"xA(x) Û $x┐A(x)（2）┐$xA(x) Û "x┐A(x)设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则（1） "x(A(x)∨B) Û "xA(x)∨B"x(A(x)∧B) Û "xA(x)∧B"x(A(x)→B) Û $xA(x)→B"x(B→A(x)) Û B→"xA(x)（2） $x(A(x)∨B) Û $xA(x)∨B$x(A(x)∧B) Û $xA(x)∧B$x(A(x)→B) Û "xA(x)→B$x(B→A(x)) Û B→$xA(x)设A(x)，B(x)是任意的含自由出现个体变项x的公式，则（1）"x(A(x)∧B(x)) Û "xA(x)∧"xB(x)（2）$x(A(x)∨B(x)) Û $xA(x)∨ $xB(x)全称量词“"”对“∨”无分配律。

离散数学命题公式的定义离散数学中的命题公式，就像是数学世界里的独特密码，等待着我们去破解和理解。

咱先来说说啥是命题公式。

简单来讲，命题公式就是由命题常量、命题变量、联结词还有括号，按照一定的规则组合起来的式子。

这就好像搭积木一样，不同的积木（元素）按照特定的方式拼凑在一起，就形成了一个独特的结构。

比如说，“P 并且Q”，这里的“P”和“Q”可以是简单的命题，像“今天是晴天”“小明喜欢吃苹果”，而“并且”就是那个把它们连接起来的桥梁，这样组合在一起就成了一个命题公式。

我记得有一次给学生们讲这个知识点的时候，有个小家伙一脸懵地问我：“老师，这命题公式有啥用啊，感觉好复杂！”我笑了笑，拿起一支笔在纸上画了个简单的逻辑图，跟他说：“你看啊，假如我们要判断一个事情能不能发生，是不是得先搞清楚各种条件之间的关系？命题公式就是帮我们理清这些关系的工具。

”然后我举了个例子，比如学校组织春游，“天气好”是 P，“有足够的车辆”是 Q，那么“天气好并且有足够的车辆”这个命题公式成立的时候，春游就能顺利进行。

这小家伙听完，眼睛一下子亮了起来，好像突然明白了其中的奥妙。

命题公式的定义可不是随便定的，它有着严格的规则。

命题常量和命题变量是基础的元素，就像盖房子的砖头。

而联结词呢，像是“并且”（∧）、“或者”（∨）、“如果……那么……”（→）等等，它们决定了这些元素之间的逻辑关系。

括号的作用也不能小觑，它能明确运算的顺序，避免出现混乱。

在实际应用中，命题公式的作用可大了去了。

比如说在计算机科学里，编程的时候需要通过逻辑判断来决定程序的走向，这时候命题公式就能派上用场，帮助程序员准确地表达和处理各种条件。

再比如在数学推理中，通过对命题公式的分析和变形，可以得出很多重要的结论。

总之，离散数学中的命题公式虽然看起来有点复杂，但只要我们用心去理解，掌握它的规律，就能像掌握了一把神奇的钥匙，打开数学世界中一扇又一扇充满奥秘的门。

所以啊，同学们可别被它一开始的样子吓住，只要多琢磨、多练习，就能发现其中的乐趣和奇妙之处！。

注意/技巧：析取符号为V，大写字母Vx + y = 3不是命题前件为假时，命题恒为真运用吸收律命题符号化过程中要注意命题间的逻辑关系，认真分析命题联结词所对应的自然语言中的联结词，不能只凭字面翻译。

也就是说，在不改变原意的基础上，按照最简单的方式翻译通用的方法：真值表法VxP（x）蕴含存在xP（x）利用维恩图解题证明两个集合相等：证明这两个集合互为子集常用的证明方法：任取待证集合中的元素<,>构造相应的图论模型第一章命题逻辑命题和联结词命题的条件：表达判断的陈述句、具有确定的真假值。

选择题中的送分题原子命题也叫简单命题，与复合命题相对简单联结词的真值表要记住非（简单）合取（当且仅当P，Q都为真时，命题为真）析取（当且仅当P，Q都为假时，命题为假），P，Q可以同时成立，是可兼的或条件（→）（当且仅当P为真，Q为假时，命题为假）P是前件，Q是后件只要P，就Q等价于P→Q只有P，才Q等价于非P→非Q，也就是Q→PP→Q特殊的表达形式：P仅当Q、Q每当P双条件（↔）（当且仅当P与Q具有相同的真假值时，命题为真，与异或相反）命题公式优先级由高到低：非、合取和析取、条件和双条件括号省略条件：①不改变先后次序的括号可省去②最外层的括号可省去重言式（永真式）、矛盾式（永假式）、偶然式可满足式：包括重言式和偶然式逻辑等价和蕴含（逻辑）等价:这是两个命题公式之间的关系，写作“⇔”，要与作为联结词的↔区分开来。

如果命题公式A为重言式，那么A⇔T常见的命题等价公式：需要背过被标出的，尽量去理解。

关键是掌握公式是将哪个符号转换为了哪个符号，这对于解证明题有很大的帮助！验证两个命题公式是否等价：当命题变元较少时，用真值表法。

当命题变元较多时，用等价变换的方法，如代入规则、替换规则和传递规则定理：设A、B是命题公式，当且仅当A↔B是一个重言式时，有A和B逻辑等价。

蕴含:若A→B是一个重言式，就称作A蕴含B，记作A⇒B常见的蕴含公式的运用方法同上面的命题等价公式证明A⇒B：①肯定前件，推出后件为真②否定后件，推出前件为假当且仅当A⇒B且B⇒A时，A⇔B，也就是说，要证明两个命题公式等价，可以证明它们相互蕴含联结词的完备集新的联结词：条件否定、异或（不可兼或）、或非（析取的否定）、与非（合取的否定）任意命题公式都可由仅含{非，析取}或{非，合取}的命题公式来等价地表示全功能联结词集合极小全功能联结词集合对偶式对偶式：将仅含有联结词非、析取、合取（若不满足，需先做转换）的命题公式A中的析取变合取，合取变析取，T变F，F变T得到的命题公式A*称为A的对偶式范式析取式：否定+析取合取式：否定+合取析取范式：（合取式）析取（合取式）……析取（合取式）。

离散数学排列组合公式简介离散数学是一门研究离散对象的数学学科，其中排列组合是其重要的一部分。

排列组合是指在给定的元素集合中，通过选择和安排元素，得到不同的结果。

在离散数学中，排列和组合是两个基本概念，并且有相应的计算公式来帮助解决问题。

一、排列公式排列是指从给定的元素集合中，按照一定的顺序，选取若干元素进行排列。

在离散数学中，排列的计算方法有两种：允许重复和不允许重复。

下面分别介绍这两种排列的计算公式。

1. 允许重复的排列当元素集合中的元素可以重复出现在排列中时，就称为允许重复的排列。

对于含有n个元素的集合，要求选择r个元素进行排列，公式如下：P(n, r) = n^r其中，P表示排列的个数，n表示元素集合中的元素个数，r表示选择的元素个数。

举个例子，假设有一个字母集合{a, b, c}，要选择两个字母进行排列，那么根据公式，可以计算出排列的个数为：P(3, 2) = 3^2 = 9因此，共有9种不同的排列方式：aa、ab、ac、ba、bb、bc、ca、cb、cc。

2. 不允许重复的排列当元素集合中的元素不允许重复出现在排列中时，就称为不允许重复的排列。

对于含有n个元素的集合，要求选择r个元素进行排列，公式如下：P(n, r) = n! / (n - r)!其中，"!"表示阶乘，n!表示n的阶乘，即n × (n-1) × ... × 1。

举个例子，假设有一个字母集合{a, b, c}，要选择两个字母进行排列，那么根据公式，可以计算出排列的个数为：P(3, 2) = 3! / (3 - 2)! = 3! / 1! = 6因此，共有6种不同的排列方式：ab、ac、ba、bc、ca、cb。

二、组合公式组合是指从给定的元素集合中，不考虑顺序，选择若干元素进行组合。

在离散数学中，组合的计算方法也有两种：允许重复和不允许重复。

下面分别介绍这两种组合的计算公式。

离散数学知识点(总23页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法:绿色表示页码：灰色表示数理逻辑：1.命题公式：命题，联结词(，，，，)，合式公式，子公式2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5.推理理论：重言蕴含式，有效结论，P规则，T规则， CP规则，推理6.谓词与量词:谓词，个体词，论域，全称量词，存在量词7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8.公式语义:解释，赋值，有效的，可满足的，不可满足的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，-规则（US），+规则（UG），-规则(ES)，+规则(EG), 推理集合论：1.集合: 集合, 外延性原理, , , , 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R),对称闭包 s(R), 传递闭包 t(R)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元2.代数系统：代数系统，子代数，积代数，同态，同构。

1.内容及范围主要来自 ppt，标签对应书本2.可能有错，仅供参考离散数学知识点说明：定义：红色表示。

定理性质：橙色表示。

公式：蓝色表示。

算法: 绿色表示页码：灰色表示数理逻辑：1.命题公式：命题，联结词(⌝，∧，∨，→，↔)，合式公式，子公式2.公式的真值：赋值，求值函数，真值表，等值式，重言式，矛盾式3.范式：析取范式，极小项，主析取范式，合取范式，极大项，主合取范式4.联结词的完备集：真值函数，异或，条件否定，与非，或非，联结词完备集5.推理理论：重言蕴含式，有效结论，P 规则，T 规则， CP 规则，推理6.谓词与量词:谓词，个体词，论域，全称量词，存在量词7.项与公式:项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入8.公式语义:解释，赋值，有效的，可满足的，不可满足的9.前束范式:前束范式10.推理理论:逻辑蕴含式，有效结论，∀-规则（US），∀+规则（UG），∃-规则(ES)，∃+规则(EG), 推理集合论：1.集合: 集合, 外延性原理, ∈, ⊆, ⊂, 空集, 全集, 幂集, 文氏图, 交, 并, 差, 补, 对称差2.关系: 序偶, 笛卡尔积, 关系, domR, ranR, 关系图, 空关系, 全域关系, 恒等关系3.关系性质与闭包:自反的, 反自反的, 对称的, 反对称的, 传递的,自反闭包 r(R),对称闭包 s(R), 传递闭包 t(R)4.等价关系: 等价关系, 等价类, 商集, 划分5.偏序关系:偏序, 哈斯图, 全序(线序), 极大元/极小元, 最大元/最小元, 上界/下界6.函数: 函数, 常函数, 恒等函数, 满射,入射,双射，反函数, 复合函数7.集合基数:基数, 等势, 有限集/无限集, 可数集, 不可数集代数结构：1.运算及其性质：运算，封闭的,可交换的,可结合的,可分配的,吸收律, 幂等的，幺元,零元,逆元2.代数系统：代数系统，子代数，积代数，同态，同构。

离散数学组合公式推导技巧介绍离散数学是数学的一个重要分支，主要研究离散的数学结构和离散的数学对象。

在离散数学中，组合是一个重要的概念，它涉及到对离散对象进行选取、排列和组合的计数问题。

组合公式是解决这类问题的重要工具，本文将介绍一些常用的组合公式的推导技巧。

一、阶乘公式推导在组合问题中，阶乘是最基本的计算方式之一。

阶乘的推导可以基于递归定义进行，即n的阶乘定义为n乘以(n-1)的阶乘，直到1的阶乘为止。

这种递归定义的推导方法可以用来计算较小的数的阶乘。

例如，我们可以通过递归定义来推导5的阶乘：5! = 5 * 4!= 5 * 4 * 3!= 5 * 4 * 3 * 2!= 5 * 4 * 3 * 2 * 1!根据递归定义，我们可以得出n的阶乘公式：n! = n * (n-1)!二、排列公式推导排列是指从n个元素中选取m个元素，按照一定顺序进行排列。

在组合问题中，排列是一个非常常见的计数方式。

常用的排列公式有一般排列公式和循环排列公式。

1. 一般排列公式：一般排列公式可以表示为P(n,m)，表示从n个元素中选取m个元素进行排列的方式数。

P(n,m) = n! / (n-m)!其中，n!表示n的阶乘。

2. 循环排列公式：循环排列是指在一组元素中，元素之间没有顺序要求的排列方式。

对于n个元素的循环排列，可以表示为P(n,n)。

P(n,n) = (n-1)!在循环排列中，元素个数为n的循环排列等价于元素个数为n-1的一般排列。

三、组合公式推导组合是指从n个元素中选取m个元素，不考虑元素的顺序。

组合问题在离散数学中也是一个重要的概念。

常用的组合公式有一般组合公式和循环组合公式。

1. 一般组合公式：一般组合公式可以表示为C(n,m)，表示从n个元素中选取m个元素进行组合的方式数。

C(n,m) = n! / (m! * (n-m)!)其中，n!表示n的阶乘。

2. 循环组合公式：循环组合是指在一组元素中，元素之间没有顺序要求的组合方式。

离散数学公式范文离散数学是研究离散对象及其性质、结构和相互关系的一门数学学科。

它是数学中的一个重要分支，广泛应用于计算机科学、信息科学、金融、工程和其他领域。

离散数学的内容丰富多样，其中包括了许多重要的公式。

本文将介绍一些与离散数学相关的公式，帮助读者更好地理解和应用离散数学。

1.排列组合公式：排列公式表示从n个不同元素中取r个元素所能组成的不同排列的个数，记作P(n,r)。

组合公式表示从n个不同元素中取r个元素所能组成的不同组合的个数，记作C(n,r)。

它们的计算公式如下：P(n,r)=n!/(n-r)!C(n,r)=n!/(r!*(n-r)!)2.容斥原理公式：容斥原理是一种计数方法，用于计算多个集合的交集和并集中的元素个数。

假设A1,A2,...,An是n个集合，容斥原理公式如下：A1∪A2∪...∪An，=Σ(，Ai，)-Σ(，Ai∩Aj，)+Σ(，Ai∩Aj∩Ak，)-...+(-1)^(n-1)*，A1∩A2∩...∩An3.递推关系公式：递推关系是一种数列的定义方式，通过前几项的关系来递推出后面的项。

其中最著名的递推关系是斐波那契数列的定义，即F(n)=F(n-1)+F(n-2)，其中F(0)=0，F(1)=14.二项式定理公式：二项式定理是代数中一种重要的展开公式，用于计算(x+y)^n的展开式。

它的公式如下：(x+y)^n=Σ(C(n,r)*x^(n-r)*y^r)，其中r取值范围为0到n。

5.欧拉欧系数公式：欧拉欧系数是用于描述图的性质的一种算子。

对于一个图G的顶点集V和边集E，欧拉欧数E(G)定义为：E(G)=，E，-，V，+16.布尔代数公式：布尔代数是一种逻辑代数，用于描述和操作命题的真值。

其中的一些重要公式包括德摩根定律、分配律、吸收定律等。

7.图论中的公式：图论是离散数学中的一个重要分支，用于研究图的性质和结构。

其中一些重要的公式包括图的度数和、握手定理、树的性质等。

离散数学笔记第一章命题逻辑合取析取定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句定义 1.2.1合式公式(1)单个命题变元、命题常元为合式公式，称为原子公式。

(2)若某个字符串A 是合式公式，则⌝A、(A)也是合式公式。

(3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A↔B 是合式公式。

(4)有限次使用(2)~(3)形成的字符串均为合式公式。

1.3等值式1.4析取范式与合取范式将一个普通公式转换为范式的基本步骤1.6推理定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。

（用等值演算或真值表）第二章 谓词逻辑2.1、基本概念∀：全称量词 ∃：存在量词一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"∀x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如∃x(H(x)∨WL(x))，即量词的后面为合取式 例题R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ∀x ∀y(R(x)∧T(y)→H(x,y))有的兔子比所有的乌龟跑得快表示为：∃x ∀y(R(x)∧T(y)→H(x,y))2.2、谓词公式及其解释定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22y x 的 f(x,y))、 谓词常元(如表示人类的 H(x))。

定义 2.2.2、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。