CONTENTS xi CHAPTER 15 Boolean Algebra 368 15.1 Introduction 368 15.2 Basic Definitions 368 15.3 Duality 369 15.4 Basic Theorems 370 15.5 Boolean Algebras as Lattices 370 15.6 Representation Theorem 371 15.7 Sum-of-Products Form for Sets 371 15.8 Sum-of-Products Form for Boolean Algebras 372 15.9 Minimal Boolean Expressions,Prime Implicants 375 15.10 Logic Gates and Circuits 377 15.11 Truth Tables,Boolean Functions 381 15.12 Karnaugh Maps 383 Solved Problems 389 Supplementary Problems 403 APPENDIX A Vectors and Matrices 409 A.1 Introduction 409 A.2 Vectors 409 A.3 Matrices 410 A.4 Matrix Addition and Scalar Multiplication 411 A.5 Matrix Multiplication 412 A.6 Transpose 414 A.7 Square Matrices 414 A.8 Invertible (Nonsingular)Matrices,Inverses 415 A.9 Determinants 416 A.10 Elementary Row Operations,Gaussian Elimination (Optional) 418 A.11 Boolean (Zero-One)Matrices 422 Solved Problems 423 Supplementary Problems 429 APPENDIX B Algebraic Systems 432 B.1 Introduction 432 B.2 Operations 432 B.3 Semigroups 435 B.4 Groups 438 B.5 Subgroups,Normal Subgroups,and Homomorphisms 440 B.6 Rings,Internal Domains,and Fields 443 B.7 Polynomials Over a Field 446 Solved Problems 450 Supplementary Problems 461 Index 467CONTENTS xi CHAPTER 15 Boolean Algebra 368 15.1 Introduction 368 15.2 Basic Definitions 368 15.3 Duality 369 15.4 Basic Theorems 370 15.5 Boolean Algebras as Lattices 370 15.6 Representation Theorem 371 15.7 Sum-of-Products Form for Sets 371 15.8 Sum-of-Products Form for Boolean Algebras 372 15.9 Minimal Boolean Expressions, Prime Implicants 375 15.10 Logic Gates and Circuits 377 15.11 Truth Tables, Boolean Functions 381 15.12 Karnaugh Maps 383 Solved Problems 389 Supplementary Problems 403 APPENDIX A Vectors and Matrices 409 A.1 Introduction 409 A.2 Vectors 409 A.3 Matrices 410 A.4 Matrix Addition and Scalar Multiplication 411 A.5 Matrix Multiplication 412 A.6 Transpose 414 A.7 Square Matrices 414 A.8 Invertible (Nonsingular) Matrices, Inverses 415 A.9 Determinants 416 A.10 Elementary Row Operations, Gaussian Elimination (Optional) 418 A.11 Boolean (Zero-One) Matrices 422 Solved Problems 423 Supplementary Problems 429 APPENDIX B Algebraic Systems 432 B.1 Introduction 432 B.2 Operations 432 B.3 Semigroups 435 B.4 Groups 438 B.5 Subgroups, Normal Subgroups, and Homomorphisms 440 B.6 Rings, Internal Domains, and Fields 443 B.7 Polynomials Over a Field 446 Solved Problems 450 Supplementary Problems 461 Index 467