形式语言与自动机基础知识

Frey September 22, 2018 [数学] #集合

形式语言与自动机这门课需要有离散数学的基础,但本科通信工程里没有学过这门课,总结一些这门课中需要的基础知识

1.集合及其运算

1.1子集和真子集

$A$子集:$A \subseteq B​$或$B \subseteq A​$
$A​$是$B​$的真子集:$A \subset B​$或$B \subset A​$
$x​$是$A​$的一个元素:$x \in A​$
$x​$不是$A​$的一个元素:$x \notin A​$

1.2集合的交并差补

$A$和$B$的并集:$A\cup B={x|x\in A或x\in B}$
$A$和$B$的交集:$A\cap B={x|x\in A且x\in B}$
$A$和$B$的差集:$A - B={x|x\in A且x\notin B}$
若$B\subseteq A$我们也称$A−B$为$B$的(关于$A$)补,记作:$\overline B(A)​$

1.3集合的并的推广

设$I​$是某些标号的集合我们将$\displaystyle \bigcup_{i\in I}A_i={x|存在i\in I,使得x\in A_i}​$

1.4A的幂集

$A$的所有子集的集合,记作$2^A={B|B\subseteq A}​$

1.5笛卡尔乘积

$A\times B={(a,b)|a\in A且b\in B}$

1.6集合之间的关系

由$A$到$B$的关系是$A×B$的任何子集。若$A=B$,则称为$A$上的关系。若$R$为$A$到$B$的关系,当$(a,b)$在$R$内时,可写成$aRb​$

1.7集合关系的性质

设$R$是集合$A$上的关系,则有
(1)若对$A$中的任一元素$a$,都有$aRa$,则称$R$是自反的
(2)若对$A$中的任何元素$a,b$,从$aRb$能够推到出$bRa$,则称$R$是对称的
(3)若$a,b,c$是$A$中的元素,从$aRb$和$bRc$能够推出$aRc$,则称$R$是传递的
若关系$R​$同时是自反的,对称的和传递的,则称之为等价关系
2018-09-22 15:28:12

参考资料


1.《形式语言与自动机》陈有祺编著

Back to top