Discrete Structures

Welcome to Discrete Structures! Our texts will be my notes, together with other material available online.

Click here for printer/mobile device-friendly version

Discrete Structures

Complete only these tasks before our first class: FINALIZED

* Watch this video: Welcome!
* How to be a student in a flipped classroom (about 11 minutes - our class will not be entirely flipped, but enough that this is worth watching).
* Read the Carthage Mask and Vaccination Policy.

You do not need to do an of the assignments outside of this box until after our first class.

1/11: These exercises are due on 1/12. (Yes, they are due tomorrow at the beginning of class, before I take questions over the assignment. Have them ready to turn in when you enter the classroom!) (Never start on an assignment that isn't FINALIZED. I may change it!) FINALIZED

* DO THIS BEFORE OUR NEXT CLASS: Read Chapter 0 in the text. This is an important part of your assignment. Highlight items that you believe could be useful in the future. You are responsible for knowing the information contained in Chapter 0.
* DO THIS BEFORE OUR NEXT CLASS: Read Section 1.1 in the text
* DO THIS BEFORE OUR NEXT CLASS: Re-read your class notes from the worksheet.
* DO THIS BEFORE OUR NEXT CLASS: Do exercises 2acd, 3, 7 from Section 1.1 in the notes. These exercises will be collected at the beginning of our next class on Thursday. They should be written neatly or typed on a piece of paper that can be turned in, not in your notes.
* DO THIS BEFORE OUR NEXT CLASS: If you haven't done this already for another class, create your account on user.wolfram.com using your Carthage email address. If you already have an account, make sure that you remember your password. If you don't have a user.wolfram account, you can create one here with your Carthage e-mail address.
* Check the blog for new entries. Even if I fail to put this in your assignment, it would be a good idea to check the blog at least every other day. As I read your homework or think about how class went, I will post insights and hints in the blog.

* Watch these videos before class on Thursday. Take notes while watching the videos, either in the handout or in a notebook that you can bring to class. They will prepare you for class.
(1) Factorials
(2) Properties of Functions
(3) Sets
(4) Important Sets

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises below are due on 1/13. They are due at the beginning of class, before I take questions over the assignment. Have them ready to turn in when you enter the classroom!

* Do exercises 2bef, 6 from Section 1.1 in the text. These exercises will be collected at the beginning of our class on Friday. They should be written neatly on a piece of paper that can be turned in, not in your notes. Turn them in as you enter the classroom or shortly thereafter. Don't wait for me to ask! Please do not put these on the same piece of paper that you turn in on Thursday!
* Check the blog for new entries.

Optional Material

* If you wish, you can download copies of the following two Discrete Structures texts which I will reference from time to time. Both are available for no cost over the internet, or for a very reasonable price in hard copy.
- The Book of Proof by Hammack
- Discrete Structures in Five Chapters by Witno

* Think about the function \(f(x)=4x(1-x)\) with \(D=T=[0,1]\). Can you find two points \(a\neq b\) such that \(f(a)=b\) and \(f(b)=a\)? How about points \(a\), \(b\), and \(c\) such that \(f(a)=b\), \(f(b)=c\), and \(f(c)=a\) (with \(a\neq b \neq c\) of course)? (Yes, they do exist!) I have posted some code at this link for download, or here for use online.
* Choose a starting value, chose a button on your calculator, and push the calculator button repeatedly. The \(\sin x\) button, the \(\cos x\) button, the \(x^2\) button, the \(\sqrt x\) button, and the \(\tan^{-1} x\) button are all good choices. Did you see any pattern?
* Can a rectangle have a square gnomon? If so, which ones? If not, why not?
* Can a rectangle be its own gnomon? That is, can you slice a rectangle in half and obtain two scaled-down versions of the original rectangle?

Today's VQ for In-Class Use (You can't take the quiz here - take the quiz using the link above.)

1/12: These exercises are due on 1/13. They will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Introduction to Iteration
(2) Periodic Points
(3) The Shift Function and Connected Components

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/16.

* Do Exercises 4 and 5 from Section 1.1 in the notes.
* Read Section 1.2 in the text.
* Re-read the in-class worksheet for Section 1.2.
* Do exercises 1, 3, 4, 5, 6 from Section 1.2 in the notes.

Optional Material

* For the function \(p(x):=x(k-x)\) with \(p:\mathbb Z \rightarrow \mathbb R\), can you predict the number of elements of the range of \(p\) that are integers and also perfect squares? We did \(k=20\) in class - what about \(k=30\)? Can you predict the number of perfect squares given a value for \(k\)?

Today's VQ for In-Class Use (You can't take the quiz here - take the quiz using the link above.)

1/13: These exercises are due on 1/16. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) Propositions
(2) Compound Propositions
(3) Basic Set Operations
(4) Two More Definitions

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

