Section2Logic¶ permalink

Hopefully you get a taste of what it means by "convincing justifications" in Task 1.1. Whether a justification is convincing or not should not depend on who came up with it. A convincing justification not only needs to convince a Fields Medalist but also math major students, or anyone who has the backgrounds of the context. A convincing justification is called a proof and that is what you will learn to construct for the rest of this class. To construct proofs, we will need our own vocabulary and grammar. Let’s get started.

Subsection2.1Statements

Definition2.1

A statement is a declarative sentence that is either true or false but not both. We refer to true (T) or false (F) as the truth value of the statement.

A definition is an exact, unambiguous explanation of the meaning of a mathematical word or phrase. Definitions are the starting points of all mathematical reasonings. They are assumed to be true at all times! All mathematical theorems are derived from definitions.

Task2.2

Which one(s) of the following is/are statement(s)? Determine their truth values for those that are statements (if possible).

Albany is the capital of New York State.
She graduated from Utica College last year.
Run!
The land area of United States of America is larger than the land area of People's Republic of China.

Task2.3

Which one(s) of the following is/are statement(s)? Determine their truth values for those that are statements (if possible).

$x$ squared plus $1$ is equal to $3$.
There will be rain in Utica, NY on Dec. 3, 2075.
Leonardo da Vinci's Mona Lisa is a beautiful paint.

Task2.4

Which one(s) of the following is/are statement(s)? Determine their truth values for those that are statements (if possible).

The $10^{39}$th digit of $\pi$ is $7$.
The twins were born on Monday.
Julius Caesar (an ancient Roman dictator) ate eight eggs on the day that he was assassinated.

The truth value of a statement is unambiguous but it does not mean that it is known by anyone. For some statements, we might have to wait to find out their truth values. For other statements, we might not know their truth values till the end of the time.

Some sentences are not statements because they are not declarative. Other sentences are not statements because they use subjective words that cannot be agreed by all people. But there are some sentences that are not statements simply because they use pronouns that are not clear to other people. For example, a sentence like \begin{gather} x \; \text{is a positive rational number}.\label{predicate}\tag{2.1} \end{gather} is too ambiguous to be a statement because we do not know the value of $x$. If $x = 1$, then the sentence (2.1) becomes "1 is a positive rational number", which is a true statement; if $x = \pi$, then the sentence (2.1) becomes “$\pi$ is a positive rational number” which is a false statement.

A sentence like (2.1) is called a predicate. A predicate has a free variable that may be allowed to take on many possible values. In sentence (2.1), the free variable is "$x$" and can be taken on any numbers. If you really want, you can take $x$ to be a cat and the predicate becomes “A cat is a positive rational number”. Of course it is a false statement.

Task2.5

Which sentence(s) in Task 2.2, 2.3 and 2.4 is/are predicate(s)? Can you find the free variable for each predicate? Turn the predicates into statements by taking some specific values for the free variable and decide if the statements are true or false.

Subsection2.2Quantifications

There is another way to turn a predicate into a statement, that is, by adding quantifiers. For example, sentence (2.1) is a statement if we add the following type of quantification:\begin{equation*}\text{For every positive integer $x$, $x$ is a positive rational number.}\end{equation*}or a different type of quantification:\begin{equation*}\text{There exists a rational number $x$ such that $x$ is a positive rational number.}\end{equation*} What are the truth values of the previous two statements?

There are two quantifiers:

the universal quantifier for all (notation $\forall$)
the existential quantifier there exists (notation $\exists$)

Task2.6

The following are examples of statements with quantifiers. Identify which quantifier is used in each statement (you might have to restate a statement in a different way to find out the answer.) Determine the truth value of each statement.

For all non-zero integer $x$, $x^2 \gt x$.
For every non-zero real number $x$, $x^2 \gt x$.
It is true that $x^2 = -1$ for some real number $x$.
For each member of the United States Senate, they represent one of the fifty states of United States.

Task2.7

All students in MAT 100 Basic Mathematics course at Utica College have passed the class in Fall 2016.
At least one book from Utica College library is hardcover.
Every college in United States has a mathematics program.

