邏輯代數與集合理論的融合教學

熊小兵

摘要：文章在對邏輯問題進行代數建模的基礎上，闡釋了集合理論和邏輯代數的內在聯系，對集合和邏輯代數的基本理論做了對比分析，同時也對相關的問題做了探討，說明了邏輯代數和集合理論融合教學的切實可行性。

關鍵詞：集合;命題;邏輯;邏輯代數

中圖分類號：G642? ? ? ? 文獻標識碼：A

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

開放科學（資源服務）標識碼（OSID）：

計算機相關專業一般都有兩門必修基礎課程：離散數學和數字邏輯。離散數學的一個重點章節是布爾代數，數字邏輯的一個重點章節是邏輯代數。實際上，布爾代數就是邏輯代數，二者只是采用了不同的表述形式而已。

數字邏輯是計算機硬件技術的重要基礎，學好數字邏輯的基礎是先學好邏輯代數。邏輯代數的本質是用代數的方法研究邏輯問題，即邏輯問題的代數化。遺憾的是，絕大多數學生在中學時代幾乎沒有系統地學習過邏輯問題的基礎理論。如何在短時間內學好邏輯代數就是學生面臨的一個挑戰。

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

中學數學中學習過的集合及其基礎理論就是可以利用的對象。

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

1 邏輯問題的代數模型

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

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

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

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

設A和B為任意的兩個命題，利用A和B可以構造一些新的命題。

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

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

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

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

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

基于上述運算規則，可以歸納總結出邏輯問題的代數模型，也就是邏輯代數的公理系統。

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

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

結合律： [（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 集合與命題

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

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

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

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

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

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

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

證明：[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]來表達。

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

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

3 集合的基本理論和邏輯代數的基本理論

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

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

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

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

結合律 對集合有：

[（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]

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

定律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]可以用邏輯表達式[AB]來表示。

2）集合的包含關系與命題的蘊含關系

集合的包含關系[A?B]可以確定命題[P：A→B]，命題[P：A→B]可以用邏輯表達式[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）集合表達式的標準式

對任意的邏輯表達式[F]，[F]可以轉換成基本與或式、最簡與或式以及標準與或式，也可以轉換成基本或與式、最簡或與式以及標準或與式。

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

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

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

類似地，對任意的集合運算表達式[F]，[F]也有類似的形式，可以稱為基本交并式、最簡交并式、標準交并式，以及基本并交式、最簡并交式、標準并交式。或者，借用離散數學中布爾代數的相關術語，分別稱為析取式、合取式[6]。

例如：

5 結語

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

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

參考文獻：

[1] 陳光夢.數字邏輯基礎[M].2版.上海：復旦大學出版社，2007.

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

[3] 康磊，李潤洲.數字電路設計及Verilog HDL實現[M].2版.西安：西安電子科技大學出版社，2019.

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

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

[6] 劉鐸.離散數學及應用[M].2版.北京：清華大學出版社，2018.

【通聯編輯：王力】