Propositions and logical connectives

All of mathematics rests on one gesture: proving. Not convincing, not illustrating, proving. And proving requires a language where every sentence is either true or false, with no grey area. That language is propositional logic. It is the very first tool to lay down before writing a single serious proof.

By the end of this chapter you will be able to answer three questions: what counts as a statement we are allowed to call true or false, how to combine such statements with “not”, “and”, “or”, “if… then”, and why implication behaves in a way that surprises everyone the first time.

The investigation: reasoning correctly

Picture a detective at a crime scene. They only have facts, each of which is either true or false: “the window was locked”, “the suspect was in town”, “the alarm went off”. From these facts they chain deductions: if the window was locked and the alarm did not go off, then the intruder had a key.

The whole of reasoning lives in those little linking words: not, and, or, if… then. Propositional logic is exactly that, but made precise enough for a machine to check it. The detective works on intuition. We are going to write the rules down in black and white.

What is a proposition

A proposition Proposition A mathematical statement that is unambiguously either true or false, with no third possibility. This principle, called bivalence, is the starting point of all propositional logic. is a statement we can unambiguously call true or false. That is all, but it is strict.

• “2 + 2 = 4” is a proposition (true).
• “7 is an even number” is a proposition (false).
• “What time is it?” is not a proposition: a question is neither true nor false.
• "$x > 3$" is not a proposition as long as $x$ is not fixed: its truth value depends on $x$. We will turn it into a genuine proposition in chapter 2 using quantifiers.

The principle stating that a proposition is either true or false, with no third possibility, is called bivalence. We traditionally write true as $T$ (or $1$) and false as $F$ (or $0$). We denote propositions by letters: $P$, $Q$, $R$.

Play with a truth table

Before any theory, manipulate. The table below is a truth table Truth table A table giving the truth value of a logical formula for each possible combination of its variables' values. For n variables it has 2ⁿ rows. : it gives the value of two formulas for every possible combination of $P$ and $Q$. Toggle the values of $P$ and $Q$ with the buttons: the matching row is highlighted. Your mission: find the single row where $P \land Q$ is $T$, then the single row where $P \lor Q$ is $F$.

You have just met two connectives: $\land$ (and) and $\lor$ (or). Let us formalize them, together with their little sibling $\lnot$ (not).

The first three connectives: not, and, or

A logical connective Logical connective A symbol that combines one or two propositions into a new one. The five basic connectives are negation (¬), conjunction (∧), disjunction (∨), implication (⇒) and equivalence (⇔). is a symbol that builds a new proposition from one or two propositions. We define each one by its truth table, which is its complete definition: nothing is hidden.

Negation: ¬

Negation flips the truth value. $\lnot P$ reads “not $P$” and is $T$ exactly when $P$ is $F$.

$P$	$\lnot P$
T	F
F	T

Conjunction: ∧

$P \land Q$ reads ”$P$ and $Q$”. It is $T$ only when both are true at the same time.

$P$	$Q$	$P \land Q$
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction: ∨

$P \lor Q$ reads ”$P$ or $Q$”. Beware the trap: it is the inclusive or. It is $T$ as soon as at least one of the two is true, including when both are.

$P$	$Q$	$P \lor Q$
T	T	T
T	F	T
F	T	T
F	F	F

Implication, the connective that traps you

Here is the most important connective in mathematics, and the most counterintuitive. Implication Implication The "if... then..." connective, written ⇒. The proposition P ⇒ Q is false in exactly one case: when P is true and Q is false. In particular, an implication with a false premise is always true. $P \Rightarrow Q$ reads “if $P$ then $Q$”. Just as the neuron reads three ways, implication does too, and you need all three:

if P then Q | P is sufficient for Q | Q is necessary for P

Its truth table holds a surprise: $P \Rightarrow Q$ is false in only one case, the one where $P$ is true but $Q$ false.

$P$	$Q$	$P \Rightarrow Q$
T	T	T
T	F	F
F	T	T
F	F	T

The last two rows are shocking: when $P$ is false, $P \Rightarrow Q$ is true no matter what. We say an implication with a false premise is vacuously true.

Implication hides a second surprise, even more useful: it can be rewritten without the symbol $\Rightarrow$. Compare $P \Rightarrow Q$ and $\lnot P \lor Q$ below. Click “Show all”: the two columns are identical.

This rewriting $P \Rightarrow Q \equiv \lnot P \lor Q$ is a tool we will use constantly to manipulate implications inside proofs.

Equivalence, tautologies and contradictions

