熊小兵

摘要：文章在對邏輯問題進(jìn)行代數(shù)建模的基礎(chǔ)上，闡釋了集合理論和邏輯代數(shù)的內(nèi)在聯(lián)系，對集合和邏輯代數(shù)的基本理論做了對比分析，同時也對相關(guān)的問題做了探討，說明了邏輯代數(shù)和集合理論融合教學(xué)的切實可行性。

關(guān)鍵詞：集合;命題;邏輯;邏輯代數(shù)

中圖分類號：G642? ? ? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2022）18-0120-03

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

計算機(jī)相關(guān)專業(yè)一般都有兩門必修基礎(chǔ)課程：離散數(shù)學(xué)和數(shù)字邏輯。離散數(shù)學(xué)的一個重點章節(jié)是布爾代數(shù)，數(shù)字邏輯的一個重點章節(jié)是邏輯代數(shù)。實際上，布爾代數(shù)就是邏輯代數(shù)，二者只是采用了不同的表述形式而已。

數(shù)字邏輯是計算機(jī)硬件技術(shù)的重要基礎(chǔ)，學(xué)好數(shù)字邏輯的基礎(chǔ)是先學(xué)好邏輯代數(shù)。邏輯代數(shù)的本質(zhì)是用代數(shù)的方法研究邏輯問題，即邏輯問題的代數(shù)化。遺憾的是，絕大多數(shù)學(xué)生在中學(xué)時代幾乎沒有系統(tǒng)地學(xué)習(xí)過邏輯問題的基礎(chǔ)理論。如何在短時間內(nèi)學(xué)好邏輯代數(shù)就是學(xué)生面臨的一個挑戰(zhàn)。

一般來說，效率最高的學(xué)習(xí)方法應(yīng)該是利用曾經(jīng)學(xué)過并且已經(jīng)掌握的知識來幫助我們學(xué)習(xí)并掌握新的知識，也就是主動充分利用學(xué)習(xí)遷移規(guī)律。

中學(xué)數(shù)學(xué)中學(xué)習(xí)過的集合及其基礎(chǔ)理論就是可以利用的對象。

邏輯問題實際上就是命題的真假及其相互關(guān)系的問題。邏輯代數(shù)的基本公理、定理、公式和集合理論的相關(guān)內(nèi)容驚人相似。為說明這種相似性，首先有必要通過命題溝通集合的基本運算和基本邏輯運算之間的關(guān)系，在此基礎(chǔ)上，集合問題就變成了邏輯問題。

1 邏輯問題的代數(shù)模型

邏輯問題實際上就是命題的真假及其相互關(guān)系的問題，邏輯代數(shù)的實質(zhì)就是用代數(shù)的方法來研究邏輯問題，這就需要為邏輯問題建立一個代數(shù)模型。

定義1：命題的真假可以用常量1（表示“真”）和0（表示“假”）來表示，稱為邏輯常量。

定義2：命題本身可以用變量（常用大寫字母）來表示，稱為邏輯變量。

邏輯變量的值就是命題的真假，即邏輯常量。值恒為1的邏輯變量代表的就是永真命題，而值恒為0的邏輯變量代表的就是永假命題。

設(shè)A和B為任意的兩個命題，利用A和B可以構(gòu)造一些新的命題。

定義3：命題“A與B”為“真”當(dāng)且僅當(dāng)A和B同時為“真”，稱為A和B的“與”命題，簡稱“與”。

定義4：命題“A或B”為“假”當(dāng)且僅當(dāng)A和B同時為“假”，稱為A和B的“或”命題，簡稱“或”。

定義5：命題“非A”為“真”當(dāng)且僅當(dāng)A為“假”，稱為A的“非”命題，簡稱“非”。

定義3～5實際上就是規(guī)定了命題之間的3種基本運算關(guān)系，也就是邏輯變量之間的3種基本運算：與、或、非，及其運算規(guī)則。

在數(shù)字邏輯中，習(xí)慣上用[A?B]或[AB]表示A和B的“與”，即“A與B”;[A+B]表示A和B的“或”，即“A或B”;[A]表示A的“非”，即“非A”。

基于上述運算規(guī)則，可以歸納總結(jié)出邏輯問題的代數(shù)模型，也就是邏輯代數(shù)的公理系統(tǒng)。

邏輯代數(shù)的公理系統(tǒng)[1-3]：對任意的邏輯變量[A]、[B]、[C]，以及邏輯常量1和0，有：

交換律： [A?B=B?A]、[A+B=B+A]

結(jié)合律： [（A?B）?C=A?（B?C）]、[（A+B）+C=A+（B+C）]

分配律： [A?（B+C）=A?B+A?C]、

[A+B?C=（A+B）（A+C）]

0-1律： [A+1=1]，[A?1=A];[A+0=A]，[A?0=0];

互補律： [A+A=1]，[A?A=0]

2 集合與命題

設(shè)：[U]為全集，[Φ]為空集，[A]和[B]是[U]的任意兩個子集，[x∈U]。

由集合[U]可以確定命題[P：x∈U]，命題[P：x∈U]永遠(yuǎn)成立，可以用邏輯常量1（真）來表達(dá)。

由集合[Φ]可以確定命題[P：x∈Φ]，命題[P：x∈Φ]永遠(yuǎn)為假，可以用邏輯常量0（假）來表達(dá)。

由集合[A]可以確定命題[P：x∈A]，命題[P：x∈A]可能為真或假，可以直接用邏輯變量[A]來表示。

由補集[A]可以確定命題[P：x∈A]，命題[P：x∈A]可能為真或假，可以用邏輯變量[A]的“非”[A]來表達(dá)。

由交集[A?B]可以確定命題[P：x∈A?B]，命題[P：x∈A?B]可能為真或假。

定律：命題[P：x∈A?B]可以用邏輯變量[A]和[B]的“與”運算[A?B]來表達(dá)。

證明：[P：x∈A?B?P：x∈A and x∈B][?P：x∈A and P：x∈B][?A?B]

由并集[A?B]可以確定命題[P：x∈A?B]，命題[P：x∈A?B]可能為真或假。

定律：命題[P：x∈A?B]可以用邏輯變量[A]和[B]的“或”運算[A+B]來表達(dá)。

證明：[P：x∈A?B?P：x∈A or x∈B?A：x∈A or B：x∈B?A+B]

以上建立了集合和命題之間的聯(lián)系，以及集合的3種基本運算（交、并、補）和命題的3種基本運算（即邏輯運算：與、或、非）之間的聯(lián)系。

3 集合的基本理論和邏輯代數(shù)的基本理論

將集合看成命題時，集合的很多運算規(guī)律也適用于命題。

設(shè)[U]為全集，[A]、[B]、[C]是[U]的任意子集，同時也用[A]、[B]、[C]表示任意的邏輯變量，以下是集合理論[4]-[5]和邏輯代數(shù)的基本定律[1-3]之間的對比分析。

交換律 對集合有：[A?B=B?A]、[A?B=B?A];

對邏輯變量有：[A?B=B?A]、[A+B=B+A]

結(jié)合律 對集合有：

[（A?B）?C=A?（B?C）]、[（A?B）?C=A?（B?C）]

對邏輯變量有：

[（A?B）?C=A?（B?C）]、[（A+B）+C=A+（B+C）]

分配律 對集合有：

[A?（B?C）=A?B?A?C]、[A?（B?C）=（A?B）?（A?C）]

對邏輯變量有：[A?（B+C）=A?B+A?C]、[A+B?C=（A+B）（A+C）]

0-1律 對集合有：[A?U=U]，[A?U=A];[A?Φ=A]，[A?Φ=Φ];

對邏輯變量有：[A+1=1]，[A?1=A];[A+0=A]，[A?0=0];

互補律 對集合有：[A?A=U]，[A?A=Φ];對邏輯變量有：[A+A=1]，[A?A=0]

在此基礎(chǔ)上，可以很容易得到集合理論和邏輯代數(shù)的其他常用定律：

定律1 對全集和空集有：[Φ?Φ=Φ]，[Φ?U=Φ]，[U?Φ=Φ]，[U?U=U]

[Φ?Φ=Φ]，[Φ?U=U]，[U?Φ=U]，[U?U=U]

[U=Φ]，[Φ=U]

對邏輯常量有：[0?0=0]，[0?1=0]，[1?0=0]，[1?1=1];[0+0=0]，

[0+1=1]，[1+0=1]，[1+1=1]，[1=0]，[0=1]

定律2 對集合有：[A?A=A]，[A?A=A];對邏輯變量有：[A?A=A]，[A+A=A]

定律3 對集合有：[A?A?B=A]，[A?（A?B）=A]

對邏輯變量有：[A+A?B=A]，[A（A+B）=A]

定律4 對集合有：[A?A?B=A?B]，[A?（A?B）=A?B]

對邏輯變量有：[A+A?B=A+B]，[A（A+B）=A?B]

定律5 對集合有：[A=A];對邏輯變量有：[A=A]

定律6 對集合有：[A?B=A?B]，[A?B=A?B]

對邏輯變量有：[A?B=A+B]，[A+B=A?B]

定律7 對集合有：

[A?B?A?B=A]，[（A?B）?（A?B）=A]

對邏輯變量有：[A?B+A?B=A]，[（A+B）（A+B）=A]

定律8 對集合有：

[A?B?A?C?B?C=A?B?A?C]

[（A?B）（A?C）（B?C）=（A?B）（A?C）]

對邏輯變量有：[A?B+A?C+B?C=A?B+A?C]

[（A+B）（A+C）（B+C）=（A+B）（A+C）]

4 其他集合和邏輯問題

