2.2.2 Truth Functions

A function is a fundamental mathematical concept. It is an assignment of one element of a set called the codomain/range to another set called the domain. You can think of it as an abstract machine that takes inputs, returns outputs and that for any input, a single output is returned. The inputs are called the function arguments and the outputs are called the function's images.

You might be aware, especially if you already are familiar with set theory, that this is an informal definition. Indeed, we are going to assume the function concept as part of our metalanguage, but of course, this won't prevent us from rigorously defining what a function is in our formal theory later on. Also, do not fret if you are familiar with the paradoxes from set theory. Here we did use the concept of a set, but nothing crazy was done. I'm assuming this is a concept of our informal metalanguage and once we formally develop set theory, you may come back and realize that everything's fine. From here on, when referring to a set containing some given finite number of elements, I may write these elements separated by commas inside of curly parenthesis \(\{\}\). Consider that sets containing the same elements or even repeated ones are the same, i.e. element order and repetition doesn't matter.

A truth function is a function that has at least one input and a single output. Both inputs and output take in truth values. In propositional logic, a truth function is defined by a truth table, where one lists all the truth value combinations that its arguments can take as well as their respective output value. As we saw in 2.2.1 Definitions, truth tables are used to determine all the truth values that a wff can take. Thus, you may view wffs as truth functions whose arguments are the most basic subformulas and whose output takes the wff's truth value.

One of the things that we are going to do in this chapter is to find wffs whose truth tables correspond to any given truth function by providing an algorithm to do so, but first, let's talk about the De Morgan's laws, which will be useful for our discussion.

De Morgan's laws

Let \(A_k\) be metavariables. The De Morgan's laws state that

• \(\neg\bigwedge\limits_{k=1}^nA_k \Leftrightarrow \bigvee\limits_{k=1}^n\neg A_k\), i.e. the negation of conjunctions is equivalent to the disjunction of negations
• \(\neg\bigvee\limits_{k=1}^nA_k \Leftrightarrow \bigwedge\limits_{k=1}^n\neg A_k\), i.e. the negation of disjunctions is equivalent to the conjunction of negations

To check this, it suffices to draw the respective truth tables for two metavariables \(A\) and \(B\):

If \(A\) and \(B\) also are conjunctions or disjunctions, then the De Morgan's laws hold by induction.

Representing truth functions by wffs

Theorem: Every truth function can be generated by a wff involving only the connectives \(\neg\), \(\land\) and \(\lor\).

Proof:

Consider the wff created by the following procedure. Given a truth function, do the following for each of its rows whose output is true:

1. Make an ordered list of wffs \(U_{ij}\), such that \(U_{ij}\) is \(A_j\) if the \(j^\text{th}\) value of the \(i^\text{th}\) row is true and is \(\neg A_j\) if the \(j^\text{th}\) value of the \(i^\text{th}\) row is false
2. Let \(C_i\) be the conjunction of all these \(U_{ij}\)

The wff that I want you to consider is the disjunction of all \(C_i\), which I'll call \(D\). Notice that the only symbols it contains are \(\neg\), \(\land\) and \(\lor\). Now I'm going to prove that the truth table of that wff is exactly the truth table of the given truth function.

Each \(C_i\)'s truth table is such that all of its outputs are false except for the \(i^\text{th}\) row. The reason is that for each \(C_i\), because of the way that each \(U_{ij}\) was defined, whenever \(A_j\) is true, \(U_{ij}\) is true and whenever \(A_j\) is false, \(U_{ij}\) is again true. Thus, the output of \(C_i\)'s truth table is necessarily true for the \(i^\text{th}\) row. For any other row however, there will be a column for which at least one of the \(U_{ij}\) is false, so for any row other than the \(i^\text{th}\), \(C_i\)'s output will be false (as conjunction is false iff at least one of its closest subformulas is false).

Therefore, since the disjunction is true when at least one of its closest subformulas is true and false when all its closest subformulas are false, \(D\)'s truth table is exactly the same as the given function's!

