Two Frameworks for Discrete Mathematics Kirby McMaster kmcmaster@weber.edu CS Dept., Weber State University Ogden, UT 84408 USA Brian Rague brague@weber.edu CS Dept., Weber State University Ogden, UT 84408 USA Steven Hadfield steven.hadfield@usafa.edu CS Dept., Air Force Academy USAFA, CO 80840 USA 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