. 1
( 13)



>>

MODERN ALGEBRA
WITH APPLICATIONS
PURE AND APPLIED MATHEMATICS

A Wiley-Interscience Series of Texts, Monograph, and Tracts

Founded by RICHARD COURANT
Editors: MYRON B. ALLEN III, DAVID A. COX, PETER LAX
Editors Emeriti: PETER HILTON, HARRY HOCHSTADT, JOHN TOLAND

A complete list of the titles in this series appears at the end of this volume.
MODERN ALGEBRA
WITH APPLICATIONS
Second Edition



WILLIAM J. GILBERT
University of Waterloo
Department of Pure Mathematics
Waterloo, Ontario, Canada

W. KEITH NICHOLSON
University of Calgary
Department of Mathematics and Statistics
Calgary, Alberta, Canada




A JOHN WILEY & SONS, INC., PUBLICATION
Cover: Still image from the applet KaleidoHedron, Copyright ™ 2000 by Greg Egan, from his
website http://www.netspace.net.au/∼gregegan/. The pattern has the symmetry of the icosahedral
group.

Copyright ™ 2004 by John Wiley & Sons, Inc. All rights reserved.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey.
Published simultaneously in Canada.

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any
form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise,
except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without
either the prior written permission of the Publisher, or authorization through payment of the
appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers,
MA 01923, 978-750-8400, fax 978-750-4470, or on the web at www.copyright.com. Requests to
the Publisher for permission should be addressed to the Permissions Department, John Wiley &
Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, e-mail:
permreq@wiley.com.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best
efforts in preparing this book, they make no representations or warranties with respect to the
accuracy or completeness of the contents of this book and speci¬cally disclaim any implied
warranties of merchantability or ¬tness for a particular purpose. No warranty may be created or
extended by sales representatives or written sales materials. The advice and strategies contained
herein may not be suitable for your situation. You should consult with a professional where
appropriate. Neither the publisher nor author shall be liable for any loss of pro¬t or any other
commercial damages, including but not limited to special, incidental, consequential, or other
damages.

For general information on our other products and services please contact our Customer Care
Department within the U.S. at 877-762-2974, outside the U.S. at 317-572-3993 or
fax 317-572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in
print, however, may not be available in electronic format.

Library of Congress Cataloging-in-Publication Data:

Gilbert, William J., 1941“
Modern algebra with applications / William J. Gilbert, W. Keith Nicholson.”2nd ed.
p. cm.”(Pure and applied mathematics)
Includes bibliographical references and index.
ISBN 0-471-41451-4 (cloth)
1. Algebra, Abstract. I. Nicholson, W. Keith. II. Title. III. Pure and applied
mathematics (John Wiley & Sons : Unnumbered)

QA162.G53 2003
512”dc21
2003049734


Printed in the United States of America.

10 9 8 7 6 5 4 3 2 1
CONTENTS


Preface to the First Edition ix

Preface to the Second Edition xiii

List of Symbols xv

1 Introduction 1
Classical Algebra, 1
Modern Algebra, 2
Binary Operations, 2
Algebraic Structures, 4
Extending Number Systems, 5

2 Boolean Algebras 7
Algebra of Sets, 7
Number of Elements in a Set, 11
Boolean Algebras, 13
Propositional Logic, 16
Switching Circuits, 19
Divisors, 21
Posets and Lattices, 23
Normal Forms and Simpli¬cation of Circuits, 26
Transistor Gates, 36
Representation Theorem, 39
Exercises, 41

3 Groups 47
Groups and Symmetries, 48
Subgroups, 54



v
vi CONTENTS


Cyclic Groups and Dihedral Groups, 56
Morphisms, 60
Permutation Groups, 63
Even and Odd Permutations, 67
Cayley™s Representation Theorem, 71
Exercises, 71

4 Quotient Groups 76
Equivalence Relations, 76
Cosets and Lagrange™s Theorem, 78
Normal Subgroups and Quotient Groups, 82
Morphism Theorem, 86
Direct Products, 91
Groups of Low Order, 94
Action of a Group on a Set, 96
Exercises, 99

5 Symmetry Groups in Three Dimensions 104
Translations and the Euclidean Group, 104
Matrix Groups, 107
Finite Groups in Two Dimensions, 109
Proper Rotations of Regular Solids, 111
Finite Rotation Groups in Three Dimensions, 116
Crystallographic Groups, 120
Exercises, 121

6 P´ lya“Burnside Method of Enumeration
o 124
Burnside™s Theorem, 124
Necklace Problems, 126
Coloring Polyhedra, 128
Counting Switching Circuits, 130
Exercises, 134

7 Monoids and Machines 137
Monoids and Semigroups, 137
Finite-State Machines, 142
Quotient Monoids and the Monoid of a Machine, 144
Exercises, 149

8 Rings and Fields 155
Rings, 155
Integral Domains and Fields, 159
Subrings and Morphisms of Rings, 161
CONTENTS vii


New Rings from Old, 164
Field of Fractions, 170
Convolution Fractions, 172
Exercises, 176

9 Polynomial and Euclidean Rings 180
Euclidean Rings, 180
Euclidean Algorithm, 184
Unique Factorization, 187
Factoring Real and Complex Polynomials, 190
Factoring Rational and Integral Polynomials, 192
Factoring Polynomials over Finite Fields, 195
Linear Congruences and the Chinese Remainder Theorem, 197
Exercises, 201

10 Quotient Rings 204
Ideals and Quotient Rings, 204
Computations in Quotient Rings, 207
Morphism Theorem, 209
Quotient Polynomial Rings That Are Fields, 210
Exercises, 214

11 Field Extensions 218
Field Extensions, 218
Algebraic Numbers, 221
Galois Fields, 225
Primitive Elements, 228
Exercises, 232

12 Latin Squares 236
Latin Squares, 236
Orthogonal Latin Squares, 238
Finite Geometries, 242
Magic Squares, 245
Exercises, 249

13 Geometrical Constructions 251
Constructible Numbers, 251
Duplicating a Cube, 256
Trisecting an Angle, 257
Squaring the Circle, 259
Constructing Regular Polygons, 259
viii CONTENTS


Nonconstructible Number of Degree 4, 260
Exercises, 262

14 Error-Correcting Codes 264
The Coding Problem, 266
Simple Codes, 267
Polynomial Representation, 270
Matrix Representation, 276
Error Correcting and Decoding, 280
BCH Codes, 284
Exercises, 288

