淺談離散數學的問題

摘要：離散數學是計算和信息學科的理論基礎，知識點多且散，是學習和應用的主要障礙。本文通過細分離散數學問題的內容，劃分了問題的類型，提出了問題的模式，分析了各種類型問題的主要特征和解題方法，提升了離散數學的系統性，降低了其學習和應用的難度。

關鍵詞：精益學習;精益生產;模式;離散數學

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

文章編號：1009-3044（2019）23-0067-04

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

The Pattern of the Problem of Discrete Mathematics

CAI Guang-jun

（Henan Science and Technology University， Luoyang 471023， China）

Abstract： Discrete mathematics is the theoretical basis of Computing and Information Science. For the reason there are so many and scattered knowledge points in discrete mathematics， it is difficult to learn and use in reality. By analyzing the content of the problems of discrete mathematics， this paper presents the pattern of them. Each pattern puts forward the models of problems， analyses the main characteristics of the various types of problems and their solutions. These work can improve the systematic of discrete mathematics， and reduce the difficulty of its learning and application.

Key words： Lean learning; lean production; Pattern; Discrete Mathematics

離散數學作為計算和信息學科的理論基礎，和很多現實問題緊密相關，應用廣泛深入。離散數學又具有范圍廣、內容多的特征，各個部分獨立性強，難以整體把握、形成可應用的知識模塊。

本文從精益學習[1]理念出發，在5S方法[2]進行局部知識精益化的基礎上，從整體上用模式歸納離散數學的問題。模式源于建筑[3]，引入軟件后經[4]發揚光大，對程序設計理論具有重大的影響。為了克服模式多、方法雜的不足，[6]根據內容和關系類型進行模式得抽象提取，本文以離散數學[5]問題的類型和關系為基礎，利用模式方法進行問題的分析歸類。

首先討論了問題的內容，以內容為基礎把問題分為判定題、證明題、計算題和應用題四個部分，分析了每類問題的主要特征和解決方法。

1 離散數學問題的內容

離散數學中問題的元素結構如圖1所示，含義如表1所示。其中，題目是已有的內容，開始是實的;答案是對問題的解答，開始是虛的。

本文問題的分類主要依據要求和結果間的關系，它們間的主要區別如表2所示。其中判斷題和證明題都有確定的結論或目標，關鍵是方法的選擇，判斷題需要確定是否或類型的選擇、證明題則需要提供結論成立的依據;計算題雖然沒有確定的結論，但是一般具有確定的規則和推導方法;應用題則不僅無法確定結論和方法，而且前提是什么，是否有方法解決都不確定。

每個模式分為特征、內容、類型、步驟、難點和示例6個部分，其中特征用以判斷問題的類型;內容用以細化對問題的判斷，分析問題各個部分間的特征和關系;類型用以細分問題，提供問題的解決的整體框架和策略;步驟是解決該類問題的關鍵步驟，難點是解決問題的核心;示例展示問題的特征和通用的解決方法。

2 判斷題

判斷題根據前提確定結論的類型。以“要求”是核心，題干具體、要求抽象、類型簡單，外部知識少且較易確定，題目和答案之間、題干和要求之間多是一對一的關系。解題多從要求出發，是從具體到抽象的過程，可以看作對具體對象的分類。判斷題可以實現性質或規律點到面的擴展，比如通過判斷一個系統是群，則系統可以進行所有群的運算，具有群的元素和內部結構。

特征：題目的“要求”蘊含答案的“結論”，結論是“是或否”或是要求的類型之一;“題干”比“要求”具體。

內容：題目一般比較簡單，題目中題干具體、要求明確;答案部分以結果為主、過程比較簡單。答案具有確定的范圍，解答所需知識范圍小，和要求或題干直接相關，容易確定。題干比較具體，可以是某個對象、對象的某個性質或對象間的某種關系;要求比較抽象，是對對象、對象性質或關系的歸類。過程通常比較簡單，多來自要求的定義、定理;結論為“是否”之一或某些性質、關系、類型。

類型：根據要求是否包含結論，可以分為直接型和間接型兩種。直接型的結論是“是”或“否”;間接型的需要在可能的性質、關系或類型中選擇。是與否的判斷直接從“要求”對應的定義、定理出發，分解、選擇所需對比的內容;性質、類型和關系的判斷要先確定可選擇的選項，再根據選項的要求和題干特征選擇合適的表示、性質進行判斷。

步驟：判斷題可以從正反兩個方面解決，既可以通過相符判斷是，也可以通過不符判斷否。判斷題的主要步驟有：分解、對比。分解是根據題目的要求對應的定義、定理把其分為多個局部的、具體的特征，最好是實現與題干的對應。對比是判斷“要求”分解的結果與題干的內容是否一致。

難點：判斷題多數比較簡單，主要難在如何記住分解所需的定義、定理。

示例：離散數學中的主要判斷題如表3所示。要求代表了問題，直接型的主要依據是要求的對象、關系或性質;間接型的主要依據是要求蘊含的選項。

3 證明題

證明是要為“要求”提供正面支持，即實現“前提+性質”到要求的轉換。證明是由前提和外部知識為兩端，選擇中間內容及其次序、結構的過程。證明題的“要求”就是結論，以多對一和一對一的結構為主，過程的內容和變化規律難以確定。從問題形式可以分為恒等式證明，目標證明;從證明對象可以分為實體證明、性質證明、關系證明等。證明適合具有明確目標的問題，還可以通過對性質和關系的確立，獲取新的定理來簡化問題的處理，如握手定理的證明提供了判斷度數序列能否成圖的依據。

特征：題目的要求就是答案的結論，答案的中心是過程;題干和要求以抽象的內容為主。

內容：題目和答案以抽象內容為主，題目范圍較廣，題干是要求的前提，要求是題干的結論，兩者可以是互為充要條件或題干是要求的充分條件（含外部知識）。答案的核心是過程，且具有兩個相反的方向，思考時多是從后向前，即從要求到題干;書寫時多從前向后，即從題干到要求。

類型：根據前提和結論的數量，證明題主要為一到一的和一到多兩類。一到一;多到一。

一到一證明時前提和結論之間多是等價的，證明的關鍵是求同去異，可以采用從左到右、從右到左和從兩端到中間的不同策略，依據從復雜到簡單、從長到短、從雜亂到統一的原則，根據前提和結論的差異，先對前提進行拆分，再根據目標進行重組。

多到一證明時前提和結論存在大小、數量上的差異，需要進行組合和轉換，組合的依據多是“要求”蘊含的結構、規則或題干不同元素之間的聯系，轉換是同一內容的形式變換是多個前提條件到單個結論的轉換。證明時“一”是核心，證明的關鍵是根據“一”進行條件的選擇和中間的排序，包括根據“一”的結構進行分解，選擇元素并組合;根據與“一”的遠近關系進行連接排序。

步驟：證明題的關鍵步驟有：分解，轉換，綜合。分解多是虛步驟，主要針對要求，也可以是部分題干，要求分解是實現問題從大到小的簡化，并可以提供后期綜合的依據;題干的分解是增加、提取所需的證據。轉換主要針對內容相似形式不同的題干和要求之間或一些中間結果之間，關鍵是確定兩者間的不同，利用相似性轉換，導出結論所需的內容，舍棄結論無關的內容。綜合是進行內容的結構合成，是多到一變化的關鍵，主要任務確定元素的位置和關系，動態可以根據內容的相關性（如邏輯推理時是否有相同的命題變項或子公式），靜態主要根據“一”（如要求）的結構。

難點：證明題的難點是轉換和分解，轉換難在如何取舍不同內容的異同，分解難在如何使分解結果和題干對應。

示例：證明題考查的是對中間步驟的填充，如表4所示。1：1的典型是等值式的證明，依據公式的性質進行變換，求同去異;m：1的關鍵是確定多到1中內容的對應，實現多方內容的組織和綜合。

