CSC401: Fundamentals of Computer Science - Digital Logic

The section introduces the objectives of understanding Boolean logic and digital circuits, and how complex computer systems are formed. The outline covers transistors, Boolean algebra, logic gates, digital components, and combinational circuits. Transistors are presented as the primary components of Integrated Circuits (ICs), acting as switches to implement logic functions like AND, OR, NOT, and higher-level structures such as adders and multiplexers. Processors contain millions of transistors, and Boolean algebra is the basis for their design, with transistors implementing the 0s and 1s of binary digital circuits.

Boolean algebra, developed by George Boole, is a mathematical system for manipulating variables with two values ('true'/'false' or 'on'/'off', 1/0). Boolean expressions are formed using operators like AND, OR, and NOT, each described by a truth table. The AND operator (Boolean product) is true only if both inputs are true, while the INCLUSIVE OR operator (Boolean sum) is true if any input is true. The NOT operator inverts the input value. The EXCLUSIVE-OR (XOR) operator is true if either input is true but not both, and can be derived from INCLUSIVE-OR, AND, and NOT.

A Boolean function includes at least one variable, one operator, and one input from {0,1}, producing an output also from {0,1}. The binary numbering system is ideal for digital systems. Truth tables are used to evaluate Boolean functions, with a defined order of precedence for operators (NOT highest, then AND, then OR). Simplifying Boolean functions is crucial for building smaller, cheaper, faster, and more power-efficient circuits. This simplification is achieved through Boolean identities, which have both AND (product) and OR (sum) forms, and include intuitive, algebraic, and set theory-related laws. DeMorgan's law is presented as a method for finding the complement of a Boolean function, extending to multiple variables by complementing each variable and switching ANDs to ORs, and vice versa.

Because there are many ways to express logically equivalent Boolean functions, designers use standardized or canonical forms, which have identical truth tables. Two primary canonical forms exist: sum-of-products and product-of-sums. In sum-of-products, ANDed variables are ORed together. In product-of-sums, ORed variables are ANDed together. The article details how to convert a function to sum-of-products form using its truth table, focusing on the variable values that make the function true, and then ORing these groups together.

Boolean functions are implemented in digital computer circuits called gates, which are electronic devices producing results based on input values. Gates, though consisting of transistors, are viewed as single units by designers. The simplest gates are AND, OR, and NOT, directly corresponding to their Boolean operations. The exclusive OR (XOR) gate is also important, with its output being true only when inputs differ. NAND and NOR gates are highlighted as 'universal gates' because they are inexpensive to manufacture and any Boolean function can be constructed using only one of these types. Gates can have multiple inputs and sometimes provide a complementary output.

The article explains how combinations of gates implement Boolean functions, leading to simpler circuits through Boolean expression simplification. Combinational logic circuits produce a specified output almost instantly when inputs are applied. An example is the half-adder, which sums two bits. Its truth table shows that the sum can be found using the XOR operation and the carry using the AND operation. This concept is extended to a full adder, which processes a carry-in bit, with its truth table and circuit design outlined. Full adders can be connected in series to form ripple-carry adders, though modern systems use more efficient designs.

Decoders are introduced as another crucial type of combinational circuit, useful for selecting memory locations based on binary input. An n-input address decoder can select any of 2^n locations. A block diagram and an internal view of a 2-to-4 decoder are provided. Multiplexers are described as the opposite of decoders, selecting a single output from several inputs based on control lines. To select among n inputs, log2n control lines are needed. A block diagram and an internal view of a 4-to-1 multiplexer are shown. Finally, a shifter circuit is presented, demonstrating how it moves bits of a nibble left or right.