A Complete Set of Operations

Definition

A complete set of operations is sufficient to represent any possible truth table. In other words, we can express any customized function using elements from this set.

Examples

Look at the following examples and notice that by only using conjunction, disjunction, and negation operations, we can achieve the effect of exclusive disjunction, implication, and bi-implication.

---

Take $q_1$ and $q_2$ as arbitrary propositions:

• $q_1 \oplus q_2 \equiv \left(q_1 \land \neg q_2\right)\lor\left(\neg q_1 \land q_2\right).$
• $q_1 \Rightarrow q_2 \equiv \neg q_1 \lor q_2.$
• $q_1 \Leftrightarrow q_2 \equiv \left(\neg q_1 \lor q_2\right)\land\left(q_1 \lor \neg q_2\right).$

---

We construct a composite proposition for a given truth table in the following example:

$q_1$	$q_2$	Custom Operation$\left(q_1, q_2\right)$
T	T	T
T	F	F
F	T	T
F	F	F

Consider only those rows of the truth table where the custom operation is true. There are two such rows. Take the first one: $q_1$ is true, and $q_2$ is also true. Corresponding to this row, we get $\left(q_1 \land q_2\right)$. For the second row where the custom operation is true, $q_1$ is false, and $q_2$ is true. Corresponding to this row, we get $\left(\neg q_1 \land q_2\right)$. We call this piece of proposition obtained against one row a clause. In the example under consideration, we have two such clauses. We take the disjunction of these clauses to represent the custom operation. Therefore,

Custom operation$\left(q_1, q_2\right) =\left(q_1 \land q_2\right)\lor \left(\neg q_1 \land q_2\right).$

Theorem

Let’s look at a theorem about the complete set of operations. First, look at the formal statement of the theorem followed by its proof.

Statement

Negation, conjunction, and disjunction make a complete set of operations.

Proof

We want to show that $\{\neg,\land,\lor \}$ is a complete set. For that, we’ll show how to come up with a compound proposition ($p$) using connectives only from the given set corresponding to any conceivable truth table. Consider the following generic truth table:

$q_1$	$q_2$	$q_3$	$\ldots$	$q_n$	$p$
T	T	T	$\ldots$	T	F
T	T	F	$\ldots$	F	T
T	F	T	$\ldots$	F	F
$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$	$\vdots$
F	F	T	$\ldots$	F	F
F	F	F	$\ldots$	T	T

Let’s call, $q_{i}$ or $\neg q_{i}$ a literal.

A clause is a conjunction of $n$ literals. For each truth value ‘T’ in the last column, we make a clause consisting of $n$ literals. Let’s assume there are $k$ such rows in the truth table, and we get $k$ clauses.

While making a clause corresponding to $j$th row in the truth table, if $q_{i}$ is ‘T,’ in the $j$th row we take the literal $q_{i}$, and if it is ‘F,’ we take $\neg q_{i}$.

For example, we’ll get the following clause corresponding to the second row of the generic truth table shown above.

$$\left(q_1\land q_2\land \neg q_3 \land \ldots \land \neg q_n\right).$$

The clause corresponding to the last row will be as follows:

$$\left(\neg q_1\land \neg q_2\land \neg q_3 \land \ldots \land q_n\right).$$

We obtain the final compound proposition with desired truth values by taking the disjunction of all $k$ clauses where the desired truth value is true.

We’ll get the following compound proposition ($p$) for the above generic truth table.

$$p = \left(q_1\land q_2\land \neg q_3 \land \ldots \land \neg q_n\right)\lor \ldots \lor \left(\neg q_1\land \neg q_2\land \neg q_3 \land \ldots \land q_n\right).$$

1. Note that $p$ has only $k$ clauses out of $2^n$ possible clauses. Where $k\le 2^n$ as there are $2^n$ rows in the truth table.

2. Each clause is different from all other possible clauses. Therefore, we can call each clause unique.

3. For a given assignment of truth values to $q_1, q_2, \ldots, q_n$, exactly one clause will be true out of $2^n$ possible clauses, and the remaining $2^n-1$ will be false. If the true clause appears in $p$, it will make $p$ true; otherwise, $p$ will be false as each clause is unique.

4. If $p$ is false in all rows of the truth table, we can write $p = q_1 \land \neg q_1.$

5. If $p$ is true in all rows of the truth table, we can wire $p = q_1 \lor \neg q_1.$

As the compound proposition $p$ uses only conjunctions, disjunctions, and negation operations, and it is capable of representing any generic truth table, therefore, the set of these three operations, $\{\neg,\land,\lor \}$ is a complete set.