段景輝

(三亞學(xué)院信息與智能工程學(xué)院,海南三亞 572022)

命題邏輯是以原子命題為基本單位,符號化和形式化地描述人類思維的規(guī)律。人類思維的規(guī)律是以排中律和矛盾律為基礎(chǔ)的規(guī)律。排中律思想是二者的選擇,只能選擇其一,必選擇其一,兩者不可兼而得之。矛盾律思想是二者的選擇,可以兼而得之。

集合恒等式是指集合運算的恒等式,集合運算是集合族上的運算,即以集合為運算對象、以集合為結(jié)果的運算。所以集合恒等式本質(zhì)上就是集合相等問題。集合恒等式的證明,是學(xué)習(xí)集合論的最基本要求和技能的體現(xiàn),也是思維方式的一種鍛煉[1]。

根據(jù)集合對象的確定性,對任何元素a和任何集合A,或者a∈A或者aA,兩者必居其一,也只居其一,這條邏輯學(xué)中的排中律,再結(jié)合命題公式的真值表,本文提出構(gòu)造集合成員表來證明集合恒等式的方法。

集合恒等式的證明常用方法是:(1)邏輯演算法;(2)集合演算法;(3)集合相等證明法。

1 邏輯演算法

邏輯演算法亦是集合定義證明法。證明思想是從集合運算的邏輯定義出發(fā),設(shè)任意元素屬于恒等式左邊(或右邊)集合,根據(jù)邏輯演算,等價出恒等式右邊(或左邊)。

設(shè)A、B 為任意集合。

(l)A ∪ B稱為A與B的并集,由所有屬于A或?qū)儆贐的元素組成,定義為:

A ∪ B＝｛x|x∈A∨x∈B｝,其中“ ∪ ”稱為并運算。因此,x∈A ∪ B ? x∈A∨x∈B。

(2)A ∩ B稱為A與B的交集,由屬于A同時又屬于B的所有元素組成,定義為:

A ∩ B＝｛x|x∈A∧x∈B｝,其中“ ∩ ”稱為交運算。因此,x∈A ∩ B ? x∈A∧x∈B。

(3)A-B稱為A與B的差集,由屬于A而不屬于B的所有元素組成,定義為:

例如,吸收律A ∩ (A ∪ B)＝A,A ∪ (A ∩ B)＝A。

證明:對任意x,

x∈A ∩ (A ∪ B) ? x∈A∧x∈(A ∪ B)

? x ∈A

x∈A ∪ (A ∩ B) ? x∈A∨x∈(A ∩ B)

? x∈(A ∩ U)∨x∈(A ∩ B)

? x∈A ∩ (U ∪ B)

? x ∈A ∩ U

? x ∈A

2 集合演算法

集合演算法亦是集合恒等式法。證明思想是從集合恒等式的左邊(或右邊)開始,利用已知的集合恒等式作等價代換處理,直到集合恒等式的右邊(或左邊)。有的時候,也需要從恒等式的左右兩邊同時利用集合恒等式法,等價出中間一個相同的集合。

例如,吸收律A ∩ (A ∪ B)＝A。

表1 集合成員表Tab.1 Set member table

例如,A-(B ∪ C)＝(A-B) ∩ (A-C)。

證明:左邊＝A-(B ∪ C)

右邊＝(A-B) ∩ (A-C)

因為:左邊=右邊。

所以:恒等式成立。

此例證明中,還可由(1)式直接等價演算右邊。

例如:對任意集合A、B、C、D,證明 A ? B, A - B=,A ∪ B = B, A ∩ B = A四命題等價。

證明:設(shè)4個命題為P、Q、R、S,即證P? Q? R? S? P,從而就證實4個命題等價。

(Q? R):為證A ∪ B＝B,需證

1)B ? A ∪ B。但由定理4.2之(1),此已得證。

2)A ∪ B ? B。設(shè)x為A ∪ B中任一元素,從而x∈A或x∈B。當x∈B時目的已達到。當x∈A時,若xB,則x∈A-B,此與A-B＝矛盾。故x∈B?？傊?A ∪ B中元素x必為B中元素。

綜合1)、2)可知A ∪ B＝B,R得證。

(R? S):因A ∪ B＝B,故A ∩ B＝A ∩ (A ∪ B)＝A(吸收律)。S得證。

(S? P):設(shè)A ∩ B＝A。要證A ? B,現(xiàn)設(shè)x為A中任一元素。由A ∩ B＝A,可得x∈A ∩ B從而知x∈B。故A ? B,P得證。

注意,上述“循環(huán)論證”只是證明若干命題相互等價的方法;在此過程中,那些命題自身一個也沒有得到證明。

3 集合相等證明法

集合相等證明法是根據(jù)集合相等定義(即外延性原理)進行證明,即A＝B,當且僅當A ? B且B ? A。

