A truth table can tell us more than the value of one formula. Its final column tells us whether the formula can ever be true, whether it can ever be false, and whether an argument is valid. Predicates and quantifiers extend the same true-or-false language to statements about objects in a chosen universe.

Walkthrough

Read the final column as a classification

Start with the completed final column of a truth table.

• If it contains only $1$s, the formula is a tautology.
• If it contains only $0$s, the formula is a contradiction.
• If it contains both values, the formula is a contingency.

This is useful because validity can also be phrased as a classification problem. Join an argument's premises with $\land$, make that conjunction imply the conclusion, and ask whether the result is a tautology. If it is, there is no truth assignment where all the premises are true and the conclusion is false.

Let the subject vary

A proposition such as “Socrates is mortal” has a truth value. The phrase “is mortal” is different: it becomes true or false only after a subject is supplied. Write

$$M(x)=\text{“}x\text{ is mortal.”}$$

The symbol $x$ is a variable, and $M$ is a predicate. Once we choose a subject, $M(x)$ becomes a proposition. For example, $M(\text{Socrates})$ is true in the intended interpretation.

Bind the variable with a quantifier

A quantifier says how many objects must make a predicate true:

$$\forall x\,P(x) \qquad\text{or}\qquad \exists x\,P(x).$$

The first means “every $x$ has property $P$.” The second means “at least one $x$ has property $P$.” A universal statement needs every case, so one counterexample disproves it. An existential statement needs only one successful case, called a witness.

Negation swaps these two jobs:

$$\neg\forall x\,P(x)\equiv\exists x\,\neg P(x), \qquad \neg\exists x\,P(x)\equiv\forall x\,\neg P(x).$$

In words, “not everyone” means “someone not,” while “there is nobody” means “everyone not.”

Classifying propositional formulas

A propositional formula is satisfiable when at least one truth assignment makes it true. It is falsifiable when at least one assignment makes it false. These properties give three important classes:

The following table checks one formula from each class. The implication $p\Rightarrow q$ is false only when $p=1$ and $q=0$.

The final columns now classify the formulas:

$$p\lor\neg p\text{ is a tautology}, \qquad p\land\neg p\text{ is a contradiction}, \qquad p\Rightarrow q\text{ is a contingency}.$$

Formula classes overlap in one place

Why truth tables become expensive

A formula with $n$ distinct propositional variables has $2^n$ possible truth assignments, so its complete truth table has $2^n$ rows. The number of columns depends on how many intermediate expressions we choose to display.

Checking every row is a valid decision procedure, but its cost grows exponentially with $n$. The Boolean satisfiability problem, usually called SAT, asks whether a formula has at least one satisfying assignment. SAT is NP-complete: a polynomial-time algorithm for every SAT instance would prove $P=NP$, while a proof that no such algorithm exists would prove $P\ne NP$. Logical identities can classify many particular formulas without listing every row, but they do not give a known polynomial-time method for every SAT instance.

Valid arguments and syllogisms

An argument has premises $P_1,\ldots,P_k$ and a conclusion $C$. It is valid when

$$(P_1\land\cdots\land P_k)\Rightarrow C$$

is a tautology. Validity does not say that the premises are actually true. It says that there is no case where all of them are true and the conclusion is false.

Modus ponens

Modus ponens has the form

$$\frac{p\Rightarrow q\qquad p}{q}.$$

Its associated formula is

$$((p\Rightarrow q)\land p)\Rightarrow q.$$

Logical identities reduce it to true:

$$\begin{aligned} ((p\Rightarrow q)\land p)\Rightarrow q &\equiv \neg((\neg p\lor q)\land p)\lor q\\ &\equiv \bigl(\neg(\neg p\lor q)\lor\neg p\bigr)\lor q\\ &\equiv \neg(\neg p\lor q)\lor(\neg p\lor q)\\ &\equiv 1. \end{aligned}$$

The last line has the form $\neg A\lor A$, so the argument is valid.

Two more valid forms

The second form reasons backward through an implication correctly: if $p$ would force $q$, but $q$ is false, then $p$ cannot be true. This is not the same as the invalid move from $p\Rightarrow q$ and $q$ to $p$.

Predicates and universes of discourse

A universe of discourse, written $U$, is the set of objects currently under discussion. A one-variable predicate is a Boolean-valued function

$$P:U\longrightarrow\mathbb B, \qquad \mathbb B=\{0,1\}.$$

The value $P(x)=1$ means that object $x$ has the property; $P(x)=0$ means that it does not.

For a small universe containing the Greek figures used in the example, define

$$M(x)=\text{“}x\text{ is mortal.”}$$

Under the intended interpretation,

$$M(\text{Socrates})=1, \qquad M(\text{Zeus})=0.$$

The universe matters. A predicate can be evaluated only on objects in its stated domain, and its truth values depend on the interpretation we chose.

A predicate may have more than one variable. A two-variable predicate on the real numbers has type

