Logic and Proofs

The Language of Logic

In mathematics, we need to be precise. We can't rely on ambiguity or nuance. To achieve this precision, we use logic. The basic building block of logic is the proposition, a statement that is definitively either true or false, but not both. It's a simple, powerful idea.

"The sky is blue" is a proposition. It's a statement that's either true or false.

"What time is it?" is not a proposition. It's a question, not a statement with a truth value.

"This statement is false" is also not a proposition. It's a paradox; if it's true, it's false, and if it's false, it's true.

We often represent propositions with lowercase letters like $p$ and $q$ . For example, we could set:

$p$ : "It is raining." $q$ : "I will take an umbrella."

These are simple statements. The real power of logic comes from connecting them to form more complex ideas.

Connecting Ideas

We link propositions together using logical connectives. Think of them as the conjunctions and operators of our logical language. There are five basic connectives you'll need to know. We can explore how they work using truth tables, which show the truth value of a compound statement for every possible combination of truth values of its simple components.

Connective	Symbol	Name	Meaning
NOT	$¬$	Negation	The opposite truth value. "It is not raining."
AND	$∧$	Conjunction	True only if both propositions are true. "It is raining and I will take an umbrella."
OR	$∨$	Disjunction	True if at least one proposition is true. "It is raining or I will take an umbrella."
IF...THEN	$→$	Implication	False only when the first proposition is true and the second is false. "If it is raining, then I will take an umbrella."
IF AND ONLY IF	$↔$	Biconditional	True only if both propositions have the same truth value. "I will take an umbrella if and only if it is raining."

Here are the truth tables for these connectives. Let's use T for True and F for False.

p	q	¬p	p ∧ q	p ∨ q	p → q	p ↔ q
T	T	F	T	T	T	T
T	F	F	F	T	F	F
F	T	T	F	T	T	F
F	F	T	F	F	T	T

The implication ( $p → q$ ) can seem a bit strange at first. The only time it's false is when you have a true premise leading to a false conclusion. If the premise ( $p$ ) is false, the implication is considered true regardless of the conclusion. This is called vacuous truth. For example, the statement "If the moon is made of cheese, then I am a billionaire" is logically true, because the premise is false.

Building an Argument

Understanding propositions and connectives is the first step. The next is using them to build unshakable arguments. In mathematics, this is called a proof. A proof is a sequence of logical steps that demonstrates a statement is always true. There are several powerful techniques for constructing proofs.

Learn to write clear, logical proofs using given information, definitions, and theorems.

Let's start with the most straightforward method.

Direct Proof To prove a statement of the form $p → q$ , you assume $p$ is true and use a series of logical deductions to show that $q$ must also be true.

Let's prove the statement: "If $n$ is an even integer, then $n^2$ is an even integer."

First, we identify our propositions. $p$ : " $n$ is an even integer." $q$ : " $n^2$ is an even integer."

Now, we follow the steps for a direct proof:

Assume $p$ is true. Assume $n$ is an even integer.
Use definitions. By the definition of an even integer, we know that $n = 2k$ for some integer $k$ .
Perform algebraic manipulation. Now we look at $n^2$ :

n^2 = (2k)^2 = 4k^2

Show $q$ is true. We can rewrite the result as:

n^2 = 2(2k^2)

Since $k$ is an integer, $2k^2$ is also an integer. This means $n^2$ is 2 times some integer, which is the definition of an even number. We have successfully shown that if $p$ is true, $q$ must be true.

Proof by Contradiction To prove a proposition $p$ , you assume its negation, $¬p$ , is true. Then you show that this assumption leads to a logical contradiction (something that is always false, like $x ext{ and } ¬x$ ). If the assumption leads to a contradiction, the assumption must be false, and therefore the original proposition $p$ must be true.

This is a powerful technique for when a direct path is hard to find. Let's use it to prove: "There is no largest integer."

State the proposition. Let $p$ be "There is no largest integer."
Assume the negation is true. Assume $¬p$ is true, which means "There is a largest integer." Let's call this integer $N$ .
Work towards a contradiction. If $N$ is the largest integer, then every other integer must be less than or equal to $N$ . But consider the number $M = N + 1$ . Since $N$ is an integer, $N+1$ is also an integer. We also know that $N+1 > N$ . So, $M > N$ .
State the contradiction. We have found an integer $M$ that is larger than $N$ . This contradicts our assumption that $N$ is the largest integer. Our assumption must be false.
Conclude the original proposition is true. Since the assumption "There is a largest integer" leads to a contradiction, it must be false. Therefore, the original statement, "There is no largest integer," must be true.

The Domino Effect

Some statements involve all positive integers. For example, how would you prove that the sum of the first $n$ positive integers is always equal to $n(n+1)/2$ ? You could check it for $n=1$ , $n=2$ , and $n=3$ , but that doesn't prove it for all integers. For this, we use a special proof technique.

Mathematical Induction This is a technique used to prove a statement, $P(n)$ , is true for all positive integers $n$ . It's like knocking over an infinite line of dominoes. You need to do two things:

Knock over the first domino (the Base Case).

Show that if any one domino falls, it will knock over the next one (the Inductive Step).

Let's prove the statement $P(n)$ : The sum of the first $n$ positive integers is given by the formula:

1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}

1. Base Case: We prove the statement is true for the first integer, $n=1$ . The sum is just 1. Let's check the formula:

\frac{1(1+1)}{2} = \frac{1(2)}{2} = 1

The formula holds for $n=1$ . The first domino has fallen.

2. Inductive Step: We must show that if the statement is true for any arbitrary positive integer $k$ , then it must also be true for the next integer, $k+1$ . In other words, we must prove that $P(k) → P(k+1)$ .

First, we assume $P(k)$ is true. This is our inductive hypothesis.

1 + 2 + \dots + k = \frac{k(k+1)}{2}

Now, we need to prove that $P(k+1)$ is true. We want to show:

1 + 2 + \dots + k + (k+1) = \frac{(k+1)((k+1)+1)}{2}

Let's start with the left side of the equation. We can use our inductive hypothesis to substitute the sum up to $k$ .

\underbrace{1 + 2 + \dots + k}_{\text{This is } \frac{k(k+1)}{2}} + (k+1)

Now, we substitute and simplify:

\begin{aligned} \frac{k(k+1)}{2} + (k+1) & = \frac{k(k+1) + 2(k+1)}{2} \\ & = \frac{(k+1)(k+2)}{2} \\ & = \frac{(k+1)((k+1)+1)}{2} \end{aligned}

This is exactly the right side of the equation for $P(k+1)$ . We have shown that if the formula works for $k$ , it must work for $k+1$ . We've shown that each domino knocks over the next.

Since we've proven the base case and the inductive step, we can conclude by mathematical induction that the formula is true for all positive integers $n$ .

Quiz Questions 1/5

Which of the following is a proposition?

Quiz Questions 2/5

Consider the logical implication "If the moon is made of cheese, then pigs can fly." According to the rules of logic, is this statement true or false?

Logic and proofs are the bedrock of discrete mathematics. They provide the tools to build, understand, and verify the complex systems you'll encounter next.

Introduction to Discrete Mathematics