计算机数学基础②(Sets and Strings)

计算机数学基础②(Sets and Strings)

文章目录

​​Sets and Strings​​

​​Strings​​​​Sets​​

Sets and Strings

Strings

Definition 2.1. An alphabet is any collection of symbols.

字母表是任何符号的集合

Definition 2.2. Take any alphabet Σ. A string over the alphabet Σ isany sequence of letters in an alphabet.

以任何字母Σ为例。字母Σ上的字符串是字母表中的任何字母序列。

Definition 2.3. The length of any string is the number of charactersin that string.

任何字符串的长度都是字符的数量

换句话说，当且仅当两个字符串字面上的字符对字符完全相同时，它们是相等的!注意，两个长度不同的字符串总是不相等的。

我们规定st是字符串s与字符串t的连接

Definition 2.6. Let s and t be strings. We say that s is a prefix of tif t is just s with some additional stuff possibly tacked on the end: i.e. ifwe can find a third string u such that su = t.Similarly, we say that s is a suffix of t if t is just s with some additionalstuff possibly tacked on the front: i.e. if we can find a third string u suchthat us = t.Finally, we say that s is a substring (alternately, an “infix”) of t if tis just s with some stuff possibly tacked on both the front and end: i.e.if we can find strings u, v such that usv = t.

让s和t是字符串。我们说s是t的前缀.如果t只是s最后加上一些额外的东西,我们可以找到第三个字符串u，使得su = t。

类似地，如果t只是s加上一些可能附加在前面的东西:例如，如果我们能找到第三个字符串u，使us = t。我们说s是t的后缀，

最后，如果t只是s，可能在前端和末端都附加了一些东西:如果我们能找到字符串u, v，使usv = t。我们说s是t的子串(或者说是“中缀”).

Claim 2.1. The empty string λ is a prefix, suffix, and substring of everystring t.

空字符串λ是每个字符串t的前缀、后缀和子字符串。

Claim 2.2. If s is a prefix of t, then s is a substring of t.

如果s是t的前缀，那么s是t的子串

Sets

Definition 2.7. A set A is just a collection of things. We call thosethings the elements of A, and write x ∈ A to denote with symbols thestatement “x is an element of A.”To describe a set, we just list its elements between a pair of curly braces:for example, {1, 2, 3} would be how we would describe the set consistingof the three numbers 1, 2 and 3.

集合A就是一些东西的集合。我们 将x∈A表示为A的元素 " x是a的一个元素"

要描述一个集合，只需在一对花括号之间列出它的元素:例如，{1,2,3}是描述由数字1,2和3组成的集合的方式。

Definition 2.8. A set A has size n if it contains precisely n differentelements. If A contains infinitely many different elements, we say thatA has “infinite” size. We denote the size of A by writing ∣A∣.

如果它恰好包含n个不同的元素,集合A的大小为n。如果A包含无限多个不同的元素，我们说A的大小是“无限”的。我们通过写∣A∣来表示A的大小。

Definition 2.9. Take two sets A, B We say that B is a subset of A,and write B ⊆ A, if every object in B is also an object in A.

取两个集合A和B，如果B中的每个对象也是A中的一个对象,我们说B是A的子集，写作B⊆A。

Definition 2.10. Let A, B be a pair of sets. We define the union ofthese two sets, A ∪ B, to be the collection of all elements that are ineither A or B or both.

设A, B是一对集合。定义这两个集合的并集： A∪B，是其中所有元素的集合，不是A就是B，或者两者都有。

Definition 2.11. Let A, B be a pair of sets. We define the intersectionof these two sets, A ∩ B, to be the collection of all elements that are inboth A and B at the same time.

设A, B是一对集合。我们定义在这两个集合中交集： A∩B，是所有A和B中的元素同 时出现的集合。

Definition 2.12. Let A, B be a pair of sets. We define the differenceof these two sets, written A∖B or alternately A−B, to be the collectionof all elements that are both in A and not in B at the same time.

设A, B是一对集合。我们定义差集，写成A∖B或写成A - B，作为所有同时在A但不在B中的元素集合。

Definition 2.13. We say that two sets A, B are equal if they bothconsist of the same elements; that is, if• Every element in A is a element in B, and• Every element in B is also a element in A.

我们说集合A和集合B相等，如果它们都相等 相同的:由相同的元素组成的;也就是说,如果 •A中的每个元素都是B中的一个元素，并且 •B中的每个元素在a中也是一个元素。

Claim 2.3. Let A, B be any two sets such that A ⊆ B. Then A∪B = B.

设A, B为A⊆B的任意两个集合，则A∪B = B

Claim 2.4. Let A, B be any two sets. Then (A ∖ B) ∖ A = ∅.

设A B是任意两个集合。则(A∖B)∖A =∅。

Claim 2.5. If A, B, C are three sets, then A∖(B∪C) = (A∖B)∩(A∖C).

如果A、B、C是三个集合，则A∖(B∪C) = (A∖B)∩(A∖C)。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。