Logic

Propositions, truth values, connectives, implication, and truth tables.

Logic is the grammar of mathematical reasoning. It helps us say exactly what is being assumed, what must be proved, and when a statement is true or false.

Learning objectives

After this lesson you should be able to:

• identify propositions;
• use not, and, or, implication, and biconditional;
• build and read truth tables;
• explain when p -> q is false;
• distinguish converse and contrapositive;
• recognize tautologies and contradictions.

Propositions

A proposition is a statement that is either true or false.

Examples:

• 7 is prime. This is a proposition and it is true.
• 10 < 4. This is a proposition and it is false.
• Close the door. This is not a proposition because it is a command.
• This number is large. This is too vague unless “large” is defined.

Logical connectives

Symbol	Name	Meaning
not p	negation	the opposite truth value of p
p and q	conjunction	true only when both are true
p or q	disjunction	true when at least one is true
p -> q	implication	if p, then q
p <-> q	biconditional	p and q have the same truth value

TipInclusive or

In mathematics, or usually means inclusive or. The statement p or q is true when p is true, when q is true, or when both are true.

Implication

The implication p -> q is false only in one case: p is true and q is false.

Think of it as a promise:

If p happens, then q must happen.

The promise is broken only when p happens but q does not.

Converse and contrapositive

For the statement p -> q:

• converse: q -> p;
• inverse: not p -> not q;
• contrapositive: not q -> not p.

The original implication and the contrapositive are logically equivalent. The converse is not always equivalent.

Worked example 1: truth table for implication

p	q	p -> q
false	false	true
false	true	true
true	false	false
true	true	true

The only false row is the row where the premise p is true and the conclusion q is false.

Worked example 2: contrapositive

Statement:

If a number is divisible by 4, then it is even.

Contrapositive:

If a number is not even, then it is not divisible by 4.

These two statements are equivalent. The converse would be:

If a number is even, then it is divisible by 4.

That converse is false because 6 is even but not divisible by 4.

Tautologies and contradictions

A tautology is always true, such as p or not p. A contradiction is always false, such as p and not p.

Common pitfalls

• Treating mathematical or as exclusive.
• Thinking p -> q is false whenever q is false.
• Confusing the converse with the contrapositive.
• Calling vague sentences propositions.
• Forgetting one or more rows in a truth table.

Practice

1. Is x + 2 = 5 a proposition before x is specified?
2. When is p and q true?
3. Write the converse of p -> q.
4. Write the contrapositive of p -> q.
5. Is p or not p a tautology?

TipSolutions

1. Not by itself. Its truth depends on the value of x.
2. Only when both p and q are true.
3. q -> p.
4. not q -> not p.
5. Yes. It is always true.

Subtopic guided practice and checkpoints

Logic problems are safest when you slow down and name the statement form before deciding whether it is true or false.

Lab 1: decide whether a sentence is a proposition

Guess first. Is “x is large” a proposition?

Guided exercise.

1. A proposition must have a definite truth value.
2. “x is large” depends on what x is and what “large” means.
3. Without definitions, it is not a proposition.
4. “7 is prime” is a proposition because it is definitely true.

Checkpoint. Decide whether each sentence is a proposition: “12 is even,” “Close the window,” and “n + 1 is positive.” Explain any dependence on undefined variables.

Lab 2: build a truth table row by row

Guess first. When p is false and q is false, is p -> q true or false?

Guided exercise.

p -> q is false only when p is true and q is false.

So the implication column is:

p=false, q=false -> true
p=false, q=true  -> true
p=true,  q=false -> false
p=true,  q=true  -> true

The first row is true because the promise “if p, then q” was never tested: p did not happen.

Checkpoint. Make the truth table for p and not q. Which row or rows are true?

Lab 3: use the contrapositive correctly

Guess first. Is the contrapositive of “if p, then q” the same as the converse?

Guided exercise.

Original:       p -> q
Converse:       q -> p
Contrapositive: not q -> not p

The original and contrapositive always have the same truth value. The converse may be false even when the original is true.

Checkpoint. Write the converse and contrapositive of “If an integer is divisible by 6, then it is divisible by 3.” Which one is guaranteed equivalent to the original?

Lab 4: recognize tautologies and contradictions

Guess first. Can p and not p ever be true?

Guided exercise.

If p is true, then not p is false. If p is false, then not p is true. They are never both true, so p and not p is a contradiction.

Checkpoint. Decide whether p or not p is a tautology, contradiction, or neither. Justify your answer with a two-row truth table.

TipLab checkpoint answers

1. “12 is even” is a proposition and it is true. “Close the window” is not a proposition because it is a command. “n + 1 is positive” is not a definite proposition until n and its allowed values are specified.
2. p and not q is true only when p is true and q is false.
3. Converse: if an integer is divisible by 3, then it is divisible by 6. Contrapositive: if an integer is not divisible by 3, then it is not divisible by 6. The contrapositive is guaranteed equivalent to the original.
4. p or not p is a tautology: when p is true, the first part is true; when p is false, not p is true.

Logic checkpoint

Using this lesson with edumath and SymPy

from edumath.discrete_math import implies, is_tautology, truth_table_rows

truth_table_rows(("p", "q"), "Implies(p, q)")

[{'p': False, 'q': False, 'result': True},
 {'p': False, 'q': True, 'result': True},
 {'p': True, 'q': False, 'result': False},
 {'p': True, 'q': True, 'result': True}]

is_tautology(truth_table_rows(("p",), "p | ~p"))

True

SymPy can also manipulate Boolean expressions directly.

import sympy as sp

p, q = sp.symbols("p q")
sp.Equivalent(sp.Implies(p, q), sp.Implies(~q, ~p))

\(\displaystyle \left(p \Rightarrow q\right) \Leftrightarrow \left(\neg q \Rightarrow \neg p\right)\)