Math 231: Elementary Discrete Mathematics I, Syllabus, Winter 2025


Instructor: Prof. Boris Botvinnik : e-mail botvinn[at]uoregon.edu

Lectures: 251 Straub Hall: Monday, Tuesday, Wednesday, and Thursday at 3:00--3:50 pm,

Office hours: Tuesday, 4--5 pm, Wednesday 11 am -- 12 pm or by appointment

Textbook: Discrete Mathematics and Applications. Kenneth H. Rosen, Either the 7th or 8th edition.

You are expected to read the textbook carefully, and will be responsible for all the material in those sections that are covered in class. The text contains solutions or hints for odd numbered problems. The homework assignments will consist mostly of even numbered problems, although I strongly recommend that you try some of the odd numbered problems on your own. The accompanying study guide contains a great deal of additional information that you should find helpful.

Course Content:

The course has a few main topics:

  • Week 1-3: COUNTING. Mostly sections 6.1 and 6.3 of text, plus a little bit of 6.4. Factorials, counting arrangements of words with repeated letters ("spelling problems"), binomial coefficients. Counting poker hands of various types, ways of picking r elements from n different elements when order matters and does not matter. Pascal's triangle and the binomial theorem. Balls-in-boxes/stars-and- bars problems with lots of variations. Inclusion/exclusion principle and more examples.

  • Week 3-4: LOGIC. Material extracted from sections 1.1, 1.2, 1.3, 1.4, 1.5 from the textbook (which contain a lot more than we will actually cover in class). Propositions and the truth tables for the basic logical connectives. Proving logical equivalences via truth tables. Predicates as propositions with variables. Quantifiers "for all" and "there exists." More complicated logical sentences written using predicates and quantifiers, and practice of negating such statements. The difference between the mathematician's "if and only if" symbol with double thickness left/right arrow and the underlying logical connective with single thickness left/right arrow should be explained since this is confusing—the former means the statement involving the latter is a tautology.

  • Week 4-5: FIRST LOOK AT PROOF WRITING. Sections 1.7, 1.8 and 2.4. Lots of examples of proofs in elementary mathematics, prac- tice of writing proofs of various types. Definitions of "even" and "odd" and proofs using them and “contrapositive,” definition of rational and irrational and proofs using them and "contrapositive" or "proof by contradiction," e.g. square root or cube root of 2 is irrational. Some other examples of direct proofs especially "if and only if" proofs getting used to the word "converse." Proofs involving inequalities, proofs involving summations and the method of differences. Formulas for the sums 1+2+...+n, 12+22+...+n2, 13+23+...+n3, geometric progressions and so on.

  • Weeks 5-8: LANGUAGE OF SETS AND FUNCTIONS. Sections 2.1, 2.2 and 2.3. CS majors are familiar with the notion of "type" of a variable, and throughout this material it is helpful to see that in mathematics the basic type is "set" but subsequent constructions are refining this notion to introduce higher level objects. The notion of sets, elements, subsets, supersets, and equality of sets. Intersections, unions, complements, set minus. Examples of proofs of equality of sets by establishing both containments, and translation of set-theoretic identities to logic identities and truth tables as seen in chapter 1. Recursive definition of natural numbers starting from 0 being the empty set. Power sets, ordered pairs and Cartesian products, size of a set. Definition of a function: domain, range, image. Notions of injective, surjective and bijective, the set Y X of all functions from X to Y , ordered tuples. Examples of bijections appearing in counting, with more practice of counting.

  • Weeks 8-10: FUNDAMENTAL THEOREM OF ARITHMETIC and REVIEW. Sections 4.1, 4.2, 4.3. Greatest common divisors and the Euclidean algorithm (the most important recursive algorithm of all). Prime numbers. Lowest common multiples. The statement of the Fundamental Theorem of Arithmetic (without proof), and practice using it. Parts of sections 11.1, 11.2, 11.3. Basic terminology of trees and forests, formulae for their number of edges. Then ordered rooted trees and some of their applications, ending with the connection between binary rooted trees and Catalan numbers.

    Homework:

    Homework is due by 11:59 pm on Wednesdays, beginning January 15. Late homework will not be accepted. There will be 9 homework assignments, the last of which will not be graded. Your lowest homework score will be dropped. You may collaborate with other class members on your homework, although you must each write up your solutions independently and in your own words. To avoid falling behind, you should do the reading and homework as the material is presented in class, rather than leaving it all until the last minute.

    The homework should be uploaded to Canvas by the deadline.

    Graded homework will be returned electronically, using Canvas.

    Exams:

    here will be two in-class midterm exams and a final exam. No cell phones and computersm are alloowed. You may have one 3x5 index card with everything you wish written there.

  • First Midterm Exam: 3:00-3:50 pm, Thursday, January 30, 2025

  • Second Midterm Exam: 3:00-3:50 pm, Thursday, February 27, 2025

  • Final Exam: 2:45-4:45 pm, Monday, March 17, 2025

  • Important: There will be no makeup for these exams, except for documented medical Emergencies.

    Grading:

    Homework:  20%
    First Midterm Exam:  20%
    Second Midterm Exam:  20%
    Final Exam:  40%

    Classroom behavior

    Students are expected to behave respectfully toward each other and toward the instructor during class time. This includes refraining from using cell phones during lectures.

    Academic conduct

    The code of student conduct and community standards is here. In this course, it is appropriate to give and obtain help on homeworks so long as the work you are submitting is your own and you understand it. It is not appropriate to obtain help on exams or to give help to other students with their exams. Cheating hurts the cheater and all the other honest students in the system, basically: PLEASE DO NOT CHEAT!

    Learning environment and AEC accommodations

    The University of Oregon strives for inclusive learning environments. Please notify me if the instruction or design of this course results in disability-related barriers to your participation. You are also encouraged to contact the Accessible Education Center at her.

    Accommodations for religious observances

    The university makes reasonable accommodations, upon request, for students who are unable to attend a class for religious obligations or observance reasons, in accordance with the university discrimination policy which says ``Any student who, because of religious beliefs, is unable to attend classes on a particular day shall be excused from attendance requirements and from any examination or other assignment on that day. The student shall make up the examination or other assignment missed because of the absence." To request accommodations for this course for religious observance, visit the Office of the Registrar's website and complete and submit to the instructor the ``Student Religious Accommodation Request" form prior to the end of the second week of the term.

    Basic needs

    Any student who has difficulty affording groceries or accessing sufficient food to eat every day, or who lacks a safe and stable place to live and believes this may affect their performance in the course is urged to contact the Dean of Students Office (346-3216, 164 Oregon Hall) for support. This UO webpage includes resources for food, housing, healthcare, childcare, transportation, technology, finances, and legal support.

    Inclement weather

    It is generally expected that class will meet unless the University is officially closed for inclement weather. If it becomes necessary to cancel class while the University remains open, this will be announced on Canvas and by email.

    Mental health and wellness

    Life at college can be very complicated. Students often feel overwhelmed or stressed, experience anxiety or depression, struggle with relationships, or just need help navigating challenges in their life. If you're facing such challenges, you don't need to handle them on your own--there's help and support on campus. Getting help is a courageous thing to do-for yourself and those you care about. University Health Services help students cope with difficult emotions and life stressors. If you need general resources on coping with stress or want to talk with another student who has been in the same place as you, visit the Duck Nest (located in the EMU on the ground floor) and get help from one of the specially trained Peer Wellness Advocates. Find out more here.

    Last modified December 28, 2025 by Boris Botvinnik.