Propositions and Conditional Statements

The Atoms of Logic: Propositions

A mathematical proof is a structured argument that demonstrates the truth of a conclusion based on a set of assumptions. But what are these assumptions and conclusions made of? They are made of statements, or what logicians call propositions.

A proposition is a sentence that makes a claim that can be definitively assigned a truth value: it is either true or false, but not both. This requirement for clarity and lack of ambiguity is the bedrock of mathematical reasoning.

• "2 + 2 = 4" is a true proposition.
• "2 + 2 = 5" is a false proposition.
• "The sky is blue" is a proposition, as it's a declarative sentence with a truth value.
• "What time is it?" is not a proposition because it's a question and makes no claim.
• "Solve this equation" is not a proposition because it's a command.
• "This statement is false" is not a proposition because it's a paradox that cannot be assigned a truth value without contradiction.

To formalize this, please read the following brief text, which defines what qualifies as a mathematical statement.

To reinforce this and see more examples, let's watch a short video that explains the concept in the context of propositional logic.

As you've seen, we can distill complex ideas into simple propositions represented by letters. For example, in the Pythagorean theorem, we could define:

• P: "A triangle is a right-angled triangle."
• Q: "The square of the hypotenuse is equal to the sum of the squares of the other two sides."

The theorem itself connects these propositions. The nature of that connection is what we will explore next.

The Engine of Deduction: The Conditional Statement

The most common way to connect propositions in mathematics is through a conditional statement, also known as an implication. This is the familiar "If P, then Q" structure. In our Pythagorean example, the theorem states, "If P, then Q."

The proposition P is called the hypothesis (or antecedent, or premise), and the proposition Q is the conclusion (or consequent). The conditional statement asserts that whenever the hypothesis P is true, the conclusion Q must also be true.

We use the notation $P\to Q$ to represent "If P, then Q".

Now, a crucial question arises: under what conditions is the entire statement $P\to Q$ considered true? The answer is not entirely intuitive and is a cornerstone of formal logic. Let's explore this with a video.

As the video explains, the conditional statement $P\to Q$ is only false in one specific scenario: when the hypothesis P is true, but the conclusion Q is false. In all other cases, the conditional is true. This can be surprising, especially the cases where P is false.

Let's solidify this with a reading that uses a practical example.

The key takeaway is that in formal logic, $P\to Q$ doesn't imply a cause-and-effect relationship. It is simply a promise, or a contract. The statement "If it rains, then the street will be wet" is a promise.

• It rains (P is true) and the street is wet (Q is true). The promise was kept. $P\to Q$ is true.
• It rains (P is true) and the street is dry (Q is false). The promise was broken. $P\to Q$ is false.
• It does not rain (P is false) and the street is wet (Q is true). The promise wasn't broken; maybe a sprinkler came on. The statement made no claim about this scenario. $P\to Q$ is true.
• It does not rain (P is false) and the street is dry (Q is false). The promise wasn't broken. $P\to Q$ is true.

A Deeper Connection: The Conditional and Other Operators

You mentioned you have an intuitive grasp of "NOT", "AND", and "OR". There is a beautiful and powerful equivalence between the conditional statement and a statement using "NOT" and "OR". This equivalence is fundamental to logic and computer science.

The statement $P\to Q$ is logically equivalent to $\neg P\vee Q$ ("Not P or Q").

Let's verify this. Consider the promise "If you score at least 85, you will get an A." This is equivalent to saying, "Either you did not score at least 85, or you got an A." The only way for this "either/or" statement to be false is if both parts are false: you did score at least 85, and you did not get an A. This is the exact same condition that makes $P\to Q$ false.

The following segment of the video you watched earlier explains this equivalence and demonstrates how to translate between English sentences and formal logical structures.

Logical Equivalence and the Contrapositive

Two statements that have the exact same truth table are said to be logically equivalent. They are different ways of saying the same thing. We already saw that $P\to Q$ is equivalent to $\neg P\vee Q$.

There is another important equivalence. Consider the following statements related to an original conditional $P\to Q$:

• Converse: $Q\to P$ (If Q, then P)
• Inverse: $\neg P\to \neg Q$ (If not P, then not Q)
• Contrapositive: $\neg Q\to \neg P$ (If not Q, then not P)

Let's examine the truth tables for these related statements.

If you compare the columns, you will see two things:

1. The column for the original conditional ($p\to q$) is identical to the column for the contrapositive ($\neg q\to \neg p$). This means they are logically equivalent. Proving one is the same as proving the other. This is a very common and powerful strategy in proofs.
2. The column for the converse ($q\to p$) is identical to the column for the inverse ($\neg p\to \neg q$), but they are different from the original conditional. Mistaking a conditional for its converse is a common logical fallacy. For example, "If it is a square, then it is a rectangle" is true. The converse, "If it is a rectangle, then it is a square," is false.

Conclusion

In this lesson, we have established the fundamental building blocks of mathematical arguments.

• Propositions are unambiguous declarative sentences that are either true or false. They are the "atoms" of logic.
• The conditional statement ($P\to Q$) connects a hypothesis (P) to a conclusion (Q). It is the engine of deduction.
• A conditional statement is only false when the hypothesis is true and the conclusion is false. It is considered true in all other cases, including when the hypothesis is false (a concept known as "vacuous truth").
• A conditional $P\to Q$ is logically equivalent to both $\neg P\vee Q$ ("not P or Q") and its contrapositive $\neg Q\to \neg P$ ("if not Q, then not P").

You now have a solid grasp of the syntax and meaning of the most important structure in mathematical theorems.

In the next lesson, we will put this structure to use. We will introduce our first formal rule of inference, Modus Ponens, which allows us to take a true conditional statement and a true hypothesis to formally deduce that the conclusion must also be true. This will be our first step in building a chain of valid deductive steps—the very essence of a proof.