Logical operators

Table of Contents

Logical operators are tools for building more complicated statements out of simpler ones. In this chapter, we treat them as a kind of “grammar” for mathematical statements: they tell us how to connect, modify, and compare statements so that their truth values are clear.

We will assume that you already know what a mathematical statement is and what it means for a statement to be true or false. Here, we focus on how logical operators work with those truth values.

Basic idea: truth values and connectives

In this chapter, we use:

A, B, P, Q, R, … to stand for whole statements (like “$2$ is even”, “$5$ is greater than $3$”).
“True” and “False” as the only possible truth values for these statements.

A logical operator takes one or more statements and produces a new statement whose truth depends in a precise way on the truth of the originals.

We will look at the most common operators:

“not” (negation)
“and” (conjunction)
“or” (disjunction)
“if … then …” (implication)
“if and only if” (biconditional)

Later, you will see these operators used constantly in definitions, theorems, and proofs.

Throughout, it is useful to imagine each letter like a switch that can be either on (true) or off (false), and the operator describes how the output switch depends on the input switches.

Negation: “not”

Negation turns a statement into its opposite in terms of truth.

Symbol: $\lnot P$ (read: “not P”).
Meaning: $\lnot P$ is true exactly when $P$ is false.

Examples of negation in words:

$P$: “$3$ is an even number.”
$\lnot P$: “$ is not an even number.”
$Q$: “All cats are black.”
$\lnot Q$: “Not all cats are black.” (equivalently: “At least one cat is not black.”)

The important point: the negation of $P$ is not a commentary on whether we personally know $P$ is true; it is a formal statement whose truth value is the opposite of $P$’s.

Negation affects all parts of a statement, not just one word. When you negate a compound statement such as “$P$ and $Q$”, you do not simply say “not $P$ and $Q$”. Systematic rules for this are covered later as logical equivalences but are worth mentioning here by name:

De Morgan’s Laws (stated without justification here):

$\lnot(P \land Q)$ means “not ($P$ and $Q$)” and is equivalent to “$\lnot P$ or $\lnot Q$”.
$\lnot(P \lor Q)$ means “not ($P$ or $Q$)” and is equivalent to “$\lnot P$ and $\lnot Q$”.

We will use these laws when transforming logical expressions.

Conjunction: “and”

Conjunction connects two statements and requires both to be true.

Symbol: $P \land Q$ (read: “P and Q”).
Meaning: “$P$ is true and $Q$ is true.”

Truth table for “and”:

$$
\begin{array}{c|c|c}
P & Q & P \land Q \\
\hline
\text{T} & \text{T} & \text{T} \\
\text{T} & \text{F} & \text{F} \\
\text{F} & \text{T} & \text{F} \\
\text{F} & \text{F} & \text{F}
\end{array}
$$

So $P \land Q$ is true only in one case: when both $P$ and $Q$ are true.

Examples:

$P$: “$2+2=4$” (true)
$Q$: “$ is odd” (true)
Then $P \land Q$: “+2=4$ and $ is odd” is true.
$R$: “$5$ is even” (false)
$S$: “$ is greater than $” (true)
Then $R \land S$: “$ is even and $ is greater than $” is false.

Important points:

In everyday language, “and” sometimes suggests order or time (“I ate and went to sleep”), but in logic, $P \land Q$ does not contain any ordering information. It is just the claim that both are true.
$P \land Q$ means something stronger than each of $P$ or $Q$ alone.

Disjunction: “or”

Disjunction connects two statements and accepts either of them being true.

Symbol: $P \lor Q$ (read: “P or Q”).
Meaning (in standard mathematical logic):
$P \lor Q$ is true if at least one of $P$ or $Q$ is true, possibly both.

This is called the inclusive or. It allows the possibility that both are true.

Truth table:

$$
\begin{array}{c|c|c}
P & Q & P \lor Q \\
\hline
\text{T} & \text{T} & \text{T} \\
\text{T} & \text{F} & \text{T} \\
\text{F} & \text{T} & \text{T} \\
\text{F} & \text{F} & \text{F}
\end{array}
$$

Examples:

