Expressibility

Truth functions

A formula with n sentence letters requires ${\displaystyle 2^{n}\,\!}$ lines in its truth table. And there are ${\displaystyle 2^{m}\,\!}$ possible truth functions having a truth table of m lines. Thus there are ${\displaystyle 2^{2^{n}}\,\!}$ possible truth functions of n sentence letters. There are 4 possible truth functions of one sentence letter (requiring a 2 line truth table) and 16 possible truth functions of two sentence letters (requiring a 4 line truth table). We illustrate this with the following tables. The numbered columns represent the different possibilities for the column of a main connective.

${\displaystyle \mathrm {P} \,\!}$ (i) (ii) (iii) (iv) T T T F F F T F T F

You will recognize column (iii) as the negation truth function.

${\displaystyle \mathrm {P} \,\!}$ ${\displaystyle \mathrm {Q} \,\!}$ (i) (ii) (iii) (iv) (v) (vi) (vii) (viii) (ix) (x) (xi) (xii) (xiii) (xiv) (xv) (xvi) T T T T T T T T T T F F F F F F F F T F T T T T F F F F T T T T F F F F F T T T F F T T F F T T F F T T F F F F T F T F T F T F T F T F T F T F

Column (ii) represents the truth function for disjunction, column (v) represents conditional, column (vii) represents biconditional, and column (viii) represents conjunction.

Expressing arbitrary truth functions

The question arises whether we have enough connectives to represent all the truth functions of any number of sentence letters. Remember that each row represents one valuation. We can express that valuation by conjoining sentence letters assigned True under that valuation and negations of sentence letters assigned false under that valuation. The four valuations of the second table above can be expressed as

${\displaystyle \mathrm {P} \land \mathrm {Q} \,\!}$

${\displaystyle \mathrm {P} \land \lnot \mathrm {Q} \,\!}$

${\displaystyle \lnot \mathrm {P} \land \mathrm {Q} \,\!}$

${\displaystyle \lnot \mathrm {P} \land \lnot \mathrm {Q} \,\!}$

Now we can express an arbitrary truth function by disjoining the valuations under which the truth function has the value true. For example, we can express column (x) with:

(1)      ${\displaystyle (\mathrm {P} \land \lnot \mathrm {Q} )\lor (\lnot \mathrm {P} \land \mathrm {Q} )\,\!}$

You can confirm by completing the truth table that this produces the desired result. The formula is true when either (a) ${\displaystyle \mathrm {P} \,\!}$ is true and ${\displaystyle \mathrm {Q} \,\!}$ is false or (b) ${\displaystyle \mathrm {P} \,\!}$ is false and ${\displaystyle \mathrm {Q} \,\!}$ is true. There is an easier way to express this same truth function: ${\displaystyle \mathrm {P} \leftrightarrow \lnot \mathrm {Q} \,\!}$. Coming up with a simple way to express an arbitrary truth function may require insight, but at least we have an automatic mechanism for finding some way to express it.

Now consider a second example. We want to express a truth function of ${\displaystyle \mathrm {P} \,\!}$, ${\displaystyle \mathrm {Q} \,\!}$, and ${\displaystyle \mathrm {R} \,\!}$, and we want this to be true under (and only under) the following three valuations.

			(i)		(ii)		(iii)
	${\displaystyle \mathrm {P} \,\!}$		True		False		False
	${\displaystyle \mathrm {Q} \,\!}$		True		True		False
	${\displaystyle \mathrm {R} \,\!}$		False		False		True

We can express the three conditions which yield true as

${\displaystyle \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} \,\!}$

${\displaystyle \lnot \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} \,\!}$

${\displaystyle \lnot \mathrm {P} \land \lnot \mathrm {Q} \land \mathrm {R} \,\!}$

Now we need to say that either the first condition holds or that the second condition holds or that the third condition holds:

(2)      ${\displaystyle (\mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} )\lor (\lnot \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} )\lor (\lnot \mathrm {P} \land \lnot \mathrm {Q} \land \mathrm {R} )\,\!}$

You can verify by a truth table that it yields the desired result, that the formula is true in just the interpretation above.

This technique for expressing arbitrary truth functions does not work for truth functions evaluating to False in every interpretation. We need at least one interpretation yielding True in order to get the formula started. However, we can use any tautologically false formula to express such truth functions. ${\displaystyle \mathrm {P} \land \lnot \mathrm {P} \,\!}$ will suffice.