Appendix 1: Proofs 293

Appendix 2: Integers 296

Bibliography and References 306

Answers to Odd-Numbered Exercises 309

Index 323
PREFACE TO THE
FIRST EDITION


Until recently the applications of modern algebra were mainly con¬ned to other
branches of mathematics. However, the importance of modern algebra and dis-
crete structures to many areas of science and technology is now growing rapidly.
It is being used extensively in computing science, physics, chemistry, and data
communication as well as in new areas of mathematics such as combinatorics.
We believe that the fundamentals of these applications can now be taught at the
junior level. This book therefore constitutes a one-year course in modern algebra
for those students who have been exposed to some linear algebra. It contains
the essentials of a ¬rst course in modern algebra together with a wide variety of
applications.
Modern algebra is usually taught from the point of view of its intrinsic inter-
est, and students are told that applications will appear in later courses. Many
students lose interest when they do not see the relevance of the subject and often
become skeptical of the perennial explanation that the material will be used later.
However, we believe that by providing interesting and nontrivial applications as
we proceed, the student will better appreciate and understand the subject.
We cover all the group, ring, and ¬eld theory that is usually contained in a
standard modern algebra course; the exact sections containing this material are
indicated in the table of contents. We stop short of the Sylow theorems and Galois
theory. These topics could only be touched on in a ¬rst course, and we feel that
more time should be spent on them if they are to be appreciated.
In Chapter 2 we discuss boolean algebras and their application to switching
circuits. These provide a good example of algebraic structures whose elements
are nonnumerical. However, many instructors may prefer to postpone or omit this
chapter and start with the group theory in Chapters 3 and 4. Groups are viewed
as describing symmetries in nature and in mathematics. In keeping with this view,
the rotation groups of the regular solids are investigated in Chapter 5. This mate-
rial provides a good starting point for students interested in applying group theory
to physics and chemistry. Chapter 6 introduces the P´ lya“Burnside method of
o
enumerating equivalence classes of sets of symmetries and provides a very prac-
tical application of group theory to combinatorics. Monoids are becoming more
ix
x PREFACE TO THE FIRST EDITION


important algebraic structures today; these are discussed in Chapter 7 and are
applied to ¬nite-state machines.
The ring and ¬eld theory is covered in Chapters 8“11. This theory is motivated
by the desire to extend the familiar number systems to obtain the Galois ¬elds and
to discover the structure of various sub¬elds of the real and complex numbers.
Groups are used in Chapter 12 to construct latin squares, whereas Galois ¬elds are
used to construct orthogonal latin squares. These can be used to design statistical
experiments. We also indicate the close relationship between orthogonal latin
squares and ¬nite geometries. In Chapter 13 ¬eld extensions are used to show
that some famous geometrical constructions, such as the trisection of an angle
and the squaring of the circle, are impossible to perform using only a straightedge
and compass. Finally, Chapter 14 gives an introduction to coding theory using
polynomial and matrix techniques.
We do not give exhaustive treatments of any of the applications. We only go so
far as to give the ¬‚avor without becoming too involved in technical complications.



1 Introduction


2 3 8
Rings
Boolean Groups and
Algebras
Fields

9
4 7 Polynomial
Monoids
Quotient
and Euclidean
and
Groups
Rings
Machines


5
6 10
Pólya“Burnside Symmetry Quotient
Method of Groups in Three Rings
Enumeration Dimensions

11
Field
Extensions



12 13
Latin Geometrical
Squares Constructions



14
Error-Correcting
Codes

Figure P.1. Structure of the chapters.
PREFACE TO THE FIRST EDITION xi


The interested reader may delve further into any topic by consulting the books
in the bibliography.
It is important to realize that the study of these applications is not the only
reason for learning modern algebra. These examples illustrate the varied uses to
which algebra has been put in the past, and it is extremely likely that many more
different applications will be found in the future.
One cannot understand mathematics without doing numerous examples. There
are a total of over 600 exercises of varying dif¬culty, at the ends of chapters.
Answers to the odd-numbered exercises are given at the back of the book.
Figure P.1 illustrates the interdependence of the chapters. A solid line indicates
a necessary prerequisite for the whole chapter, and a dashed line indicates a
prerequisite for one section of the chapter. Since the book contains more than
suf¬cient material for a two-term course, various sections or chapters may be
omitted. The choice of topics will depend on the interests of the students and the
instructor. However, to preserve the essence of the book, the instructor should be
careful not to devote most of the course to the theory, but should leave suf¬cient
time for the applications to be appreciated.
I would like to thank all my students and colleagues at the University of
ˇ
Waterloo, especially Harry Davis, D. Z. Djokovi´ , Denis Higgs, and Keith Rowe,
c
who offered helpful suggestions during the various stages of the manuscript. I am
very grateful to Michael Boyle, Ian McGee, Juris Step´ans, and Jack Weiner
r
for their help in preparing and proofreading the preliminary versions and the
¬nal draft. Finally, I would like to thank Sue Cooper, Annemarie DeBrusk, Lois
Graham, and Denise Stack for their excellent typing of the different drafts, and
Nadia Bahar for tracing all the ¬gures.

Waterloo, Ontario, Canada WILLIAM J. GILBERT
April 1976
PREFACE TO THE
SECOND EDITION


In addition to improvements in exposition, the second edition contains the fol-
lowing new items:

New shorter proof of the parity theorem using the action of the symmetric
ž
group on the discriminant polynomial
New proof that linear isometries are linear, and more detail about their
ž
relation to orthogonal matrices
Appendix on methods of proof for beginning students, including the def-
ž
inition of an implication, proof by contradiction, converses, and logical
equivalence
Appendix on basic number theory covering induction, greatest common divi-
ž
sors, least common multiples, and the prime factorization theorem
New material on the order of an element and cyclic groups
ž

More detail about the lattice of divisors of an integer
ž

New historical notes on Fermat™s last theorem, the classi¬cation theorem
ž
for ¬nite simple groups, ¬nite af¬ne planes, and more
More detail on set theory and composition of functions
ž

26 new exercises, 46 counting parts
ž

Updated symbols and notation
ž

Updated bibliography
ž


February 2003 WILLIAM J. GILBERT
W. KEITH NICHOLSON




xiii
LIST OF SYMBOLS


