在計算理論(TOC)中解釋集合關係和運算?
讓我們從瞭解計算理論(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 ∈ S 或 w ∈ 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 ∈ S 且 w ∈ 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, bb, 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。
我們可以為兩個以上集合定義笛卡爾積。