620
Boolean Algebra and Computer Logic
structures represent the underlying sameness in situations that may appear outwardly different.
It appears reasonable to abstract the common properties (tautological equivalences and set identities) for propositional wffs and set theory. Thus we will soon
define a mathematical structure called a Boolean algebra that incorporates these
properties. First, however, we note that modeling or abstracting is not an entirely
new idea to us.
1. We used predicate logic to model reasoning and formally defined an interpretation as a specific instance of predicate logic (Section 1.3).
2. We defined the abstract ideas of partial ordering and equivalence relation,
and considered a number of specific instances that could be modeled as
posets or sets on which an equivalence relation is defined (Section 5.1).
3. We noted that graph and tree structures can model a great variety of instances (Sections 6.1 and 6.2).
Boolean algebra is just another model or abstraction for which we already have
two instances.
Definition and Properties
Let us characterize formally the similarities between propositional logic and set
theory. In each case we are talking about items from a set: a set of wffs or a set
of subsets of a set S. In each case we have two binary operations and one unary
operation on the members of the set: disjunction/conjunction/negation or union/
intersection/complementation. In each case there are two distinguished elements
of the set: 0/1 or [∙S. Finally, there are the 10 properties that hold in each case.
Whenever all these features are present, we say that we have a Boolean algebra.
Definition BooLeAn ALgeBrA
A boolean algebra is a set B on which are defined two binary operations + and #
and one unary operation ′ and in which there are two distinct elements 0 and 1
such that the following properties hold for all x, y, z [ B:
1a. x + y = y + x
1b. x # y = y # x
(commutative properties)
2a. (x + y) + z =
2b. (x # y) # z =
(associative properties)
x + ( y + z)
x # ( y # z)
3a. x + ( y # z) =
3b. x # ( y + z) =
(distributive properties)
(x + y) # (x + z)
(x # y) + (x # z)
4a. x + 0 = x
4b. x # 1 = x
(identity properties)
5a. x + x′ = 1
5b. x # x′ = 0
(complement properties)
What, then, is the Boolean algebra structure? It is a formalization that abstracts, or models, the two cases we have considered (and perhaps others as well).
There is a subtle philosophical distinction between the formalization itself, the
idea of the Boolean algebra structure, and any instance of the formalization, such
as these two cases. Nevertheless, we will often use the term Boolean algebra to
describe both the idea and its occurrences. This usage should not be confusing.
We often have a mental idea (“chair,” for example), and whenever we encounter a
Boolean Algebra and Computer Logic
structures represent the underlying sameness in situations that may appear outwardly different.
It appears reasonable to abstract the common properties (tautological equivalences and set identities) for propositional wffs and set theory. Thus we will soon
define a mathematical structure called a Boolean algebra that incorporates these
properties. First, however, we note that modeling or abstracting is not an entirely
new idea to us.
1. We used predicate logic to model reasoning and formally defined an interpretation as a specific instance of predicate logic (Section 1.3).
2. We defined the abstract ideas of partial ordering and equivalence relation,
and considered a number of specific instances that could be modeled as
posets or sets on which an equivalence relation is defined (Section 5.1).
3. We noted that graph and tree structures can model a great variety of instances (Sections 6.1 and 6.2).
Boolean algebra is just another model or abstraction for which we already have
two instances.
Definition and Properties
Let us characterize formally the similarities between propositional logic and set
theory. In each case we are talking about items from a set: a set of wffs or a set
of subsets of a set S. In each case we have two binary operations and one unary
operation on the members of the set: disjunction/conjunction/negation or union/
intersection/complementation. In each case there are two distinguished elements
of the set: 0/1 or [∙S. Finally, there are the 10 properties that hold in each case.
Whenever all these features are present, we say that we have a Boolean algebra.
Definition BooLeAn ALgeBrA
A boolean algebra is a set B on which are defined two binary operations + and #
and one unary operation ′ and in which there are two distinct elements 0 and 1
such that the following properties hold for all x, y, z [ B:
1a. x + y = y + x
1b. x # y = y # x
(commutative properties)
2a. (x + y) + z =
2b. (x # y) # z =
(associative properties)
x + ( y + z)
x # ( y # z)
3a. x + ( y # z) =
3b. x # ( y + z) =
(distributive properties)
(x + y) # (x + z)
(x # y) + (x # z)
4a. x + 0 = x
4b. x # 1 = x
(identity properties)
5a. x + x′ = 1
5b. x # x′ = 0
(complement properties)
What, then, is the Boolean algebra structure? It is a formalization that abstracts, or models, the two cases we have considered (and perhaps others as well).
There is a subtle philosophical distinction between the formalization itself, the
idea of the Boolean algebra structure, and any instance of the formalization, such
as these two cases. Nevertheless, we will often use the term Boolean algebra to
describe both the idea and its occurrences. This usage should not be confusing.
We often have a mental idea (“chair,” for example), and whenever we encounter a