4 計算題

計算是由已知求未知，是根據題干、計算規則和“要求”的含義確定答案的過程。計算題是規則和方法在具體內容上的應用。題干相對證明較具體，所需知識范圍較確定，不具有可以對比的結果。計算題類型多樣，可以從多個角度劃分。計算題由于答案中結果和過程都不確定，導出結果的關鍵在于題目中蘊含的題外的規則。計算題是規則和方法的縱向應用，是已知到未知的轉變，可以直接用于理論的轉換和獲取結果及本質。如求真值表可以確定命題公式的取值，求極大元可以確定滿足要求的元素。

特征：答案中過程和結果都不確定;題目要求只確定了結果的要求，不直接包含最終的結果;答案過程對外部規則依賴大，范圍選擇較廣。

內容：計算題無論內容和關系都比較復雜。題干是需要轉換的內容、要求是轉換的方向、外部知識是轉換的原則。題目和答案內容以具體的為主，也有抽象的;答案既要求過程，也要保證結果;各個部分的內容既有實體的，也有關系和性質的;計算題對外部知識要求較高。

類型：計算題核心可以分三類：一是題目之外的規則，二是題目的要求，三是題干和要求一起作為核心;數量上有一到一的、一到多的和多到一的;大小上有同級的、大到小的和小到大的。規則為核心的，多是多到一的，大小以同級的為主，解題時多采用從題干出發選擇規則，根據確定的計算方向、優先級和結合性進行到結果的轉變;要求為核心的，多是多到一的，大小以從小到大的為主，解題時多從要求確定解題的規則和方法，然后根據規則和方法對題干進行組合或轉換;核心是題干和要求一起的，多是一對一的或一對多的，大小為同級或從大到小的，解題時多從要求出發確定目標，再對比題干和目標的差異，根據差異確定由題干導出結論的方法。

步驟：計算題的大步驟可以分為三步：分解，轉換，綜合。

分解針對題干和要求數量、粒度上不對等的問題，是根據定義、定理的分解，包括要求、題干或中間結果的分解。要求的分解是問題的化簡、規則或方法的提取，通過分解把一個大問題分為多個小問題、再根據各個小問題的要求確定題干的變化原則，多是該類問題的起點;題干的分解是為了提取要求所需的直接或間接元素，去除要求無關的元素;中間結果的分解根據位置不同可以具有題干分解、要求分解或同時兼具兩者的特征。

轉換多時針對內容相同、形式不同的問題，轉換的關鍵是確定題干和要求或其內容之間的對應關系，根據被轉換對象和轉換結果之間概念之間的相同點和形式不同確定形式上的對應規則和方法，然后根據規則進行被轉換對象的轉換。

綜合是分解的逆反，問題特征與分解相似，但方向不同。包括基于目標的綜合和基于題干的綜合，前者是根據目標對象內容、結構和性質要求，確定需要綜合的元素和元素之間的關系;后者是根據題干相關的外部規則，確定題干不同內容或其元素之間的關系。

難點：一是結果不確定，題干、要求、過程都不含結果的直接形式;二是過程的構建在題干之外;三是類型多，不同類型解決方法不同。

示例：計算題的解決是由題干+外部知識導出答案的過程，關鍵是確定題干和要求之間的關系和外部知識的選擇，典型代表如表5所示。影響較大的是題干元素和要求之間的關系，包括大小和數量關系，大小相同、數量一對一多是轉換的問題;前大后小、一對多的多是分解的問題;前小后大、多對一的多是綜合問題。

5 應用題

應用題是知識和方法在自身領域之外的使用，是知識在現實中的使用能力的考驗，包括問題的轉換和一個或多個判斷、證明或計算的過程。應用題不僅不具有確定的過程和結果，所需要的知識、方法的內容和范圍不確定。可以分為根據要求確定知識的直接應用和根據題干確定知識的間接應用，前者目的明確，通常是單次應用;后者可以多次應用。應用題是規則和方法的橫向應用，可以直接解決現實問題或擴大知識的應用范圍。如求最短路徑可以確定兩點的最短距離，求最小生成樹可以確定城市間的最小連通成本。