Task2.8

Some student at Utica College has a dog.
There exists a real number $x$ such that $x^2 = -1$.
Every square is a rectangle.

It is very important to provide enough context to avoid ambiguities when using free variables. For example, if we are talking about real numbers, then it makes sense to say that "For any $x$, $x + 1 \gt x$" and it is a true statement. But if the range of values of $x$ is not clear, we can say that the statement "For any $x$, $x + 1 \gt x$"" is false because "$i+1$ is not greater than $i$" as we cannot compare complex numbers. So we should always be clear about the context.

We shall realize that the phrases "for all", "for any", "for every" and "for each" are used interchangeably in mathematical English. We can also use the phrase "for some" to replace "there exists". For example, the statement "The inequality $x^2 \gt 10$ holds for some real number $x$" has the same meaning as "There exists a real number $x$ such that $x^2 \gt 10$". Also, we do not use the symbols $\forall$ and $\exists$ in formal written mathematics although they are convenient for informal mathematical discourse.

Subsection2.3Logical Connectives¶ permalink

In this section, we will introduce four logical connectives so that we can combine statements into more complex statements to state more complicated mathematics and to construct its proof. We will use $P, Q, R, \dots$ to denote generic statements and $P(x), Q(x), R(x), \dots$ to denote generic predicates where $x$ is the free variable.

Subsubsection2.3.1AND

Definition2.9

If $P$ and $Q$ are two statements, then $P$ and $Q$ is called the conjunction of $P$ and $Q$, denoted by $P \land Q$.

What is the truth value of $P \land Q$? Let us consider the following example: \begin{gather} \text{Mike can swim and ski}.\label{andexample}\tag{2.2} \end{gather} Let $P$ denote "Mike can swim" and $Q$ denote "Mike can ski". Then the statement (2.2) can be rewritten as $P \land Q$. We say that the statement (2.2) is true exactly when Mike knows how to swim and knows how to ski at the same time. If Mike cannot swim or cannot ski, then statement (2.2) is false. Thus for generic statements $P$ and $Q$, $P \land Q$ is true only if $P$ and $Q$ are both true. We can use a table to describe this:

$P$	$Q$	$P \land Q$
T	T
T	F
F	T
F	F

Table2.10Truth table for $P \land Q$

Since $P$ and $Q$ are generic statements, we do not know their truth values. We have to list all possible combinations of the truth values of $P$ and $Q$. As $P$ and $Q$ can be true or false, we have $2 \times 2 = 4$ different combinations.

Task2.11

Fill in all the blanks of the truth table for $P \land Q$ with either T or F. Determine the truth values of the following statements.

$5$ is an odd number and a prime number.
$9$ is an odd number and a prime number.
$2$ is an odd number and a prime number.
$4$ is an odd number and a prime number.

Subsubsection2.3.2OR

Definition2.12

If $P$ and $Q$ are two statements, then $P$ or $Q$ is called the disjunction of $P$ and $Q$, denoted by $P \lor Q$.

Here is an example of use of "or".

\begin{gather} \text{Eat your dinner or you cannot have ice-cream}.\label{dailyor}\tag{2.3} \end{gather}

The above statement is true when exactly one of the following happens:

you eat the dinner (and then you can have ice-cream) or
you cannot have ice-cream (because you did not eat your dinner).

Assuming that the statement (2.3) is true, then it is not possible for both (1) and (2) happen at the same time. In our daily lives, this is how we use "or" most of the time, that is, "$P$ or $Q$" is true when exactly of one of them is true but not both.

Unfortunately, this is not how we use "or" in mathematics. In mathematical logic, "$P$ or $Q$" is true when at least one of $P$ and $Q$ is true. In other words, "$P$ or $Q$" is true if $P$ is true or $Q$ is true or both of $P$ and $Q$ are true. Here is the truth table for $P \lor Q$

$P$	$Q$	$P \lor Q$
T	T
T	F
F	T
F	F

Table2.13Truth table for $P \lor Q$

