Mathematical Proof/Introduction/Logical Reasoning

Template:Mathematical Proof/navigation As discussed in the [[../|introduction]], logical statements are different from common English. We will discuss concepts like "or," "and," "if," "only if." (Here I would like to point out that in most mathematical papers it is acceptable to use the term "we" when referring to oneself. This is considered polite by not commanding the audience to do something nor excluding them from the discussion.)

Truth

A truth statement is one that is either true or false, not neither, and not both. Therefore, the sentence "This sentence is false." is not a truth statement because its truth value cannot be determined. However, the sentence "All people are cows." is a truth statement because its truth value can be determined, and is clearly false, since there are some people that are not cows. In mathematics, normally this phrase is shortened to statement to achieve conciseness and to avoid confusion.

The truth value of a statement is an evaluation of whether the statement is true or false. Thus, the truth value of "2 < 3" is true and "4 > 5" is false.

In discussing logic and statements, it is common to use the letters P and Q as variables to denote statements. Throughout this section, this convention will be followed. We will now discuss logical connectors, or conjunctions that connect statements.

Or

The connector "or" is used to connect two statements and make a third statement whose truth value is based on the first two. The statement "P or Q" is true if either P or Q is true, or if both of them are true. Therefore, the statement, "The internet is complex or math is exciting." is true, as is "7 > 9 or 2 < 3." The only time the statement "P or Q" is false is when both P and Q are false, e.g., "All people are American or all Americans are tall."

"Or" is sometimes denoted as $\vee$. So $P\vee Q$ means "P or Q." This is also sometimes referred to as disjunction.

And

"And" is used to connect two statements, just as "or"; however, "P and Q" is only true when both P and Q are true, and false otherwise. The statement "I like cheesecake and broccoli." is true since the statements "I like cheesecake." and "I like broccoli." are both true. Of course, it doesn't mean that I like them together on the same plate or in my mouth at the same time as one might infer.

"And" is sometimes denoted as $\wedge$. $P\wedge Q$ means "P and Q." This is referred to as conjunction.

Implications

This is another class of logical connectors, like "and" and "or." The three implication types are "if" $\Rightarrow$, "only if" $\Leftarrow$, and "if and only if" or "iff" $\iff$. See also Necessary and sufficient conditions. The vast majority of mathematical proofs deal with statements such as $P\Rightarrow Q$ or $P\iff Q$.

Necessary

To say that "P is necessary for Q" means that Q cannot exist without P. Another way of saying this is "P only if Q" or "if Q then P". Thus the statement "Sunday is necessary for Easter" is true because if it is Easter, then it is also Sunday. Yet, the statement "Water is necessary for humans" is, in a logical sense, false because something that is a human is probably not water as well. (However, the statement "Having water is necessary for humans" is true, because to be a human being something must contain water.) The statement "Q only if P" is false only when Q is true and P is false.

Sufficient

To say that "P is sufficient for Q" means "P cannot exist without Q" or "if P then Q". The notation for this is $P\Rightarrow Q$. This statement is only false when P is true and Q is false. This is the same statement as $Q\Leftarrow P$, but the roles are reversed; the former, however, is more common.

The interesting thing about an implication (an if-then statement) is that in the case that P is false, $P\Rightarrow Q$ is always true. Thus, "If the world is flat, then the Sun does not exist" is a true statement. This kind of a statement is called vacuously true because Q can be replaced with any statement and the implication is still true. In fact, the mathematician Bertrand Russell boasted, "Give me any false statement and any other statement to prove and I will prove it". Given the statement "1 = 2" he was asked to prove that he was God. "Consider the set $\{Russell,God\}$", he replied, "since 1 = 2, the two elements are one, and therefore Russell = God".

"If" and "only if" statements are called conditional statements. These two are related—they are the converse of each other. Converse simply means to switch the direction of the arrow. (The converse of $P\Rightarrow Q$ is $Q\Rightarrow P$.)

Necessary and Sufficient

To say that "P is necessary and sufficient for Q" means "P is true exactly when Q is true" or "P implies Q and Q implies P". This means that P and Q always have the same truth value—that is, they are both true or both false simultaneously. In mathematical symbols this is expressed as $P\iff Q$. This is referred to as a biconditional. When $P\iff Q$ is a true statement, we say that P and Q are logically equivalent.

Modifiers

We have explored truth statements and logical connectors used to create new statements. We will now look at two more variations of logical statements.

Negation

Negation refers to toggling a truth statement's truth value. The result is not always negative, or false, it is only the opposite of the original. Thus, the negation of "false" is "true." This is denoted by a tilde (~) or the negation symbol $\mathrm{\neg }$.

It will be shown below in a truth table that the negation of the statement $P\vee Q$, which is $\mathrm{\neg }(P\vee Q)$, is equivalent to $\mathrm{\neg }P\wedge \mathrm{\neg }Q$. Thus, to use loose terminology, "not or" is "and" (similarly, "not and" is "or").

Contrapositive

The contrapositive is related to negation. However, it is only defined for a conditional statement. It basically means negate both P and Q and switch the direction of the conditional. That is, the contrapositive of $P\Rightarrow Q$ is $\mathrm{\neg }P\Leftarrow \mathrm{\neg }Q$; or, equivalently, $\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P$. It will be shown below that the contrapositive of a statement is equivalent to the statement itself.

Truth Tables

A truth table is helpful in visualizing all of these logical relations. The table is filled in by considering all possible combinations of true and false for P and Q and then filling in the results for the various connectors mentioned above.

The Or and And Table

OR and AND

P	Q	$P\vee Q$	$P\wedge Q$
T	T	T	T
T	F	T	F
F	T	T	F
F	F	F	F

If, Only if, and If and only if Table

If, only if, and iff

P	Q	$P\Rightarrow Q$	$P\Leftarrow Q$	$P\iff Q$
T	T	T	T	T
T	F	F	T	F
F	T	T	F	F
F	F	T	T	T

Note that the $P\iff Q$ column can be obtained from $(P\Rightarrow Q)\wedge (P\Leftarrow Q)$. Truth tables are very useful in helping beginners understand logical relationships.

Negation and Contrapositive Table

Negation and Contrapositive

P	Q	$\mathrm{\neg }P$	$\mathrm{\neg }Q$	$P\Rightarrow Q$	$\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P$
T	T	F	F	T	T
T	F	F	T	F	F
F	T	T	F	T	T
F	F	T	T	T	T

Exercises

In the following exercises, P, Q, R, and S will represent truth statements.

A. Construct the truth tables for the following statements, and give their converse and contrapositive:

1. 1. $\mathrm{\neg }P\Rightarrow Q$
   2. $P\Rightarrow \mathrm{\neg }Q$
   3. $(P\vee Q)\Rightarrow R$
   4. $(P\wedge Q)\Rightarrow (R\vee S)$
   5. $(P\Rightarrow Q)\Leftarrow (R\Rightarrow S)$

B. Negate the following statements:

1. 1. $P\wedge Q$
   2. $(P\vee Q)\wedge (R\wedge S)$
   3. $(P\wedge \mathrm{\neg }Q)\vee (\mathrm{\neg }R\vee S)$