代码编织梦想

一、数理逻辑

逻辑基本律:同一律(A=A)、矛盾律(A且!A为假)、排中律(A或!A为真)

(一)基本概念

1.命题逻辑基本概念:命题常项,命题变项,联结词,命题公式

(1)悖论:非命题

(2)联结词完备集:{非,或,与},{与非^},{或非}

(3)命题公式的表达:真值表、析取合取范式

(4)命题公式的可满足性问题:消解法

2.一阶逻辑基本概念:个体词(常项,变项,约束,自由。域),谓词(常项,变项),量词(辖域),一阶语言,谓词公式,解释

(1)个体词:客体

(2)谓词:客体的性质,客体之间的关系

(3)量词:任意,存在

(4)谓词公式的表达:前束范式

3.命题逻辑和一阶逻辑的关系

封闭的谓词公式在任何解释下都变成命题常项。

非封闭的谓词公式在某些解释下可以变成命题常项。

(二)等值式/算律

1.共有的等值式

(1)双重否定律、结合律、交换律、幂等律

(2)分配律、吸收律、德摩根律

(3)格的性质:零律、一律

(4)布尔代数性质:排中律,矛盾律

(5)蕴含式,等价式,逆否命题,等价否定,归谬论

2.一阶逻辑特有的等值式

(1)消去量词2

(2)量词否定2

(3)量词辖域收缩、扩张8

(4)量词分配2

3.一阶逻辑的置换规则

(1)换谓词名(置换)

(2)换约束个体名(换名)

(3)换自由个体名(代替)

(三)形式系统

1.自然推理系统

(1)命题自然推理系统

推理规则:

前提引入、中间结论引入、置换

假言推理、附加、化简、拒取、假言三段论、析取三段论、构造性二难、破坏性二难、合取引入

(2)一阶逻辑自然推理系统

特有的推理规则:任意+、任意-,存在+,存在-

2.公理推理系统

组成:符号集、公式集(符号使用)、公理模式集、推理规则集

欧式几何数学体系(半形式化)