特征：題目和答案沒有直接關系，題目內容在所用知識之外，甚至在離散數學之外，答案過程和結果不確定性更大。

內容：題目范圍更廣，題干可能含有與解題或結果無關的信息，要求可能是判斷、計算或證明的任一類型，現實中題干和要求還具有不確定、不完整或冗余等特征。答案中不僅含有解題過程，還包括題目與方法間的轉換過程。答案和題目沒有直接關系，主要根據題干與表示方法，要求與解決方法之間的相似性進行嘗試判斷。

類型：根據求解問題類型的不同，可以分為直接型和間接型兩種。直接型應用題中方法與要求可以一一對應，主要用于解決單個或一類問題，根據要求的特征確定所需的知識、方法和解題過程;間接型應用題方法與題干具有相似性，先轉換為方法的理論，再尋找解決方法和答案。直接應用是已確定需要解決的問題，利用目標知識或方法和問題間的對應關系直接解決;間接應用是先把具體對象轉換為目標方法中的對象，再運用相關方法確定需要解決的問題和解決方法。

步驟：應用題的大步驟可以分為三步：對比，轉入，求解，轉出。對比是通過比較題目和各種方法之間的關系，確定解題所需的方法，不一定出現在答案中，卻是解題的關鍵。轉入是實現題干（部分含要求）到方法表示之間的轉換，把題目中問題轉換為具體方法可以解決的問題。求解基本是包含一個完整的判斷、證明或計算過程，是答案中過程的核心。轉出是把求解結果轉換為問題的答案的結論，通常比較簡單。

難點：應用題的難點是對比，對比的關鍵是確定所需要的理論知識，它的選擇不僅確定了結果是否正確，還決定了過程的對錯和效率。

示例：應用題的解決從要求出發，看是否直接蘊含了所需的方法或理論，否則再看是否能根據題干一起確定，典型例子如表6所示。

6 小結

總的來看，離散數學不同類型的問題間內容、外部知識和核心間的區別比較明顯，如表7所示。結果和過程的導出都有一定的規則，且通常長度不大，主要難在概念多，范圍廣。判斷題重結果、證明題重過程、計算題兩者并重;應用題則是三者的綜合，是問題的轉換，可以細分為判斷應用、證明應用和計算應用。

本文用模式總結了離散數學的問題，提供了一種新的認識學習離散的緯度。雖然本文只是離散數學問題、表示、方法、化簡等內容的第一部分，其效果和使用方式即使在離散數學中還有待進一步驗證，但本文得方法和原則卻不限于離散數學，它可以作為一種新的知識提取模式實現對各個學科高層知識和內在方法進行提取，為素質提升和能力培養提供了新的內容和方法。

參考文獻：

[1] 蔡廣軍. 精益學習初探[J]. 教育現代化， 2017，4（7）：28-30.

[2] 蔡廣軍，付海，王書通，呂鵬云. 精益5S方法在離散數學中的應用[J]. 電腦知識與技術，2017， 13（1）：112-114.

[3] Alexander， Christopher;Ishikawa， Sara; Silverstein， Murray; Jacobson， Max; Fiksdahl-King， Ingrid; Angel， Shlomo. A Pattern Language： Towns， Buildings， Construction[M]. New York： Oxford University Press.1977.

[4]E. Gamma， R. Helm， R. Johnson， and J. Vlissides. Design Patterns： Elements of Reusable Object-Oriented Software[M]. New York：Addison-Wesley Professional， 1994.

[5]屈腕令，耿素云，張立昂.離散數學[M]（第二版）.北京：高等教育出版社， 2008.

[6]蔡廣軍.基于環境建模的服務組合方法[D]. 北京：中國科學院計算技術研究所， 2011：61-74.

【通聯編輯：王力】