A combinational circuit can be constructed using solid-state devices, called gates, which are capable of switching voltage levels (bits). The output of a combinational circuit is uniquely defined for every combination of inputs. Circuits for which the output is a function, not only of the inputs, but also of the state of the system, are called sequential circuits.
An AND gate receives input x and y, where x and y are bits, and produces output 1 if x and y are both 1, otherwise 0. An OR gate receives input x and y, where x and y are bits, and produces output 0 if x and y are both 0, and 1 otherwise. A NOT gate, which is an inverter, receives input x, where x is a bit, and produces output 1 if x 0, and 0 is x is 1. A logic table of a combinational circuit lists all possible inputs together with the resulting outputs. Boolean expressions in the symbols
x1,…,xn are defined recursively as follows. 0, 1, x1,…,xn are Boolean expressions. A literal is the symbol x that appears in a Boolean expression.
A Boolean algebra consists of a set S containing distinct elements 0 and 1, binary operators + and ∙, and a unary operator ’ on S satisfying the associative, commutative, distributive, identity, and complement laws. A Boolean algebra also has several additional properties such as: Idempotent laws, Bound laws, Absorption laws, Involution laws, 0 and 1 laws, De Morgan laws. The dual of a Boolean expression is obtained by replacing 0 by 1, 1 by 0, + by ∙, and ∙ by +. The dual of a theorem about Boolean algebra is also a theorem.
Functions that can be represented by Boolean expressions are called Boolean functions. A minterm is a Boolean expression of the form y1 /\ y2 /\ …/\ yn, where each yi is either xi or ~xi.
A maxterm is a Boolean expression of the form y1 \/ y2 \/ … \/ yn, where each yi is either xi or
~xi. The exclusive-OR of x1 and x2 is 0 if x1 = x2, and 1 otherwise. A NAND gate receives input x and y, where x and y are bits, and produces output 0 if x and y are both 1, and 1 otherwise.
APPLICATIONS
1. Boolean algebra has many practical
applications in the physical sciences, in electric-circuit theory and
particularly in the field of computers. As an example of an application of
Boolean algebra in electrical-circuit theory, let p and q denote two
propositions, that is, declarative sentences that are either true or false but
not both. If each of the propositions p and q is associated with a switch that
will be closed if the proposition is true, and open if the proposition is
false, then the statement p Ù q may be represented by
connecting the switches in series:
URL: http://www.fwkc.com/encyclopedia/low/articles/b/b003002030f.html
2. Combinatorial circuits are used almost
every modern electronic such as parallel computation.
http://www.cs.brown.edu/people/jes/book/BOOK/node13.html
QUESTIONS
1. What is the smallest number of gates required of design a traffic light system?
2. What type of devices were used before the development of solid-state devices?