解释 TOC 中的 Set 关系和操作?
让我们首先了解计算理论(TOC)中的子集。
子集
如果A和B是集合,则A⊂B(A是B的子集)如果w∈A这意味着w∈B;即A的每个元素也是B的元素。
例子
设A={ab,ba}和B={ab,ba,aaa}。则A⊂B,但B⊄A。
设A={x,xx,xxx,...}和B={∧,x,xx,xxx,...}.那么,A⊂B,但B⊄A。
设A={ba,ab}和B={aa,bb}。然后,A⊄B和B⊄A。
定义
设A和B为2组。如果A⊂B且B⊂A,则A=B。
例子
设A={ab,ba}和B={ab,ba}。则A⊂B和B⊂A,所以A=B。
设A={ab,ba}和B={ab,ba,aaa}。则A⊂B,但B⊄A,所以A⊄B。
设A={x,xx,xxx,...}和B={xn|n≥1}。则A⊂B和B⊂A,所以A=B。
联盟
给定两组字符串S和T,我们可以定义S+T={w:w∈Sorw∈T}为S和T的并集,即S+T由S或T(或两者兼有)。
例子
假设S={ac,bb}和T={aa,bb,a}。然后S+T={ac,bb,aa,a}。
路口
给定两个字符串集合S和T,我们可以定义S∩T={w:w∈Sandw∈T},它是S和T的交集,即S∩T由两个S中的字符串组成和T。
当S∩T=∅时,集合S和T是不相交的。
例子
设S={ab,bb}和T={aa,bb,a}。那么S∩T={bb}。
设S={ab,bb}和T={ab,bb}。那么S∩T={ab,bb}。
设S={ab,bb}和T={aa,ba,a}。然后S∩T=∅
区别
对于任意2个字符串集合S和T,我们可以定义S−T={w:w∈S,w⊄T}。
例子
令S={a,b,bb,bbb}和T={a,b,bab}。然后S−T={b,bbb}。
设S={ab,ba}和T={ab,ba}。则S−T=∅。
笛卡尔积
两个集合A和B的笛卡尔积是有序对的集合A×B={(x,y):x∈A,y∈B}。
例子
如果A={ab,ba,bbb}且B={bb,ba},则
A×B={(ab,bb),(ab,ba),(ba,bb),(ba,ba),(bbb,bb),(bbb,ba)}。
注意(ab,ba)∈A×B。
另外,请注意
B×A={(bb,ab),(bb,ba),(bb,bbb),(ba,ab),(ba,ba),(ba,bbb)}。
(bb,ba)∈B×A,
但是(bb,ba)⊄A×B,所以B×A⊄A×B。
我们可以定义超过2个集合的笛卡尔积。