Normal forms

A normal form provides a standardized rule of expression where any formula is equivalent to one which conforms to the rule. It will be useful in the following to define a literal as a sentence letter or its negation.

The technique for expressing arbitrary truth functions used formulae in disjunctive normal form. A formula in disjunctive normal form is a disjunction of conjunctions of literals. For the purposes of this definition, we countenance many-place disjunctions and conjunctions such as ${\displaystyle \lnot \mathrm {P} \land \mathrm {Q} \land \lnot \mathrm {R} \,\!}$ or ${\displaystyle \lnot \mathrm {P} \lor \mathrm {Q} \lor \lnot \mathrm {R} \,\!}$. Also for the purpose of this definition we countenance degenerate disjunctions and conjunctions of only one disjunct or conjunct. Thus we count ${\displaystyle \mathrm {P} \,\!}$ as being in disjunctive normal form. It is a degenerate (one-place) disjunction of a degenerate (one-place) conjunction. We could make it less degenerate (but more debauched) by converting it to the equivalent formula ${\displaystyle (\mathrm {P} \land \mathrm {P} )\lor (\mathrm {P} \land \mathrm {P} )\,\!}$.

There is another common normal form in sentential logic, conjunctive normal form. Conjunctive normal form is a conjunction of disjunctions of literals. We can express arbitrary truth functions in conjunctive normal form. First, take the valuations for which the truth function evaluates to False. For each such valuation, form a disjunction of sentence letters the valuation assigns False together with the negations of sentence letters the valuation assign true. For the valuation

${\displaystyle \mathrm {P} \,\!}$   :    False

${\displaystyle \mathrm {Q} \,\!}$   :    True

${\displaystyle \mathrm {R} \,\!}$   :    False

we form the disjunction

${\displaystyle \lnot \mathrm {P} \lor \mathrm {Q} \lor \lnot \mathrm {R} \,\!}$

The conjunctive normal form expression of an arbitrary truth function is the conjunction of all such disjunctions matching the interpretations for which the truth function evaluates to false. The conjunctive normal form equivalent of (1) above is

${\displaystyle (\lnot \mathrm {P} \lor \mathrm {Q} )\land (\mathrm {P} \lor \lnot \mathrm {Q} )\,\!}$

The conjunctive normal form equivalent of (2) above is

${\displaystyle (\lnot \mathrm {P} \lor \lnot \mathrm {Q} \lor \lnot \mathrm {R} )\land (\mathrm {P} \lor \lnot \mathrm {Q} \lor \lnot \mathrm {R} )\land (\mathrm {P} \lor \lnot \mathrm {Q} \lor \mathrm {R} )\land (\mathrm {P} \lor \mathrm {Q} \lor \lnot \mathrm {R} )\land (\mathrm {P} \lor \mathrm {Q} \lor \mathrm {R} )}$

Interdefinability of connectives

Negation and conjunction are sufficient to express the other three connectives and indeed any arbitrary truth function.

${\displaystyle \mathrm {P} \lor \mathrm {Q} \,\!}$       ${\displaystyle \lnot (\lnot \mathrm {P} \land \lnot \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \rightarrow \mathrm {Q} \,\!}$       ${\displaystyle \lnot (\mathrm {P} \land \lnot \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \leftrightarrow \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {P} )\,\!}$       ${\displaystyle \lnot (\mathrm {P} \land \lnot \mathrm {Q} )\land \lnot (\mathrm {Q} \land \lnot \mathrm {P} )\,\!}$

Negation and disjunction are sufficient to express the other three connectives and indeed any arbitrary truth function.

${\displaystyle \mathrm {P} \land \mathrm {Q} \,\!}$       ${\displaystyle \lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \rightarrow \mathrm {Q} \,\!}$       ${\displaystyle \lnot \mathrm {P} \lor \mathrm {Q} \,\!}$

${\displaystyle \mathrm {P} \leftrightarrow \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \land \mathrm {Q} )\lor (\lnot \mathrm {P} \land \lnot \mathrm {Q} )\,\!}$       ${\displaystyle \lnot (\lnot \mathrm {P} \lor \lnot \mathrm {Q} )\lor \lnot (\mathrm {P} \lor \mathrm {Q} )\,\!}$

Negation and conditional are sufficient to express the other three connectives and indeed any arbitrary truth function.

${\displaystyle \mathrm {P} \lor \mathrm {Q} \,\!}$       ${\displaystyle \lnot \mathrm {P} \rightarrow \mathrm {Q} \,\!}$

