Logic and statements

A statement (or proposition) is a sentence that is either true or false, but not both. "$7$ is prime" and "$2 + 2 = 5$" are statements (true and false). "Is $x$ prime?" and "$x > 3$" are not: the first is a question, and the truth of the second depends on $x$. A sentence like "$x > 3$" whose truth depends on a variable is a predicate $P(x)$; it becomes a statement once $x$ is fixed or quantified.

For statements $P, Q$:

• $\neg P$ ("not $P$") is true exactly when $P$ is false.
• $P\wedge Q$ ("$P$ and $Q$") is true exactly when both are true.
• $P\vee Q$ ("$P$ or $Q$") is true when at least one is true. Mathematical "or" is inclusive: $P\vee Q$ is true when both are.

Truth tables list the value for each of the four combinations of $P, Q$.

$P\Rightarrow Q$ ("if $P$ then $Q$", "$P$ implies $Q$") is false only when $P$ is true and $Q$ is false; in the other three cases it is true. $P$ is the hypothesis and $Q$ the conclusion. Other readings: "$Q$ if $P$", "$P$ only if $Q$", "$P$ is sufficient for $Q$", "$Q$ is necessary for $P$". In particular an implication with a false hypothesis is (vacuously) true.

For the implication $P\Rightarrow Q$:

• its converse is $Q\Rightarrow P$;
• its contrapositive is $\neg Q\Rightarrow\neg P$;
• the biconditional $P\Leftrightarrow Q$ ("$P$ if and only if $Q$", "iff") means $(P\Rightarrow Q)\wedge(Q\Rightarrow P)$, and is true exactly when $P$ and $Q$ have the same truth value.

For all statements $P, Q$, the implication $P\Rightarrow Q$ and its contrapositive $\neg Q\Rightarrow\neg P$ have the same truth value. Consequence: to prove $P\Rightarrow Q$ it is enough to prove $\neg Q\Rightarrow\neg P$ (proof by contrapositive, §2).

A formula built from statement letters is a tautology if it is true for every assignment of truth values, and a contradiction if it is false for every assignment. Formulas $A$ and $B$ are logically equivalent, written $A\equiv B$, if they have the same truth value under every assignment; equivalently, $A\Leftrightarrow B$ is a tautology. Examples: $P\vee\neg P$ is a tautology (excluded middle); $P\wedge\neg P$ is a contradiction; $\neg\neg P\equiv P$; $P\Rightarrow Q\equiv\neg P\vee Q$.

For all statements $P, Q$:

Consequence: negating "and" gives "or" and vice versa, e.g. $\neg(0 < x < 1)\equiv x\le0\vee x\ge1$.

For all statements $P, Q, R$:

$\wedge$ and $\vee$ are also commutative and associative, so brackets in $P\wedge Q\wedge R$ or $P\vee Q\vee R$ don't matter.

For all statements $P, Q$: $\neg(P\Rightarrow Q)\equiv P\wedge\neg Q$. Consequence: an implication is disproved by exhibiting a case where the hypothesis holds and the conclusion fails; the negation of an implication is not another implication.

For a predicate $P(x)$ about elements $x$ of a set $S$:

• $\forall x\in S,\ P(x)$ ("for all $x$ in $S$, $P(x)$") is true when $P(x)$ holds for every $x\in S$;
• $\exists x\in S,\ P(x)$ ("there exists $x$ in $S$ with $P(x)$") is true when $P(x)$ holds for at least one $x\in S$;
• $\exists!\,x\in S,\ P(x)$ means there is exactly one such $x$. Statements can nest quantifiers, e.g. $\forall x\in\mathbb{R}\ \exists y\in\mathbb{R},\ y > x$.

Consequence: to negate a statement with several quantifiers, move $\neg$ inwards one quantifier at a time, swapping $\forall\leftrightarrow\exists$, and finally negate the predicate. For example, the negation of "$\forall\varepsilon > 0\ \exists N\ \forall n\ge N,\ |a_n| < \varepsilon$" is "$\exists\varepsilon > 0\ \forall N\ \exists n\ge N,\ |a_n|\ge\varepsilon$".

Quantifiers of the same type commute ($\forall x\forall y\equiv\forall y\forall x$, likewise $\exists$), but $\forall$ and $\exists$ do not. $\forall x\in\mathbb{R}\ \exists y\in\mathbb{R},\ y > x$ is true ($y$ may depend on $x$, e.g. $y = x + 1$), whereas $\exists y\in\mathbb{R}\ \forall x\in\mathbb{R},\ y > x$ is false (no real exceeds every real). In general $\exists y\ \forall x,\ P(x, y)\Rightarrow\forall x\ \exists y,\ P(x, y)$, but not conversely.

A reliable routine for negating a mathematical statement:

1. Write it fully in symbols, with every quantifier explicit (hidden quantifiers: "a multiple of $3$" means "$\exists k\in\mathbb{Z}$, $n = 3k$").
2. Swap each $\forall\leftrightarrow\exists$, keeping the order and the ranges.
3. Negate the innermost condition: $<$ becomes $\ge$; $\wedge\leftrightarrow\vee$; $P\Rightarrow Q$ becomes $P\wedge\neg Q$.
4. Sanity check: exactly one of the statement and your negation should be true in any example you try.