Two Frameworks for Discrete Mathematics
Kirby McMaster
kmcmaster@weber.edu
Brian Rague
brague@weber.edu
CS Dept., Weber State University
Ogden, UT 84408
Steven Hadfield
steven.hadfield@usafa.edu
CS Dept., Air Force Academy
USAFA, CO 80840
ABSTRACT
Information Systems and Computer Science educators have campaigned to increase mathematical content in the computing curriculum. Unfortunately, mathematical concepts are often presented in a manner that conflicts with the general mental framework, or gestalt, of IS and CS students. However, there is more than one gestalt in mathematics. In previous research, we developed two scales for measuring mathematical gestalt in books--a Logical Math scale and a Computational Math scale. In this paper, we apply our two scales to current Discrete Math textbooks to assess the relative emphasis these books give to each gestalt. Our findings have relevance in the development of approaches for teaching mathematical topics in computer courses, especially Discrete Math courses.
Keywords: framework, gestalt, discrete math, logical math, computational math.
1. INTRODUCTION
Information Systems and Computer Science educators have campaigned to increase mathematical content in the computing curriculum. Reasons for this zeal include faith in the positive effects of mathematics on the mind (Ralston, 2005), as well as the belief that mathematical logic provides skills that improve the software development process (Kim, 2003). If one agrees with this position, then one must decide how mathematical topics should be presented to IS and CS students. In an ideal world, mathematical ideas would blend naturally into the general mental framework, or gestalt, of these students.
In The Mathematical Experience, Davis and Hersh (1981) state: "People vary dramatically in what might be called their cognitive style, that is, their primary mode of thinking." Unfortunately, the traditional gestalt of mathematics often conflicts with the cognitive style of many IS and CS students. Davis and Hersh observe that:
The definition-theorem-proof approach to mathematics has become almost the sole paradigm of mathematical exposition and advanced instruction.
However, there is more than one gestalt in mathematics. Some authors have not succumbed to a purely logical view of mathematics. In their book What is Mathematics? Courant and Robbins (1941) offer a constructive approach:
There seems to be a great danger in the prevailing overemphasis on the deductive-postulational character of mathematics. The element of constructive invention, of directing and motivating intuition, remains the core of any mathematical achievement, even in the most abstract fields.
The classic proponent of a problem-solving approach to mathematics was Polya (1945) in his book How to Solve It:
Studying the methods of solving problems, we perceive another face of mathematics. Yes, mathematics has two faces; it is the rigorous science of Euclid, but it is also something else. Mathematics presented in the Euclidean way appears as a systematic, deductive science; but mathematics in the making appears as an experimental, inductive science. Both aspects are as old as the science of mathematics itself.
In an earlier paper (McMaster, 2007a), we describe our efforts to characterize and measure two gestalts for mathematics, one based on proving theorems and the other based on solving problems. Our methodology makes the assumption that words used frequently in a book indicate the gestalt of the author. By comparing word frequencies in various mathematics books, we developed two scales for measuring the mathematical gestalt of the authors. A Logical Math scale measures theorem-proving gestalt, and a Computational Math scale measures problem-solving gestalt. We use the term "computational" in the broad sense described by the Program in Applied and Computational Mathematics at Princeton University (www.pacm.princeton.edu).
2. RESEARCH PROBLEM
The prevailing view of mathematics in Discrete Math courses seems to favor theorems and proofs. Koshy (2004) claims in his Discrete Math book that "Theorems are the backbones of mathematics." Gossett's (2002) textbook entitled Discrete Math with Proof advertises that proofs are "inside the book", like a nutritional supplement. Gossett's book is not the only one with the word "proof" in the title.
With respect to mathematical gestalt, some Discrete Math books have split personalities. Several have the word "Applications" in the title. Kolman (2007) expects students "to develop...the ability to write a mathematical proof", but also includes computational experiments at the end of most chapters. Gersting (2006) stresses "the importance of logical thinking, the power of mathematical notation, and the usefulness of abstractions", but her book includes more computer applications than most Discrete Math texts.
In this paper, we apply our Logical Math and Computational Math scales to a sample of 25 current Discrete Math textbooks. Our primary purpose is to assess the level of emphasis these books give to each gestalt. Our findings have relevance in the development of approaches for teaching mathematical topics in computer courses, especially Discrete Math courses.
3. MATH GESTALT SCALES
The methodology we used to create our Logical Math and Computational Math gestalt scales is summarized in this section. A more detailed description is presented in our earlier paper (McMaster, 2007a). The methodology involved the following steps.
Sampling. Choose a broad sample of books from many mathematical areas. We selected 112 books from the Amazon web site that included a concordance (a list of frequently used words). We made an a priori classification of each book as either Traditional Math or Applied Math based on title and content.
Data Collection. The Amazon concordance for a book provides a list of the 100 most frequently used words. An Amazon concordance screens out many common English words, such as "the" and "of". For each concordance word, we recorded the book, word, and frequency (total number of times the word occurs in the book).
Transform Frequencies. We transformed word frequencies within each concordance because books vary in their total number of words. We excluded any Top 100 Common English Words (Fry, 1993) that had not already been removed by Amazon. For the remaining words, we calculated the average word frequency per book. We then divided each word frequency by the average and multiplied by 100, giving a "standard frequency" (StdFreq). This sets the average word frequency to 100.
Convert and Combine Words. We converted many words to a standard form, so that the scale contribution of a word would not depend on the particular form or tense an author favored. For example, we converted plural nouns to singular form and converted verbs to present tense. In selected cases, we combined two or more synonyms into one word (e.g. "theorem" and "lemma" became "theorem/lemma").
Construct Gestalt Scales. Constructing the Logical Math scale (referred to as LMATH) and the Computational Math scale (referred to as CMATH) was an iterative process. We searched for words that are used frequently within each book, and consistently across similar books. During each iteration:
1. Query all Traditional Math books for the LMATH scale. Query all Applied Math books for the CMATH scale. Find all words in which the average StdFreq taken across all books for that scale is relatively "high".
2. Calculate a weight for each of the chosen words.
3. Calculate the LMATH and CMATH scores for all books in the sample. Each score is a weighted average of the StdFreq values for words on the scale.
4. Remove books from the sample that have a relatively low score on their relevant scale.
5. Repeat the above steps, obtaining a revised list of words and weights for each scale. Stop when the scale words and weights do not change.
After several iterations, we obtained LMATH and CMATH scales constructed from 25 Traditional Math books and 25 Applied Math books, respectively. Each gestalt scale consists of a list of word/groups and weights. A word/group is created when two or more word forms (e.g. "proof" and "prove") or synonyms (e.g. "function" and "map") are combined.
Logical Math Gestalt
The Logical Math (LMATH) scale consists of 10 word/groups and weights. The details of this scale are presented in Table 1. The most frequent word/group for the LMATH scale is "theorem/lemma/corollary". As expected, the concepts of "theorem", "proof", and "definition" (with equivalent words combined) are represented on the scale. Surprisingly, the most frequent individual word is "let". Words like "hence/thus/therefore", "show", "follow", and "since" are conventions commonly used to convey logical ordering in proofs.
Table 1: LOGICAL MATH Words
Based on 25 Traditional Math books
Word/Group
Books
Avg
StdFreq
Weight
theorem/lemma
/corollary
25
428.2
18.34
let
25
418.1
17.78
set/subset
25
333.1
13.03
proof/prove
25
329.9
12.85
function/map
25
300.9
11.23
hence/thus/
therefore
25
230.3
7.28
definition/define
25
221.4
6.78
show/shown
25
191.3
5.10
follow/following
24
175.4
4.21
since
24
160.8
3.40
TOTAL
100.00
The words "function" and "set" appear on the scale because these terms are commonly used throughout mathematics. Words specific to only a few areas of mathematics (e.g. "derivative" and "ring") do not appear on the scale. Thus, LMATH measures a general gestalt for Traditional Mathematics.
Computational Math Gestalt
The Computational Math (CMATH) scale consists of 10 word/groups and weights. The details of this scale are presented in Table 2. The most frequent word for the CMATH scale is "problem", and the third most frequent word is "solution/solve". This confirms that problem solving is a central theme in the Computational Math gestalt of Applied Math books.
Table 2: COMPUTATIONAL MATH Words
Based on 25 Applied Math books
Word/Group
Books
Avg
StdFreq
Weight
problem
25
394.3
18.56
method/algorithm
23
343.1
15.33
solution/solve
25
322.4
14.03
value/variable
24
271.7
10.83
equation/inequality
21
265.9
10.46
function/map
24
257.0
9.90
model/modeling
19
222.3
7.71
point/line
24
175.8
4.78
system/subsystem
23
168.7
4.33
condition/constraint
25
164.3
4.06
TOTAL
100.00
CMATH gestalt is concerned with how to use mathematics to solve real-world problems. The words "model" and "method/algorithm" describe the main approach to solving problems. Words like "variable", "equation", "function", and "condition/constraint" are components of mathematical models and algorithms. The word "model" is an essential part of Computational Math gestalt. By comparison, "model" rarely appears in Traditional Math books. In Logical Math gestalt, the real world is irrelevant, so there is no need for models.
The word "function" appears on both the LMATH and the CMATH scales, although with slightly different weights. We considered excluding this word from both scales to make the scales more "orthogonal," but decided to retain "function" on each scale.
LMATH Calculations
We can learn a lot about a book from the calculation of its LMATH (and CMATH) scores. The calculations show which words contribute most to the overall gestalt score for a book. Royden's (1988) Real Analysis was one of the 25 Traditional Math books used to develop the final LMATH scale. The LMATH calculations for this book are shown in Table 3.
Table 3: LMATH Calculations
Royden -- Real Analysis
Word/Group
Weight
Std
Freq
LMATH
Scale
theorem/lemma/
corollary
18.34
214.8
39.4
let
17.78
413.1
73.4
set/subset
13.03
962.3
125.4
proof/prove
12.85
188.7
24.2
function/map
11.23
527.0
59.2
hence/thus/
therefore
7.28
226.8
16.5
definition/define
6.78
230.0
15.6
show/shown
5.10
237.4
12.1
follow/following
4.21
127.7
5.4
since
3.40
187.3
6.4
TOTAL
377.6
Royden's concordance includes all 10 of the LMATH scale word/groups. The StdFreq value indicates how often a scale word is used in the book. The weight defines the importance of a word for measuring gestalt (as derived in Table 1). For Royden, the most frequent words are "set/subset" (StdFreq = 962.3), "function/map" (StdFreq = 527.0), and "let" (StdFreq = 413.1). The LMATH value of 377.6 can be interpreted as follows: scale words appear (on average) about 3.776 times more often than an average concordance word in the same book. Thus, Royden's book exhibits a high level of Logical Math gestalt.
CMATH Calculations
The field of Operations Research can be viewed as an archetype for Computational Math gestalt. The Operations Research titles in our original sample of Applied Math books consistently scored high on the CMATH scale. We performed CMATH calculations for Hillier & Lieberman's (2004) Operations Research textbook, resulting in a CMATH score of 303.7. The CMATH results for this book are shown in Table 4.
Table 4: CMATH Calculations
Hillier & Lieberman -- Operations Research
Word/Group
Weight
Std
Freq
CMATH
Scale
problem
18.56
483.8
89.8
method/algorithm
15.33
262.7
40.3
solution/solve
14.03
496.9
69.7
value/variable
10.83
474.4
51.4
equation/inequality
10.46
69.3
7.2
function/map
9.90
114.4
11.3
model/modeling
7.71
268.3
20.7
point/line
4.78
--
--
system/subsystem
4.33
137.4
5.9
condition/constraint
4.06
180.7
7.3
TOTAL
303.7
Hillier & Lieberman's concordance includes 9 of the 10 CMATH scale word/groups. The most frequent words are "solution/solve" (StdFreq = 496.9), "problem" (StdFreq = 483.8), and "value/variable" (StdFreq = 474.4). Also, both "model" and "method/ algorithm" have StdFreq values above 250.
4. DISCRETE MATH FRAMEWORKS
Two related questions concern mathematical gestalt for Discrete Math.
1. Which gestalt is emphasized in Discrete Math textbooks?
2. Which gestalt is more suitable for Discrete Math courses?
This paper focuses primarily on the first question. We wanted to determine how much support current Discrete Math textbooks provide for each framework. The answer to this question can influence how teachers respond to the second question.
In this study, we selected a sample of 25 Discrete Math books having Amazon concordance data. Unfortunately, concordance data was not available for several well-known Discrete Math textbooks. We transformed frequencies and converted/combined words as in our scale development methodology. Then we calculated Logical Math and Computational Math gestalt measures for each book using the LMATH and CMATH scales defined previously. The scale scores for the 25 books are listed in Appendix 1.
Gestalt Words in Discrete Math Books
Table 5 displays eight word/groups selected from the two gestalt scales. Each word is presented with the number of Discrete Math books that use the word frequently, along with the average standard frequency (Avg StdFreq) value. The Logical Math words "theorem", "proof", and "set" were used frequently in at least 22 of the books. The word "problem" was the only Computational Math word used frequently by as many as 18 books.
Table 5: Gestalt Scale Words
25 Discrete Mathematics books
Word/Group
Books
Avg
StdFreq
Logical Math
set/subset
25
427.0
proof/prove
22
217.0
definition/define
17
210.6
theorem/lemma/corollary
23
180.3
Computational Math
method/algorithm
17
145.3
solution/solve
14
139.2
problem
18
127.4
model/modeling
1
52.8
The average StdFreq values are much higher for the Logical Math words. This indicates that Discrete Math books contain more Logical Math words than Computational Math words. It is disappointing that only one Discrete Math book listed "model" as a frequent word. According to Kramer (2007), "modeling is the most important engineering technique."
LMATH Scores for Discrete Math Books
For the 25 Discrete Math books, the LMATH scores ranged from a minimum of 94.3 to a maximum of 348.9, with a mean of 200.3. The distribution of LMATH scores is presented in Figure 1. In this graph, scores are grouped into intervals of size 50.
Figure 1: Mathematical Gestalt Scores
25 Discrete Math Books
Eleven of the 25 books had LMATH scores above 200. A LMATH score of 200 means that scale words appear twice as often as the "average concordance word." Two of the books had LMATH scores above 300: (1) Nievergelt's (2002) Foundations of Logic and Mathematics (LMATH = 348.9), and (2) Gries' (1993) A Logical Approach to Discrete Math (LMATH = 316.5). Note that these books contain "logic" in the title.
The LMATH calculations for Gries' textbook are shown in Table 6. The word/groups with StdFreq values above 300 are "proof/prove" "theorem/lemma/corollary", "set/subset", and "definition/define". Gries' book is vintage Logical Math.
Table 6: LMATH Calculations
Gries -- A Logical Approach to Discrete Math
Word/Group
Weight
Std
Freq
LMATH
Scale
theorem/lemma/
corollary
18.34
422.8
77.5
let
17.78
103.0
18.3
set/subset
13.03
411.0
53.6
proof/prove
12.85
716.3
92.0
function/map
11.23
192.9
21.7
hence/thus/
therefore
7.28
164.8
12.0
definition/define
6.78
342.7
23.2
show/shown
5.10
101.1
5.2
follow/following
4.21
220.0
9.3
since
3.40
108.6
3.7
TOTAL
316.5
CMATH Scores for Discrete Math Books
The 25 CMATH scores ranged from 36.8 to 175.2, with a mean of 83.8. The distribution of CMATH scores, compared to LMATH scores, is shown in Figure 1. The excess of lower CMATH scores is evident in this graph.
No Discrete Math book in the sample had a CMATH score above 200. The two books with highest CMATH scores are: (1) Rosen's (1999) Handbook of Discrete and Combinatorial Math (CMATH = 175.2), and (2) Alt's (2001) Computational Discrete Mathematics (CMATH = 161.1). We note that, even though Alt's book has the word "computational" in the title, the LMATH score (181.8) for this book is higher than its CMATH score.
The CMATH calculations for Rosen's Handbook (which is not his popular Discrete Mathematics and It's Applications textbook) are shown in Table 7. This book promotes "methods/algorithms" but with little emphasis on "models". However, this was the only Discrete Math book in the sample to include "model" in its concordance.
Table 7: CMATH Calculations
Rosen -- Handbook of Discrete and
Combinatorial Math
Word/Group
Weight
Std
Freq
CMATH
Scale
problem
18.56
206.5
38.3
method/algorithm
15.33
341.3
52.3
solution/solve
14.03
105.4
14.8
value/variable
10.83
182.1
19.7
equation/inequality
10.46
55.3
5.8
function/map
9.90
241.3
23.9
model/modeling
7.71
52.8
4.1
point/line
4.78
249.6
11.9
system/subsystem
4.33
101.3
4.4
condition/constraint
4.06
--
--
TOTAL
175.2
LMATH vs. CMATH Scores
For 24 of the 25 Discrete Math books, the LMATH score is higher than the CMATH score. The exception was Rosen's (1999) Handbook of Discrete and Combinatorial Math. Logical Math gestalt is consistently the predominant framework in Discrete Math books, even when the authors declare they are providing balanced coverage of theorem proving and problem solving.
The relationship between LMATH and CMATH scores for the 25 Discrete Math books is presented as a scatter diagram in Figure 2. For descriptive purposes, the (negative) correlation between LMATH and CMATH scores is -0.343. Books with high LMATH scores tend to have low CMATH scores. The converse is not true, because no book in the sample had a high CMATH score.
Figure 2: LMATH vs. CMATH Scores
25 Discrete Math Books
5. SUMMARY AND CONCLUSIONS
The main purpose of this study was to measure two mental frameworks, or gestalts, in Discrete Math books. Logical Math gestalt is based on proving theorems, while Computational Math gestalt is based on solving problems. The gestalt scales are based on words that are used frequently in mathematics books. Our Logical Math (LMATH) scale contains 10 word/groups, including theorem/lemma, proof, let, and definition. The Computational Math (CMATH) scale has 10 word/groups, including problem, solution, model, and method/algorithm.
We calculated LMATH and CMATH scores for 25 Discrete Math books. For 24 of the books, the LMATH score is higher than the CMATH score, indicating an emphasis on Logical Math gestalt. Of particular note, only one Discrete Math book included "model" as a frequent word. The data also showed a slight negative relationship between LMATH and CMATH scores, primarily because the highest LMATH books had low CMATH scores. However, no Discrete Math book had a high CMATH score.
Which Framework for Discrete Math?
Our intent in this study was not to determine which framework is "best" for Discrete Math, since each gestalt can provide value in the course. The Realistic Math Education program in Holland, based on the work of Treffers (1987), encourages two types of "mathematization":
1. Horizontal mathematization, where students solve a problem located in a real-life situation (this is Computational Math).
2. Vertical mathematization, where students reorganize concepts within the mathematical system itself (this is Logical Math).
Both types of mathematization encourage abstraction--by constructing models for real-world systems, and through manipulating symbolic objects in proofs.
Computational Math and Software Development
Logical Math and Computational Math are not the only mental frameworks relevant to Information Systems and Computer Science. We are currently developing gestalt measures for software development, with interrelated scales for programming, database, and software engineering. In our initial sample of software development books, frequent programming words include class and method; frequent database words include data and database; and frequent software engineering words include software and system. Computational Math gestalt, where models and algorithms are used to solve real-world problems, appears to be closer in spirit to the framework used in software development.
We are continuing our efforts to combine mathematical and software frameworks in Information Systems and Computer Science courses. In his Discrete Math book, Koshy (2004) admits that "knowledge of a structured programming language, such as Java or C++, can make the study of discrete mathematics more rewarding." If a Discrete Math course is taught with a Computational Math gestalt, then it is natural to include programming in the course (see McMaster, 2007b). In computing, models and algorithms are implemented as software.
Each Discrete Math teacher should choose an appropriate blend of Logical Math and Computational Math for the course. If the instructor wants to emphasize Logical Math, then she/he can consider the 11 Discrete Math books with LMATH scores above 200. If a Computational Math emphasis is desired, then the instructor has a dilemma. No Discrete Math book in our sample promotes this framework. Discrete Math books not included in our sample could be examined, with special attention paid to their use of CMATH scale words such as "model" and "algorithm". Or the instructor can prepare custom classroom materials and assignments that are based on Computational Math gestalt.
6. REFERENCES
Alt, Helmut (2001), Computational Discrete Mathematics: Advanced Lectures. Springer.
Bruce, Kim, et al (2003), “Why Math?” Com-munications of the ACM, Vol. 46, No. 9.
Courant, Richard, and Herbert Robbins (1941), What Is Mathematics? Oxford University Press.
Davis, Philip, and Reuben Hersh (1981), The Mathematical Experience. Birkhauser.
Fry, Edward, et al (1993), The Reading Teacher's Book of Lists (3rd ed). Center for Applied Research in Education.
Gersting, Judith (2006), Mathematical Structures for Computer Science (6th ed). W. H. Freeman.
Gossett, Eric (2002), Discrete Math with Proof. Prentice-Hall.
Gries, David, and Fred Schneider (1993), A Logical Approach to Discrete Math. Springer.
Hillier, Frederick, and Gerald Lieberman (2004), Introduction to Operations Research (8th ed). McGraw-Hill.
Kolman, Bernard, et al (2007), Discrete Mathematical Structures (6th ed). Prentice Hall.
Koshy, Thomas (2004), Discrete Mathematics with Applications. Elsevier.
Kramer, Jeff (2007), "Is Abstraction the Key to Computing?" Communications of the ACM, Vol. 50, No. 4.
McMaster, Kirby, et al (2007a), "Two Gestalts for Mathematics: Logical vs. Computational." Proceedings of ISECON 2007, Vol. 24.
McMaster, Kirby, et al (2007b), "Discrete Mathematics with Programming: Better Together." Proceedings of SIGCSE 2007.
Nievergelt, Yves (2002), Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography. Birkhauser Boston.
Pemmaraju, Sriram, and Steven Skiena (2003), Computational Discrete Mathematics. Cambridge University Press.
Polya, G. (1945), How To Solve It. Princeton University Press.
Ralston, Anthony (2005), “Do We Need ANY Mathematics in Computer Science Curricula?” SIGCSE Bulletin, Vol. 37, No. 2.
Rosen, Kenneth (2006), Discrete Mathematics and Its Applications (6th ed). McGraw-Hill.
Rosen, Kenneth (1999), Handbook of Discrete and Combinatorial Math. CRC.
Royden, H. L. (1988), Real Analysis (3rd ed). Prentice Hall.
Treffers, A. (1987), Three Dimensions: A Model of Goal and Theory Description in Mathematics Instruction. Reidel Publishing Company.
Wazwaz, Abdul-Majid (2004), Discrete Mathematics: Methods and Applications. Stipes Publishing.
APPENDIX 1: 25 Discrete Mathematics Books
Author
Year
Title
LMATH
CMATH
Aigner
2007
Discrete Mathematics
240.6
118.0
Alt
2001
Computational Discrete Math
181.8
161.1
Anderson
2005
First Course in Discrete Math
134.8
44.9
Biggs
2002
Discrete Mathematics
227.3
100.5
Chetwynd
1995
Discrete Mathematics
180.6
65.6
Ensley
2005
Discrete Math: Math Reasoning and Proof
183.1
91.0
Foldes
1994
Fund Structures of Algebra and DM
298.5
36.8
Garnier
1992
Discrete Math For New Technology
229.5
75.5
Gries
1993
Logical Approach to Discrete Math
316.5
67.2
Laywine
1998
Discrete Math Using Latin Squares
121.1
40.4
Lipschutz
1991
2000 Solved Problems in Discrete Math
265.5
67.9
Lipschutz
1997
Schaum Outline of Discrete Math
223.8
73.7
Lovasz
2003
Discrete Mathematics
174.2
42.3
Molluzzo
1997
First Course in Discrete Mathematics
164.5
126.6
Nievergelt
2002
Foundations of Logic and Math
348.9
39.2
O'Donnell
2006
Discrete Math Using a Computer 2
213.0
99.1
Pemmaraju
2003
Computational Discrete Mathematics
94.3
74.7
Penner
1999
DM: Proof Techniques and Math Structures
291.6
44.3
Piff
1991
Discrete Mathematics
210.5
60.5
Rosen
2006
Discrete Mathematics
161.4
84.5
Rosen
1999
Handbook of Discrete Math and Comp Math
148.6
175.2
Ross
2000
Finite and Discrete Mathematics
166.7
96.8
Sethumadhavan
2006
Discrete Mathematics
190.6
101.6
Wallis
2002
Beginner's Guide to Discrete Math
131.5
98.2
Wazwaz
2004
Discrete Mathematics
109.8
108.4