A Algebraic numbers, 233
Alternating group on n elements, 70
An
C Complex numbers, 4
C— Nonzero complex numbers, 48
Cyclic group of order n, 58
Cn
C[0, ∞) Continuous real valued functions on [0, ∞), 173
Dihedral group of order 2n, 58
Dn
Dn Divisors of n, 22
Hamming distance between u and v, 269
d(u, v)
deg Degree of a polynomial, 166
Identity element of a group or monoid, 48, 137
e
Identity element in the group G, 61
eG
E(n) Euclidean group in n dimensions, 104
Field, 4, 160
F
Switching functions of n variables, 28
Fn
Fixg Set of elements ¬xed under the action of g, 125
FM(A) Free monoid on A, 140
gcd(a, b) Greatest common divisor of a and b, 184, 299
GF(n) Galois ¬eld of order n, 227
GL(n, F ) General linear group of dimension n over F , 107
H Quaternions, 177
Identity matrix, 4
I
k — k identity matrix, 277
Ik
Imf Image of f , 87
Kerf Kernel of f , 86
lcm(a, b) Least common multiple of a and b, 184, 303
L(Rn , Rn ) Linear transformations from Rn to Rn , 163
n — n matrices with entries from R, 4, 166
Mn (R)
N Nonnegative integers, 55
NAND NOT-AND, 28, 36
NOR NOT-OR, 28, 36
O(n) Orthogonal group of dimension n, 105
Orb x Orbit of x, 97
xv
xvi LIST OF SYMBOLS


P Positive integers, 3
Power set of X, 8
P (X)
Q Rational numbers, 6
Q— Nonzero rational numbers, 48
Quaternion group, 73
Q
R Real numbers, 2
R— Nonzero real numbers, 48
R+ Positive real numbers, 5
Symmetric group of X, 50
S(X)
Symmetric group on n elements, 63
Sn
SO(n) Special orthogonal group of dimension n, 108
Stab x Stabilizer of x, 97
SU(n) Special unitary group of dimension n, 108
T(n) Translations in n dimensions, 104
U(n) Unitary group of dimension n, 108
Z Integers, 5
Zn Integers modulo n, 5, 78
Z— Integers modulo n coprime to n, 102
n
Dirac delta function, or remainder in general
δ(x)
division algorithm, 172, 181
Null sequence, 140
… Empty set, 7
Euler φ-function, 102
φ(n)
General binary operation or concatenation, 2, 140
* Convolution, 168, 173
Composition, 49
Ž
Symmetric difference, 9, 29
’ Difference, 9
§ Meet, 14
∨ Join, 14
⊆ Inclusion, 7
Less than or equal, 23
’ Implies, 17, 293
” If and only if, 18, 295

= Isomorphic, 60, 172
≡ mod n Congruent modulo n, 77
≡ mod H Congruent modulo H , 79
|X| Number of elements in X, 12, 56
|G : H | Index of H in G, 80
R— Invertible elements in the ring R, 188
Complement of a in a boolean algebra, 14, 28
a
a ’1 Inverse of a, 3, 48
Complement of the set A, 8
A
© Intersection of sets, 8
∪ Union of sets, 8
LIST OF SYMBOLS xvii


∈ Membership in a set, 7
Set difference, 9
A“B
||v|| Length of v in Rn , 105
v·w Inner product in Rn , 105
VT Transpose of the matrix V , 104
End of a proof or example, 9
(a) Ideal generated by a, 204
n-cycle, 64
(a1 a2 . . . an )
1 2...n
Permutation, 63
a1 a2 . . . an
n
Binomial coef¬cient n!/r!(n ’ r)!, 129
r
Smallest ¬eld containing F and a, 220
F (a)
Smallest ¬eld containing F and a1 , . . . , an , 220
F (a1 , . . . , an )
Code of length n with messages of length k, 266
(n, k)-code
Group or monoid, 5, 48, 137
(X, )
(R, +, ·) Ring, 156
(K, §, ∨, ) Boolean algebra, 14
[x] Equivalence class containing x, 77
[x]n Congruence class modulo n containing x, 100
Polynomials in x with coef¬cients from R, 167
R[x]
Formal power series in x with coef¬cients from R, 169
R[[x]]
R[x1 , . . . , xn ] Polynomials in x1 , . . . , xn with coef¬cients from R, 168
[K : F ] Degree of K over F , 219
XY Set of functions from Y to X, 138
RN Sequences of elements from R, 168
Sequence whose ith term is ai , 168
ai
G—H Direct product of G and H , 91
S—S Direct product of sets, 2
Quotient set, 77
S/E
Quotient group or set of right cosets, 83
G/H
Quotient ring, 206
R/I
a divides b, 21, 184, 299
a|b
l is parallel to m, 242
l//m
Ha Right coset of H containing a, 79
aH Left coset of H containing a, 82
I +r Coset of I containing r, 205
1
INTRODUCTION


Algebra can be de¬ned as the manipulation of symbols. Its history falls into two
distinct parts, with the dividing date being approximately 1800. The algebra done
before the nineteenth century is called classical algebra, whereas most of that
done later is called modern algebra or abstract algebra.


CLASSICAL ALGEBRA

The technique of introducing a symbol, such as x, to represent an unknown
number in solving problems was known to the ancient Greeks. This symbol could
be manipulated just like the arithmetic symbols until a solution was obtained.
Classical algebra can be characterized by the fact that each symbol always
stood for a number. This number could be integral, real, or complex. However,
in the seventeenth and eighteenth centuries, mathematicians were not quite sure
whether the square root of ’1 was a number. It was not until the nineteenth
century and the beginning of modern algebra that a satisfactory explanation of
the complex numbers was given.
The main goal of classical algebra was to use algebraic manipulation to solve
polynomial equations. Classical algebra succeeded in producing algorithms for
solving all polynomial equations in one variable of degree at most four. However,
it was shown by Niels Henrik Abel (1802“1829), by modern algebraic methods,
that it was not always possible to solve a polynomial equation of degree ¬ve
or higher in terms of nth roots. Classical algebra also developed methods for
dealing with linear equations containing several variables, but little was known
about the solution of nonlinear equations.
Classical algebra provided a powerful tool for tackling many scienti¬c prob-
lems, and it is still extremely important today. Perhaps the most useful math-
ematical tool in science, engineering, and the social sciences is the method of
solution of a system of linear equations together with all its allied linear algebra.


Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson
ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

1
2 1 INTRODUCTION


MODERN ALGEBRA

