离散数学在计算机科学中的应用

离散数学用于为计算机科学的各个领域提供良好的知识。在计算机科学中，离散数学的应用非常广泛，描述如下：

布尔代数

在最基本的层面上，计算机的所有数据都用位（如 1 或 0）来表示。当计算机根据用于构成所有数字电路的**布尔代数**定律修改这些位时，它们会执行计算。图用于表示数字电路。

“与”、“或”和“非”等逻辑运算符用于开发低级编程语言。当软件开发人员开发任何项目时，他们大多喜欢高级语言。有时他们想通过减少低级操作来优化代码，有时他们也直接操作位。程序员还可以通过使用布尔逻辑来控制程序流程。这意味着他们可以定义某些条件，然后控制哪些指令将被执行。

布尔代数有各种定律，描述如下：

交换律

根据**交换律**，如果我们改变变量的顺序，它不会影响结果。如果一个操作包含以下表达式，它将被称为交换操作：

1. A.B = B.A
2. A + B = B + A

结合律

根据**结合律**，如果我们重新排列任何二元表达式的括号，它不会改变逻辑电路的结果。如果一个二元操作包含以下表达式，它将被称为结合操作：

1. (A.B).C = A.(B.C)
2. (A + B) + C = A + (B + C)  

分配律

根据**分配律**，如果我们将一个数字乘以一组相加的数字，其结果与分别进行每个乘法相同。如果一个操作包含以下表达式，它将被称为分配操作：

A.(B + C) = A.B + A.C

AND 律

如果二元操作使用 **AND**，它将被称为 AND 律，描述如下：

1.	A.0 = 0
2.	A.1 = A
3.	A.A = A
4.	A.Ā = 0 

OR 律

如果二元操作使用 **OR**，它将被称为 OR 律，描述如下：

1.	A + 0 = A
2.	A + 1 = 1
3.	A + A = A
4.	A + Ā = 1  

反演律

根据**反演律**，如果我们对任何变量执行双重反演，它将输出变量本身。此定律使用非操作。如果一个操作包含以下表达式，它将被称为反演操作：

A + Ā+= 1

布尔代数还有**德摩根定理**，它有两个定律：

德摩根第一定律

根据**第一定律**，变量乘积的补码和它们各自变量补码的和彼此相等，描述如下：

 (A.B) = A + B  

德摩根第二定律

根据**第二定律**，变量和的补码和它们各自变量补码的乘积彼此相等，描述如下：

(A+B) = A.B

布尔代数示例

在此示例中，我们将求解表达式 **C + BC**。

根据德摩根定律，我们可以将上述表达式写成如下：

C + (B + C)

现在我们将这样使用交换律：

(C + C) + B

之后，我们将这样使用补码律：

1 + B = 1

因此，

C + BC = 1

概率

**概率**用于定量领域以及计算机科学领域。概率在软件工程中用于评估风险量。例如，假设我们正在设计一个系统，并且我们正在使用概率。在这种情况下，概率将说明系统的容量，这意味着我们的系统可以处理多少负载，以及在该峰值负载之后系统将崩溃。我们还可以使用概率测量网络的可靠性。在机器学习中，我们可以使用各种条件概率应用来完成从开发良好医疗到校准垃圾邮件过滤器等任务。

随机算法在实践中被称为更高效和最好的算法，因为它们提供了那些难以计算的任务的精确计算。概率可以被描述为数据科学和统计学的基础之一。它也被称为行业中最热门的领域之一。如果学生们在计算机科学的基础上学习概率，它将为他们提供定量直觉，这在他们的日常生活中和整个职业生涯中都很有用。我们有指定概率的公式，

Probability of event to happen P(E) = Number of favorable outcomes/Total Number of outcomes

概率示例

假设一家商店有 6 套西装，其中 3 套是绿色的，2 套是紫色的，1 套是橙色的。我们将找到选择橙色西装的概率。