These exercises are due on 1/17. They are due at the beginning of class, before I take questions over the assignment. Turn them in when you enter the classroom!

* Do Exercises 2, 7, 8 from Section 1.2 in the notes.
* Use Exercise 3 from Section 1.2 to prove that \(f:\mathbb R\rightarrow\mathbb R\) by \(f(x)=15x+8\) is one-to-one. Do not prove this directly using the definition! You must use Exercise 3. Make sure that all of the assumptions of the exercise are satisfied.
* Read Section 1.3 in the text.
* Re-read the in-class worksheet for Section 1.3.
* Do exercises 1, 2, 4, 8, 11 from Section 1.3.
* Read Section 1.4 in the text, particularly the material that we discussed in class. We did not cover graphs of circle functions or connected components.
* Re-read the in-class worksheet from Section 1.4.
* Do exercises 1, 2, 4 from Section 1.4.

Optional Material

* We didn't do an exploration today, so I don't have any additional optional material. However, several of you are investigating questions I posed earlier - that's fantastic! Keep it up!

Today's VQ for In-Class Use (take the quiz at the link above)


Week 2

1/16: These exercises are due on 1/17. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.

(1) Truth Table Proofs
(2) Using a Spreadsheet
(3) Proofs of Argument Forms
(4) Quantifiers and Propositional Functions

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/18.

* Do Exercises 5, 10, 12 from 1.3 in the text.
* Do exercises 9, 11 from Section 1.4. DON'T WORRY ABOUT NUMBER 9!
* Read Section 1.5 in the text.
* Re-read the in-class worksheet from Section 1.5.
* Do exercises 7ace and 8ab from Section 1.5.
* Read Section 1.6 in the text.
* Re-read the in-class worksheet from Section 1.6.
* Do exercises 1, 6 from Section 1.6.

Optional Material

* Think about a districting strategy that would yield a "fair" district map. Can your process be automated?

Today's VQ for Class Use

1/17: These exercises are due on 1/18. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) The Multiplication Principle
(2) The Addition Principle
(3) The Inclusion-Exclusion Principle

(4) The First Nine Rules
(5) Which Rule Was Used?
(6) Filling in the Rules
(7) Writing a Proof

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/19.

* Do exercises 3, 6 and 13 from Section 1.3.
* Do exercises 2, 4 from Section 1.6.
* Read Section 1.7 in the text.
* Re-read the in-class worksheet from Section 1.7.
* Do exercises 1ace, 2ace from Section 1.7.
* Read Section 2.1 in the text.
* Re-read the in-class handout over Section 2.1.
* Do exercise 1 from Section 2.1 as follows. If your last name begins with the letters A-K, prove logic rules Disjunctive Syllogism, Constructive Dilemma, Conjunction, and Double Negation. If your last name begins with the letters L-Z, prove logic rules Destructive Dilemma, Simplification, Addition, and Tautology (both parts).

Optional Material

* Continue to consider today's game, and determine whether 11 is a winning or losing state. (I still claim you will lose if you go first and your opponent plays corrected. See this graph.)
* How could you change the game to make it more interesting? Allow players to put some pieces back? Allow the players to take 1, 2, 3, or 4 pieces?

Today's VQ for Class Use

1/18: These exercises are due on 1/19. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Making a Bijection
(2) The Set \(\mathbb N\) is Not Finite

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/20.

* Do exercises 7 and 14 from Section 1.3.
* Do exercises 10, 11 from Section 1.6.
* Do exercises 1bd, 2bd from Section 1.7.
* Do exercise 2 from Section 2.1.
* Read Section 1.8 in the text.
* Re-read the in-class worksheet from Section 1.8
* Do exercises 1bcd, 3, 5, 6, 8, from Section 1.8.
* Read Section 2.2 in the text.
* Re-read the in-class handout from Section 2.2.
* Do exercises 1, 2, 3abcd from Section 2.2. (If you have trouble with problem 1, don't try problem 2! Ask for help in office hours or on the blog. If you have a lot of trouble with problem 2 (having a few problems isn't a big deal), don't move on to problem 3! Ask for help.)

Optional Material

* See if you can find more than one distict proof for the logic exercises assigned today.

Today's VQ for Class Use

1/19: Exam 1 will be given today. It will cover the material from in-class work on 1/11-1/17. That includes Sections 1.1-1.7 and 2.1. Expect to work for around 45 minutes, maybe less. The exam will be open notes. All of you are expected to be in class to take the exam unless you are ill or in COVID quarantine. If I have not given you permission to take the exam remotely, you should be in class! If you did not receive an email from me, you should be in class for the exam. The makeup exam is at 7:30 am on Friday.

