软件工程-基础课程-离散数学_图论.docxVIP

PAGE1

PAGE1

离散数学基础

1集合论基础

集合论是离散数学的基石，它研究的是集合的性质和操作。集合是一个无序的元素的集合，其中的元素是唯一的，没有重复。集合的表示通常有两种方式：列举法和描述法。列举法是将集合中的所有元素列出，如A={1,

集合的基本操作包括并集、交集、差集和补集。并集是两个集合中所有元素的集合，交集是两个集合中共同元素的集合，差集是第一个集合中但不在第二个集合中的元素的集合，补集是全集中的元素但不在原集合中的元素的集合。

1.1代码示例

#Python中使用set类型表示集合

A=set([1,2,3])

B=set([2,3,4])

#并集

C=A.union(B)

print(C)#输出{1,2,3,4}

#交集

D=A.intersection(B)

print(D)#输出{2,3}

#差集

E=A.difference(B)

print(E)#输出{1}

#补集需要先定义全集

U=set([1,2,3,4,5])

F=U.difference(A)

print(F)#输出{4,5}

2关系与函数

关系是集合中元素之间的联系，通常表示为有序对的集合。例如，集合A={1,2,3}和集合B=

函数是一种特殊的关系，其中每个输入都有一个确定的输出。函数通常表示为f:A→B，其中A是定义域，B是值域。例如，函数

2.1代码示例

#Python中使用字典表示函数

deff(x):

函数f(x)=x^2

returnx**2

#测试函数

forxin[1,2,3]:

print(f(x))#输出1,4,9

3逻辑与证明方法

逻辑是研究推理的科学，它在离散数学中用于证明定理和命题。逻辑的基本元素是命题，命题是一个可以判断真假的陈述。例如，“2是偶数”是一个命题，而“x是偶数”不是一个命题，因为它包含一个变量x。

证明方法包括直接证明、反证法、构造证明和归纳证明。直接证明是最常见的证明方法，它直接从已知的命题推导出要证明的命题。反证法是假设要证明的命题的否定是真的，然后推导出矛盾，从而证明原命题是真的。构造证明是通过构造一个实例来证明存在性。归纳证明是通过证明一个命题对于所有自然数都成立来证明该命题。

3.1代码示例

defis_even(n):

判断一个数是否是偶数

returnn%2==0

#直接证明

assertis_even(2)#2是偶数

#反证法

assertnotis_even(3)#3不是偶数，如果3是偶数，那么3%2应该等于0，这是矛盾的

#构造证明

assertis_even(4)#4是偶数，我们构造了一个偶数4

#归纳证明

defis_even_for_all_n(n):

证明所有自然数的偶数倍都是偶数

ifn==1:

returnis_even(2)

else:

returnis_even_for_all_n(n-1)andis_even(2*n)

assertis_even_for_all_n(5)#证明所有自然数的偶数倍都是偶数

4数理归纳法与递归

数理归纳法是一种证明方法，用于证明一个命题对于所有自然数都成立。它通常包括两个步骤：基础步骤和归纳步骤。在基础步骤中，我们证明命题对于最小的自然数（通常是1）成立。在归纳步骤中，我们假设命题对于某个自然数n成立，然后证明命题对于n+1也成立。

递归是一种算法设计策略，它将问题分解为更小的子问题，然后通过解决子问题来解决原问题。递归通常包括两个部分：基本情况和递归情况。在基本情况中，我们直接给出问题的解。在递归情况中，我们将问题分解为更小的子问题，然后通过递归调用来解决子问题。

4.1代码示例

deffactorial(n):

计算n的阶乘

ifn==0:#基本情况

return1

else:#递归情况

returnn*factorial(n-1)

#测试函数

print(factorial(5))#输出120

在上述代码中，我们使用递归来计算n的阶乘。基本情况是n=0，此时阶乘的值为1。递归情况是n0，此时阶乘的值为n*(n-1)的阶乘。我们通过递归调用来计算(n-1)的阶乘，从而解决了原问题。#图论入门

5图的基本