解决方案

概率将通过将商店中橙色西装的数量除以西装总数来计算。所以：

2/6 = 1/3 

命题逻辑

当开发人员开发任何项目时，重要的是他应该有信心通过运行代码获得预期的结果。我们可以使用数学来描述程序。它们正确性的原因是**命题逻辑**工具。计算机科学的核心领域被称为算法，使用这些关键技能来分析和设计算法是困难的。**数学归纳法**原理被两个主要范式使用：函数式编程和迭代编程。此原理用于分别验证它们的循环和递归函数调用。

最正式的规范语言可以称为**逻辑**，用于编程语言的基础和设计。例如，SQL 系列中的语言只是关系逻辑的实现，具有一些附加功能。一些特定的逻辑演算和许多领域特定语言具有相同的实现。在工业中，形式化方法和程序验证的采用率正在增加。它还与传统测试技术结合使用，以增加对软件性能和有效性的信心。

命题逻辑示例

3+3=5
Narendra Modi is the Prime Minister.
'a' is a vowel. 

此示例有三个句子，它们是命题。其中第一个句子是假或无效的，最后两个句子是真或有效的。

有些示例不是命题，描述如下：

1 + a = 5
Go on vacation and enjoy

此示例有两个句子不是命题，因为第一个句子可能为假或为真，因为“a”的值未指定，所以我们无法判断它为真或为假，除非我们指定该值，并且最后一个句子没有真值。

归纳与递归

如果我们想了解编程的函数式范式，将使用的关键概念是**归纳和递归**。递归是一种编程策略，用于解决大问题。我们将大问题分解为相同类型的较小问题。而归纳是一种数学策略，用于证明与大量事物相关的陈述。

