Logic Unit #

developed by Jennifer Taback
adapted by Thomas Pietraho

This independent unit introduces you to the language of mathematics. If you think of writing mathematics as learning a new language, and think back to the time when you learned French, Spanish, German or English (or other languages, if your high school was lucky enough to offer them), you will remember how slow it was initially to express yourself in that new language!

We will learn the structure of the language of mathematics through logic. Many times, mathematics and English will agree, but sometimes they will differ, and those instances will require extra care. The following example is due to Terry Tao and taken from his text Analysis I :

By the way, one should be careful with the English word “and.” If one talks about a set of “boys and girls”, one means the union of a set of boys with a set of girls, but if one talks about the set of people who are single and male, then one means the intersection of the set of single people with the set of male people.

This unit is meant for you to work through independently, and then attend one of the discussion sessions hosted by your professor or the class learning assistant. Completing this content will count as one homework assignment for which you will receive full credit.

Notation for sets of numbers #

Please watch this video before anything else. It introduces the shorthand notation we will use for different sets of numbers.

1. Introduction to logical reasoning #

This section is a guided reading to several parts of the textbook. Please do the reading and try the suggested exercises. The sections in the text are discussed in the videos below as well. For help with these problems, write to your professor, come to office hours, attend a session with a learning assistant or join a discussion session about these problems. You do not have to turn in these problems, but you would be expected to complete similar problems on a quiz or exam.

Note: These problems must be completed independently but are not to be turned in You will be expected to do similar problems on a quiz or exam, or in class. These problems will be discussed during an extra class session. It is important that you learn the terminology in this section. If I use the word contrapositive, for example, I don’t want to get blank looks! These ideas will be used throughout the semester in a variety of different contexts. Please learn them! As part of this assignment, you will read Sections 1.1, 1.2, 1.3 and (most of) 1.5 from the textbook. The notes below add some commentary to your reading, and tell you which parts are most important. I would read along with the outline below instead of just reading the sections independently.

1.1 Mathematical statements #

Our language of mathematics has the statement as its building block. A statement has a defined truth value – it can be true or false but not both; for example, “James is in College” is not a statement because its truth value varies depending on who James is. But \(2+2=4\) is a statement because it is always true. Similarly, \(2+3=1\) is a statement as well, because it is always false.

Exercise: Look at problem 1 on page 5 of the course text. Can you decide which are statements?

1.2 Conjunctions and disjunctions #

Just like in English, where we connect nouns and verbs with various connectives (and, or, but, if, etc) we have similar structures in logical reasoning. Read Section 1.2, which will introduce the negation of a statement, the conjunction of statements (“and”) and the disjunction (“or”). We will begin to represent statements by letters like \(P\) and \(Q\).

When we write “\(P\) and \(Q\)” where \(P\) and \(Q\) represent statements, we don’t immediately know the truth value of this compound statement, because it will depend on what \(P\) and \(Q\) actually are. So we call “\(P\) and \(Q\)” (mathematically written \(P \wedge Q\)) a statement form. This means that when you substitute actual words for \(P\) and \(Q\) you always get a statement, that is, something with a fixed truth value. The \(P\) and \(Q\) are like placeholders.

To keep track of all the possible truth values of \(P\) and \(Q\) separately, as well as the truth value of the compound statement, we use a truth table. These are explained in Section 1.2. Note that the book calls statement forms sentential forms. At the end of Section 1.2, you should be able to make truth tables for the statements \(P \vee Q\), \(P \wedge Q\) and \( \sim P\) . You should understand the difference between a statement and a statement form.

Exercise:

Now try problem 1 on page 15. Also make truth tables for the following statement forms:

\(P \wedge \sim Q\)
\(P \wedge \sim P \)
\(P \vee (Q \vee \sim Q)\)

This works just like order of operations – evaluate the truth value of expressions inside parentheses first; and negation is done before conjunctions and disjunctions.

1.3 Conditional statements #

Now read Section 1.3. This section introduces a very important structure both in English and in mathematics: the conditional statement, that is, a statement of the form “if \(P\) then \(Q\)”, written as \(P \rightarrow Q\). Here is the way you should think about the truth value of a statement form representing a conditional: it is true when it is not false. So figure out when it is false - when the first thing happens and the second one does not. In all other cases it must be true. This leads to things like “If Searles is made of chocolate then pigs fly” being a true mathematical statement. After this section you should be able to make a truth table for \(P \rightarrow Q\).

Exercise:

Do problems 11 and 18 on page 17. Remember the word tautology from this problem. Some statement forms are called contradictions. What do you think the truth table for a contradiction looks like? Can you make up a statement form which is a contradiction? Make the truth tables for the following:

\((P \wedge Q) \rightarrow R\)
\((P \rightarrow Q) \vee R\)

The key to making truth tables is to make columns for all the different expressions using the order of operations dictated by the parentheses. So, in the first example, my truth table will have columns corresponding to: \(P\), \(Q\), \(R\), \(P \wedge Q\), and finally \((P \wedge Q) \rightarrow R\). Always start with the single variables – first you will have to figure out how many different combinations of truth values three variables can have!

1.4 Variations on conditional statements #

