618
Boolean Algebra and Computer Logic
In Section 8.1 we define Boolean algebra as a mathematical model of both
propositional logic and set theory. The definition requires every Boolean algebra
to have certain properties, from which many additional properties can be derived.
This section also discusses what it means for two instances of a Boolean algebra
to be isomorphic.
Section 8.2 establishes a relationship between the Boolean algebra structure
and the wiring diagrams for the electronic circuits in computers, calculators, industrial control devices, telephone systems, and so forth. Indeed, we will see that
truth functions, expressions made up of variables and the operations of Boolean
algebra, and these wiring diagrams are all related. As a result, we can effectively
pass from one formulation to another and still preserve characteristic behavior
with respect to truth values. We will also find that we can simplify wiring diagrams by using properties of Boolean algebras. In Section 8.3 we will look at two
other procedures for simplifying wiring diagrams.
S e c t i o n 8 . 1 Boolean algeBr a StruCture
Let us revisit the wffs of propositional logic and associate with them a certain
type of function. Suppose a propositional wff P has n statement letters. Then each
row of the truth table for that wff associates a value of T or F with an n-tuple of
T–F values. The entire truth table defines a function f such that f: 5T, F6
n S 5T, F6.
The function associated with a tautology maps 5T, F6
n S 5T6, and the function
associated with a contradiction maps 5T, F6
n S 5F6.
example 1
We’ve seen this idea before. From Example 31 in Chapter 5, the function
f: 5T, F6
2 S 5T, F6 for the wff A ~ B′ is given by the following truth table.
A
B
B∙
A ~ B′
T
T
F
T
T
F
T
T
F
T
F
F
F
F
T
T
Here f (T, F) = T and f (F, T) = F.
Suppose we agree, for any propositional wff P with n statement letters, to let
the symbol P denote not only the wff but also the corresponding function defined
by the truth table. If P and Q are equivalent wffs, then they have the same truth
tables and therefore define the same function. Then we can write P = Q rather
than P 3 Q. This simply confirms that a given function has multiple names, although a given wff defines a unique function.
With this agreement, the short list of tautological equivalences from Section
1.1 can be written as follows, where ~ and ` denote disjunction and conjunction, respectively, A′denotes the negation of a statement A, 0 stands for any contradiction, and 1 stands for any tautology:
Boolean Algebra and Computer Logic
In Section 8.1 we define Boolean algebra as a mathematical model of both
propositional logic and set theory. The definition requires every Boolean algebra
to have certain properties, from which many additional properties can be derived.
This section also discusses what it means for two instances of a Boolean algebra
to be isomorphic.
Section 8.2 establishes a relationship between the Boolean algebra structure
and the wiring diagrams for the electronic circuits in computers, calculators, industrial control devices, telephone systems, and so forth. Indeed, we will see that
truth functions, expressions made up of variables and the operations of Boolean
algebra, and these wiring diagrams are all related. As a result, we can effectively
pass from one formulation to another and still preserve characteristic behavior
with respect to truth values. We will also find that we can simplify wiring diagrams by using properties of Boolean algebras. In Section 8.3 we will look at two
other procedures for simplifying wiring diagrams.
S e c t i o n 8 . 1 Boolean algeBr a StruCture
Let us revisit the wffs of propositional logic and associate with them a certain
type of function. Suppose a propositional wff P has n statement letters. Then each
row of the truth table for that wff associates a value of T or F with an n-tuple of
T–F values. The entire truth table defines a function f such that f: 5T, F6
n S 5T, F6.
The function associated with a tautology maps 5T, F6
n S 5T6, and the function
associated with a contradiction maps 5T, F6
n S 5F6.
example 1
We’ve seen this idea before. From Example 31 in Chapter 5, the function
f: 5T, F6
2 S 5T, F6 for the wff A ~ B′ is given by the following truth table.
A
B
B∙
A ~ B′
T
T
F
T
T
F
T
T
F
T
F
F
F
F
T
T
Here f (T, F) = T and f (F, T) = F.
Suppose we agree, for any propositional wff P with n statement letters, to let
the symbol P denote not only the wff but also the corresponding function defined
by the truth table. If P and Q are equivalent wffs, then they have the same truth
tables and therefore define the same function. Then we can write P = Q rather
than P 3 Q. This simply confirms that a given function has multiple names, although a given wff defines a unique function.
With this agreement, the short list of tautological equivalences from Section
1.1 can be written as follows, where ~ and ` denote disjunction and conjunction, respectively, A′denotes the negation of a statement A, 0 stands for any contradiction, and 1 stands for any tautology: