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.