This is an exam, and whether you are taking the exam in class or elsewhere, you should not do anything that you would not do if you were taking the exam in class in person.

You are not permitted to communicate with any human being by any means, including but not limited to, talking, phone conversations, text messages, email messages, hand signals, smoke signals, semaphore, Morse code, Norse code (used to communicate with vikings), social media, antisocial media, or any other means that I've omitted. You are not permitted to use any internet resource whatsoever. You are not permitted to use any text other than mine, any app on your phone, any app that's not on your phone, Google, WolframAlpha, or any other print or internet resource that I've omitted.

These exercises are due on 1/20. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) Rules of Replacement
(2) Applying the Rules
(3) Definition of Divides
(4) Types of Proofs

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/23.

* Read Section 1.9 in the text.
* Re-read the in-class handout over Section 1.9.
* Do exercises 1abg from Section 1.9.
* Do exercises 3efghi from Section 2.2 in the text. (If you can't finish the proof, take a few legal steps!)

Optional Material

* Nothing today, except to think about infinite sets and the material we covered today!

Today's VQ for Class Use

1/20: These exercises are due on 1/23. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) Induction, Part I
(2) Induction, Part II
(3) An Example of an Induction Proof
(4) The Word Graph
(5) Important Graphs

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/24.

* Read Section 2.3 in the text.
* Re-read the in class handout and your notes from Section 2.3.
* Do exercises 1 and 2 from Section 2.3 in the text. (If you have trouble with problem 1, don't try problem 2! Ask for help in office hours or on the blog. If you have a lot of trouble with problem 2 (having a few problems isn't a big deal), don't move on to problem 3! Ask for help.)
* Do exercises 3a-d from Section 2.3 in the text. (If you can't finish the proof, take a few legal steps!)
* Read Section 3.1 in the text.
* Re-read the in class handout and your notes from Section 3.1.
* Do exercises 1, 3, 7, 9, and 10 from Section 3.1 in the text. TYPE YOUR PROOFS FOR EXERCISES 1 AND 3! Your proofs for Exercises 7, 9 and 10 should also be written using complete sentences with correct punctuation. (You could type them all...) See the blog for some hints!

Optional Material

* Have a good weekend!

Today's VQ for Class Use


Week 3

1/23: These exercises are due on 1/24. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) The Division Algorithm
(2) Addition Modulo \(p\)

(3) Equivalent Graphs
(4) Planar Graphs

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/25.

