邏輯代數(shù)與集合理論的融合教學(xué)

熊小兵

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

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

中圖分類(lèi)號(hào)：G642? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2022）18-0120-03

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

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

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

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

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

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

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

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

定義1：命題的真假可以用常量1（表示“真”）和0（表示“假”）來(lái)表示，稱(chēng)為邏輯常量。

定義2：命題本身可以用變量（常用大寫(xiě)字母）來(lái)表示，稱(chēng)為邏輯變量。

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

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

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

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

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

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

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

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

邏輯代數(shù)的公理系統(tǒng)[1-3]：對(duì)任意的邏輯變量[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];

互補(bǔ)律： [A+A=1]，[A?A=0]

2 集合與命題

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

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

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

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

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

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

定律：命題[P：x∈A?B]可以用邏輯變量[A]和[B]的“與”運(yùn)算[A?B]來(lái)表達(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]的“或”運(yùn)算[A+B]來(lái)表達(dá)。

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

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

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

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

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

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

對(duì)邏輯變量有：[A?B=B?A]、[A+B=B+A]

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

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

對(duì)邏輯變量有：

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

分配律 對(duì)集合有：

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

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

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

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

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

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

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

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

[U=Φ]，[Φ=U]

對(duì)邏輯常量有：[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 對(duì)集合有：[A?A=A]，[A?A=A];對(duì)邏輯變量有：[A?A=A]，[A+A=A]

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

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

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

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

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

定律6 對(duì)集合有：[A?B=A?B]，[A?B=A?B]

對(duì)邏輯變量有：[A?B=A+B]，[A+B=A?B]

定律7 對(duì)集合有：

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

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

定律8 對(duì)集合有：

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

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

對(duì)邏輯變量有：[A?B+A?C+B?C=A?B+A?C]

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

4 其他集合和邏輯問(wèn)題

1）差集問(wèn)題

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

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

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

3）相等問(wèn)題

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

類(lèi)似地，對(duì)集合有：[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）不等問(wèn)題

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

類(lèi)似地，對(duì)集合有：[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）集合的劃分

對(duì)邏輯變量有：

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

對(duì)集合有：

[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)式

對(duì)任意的邏輯表達(dá)式[F]，[F]可以轉(zhuǎn)換成基本與或式、最簡(jiǎn)與或式以及標(biāo)準(zhǔn)與或式，也可以轉(zhuǎn)換成基本或與式、最簡(jiǎ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]

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

例如：

5 結(jié)語(yǔ)

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

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

參考文獻(xiàn)：

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

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

[3] 康磊，李潤(rùn)洲.數(shù)字電路設(shè)計(jì)及Verilog HDL實(shí)現(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)編輯：王力】