景花廠的員工增到了七十多人，仍忙不過來，訂單像鵝毛，一片片飛來。王義山對我很敬佩，不時在阿花面前夸我，說我比高文鵬強，技術(shù)水平高，質(zhì)量要求嚴，還會拉訂單。高文鵬就是我的前任。我也禮節(jié)性地贊揚王義山，生產(chǎn)才是工廠的生命，你也功不可沒，阿花經(jīng)常表揚你。阿花說，你們是我的左膀右臂，你們合作得好，我就輕松了許多。怎么樣，最近人手夠嗎？王義山說，差不多了，機位快坐滿了，車間也顯得有點擁擠。我們邊說邊進了車間。

例如,分配律A ∩ (B ∪ C)＝(A ∩ B) ∪ (A ∩ C)。

證明:為了證明A ∩ (B ∪ C)＝(A ∩ B) ∪ (A ∩ C),只需要證明

A ∩ (B ∪ C) ? (A ∩ B) ∪ (A ∩ C)和(A ∩ B) ∪ (A ∩ C) ? A ∩(B ∪ C)。

首先,設(shè)x∈A ∩ (B ∪ C),那么x∈A且x∈B ∪ C。根據(jù)集合并集定義,得x∈A且x∈B或x∈C;根據(jù)集合交集定義,再利用命題公式的分配律,可得到,x∈A且x∈B或x∈A且x∈C。根據(jù)集合交集定義,可得x∈(A ∩ B) ∪ (A ∩ C)。因此,得證A ∩ (B ∪ C) ? (A ∩ B) ∪ (A ∩ C)。

然后,設(shè)x∈(A ∩ B) ∪ (A ∩ C),那么x∈A ∩ B或x∈A ∩ C。根據(jù)集合交集定義,得x ∈A 且x ∈B或x ∈A 且x ∈C;根據(jù)集合并集定義,再結(jié)合命題公式的分配律,可得到x ∩ A ∪ (B ∩ C)。因此,得證(A ∩ B) ∪ (A ∩ C) ? A ∩ (B ∪ C)。

綜上,A ∩ (B ∪ C) ? (A ∩ B) ∪ (A ∩ C)且(A ∩ B) ∪ (A ∩ C)? A ∩ (B ∪ C),所以A ∩ (B ∪ C)＝(A ∩ B) ∪ (A ∩ C)。

上述三種集合恒等式的證明方法是較為常用的方法,也是學(xué)習(xí)集合論必須掌握的證明方法。其中,邏輯演算法和集合相等證明法,都是基于集合運算的邏輯定義進行的。由此可以看出,集合運算的恒等式與命題公式的邏輯等價式是非常類似的。所以,在命題公式的真值表的基礎(chǔ),提出了集合恒等式的另一種證明方法——集合成員表法[2]。

表2 集合成員表Tab.2 Set member table

4 集合成員表法

集合成員表類似命題公式的真值表。

首先, 考慮一個元素可能屬于的集合的每一種組合,用1表示元素屬于一個集合,用0表示元素不屬于一個集合。

其次,再證明在同樣的集合組合中的元素屬于恒等式兩邊的集合。

(2)集合成員表法的作法。

首先,確定恒等式中不同集合的個數(shù)n,那么成員表就有2n+1行(第1行是表頭)。

其次,恒等式兩邊的表達式分別表示,確定恒等式左邊的集合運算符個數(shù)m,右邊恒等式的集合運算符個數(shù)z,那么就有n+m+z列。

(3)舉例。

例1:證明分配律A ∩ (B ∪ C)＝(A ∩ B) ∪ (A ∩ C)。

證明:作A ∩ (B ∪ C)＝(A ∩ B) ∪ (A ∩ C)的成員表,如表1所示。

由表1的第五列和第八列可以看出,其值完全一樣,所以A ∩ (B ∪ C)＝(A ∩ B) ∪ (A ∩ C)得證。

表3 集合成員表Tab.3 Set member table

例3:證明A⊕B＝(A ∪ B)-(A ∩ B)。

證明:作A⊕B＝(A ∪ B)-(A ∩ B)的成員表,如表3所示。

由表3的第三列和第六列可以看出,其值完全一樣,所以A⊕B＝(A ∪ B)-(A ∩ B)成立。

5 總結(jié)

集合論是一門研究數(shù)學(xué)基礎(chǔ)的學(xué)科,集合恒等式是集合論的最基礎(chǔ)內(nèi)容,集合恒等式的證明,是人們拓展集合運算的一種方式,也是人類思維的一種形式體現(xiàn)。

集合恒等式的證明,方法很多,本文的集合成員表法是基于命題公式的真值表而提出的,這種方法形式簡單、易于掌握,更重要的是它揭示了集合恒等式與命題公式恒等式之間邏輯特性。

集合成員表證明方法,實質(zhì)是將命題演算中的排中律、矛盾律運用在集合中,這種方法不僅可以直接證明集合恒等式，還可以體現(xiàn)出邏輯思維。