Greenwood press

136
SYMBOLIC LOGIC
(p AND q)
p
q
NOT p
p AND q
p OR q
OR (NOT q)
True
True
False
True
True
True
True
False
False
False
True
True
False
True
True
False
True
False
False
False
True
False
False
True
Truth tables from Microsoft Excel. 

---

Each of these has a representation in an electrical circuit. The diagram below
is a circuit showing two ON–OFF switches p and q. The circuits pass through
AND, OR, and NOT connectors that act on the current as though it were a logic
statement, with ON represented by TRUE, and OFF by FALSE. When will the
light bulb be on? The logical expression corresponding to the circuit is in the last
column of the spreadsheet in the previous table. The light is off when p is FALSE
(OFF) and q is TRUE (ON). All other situations result in the light being ON.
Two Boolean expressions that yield the same truth tables are equivalent.
When complex circuits are expressed as Boolean algebra statements, the rules of
logic can be used to simplify the circuit to one that is logically equivalent. The
result is lower cost. Some circuits are used so frequently that they are designed
as “new” Boolean operations. One of DeMorgan’s laws is that (NOT p) OR
(NOT q) is equivalent to NOT(p AND q). The first form would require a circuit
with three logic switches. The second requires only two. The result is usually
combined in a switch called a NAND switch. There is also a NOR switch that
computes NOT(p OR q).
Computers represent numbers in binary form, whereby the numbers 0, 1, 2, 3,
4, 5, 6 look like 0, 1, 10, 11, 100, 101. The digits in a base 2 number can be stored
as a sequence of memory positions (bits) that are on (1) or off (0). Addition rules
for three cases of digit pairs are easy: 0 + 0 = 0, 0 + 1 = 1, 1 + 0 = 1. The third
case requires a “carry”: 1 + 1 = 10. Circuits called “half-adders” perform the addi-
tion of two bits to produce a sum bit and a carry bit. The addition of multidigit
numbers requires many half-adders.
Boolean operators are the fundamental connectors in written commands that
perform searches on the Internet or in computer-based library card-catalogs.
Inquiries on such databases are called “Boolean searches.” The set operations
of union and intersection are used in place of OR and AND, respectively, in set
theory.
The example of the light circuit assumes that electricity flows through a cir-
cuit instantaneously. Circuits that represent sequential firing of switches require
that the algebra include a parameter for time. Although this complicates the oper-
ations, a time parameter makes the Boolean operators effective for describing
neural nets in the brain and spinal cord, as well as simplifying computer circuits
that require timed pulses of electricity.
Boole suggested that the truth values of 1 and 0 could be extended to proba-
bilities of a statement being correct. In the late 1960s his idea was formalized in
the field called fuzzy logic. The algorithms for fuzzy logic related to the binary
logic shown here, but have been more successful in providing answers to prob-
lems that start with vague or contradictory information. Applications have in-