Mathematical logic formulas

Use it to remove $\to$ before any manipulation; it holds for all truth values.

True exactly when $p$ and $q$ have the same truth value; $p\oplus q\equiv \neg (p\leftrightarrow q)$.

For $n$ distinct atoms; the second count is the number of different possible output columns.

Here T and F stand for the constants true and false.

Negation swaps $\wedge$ and $\vee$ and negates each part.

Each of $\wedge$ and $\vee$ distributes over the other.

Useful for quickly simplifying a formula.

An implication fails only when the hypothesis holds and the conclusion fails.

Exportation and the two combining rules; note the hypotheses combine with $\vee$ when the conclusion is shared.

Rewrite each side with $\neg a\vee b$ to check them. With a shared conclusion and $\vee$ between the implications, the hypotheses combine with $\wedge$.

To refute an argument, find one assignment making every premise true and the conclusion false.

Push $\neg$ inside by flipping each quantifier and negating the body; repeat for nested quantifiers.

$\forall$ distributes over $\wedge$ and $\exists$ distributes over $\vee$, as equivalences.

The same holds for $\forall$ with $\wedge$ and $\exists$ with $\vee$. The step $\exists x\psi \equiv \psi$ (or $\forall x\psi \equiv \psi$) used here relies on the domain being non-empty.

The quantifier flips when it leaves the antecedent. It keeps its kind when it leaves the consequent: $\forall x(\psi \to P(x))\equiv \psi \to \forall xP(x)$ and $\exists x(\psi \to P(x))\equiv \psi \to \exists xP(x)$. The $\exists$ forms need a non-empty domain.

Write the body as $\neg P(x)\vee Q(x)$, distribute $\exists$ over $\vee$, and use $\exists x\neg P(x)\equiv \neg \forall xP(x)$. By contrast, $\forall x(P(x)\to Q(x))$ only implies $\forall xP(x)\to \forall xQ(x)$.