If \(P \rightarrow Q\) is your original conditional statement, then:

\(Q \rightarrow P\) is called its converse,
\(\sim P \rightarrow \sim Q\) is called its inverse, and
\( \sim Q \rightarrow \sim P\) is called its contrapositive.

Exercise: Write the converse, inverse and contrapositive for the statement “If \(p\) is prime, then \(p^2\) is not prime.”

Read Section 1.5, up to (but not including) the replacement principle. Here are the main ideas of this section.

Two statement forms are said to be logically equivalent if they have the same truth tables. This means that they are true in exactly the same cases and can be used interchangeably.
DeMorgan’s Laws are rules about how to negate a compound statement like \(P \wedge Q\) or \(P \vee Q\). Make sure you can reason out in words why DeMorgan’s Laws are true. (This will also be discussed in the session.)

Exercise:

Which of the following are logically equivalent? Please show your truth tables.

\(P \rightarrow Q\)
\(Q → P\)
\(\sim P \rightarrow\sim Q\)
\(\sim Q \rightarrow\sim P\)

Do problem 3(a,b) on Page 30. Look again at De Morgan’s laws on page 28. (Equation 1.28). Apply them repeatedly to negate the following expressions. Continue to apply them until there are no negated parenthetical expressions.

\(\sim ((P \wedge Q) \vee R)\)
\(\sim ((P \vee Q) \wedge (Q \vee R))\)

Exercise: Figure out how to negate a conditional statement. Surprisingly, the negation of a conditional is NOT a conditional! Write out the truth table for \(P \rightarrow Q\). From this, you can figure out what the final column in the truth table for \(\sim (P \rightarrow Q)\) must be. Write this down. Everyone always thinks that \(\sim (P \rightarrow Q)\) must be \(\sim P \rightarrow\sim Q\). Make a truth table for this statement to see that it is NOT the negation of \(P → Q\). To figure out what \(\sim (P \rightarrow Q)\) must be, ask yourself this: If \(\sim (P \rightarrow Q)\) is true, how would I make it false? See if the answer to that question leads you to the negation you are looking for. You can always check your answer by making a truth table, because you KNOW what the truth table for \(\sim (P \rightarrow Q)\) must have as its final column! This will be discussed at length in one of the videos on the Logical Reasoning webpage.

Exercise:

Complete the following extercises from the course texybook:

Page 5 #1 (yes or no, no explanation required)
Page 15 #1(a),11(a,b,d),18(a,b)

1.5 Companion videos #

The following two videos are good companions to the above. You may watch them at any time as you are working through this material.

2. Expanding our language of mathematics: quantified statements #

Quantified statements let us talk precisely about “how many” objects in a set have a property. They allow for precise, generalized logical arguments and proofs, forming the foundation of logic and are crucial in mathematics, computer science, and philosophy. Please watch the following video for an introduction.

3. Negating quantified statements #

Negating quantified statements is fun and important. Please watch the following video to see how it is done. When you are done, complete the exercises from this section. Their solutions are included for your enjoyment.

Exercise:

For each of the quantified statements below, please do three things:

Decide whether the statement is true or false.
Justify the truth value.
Write the negation, simplifying as much as possible, which means until there are no more negation signs in your answer.

To complete the problems below, you will need to watch the video on quantified statements, and the video on negating quantified statements.

\(\forall x \in \mathbb{R}, x^2 \in \mathbb{Q}\)
\(\exists x \in \mathbb{Q}, x^2 < x\)
\(\exists x \in \mathbb{R} \text{ so that }x^2 = 2\)
\(\exists x \in \mathbb{R} \text{ so that } x^2+2x+2 = 5\)
\(\forall x \in \mathbb{Z}, x^2 = x\)
\(\forall x \in \mathbb{Q}, x+1 \in \mathbb{Q}\)

Solutions

Solutions are linked here.

4. Doubly quantified statements #

This section introduces even more complex mathematical statements. Again, there are exercises and solutions after the video.

Exercise:

For each of the quantified statements below, please do three things:

Decide whether the statement is true or false.
Justify the truth value.
Write the negation, simplifying as much as possible, which means until there are no more negation signs in your answer.

To complete the problems below, you will need to watch the video on doubly quantified statements.

\(\forall x \in \mathbb{R}, \exists y \in \mathbb{R} \text{ so that } 2x + y = 3\)
\(\exists x \in \mathbb{R} \text{ so that } \forall y \in \mathbb{R}, 2x + y = 3\)
\(\forall z \in \mathbb{Q}, \exists w \in \mathbb{Z} \text{ so that } zw \in \mathbb{Z}\)
\(\forall x \in \mathbb{N}, \exists y \in \mathbb{N} \text{ so that } xy = 2\)
\(\exists a \in \mathbb{Z} \text{ so that } \forall b\in \mathbb{Z}, ab = b \)
\(\exists a \in \mathbb{Z} \text{ so that } \forall b \in \mathbb{Z}, ab = a\)

Solutions

Solutions are linked here.

5. More examples of doubly quantified statements #

This video contains two additional examples of how to determine the truth value of, and then justify, doubly quantified statements. Watching this video is optional.