Task2.14

Fill in all the blanks of the truth table for $P \lor Q$ with either T or F. Determine the truth values of the following statements.

$5$ is an odd number or a prime number.
$9$ is an odd number or a prime number.
$2$ is an odd number or a prime number.
$4$ is an odd number or a prime number.

Subsubsection2.3.3NOT

Definition2.15

If $P$ is a statement, then not $P$ is called the negation of $P$, denoted by $\sim P$.

The truth table for $\sim P$ should be straightforward. Try to fill in the blanks of the following table.

$P$	$\sim P$
T
F

Table2.16Truth table for $\sim P$

Let us see how to get a useful negation of a statement. Consider the statement: $3 \gt \pi$. We can negate this statement as "It is not true that $3 \gt \pi$". This is correct but not very useful. A more useful negation would be "$3 \leq \pi$".

Task2.17

Write the negation of the following statements, without just putting the phrase "It is not true that ..." in front of the given phrase. Try your best to make the negation useful by not using the word "not" whenever possible.

The function $y = e^x$ is increasing on the interval $[0,1]$.
$-1+3$ is less than $2$.
$\sqrt{5}$ is an irrational number.

Task2.18

The number of solutions of the equation $x^2-2x+1=0$ is equal to $1$.
Utica College does not have a law school.
An odd number times an odd number is an odd number.

Negations of statements that have quantifiers are slightly more tricky.

Task2.19

Every student enrolled in Utica College in Fall 2016 has taken Calculus I.
All students in the basic mathematics class at Utica College are female.
No sedan has more than six seats.

Task2.20

There exists a real number $x$ such that $x^2+x+1 \lt 0$.
Every even integer greater than $2$ can be expressed as the sum of two prime numbers.
There is someone in the world who have purchased all the vinyl record of Herbert von Karajan published by Deutsche Grammophon released after year 1950.

Task2.21

Consider the following two statements:

For every student S that was taking classes during the Fall 2014 semester at Utica College, there was a course C offered in the same semester at Utica College such that S was not taking C.
There was a course C offered during the Fall 2014 semester such that for every student S that was taking classes during the same semester, S was not taking C.

What is the truth value of the above two statements? Do they have the same meaning? In general, what can we say about the order of the quantifiers?

Subsubsection2.3.4If ..., then ...

Definition2.22

If $P$ and $Q$ are two statements, then "If $P$, then $Q$" is called an implication in which $P$ is called the hypothesis and $Q$ is called the conclusion, denoted by $P \Rightarrow Q$.

First let us find the truth table of ``if ..., then ...''. Consider the following statement: \begin{gather} \text{If tomorrow does not rain, then Mike will go shop at Target.}.\label{ifthenexample}\tag{2.4} \end{gather} Under what situation can we say that the statement (2.4) is false? If tomorrow indeed does not rain but Mike decides not to go shop at Target, then statement (2.4) is certainly false.

Some people would also argue that the statement (2.4) is false in the event that tomorrow does rain and Mike does go shop at Target. Unfortunately, this is not what mathematicians agree upon. In other words, statement (2.4) makes a claim (Mike will go shop at Target) under the assumption that tomorrow does not rain. Statement (2.4) contains absolutely no information about what is going to happen if tomorrow does rain. Therefore, if tomorrow does rain, we cannot say that statement (2.4) is false no matter what happens. Now read this paragraph again before you move on.

To summarize, statement (2.4) is only false when tomorrow does not rain but Mike decides not to go shop at Target. In all other cases, statement (2.4) is true! Now fill in the following truth table.

$P$	$Q$	$P \Rightarrow Q$
T	T
T	F
F	T
F	F

Table2.23Truth table for $P \Rightarrow Q$

Task2.24

Fill in all the blanks of the truth table for $P \Rightarrow Q$ with either T or F. Determine the truth values of the following statements. For each statement, try to explain briefly why you think it is true or false.