When two propositions have the same truth value in every case, we say they are in logical equivalence Logical equivalence A relation between two propositions that share the same truth value in every possible case. The associated connective, written ⇔, reads "if and only if" and amounts to a double implication. . The connective $P \Leftrightarrow Q$ reads ”$P$ if and only if $Q$”. It is $T$ exactly when $P$ and $Q$ have the same value.

$P$	$Q$	$P \Leftrightarrow Q$
T	T	T
T	F	F
F	T	F
F	F	T

Two families of propositions deserve a name:

• A tautology Tautology A proposition that is true regardless of the truth values of its components. Example: P ∨ ¬P (law of excluded middle). Its opposite is a contradiction, always false. is true whatever the values of its variables. The flagship example is the law of excluded middle: $P \lor \lnot P$. Either $P$ is true, or $\lnot P$ is, never both, never neither.
• A contradiction is always false. The flagship example is $P \land \lnot P$: a proposition cannot be both true and false at once (law of non-contradiction).

De Morgan’s laws

How do we negate an “and”? How do we negate an “or”? The answer is De Morgan’s two laws, among the most used in all of mathematics:

¬(P ∧ Q) ≡ ¬P ∨ ¬Q ¬(P ∨ Q) ≡ ¬P ∧ ¬Q

In plain words: negating “both” amounts to saying “at least one of the two is false”; negating “at least one” amounts to saying “both are false”. Check the first law yourself below, column against column.

Here is the summary table of the five connectives. Keep it in sight: it is your map of the chapter.

Symbol	Name	Reading	True when…
$\lnot$	negation	not P	$P$ is false
$\land$	conjunction	P and Q	$P$ and $Q$ are both true
$\lor$	disjunction	P or Q	at least one of the two is true
$\Rightarrow$	implication	if P then Q	except when $P$ true and $Q$ false
$\Leftrightarrow$	equivalence	P if and only if Q	$P$ and $Q$ have the same value

Every formula is a tree

A logical formula is not a flat string of symbols: it is a nested structure, a tree. The connectives are the nodes, the variables are the leaves. Here is the tree of $(P \land Q) \Rightarrow R$:

This tree dictates the order of evaluation: compute the leaves first, then climb back up. It also dictates the precedence of the connectives, exactly as multiplication comes before addition. The convention, from highest to lowest precedence: $\lnot$, then $\land$, then $\lor$, then $\Rightarrow$, then $\Leftrightarrow$. So $\lnot P \lor Q$ reads $(\lnot P) \lor Q$, not $\lnot (P \lor Q)$. When in doubt, parentheses settle it.

A history: from Boole to circuits

The idea that reasoning could become computation is recent on the scale of mathematics.

Year	Event
1847	George Boole publishes an algebra where true and false are computed like numbers. Logic becomes mathematical.
1879	Gottlob Frege invents a notation for quantifiers and founds modern logic. We reap the rewards in chapter 2.
1937	Claude Shannon shows in his master’s thesis that switching circuits realize exactly Boolean algebra. Digital electronics is born.

In one sentence

Propositional logic is a small exact calculus: propositions, true or false, combine through five connectives, and the value of any formula can be read mechanically from its truth table.

Towards chapter 2

We carefully avoided "$x > 3$", saying it was not a proposition. That is awkward: mathematics is full of statements that depend on a variable. To make them true or false, we must say “for all $x$” or “there exists an $x$”. Those are the quantifiers $\forall$ and $\exists$, the subject of chapter 2.

Exercises

Take a sheet of paper and a pencil. The solutions are right below, look at them only after trying.

Exercise 1: recognizing an equivalence

Build the truth table of $(P \Rightarrow Q) \land (Q \Rightarrow P)$, then compare it with $P \Leftrightarrow Q$. What do you notice?

Exercise 2: negating an implication

Show, using a truth table, that $\lnot(P \Rightarrow Q)$ is equivalent to $P \land \lnot Q$. This identity is precious: it says what you must exhibit to refute an “if… then”.

Sources

• Boole, G. (1854). An Investigation of the Laws of Thought. Walton and Maberly. Archive.org
• Frege, G. (1879). Begriffsschrift. Louis Nebert.
• Shannon, C. E. (1938). “A Symbolic Analysis of Relay and Switching Circuits.” Transactions of the AIEE 57(12), 713-723. DOI 10.1109/T-AIEE.1938.5057767

Going further

• Cori, R. & Lascar, D. (2000). Mathematical Logic, volume 1. Oxford University Press.
• Velleman, D. J. (2019). How to Prove It. Cambridge University Press. Excellent for moving from logic to proofs.
• Halmos, P. & Givant, S. (1998). Logic as Algebra. Mathematical Association of America.