Section 10.2 Digital Logic Circuits
In the late 1930s, Claude Shannon (1916-2001), American mathematician, discovered a connection between logical connectives and physical circuits. Then, John Tukey (1915-2000), American mathematician and statistician, coined the term bits, short for binary digits, which are digits that can either be 0 or 1, and can represent T and F in logic.
Subsection 10.2.1 Digital Logic Circuits
One or more inputs are combined according to some rule, to produce an output. This is similar to a function.
The 3 basic logic gates are:
NOT gate, or inverter, which takes in a single input and outputs the opposite, like the negation operator.
AND gate, which behaves like the conjunction operator.
OR gate, which behaves like the disjunction operator.
By combining these gates in various ways, the inputs can be combined to form circuits that produce certain outputs. The output of a circuit can be summaried in an input/output table, which is analogous to a truth table for Boolean expressions.
There is a one-to-one correspondence between Boolean expressions and combinatorial circuits.
We can also consider a multiple-input AND-gate, or multiple-input OR-gate, which is an AND or OR gate which takes in multiple inputs.
With a combinatorial circuit, a single input can be split to be used as the input for two separate logic gates. Also, the output of a logic gate can be used as an input for another. Two input wires cannot be combined. Also, outputs can't loop back to be used as an input for the same logic gate.
Subsection 10.2.2
Definition 10.2.1.
Two logic circuits are equivalent if their input/ouput tables are identical.
Definition 10.2.2.
Consider two equiavalent logic gates. One is said to be simpler than the other if it contains fewer logic gates.
Subsection 10.2.3 Converting Input/Output Table to Boolean Expression/Circuit
Consider an input/output table. To determine an associated Boolean expression, first, we can simply examine the table to see if there is any obvious pattern.
Otherwise, there are multiple methods that can be considered. One method is to consider all rows which produce an output of 1 (the “true” rows), and construct a Boolean expression which is true in precisely each case, made up of conjunctions of the components. Then, combine each of these conjunctions with a disjunction. This expression will be a Boolean expression for the table.
On the other hand, it is possible that there is a simpler equivalent expression that describes the same table. The Boolean expression can be simplified to this by using the laws of logic.
Finally, to check your solution, your Boolean expression can be checked with the original input/output table, to see if it is correct.
Subsection 10.2.4 Karnaugh Maps (K-maps)
A method for simplifying Boolean expressions.
Subsection 10.2.5 More Complex Logic Gates
The NAND-gate is the negation of an AND-gate, and is denoted by \(P \mid Q\text{,}\) where the symbol \(\mid\) is called the Scheffer stroke.
The NOR-gate is the negation of an OR-gate, and is denoted by \(P \downarrow Q\text{,}\) where \(\downarrow\) is called the Pierce arrow.
Subsection 10.2.6 Other Possible Combinations
With 2 inputs \(P\) and \(Q\text{,}\) the number of possible output patterns of 4 digits is \(2^4 = 16\text{.}\)