In the nineteenth century it was gradually realized that mathematical symbols did
not necessarily have to stand for numbers; in fact, it was not necessary that they
stand for anything at all! From this realization emerged what is now known as
modern algebra or abstract algebra.
For example, the symbols could be interpreted as symmetries of an object, as
the position of a switch, as an instruction to a machine, or as a way to design
a statistical experiment. The symbols could be manipulated using some of the
usual rules for numbers. For example, the polynomial 3x 2 + 2x ’ 1 could be
added to and multiplied by other polynomials without ever having to interpret
the symbol x as a number.
Modern algebra has two basic uses. The ¬rst is to describe patterns or sym-
metries that occur in nature and in mathematics. For example, it can describe
the different crystal formations in which certain chemical substances are found
and can be used to show the similarity between the logic of switching circuits
and the algebra of subsets of a set. The second basic use of modern algebra is
to extend the common number systems naturally to other useful systems.


BINARY OPERATIONS

The symbols that are to be manipulated are elements of some set, and the manipu-
lation is done by performing certain operations on elements of that set. Examples
of such operations are addition and multiplication on the set of real numbers.
As shown in Figure 1.1, we can visualize an operation as a “black box” with
various inputs coming from a set S and one output, which combines the inputs
in some speci¬ed way. If the black box has two inputs, the operation combines
two elements of the set to form a third. Such an operation is called a binary
operation. If there is only one input, the operation is called unary. An example
of a unary operation is ¬nding the reciprocal of a nonzero real number.
If S is a set, the direct product S — S consists of all ordered pairs (a, b)
with a, b ∈ S. Here the term ordered means that (a, b) = (a1 , b1 ) if and only if
a = a1 and b = b1 . For example, if we denote the set of all real numbers by R,
then R — R is the euclidean plane.
Using this terminology, a binary operation, , on a set S is really just a
particular function from S — S to S. We denote the image of the pair (a, b)



a
a—b c c′
b


Binary operation Unary operation

Figure 1.1
BINARY OPERATIONS 3


under this function by a b. In other words, the binary operation assigns to
any two elements a and b of S the element a b of S. We often refer to an
operation as being closed to emphasize that each element a b belongs to
the set S and not to a possibly larger set. Many symbols are used for binary
operations; the most common are +, ·, ’, Ž , ·, ∪, ©, §, and ∨.
A unary operation on S is just a function from S to S. The image of c under
a unary operation is usually denoted by a symbol such as c , c, c’1 , or (’c).
Let P = {1, 2, 3, . . .} be the set of positive integers. Addition and multipli-
cation are both binary operations on P, because, if x, y ∈ P, then x + y and
x · y ∈ P. However, subtraction is not a binary operation on P because, for
instance, 1 ’ 2 ∈ P. Other natural binary operations on P are exponentiation and
/
the greatest common divisor, since for any two positive integers x and y, x y and
gcd(x, y) are well-de¬ned elements of P.
Addition, multiplication, and subtraction are all binary operations on R because
x + y, x · y, and x ’ y are real numbers for every pair of real numbers x and y.
The symbol ’ stands for a binary operation when used in an expression such as
x ’ y, but it stands for the unary operation of taking the negative when used in
the expression ’x. Division is not a binary operation on R because division by
zero is unde¬ned. However, division is a binary operation on R ’ {0}, the set of
nonzero real numbers.
A binary operation on a ¬nite set can often be presented conveniently by
means of a table. For example, consider the set T = {a, b, c}, containing three
elements. A binary operation on T is de¬ned by Table 1.1. In this table, x y
is the element in row x and column y. For example, b c = b and c b = a.
One important binary operation is the composition of symmetries of a given
¬gure or object. Consider a square lying in a plane. The set S of symmetries
of this square is the set of mappings of the square to itself that preserve dis-
tances. Figure 1.2 illustrates the composition of two such symmetries to form a
third symmetry.
Most of the binary operations we use have one or more of the following
special properties. Let be a binary operation on a set S. This operation is called
associative if a (b c) = (a b) c for all a, b, c ∈ S. The operation is called
commutative if a b = b a for all a, b ∈ S. The element e ∈ S is said to be
an identity for if a e = e a = a for all a ∈ S.
If is a binary operation on S that has an identity e, then b is called the
if a b = b a = e. We usually denote the
inverse of a with respect to


TABLE 1.1. Binary Operation
on {a, b, c}
a b c
a b a a
b c a b
c c a b
4 1 INTRODUCTION


Square in its
original position

2 1 1 4 4 1
Flip about
Rotation
the vertical
through p/2
axis
3 4 2 3 3 2



Flip about a diagonal axis


Figure 1.2. Composition of symmetries of a square.



inverse of a by a ’1 ; however, if the operation is addition, the inverse is denoted
by ’a.
If and Ž are two binary operations on S, then Ž is said to be distributive over
if a Ž (b c) = (a Ž b) (a Ž c) and (b c) Ž a = (b Ž a) (c Ž a) for all a, b, c ∈
S.
Addition and multiplication are both associative and commutative operations
on the set R of real numbers. The identity for addition is 0, whereas the mul-
tiplicative identity is 1. Every real number, a, has an inverse under addition,
namely, its negative, ’a. Every nonzero real number a has a multiplicative
inverse, a ’1 . Furthermore, multiplication is distributive over addition because
a · (b + c) = (a · b) + (a · c) and (b + c) · a = (b · a) + (c · a); however, addi-
tion is not distributive over multiplication because a + (b · c) = (a + b) · (a + c)
in general.
Denote the set of n — n real matrices by Mn (R). Matrix multiplication is an
associative operation on Mn (R), but it is not commutative (unless n = 1). The
matrix I , whose (i, j )th entry is 1 if i = j and 0 otherwise, is the multiplicative
identity. Matrices with multiplicative inverses are called nonsingular.


ALGEBRAIC STRUCTURES

A set, together with one or more operations on the set, is called an algebraic
structure. The set is called the underlying set of the structure. Modern algebra
is the study of these structures; in later chapters, we examine various types of
algebraic structures. For example, a ¬eld is an algebraic structure consisting of
a set F together with two binary operations, usually denoted by + and ·, that
satisfy certain conditions. We denote such a structure by (F, +, ·).
In order to understand a particular structure, we usually begin by examining its
substructures. The underlying set of a substructure is a subset of the underlying
set of the structure, and the operations in both structures are the same. For
example, the set of complex numbers, C, contains the set of real numbers, R, as
a subset. The operations of addition and multiplication on C restrict to the same
operations on R, and therefore (R, +, ·) is a substructure of (C, +, ·).
EXTENDING NUMBER SYSTEMS 5