$$L:\mathbb R^2\longrightarrow\mathbb B.$$

For example, let $L(x,y)$ mean $x\le y$. Then

$$L(1,2)=1, \qquad L(4,2)=0.$$

Before values are supplied or variables are quantified, $L(x,y)$ is an open formula rather than a proposition with one fixed truth value.

Quantifiers, scope, and bound variables

The two basic quantifiers are

Unless a smaller domain is written beside the quantifier, $x$ ranges over the chosen universe $U$.

$$\forall x\,P(x)$$

is true exactly when $P(x)=1$ for every $x\in U$. One element with $P(x)=0$ is a counterexample.

$$\exists x\,P(x)$$

is true exactly when at least one $x\in U$ has $P(x)=1$. Such an element is a witness. The existential statement is false only when $P(x)=0$ throughout $U$.

A universal statement requires a constant true predicate

Translating “all humans are mortal”

Let $H(x)$ mean “$x$ is human” and $M(x)$ mean “$x$ is mortal.” Then

$$\forall x\,(H(x)\Rightarrow M(x))$$

says “Every human is mortal.” The implication is important. An object that is not human does not refute the statement; its antecedent $H(x)$ is false, so that instance of the implication is true.

Free and bound variables

A quantifier binds occurrences of its variable inside its scope. In

$$\forall x\,Q(x,y),$$

$x$ is bound, but $y$ is still free. The formula may still depend on $y$. In

$$\forall x\,\exists y\,Q(x,y),$$

both variables are bound, so the result is a proposition once the universe and predicate have been interpreted.

Order matters. In general,

$$\forall x\,\exists y\,Q(x,y) \not\equiv \exists y\,\forall x\,Q(x,y).$$

The first formula may choose a different $y$ for each $x$. The second requires one $y$ that works for every $x$.

Negating quantified statements

Quantifier negation follows De Morgan's pattern:

$$\boxed{\neg\forall x\,P(x)\equiv\exists x\,\neg P(x)}, \qquad \boxed{\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)}.$$

The first identity says that a universal claim is false exactly when a counterexample exists. The second says that an existential claim is false exactly when every candidate fails.

Example with nested quantifiers

Negate

$$\forall x\,\bigl(P(x)\lor\exists y\,Q(x,y)\bigr).$$

Move the negation inward one layer at a time:

1. Pass the negation through the universal quantifier, changing $\forall x$ to $\exists x$.
2. Apply De Morgan's law to the disjunction, changing $\lor$ to $\land$ and negating both parts.
3. Pass the remaining negation through the existential quantifier, changing $\exists y$ to $\forall y$.

$$\begin{aligned} \neg\forall x\,\bigl(P(x)\lor\exists y\,Q(x,y)\bigr) &\equiv \exists x\,\neg\bigl(P(x)\lor\exists y\,Q(x,y)\bigr)\\ &\equiv \exists x\,\bigl(\neg P(x)\land\neg\exists y\,Q(x,y)\bigr)\\ &\equiv \exists x\,\bigl(\neg P(x)\land\forall y\,\neg Q(x,y)\bigr). \end{aligned}$$

The final statement says that some $x$ fails $P$, and for that same $x$, $Q(x,y)$ fails for every $y$.

Why the universe matters

An unrestricted quantified statement can change truth value when its universe changes. For example,

$$\forall x\,(x>0)$$

is true if $U=\{1,2,3,\ldots\}$, but false if $U=\mathbb R$ because $0$ and every negative real number are counterexamples. If your convention includes $0$ in $\mathbb N$, the statement is also false over $\mathbb N$. Always state the universe rather than relying on an unstated convention.

Restricted quantifiers

If $A\subseteq U$, a quantifier can be restricted to $A$:

$$\forall x\in A\,P(x) \equiv \forall x\,(x\in A\Rightarrow P(x)),$$

and

$$\exists x\in A\,P(x) \equiv \exists x\,(x\in A\land P(x)).$$

The connective changes because the two statements have different jobs:

• A universal restriction uses an implication. Objects outside $A$ must not become counterexamples.
• An existential restriction uses a conjunction. A witness must both belong to $A$ and satisfy $P$.

For example,

$$\forall x\in\mathbb N\,(x\ge0)$$

is true under the usual conventions for $\mathbb N$. If the surrounding universe also contains $-1$, that object is irrelevant: the expanded implication

$$-1\in\mathbb N\Rightarrow -1\ge0$$

has a false antecedent and is therefore true.

Likewise,

$$\exists x\in\mathbb N\,(x>9000)$$

is true because $10{,}000$ is a witness. Objects outside $\mathbb N$ neither prove nor disprove it.

De Morgan's laws keep the restriction:

$$\neg\forall x\in A\,P(x) \equiv \exists x\in A\,\neg P(x),$$ $$\neg\exists x\in A\,P(x) \equiv \forall x\in A\,\neg P(x).$$