Question

It can be shown that the set of operations \(S=\\{+, \cdot, \sim\\}\) is functionally complete. That is, every Boolean function can be represented by a form \(\mathrm{f}\left(\mathrm{x}_{1}, \ldots, \mathrm{x}_{n}\right)\) in variables \(\mathrm{x}_{1}, \ldots, \mathrm{x}_{\mathrm{n}}\) and operations \(+, \cdot, \sim .\) Equivalently, the set of gates \(\mathrm{S}^{1}=\\{\mathrm{OR}\), AND, NOT \(\\}\) is functionally complete. Show that: a) \(S_{1}=\\{+, \sim\\}\) b) \(S_{0}=\\{\bullet \sim\\}\) c) \(\mathrm{S}_{3}=\\{\uparrow\\}\) where \(\mathrm{x}_{1} \uparrow \mathrm{x}_{2}=\sim\left(\mathrm{x}_{1} \cdot \mathrm{x}_{2}\right)\) d) \(\mathrm{S}_{4}=\\{\downarrow\\}\) where \(\mathrm{x}_{1} \downarrow \mathrm{x}_{2}=\sim\left(\mathrm{x}_{1} \cdot \mathrm{x}_{2}\right)\) (2) are functionally complete.

Short answer

The sets \(\mathrm{S}_{1} = \{+,\sim\}\), \(\mathrm{S}_{0} = \{\cdot, \sim\}\), \(\mathrm{S}_{3} = \{\uparrow\}\), and \(\mathrm{S}_{4} = \{\downarrow\}\) are all functionally complete since we can construct OR, AND, and NOT gates using the operations in each set: 1. \(\mathrm{S}_{1}\): AND can be constructed as \(x AND y = \sim(\sim x + \sim y)\). 2. \(\mathrm{S}_{0}\): OR can be constructed as \(x OR y = \sim (\sim x \cdot \sim y)\). 3. \(\mathrm{S}_{3}\): NOT, AND, and OR can be constructed as \(NOT(x) = x \uparrow x\), \(x AND y = (x \uparrow y) \uparrow (x \uparrow y)\), and \(x OR y = (x \uparrow x) \uparrow (y \uparrow y)\), respectively. 4. \(\mathrm{S}_{4}\): NOT, AND, and OR can be constructed as \(NOT(x) = x \downarrow x\), \(x AND y = (x \downarrow y) \downarrow (x \downarrow y)\), and \(x OR y = (x \downarrow x) \downarrow (y \downarrow y)\), respectively.

Step-by-step solution

(a) \(\mathrm{S}_{1} = \\{+, \sim\\}\) is functionally complete.

We need to show that we can construct OR, AND, and NOT gates using the operations in \(\mathrm{S}_{1}\). 1. \(NOT (x) = \sim x\) - The NOT gate is already given as a part of the set. 2. \(x OR y = x + y\) - The OR gate is also given as a part of the set. 3. \(x AND y = \sim(\sim x + \sim y)\) - Applying De Morgan's Law, we can construct the AND gate using NOT and OR gates. Since we can construct all the basic gates, the set \(\mathrm{S}_{1}\) is functionally complete.

(b) \(\mathrm{S}_{0} = \\{\cdot, \sim\\}\) is functionally complete.

We need to show that we can construct OR, AND, and NOT gates using the operations in \(\mathrm{S}_{0}\). 1. \(NOT (x) = \sim x\) - The NOT gate is given as a part of the set. 2. \(x AND y = x \cdot y\) - The AND gate is given as a part of the set. 3. \(x OR y = \sim (\sim x \cdot \sim y)\) - Applying De Morgan's Law, we can construct the OR gate using NOT and AND gates. Since we can construct all the basic gates, the set \(\mathrm{S}_{0}\) is functionally complete.

(c) \(\mathrm{S}_{3} = \\{\uparrow\\}\) is functionally complete.