弗雷格公理系统(Frege's system),仅用非、推 符号。

卢卡西维茨公理系统(Lukasiewicz),仅用 非 、 推 符号。

罗素公理系统(Russell-Bernays),仅用 非 、或 、推 符号。

亨廷顿公理系统(Huntington axiomatic system)。

ZFC公理系统。

二、集合论

1.基本概念:

(1)集合(相异、无序)、隶属、包含、子集、幂集、空集、全集

(2)交,并,广义并,广义交、补,相对补(差),对称差

(3)集合的基数、Venn图、容斥原理

(4)集合恒等式

2.关系

表达:集合、矩阵、关系图

性质:自反、对称、传递、反自反、反对称、闭包

等价关系:饼状图,划分,商集

偏序关系:哈斯图,最、极,上、下界

3.映射/函数

定义域、值域、像、完全原像、单、满、双、复合、逆、

集合计数:势、康托定理

三、代数系统

运算:映射到自身的映射

六律四元(结合、交换、幂等、消去;分配、吸收;单位元、逆元、零元,补元)

代数系统:<集合,一元或二元运算>    类型、种(积代数,子代数)、态、结构

群 定义:封结幺逆    

直观:对称(二维图形,多项式):保持运算的一一变换的全体所构成的群

子群    判定    正规子群(内自同构不变)    中心(自同构不变)

商群    <合同划分,[a]X[b]=[ab]>

同态    核,像    同态定理(单:甲是乙的一个子群,满:甲的一个商群是乙,非单非满:甲的一个商群是乙的一个子群,双:甲就是乙)

有限群    拉格朗日定理

生成元集

环    加法交换群、乘法半群,乘关于加分配    <矩阵,+,*> 

域    加法交换群、乘法交换群(零元可以没有逆元,且无零因子)    <有理数,+,*>

格    结合律、交换律、吸收率    <偏序集,交,并>

布尔代数    有补(任意元素存在交为0,并为1的补元)、分配(不含五角格、钻石格)格    <幂集,交,并>

四、图论

1.分类:无向图或有向图,标定图或非标定图

2.基本概念:点、边、邻域(前驱、后继)、关联边、端点、相邻边、割、桥

3.进阶概念:度,握手定理    度数列,HAVEL定理:可图化、可简单图化

3.1高级概念:k-core,k-truss,k-clique,k-club,p-cohesion,k-edge/vertex connected,k-shell

4.表示:集合,矩阵(关联矩阵、邻接矩阵、可达矩阵)

4.图的操作:{增加、删除}X{点、边}    收缩边    求补    并、交、差、环和

5.连通性

(1)基本概念:通路、回路、简单通路、简单回路、初级通路、初级回路

(2)连通程度

无向图:点连通、边连通、最小度

有向图:强连通图、单向连通图、弱连通图

最短路径/短程线:Dijstrar、Bellman-Floyd

关键路径:最早、最晚、缓冲时间

r-正则图

(3)图的遍历

深搜、广搜

6.特殊的图

(1)二部图<=>无奇圈 证明

(2)欧拉图和半欧拉图

构造方法:Fleury(不走桥)、边不重的圈的并

充要条件:有向图、无向图

(3)哈密顿图

充分条件:任意不相邻顶点度和大于等于N-1

必要条件:去除任意非空点集后连通分支小于等于被去除点集的基数

递归充要条件:若两个不相邻顶点度和大于等于N,则G和G+e要么都是哈密顿图要么都不是

(4)树

最小生成树(Kruskal,Prime,破圈法(管梅谷法))

哈夫曼树

(5)平面图

欧拉公式

充要条件:不含与K5同胚,也不含与K3,3同胚的子图。

7.一种重要思想

扩大路径法。思想很简单,但需要彻底掌握十道不同类型的习题或者定理证明应用才可彻底掌握该思想。

五、初等数论

1、基础知识

欧几里得原理

整除:商和余数定理

素数、合数:充要条件  判定

算数基本定理(因子分解定理):素数个数无限

最大公约数gcd、最小公倍数lcm:gcd*lcm=mn,列因子、列素因子分解、欧几里得算法(辗转相除法)

费马小定理证明、a^n计算、ab mod z=[(a mod z)(b mod z)] mod z证明、a^n mod z计算、邮资问题

2、均匀随机数产生、RSA密钥是这一块的巅峰应用(会了理解透了RSA就基本会了初等数论)

六、组合数学

主要是如何数数,递归数数之类的,十分基础而且重要

七、数学机械化

中国科学院数学机械化重点实验室 (KLMM)吴文俊

积分计算器:用 Wolfram|Alpha 求积分WolframeAlpha,Mathematic等

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/SiKongPop/article/details/79538670

离散数据:析取范式与合取范式_南山93的博客-爱代码爱编程_求合取范式

一、前言 析取范式和合取范式是命题逻辑等值演算中的重要内容,其目的是为了标准化命题公式。下面我将给出析取范式和合取范式的计算步骤。又由于析取范式和合取范式的形式不唯一,为了便于比较命题公式之间的关系,因此衍生出了主析取范式和主合取范式。所以,也将给出主析取范式和主合取范式的求解方法。 二、范式存在定理 范式存在定理:任一命题公式都存在与之等值的析取范

离散数学简单复习知识点汇总_毕东的博客-爱代码爱编程_离散数学知识点汇总

命题是非真必假的陈述句。联结词:与原子命题一起构成复合命题。原子命题公式:命题常元、命题变元同城为原子命题公式,简称原子公式。 合式公式是由下列规则形成的字符串:    (1) 真值 T 和 F 是合式公式。    (2) 原子命题公式是一个合式公式。    (3) 若 A 是合式公式,则 ┐A 是合式公式。    (4) 若A和B是合式公式,则A∧B、A

【记录】离散数学知识点总结_earnest~的博客-爱代码爱编程

点击目录传送ฅʕ•̫͡•ʔฅ 第一章 命题逻辑1.1 命题符号化及联接词1.2 命题公式及分类1.3 等值演算 第二章 一阶逻辑 https://blog.csdn.net/qq_4376

离散数学第一章总结-爱代码爱编程

离散数学第一章 1.公式类型 1)重言式 也是永真式,公式真值恒为1。 2)矛盾式 永假式,真值恒为0。 3)可满足式 不是矛盾式的就都是可满足式。重言式一定是可满足式。 2.成真赋值与成假赋值 也叫成真指派与成假指派。 一组原子的取值(真值指派)使得公式为真:成真指派(赋值) 一组原子的取值(真值指派)使得公式为假:成假指派(赋值)

