Mathematical Proof/Introduction/Logical Reasoning

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 and Statements

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 (sometimes also referred or abbreviated as 1 or T) or false (sometimes referred also as 0 or F). 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.

Logical Connectors

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, given that either or both statements are true. Another example, the statement "7 > 9 or 2 < 3" is true, because one of the connected statements is true. The only time the statement "P or Q" is false is when both P and Q are false; an example of a statement where both P and Q are false is the following "All people are American or all Americans are tall". Clearly, the statement "All people are American" is false, and is false also the statement "all Americans are tall".

"Or" is sometimes denoted with the symbol $\lor$ . So $P\lor 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 "The author of this article likes cheesecake and broccoli." is true since the statements "The author of this article likes cheesecake." and "The author of this article likes 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.

Another example might be the statement "2<6 and 3<6", which is true, since both statements "2<6" and "3<6" are true. The statement "2<6 and 3>6" is not true since "3>6" is false.

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

Implications and Conditional Statements

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

Necessary

To say that "Q is necessary for P" means that P cannot exist without Q. Another way of saying this is "P only if Q" or "if P then Q". The notation for this is $P\Rightarrow Q$ (P implies Q).

The statement "It is necessary for the day to be a sunday if the day is Easter" is true because if it is Easter, then it must be also Sunday. The statement "P only if Q" is false only when P is true and Q is false, because Q is a necessary condition (it must be true) for P to be true.

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, in fact 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\Leftrightarrow Q$ . This is referred to as a biconditional. When $P\Leftrightarrow 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 $\neg$ .

It will be shown below in a truth table that the negation of the statement $P\lor Q$ , which is $\neg (P\lor Q)$ , is equivalent to $\neg P\land \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 $\neg P\Leftarrow \neg Q$ ; or, equivalently, $\neg Q\Rightarrow \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\lor Q$ $P\land 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, if and only if
P Q $P\Rightarrow Q$ $P\Leftarrow Q$ $P\Leftrightarrow 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\Leftrightarrow Q$ column can be obtained from $(P\Rightarrow Q)\land (P\Leftarrow Q)$ . Truth tables are very useful in helping beginners understand logical relationships.

Negation and Contrapositive Table

Negation and Contrapositive
P Q $\neg P$ $\neg Q$ $P\Rightarrow Q$ $\neg Q\Rightarrow \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. $\neg P\Rightarrow Q$ 2. $P\Rightarrow \neg Q$ 3. $(P\lor Q)\Rightarrow R$ 4. $(P\land Q)\Rightarrow (R\lor S)$ 5. $(P\Rightarrow Q)\Leftarrow (R\Rightarrow S)$ B. Negate the following statements:

1. $P\land Q$ 2. $(P\lor Q)\land (R\land S)$ 3. $(P\land \neg Q)\lor (\neg R\lor S)$ 