郭 蕓， 王朝暉

（蘇州大學計算機科學與技術學院，江蘇蘇州 215006）

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

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

關于分配格的定義，可以按照偏序集－格－分配格的順序來理解，其定義如下：

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

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

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

圖2

圖1

圖3

2 一個典型例子

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

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

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

由于格本質上是一種關系，注意到用哈斯圖表示的關系不便于計算機實現(xiàn)，可以將哈斯圖轉化為關系矩陣，而關系矩陣就可以用程序設計語言的數組來表達.設格為〈A，≤〉，以下是我們指導學生編寫的VB程序的算法：

圖4

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

解釋完以后，可以讓學生思考兩個問題：

問題1 鉆石格和五角格是分配格嗎？為什么？

問題2 為什么定理1中一定強調子格？

對于問題1，學生利用已經編好的程序給出了如下答案：因為三元組〈b，c，d〉，〈b，d，c〉，〈c，b，d〉，〈c，d，b〉，〈d，b，c〉和〈d，c，b〉均不滿足分配等式（1），所以鉆石格不是分配格；同理，因為三元組〈c，b，d〉和〈c，d，b〉不滿足分配等式（1），所以五角格也不是分配格.

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

事實上，對于該問題我們還得到了另一種解法.該解法不通過定義3和定理1，而是需用到以下性質1（即文獻［3］的習題6－18）：

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

該性質的證明如下：

圖5

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

3 結束語

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

［1］左孝凌，李為鑑，劉永才.離散數學［M］.上海：上海科學技術文獻出版社，2007.

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

［3］左孝凌，李為鑑，劉永才.離散數學——理論·分析·題解［M］.上海：上海科學技術文獻出版社，2005：328－329.

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