在計算理論(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。

我們可以為兩個以上集合定義笛卡爾積。

更新於: 2021年6月16日

2K+ 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告