∎

Remark: If you think about it, what the algorithm from the above proof tells is that saying "\(A\)" is the same as saying "\(A\) is true"

The wff obtained from the proof's algorithm contains disjunctions of conjunctions. Such wffs are said to be in disjunctive normal form. The more rows for which the truth function evaluates to \(\mathcal{T}\) its truth table contains, the longest its disjunctive normal form formula is going to be. Thus, if its truth table contains more true rows than false ones, the following algorithm will produce a shorter wff:

1. Given a truth function, do the following for each of its rows whose output is false:
1. Make an ordered list of wffs \(U_{ij}\), such that \(U_{ij}\) is \(A_j\) if the \(j^\text{th}\) value of the \(i^\text{th}\) row is true and is \(\neg A_j\) if the \(j^\text{th}\) value of the \(i^\text{th}\) row is false
2. Let \(C_i\) be the conjunction of all these \(U_{ij}\)
2. Let \(D\) the negation of the disjunction of all \(C_i\)
3. The final wff is the one obtained by applying the De Morgan's laws to \(D\) and to each of its \(C_i\)

In step 2., if we were to simply consider the disjunction of all \(C_i\), this would be the same algorithm that we used to create the disjunctive normal form wff, but for the truth table whose values of the final column would be opposite, as the \(C_i\) would only be taken from rows that evaluate to false. That's why the negation of the disjunction of all \(C_i\) was taken.

Remark: This could have been stated as a theorem. In fact, many informations that are transmitted in the mathematical literature could be stated as theorems, but since communication is usually done in a informal metalanguage, the proofs are informal and it's up to the author to decide whether to write statements as theorems or simply to discuss them

This new wff contains conjunctions of disjunctions, so it's said to be in conjunctive normal form.

Let's apply these algorithms to the following example, in which \(f\) is the truth function and \(f(A, B, C)\) is its image given the truth values of \(A\), \(B\) and \(C\):

First method (disjunctive normal form):

1. Make the list of \(C_i\) (for all rows except the second and the sixth, as their output is \(\mathcal{F}\)):
• \(\neg A \land \neg B \land \neg C\)
• \(\neg A \land B \land \neg C\)
• \(\neg A \land B \land C\)
• \(A \land \neg B \land \neg C\)
• \(A \land B \land \neg C\)
• \(A \land B \land C\)
2. Form the disjunction of the \(C_i\), thus getting $$\boldsymbol{(\neg A \land \neg B \land \neg C) \lor (\neg A \land B \land \neg C) \lor (\neg A \land B \land C) \lor (A \land \neg B \land \neg C) \lor (A \land B \land \neg C) \lor (A \land B \land C)}$$

Second method (conjunctive normal form):

1. Make the list of \(C_i\) (just for the second and the sixth, as their output is \(\mathcal{F}\)):
• \(\neg A \land \neg B \land C\)
• \(A \land \neg B \land C\)
2. Form the negation of the disjunction of the \(C_i\), thus getting \(\neg[(\neg A \land \neg B \land C) \lor (A \land \neg B \land C)]\)
3. Apply the De Morgan's law, thus getting $$\boldsymbol{(A \lor B \lor \neg C) \land (\neg A \lor B \lor \neg C)}$$

Since this truth table contains more true rows than false, the conjunctive normal form is shorter.

However, this still isn't the shortest wff one could come up with for this truth function. To see how, remark that independently of \(A\)'s values, \(f\) is only false whenever \(B\) is false and \(C\) is true, i.e. the first four rows are identical to the last four. Thus, you could simply consider the truth table

from which the conjunctive normal form algorithm yields $$\boldsymbol{B \lor \neg C}$$

Another way to derive that same wff is by realizing that \(f(A, B, C)\) is true whenever \(B\) is true or whenever \(C\) is false. Since \(B\)'s truth table contains \(\mathcal{T}\) only when \(B\) is true and \(\neg C\)'s truth table contains \(\mathcal{T}\) only when \(C\) is false, the disjunction of \(B\) and \(\neg C\) necessarily yields the desired truth table.

