關(guān)于分配格的判定問(wèn)題

郭 蕓， 王朝暉

（蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇蘇州 215006）

分配格的判定是離散數(shù)學(xué)課程中的一個(gè)基本問(wèn)題，它要求學(xué)生在對(duì)基本概念有深入理解的同時(shí)，又具備一定的計(jì)算能力，這就導(dǎo)致學(xué)生在處理該類問(wèn)題時(shí)經(jīng)常會(huì)犯錯(cuò)，甚至離散數(shù)學(xué)教材的配套習(xí)題解答書(shū)在該問(wèn)題上也出錯(cuò).探索如何有效解決這一教學(xué)問(wèn)題顯得很有必要.在思考過(guò)程中我們想到，由于離散數(shù)學(xué)的教學(xué)對(duì)象主要是計(jì)算機(jī)學(xué)院的學(xué)生，既然他們已經(jīng)具備一定的計(jì)算機(jī)運(yùn)用能力，那為何不因地制宜結(jié)合計(jì)算機(jī)這一工具呢？事實(shí)證明我們這個(gè)想法在教學(xué)實(shí)踐中取得了較好的效果.下面本文通過(guò)一個(gè)具體的例子來(lái)對(duì)我們的做法進(jìn)行說(shuō)明，希望能給同仁有所借鑒.我們發(fā)現(xiàn)習(xí)題解答書(shū)中該例子的答案有錯(cuò)，因此具有一定的典型性.

1 分配格的定義和判定定理

關(guān)于分配格的定義，可以按照偏序集－格－分配格的順序來(lái)理解，其定義如下：

在判斷一個(gè)具體的格是否是分配格時(shí)，只需驗(yàn)證（1）式（或（2）式）是否成立即可.盡管如此，注意到（1）式中a，b，c三個(gè)元素是任取的，即當(dāng)且僅當(dāng)對(duì)A中任意三個(gè)元素（1）式都成立時(shí)，〈A，≤〉是分配格；只要存在三個(gè)元素a0，b0，c0，不滿足（1）式，就可說(shuō)明〈A，≤〉不是分配格，所以當(dāng)A中所含元素較多時(shí)，利用定義來(lái)判定的計(jì)算量將很大.文獻(xiàn)［2］給出了如下一個(gè)判定定理：

定理1［2］格〈A，≤〉是分配格當(dāng)且僅當(dāng)A中不含與鉆石格或五角格同構(gòu)的子格.其中鉆石格和五角格分別如圖1和圖2所示.

可以看出，與定義3相比，定理1相對(duì)直觀便捷，因此學(xué)生大多傾向于用后者來(lái)判定.但在解題過(guò)程中，只要對(duì)該定理理解不透徹，就容易出錯(cuò).下面我們舉例說(shuō)明.

圖2

圖1

圖3

2 一個(gè)典型例子

這里以文獻(xiàn)［1］中第六章第二節(jié)習(xí)題（2）的圖（a）（如圖3所示）為例，學(xué)生在解這道題時(shí)出現(xiàn)的錯(cuò)誤具有一定的典型性.

該題要求判斷圖3表示的格是否是分配格.學(xué)生很自然會(huì)想到運(yùn)用定理1這樣來(lái)判定：因?yàn)閳D3表示的格中有與五角格同構(gòu)的子格，所以它不是分配格.這一錯(cuò)誤解答相當(dāng)普遍，幾乎每屆學(xué)生都會(huì)出現(xiàn)，能夠得出正確結(jié)果的只是鳳毛麟角.文獻(xiàn)［1］的配套習(xí)題解答書(shū)［3］中給出的也是這一錯(cuò)誤解答，甚至很多教師在沒(méi)有深入思考的情況下也會(huì)采納這個(gè)解法.下面結(jié)合該例子探討如何解決學(xué)生在求解該類問(wèn)題時(shí)容易出錯(cuò)的教學(xué)問(wèn)題.

學(xué)生對(duì)答案書(shū)的迷信，加大了我們糾正錯(cuò)誤的難度.我們發(fā)現(xiàn)，在教學(xué)尤其是課堂管理過(guò)程中，權(quán)威效應(yīng)是不容忽視的，答案書(shū)在學(xué)生的觀念中就具有一定的權(quán)威性，所以，必須通過(guò)有效的方法，引導(dǎo)學(xué)生自己來(lái)發(fā)現(xiàn)錯(cuò)誤.既然學(xué)生具有計(jì)算機(jī)專業(yè)這一背景，我們就思考能否借助計(jì)算機(jī)這一工具來(lái)輔助教學(xué).由于概念的原始定義一般都比較容易理解，所以可以考慮先放棄從定理1入手，而是回到原始定義嘗試用定義3來(lái)判定.因?yàn)閳D3中的格有6個(gè)點(diǎn)，所以需要對(duì)120（即A36）組數(shù)據(jù)分別判斷分配等式（1）是否成立.此時(shí)，手工計(jì)算很是麻煩，但可以借助計(jì)算機(jī)程序來(lái)處理.我們可以引導(dǎo)學(xué)生編一個(gè)通過(guò)定義來(lái)判斷任意一個(gè)格是否是分配格的小程序.