Two algebraic structures of a particular type may be compared by means of
structure-preserving functions called morphisms. This concept of morphism is
one of the fundamental notions of modern algebra. We encounter it among every
algebraic structure we consider.
More precisely, let (S, ) and (T , Ž ) be two algebraic structures consisting of
the sets S and T , together with the binary operations on S and Ž on T . Then a
function f : S ’ T is said to be a morphism from (S, ) to (T , Ž ) if for every
x, y ∈ S,
f (x y) = f (x) Ž f (y).

If the structures contain more than one operation, the morphism must preserve
all these operations. Furthermore, if the structures have identities, these must be
preserved, too.
As an example of a morphism, consider the set of all integers, Z, under the
operation of addition and the set of positive real numbers, R+ , under multiplica-
tion. The function f : Z ’ R+ de¬ned by f (x) = ex is a morphism from (Z, +)
to (R+ , ·). Multiplication of the exponentials ex and ey corresponds to addition
of their exponents x and y.
A vector space is an algebraic structure whose underlying set is a set of
vectors. Its operations consist of the binary operation of addition and, for each
scalar », a unary operation of multiplication by ». A function f : S ’ T , between
vector spaces, is a morphism if f (x + y) = f (x) + f (y) and f (»x) = »f (x) for
all vectors x and y in the domain S and all scalars ». Such a vector space
morphism is usually called a linear transformation.
A morphism preserves some, but not necessarily all, of the properties of the
domain structure. However, if a morphism between two structures is a bijective
function (that is, one-to-one and onto), it is called an isomorphism, and the
structures are called isomorphic. Isomorphic structures have identical properties,
and they are indistinguishable from an algebraic point of view. For example, two
vector spaces of the same ¬nite dimension over a ¬eld F are isomorphic.
One important method of constructing new algebraic structures from old ones
is by means of equivalence relations. If (S, ) is a structure consisting of the set
S with the binary operation on it, the equivalence relation ∼ on S is said to be
compatible with if, whenever a ∼ b and c ∼ d, it follows that a c ∼ b d.
Such a compatible equivalence relation allows us to construct a new structure
called the quotient structure, whose underlying set is the set of equivalence
classes. For example, the quotient structure of the integers, (Z, +, ·), under the
congruence relation modulo n, is the set of integers modulo n, (Zn , +, ·) (see
Appendix 2).


EXTENDING NUMBER SYSTEMS

In the words of Leopold Kronecker (1823“1891), “God created the natural num-
bers; everything else was man™s handiwork.” Starting with the set of natural
6 1 INTRODUCTION


numbers under addition and multiplication, we show how this can be extended
to other algebraic systems that satisfy properties not held by the natural numbers.
The integers (Z, +, ·) is the smallest system containing the natural numbers, in
which addition has an identity (the zero) and every element has an inverse under
addition (its negative). The integers have an identity under multiplication (the
element 1), but 1 and ’1 are the only elements with multiplicative inverses. A
standard construction will produce the ¬eld of fractions of the integers, which is
the rational number system (Q, +, ·), and we show that this is the smallest ¬eld
containing (Z, +, ·). We can now divide by nonzero elements in Q and solve
every linear equation of the form ax = b (a = 0). However, not all quadratic
equations have solutions in Q; for example, x 2 ’ 2 = 0 has no rational solution.
The next step is to extend the rationals to the real number system (R, +, ·).
The construction of the real numbers requires the use of nonalgebraic concepts
such as Dedekind cuts or Cauchy sequences, and we will not pursue this, being
content to assume that they have been constructed. Even though many polynomial
equations have real solutions, there are some, such as x 2 + 1 = 0, that do not.
We show how to extend the real number system by adjoining a root of x 2 + 1
to obtain the complex number system (C, +, ·). The complex number system
is really the end of the line, because Carl Friedrich Gauss (1777“1855), in his
doctoral thesis, proved that any nonconstant polynomial with real or complex
coef¬cients has a root in the complex numbers. This result is now known as the
fundamental theorem of algebra.
However, the classical number system can be generalized in a different way.
We can look for ¬elds that are not sub¬elds of (C, +, ·). An example of such a
¬eld is the system of integers modulo a prime p, (Zp , +, ·). All the usual oper-
ations of addition, subtraction, multiplication, and division by nonzero elements
can be performed in Zp . We show that these ¬elds can be extended and that
for each prime p and positive integer n, there is a ¬eld (GF(p n ), +, ·) with p n
elements. These ¬nite ¬elds are called Galois ¬elds after the French mathemati-
´
cian Evariste Galois. We use Galois ¬elds in the construction of orthogonal latin
squares and in coding theory.
2
BOOLEAN ALGEBRAS


A boolean algebra is a good example of a type of algebraic structure in which the
symbols usually represent nonnumerical objects. This algebra is modeled after
the algebra of subsets of a set under the binary operations of union and inter-
section and the unary operation of complementation. However, boolean algebra
has important applications to switching circuits, where each symbol represents a
particular electrical circuit or switch. The origin of boolean algebra dates back
to 1847, when the English mathematician George Boole (1815“1864) published
a slim volume entitled The Mathematical Analysis of Logic, which showed how
algebraic symbols could be applied to logic. The manipulation of logical propo-
sitions by means of boolean algebra is now called the propositional calculus.
At the end of this chapter, we show that any ¬nite boolean algebra is equivalent
to the algebra of subsets of a set; in other words, there is a boolean algebra
isomorphism between the two algebras.


ALGEBRA OF SETS

In this section, we develop some properties of the basic operations on sets. A set
is often referred to informally as a collection of objects called the elements of
the set. This is not a proper de¬nition”collection is just another word for set.
What is clear is that there are sets, and there is a notion of being an element
(or member) of a set. These fundamental ideas are the primitive concepts of
set theory and are left unde¬ned.— The fact that a is an element of a set X is
denoted a ∈ X. If every element of X is also an element of Y , we write X ⊆ Y
(equivalently, Y ⊇ X) and say that X is contained in Y , or that X is a subset
of Y . If X and Y have the same elements, we say that X and Y are equal sets
and write X = Y . Hence X = Y if and only if both X ⊆ Y and Y ⊆ X. The set
with no elements is called the empty set and is denoted as ˜.

Certain basic properties of sets must also be assumed (called the axioms of the theory), but it is
not our intention to go into this here.

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson
ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.

