The set of boolean values is the set \(\{0, 1\}\text{.}\) Usually we think of \(0\) as the value “false” and \(1\) as the value “true”. In this section, the word function is used in its mathematical sense. Such a function can be thought of as a black box that converts its inputs into an output. The inputs are also called arguments and the output is called the value of the function. The set of all possible inputs of a function \(T\) is called the domain of \(T\text{.}\) The set of all possible outputs of \(T\) is called the codomain of \(T\text{.}\)
A boolean function is a function that returns a boolean value. A boolean operator is a function that takes only boolean values as inputs and returns a boolean value.
A binary boolean operator is a boolean operator that takes two boolean values as inputs. We usually use infix notation instead of functional notation to represent them. This means a symbol like \(T\) is placed between the two inputs \(x\) and \(y\) like this: \(x T y\) to represent the operator instead of using the functional notation \(T(x, y)\text{.}\) For such operators, we often use symbols that look more like arithmetic operators, e.g., \(\circ\text{,}\) than function names.
A binary boolean operator is commutative if the order of the inputs does not affect the output. In symbols, and representing the operator, \(\circ\text{,}\) we have
\begin{equation*}
x \circ y = y \circ x \quad \text{for all $x$, $y$ in the domain of $\circ$}
\end{equation*}
as the defining property of commutativity.
There are six nonconstant binary boolean operators that are commutative. They are given in the tables below. Tables like these are called truth tables, because they help us determine when a boolean expression (a combination of boolean values and boolean operators) is true and when it is false.
Note1.2.1.
We saw truth tables displayed in a slightly different format in class. This new format is helpful when computing truth tables of complex expressions. One can add columns for bigger and bigger subexpressions, working one’s way up to the full expression.
\(x\)
\(y\)
\(x \vee y\)
\(0\)
\(0\)
\(0\)
\(0\)
\(1\)
\(1\)
\(1\)
\(0\)
\(1\)
\(1\)
\(1\)
\(1\)
Table1.2.2.Or \(\left(\vee\right)\)
\(x\)
\(y\)
\(x \wedge y\)
\(0\)
\(0\)
\(0\)
\(0\)
\(1\)
\(0\)
\(1\)
\(0\)
\(0\)
\(1\)
\(1\)
\(1\)
Table1.2.3.And \(\left(\wedge\right)\)
\(x\)
\(y\)
\(x \text{ NOR } y\)
\(0\)
\(0\)
\(1\)
\(0\)
\(1\)
\(0\)
\(1\)
\(0\)
\(0\)
\(1\)
\(1\)
\(0\)
Table1.2.4.Nor
\(x\)
\(y\)
\(x \text{ NAND } y\)
\(0\)
\(0\)
\(1\)
\(0\)
\(1\)
\(1\)
\(1\)
\(0\)
\(1\)
\(1\)
\(1\)
\(0\)
Table1.2.5.Nand
\(x\)
\(y\)
\(x \veebar y\)
\(0\)
\(0\)
\(0\)
\(0\)
\(1\)
\(1\)
\(1\)
\(0\)
\(1\)
\(1\)
\(1\)
\(0\)
Table1.2.6.Xor \(\left(\veebar\right)\)
\(x\)
\(y\)
\(x \text{ XNOR } y\)
\(0\)
\(0\)
\(1\)
\(0\)
\(1\)
\(0\)
\(1\)
\(0\)
\(0\)
\(1\)
\(1\)
\(1\)
Table1.2.7.Xnor
Instead of introducing symbols for NOR, NAND, and XNOR, we can make use of symbols for a unary NOT operator as described in class. We will write \(\negg x\) for \(\text{NOT } x\text{,}\) and we will also use the overbar to negate a boolean expression. So, for example, \(\negg x = \overline{x}\text{,}\) and
Make a truth table for each of the following expressions. Each expression is a binary boolean expression, so it has two boolean values as inputs and returns a boolean value. It need not be commutative, so your truth table might or might not be one of the eight special ones above. For each expression, decide whether it in fact represents one of our six named operators (by looking at the truth table you made).
(a)
\(\overline{x} \vee \overline{y}\)
Hint.
Make the truth table. Is it one of the six special ones?
Answer.
\(x\)
\(y\)
\(\bar{x}\)
\(\bar{y}\)
\(\bar{x} \vee \bar{y}\)
\(0\)
\(0\)
\(1\)
\(1\)
\(1\)
\(0\)
\(1\)
\(1\)
\(0\)
\(1\)
\(1\)
\(0\)
\(0\)
\(1\)
\(1\)
\(1\)
\(1\)
\(0\)
\(0\)
\(0\)
(b)
\(\overline{x} \wedge \overline{y}\)
Activity1.2.2.Universal gates.
(a)
Use a single NOR operator to express \(\negg x\text{.}\)
Hint.
The NOR operator has two inputs, and you only have \(x\text{.}\) What can you do?
Answer.
\(\negg x = x \text{ NOR } x\text{.}\)
(b)
Use the results of Task 1.2.2.a and Task 1.2.1.a to express \(x \wedge y\) using only the NOR operator. (You can use as many NORs as you need, but not any other operators.)
Hint.
\(x \wedge y = \overline{x \text{ NAND } y}\text{.}\)
(c)
Similarly, use the result of Task 1.2.1.b to express \(x \vee y\) using only the NOR operator. (You can use as many NORs as you need, but not any other operators.)
(d)
Use NOR operators to express \(x \veebar y\text{.}\)
In doing Activity 1.2.2, you showed that the NOR operator is a universal gate. This means that any boolean function can be expressed using only NORs. To spell it out, we used NORs to express \(\negg x\text{,}\)\(x \wedge y\text{,}\)\(x \vee y\text{,}\) and \(x \veebar y\text{.}\) The remaining operators, NAND and XNOR, can be expressed in terms of these four. This shows that all six binary boolean operators (that is, those represented in Table 1.2.2–1.2.7 ) are expressible in terms of NOR alone.
Remark 1.2.8 is interesting from a hardware point of view. We will soon begin to explore the manner in which digital computers are constructed from logic gates. A logic gate is the basic building block of a digital electronic circuit, much like a statement is the building block of a Python program. Logic gates operate on logical signals, which are voltages representing boolean values. Their inputs are combined or modified inside the gate to produce an output signal representing the value of the operation as applied to the input signals.
Because NOR is a universal gate, it is possible to build a computer using only NOR gates. They are cheaper to manufacture than AND and OR gates, and even NOT gates are expressible in terms of NOR. They also are faster: every gate through which a signal passes adds a small delay to the circuit. These are only measured in nanoseconds, but when you have millions of gates, it adds up. NOR gates require less internal wiring than AND and OR gates, so they are faster.
In Homework 1 you will show that NAND is similarly universal. The idea is similar to the one above, but you will have to work out the details yourself.