1）差集問題

由差集[A-B=A?B]可以確定命題[P：x∈A?B]，命題[P：x∈A?B]可以用邏輯表達(dá)式[AB]來表示。

2）集合的包含關(guān)系與命題的蘊含關(guān)系

集合的包含關(guān)系[A?B]可以確定命題[P：A→B]，命題[P：A→B]可以用邏輯表達(dá)式[A+B=AB]來表示。

3）相等問題

對邏輯變量有：[A=B?A⊙B=1?AB+AB=1]

類似地，對集合有：[A=B?A?B?A?B=U]

分析：[A=B?A?B?A?B=A?A=U]

[A?B?A?B=U?B?（A?B?A?B）=B]

[?B?A?B?B?A?B=B]

[?A?B?Φ=B]

[?A?B=B]

[?B?A]

同理，[A?B]。故[A=B]

4）不等問題

對邏輯變量有：[A≠B?A⊕B=1?AB+AB=1]

類似地，對集合有：[A≠B and A=B?A?B?A?B=U]

分析：[A≠B and A=B?A?B?A?B=U]

[A?B?A?B=U?A?B?A?B=Φ]

[?（A?B）?（A?B）=Φ]

[?A?B?A?B=Φ]

[A?B=Φ and A?B=Φ]

[?A≠B and A=B]

5）集合的劃分

對邏輯變量有：

[1=ABC+ABC+ABC+ABC+ABC+ABC+ABC+ABC]

[0=（A+B+C）（A+B+C）（A+B+C）（A+B+C）? ? ?（A+B+C）（A+B+C）（A+B+C）（A+B+C）]

對集合有：

[U=A?B?C?A?B?C?A?B?C?A?B?C? ??A?B?C?A?B?C?A?B?C?A?B?C]

[Φ=（A?B?C）?（A?B?C）?（A?B?C）?（A?B?C）? ??（A?B?C）?（A?B?C）?（A?B?C）?（A?B?C）]

6）集合表達(dá)式的標(biāo)準(zhǔn)式

對任意的邏輯表達(dá)式[F]，[F]可以轉(zhuǎn)換成基本與或式、最簡與或式以及標(biāo)準(zhǔn)與或式，也可以轉(zhuǎn)換成基本或與式、最簡或與式以及標(biāo)準(zhǔn)或與式。

例如：[F（A，B，C）=ABC+AC][=AB+C+AC]

[=ABC+ABC+ABC+ABC+ABC+ABC]

[=ABC+ABC+ABC+ABC+ABC+ABC]

類似地，對任意的集合運算表達(dá)式[F]，[F]也有類似的形式，可以稱為基本交并式、最簡交并式、標(biāo)準(zhǔn)交并式，以及基本并交式、最簡并交式、標(biāo)準(zhǔn)并交式。或者，借用離散數(shù)學(xué)中布爾代數(shù)的相關(guān)術(shù)語，分別稱為析取式、合取式[6]。

例如：

5 結(jié)語

基于上述分析，在數(shù)字邏輯課程的邏輯代數(shù)部分教學(xué)過程中可以利用學(xué)習(xí)遷移規(guī)律，將學(xué)生在中學(xué)時代就已經(jīng)初步接觸過的集合論的有關(guān)理論（重點是集合的運算規(guī)律）遷移到邏輯代數(shù)的教學(xué)中來，幫助大家快速掌握邏輯代數(shù)。

此外，為了提高學(xué)生學(xué)習(xí)邏輯代數(shù)的效率和效果，還可以考慮借力差不多同時開設(shè)的離散數(shù)學(xué)中的布爾代數(shù)理論。在講授邏輯代數(shù)之初可以告訴學(xué)生，在學(xué)習(xí)過程中，可以將數(shù)字邏輯的邏輯代數(shù)部分和離散數(shù)學(xué)的布爾代數(shù)部分結(jié)合起來學(xué)習(xí)，互相參照，以此提高學(xué)習(xí)效率，增強學(xué)習(xí)效果！

參考文獻(xiàn)：

[1] 陳光夢.數(shù)字邏輯基礎(chǔ)[M].2版.上海：復(fù)旦大學(xué)出版社，2007.

[2] 何建新，高勝東.數(shù)字邏輯設(shè)計基礎(chǔ)[M].北京：高等教育出版社，2012.

[3] 康磊，李潤洲.數(shù)字電路設(shè)計及Verilog HDL實現(xiàn)[M].2版.西安：西安電子科技大學(xué)出版社，2019.

[4] 張峰.集合論基礎(chǔ)教程[M].北京：清華大學(xué)出版社，2021.

[5] 劉坤起.集合論基礎(chǔ)[M].北京：電子工業(yè)出版社，2014.

[6] 劉鐸.離散數(shù)學(xué)及應(yīng)用[M].2版.北京：清華大學(xué)出版社，2018.

【通聯(lián)編輯：王力】