7
8 2 BOOLEAN ALGEBRAS


Let X be any set. The set of all subsets of X is called the power
set of X and is denoted by P (X). Hence P (X) = {A|A ⊆ X}. Thus if
X = {a, b}, then P (X) = {˜, {a}, {b}, X}. If X = {1, 2, 3}, then P (X) =
{˜, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, X}.
If A and B are subsets of a set X, their intersection A © B is de¬ned to be
the set of elements common to A and B, and their union A ∪ B is the set of
elements in A or B (or both). More formally,

A © B = {x|x ∈ A and x ∈ B} and A ∪ B = {x|x ∈ A or x ∈ B}.

The complement of A in X is A = {x|x ∈ X and x ∈ A} and is the set of
/
elements in X that are not in A. The shaded areas of the Venn diagrams in
Figure 2.1 illustrate these operations.
Union and intersection are both binary operations on the power set P (X),
whereas complementation is a unary operation on P (X). For example, with
X = {a, b}, the tables for the structures (P (X), ©), (P (X), ∪) and (P (X), ’ )
are given in Table 2.1, where we write A for {a} and B for {b}.

Proposition 2.1. The following are some of the more important relations involv-
ing the operations ©, ∪, and ’ , holding for all A, B, C ∈ P (X).

(i) A © (B © C) = (A © B) © C. (ii) A ∪ (B ∪ C) = (A ∪ B) ∪ C.
(iii) A © B = B © A. (iv) A ∪ B = B ∪ A.
(v) A © (B ∪ C) (vi) A ∪ (B © C)
= (A © B) ∪ (A © C). = (A ∪ B) © (A ∪ C).
(vii) A © X = A. (viii) A ∪ ˜ = A.
(ix) A © A = ˜. (x) A ∪ A = X.
(xi) A © ˜ = ˜. (xii) A ∪ X = X.
(xiii) A © (A ∪ B) = A. (xiv) A ∪ (A © B) = A.


X X X
A B A B A


A©B A∪B A

Figure 2.1. Venn diagrams.


TABLE 2.1. Intersection, Union, and Complements in P ({a, b})
© ∪
˜ ˜ Subset Complement
A B X A B X
˜ ˜ ˜ ˜ ˜ ˜ ˜ ˜
A B X X
˜ ˜
A A A A A A X X A B
˜ ˜
B B B B B X B X B A
˜ ˜
X A B X X X X X X X
ALGEBRA OF SETS 9


A © A = A. (xvi) A ∪ A = A.
(xv)
(A © B) = A ∪ B. (xviii) (A ∪ B) = A © B.
(xvii)
X = ˜. (xx) ˜ = X.
(xix)
A = A.
(xxi)

Proof. We shall prove relations (v) and (x) and leave the proofs of the others
to the reader.

(v) A © (B ∪ C) = {x|x ∈ A and x ∈ B ∪ C}
= {x|x ∈ A and (x ∈ B or x ∈ C)}
= {x|(x ∈ A and x ∈ B) or (x ∈ A and x ∈ C)}
= {x|x ∈ A © B or x ∈ A © C}
= (A © B) ∪ (A © C).

The Venn diagrams in Figure 2.2 illustrate this result.

(x) A ∪ A = {x|x ∈ A or x ∈ A}
= {x|x ∈ A or (x ∈ X and x ∈ A)}
/
= {x|(x ∈ X and x ∈ A) or (x ∈ X and x ∈ A)}, since A ⊆ X
/
= {x|x ∈ X and (x ∈ A or x ∈ A)}
/
= {x|x ∈ X}, since it is always true that x ∈ A or x ∈ A
/
= X.

Relations (i)“(iv), (vii), and (viii) show that © and ∪ are associative and
commutative operations on P (X) with identities X and ˜, respectively. The
only element with an inverse under © is its identity X, and the only element with
an inverse under ∪ is its identity ˜.
Note the duality between © and ∪. If these operations are interchanged in any
relation, the resulting relation is also true.
Another operation on P (X) is the difference of two subsets. It is de¬ned by

A ’ B = {x|x ∈ A and x ∈ B} = A © B.
/

Since this operation is neither associative nor commutative, we introduce another
operation A B, called the symmetric difference, illustrated in Figure 2.3,



B
A
B
A

C
C

A © (B ∪ C) (A © B) ∪ (A © C)

Figure 2.2. Venn diagrams illustrating a distributive law.
10 2 BOOLEAN ALGEBRAS


X X
B B
A A


A’B A∆B
Figure 2.3. Difference and symmetric difference of sets.


de¬ned by

A B = (A © B) ∪ (A © B) = (A ∪ B) ’ (A © B) = (A ’ B) ∪ (B ’ A).

The symmetric difference of A and B is the set of elements in A or B, but not
in both. This is often referred to as the exclusive OR function of A and B.

Example 2.2. Write down the table for the structure (P (X), ) when X =
{a, b}.

Solution. The table is given in Table 2.2, where we write A for {a} and B
for {b}.


Proposition 2.3. The operation is associative and commutative on P (X); it
has an identity ˜, and each element is its own inverse. That is, the following
relations hold for all A, B, C ∈ P (X):
(i) A (B C) = (A B) C. (ii) A B = B A.
(iii) A ˜ = A. (iv) A A = ˜.

Three further properties of the symmetric difference are:

(v) A X = A. (vi) A A = X.
(vii) A © (B C) = (A © B) (A © C).

Proof. (ii) follows because the de¬nition of A B is symmetric in A and B.
To prove (i) observe ¬rst that Proposition 2.1 gives

B C = (B © C) ∪ (B © C) = (B ∪ C) © (B ∪ C)
= (B © B) ∪ (B © C) ∪ (C © B) ∪ (C © C)
= (B © C) ∪ (B © C).


TABLE 2.2. Symmetric Difference in P ({a, b})
˜ A B X
˜ ˜ A B X
˜
A A X B
˜
B B X A
˜
X X B A
NUMBER OF ELEMENTS IN A SET 11


A B A B

C C

A ∆ (B ∆ C) = (A ∆ B) ∆ C A © (B ∆ C) = (A © B) ∆ (A © C)
Figure 2.4. Venn diagrams.


A B A B

C C

A ∪ (B ∆ C) (A ∪ B) ∆ (A ∪ C)
Figure 2.5. Venn diagrams of unequal expressions.

