Unit 1: Logic
In this unit, you will begin by considering various puzzles, including Ken-Ken and Sudoku. You will learn the importance of tenacity in approaching mathematical problems including puzzles and brain teasers. You will also learn why giving names to mathematical ideas will enable you to think more effectively about concepts that are built upon several ideas. Then, you will learn that propositions are (English) sentences whose truth value can be established. You will see examples of self-referencing sentences which are not propositions. You will learn how to combine propositions to build compound ones and then how to determine the truth value of a compound proposition in terms of its component propositions. Then, you will learn about predicates, which are functions from a collection of objects to a collection of propositions, and how to quantify predicates. Finally, you will study several methods of proof including proof by contradiction, proof by complete enumeration, etc.
Completing this unit should take you approximately 31 hours.
Upon successful completion of this unit, you will be able to:
- determine the truth value of a proposition;
- use truth tables to verify the logical equivalence of two mathematical expressions, statements, and propositions, as well as to determine the category of a proposition: tautology, contingency, or contradiction;
- form the negation, contrapositive, converse, and inverse of a proposition;
- express statements formally using universal quantifiers, logical connectives, and predicates;
- use the technique "proof by contradiction” to verify a mathematical statement; and
- construct counterexamples to verify the falsity of a mathematical statement in particular contexts.
1.1: Sudoku and Latin Squares
Read this article. Try not to get sidetracked looking at variations. Pay special attention to the growth of the number of Latin squares as the size increases. Note that if you want to look ahead at the type of problem you will be asked to solve, check the file "Logic.pdf" at the end of Unit 2.
Read Tom Davis' paper, paying special attention to the way he names the cells and to his development of language. Next, if you have not done Sudoku puzzles before, Web Sudoku and Daily Sudoku and are two popular sites. Do one or two before moving on to Ken-Ken.
1.2: Ken-Ken
This article is optional. If you have an interest in solving Ken-Ken problems, then you will find this section interesting. Otherwise, omitting it will not hinder your understanding of subsequent material. Read this article for an introduction to Ken-Ken and complete the exercises in the PDF.
This activity is optional. Attempt to complete one of these puzzles. Note that you can choose the level of difficulty (easier, medium, and harder). After a few practices, challenge yourself to attempt a Ken-Ken puzzle that is at the next level of difficulty. Do not allow yourself to get addicted!
1.3: SET
This activity is optional. Read the game rules by clicking on the "daily puzzle rules" link, and play a bit.
1.4: Other Brain Teasers
Pick out a few videos to watch on brain teasers. The puzzle will be introduced to you at the beginning of the video. You should pause the video and attempt to solve the puzzle before viewing the solution. Watch the solutions only if you absolutely cannot solve the puzzle; then, go back and reattempt the problem.
1.4.1: Truth Tellers and Liars
Work on the problems on this webpage: liars and truth-tellers puzzles, the Rubik's cube, knots and graphs, and arithmetic and geometry.
1.4.2: Coin Weighing Puzzles
Problems about finding the counterfeit coin among a large group of otherwise genuine coins are quite abundant. Attempt to solve the problem on this webpage. Solutions appear at the bottom of the webpage. If this type of logical thinking interests you, attempt to find similar problems to solve with an online search.
1.5: Propositional Logic
Read this page. This text will enable you to see the very close connection between propositional logic and naïve set theory, which you will study in Unit 3.
Watch this lecture. In particular, focus on the information provided from the 12-minute mark until the 18-minute mark. In this lecture, you will learn which sentences are propositions.
1.5.1: Compound Proposition
Watch this video, which will help you later when you are asked to build proofs of statements about rational numbers and about integers.
Watch this video, which will help you later when you are asked to build proofs of statements about rational numbers and about integers.
Read this article, which covers the properties of connectives. While reading, pay special attention to the connection between the Boolean connective and its Venn diagram.
1.5.2: Truth Tables
Read these four sections of Koehler's lectures on logic and set theory. A contingency is simply a proposition that is caught between tautology (at the top) and contradiction (at the bottom). In other words, it is a proposition which is true for some values of its components and false for others. For example "if it rains today, it will snow tomorrow" is a contingency, because it can be true or false depending on the truth values of the two component propositions.
1.6: Predicate Logic
1.6.1: Modus Ponens and Modus Tollens
1.6.2: Proofs by Contradiction
Read the following sections: "Introduction", "Definition and Theorems", "Disproving Statements", and "Types of Proofs". The types of proofs include Direct Proofs, Proof by Contradiction, Existence Proofs, and Uniqueness Proofs. You may stop the reading here; we will cover the sixth one, Mathematical Induction, later in the course.
1.6.3: Problem Solving Strategies
Read through the examples in the article. The problems are not difficult, but they do serve as clear illustrations of the various aspects of entry-level problem solving.
1.6.4: Contrapositive and Equivalent Forms
- Gowers' Weblog: "Basic Logical Relationships between Statements, Converses, and Contrapositives" URL
Read this article, paying special attention to the parts of converses and contrapositives.
Unit 1 Assessment
Complete this 10-question quiz on logic and related conditionals. Once you choose an answer, a pop up will tell you if you have chosen correctly or incorrectly. You may also click on the drop down menu for an explanation.
- Receive a grade
Take this assessment to see how well you understood this unit.
- This assessment does not count towards your grade. It is just for practice!
- You will see the correct answers when you submit your answers. Use this to help you study for the final exam!
- You can take this assessment as many times as you want, whenever you want.