由于格本質(zhì)上是一種關(guān)系，注意到用哈斯圖表示的關(guān)系不便于計(jì)算機(jī)實(shí)現(xiàn)，可以將哈斯圖轉(zhuǎn)化為關(guān)系矩陣，而關(guān)系矩陣就可以用程序設(shè)計(jì)語(yǔ)言的數(shù)組來(lái)表達(dá).設(shè)格為〈A，≤〉，以下是我們指導(dǎo)學(xué)生編寫(xiě)的VB程序的算法：

圖4

在圖3的格中，很多學(xué)生會(huì)提出B1＝｛a，c，d，e，f｝，B2＝｛a，b，c，d，f｝兩個(gè)五元素子集與五角格同構(gòu)，但它們關(guān)于∨或∧不封閉，因而不是子格.不妨考察B2，b，c∈B2，但b∧c＝e?B2.事實(shí)上，符合子格要求的五元素子集只有B3＝｛a，b，c，e，f｝，B4＝｛a，b，d，e，f｝兩個(gè)，而它們顯然不與五角格同構(gòu).因此，由定理1可知圖3的格是分配格.

解釋完以后，可以讓學(xué)生思考兩個(gè)問(wèn)題：

問(wèn)題1 鉆石格和五角格是分配格嗎？為什么？

問(wèn)題2 為什么定理1中一定強(qiáng)調(diào)子格？

對(duì)于問(wèn)題1，學(xué)生利用已經(jīng)編好的程序給出了如下答案：因?yàn)槿M〈b，c，d〉，〈b，d，c〉，〈c，b，d〉，〈c，d，b〉，〈d，b，c〉和〈d，c，b〉均不滿足分配等式（1），所以鉆石格不是分配格；同理，因?yàn)槿M〈c，b，d〉和〈c，d，b〉不滿足分配等式（1），所以五角格也不是分配格.

對(duì)于問(wèn)題2，學(xué)生經(jīng)過(guò)討論也給出了正確答案：一個(gè)格中若含有與五角格或鉆石格同構(gòu)的子格，則在該格中會(huì)出現(xiàn)與上述三元組地位相同的三元組，它們也不滿足分配等式（1），因而該格不是分配格.

事實(shí)上，對(duì)于該問(wèn)題我們還得到了另一種解法.該解法不通過(guò)定義3和定理1，而是需用到以下性質(zhì)1（即文獻(xiàn)［3］的習(xí)題6－18）：

性質(zhì)1［3］分配格的任意子格仍是分配格，即設(shè)〈A，≤〉是一個(gè)分配格，〈A，∨，∧〉是由〈A，≤〉所誘導(dǎo)的代數(shù)系統(tǒng)，設(shè)〈B，≤〉是〈A，≤〉的一個(gè)子格，則〈B，≤〉也是一個(gè)分配格.

該性質(zhì)的證明如下：

圖5

若能記住一些類似于〈P（S），?〉的已知的分配格，在解題時(shí)，首先想到將待判定的格與這些分配格進(jìn)行比較，當(dāng)發(fā)現(xiàn)待判定的格與這些分配格的子格同構(gòu)，就可以馬上利用性質(zhì)1判定該格是分配格了.

3 結(jié)束語(yǔ)

我們運(yùn)用計(jì)算機(jī)這一工具，結(jié)合一個(gè)典型例子，很好地解決了分配格判定這一教學(xué)難點(diǎn).我們認(rèn)為這一方法可以推廣到離散數(shù)學(xué)的類似教學(xué)問(wèn)題中去.本文的做法也引出了一個(gè)問(wèn)題，那就是如何充分利用學(xué)生的專業(yè)特點(diǎn)來(lái)進(jìn)行教學(xué)，這值得我們思考.需要特別說(shuō)明的是，在撰寫(xiě)此文后，發(fā)現(xiàn)李思澤［4］已指出過(guò)文獻(xiàn)［3］中的這一錯(cuò)誤，但本文給出了2種新的解法.最后還需要指出，該錯(cuò)誤似乎沒(méi)有得到重視，文獻(xiàn)［3］2005年的印刷版仍未改正這一錯(cuò)誤，借此機(jī)會(huì)，我們呼吁該書(shū)再版時(shí)盡快修正.

［1］左孝凌，李為鑑，劉永才.離散數(shù)學(xué)［M］.上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社，2007.

［2］耿素云，屈婉玲.離散數(shù)學(xué)［M］.北京：高等教育出版社，1998.

［3］左孝凌，李為鑑，劉永才.離散數(shù)學(xué)——理論·分析·題解［M］.上海：上?？茖W(xué)技術(shù)文獻(xiàn)出版社，2005：328－329.

［4］李思澤.《離散數(shù)學(xué)》（左孝凌等編）教材中習(xí)題的探討［J］.工科數(shù)學(xué)，2001，17（6）：105－106.