最新公告
  • 欢迎您光临欧资源网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入我们
  • 离散数学基础__简单期末复习整理文章(第一次课)

    离散数学基础__简单的期末复习

    文章目录

    第一课:命题逻辑的基本概念、命题及其真值

    一个真命题就是一个真命题

    假命题是真值为假的命题

    简单和复合命题

    简单命题(原子命题):由简单陈述句组成的命题

    复合命题是通过连接词连接简单命题形成的陈述句

    连接词和复合命题

    如果p,则q称为p和q的蕴涵,记为p→q p是蕴涵的前件,q是蕴涵的后件→称为蕴涵连接词

    p→q的逻辑关系

    q 是 p 的必要条件

    p 是 q 的充分条件

    第二课公式作业

    设p,q,…为公式A中出现的所有命题变量,将一组真值赋给p,q,…,称为A的赋值或解释。

    使公式为真的赋值称为真赋值

    使公式为假的赋值称为假赋值

    命题公式的分类

    重言式(永恒的真理):没有错误赋值的命题公式

    矛盾(永久错误):没有真正赋值的命题公式

    可满足:非矛盾命题公式 注意:重言式是可满足的,但反之则不行。

    第三课:命题逻辑等价演算、等价算法

    //德摩根律
    ¬(A∨B)⇔¬A∧¬B
    ¬(A∧B)⇔¬A∨¬B
    //蕴涵等值式
    A→B⇔¬A∨B
    //假言易位
    A→B⇔¬B→¬A
    

    第四课推理

    推理是从前提推导出结论的思考过程。前提是指已知的命题公式,结论是从前提导出并应用推理规则的命题公式。前提可以是多个。

    定义:

    令 H1, H2, …, Hn, C 为命题公式

    如果 (H1∧H2∧…∧Hn)→C 是重言式,则称 C 是一组前提 H1,H2,…,Hn 的有效结论

    记为:H1∧H2∧…∧Hn⇒C

    推理方法

    1.真值表法

    2.如果H1、H2、…、Hn都是T(True),C也是T(True);

    3.如果C为F(False),则H1、H2、…、Hn中至少有一个为假

    重言式包含

    定义当且仅当 A→B 为真,我们说“A 重言式蕴含 B”,并将其表示为 A⇒B。

    重言式蕴含A⇒B的证明方法

    1、A→B是永恒的真理风格

    2、证明¬B⇒¬A

    3、如果 A 是 T,B 是 T,或者如果 B 是 F,A 是 F,那么 A⇒B。

    4、直接使用共同蕴涵(p51推理法)

    推理法则 – 同义反复

    (A→B)∧A⇒B			 //★假言推理
    (A→B)∧¬B⇒¬A		 	//★拒取式
    (A∨B)∧¬B⇒A			//★析取三段论
    (A→B)(B→C)(A→C)	//★假言三段论
    

    第五课推理法直接证明

    PT 法:

    P 定律:在推导过程中引用了前提。

    T 定律:已经引入的公式可以在后续推导过程中引用。包括 TI 法则(重言式蕴涵)和 TE 法则(等价)。

    间接证明法前提证明法:

    证明A1,A2, …,Ak→(C→B)

    前提:A1,A2, …,Ak

    结论:C→B

    等价证明

    前提:A1,A2, …,Ak,C

    结论:B

    简化为荒谬(矛盾的证据):

    证明A1,A2, …,Ak→B

    前提:A1,A2, …,Ak

    结论:B 将 ¬B 添加到前提。如果引入矛盾,则推理是正确的。

    第六课范式:简单析取和简单合取

    文本:命题变量及其否定集合

    简单析取:由有限字符组成的析取,例如 p,¬q,p∨¬q,p∨q∨r, …

    简单连词:由有限字符组成的连词,如p,¬q,p∧¬q,p∧q∧r,…

    析取范式和合取范式

    析取范式

    由有限简单合取A1∨A2∨…∨Ar组成的析取

    其中 A1,A2,…,Ar 是简单的连词

    连接范式

    合取A1∧A2∧…∧Ar,由有限简单析取组成,

    其中 A1,A2,…,Ar 是简单的析取

    范式:析取范式和合取范式的统称

    范式存在定理

    定理 任何命题公式都有其等价的析取范式和合取范式

    主要析取范式 主要析取范式:由最小项组成的析取范式

    例如当n=3时,命题变量为p,q,r

    (¬p∧¬q∧r)∨(¬p∧q∧r)是主析取范式

    定理

    任何命题公式都有一个等价的主析取范式并且是唯一的。

    问主析取范式的方法

    假设公式A包含命题变量p1,p2,…,pn

    (1) 求 A 的析取范式 A′=B1∨B2∨… ∨Bs,其中 Bj 是简单的合取 j=1,2, … ,s

    (2) 如果 Bj 既不包含 pi 也不包含 ¬pi,则将 Bj 展开为 Bj⇔Bj∧(pi∨¬pi) ⇔(Bj∧pi)∨(Bj∧¬ pi) 重复此过程直到所有简单连词是长度为 n 的最小项

    (3)消除重复的最小项,即用mi代替mi∨mi

    (4)按下标从小到大排列最小的项

    附: ∧1 m001 m010…保证m…为1自然数是整数的逆命题,记为Σ

    求连词范式的方法

    假设公式A包含命题变量p1,p2,…,pn

    (1) 求 A 的合取范式 A′=B1∧B2∧…∧Bs,其中 Bj 是简单析取 j=1,2,…,s。

    (2) 如果 Bj 既不包含 pi 也不包含 ¬pi,则将 Bj 展开为 Bj⇔Bj∨(pi∧¬pi) ⇔(Bj∨pi)∧(Bj∨¬pi) 重复此过程直到所有简单析取是长度为 n 的最大项。

    (3) 消除重复的极大项,即将Mi∧Mi替换为Mi。

    (4) 将极大的项目从小到大排列。

    附: ∨0 M001 M010…保证M…为0,记为Π

    初级析取范式的集合表示

    找出公式的真赋值和假赋值

    判断公式的类型

    判断两个公式是否等价

    第 3 章 – 一阶逻辑

    量词:表达数量的词

    万能量词∀:表示任意、全部、全部等

    如果 ∀x 表示对于单个域中的所有 x,x∀x F(x) 表示所有 x 都具有属性 F

    存在量词∃:表示有,有,至少一个等

    例如,∃x 表示在单个域中存在 x∃x。 F(x) 表示有 x 的性质为 F

    第1章集合和集合枚举的关系表示

    如A={a,b,c,d},N={0,1,2,…}

    说明 { x | P(x) } 如 N={ x | x 是自然数}

    **集合属性:**

    (1)集合中的元素不同。例如,{1,2,3}={1,1,2,3}

    (2)集合中的元素不能重复。

    (3)集合中的元素没有顺序。例如,{1,2,3}={3,1,2}={1,3,1,2,2}

    (4)集合中的元素也可以是集合。

    共同收藏

    自然数集N,整数集Z,正整数集Z+,有理数集Q,非零有理数集Q,实数集R,非零实数集R,复数集C,区间[ a,b],(a, b) 等待**

    第八课:集合之间的关系①包含和等于

    包含(子集)A⊆B ⇔ ∀x(x∈A→x∈B)

    排除 A⊈B ⇔ ∃x(x∈A∧x∉B)

    等于 A=B ⇔ A⊆B∧B⊆A

    不等于 A≠B ⇔ A⊈B ∨B⊈A

    真包含(真子集)A⊂B ⇔A ⊆B∧A≠B

    ②空集和完全集

    空集∅:没有元素的集合

    完整集 E:所讨论的集合仅限于 E 的子集

    ③电源组

    幂集 P(A):A 的所有子集的集合

    P(A)=x∣x⊆AP(A) = { x| x⊆A }P(A)=x∣x⊆A

    如果 |A| = n,则 |P(A)| = 2^n

    第九课,第四章,关系,有序对

    定义

    由x和y等两个元素按一定顺序组成的对称为有序对,记为

    笛卡尔积

    定义设A、B为集合,A与B的笛卡尔积记为A×B,A×B = { | x∈A ∧y∈B }.

    定义域、范围和域

    域:domR= {x| ∃y(∈R) }

    范围:ranR= {y| ∃x(∈R) }

    fldR=domR∪ranR

    示例 R={,,,},

    然后 domR =ranR =fldR = { a, c, {a}, d } {{b}, d, {d}}{ a, c, {a}, d , {b}, {d} }

    重要的关系

    令 A 为任意集合

    1、∅是A上的一个关系,称为空关系

    2、EA、IA分别称为全局关系和身份关系。

    KaTeX 解析错误:意外字符:第 27 位的“”:…| x∈A ∧y∈A}=A×A̲

    IA=∣x∈AIA={ | x∈A}IA=∣x∈A

    例如,A={1,2},那么

    EA={,,,}

    IA={,}

    关系的表示

    关系矩阵

    如果 A={x1, x2, …, xm}, B={y1, y2, …, yn},则 R 是 A 到 B 的关系

    R的关系矩阵是一个布尔矩阵MR= [ rij] m×n,其中rij= 1⇔ ∈R

    第十课:逆关系

    令R为X与Y的二元关系,

    R的反比关系记为RC(或R-1),

    即:R-1={| ∈R }

    显然,如果R⊆A×B,那么R-1 ⊆B×A

    R和S的复合关系

    R∘S= | | ∃y(∈R∧∈S) }

    **示例 R={, , , }S={, , , ❤️,2>, ❤️,3>} **

    R∘S={, , }

    S∘R={, , ❤️,2>, ❤️,3>}

    A 上关系的取幂

    定义设R为A上的关系,n为自然数,则R的n次方为

    (1) R0 = { | x∈A } = IA

    (2) Rn+1 = Rn∘R

    求幂方法

    对于一个集合表示的关系R,计算Rn就是n个R的合成。一个矩阵表示的关系是矩阵乘法,加法采用逻辑加法

    自反性和自反性

    定义

    令 R 为 A 上的关系,

    (1) 如果∀x(x∈A→∈R),则称R在A上是自反的

    (2) 如果∀x(x∈A→∉R),则称R在A上是自反的。

    自反:A 上的全局关系 EA,恒等关系 IA,小于或等于关系 LA,可分关系 DA 反反:实数集上的小于关系,幂集上的真包含关系。

    通俗解释:

    包括所有:反身

    排除所有:反身

    部分包含:既不自反也不自反

    对称和反对称

    定义令R为A上的关系,

    (1) 若∀x∀y(x,y∈A∧∈R→∈R),则称R为A上的对称关系。

    (2) 如果∀x∀y(x,y∈A∧∈R∧∈R→x=y),

    然后称 R 为 A 上的反对称关系。

    实例对称性:A 上的全局关系 EA、恒等关系 IA 和空关系 ∅。反对称:恒等关系IA,空关系是A上的反对称关系。

    通俗解释:

    对称:在关系R中,如果R是对称的,对于R中的任何有序对,在R中都有一个相反的有序对。

    反对称:在关系R中,如果R是反对称的,那么对于R中具有相反元素对的有序对,它们的两个元素必须相等。

    传递

    定义R是A上的关系

    如果∀x∀y∀z(x,y,z∈A∧∈R∧∈R→∈R),则称R是A上的传递关系。

    示例:A 上的全局关系 EA、恒等关系 IA 和空关系 ∅、小于等于关系、小于关系、可分关系、包含关系、真包含关系

    通俗解释:

    传递性:在关系R中,如果R具有传递关系,则必然存在∈R∧∈R→∈R

    第十一课等价关系

    定义

    令 R 为非空集上的关系。如果 R 是自反的、对称的和传递的,则称 R 为 A 上的等价关系。

    令R为等价关系,若∈R,则称x等价于y,记为x~y。

    等价类

    定义令R为非空集A上的等价关系,

    ∀x∈A,令 [x]R = { y | y∈A∧xRy } 称[x]R为x关于R的等价类,简称为x的等价类

    商业

    定义令R为非空集A上的等价关系,

    以R的所有等价类为元素的集合称为A关于R的商,记为A/R,

    等价关系与除法一一对应

    A/R 商是 A 的除法

    不同的商对应不同的除法

    给定 A 的一个分区 π,A 上的关系 R 定义如下: R ={ | x,y∈A∧x和y在π的同一个分区}

    那么R是A上的等价关系,由等价关系确定的商是π。

    第十二课:偏序关系

    定义

    非空集A上的自反、反对称和传递关系称为A上的偏序关系,

    表示为≼。设≼为偏序关系,

    如果∈≼,则写x≼y,读作x“小于或等于”y

    偏序集和哈斯图

    定义

    集合A和A上的偏序关系≼统称为偏序集,记为。

    例子:整数的集合和数的小于等于关系构成偏序集,幂集P(A)和包含关系构成偏序集

    .

    哈斯图:每个节点没有圈,两个相连的节点之间的顺序关系用节点位置的高度来表示,位置较低的元素的顺序在前面覆盖关系的两个节点之间。并排。

    偏序集合的特定元素

    (【集合论】序关系( 偏序关系中的八个特殊元素 | ① 最大元素 | ② 最小元素 | ③ 最大元素 | ④ 最小元素 | ⑤ 上界 | ⑥ 下界 | ⑦ 最小上界 精确界| ⑧ 最小下界infermum

    图无向图的基本概念

    定义

    无向图 G=,

    其中V≠∅称为顶点集,其元素称为顶点或节点;

    E是V&V的多重子集,称为边集,其元素称为无向边,或简称边。

    有时V(G)和E(G)分别用来表示V和E

    有向图

    定义有向图 D=,

    其中V≠∅称为顶点集,其元素称为顶点或节点;

    E是V×V的多重子集,称为边集,其元素称为有向边,简称边。

    有时V(D)和E(D)分别用来表示V和E

    有限图:V 和 E 都是有限图集 n 阶图:具有 n 个顶点的图 零图:具有 E=∅ 的图 平凡图:一阶零图

    空图:V=∅的图

    顶点和边的关联和邻接

    假设一个无向图G=,ek=(vi, vj)∈E,称vi,vj为ek的端点,ek与vi(vj)相关联。

    若vi≠vj,则ek与vi(vj)的关联数为1;若vi=vj,则ek与vi的关联数为2;

    如果vi不是边e的端点,则称e和vi之间的关联数为0。

    设vi,vj∈V,ek,el∈E,若(vi,vj)∈E,vi,vj称为相邻;如果 ek,el 有一个公共端点,则 ek,el 是相邻的。

    顶点度数

    令 G= 为无向图,v∈V,

    v的度数(degree) d(v):v是边的端点数之和

    悬垂顶点:1 度的顶点悬垂边:与悬垂顶点关联的边

    G的最大度Δ(G)=max{d(v)|v∈V}

    G的最小度δ(G)=min{d(v)|v∈V}

    第十三类握手定理

    定理

    任何图(无向和有向)中所有顶点的度数之和等于边数的 2 倍。

    有向图中所有顶点的入度之和等于出度与边数之和。

    推理

    任何图(无向图和有向图)都有偶数个奇数度顶点

    示例:在一群人中,一定有偶数个朋友有奇数个。

    简单图

    自然数是整数的逆命题_数学中什么叫命题_整数和分数比较大小

    定义

    在无向图中,与同一对顶点相关联的两条或多条边称为平行边,平行边的数量称为多重性。

    在有向图中,起点和终点相同的两条或多条边称为有向平行边,或简称平行边,平行边的数量称为多重性。

    具有平行边的图称为多重图。既没有平行边也没有环的图称为简单图。

    完全图和正则图 无向完全图:

    每对顶点之间只有一条边的无向简单图。

    n阶无向完全图记为Kn,顶点数为n

    边数m=n(n- 1)/2,Δ=δ=n- 1

    有向完全图:

    每对顶点之间有两条对边的有向简单图。

    顶点数n,边数m=n(n-1)

    Δ=δ=2(n- 1)

    k-正则图:顶点数n,边数m=kn/2

    子图

    定义集G=自然数是整数的逆命题,G′=为两个图(都是无向图,或者都是有向图),

    若V′⊆V和E′⊆E,则称G′为G的子图,G为G′的父图,

    记为G′⊆G。若G′⊆G且V′=V,则称G′为G的生成子图。

    若V′⊂V或E′⊂E,则称G′为G的真子图。

    图的同构

    定义

    如果说 G1 和 G2 同构,则写为 G1≅G2

    那么两个图的节点数相同,每个节点的度数相同,知识节点的排列组合不同

    第十四课图的矩阵表示是有向/无向图的邻接矩阵

    通路和回路

    定义

    给定图 G=(无向或有向)

    G中顶点和边的交替序列Γ=v0e1v1e2…elvl.G顶点和边的交替序列Γ=v_0e_1v_1e_2…e_lv_l.G顶点和边交替序列Γ= v0​e1​v1​e2​…el​vl​.

    如果

    ∀i(1≤i≤l),ei=(vi−1,vi)∀_i(1≤i≤l),e_i=(v_i-1,v_i)∀i​(1≤i≤l ) ),ei​=(vi​−1,vi​)

    (对于有向图,ei=),则Γ称为v0到vl的路径

    v0和vl分别是通路的起点和终点,l是通路的长度。

    如果 v0=vl,则 Γ 称为循环。

    如果一个路径(循环)中的所有顶点(for循环,v0=vl除外)都不同,则称为主路径或路径(primary loop or loop)。

    如果路径(循环)中的所有边都不同,则称为简单路径(simple loop),否则称为复杂路径(complex loop)

    无向图的连通性和连通分支

    令无向图G=,u,v∈V

    u 和 v 连通:如果 u 和 v 之间存在路径,则规定 u 和自身始终连通。

    连通图:任意两点相连的图。平凡图是连通图。

    连通性 R={|u, v∈V and u and v are connected}。 R是等价关系。

    连通分支:V 的等价类关于 R 的派生子图。

    设V/R={V1,V2,…,Vk},G的连通分支为G[V1],G[V2],…,G[Vk]

    连通分支的数量p(G)=k,G是连通图⇔p(G)=1

    有向图的连通性和分类

    有向图 D=,u,v∈V,

    u 到 v 可达:从 u 到 v 有一条路径,规定 u 到自身总是可达的。

    u 和 v 是相互可达的:u 取决于 v,v 取决于 u

    D弱连通(connected):省略每条边的方向得到的无向图是连通图

    D是单向连通的:∀u,v∈V,u可以到达v或者v可以到达u

    D是强连通的:∀u,v∈V,u和v互可达

    无向图的相关矩阵

    令无向图 G=,V={v1,v2,…,vn},E={e1,e2,…,em}。

    设mij为vi和ej的关联数,称(mij)n×m为G的关联矩阵,

    M(G).mij的可能取值为:0,1,2

    无环有向图的关联矩阵

    设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em}

    mij = 0 vivj 不连通 mij = 1 vi 为起点 mij=-1 vj 为终点

    第十五课:欧拉图

    欧拉路径:一条经过所有顶点且每条边只经过一次的路径。

    欧拉回路:经过所有顶点且每条边仅经过一次的回路。

    欧拉图:带有欧拉回路的图。

    判别定理

    无向图 G 具有欧拉回路当且仅当 G 是连通的且没有奇异顶点。

    Branch:V 的等价类关于 R 的派生子图。**

    设V/R={V1,V2,…,Vk},G的连通分支为G[V1],G[V2],…,G[Vk]

    连通分支的数量p(G)=k,G是连通图⇔p(G)=1

    有向图的连通性和分类

    有向图 D=,u,v∈V,

    u 到 v 可达:从 u 到 v 有一条路径,规定 u 到自身总是可达的。

    u 和 v 是相互可达的:u 取决于 v,v 取决于 u

    D弱连通(connected):省略每条边的方向得到的无向图是连通图

    D是单向连通的:∀u,v∈V,u可以到达v或者v可以到达u

    D是强连通的:∀u,v∈V,u和v互可达

    无向图的相关矩阵

    令无向图 G=,V={v1,v2,…,vn},E={e1,e2,…,em}。

    设mij为vi和ej的关联数,称(mij)n×m为G的关联矩阵,

    M(G).mij的可能取值为:0,1,2

    无环有向图的关联矩阵

    设无环有向图D=,V={v1,v2,…,vn},E={e1,e2,…,em}

    mij = 0 vivj 不连通 mij = 1 vi 为起点 mij=-1 vj 为终点

    第十五课:欧拉图

    欧拉路径:一条经过所有顶点且每条边只经过一次的路径。

    欧拉回路:经过所有顶点且每条边仅经过一次的回路。

    欧拉图:带有欧拉回路的图。

    判别定理

    无向图 G 具有欧拉回路当且仅当 G 是连通的且没有奇异顶点。

    G 有欧拉回路,但没有欧拉回路当且仅当 G 是连通的并且恰好有两个奇数顶点。

    站内大部分资源收集于网络,若侵犯了您的合法权益,请联系我们删除!
    欧资源网 » 离散数学基础__简单期末复习整理文章(第一次课)

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    欧资源网
    一个高级程序员模板开发平台

    发表评论