Skip to main content

Exploration in Modern Mathematics

Mike Janssen

Section 3.1 Logical Connectives and Rules of Inference

Motivating Questions.

In this section, we will explore the following questions.
  1. What is a proposition?
  2. What are logical connectives? How can they be used to build new propositions?
  3. What does it mean for two propositions to be logically equivalent?
In the late 19th and early 20th centuries, mathematicians began mathematize and formalize logic itself. Today we begin to explore these foundational issues. We’ll start with some definitions.

Definition 3.1.1.

A proposition is a declarative sentence which is either true or false, but not both. An elementary proposition is a sentence with a subject and a verb, but no connectives (such as and, or, not, if-then, or if-and-only-if).

Activity 3.1.2.

Determine which of the following are propositions (elementary or otherwise). If a given sentence is a proposition, determine its truth value. If it isn’t, explain why not.
  1. Barack Obama was the 44th president of the United States.
  2. The square root of a whole number is always a whole number.
  3. The Green Bay Packers are the worst football team.
  4. Why is this class so much fun?
  5. This sentence is false.
  6. A group of crows is called a murder.
  7. Everyone likes cats.
Now that we have a sense for what a proposition is, we’ll take old propositions and make new ones using logical connectives. In order to describe how the connectives work, mathematicians define the truth values of the new propositions formally —that is, without regard to the content of the propositions themselves —in terms of the possible combinations of truth values from the constituent propositions. This gives us an abstract way of considering the truth values of propositions.

Definition 3.1.3.

Suppose \(P\) and \(Q\) are statements (e.g., like those in Activity 3.1.2). The negation of \(P\text{,}\) denoted \(\neg P\) and read "not \(P\)", has the opposite truth value of \(P\) and is defined by Table 3.1.4.
Table 3.1.4. The negation of \(P\text{.}\)
\(​P\) \(​\neg P\)
T F
F T

Definition 3.1.5.

The conjunction of \(P\) and \(Q\text{,}\) denoted \(P \land Q\) and read “\(P\) and \(Q\)”, is true when both \(P\) and \(Q\) are true, and false otherwise. See Table 3.1.6.
Table 3.1.6. The conjunction of \(P\) and \(Q\text{.}\)
\(​P\) \(​Q\) \(P \land Q​\)
T T T
T F F
F T F
F F F

Definition 3.1.7.

The disjunction of \(P\) and \(Q\text{,}\) denoted \(P \lor Q\) and read “\(P\) or \(Q\)”, is true when \(P\) is true, \(Q\) is true, or both are true, and false otherwise. See Table 3.1.8.
Table 3.1.8. The disjunction of \(P\) and \(Q\text{.}\)
\(​P\) \(​Q\) \(P \lor Q​\)
T T T
T F T
F T T
F F F

Activity 3.1.9.

Meaningfully negate the following propositions (without just saying "It is not the case that...").
  1. \(e\) is a negative real number.
  2. Iowa is the tenth largest state in the U.S.A. (by population).
  3. 17 is a prime number.

Exploration 3.1.10.

Determine the truth values of the following propositions.
  1. Our math class meets on Mondays and the capital of Iowa is Des Moines.
  2. Our math class meets on Mondays and the capital of Minnesota is Minneapolis.
  3. Our math class meets on Mondays or the capital of Minnesota is Minneapolis.
The last connective we’ll consider (for now) is implication.

Definition 3.1.11.

Let \(P\) and \(Q\) be statements. The implication, "\(P\) implies \(Q\)" (or "if \(P\text{,}\) then \(Q\)") is denoted \(P\Rightarrow Q\text{,}\) and is false only when \(P\) is true but \(Q\) is false. See Table 3.1.12.
Table 3.1.12. The implication \(P\Rightarrow Q\text{.}\)
\(​P\) \(​Q\) \(P\Rightarrow Q​\)
T T T
T F F
F T T
F F T

Exploration 3.1.13.

Determine the truth values of the following statements. Identify which row of Table 3.1.12 you are in.
  1. If \(-5\) is a negative real number, then triangles have three sides.
  2. If our math class meets today, then it is Wednesday.
  3. If \(9 > 5\text{,}\) then dogs do not have wings.
  4. If \(2=4\text{,}\) then dogs do have wings.