Hence
A (B C) = {A © (B C)} ∪ {A © (B C)}
= {A © [(B © C) ∪ (B © C)]} ∪ {A © [(B © C) ∪ (B © C)]}
= (A © B © C) ∪ (A © B © C) ∪ (A © B © C) ∪ (A © B © C)).
This expression is symmetric in A, B, and C, so (ii) gives
A (B C) = C (A B) = (A B) C.
We leave the proof of the other parts to the reader. Parts (i) and (vii) are
illustrated in Figure 2.4.
Relation (vii) of Proposition 2.3 is a distributive law and states that © is
distributive over . It is natural to ask whether ∪ is distributive over .

Example 2.4. Is it true that A ∪ (B C) = (A ∪ B) (A ∪ C) for all A, B, C ∈
P (X)?

Solution. The Venn diagrams for each side of the equation are given in
Figure 2.5. If the shaded areas are not the same, we will be able to ¬nd a
counter example. We see from the diagrams that the result will be false if
A is nonempty. If A = X and B = C = ˜, then A ∪ (B C) = A, whereas
(A ∪ B) (A ∪ C) = ˜; thus union is not distributive over symmetric difference.




NUMBER OF ELEMENTS IN A SET

If a set X contains two or three elements, we have seen that P (X) contains 22
or 23 elements, respectively. This suggests the following general result on the
number of subsets of a ¬nite set.
12 2 BOOLEAN ALGEBRAS


Theorem 2.5. If X is a ¬nite set with n elements, then P (X) contains 2n
elements.

Proof. Each of the n elements of X is either in a given subset A or not in A.
Hence, in choosing a subset of X, we have two choices for each element, and
these choices are independent. Therefore, the number of choices is 2n , and this
is the number of subsets of X.
If n = 0, then X = ˜ and P (X) = {˜}, which contains one element.

Denote the number of elements of a set X by |X|. If A and B are ¬nite
disjoint sets (that is, A © B = ˜), then

|A ∪ B| = |A| + |B|.

Proposition 2.6. For any two ¬nite sets A and B,

|A ∪ B| = |A| + |B| ’ |A © B|.

Proof. We can express A ∪ B as the disjoint union of A and B ’ A; also,
B can be expressed as the disjoint union of B ’ A and A © B as shown in
Figure 2.6. Hence |A ∪ B| = |A| + |B ’ A| and |B| = |B ’ A| + |A © B|. It fol-
lows that |A ∪ B| = |A| + |B| ’ |A © B|.

Proposition 2.7. For any three ¬nite sets A, B, and C,

|A ∪ B ∪ C| = |A| + |B| + |C| ’ |A © B| ’ |A © C|
’ |B © C| + |A © B © C|.

Proof. Write A ∪ B ∪ C as (A ∪ B) ∪ C. Then, by Proposition 2.6,

|A ∪ B ∪ C| = |A ∪ B| + |C| ’ |(A ∪ B) © C|
= |A| + |B| ’ |A © B| + |C| ’ |(A © C) ∪ (B © C)|
= |A| + |B| + |C| ’ |A © B| ’ |A © C| ’ |B © C|
+ |(A © C) © (B © C)|.

The result follows because (A © C) © (B © C) = A © B © C.




B’A A©B B’A
A



Figure 2.6
BOOLEAN ALGEBRAS 13


C B
520 60
110
20
200 10

120 W

Figure 2.7. Different classes of commuters.


Example 2.8. A survey of 1000 commuters reported that 850 sometimes used a
car, 200 a bicycle, and 350 walked, whereas 130 used a car and a bicycle, 220
used a car and walked, 30 used a bicycle and walked, and 20 used all three. Are
these ¬gures consistent?

Solution. Let C, B, and W be the sets of commuters who sometimes used a
car, a bicycle, and walked, respectively. Then

|C ∪ B ∪ W | = |C| + |B| + |W | ’ |C © B| ’ |C © W |
’ |B © W | + |C © B © W |
= 850 + 200 + 350 ’ 130 ’ 220 ’ 30 + 20
= 1040.

Since this number is greater than 1000, the ¬gures must be inconsistent. The
breakdown of the reported ¬gures into their various classes is illustrated in
Figure 2.7. The sum of all these numbers is 1040.

Example 2.9. If 47% of the people in a community voted in a local election and
75% voted in a federal election, what is the least percentage that voted in both?

Solution. Let L and F be the sets of people who voted in the local and federal
elections, respectively. If n is the total number of voters in the community, then
|L| + |F | ’ |L © F | = |L ∪ F | n. It follows that

47 75 22
|L © F | |L| + |F | ’ n = + ’1 n= n.
100 100 100

Hence at least 22% voted in both elections.


BOOLEAN ALGEBRAS

We now give the de¬nition of an abstract boolean algebra in terms of a set
with two binary operations and one unary operation on it. We show that various
algebraic structures, such as the algebra of sets, the logic of propositions, and
14 2 BOOLEAN ALGEBRAS


the algebra of switching circuits are all boolean algebras. It then follows that
any general result derived from the axioms will hold in all our examples of
boolean algebras.
It should be noted that this axiom system is only one of many equivalent ways
of de¬ning a boolean algebra. Another common way is to de¬ne a boolean algebra
as a lattice satisfying certain properties (see the section “Posets and Lattices”).
A boolean algebra (K, §, ∨, ) is a set K together with two binary operations
§ and ∨, and a unary operation on K satisfying the following axioms for all
A, B, C ∈ K:

(i) A § (B § C) = (A § B) § C. (ii) A ∨ (B ∨ C) = (A ∨ B) ∨ C.
(associative laws)
A § B = B § A. (iv) A ∨ B = B ∨ A.
(iii)
(commutative laws)
A § (B ∨ C) (vi) A ∨ (B § C)
(v)
= (A § B) ∨ (A § C). = (A ∨ B) § (A ∨ C).
(distributive laws)
There is a zero element 0 in K such that A ∨ 0 = A.
(vii)
There is a unit element 1 in K such that A § 1 = A.
(viii)
A § A = 0. (x) A ∨ A = 1.
(ix)

We call the operations § and ∨, meet and join, respectively. The element A
is called the complement of A.
The associative axioms (i) and (ii) are redundant in the system above because
with a little effort they can be deduced from the other axioms. However, since
associativity is such an important property, we keep these properties as axioms.
It follows from Proposition 2.1 that (P (X), ©, ∪, ’ ) is a boolean algebra
with ˜ as zero and X as unit. When X = ˜, this boolean algebra of subsets
contains one element, and this is both the zero and unit. It can be proved (see
Exercise 2.17) that if the zero and unit elements are the same, the boolean algebra
must have only one element.
We can de¬ne a two-element boolean algebra ({0, 1}, §, ∨, ) by means of
Table 2.3.