To facilitate the spotting of such variable independences of truth functions, there's a tool that relies on our human pattern recognition capability, called Karnaugh map. A Karnaugh map is another representation of a truth table.

Consider the following general truth table:

In a Karnaugh map, each cell of the last column is given a square and the ones corresponding to wffs being true are labelled:

One then creates a Karnaugh map by gluing these two squares together. Here are the four ways that this can be done:

Now consider the following general truth function with two variables:

To build a corresponding Karnaugh map, one first creates two maps like before (one for each value that \(B\) can take), this time also labelling the squares for which \(B\) is true, like for example (as there are multiple options) in the following way:

Then, one glues them together in such a way that the cases for which \(B\) is true (i.e. for which its squares are labelled) remain distinguishable from the others, like

For truth tables with more arguments, one proceeds in a similar fashion. Here's how Karnaugh maps ranging from three to six arguments may look like (instead of \(f(...)\), I wrote \(Y_i\)):

Now, to explain how to use a Karnaugh map, lets turn back to our previous example, whose truth table was

A corresponding Karnaugh map can be

In order to detect redundancies from the truth table, one creates rectangular groupings of adjacent \(\mathcal{T}\) or \(\mathcal{F}\) (depending on whether you wish to find a disjunctive or a conjunctive normal form), but not both, that come in powers of 2. You should try to make groupings as large as possible. Groupings may overlap, but they shouldn't be completely contained inside of other groupings. All the truth values you do the groupings for must belong to a grouping, even if it only contains one cell.

Remark: In case you aren't familiar with what power, multiplication or addition are, know that

• the addition of two numbers \(m\) and \(n\) is the number obtained by counting \(n\) times from \(m\)
• the multiplication of two numbers \(m\) and \(n\) is the addition of \(m\) with itself done \(n\) times
• one number \(m\) to the power of another \(n\) is the number \(m\) multiplied \(n\) times with itself

One more thing that you should know about the groupings is that this grid should be considered as being toroidally connected (i.e. have a donnut shape):

Thus, the left border cells are connected to the right border cells and the upper border cells are connected to the lower border cells. This means that such cells may form a grouping even though the grouping doesn't appear to be a rectangle at first sight. That's what happens in our example if we group the \(\mathcal{T}\) values together (meaning if we consider the disjunctive normal form):

Having done the groupings, it's a simple matter to write the corresponding wffs. In our example, the blue grouping encompasses all cells for which \(B\) is true and the green one encompasses all for which \(C\) is false. Thus, the obtained disjunctive normal form is \(\boldsymbol{B \lor \neg C}\).

If instead you wish to obtain the conjunctive normal form, the grouping goes like this:

The grouping encompasses all cells for which simultaneously \(B\) is false and \(C\) is true. Now since the grouping contains \(\mathcal{F}\) values, you must take the negation, i.e. consider \(\neg(\neg B \land C)\). Finally, by applying the De Morgan's law, you get \(\boldsymbol{B \land \neg C}\), the same wff obtained by considering the disjunctive normal form.

Functionally complete connectives

A set of connectives that are enough to generate all truth functions is said to be functionally complete. Just as is the case of \(\{\neg, \land, \lor\}\), there exist other functionally complete sets. The way to prove that a set of connectives is functionally complete is pretty straightforward. Since we've already proved that \(\neg\), \(\land\) and \(\lor\) can generate any truth function, it suffices to find wffs only containing the connectives we want that have the same truth table as \(\neg A\), \(A \land B\) and \(A \lor B\). To find a wff for a given truth function, one may then simply use one of the above algorithms and then replace the expressions \(\neg A\), \(A \land B\) and \(A \lor B\) by their equivalent versions containing only the connectives of interest.