* Do exercises 3efg from Section 2.3 in the notes. (If you can't finish the proof, take a few legal steps!)
* Read Section 3.2 in the text.
* Re-read the in class handout and your notes from Section 3.2.
* Do exercises 1adfj from Section 3.2 in the text. TYPE at least one of these problems, maybe all of them. Cut and paste is a wonderful tool!
* Read Section 5.1 in the text.
* Re-read the in class handout and your notes from Section 5.1.
* Do exercises 1, 3, 8aceg, 9aceg at the end Section 5.1 in the notes.

Optional Material

* Nothing today.

Today's VQ for Class Use

1/24: These exercises are due on 1/25. FINALIZED

* Watch these videos before our next class.
(1) Conditional Proof
(2) The Euclidean Algorithm
(3) The Chart Method

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/26.

* Do exercises 3jm from Section 2.3 in the notes. (If you can't finish the proof, take a few legal steps!)
* Do exercises 1ch, 6 and 7 from Section 3.2 in the notes. TYPE at least one part of question 1, and either 6 or 7. Any problems that are not typed should be written very neatly using complete sentences. I NEGLECTED TO DO AN INEQUALITY IN CLASS! YOU MAY OMIT 6 AND 7. I address inequalities in the reading, but didn't cover this topic in class.
* Do exercises 4,7, 8bdf, 9bdf at the end Section 5.1 in the notes.
* Read Section 3.3 in the text.
* Re-read your in-class worksheet from Section 3.3.
* Do exercises 1, 2, 4 from Section 3.3. You may use the Mathematica code for constructing the zero-divisor graphs.a
* Read Section 5.3 in the text.
* Re-read your notes from Section 5.3.
* Do exercises 2, 7 from Section 5.3.

Optional Material

* Find some structure in the zero divisor graphs! What if \(n\) is the product of two primes? Or a prime number squared?

Today's VQ for Class Use

1/25: These exercises are due on 1/26. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) No additional videos! If you want to get ahead, the videos to be assigned on Thursday are ready, as is the VQ. We WILL have class after Thursday's exam!

The exercises assigned today are due on 1/27.

* Do exercises 9 and 10 from Section 3.2 in the notes. TYPE at least one of these exercises. OMIT THESE! Inequalities again.
* Read this proof of how a contradiction can imply anything!
* Read Section 2.4 in the text.
* Do all of the exercises from Section 2.4 that were not done in class, or at least do problem 1-9.
* Read Section 3.4 in the text.
* Re-read your notes from Section 3.4.
* Do exercises 1 (using the Euclidean Algorithm!) 2, 8, and 9 from Section 3.4.

Optional Material

* Nothing today.

Today's VQ for Class Use

1/26: Exam 2 will be given today. It will cover the material from in-class work on 1/18-1/24. That includes Sections 1.8, 1.9, 2.2, 2.3, 3.1, 3.3, 5.1, and 5.3. Expect to work for around 60 minutes, but no more than 75 minutes. (The quiz isn't any longer, but some of you may get stuck on the logic proof(s).) The exam will be open notes. All of you are expected to be in class to take the exam unless you are ill or in COVID quarantine. If I have not given you permission to take the exam remotely, you should be in class! If you did not receive an email from me, you should be in class for the exam.

This is an exam, and whether you are taking the exam in class or elsewhere, you should not do anything that you would not do if you were taking the exam in class in person.

You are not permitted to communicate with any human being by any means, including but not limited to, talking, phone conversations, text messages, email messages, hand signals, smoke signals, semaphore, Morse code, Force code (used to communicate with Jedi knights), social media, antisocial media, or any other means that I've omitted. You are not permitted to use any internet resource whatsoever. You are not permitted to use any text other than mine, any app on your phone, any app that's not on your phone, Google, WolframAlpha, or any other print or internet resource that I've omitted.

These exercises are due on 1/27. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Permutations
(2) Combinations

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/30.

* Type a proof of Exercise 1k from Section 3.2. Make it look really good. This is your only written assignment today. Hopefully those of you who are little behind can use this weekend to catch up!

Optional Material

* Can you predict the order in which the loops appear in a Spirograph design?

Today's VQ for Class Use

1/27: These exercises are due on 1/30. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) Set Proofs
(2) An Example Proof

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 1/31.

* Read Section 6.1 in the text.
* Re-read your class notes for Section 6.1.
* Do exercises 1-9, 12, 13, 14, 15 from Section 6.1.
* Do exercise 6 from Section 3.2.

Optional Material

* Nothing today.

Today's VQ for Class Use


Week 4

1/30: These exercises are due on 1/31. These will prepare you for our next class. - FINALIZED

* Watch these videos before our next class.
(1) No new videos.

* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

The exercises assigned today are due on 2/1.

* Skim Section 4.1 in the text.
* Read Section 7.1, and skim Section 7.2 in the text.
* Prove that \((A\cap B)\subseteq A\).
* Do exercises 1 and 2ab from Section 7.1.

* Re-TYPE your proof of Exercise 1k from Section 3.2, making it look essentially like this. Your proof needs to have WORDS! Computations need to have a context. (This one exercise will be graded as a separate homework assignment.)

Optional Material

* Why 73 is Sheldon's Number. and why 42 was nominated for number of the year. The integer 1729 is known as the Hardy-Ramanujan number. Why was 12 nominated?

For more information on the Sheldon Conjecture, click here or check out this article in the November 2015 issue of Math Horizons, available in the MathLab or from me.

Voting Triangle 1 - Voting Triangle 2

Today's VQ for Class Use

1/31: These exercises are due on 2/1. These will prepare you for our next class. FINALIZED

* Watch these videos before our next class.
(1) No new videos.

No new exercises assigned today.

* No additional exercises to turn in. However, you should know how to prove that \(((A\setminus B)\cup (B\setminus A))\subseteq A\cup B\). You don't have to write this proof to turn in.

Optional Material

*

Today's VQ for Class Use

2/1: No new exercises are due on 2/2.

* Study for the final exam, which will cover the entire course.

Optional Material

* Don't Panic.

2/2: Our final exam is from 9:00-12:00 on Thursday, February 2. This exam covers the following sections: 1.1, 1.2, 1.3, 1.6, 1.8, 2.3, 2.4, 3.1, 3.2, 3.3, 3.4, 4.1, 5.1, 5.3, 6.1, 7.1, and maybe more to be added. Expect more from the material that was not on the first two exams. You may start as early as 8:00 if you wish.

These exercises are due on 2/2. These will prepare you for our next class.

* Watch these videos before our next class.
(1)
* While you are watching the videos or immediately after watching the videos, take this short quiz. You should take this quiz before our next class starts! If I don't have your response by 9:00 am, your quiz will be counted as late, and your score will be reduced, perhaps to 0. This will count as a quiz. You should also receive an email confirmation so you can check your answers.

These exercises are due on 2/3. They are due at the beginning of class, before I take questions over the assignment. Turn them in when you enter the classroom!

* Do

Optional Material

* Nothing yet

Today's VQ for Class Use