Proposition 2.10. If the binary operation on the set K has an identity e such
that a e = e a = a for all a ∈ K, then this identity is unique.


TABLE 2.3. Two-Element Boolean Algebra
A§B A∨B
A B A A
0 0 0 0 0 1
0 1 0 1 1 0
1 0 0 1
1 1 1 1
BOOLEAN ALGEBRAS 15


Proof. Suppose that e and e are both identities. Then e = e e , since e is
an identity, and e e = e since e is an identity. Hence e = e , so the identity
must be unique.

Corollary 2.11. The zero and unit elements in a boolean algebra are unique.

Proof. This follows directly from the proposition above, because the zero
and unit elements are the identities for the join and meet operations, respec-
tively.

Proposition 2.12. The complement of an element in a boolean algebra is unique;
that is, for each A ∈ K there is only one element A ∈ K satisfying axioms (ix)
and (x): A § A = 0 and A ∨ A = 1.

Proof. Suppose that B and C are both complements of A, so that A § B =
0, A ∨ B = 1, A § C = 0, and A ∨ C = 1. Then

B = B ∨ 0 = B ∨ (A § C) = (B ∨ A) § (B ∨ C)
= (A ∨ B) § (B ∨ C) = 1 § (B ∨ C) = B ∨ C.

Similarly, C = C ∨ B and so B = B ∨ C = C ∨ B = C.

If we interchange § and ∨ and interchange 0 and 1 in the system of axioms
for a boolean algebra, we obtain the same system. Therefore, if any proposition
is derivable from the axioms, so is the proposition obtained by interchanging
§ and ∨ and interchanging 0 and 1. This is called the duality principle. For
example, in the following proposition, there are four pairs of dual statements. If
one member of each pair can be proved, the other will follow directly from the
duality principle.
If (K, §, ∨, ) is a boolean algebra with 0 as zero and 1 as unit, then (K, ∨, §, )
is also a boolean algebra with 1 as zero and 0 as unit.

Proposition 2.13. If A, B, and C are elements of a boolean algebra (K, §, ∨, ),
the following relations hold:

(i) A § 0 = 0. (ii) A ∨ 1 = 1.
(iii) A § (A ∨ B) = A. (iv) A ∨ (A § B) = A.
(absorption laws)
(v) A § A = A. (vi) A ∨ A = A. (idempotent laws)
(vii) (A § B) = A ∨ B . (viii) (A ∨ B) = A § B .
(De Morgan™s laws)
(ix) (A ) = A.

Proof. Note ¬rst that relations (ii), (iv), (vi), and (viii) are the duals of relations
(i), (iii), (v), and (vii), so we prove the last four, and relation (ix). We use the
axioms for a boolean algebra several times.
16 2 BOOLEAN ALGEBRAS


(i) A § 0 = A § (A § A ) = (A § A) § A = A § A = 0.
(iii) A § (A ∨ B) = (A ∨ 0) § (A ∨ B) = A ∨ (0 § B) = A ∨ 0 = A.
(v) A = A § 1 = A § (A ∨ A ) = (A § A) ∨ (A § A )
= (A § A) ∨ 0 = A § A.

Relations (vii) follows from Proposition 2.12 if we can show that A ∨ B is
a complement of A § B [then it is the complement (A § B) ]. Now using part
(i) of this proposition,

(A § B) § (A ∨ B ) = [(A § B) § A ] ∨ [(A § B) § B ]
= [(A § A ) § B] ∨ [A § (B § B )]
= [0 § B] ∨ [A § 0]
=0∨0
= 0.

Similarly, part (ii) gives

(A § B) ∨ (A ∨ B ) = [A ∨ (A ∨ B )] § [B ∨ (A ∨ B )]
= [(A ∨ A ) ∨ B ] § [(B ∨ B ) ∨ A ]
= [1 ∨ B ] § [1 ∨ A ]
=1§1
= 1.

To prove relation (ix), by de¬nition we have A § A = 0 and A ∨ A = 1.
Therefore, A is a complement of A , and since the complement is unique,
A = (A ) .


PROPOSITIONAL LOGIC

We now show brie¬‚y how boolean algebra can be applied to the logic of propo-
sitions. Consider two sentences “A” and “B”, which may either be true or false.
For example, “A” could be “This apple is red,” and “B” could be “This pear
is green.” We can combine these to form other sentences, such as “A and B,”
which would be “This apple is red, and this pear is green.” We could also form
the sentence “not A,” which would be “This apple is not red.” Let us now com-
pare the truth or falsity of the derived sentences with the truth or falsity of the
original ones. We illustrate the relationship by means of a diagram called a truth
table. Table 2.4 shows the truth tables for the expressions “A and B,” “A or B,”
and “not A.” In these tables, T stands for “true” and F stands for “false.” For
PROPOSITIONAL LOGIC 17

TABLE 2.4. Truth Tables
A and B A or B
A B Not A
A
F F F F F T
F T F T T F
T F F T
T T T T



example, if the statement “A” is true while “B” is false, the statement “A and
B” will be false, and the statement “A or B” will be true.
We can have two seemingly different sentences with the same meaning; for
example, “This apple is not red or this pear is not green” has the same meaning
as “It is not true that this apple is red and that this pear is green.” If two
sentences, P and Q, have the same meaning, we say that P and Q are logically
equivalent, and we write P = Q. The example above concerning apples and
pears implies that

(not A) or (not B) = not (A and B).

This equation corresponds to De Morgan™s law in a boolean algebra.
It appears that a set of sentences behaves like a boolean algebra. To be more
precise, let us consider a set of sentences that are closed under the operations of
“and,” “or,” and “not.” Let K be the set, each element of which consists of all
the sentences that are logically equivalent to a particular sentence. Then it can
be veri¬ed that (K, and, or, not) is indeed a boolean algebra. The zero element
is called a contradiction, that is, a statement that is always false, such as “This
apple is red and this apple is not red.” The unit element is called a tautology, that
is, a statement that is always true, such as “This apple is red or this apple is not
red.” This allows us to manipulate logical propositions using formulas derived
from the axioms of a boolean algebra.

. 1
( 13)



>>