Here's an example of another functionally complete set of connectives: \(\{\neg, \rightarrow\}\). Since \(\neg\) already belongs to \(\{\neg, \land, \lor\}\), it suffices to find equivalent wffs for \(A \land B\) and \(A \lor B\) containing only negation and implication, like respectively \(\neg(A \rightarrow \neg B)\) and \(\neg A \rightarrow B\). Behold their truth tables:

It's also possible to represent any truth function by wffs containing a single binary logical connective, which I'll conveniently call functionally complete. That's the case of the Sheffer stroke and the nor connectives:

• Proof for Sheffer's stroke:
• \(\neg A\):

\(A\)	\(A \uparrow A\)
\(\mathcal{F}\)	\(\mathcal{T}\)
\(\mathcal{T}\)	\(\mathcal{F}\)

• \(A \land B\):

\(A\)	\(B\)	\(A \uparrow B\)	\((A \uparrow B)\uparrow(A \uparrow B)\)
\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{F}\)
\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)
\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{F}\)
\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{T}\)

• \(A \lor B\):

\(A\)	\(B\)	\(A \uparrow A\)	\(B \uparrow B\)	\((A \uparrow A)\uparrow(B \uparrow B)\)
\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)
\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{T}\)
\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{T}\)
\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)

∎

• Proof for nor:
• \(\neg A\):

\(A\)	\(A \downarrow A\)
\(\mathcal{F}\)	\(\mathcal{T}\)
\(\mathcal{T}\)	\(\mathcal{F}\)

• \(A \land B\):

\(A\)	\(B\)	\(A \downarrow A\)	\(B \downarrow B\)	\((A \downarrow A)\downarrow(B \downarrow B)\)
\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)
\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{F}\)
\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{F}\)
\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)

• \(A \lor B\):

\(A\)	\(B\)	\(A \downarrow B\)	\((A \downarrow B)\downarrow(A \downarrow B)\)
\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{F}\)
\(\mathcal{F}\)	\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{T}\)
\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{F}\)	\(\mathcal{T}\)
\(\mathcal{T}\)	\(\mathcal{T}\)	\(\mathcal{F}\)	\(\mathcal{T}\)

∎

And as it turns out, they're the only ones of their kind!

Proof:

Let \(f\) be a binary truth function that corresponds to a functionally complete connective. If \(f(\mathcal{T},\mathcal{T})\) were \(\mathcal{T}\), then all wffs generated with it would take the value \(\mathcal{T}\) when all of its statement letters would be true, rendering it impossible to replicate connectives like \(\neg\), whose compound statement is false when the subformula it is applied to is true. Therefore, \(f(\mathcal{T},\mathcal{T})\) must be \(\mathcal{F}\). From the same reasoning, one can prove that \(f(\mathcal{F},\mathcal{F})\) must be \(\mathcal{T}\). Thus, \(f\)'s partial truth table must look like

If the table's middle entries are both \(\mathcal{T}\) or both \(\mathcal{F}\), then you respectively get nand's and nor's truth tables. If the second entry is \(\mathcal{F}\) and the third is \(\mathcal{T}\), then the truth table is equivalent to \(\neg A\)'s, which is independent of \(B\)'s truth value. Likewise, if the second entry is \(\mathcal{T}\) and the third is \(\mathcal{F}\), then the truth table is equivalent to \(\neg B\)'s, which is independent of \(A\)'s truth value. The proplem with these last two cases is that the \(\neg\) operator is not functionally complete. Indeed, the only truth functions of one variable definable from it are the identity function, whose outputs have the same values as its inputs, and negation itself. For example, the truth function whose outputs are all \(\mathcal{T}\) independently of the inputs cannot be generated by \(\neg\) alone.

Thus, \(\uparrow\) and \(\downarrow\) are the only functionally complete binary connectives!

∎

Sources:

• EE-110 Systèmes logiques (pour MT)Alexandre Schmid
• GIF Torus_from_rectangleLucas Vieira
• Introduction to Mathematical LogicEliott Mendelson