许多行业和公司，如 Facebook (Haskell)、Amazon、Microsoft Research (F*、Haskell)、Apple (Swift)、Oracle (JavaScript、Java 8) 和 Microsoft (F#)，增加了函数式范式在通用和特定任务中的采用。数据结构和算法也可以使用**递归关系**轻松描述。在计算机科学的理论领域和许多计算模型中，它们被视为骨干。更关键的部分，特别是在敏感应用中，是软件的安全性和正确性。

归纳示例

使用数学归纳法，证明对于所有正整数 n，n < 2ⁿ。

解决方案

我们假设 n 的命题是 P(n): n < 2ⁿ

**基本步骤：** P(1) 为真，因为 1 < 2¹

**归纳步骤：** 如果 P(n) 为真，则对于每个 n，P(n+1) 为真。

我们假设 P(n): n < 2ⁿ 为真

然后我们将证明 P(n+1): n+1 < 2ⁿ⁺¹ 为真。

n + 1 < 2n+ 1
< 2n + 2n
= 2n(1 + 1)
 = 2n(2)
= 2n+1

递归示例

示例 1

我们将描述递归定义函数的示例：

f(0) = 5
f(n) = f(n-1) + 2

解决方案

我们将这样计算函数的值：

f(0) = 5
f(1) = f(0) + 2 = 5 + 2 = 7
f(2) = f(1) + 2 = 7 + 2 = 9
f(3) = f(2) + 2 = 9 + 2 = 11 

这个递归定义函数等价于一个显式定义函数，描述如下：

f (n) = 2n + 5

示例 2

我们将描述递归定义函数的示例：

f(0) = 0
f(n) = f(n-1) + 2n-1 

解决方案

我们将这样计算函数的值：

f(0) = 0
f(1) = f(0) + (2)(1) -1 = 0 + 2 - 1 = 1
f(2) = f(1) + (2)(2) -1 = 1 + 4 - 1 = 4
f(3) = f(2) + (2)(3) -1 = 4 + 6 -1 = 9 
f(4) = f(3) + (2)(4) -1 = 9 + 8 -1 = 16 

这个递归定义函数等价于一个显式定义函数，描述如下：

f (n) = n2

数论

在数论中，我们将学习正整数的集合，可以是 1、2、3、4、5、6 等。它们也称为**自然数**集。在数论中，我们主要关注学习各种数字之间的关系。在计算机安全、密码学和区块链领域，**数论**包含关键应用。根据数学，借助现代密码系统，用户的数据可以完全免受各种类型的攻击和恶意对手的侵害。

模算术描述了哈希的数学基础，它是许多应用程序最有用的工具。通过互联网传输的文件由校验和验证，校验和基于哈希。像哈希映射这样的数据结构通过使用模算术来执行高效的操作。在操作系统和计算机体系结构中，数论还提供了使用内存相关事物的便利。数论有许多熟悉和不熟悉的示例，描述如下：

Even: 2, 4, 6, 8, 10, 12?..
Odd: 1, 3, 5, 7, 9??
Triangular: 1, 3, 6, 10, 15, 21?..
Prime: 2, 3, 5, 7, 11, 13, 17??
Fibonacci: 1, 1, 2, 3, 5, 8, 13, 21?..
Square: 1, 4, 9, 16, 25?.
Cube: 1, 8, 27, 64??.
Perfect: 6, 28, 496?.

计数

我们还可以通过使用**计数**技术来发展定量直觉。例如，假设用户使用一些定义的规则创建密码。现在我们可以通过使用计数技术获得有效密码的数量。此技术还用于确定攻击者暴力破解所有密码所需的时间。现在我们将学习鸽巢原理，它解释了为什么我们没有一个可以描述通用无损压缩的算法。当我们使用压缩算法时，它每次都会减少某些文件并增加其他文件的数量。可以使用每个压缩算法压缩不同类型的文件，例如视频、音频、文本、图像等。算法的复杂性可以借助计数轻松确定。

实际应用有许多不同的可用资源，它们具有复杂的权衡。有些任务没有太多空间，因此它们必须牺牲时间以换取更多空间，而另一些任务需要快速算法，因为它们可以承受巨大的空间以实现速度。在复杂情况下，我们需要在资源使用方面达到一个最佳点，以便系统不会面临资源饥饿问题并保持完美运行。通过计数，我们能够以结构化的方式创建这些考虑。它还可以提供与资源使用相关的正式保证。

计数示例

示例 1

在此示例中，我们将计算可以使用 2、3、4、5、7 和 9 位数字形成多少个 3 位数字。

**解决方案：**正如我们所见，有 6 个可用数字。所以：

(6)(6)(6) = 216

示例 2

假设 Jack 去了一家披萨店，并选择制作自己的披萨。这家店有 4 种不同的酱汁、4 种不同的面包和 3 种不同的奶酪，但他每种类别只能选择一种。现在我们必须找出可以制作披萨的不同方式有多少种。

解决方案

(4)(4)(3) = 48

图

**图**可以被描述为一组对象的图形表示，其中链接用于连接某些对对象。它是一组顶点和边。其中顶点用于表示相互连接的对象，由 V 表示。边是一种链接，用于连接顶点，由 E 表示。图被称为强大的数据结构。

图具有回答问题和建模关系的能力。例如，当我们使用导航应用程序搜索从办公室到家的最快路线时，此应用程序使用图搜索算法来搜索它。它还将根据我们的车辆向我们显示时间。图在计算机科学中广泛用于表示文件系统。它还用于数据库、深度学习、函数式编程和其他应用程序。

图的示例

**示例 1：** 假设有一对集合 (V, E)，其中 V 用于包含顶点集，E 是边集，用于连接成对的顶点。现在我们将考虑以下图并找到顶点和边的数量。

在此图中，

V = {u, v, w, x, y}
E = {uv, uw, vx, wx, xy}

**示例 2：** 我们必须找出以下图的顶点和边。

在此图中，

V = {5, 6, 7, 8, 9}
E = {56, 67, 78, 89, 59, 69, 68}