ic
Section 8.1 Boolean Algebra Structure
619
1a. A ~ B = B ~ A
lb. A ` B = B ` A
(commutative properties)
2a. (A ~ B) ~ C =
2b. (A ` B) ` C =
(associative properties)
A ~ (B ~ C )
A ` (B ` C )
3a. A ~ (B ` C ) =
3b. A ` (B ~ C ) =
(distributive properties)
(A ~ B) ` (A ~ C )
(A ` B) ~ (A ` C )
4a. A ~ 0 = A
4b. A ` 1 = A
(identity properties)
5a. A ~ A′ = 1
5b. A ` A′ = 0
(complement properties)
Switching gears a bit, in Section 4.1 we studied set identities among the subsets of a set S (the elements of `(S )). We found the following list of set identities,
where c and d denote the union and intersection of sets, respectively, A′ is the
complement of a set A, and [ is the empty set:
1a. A c B = B c A
lb. A d B = B d A
(commutative properties)
2a. (A c B) c C =
2b. (A d B) d C =
(associative properties)
A c (B c C)
A d (B d C )
3a. A c (B d C ) =
3b. A d (B c C ) =
(distributive properties)
(A c B) d ( A c C )
(A d B) c (A d C )
4a. A c [ = A
4b. A d S = A
(identity properties)
5a. A c A′ = S
5b. A d A′ = [
(complement properties)
These two lists of properties are similar. The disjunction of statements and the
union of sets seem to play the same roles in their respective environments. So do
the conjunction of statements and the intersection of sets. A contradiction seems
to correspond to the empty set and a tautology to S. What should we make of this
resemblance?
Models or Abstractions
We seem to have found two different examples—propositional logic and set
theory—that share some common properties. One of the hallmarks of scientific
thought is to look for patterns or similarities among various observed phenomena.
Are these similarities manifestations of some underlying general principle? Can
the principle itself be identified and studied? Could this research shed light on the
behavior of various instances of this principle? Sometimes, as seems to be the
case with propositional logic and set theory, similar mathematical properties or
behavior can be seen in different contexts. A mathematical structure is a formal
model that serves to embody or explain this commonality, just as in physics the
law of gravity is a formal model of why apples fall, the ocean has tides, and the
planets revolve around the sun.
Mathematical principles are models or abstractions intended to capture properties that may be common to different instances or manifestations. These principles are sometimes expressed as mathematical structures—abstract sets of objects,
together with operations on or relationships among those objects that obey certain
rules. (This concept may give you a clue about why this book is titled as it is.)
We can liken a mathematical structure to a human skeleton. We can think of
the skeleton as the basic structure of the human body. People may be thin or fat,
short or tall, black or white, and so on, but stripped down to skeletons they all look
pretty much alike. Although the outward appearances differ, the inward structure,
the shape and arrangement of the bones, is the same. Similarly, mathematical
Section 8.1 Boolean Algebra Structure
619
1a. A ~ B = B ~ A
lb. A ` B = B ` A
(commutative properties)
2a. (A ~ B) ~ C =
2b. (A ` B) ` C =
(associative properties)
A ~ (B ~ C )
A ` (B ` C )
3a. A ~ (B ` C ) =
3b. A ` (B ~ C ) =
(distributive properties)
(A ~ B) ` (A ~ C )
(A ` B) ~ (A ` C )
4a. A ~ 0 = A
4b. A ` 1 = A
(identity properties)
5a. A ~ A′ = 1
5b. A ` A′ = 0
(complement properties)
Switching gears a bit, in Section 4.1 we studied set identities among the subsets of a set S (the elements of `(S )). We found the following list of set identities,
where c and d denote the union and intersection of sets, respectively, A′ is the
complement of a set A, and [ is the empty set:
1a. A c B = B c A
lb. A d B = B d A
(commutative properties)
2a. (A c B) c C =
2b. (A d B) d C =
(associative properties)
A c (B c C)
A d (B d C )
3a. A c (B d C ) =
3b. A d (B c C ) =
(distributive properties)
(A c B) d ( A c C )
(A d B) c (A d C )
4a. A c [ = A
4b. A d S = A
(identity properties)
5a. A c A′ = S
5b. A d A′ = [
(complement properties)
These two lists of properties are similar. The disjunction of statements and the
union of sets seem to play the same roles in their respective environments. So do
the conjunction of statements and the intersection of sets. A contradiction seems
to correspond to the empty set and a tautology to S. What should we make of this
resemblance?
Models or Abstractions
We seem to have found two different examples—propositional logic and set
theory—that share some common properties. One of the hallmarks of scientific
thought is to look for patterns or similarities among various observed phenomena.
Are these similarities manifestations of some underlying general principle? Can
the principle itself be identified and studied? Could this research shed light on the
behavior of various instances of this principle? Sometimes, as seems to be the
case with propositional logic and set theory, similar mathematical properties or
behavior can be seen in different contexts. A mathematical structure is a formal
model that serves to embody or explain this commonality, just as in physics the
law of gravity is a formal model of why apples fall, the ocean has tides, and the
planets revolve around the sun.
Mathematical principles are models or abstractions intended to capture properties that may be common to different instances or manifestations. These principles are sometimes expressed as mathematical structures—abstract sets of objects,
together with operations on or relationships among those objects that obey certain
rules. (This concept may give you a clue about why this book is titled as it is.)
We can liken a mathematical structure to a human skeleton. We can think of
the skeleton as the basic structure of the human body. People may be thin or fat,
short or tall, black or white, and so on, but stripped down to skeletons they all look
pretty much alike. Although the outward appearances differ, the inward structure,
the shape and arrangement of the bones, is the same. Similarly, mathematical