4 semester credits
Catalog Description
M 187 DISCRETE AND FOUNDATIONAL MATHEMATICS I (4-0-4)(F/S). An introduction to the language and methods of reasoning used throughout mathematics and computer science, and to selected topics in discrete mathematics. Propositional and predicate logic; elementary set theory; introduction to proof techniques including mathematical induction; functions and relations; and basic principles of elementary number theory, combinatorial enumeration, and graph theory. PREREQ: M 143, M 147 or satisfactory placement score.
Prerequisites
M 143, College Algebra or M 147, Precalculus or sufficient score on placement exam. The rationale for this prerequisite is to ensure that students have an adequate level of “mathematical maturity,” in particular some familiarity with the concept of function.
Jurisdiction
This course is not currently controlled by a departmental committee. However, all sections use the same text; the instructors for a given semester meet to agree upon the text. Exams, homework, and grading system are left to the instructor.
Learning Objectives
The objectives of this course encompass all four of the Department’s general teaching goals: (D.1) identification and description of mathematical patterns, with an appreciation of mathematical aesthetics; (D.2) application of mathematics to real world problems; (D.3) mastery of specific mathematical tools; and (D.4) effective use of the language of mathematics in formulating problems and presenting solutions and proofs.
This course addresses quite extensively three of the four general outcomes specified in the Boise State University Core Curriculum guidelines: (C.1) critical thinking/problem solving skills, (C.2) communication skills, and (C.4) breadth of knowledge. The course touches on outcome (C.3), cultural perspective, only tangentially, by mentioning the variety of individuals and cultures who have contributed, over the centuries, to the development of the specific mathematical ideas treated in the course.
The specific learning objectives are listed below. Because this course emphasizes logic, critical thinking, mathematical language, and the nature of mathematical thought and proof, all of these objectives are directly related to departmental goals D.1, D.3 and D.4 and Core goals C.1, C.2 and C.4. Departmental goal D.2 is also addressed in the objectives indicated; Core outcome C.3 is not a major emphasis of any of these objectives. Upon completion of the course, students should be able to:
- Write a clear, cogent mathematical proof, using correct English grammar and punctuation. (Addresses C.2)
- Use the language of propositional and predicate logic to translate statements (both “ordinary language” statements and mathematical ones) into precise logical form.
- Use truth tables to determine under exactly what circumstances statements of propositional logic are true, and, specifically, to be able to identify tautologies and logically equivalent statements.
- Be able to identify proof strategies used to prove statements of various logical forms and apply them to construct proofs of elementary theorems in a stereotypical format. Be able to identify situations where it is appropriate to disprove a statement by producing a counterexample and be able to do this in simple cases.
- Use the language and notation of set theory to describe simple sets and perform manipulations involving set operations.
- Describe the basic notions of relations and functions, including recursive definitions; use functional notation and compute functional values correctly; analyze relations and functions to determine what properties they have.
- Use the principle of mathematical induction, including complete induction and the well-ordering principle, to prove universally quantified statements involving integers, sequences and recursively defined structures.
- In the area of number theory: define basic notions such as divisibility, prime, common divisor, linear combination; state and prove some elementary theorems; compute representations of integers in various bases; use the Euclidean algorithm to compute GCD’s and express them as linear combinations; and describe applications of number theory to fields such as cryptography. (Addresses D.2 to some extent.)
- In the area of group theory: Define basic notions such as group, subgroup, cyclic group, product of two groups, order of a finite group, order of a point in a finite group, homomorphism, isomorphism; state and prove elementary theorems about uniqueness of identity elements or inverses in groups; state some fundamental theorems such as Lagrange’s Theorem, Cauchy’s Theorem; show a mapping defined between groups is a homomorphism, or an isomorphism; answer basic questions about the structure of groups defined by the operations of modular arithmetic.
- In the area of enumeration: apply basic counting principles -including the addition and multiplication principles, permutations and combinations, compensating for overcounting, and simple forms of inclusion/exclusion- to count configurations of many different types, including several of “practical” interest. (Addresses D.2 to some extent.)
- In the area of graph theory: define basic notions such as graph and digraph, degree, subgraph, coloring, etc.; state and prove several simple theorems; give examples of applications of graph theory to practical problems; and apply several simple graph algorithms. (Addresses D.2 to some extent.)
Assessment of Learning Objectives
Students’ progress toward attaining the learning objectives is assessed continually throughout the course by means of homework assignments, in-class exams, take-home exams, and class participation.
- Homework problems encompass a wide spectrum, ranging from a few “routine” problems designed to check students’ mastery of the basic ideas, through problems requiring a higher level of critical thinking in applying those ideas to new situations, to occasional challenge problems that require considerable originality and insight to extend the ideas themselves in new directions. Solutions to homework problems are expected to be written up clearly and completely, using an adequate amount of ordinary English in addition to specialized mathematical terminology and notation; students are cautioned that solutions to many of these problems may require preliminary scratchwork and a rough draft before a final solution is written up.
- Problems given on take-home exams are generally similar to the medium to difficult homework problems, requiring critical thinking, careful exposition, and considerable time. Students are graded on clarity and presentation as well as mathematical correctness.
- Problems given on in-class exams are generally on the less complex end of the spectrum, reflecting the limited time available. Standards for presentation are not as stringent, and problems often are given in multiple-choice or short answer format. However, these problems still require analysis and critical thinking; they are never simply “regurgitation” questions.
- Class participation usually does not factor directly into student grades, but it does provide both the students and the instructor with a valuable form of ongoing, real time assessment as to whether the objectives are being attained.
Topics and Approximate Timeline
The following table is based on a typical semester schedule with days organized by topic. This is just an example: course goals can be met with a somewhat different choice of topics and quite different emphasis on specific topics (therefore, quite different times spent on individual topics) at the discretion of the instructor.
Topic |
Number of days |
Definitions, logic and proof strategy |
10 |
Sets and relations |
9 |
Counting Problems |
6 |
Induction and recursion |
5 |
Functions |
5 |
Number Theory |
7 |
Introduction to Groups (with an application) |
8 |
Graph Theory |
5 |
Tests and review |
5 |
Text
Discrete Mathematical Structures, Kolman, Busby and Ross, Prentice Hall 2000.
or Mathematics A Discrete Introduction, Scheinerman, Brooks/Cole, 2000.
Format, Student Activities, and Grades
Class meetings involve a combination of lecture, questions and discussion, and sometimes small group activity; the instructor chooses the appropriate mix. Homework is an important part of the course; students sometimes do homework in teams. Exams are often partially or wholly take-home, especially those dealing with more complex material. The instructor chooses the exact grading scheme, but a typical distribution would be:
Homework |
10–20% |
“Unit” Exams |
40–60% |
Comprehensive Final Exam |
20-50% |
Letter grades are usually based on a standard scale in which 90% of the total possible points guarantees an A , 80% a B, and 70% a C, with the instructor having the discretion to lower these cut-offs if warranted.
Last modified, 24 April 2008