The formalization of mathematical logic ramps up a bit when we consider conditional statements. It is important to remember that we define the truth value of the proposition \(P \Rightarrow Q\) purely formally based on the structure of the conditional statement and the truth values of the constituents \(P\) and \(Q\text{.}\) There need not be a causal relationship between \(P\) and \(Q\text{!}\)
The last two rows of Table 3.1.12 are also worth a moment of our time. They state that if the statement \(P\)
 1 
Often called the antecedent.
is false, then the implication \(P\Rightarrow Q\) is true. Note that this is different than saying that \(Q\)
 2 
Often called the consequent.
is true. When the implication \(P\Rightarrow Q\) is true because \(P\) is false, we usually say that \(P\Rightarrow Q\) is vacuously true.

Activity 3.1.14.

Suppose your professor promises that, if everyone has solved a Rubik’s cube by Friday, then they will bring snacks to class
 3 
This is purely hypothetical.
. Unfortunately, a few students do not solve a Rubik’s cube by Friday, so the class does not get snacks.
Decide the truth value of the following implication:
If everyone in the class solves a Rubik’s cube by Friday, the professor will bring snacks to class.
Explain your thinking.
An important tool in our logical toolkit is one you likely employed in the theorems you deduced from Axiom 2.2.2.

Exploration 3.1.15.

Let \(P\) and \(Q\) be statements. The contrapositive of the implication \(P\Rightarrow Q\) is the implication \((\neg Q) \Rightarrow (\neg P)\text{.}\) Complete Table 3.1.16. Is the contrapositive equivalent to anything we’ve looked at thus far?
Table 3.1.16. The contrapositive of \(P\Rightarrow Q\text{.}\)
\(P\) \(Q\) \(\neg P​\) \(\neg Q​\) \((\neg Q) \Rightarrow (\neg P)\)
T T
T F
F T
F F

Activity 3.1.17.

Write the contrapositives of the following statements. Be ready to explain why the contrapositives are equivalent to the original implications.
  1. If a kitten loves fish, then it is teachable.
  2. If a kitten does not have a tail, then it will play with a gorilla.
  3. If a kitten has green eyes, then it is not teachable.
  4. If today is Wednesday, then we have math class.
We have now explored several ways of combining existing propositions into larger propositions using logical connectives. When we use logic to write proofs, we also employ tools known as rules of inference. They clearly describe what steps we are allowed to take. There are many such rules; we will highlight two.
The way in which reasoning with implications is often done uses a rule of inference known as modus ponens which runs roughly:
  • If \(P\text{,}\) then \(Q\text{.}\)
  • \(P\text{,}\)
  • Therefore, \(Q\)
A closely related rule of inference is known as modus tollens, and runs thusly:
  • If \(P\text{,}\) then \(Q\text{.}\)
  • Not \(Q\text{,}\)
  • Therefore, not \(P\text{.}\)
In this section, we explored the fundamentals of logical reasoning employed in mathematics. Propositions are constructed out of elementary propositions and logical connectives. The truth values of these propositions can be determined purely formally in a consistent fashion. We then use laws of inference like modus ponens or modus tollens to reason from true proposition to true proposition.

Exercises Exercises

1.

Given an implication \(P\Rightarrow Q\text{,}\) the converse is the statement \(Q\Rightarrow P\text{.}\) Find the truth table for \(Q\Rightarrow P\text{;}\) is it the same as \(P\Rightarrow Q\text{?}\) Think of an example of a specific statement \(P\Rightarrow Q\) that illustrates this.

2.

A statement is called a tautology if is it always true. Similarly, a statement is known as a contradiction if it is never true. Determine which of the following, if any, are tautologies, and which are contradictions.
  1. \(\displaystyle P\land (\neg P)\)
  2. \(\displaystyle P\lor (\neg P)\)
  3. \(\displaystyle P\Rightarrow (P\Rightarrow (P\Rightarrow (P\Rightarrow Q)))\)
  4. \(\displaystyle P\Rightarrow (\neg P\Rightarrow (P\Rightarrow (\neg P\Rightarrow Q)))\)
PrevTopNext