If Dell is a company that makes computer, then Colgate is a company that makes toothpaste.
If there is Santa Claus, then there is no war in this world.
If Amazon sells books, then Wal-Mart sells cars.
If Beethoven is not a music composer, then da Vinci is an artist.

Some of the ways that "if...then..." are being used in Task 2.24 are strange. There are at least two reasons. The first is that if we know for sure the truth value of the hypothesis $P$, then we will never say "if $P$, then $Q$" as there is no need to assume the truthfulness of $P$ (see below for one exception). The second reason is that when we say "if $P$, then $Q$", there must be some relationships between $P$ and $Q$. Some of the hypotheses and conclusions in Task 2.24 have no real connections. Here are some examples of how we do use ``if...then...'' in our daily life.

The hypothesis $P$ is an entirely hypothetical situation that is false. For example, "If I were you, then I will quit this job." or "If Euler does not know math, then nobody knows math."
The hypothesis $P$ is a statement whose truth value is not known now but may be found out at a later time. For example, "If tomorrow rains, then I will go out."; or "If I win the lottery someday, then I will donate all of them."
The hypothesis $P$ is a statement whose truth value is known to the human society but not known to the speakers. For example, "If England has ever won a World Cup, then I will give you ten dollars."

In mathematics, what usually comes after "if" is a predicate and the predicate can sometimes have more than one variable.

Task2.25

Determine the truth values of the following statements. For each true statement, try to explain briefly why you think it is true; for each false statement, try to provide an example.

If $x$ is an integer, then $x^2 \geq 0$.
If $x$ and $y$ are two positive integers, then $x-y$ is also a positive integer.

Can you restate the above two statements without using "if...then.."?

Definition2.26

An example that proves the falsity of a universal ("for all") statement is called a counterexample.

Task2.27

Launched in 1999, the United States Mint's 50 State Quarters Program produced 50 quarters in ten years (from 1999 to 2008), each has a state design on the tail. Let us assume that the year is printed on the head. Now suppose that you have four of these coins and you see: 2005, Nebraska, Wyoming and 2004 on one side of these coins. Determine which coin(s) need to be flipped over in order to find out the truth value of the statement: If the year is a multiple of four, then the state begins with the letter M or N.

There are three statements that are naturally associated with an implication. They are created by reversing the direction of the implication and/or adding negations.

Definition2.28

Let $P$ and $Q$ be two statements. The converse of the statement $P \Rightarrow Q$ is the statement $Q \Rightarrow P$. The inverse of the statement $P \Rightarrow Q$ is the statement $(\sim P) \Rightarrow (\sim Q)$. The contrapositive of the statement $P \Rightarrow Q$ is the statement $(\sim Q) \Rightarrow (\sim P)$.

Task2.29

Find the converse, inverse, and the contrapositive of the following statement:\begin{equation*}\text{If $x \gt 0$, then $x^2 \gt 0$.}\end{equation*} Then determine the truth value of all four statements. Briefly explain why they are true or false.

Definition2.30

Let $P$ and $Q$ be two statements. If an implication $P \Rightarrow Q$ and its converse $Q \Rightarrow P$ are both true, then we say that $P$ if and only if $Q$, and denote it by $P \Leftrightarrow Q$. The connective "if and only if" can be abbreviated as "iff" for informal writing.

If the statement $P \Leftrightarrow Q$ is true, then $P$ and $Q$ are both true exactly at the same time, and are false exactly at the same time. We also call it $P$ is logically equivalent to $Q$. The truth table of $P \Leftrightarrow Q$ is as follows:

$P$	$Q$	$P \Leftrightarrow Q$
T	T
T	F
F	T
F	F

Table2.31Truth table for $P \Leftrightarrow Q$

How to check two statements are logically equivalent? We will investigate this question in the next section.

Subsection2.4Using Truth Tables

In Section 2.3, we investigated the truth tables of $P \land Q$, $P \lor Q$, $P \Rightarrow Q$ and $\sim P$. We can use them to construct truth tables for more complicated statements. Here is an example.

Task2.32

Construct the truth table for $(\sim P) \lor Q$ as follows:

