Logic Functions

Starting from two propositions \(A, B\), other propositions may be defined by combining logical operations of such propositions.

Any logic function \(C = f(A,B)\) has only two possible values: true and false. Likewise, its variables also have only two values: true and false.

is true for all ways of defining fixed but unspecified statements \(A\), \(B\), \(C\). The domain of the logic function \(f(A,B)\) is a discrete space \(S\) consisting of only \(2^2=4\) points where \(A\) and \(B\) take values {TT, TF, FT, FF} respectively. The range of the logic function \(f(A,B)\) consists of either two values: {T, F}. Therefore, there are exactly \(2^4=16\) different logic functions \(f(A,B)\). A logic function \(B = f(A_1, \ldots, A_n)\) involving \(n\) propositions is defined on a space \(S\) of \(M=2^n\) points, and there are exactly \(2^M\) such functions.

The method reduction to disjunctive form is based on the idea of retrieving \(M=2^n\) basic conjunctions from logic function which is true at one and only point. Then any logic function that is true on at least one point of \(S\) can be constructed as a logical sum of the basic conjunctions. There are \(2^M-1\) such functions. For the remaining function it suffices to take the contradiction \(A \, \overline A\). Therefore, the three operations {conjuction, disjunction, negation} are suffice to generate all possible logic functions.

Moreover, the duality property (1.9) shows that even a smaller set will suffice, because the disjunction of \(A\), \(B\) is the same as denying that they are both false:

$$A+B = \overline{(\overline A \, \overline B)}$$

As a result, the two operations (AND, NOT) already constitute an adequate set for deductive logic. Furthermore, the adequate set can be further reduced to one operation NAND, which is defined as the negation of AND:

$$A \uparrow B \equiv \overline{AB} = \overline A + \overline B \tag{1.24}$$

Now we can express at once the following:

$$\begin{align} \overline A &= A \uparrow A\\[2ex] AB &= (A \uparrow B) \uparrow (A \uparrow B)\\[2ex] A+B &= (A \uparrow A) \uparrow (B \uparrow B) \end{align} \tag{1.25}$$

Therefore, any logic function (and thus, a computer) can be constructed with NAND alone.

Likewise, a NOR operation is defined by

$$A \downarrow B \equiv \overline{A+B} = \overline A \, \overline B \tag{1.26}$$

which can also generate all logic functions:

$$\begin{align} \overline A &= A \downarrow A\\[2ex] A+B &= (A \downarrow B) \downarrow (A \downarrow B)\\[2ex] AB &= (A \downarrow A) \downarrow (B \downarrow B) \end{align} \tag{1.27}$$