$P$: “$4$ is even” (true)
$Q$: “$ is prime” (false)
$P \lor Q$: “$ is even or $ is prime” is true, because $P$ is true.
$R$: “$2$ is less than $5$” (true)
$S$: “$ is a multiple of $” (true)
$R \lor S$ is true, and stays true even though both $R$ and $S$ are true.

In everyday speech, “or” is often exclusive, meaning “one or the other, but not both” (for example, a menu might say “coffee or tea”, suggesting you pick exactly one). When mathematics needs that meaning, it is usually specified explicitly, or written as
“$P$ or $Q$ but not both”, which can be expressed in terms of the basic operators:

$$
\text{“exactly one of } P, Q \text{ is true”} \quad \Longleftrightarrow \quad (P \lor Q) \land \lnot(P \land Q).
$$

However, unless otherwise stated, “or” in mathematics means inclusive or.

Implication: “if … then …”

Implication expresses a conditional relationship between two statements.

Symbol: $P \Rightarrow Q$ (read: “if P, then Q”, or “P implies Q”).
$P$ is called the hypothesis (or antecedent).
$Q$ is called the conclusion (or consequent).

Meaning in words:

$P \Rightarrow Q$ is false only when $P$ is true and $Q$ is false.
In all other cases (when $P$ is false, or both are true), $P \Rightarrow Q$ is considered true.

Truth table:

$$
\begin{array}{c|c|c}
P & Q & P \Rightarrow Q \\
\hline
\text{T} & \text{T} & \text{T} \\
\text{T} & \text{F} & \text{F} \\
\text{F} & \text{T} & \text{T} \\
\text{F} & \text{F} & \text{T}
\end{array}
$$

This table often feels strange at first, especially the last two rows. Here is how to interpret them:

When $P$ is true and $Q$ is false, the claim “if $P$, then $Q$” has failed: $P$ happened, but $Q$ did not. So the implication is false.
When $P$ is false, the implication makes no promise about what happens, so in standard logic it is automatically counted as true. This is often described by saying that the implication is vacuously true when the hypothesis does not occur.

Examples:

$P$: “$x$ is an even integer.”
$Q$: “$x$ is divisible by $.”
The statement $P \Rightarrow Q$ says: “If $x$ is an even integer, then $x$ is divisible by $.” For integers $x$, this is true.
$R$: “$4$ is odd.” (false)
$S$: “$ is greater than $.” (true)
The implication $R \Rightarrow S$ reads: “If $ is odd, then $ is greater than $.” Because $R$ is false, the implication is counted as true (vacuously true) according to the standard truth table, even though the sentence sounds odd in everyday language.

Implication can be re-expressed using other operators:

$$
P \Rightarrow Q \quad \text{is logically equivalent to} \quad \lnot P \lor Q.
$$

This means “if $P$, then $Q$” is logically the same as “either $P$ is false or $Q$ is true”. This equivalence is very useful for simplifying logical expressions and for proofs.

Special forms related to implication

Given a statement $P \Rightarrow Q$, there are some related statements you will often see:

Converse: $Q \Rightarrow P$
(“If $Q$, then $P$.”)
Inverse: $\lnot P \Rightarrow \lnot Q$
(“If not $P$, then not $Q$.”)
Contrapositive: $\lnot Q \Rightarrow \lnot P$
(“If not $Q$, then not $P$.”)

These three are different in general. The most important fact is:

The contrapositive $\lnot Q \Rightarrow \lnot P$ is logically equivalent to $P \Rightarrow Q$.
The converse and inverse are not generally equivalent to the original implication, though they are equivalent to each other.

Example:

Original: “If a number is a square of an integer, then it is non-negative.”
$P$: “$n$ is a square of an integer.”
$Q$: “$n$ is non-negative.”

Contrapositive: “If $n$ is negative, then $n$ is not a square of an integer.”
This is true and says the same thing in a different form.
Converse: “If $n$ is non-negative, then $n$ is a square of an integer.”
This is false in general (for example, $ is non-negative but not a square).

Understanding these relationships is essential for reading and constructing mathematical arguments, especially proofs that use contraposition.

Biconditional: “if and only if”