离散数学-爱代码爱编程

第一章 命题逻辑 1.1 命题符号化及联结词 1 .陈述句: 叙述或说明事实的具有陈述语调的句子。 2.命题:能判断真假的陈述句。 3.称判断为正确的命题的真值为真,判断错误的命题的真值为假,因此称命题是具有唯一真值的陈述句。 4.命题分为简单命题和复合命题;不能分解成更简单句子的命题称为简单命题或原子命题,用小写的英文字母p,q,r,...,pi,q

离散数学定义大全-爱代码爱编程

离散定义大全 将会持续更新 空集: ∅ = { x ∣

离散数学——关系-爱代码爱编程

关系 序偶与笛卡儿积关系的概念、性质及运算关系的概念关系的表示关系的性质关系的复合运算关系的逆运算关系的闭包运算特殊关系等价关系相容关系偏序关系全序关系 序偶与笛卡儿积 两个具有固定次序的元素 a,b 组成一个有序对被称为 序

简单聊聊离散数学是什么-爱代码爱编程

一、离散数学的主要内容与历史背景 首先让我们来聊聊什么是离散数学 ? 从内容上来看,离散数学没有一个确定的中心话题,内容很杂,粗略统计其涉及到主要概念如:集合、函数、关系、命题逻辑、谓词逻辑,到算法、计数、数据结构、递归、图论、概率、数论、形式语言与自动机,布尔代数、向量与矩阵,线性规划、抽象代数,编码理论、信息论,博弈论、运筹学、理论计算机科学等,真

离散数学知识点总结(命题逻辑的基本概念及等值演算)-爱代码爱编程

1.命题:   定义:能够判断真假的陈述句叫做命题(不以句号结尾的句子,以及悖论,2*x>10这样的都不是命题)   2.连接词:否定:┓  合取:∧ 析取:∨ 蕴含:→ 等价:<->  (其中最容易让人记混的符号是合取∧ 和析取∨,我的记忆方法是合取是要倒过来盖上才能合上;而析取就像碗里装水,正着放水才能析出来,开口方向反过来的话,水

python中如何创建一颗多叉树_多叉树的设计、建立、层次优先遍历和深度优先遍历...-爱代码爱编程

多叉树的设计、建立、层次优先遍历和深度优先遍历 早起曾实现过一个简单的多叉树《实现一个多叉树》。其实现原理是多叉树中的节点有两个域,分别表示节点名以及一个数组,该数组存储其子节点的地址。实现了一个多叉树建立函数,用于输入格式为A B。A表示节点的名字,B表示节点的子节点个数。建立函数根据用户的输入,首先建立一个新的节点,然后根据B的值进行深度递归调用

离散数学第一章(知识点总结)-爱代码爱编程

提前用电子科大的视频预习了下离散数学,感觉知识点很杂,总结了下发到上面~有需要的自取 如果有需要电子版的可以评论哈 1.集合的数学符号: 用带或不带下标的大写英文字母表示集合:A,B,C,... 用带或不带下标的小写英文字母表示元素:a,b,c,....  2.常用集合 自然数集合N 整数集合Z 有理数集合Q (有理数是整数(正整数、0、负整

离散数学常见知识点-爱代码爱编程

离散数学常见知识点 本人复习自用,仅供参考,不保证全面 集合 集合的长度 集合加绝对值表示集合的长度 A = {1,2,{1,2}} 则|A|=3 B = {∅,2,{1,2}} 则|B|=3 幂集 集合A的全部子集构成的集合称之为A的幂集,记作P(A) 映射 两个非空集合A与B间存在着对应关系f,而

离散数学知识点-爱代码爱编程

商集 定义: R 是 A 上等价关系,由 R 的所有等价类构成的集合称之为 A 关于 R 的商集。记作 A/R。 A / R