${\displaystyle \mathrm {P} \land \mathrm {Q} \,\!}$       ${\displaystyle \lnot (\mathrm {P} \rightarrow \lnot \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \leftrightarrow \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \rightarrow \mathrm {Q} )\land (\mathrm {Q} \rightarrow \mathrm {P} )\,\!}$       ${\displaystyle \lnot ((\mathrm {P} \rightarrow \mathrm {Q} )\rightarrow \lnot (\mathrm {Q} \rightarrow \mathrm {P} ))\,\!}$

Negation and biconditional are not sufficient to express the other three connectives.

Joint and alternative denials

We have seen that three pairs of connectives are each jointly sufficient to express any arbitrary truth function. The question arises, is it possible to express any arbitrary truth function with just one connective? The answer is yes, but not with any of our connectives. There are two possible binary connectives each of which, if added to ${\displaystyle {\mathcal {L_{S}}}\,\!}$, would be sufficient.

Alternative denial

Alternative denial, sometimes called NAND. The usual symbol for this is called the Sheffer stroke. Temporarily add the symbol ${\displaystyle \mid \,\!}$ to ${\displaystyle {\mathcal {L_{S}}}\,\!}$ and let ${\displaystyle {\mathfrak {v}}[(\varphi \mid \psi )]\,\!}$ be True when at least one of ${\displaystyle \varphi \,\!}$ or ${\displaystyle \psi \,\!}$ is false. It has the truth table :

${\displaystyle \mathrm {P} \,\!}$ ${\displaystyle \mathrm {Q} \,\!}$ ${\displaystyle \mathrm {P} \mid \mathrm {Q} \,\!}$ T T F T F T F T T F F T

We now have the following equivalences.

${\displaystyle \lnot \mathrm {P} \,\!}$       ${\displaystyle \mathrm {P} \mid \mathrm {P} \,\!}$

${\displaystyle \mathrm {P} \land \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \mid \mathrm {Q} )\mid (\mathrm {P} \mid \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \lor \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \mid \mathrm {P} )\mid (\mathrm {Q} \mid \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \rightarrow \mathrm {Q} \,\!}$       ${\displaystyle \mathrm {P} \mid (\mathrm {Q} \mid \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \leftrightarrow \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \mid \mathrm {Q} )\mid ((\mathrm {P} \mid \mathrm {P} )\mid (\mathrm {Q} \mid \mathrm {Q} ))\,\!}$

Joint denial

Joint denial, sometimes called NOR. Temporarily add the symbol ${\displaystyle \downarrow \,\!}$ to ${\displaystyle {\mathcal {L_{S}}}\,\!}$ and let ${\displaystyle {\mathfrak {v}}[(\varphi \downarrow \psi )]\,\!}$ be True when both ${\displaystyle \varphi \,\!}$ and ${\displaystyle \psi \,\!}$ are false. It has the truth table :

${\displaystyle \mathrm {P} \,\!}$ ${\displaystyle \mathrm {Q} \,\!}$ ${\displaystyle \mathrm {P} \downarrow \mathrm {Q} \,\!}$ T T F T F F F T F F F T

We now have the following equivalences.

${\displaystyle \lnot \mathrm {P} \,\!}$       ${\displaystyle \mathrm {P} \downarrow \mathrm {P} \,\!}$

${\displaystyle \mathrm {P} \land \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \downarrow \mathrm {P} )\downarrow (\mathrm {Q} \downarrow \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \lor \mathrm {Q} \,\!}$       ${\displaystyle (\mathrm {P} \downarrow \mathrm {Q} )\downarrow (\mathrm {P} \downarrow \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \rightarrow \mathrm {Q} \,\!}$       ${\displaystyle ((\mathrm {P} \downarrow \mathrm {Q} )\downarrow \mathrm {Q} )\downarrow ((\mathrm {P} \downarrow \mathrm {Q} )\downarrow \mathrm {Q} )\,\!}$

${\displaystyle \mathrm {P} \leftrightarrow \mathrm {Q} \,\!}$       ${\displaystyle ((\mathrm {P} \downarrow \mathrm {P} )\downarrow \mathrm {Q} )\downarrow (\mathrm {P} \downarrow (\mathrm {Q} \downarrow \mathrm {Q} ))\,\!}$

← Validity

↑ Sentential Logic

Properties of Sentential Connectives →