The biconditional connects two statements in a way that asserts they are equivalent in truth value.

Symbol: $P \Leftrightarrow Q$.
Read as: “P if and only if Q” (often abbreviated “iff”).

Meaning:

$P \Leftrightarrow Q$ is true when $P$ and $Q$ are either both true or both false.
It is false when one is true and the other is false.

Truth table:

$$
\begin{array}{c|c|c}
P & Q & P \Leftrightarrow Q \\
\hline
\text{T} & \text{T} & \text{T} \\
\text{T} & \text{F} & \text{F} \\
\text{F} & \text{T} & \text{F} \\
\text{F} & \text{F} & \text{T}
\end{array}
$$

You can also see the biconditional as a combination of two implications:

$$
P \Leftrightarrow Q \quad \text{is logically equivalent to} \quad (P \Rightarrow Q) \land (Q \Rightarrow P).
$$

So “$P$ if and only if $Q$” means:

“If $P$, then $Q$” and
“If $Q$, then $P$”.

Examples:

“An integer $n$ is even if and only if $n$ is divisible by $2$.”
Here, $P$: “$n$ is even.”
$Q$: “$n$ is divisible by $.”
This asserts both directions: even implies divisible by 2, and divisible by 2 implies even.
“A polygon is a triangle if and only if it has exactly three sides.”
This states equivalence between a geometric description and a defining property.

Biconditionals are frequently used in definitions and in the precise formulation of “if and only if” theorems.

Combining operators and using parentheses

Logical operators can be combined to form more complex expressions, such as:

$(P \land Q) \Rightarrow R$
$\lnot P \lor (Q \land \lnot R)$
$(P \Rightarrow Q) \Leftrightarrow (\lnot Q \Rightarrow \lnot P)$

Parentheses are used to indicate grouping, just as in arithmetic.

There is also a commonly used precedence (or order of evaluation) when parentheses are omitted; while different texts may vary, a typical order from highest to lowest is:

$\lnot$ (negation)
$\land$ (and)
$\lor$ (or)
$\Rightarrow$ (implication)
$\Leftrightarrow$ (biconditional)

For example, the expression
$$
\lnot P \land Q \Rightarrow R
$$
is usually read as
$$
((\lnot P) \land Q) \Rightarrow R
$$
and not as
$$
\lnot(P \land (Q \Rightarrow R)).
$$

To avoid ambiguity, especially as a beginner, it is wise to use parentheses generously.

Truth tables for compound statements

For any compound statement built using logical operators, you can systematically determine its truth value in all possible cases by constructing a truth table.

The general method is:

List all possible combinations of truth values for the basic statements $P, Q, R, \dots$.
Compute the value of each sub-expression step by step.
End with the truth values of the entire expression.

Example: Consider $(P \land Q) \Rightarrow R$.

We start with columns for $P, Q, R$, then compute $P \land Q$, and finally the implication:

$$
\begin{array}{c|c|c|c|c}
P & Q & R & P \land Q & (P \land Q) \Rightarrow R \\
\hline
\text{T} & \text{T} & \text{T} & \text{T} & \text{T} \\
\text{T} & \text{T} & \text{F} & \text{T} & \text{F} \\
\text{T} & \text{F} & \text{T} & \text{F} & \text{T} \\
\text{T} & \text{F} & \text{F} & \text{F} & \text{T} \\
\text{F} & \text{T} & \text{T} & \text{F} & \text{T} \\
\text{F} & \text{T} & \text{F} & \text{F} & \text{T} \\
\text{F} & \text{F} & \text{T} & \text{F} & \text{T} \\
\text{F} & \text{F} & \text{F} & \text{F} & \text{T}
\end{array}
$$

This table shows, for example, that $(P \land Q) \Rightarrow R$ is false only in the second row, when $P$ and $Q$ are both true but $R$ is false. In all other cases it is true.

Truth tables are a basic tool for:

checking whether two logical expressions are equivalent,
seeing whether a complicated statement is always true (a tautology), always false (a contradiction), or sometimes true and sometimes false (a contingency).

The deeper study of such relationships belongs to later chapters, but the ability to read and create truth tables starts here.