As $P$ and $Q$ can be T or F (but not both), there are $2 \times 2 = 4$ rows in the truth table, with all possible combinations of truth values of $P$ and $Q$.
Write a column that gives the truth values of $\sim P$ in each of the above four possibilities. This column should only depend on the column that contains the truth values of $P$.
Now use the two columns that contains the truth values of $\sim P$ and the truth values of $Q$, construct a new column that contains the truth values of $(\sim P) \lor Q$.

Once you are done, cover the column of $\sim P$ and compare the truth table of $(\sim P) \lor Q$ with the truth table of $P \Rightarrow Q$. What have you discovered?

Surprised about the answer? Because of what you have discovered, we can conclude that $P \Rightarrow Q$ and the statement $(\sim P) \lor Q$ are logically equivalent. Using the notation "$\Leftrightarrow$", it can be denoted as \begin{equation*}(P \Rightarrow Q) \Leftrightarrow ((\sim P) \lor Q).\end{equation*} Another example would be $P$ is logically equivalent to $\sim (\sim P)$ (you should write down the details by yourself).

Task2.33

For any given implication $P \Rightarrow Q$, show that

it is logically equivalent to its contrapositive and
its inverse and converse are logically equivalent.

Task2.34

Show that \begin{equation*}(P \Leftrightarrow Q) \Leftrightarrow ((P \Rightarrow Q) \land (Q \Rightarrow P)).\end{equation*}

The previous task says that $\Leftrightarrow$ can be defined using $\Rightarrow$ and $\land$.

Task2.35

Let $P, Q$ and $R$ be three statements. Show that $P \Rightarrow (Q \lor R)$ is logically equivalent to $(P \land (\sim Q)) \Rightarrow R$.

It is often we have to negate a statement that involves the logical connectives "and" and "or". The DeMorgan's Law tells use how to do this in general.

Task2.36DeMorgan's Law

Let $P$ and $Q$ be two statements. Then

$\sim ( P \land Q)$ is logical equivalent to $(\sim P) \lor (\sim Q)$.
$\sim (P \lor Q)$ is logical equivalent to $(\sim P) \land (\sim Q)$.

Task2.37

Use the DeMorgan's Law to negate the following statements:

Manchester United won the first or the second game of the 2014-15 season of Premier League.
The function $f$ of Exercise 13.1 of our calculus book has positive first and second derivatives at $x=0$.
There exists a student at Utica College who scored full mark on SAT and has a 4.0 GPA.

Task2.38

Negate the following statements:

For every kid at Utica, if they play soccer, then they play football.
For some shoemaker in United States, if they make boots, then they also make oxfords.

Task2.39

Show that $\sim (P \Rightarrow Q)$ is logically equivalent to $P \land (\sim Q)$. Can you do it without using their truth tables?

Task2.40

Let us recall an example of an "if...then..." statement:

\begin{gather} \text{If $x$ and $y$ are positive integers, then $x-y$ is also a positive integer.} .\label{universalifthen}\tag{2.5} \end{gather}

Negate statement (2.5) using Task 2.39. Are there anything wrong?
Add a quantifier to the statement (2.5) without changing its meaning.
Then negate the statement that contains the quantifier you added. Does this one make sense now?

Task2.41

Show that $S$ is logically equivalent to $(\sim S) \Rightarrow (R \land (\sim R))$.

Definition2.42

A statement like $R \land (\sim R)$ that is never true is called a contradiction.

If we consider the truth table of $R \land (\sim R)$, we see that no matter $R$ is true or false, $R \land (\sim R)$ is always false.

$R$	$(\sim R)$	$R \land (\sim R)$
T	F
F	T

Table2.43Truth table for $R \land (\sim R)$

\(P\)	\(Q\)	\(P \land Q\)
T	T
T	F
F	T
F	F

\(P\)	\(Q\)	\(P \lor Q\)
T	T
T	F
F	T
F	F

\(P\)	\(\sim P\)
T
F

\(P\)	\(Q\)	\(P \Rightarrow Q\)
T	T
T	F
F	T
F	F