离散数学——公式与解释
- 格式:ppt
- 大小:275.00 KB
- 文档页数:21
基本等值式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.代数系统:代数系统,子代数,积代数,同态,同构。