We need to show that we can construct OR, AND, and NOT gates using the operations in \(\mathrm{S}_{3}\), where \(x_1 \uparrow x_2 = \sim (x_1 \cdot x_2)\). 1. \(NOT (x) = x \uparrow x\) - Since \(x \uparrow x = \sim (x \cdot x) = \sim x\), the NOT gate can be constructed using the operation. 2. \(x AND y = (x \uparrow y) \uparrow (x \uparrow y)\) - As \(NOT (x \uparrow y) = (x \uparrow y) \uparrow (x \uparrow y)\), this is equal to \(x \cdot y\), constructing the AND gate. 3. \(x OR y = (x \uparrow x) \uparrow (y \uparrow y)\) - Using the previous result, we found that \(x \uparrow x = NOT (x)\). Then, we get \((NOT (x)) \uparrow (NOT (y))\), which according to De Morgan's Law, is equal to \(x OR y\). Since we can construct all the basic gates, the set \(\mathrm{S}_{3}\) is functionally complete.

(d) \(\mathrm{S}_{4} = \\{\downarrow\\}\) is functionally complete.

We need to show that we can construct OR, AND, and NOT gates using the operations in \(\mathrm{S}_{4}\), where \(x_1 \downarrow x_2 = \sim (x_1 + x_2)\). 1. \(NOT (x) = x \downarrow x\) - Since \(x \downarrow x = \sim (x + x) = \sim x\), the NOT gate can be constructed using the operation. 2. \(x AND y = (x \downarrow y) \downarrow (x \downarrow y)\) - As \(NOT (x \downarrow y) = (x \downarrow y) \downarrow (x \downarrow y)\), this is equal to \(x \cdot y\), constructing the AND gate. 3. \(x OR y = (x \downarrow x) \downarrow (y \downarrow y)\) - Using the previous result, we found that \(x \downarrow x = NOT (x)\). Then, we get \((NOT (x)) \downarrow (NOT (y))\), which according to De Morgan's Law, is equal to \(x OR y\). Since we can construct all the basic gates, the set \(\mathrm{S}_{4}\) is functionally complete.

Key concepts

Boolean Function

At the heart of digital logic and computing lies the concept of a Boolean function. This is essentially a mathematical way to represent logical operations using binary variables, which can only take values of 0 or 1, often symbolized in logic as ‘false’ and ‘true’ respectively. A Boolean function operates on these binary inputs and yields a binary output based on certain logical rules.

For instance, a simple Boolean function could take two inputs, such as ‘x’ and ‘y’, and produce an output that is the logical AND of these inputs. In this case, the output is 1 (or true) only if both ‘x’ and ‘y’ are 1, and 0 (false) otherwise. In our step-by-step solution from the textbook, we see how Boolean functions can be constructed using a limited set of operations to create more complex logical expressions. This demonstrates the power and foundational role of Boolean functions in computational logic and electronic circuit design.

Boolean Algebra

Boolean algebra is the branch of algebra that deals with Boolean values and is fundamental to the design of digital computer circuits and programming languages. It provides the rules for manipulating expressions filled with binary variables and logical operations such as AND (multiplication \( \cdot \)), OR (addition \( + \)), and NOT (negation \( \sim \) or sometimes \( \overline{ } \) over the variable).

The exercise explores the concept of functional completeness in Boolean algebra by showing that a certain set of operations is sufficient to express any possible Boolean function. This forms the backbone of how computers perform calculations, as it reduces the complexity of logical statements while maintaining their logical equivalence. Boolean algebra allows us to perform algebraic manipulations on logic equations, simplifying circuit designs and improving computer algorithms.

De Morgan's Law

A keystone in the arch of logic, De Morgan's Law is vital for simplifying and transforming logical expressions in both Boolean algebra and set theory. This law consists of two transformations:

NOT (A AND B) = NOT A OR NOT B

NOT (A OR B) = NOT A AND NOT B

These rules allow us to express conjunctions and disjunctions purely in terms of each other via negation, a critical ability in digital logic design. As detailed in the step-by-step solution, De Morgan’s Law is instrumental in achieving functional completeness with different sets of operations. It provides a crucial technique to express the AND operation as OR and NOT (and vice versa), which is not only useful in theoretical proofs but is also applied in the design and minimization of logic circuits, enhancing computational efficiency. Keeping De Morgan's Law in mind is essential for students aiming to master Boolean logic and its application in computing.