The expanded and updated 2nd edition of this classic text offers the reader a comprehensive introduction to the concepts of logic functions and equations and their applications across computer science. The approach emphasizes a thorough understanding of the fundamental principles as well as numerical and computer-based solution methods. Updated throughout, some major additions for the 2nd edition include: - an expanded introductory section on logic equations; - a new chapter on sets, lattices, and classes of logic functions; - a new chapter about SAT-problems; - a new chapter about methods to solve extremely complex problems; and - an expanded section with new decomposition methods utilizing the Boolean Differential Calculus extended to lattices of logic functions. The book provides insight into applications across binary arithmetic, coding, complexity, logic design, programming, computer architecture, and artificial intelligence. Based on the extensive teaching experience of the authors, Logic Functions and Equations is highly recommended for a one- or two-semester course in computer science and related programs. It provides straightforward high-level access to these methods and enables sophisticated applications, elegantly bridging the gap between mathematics and the theoretical foundations of computer science.

Tsutomu Sasao – Kyushu Institute of Technology, Japan The material covered in this book is quite unique especially for p- ple who are reading English, since such material is quite hard to ?nd in the U.S. literature. German and Russian people have independently developed their theories, but such work is not well known in the U.S. societies. On the other hand, the theories developed in the U.S. are not conveyed to the other places. Thus, the same theory is re-invented or re-discovered in various places. For example, the switching theory was developed independently in the U.S., Europe, and Japan, almost at the same time [4, 18, 19]. Thus, the same notions are represented by di?- ent terminologies. For example, the Shegalkin polynomial is often called complement-free ring-sum, Reed-Muller expression [10], or Positive - larityReed-Mullerexpression [19].Anyway,itisquitedesirablethatsuch a unique book like this is written in English, and many people can read it without any di?culties. The authors have developed a logic system called XBOOLE.Itp- forms logical operations on the given functions. With XBOOLE, the readers can solve the problems given in the book. Many examples and complete solutions to the problems are shown, so the readers can study at home. I believe that the book containing many exercises and their solutions [9] is quite useful not only for the students, but also the p- fessors.

The greatly expanded and updated 3rd edition of this textbook offers the reader a comprehensive introduction to the concepts of logic functions and equations and their applications across computer science and engineering. The authors’ approach emphasizes a thorough understanding of the fundamental principles as well as numerical and computer-based solution methods. The book provides insight into applications across propositional logic, binary arithmetic, coding, cryptography, complexity, logic design, and artificial intelligence. Updated throughout, some major additions for the 3rd edition include: a new chapter about the concepts contributing to the power of XBOOLE; a new chapter that introduces into the application of the XBOOLE-Monitor XBM 2; many tasks that support the readers in amplifying the learned content at the end of the chapters; solutions of a large subset of these tasks to confirm learning success; challenging tasks that need the power of the XBOOLE software for their solution. The XBOOLE-monitor XBM 2 software is used to solve the exercises; in this way the time-consuming and error-prone manipulation on the bit level is moved to an ordinary PC, more realistic tasks can be solved, and the challenges of thinking about algorithms leads to a higher level of education.

One of the chief aims of this self-contained monograph is to survey recent developments of Boolean functions and equations, as well as lattice functions and equations in more general classes of lattices. Lattice (Boolean) functions are algebraic functions defined over an arbitrary lattice (Boolean algebra), while lattice (Boolean) equations are equations expressed in terms of lattice (Boolean) functions. Special attention is also paid to consistency conditions and reproductive general solutions. Applications refer to graph theory, automata theory, synthesis of circuits, fault detection, databases, marketing and others. Lattice Functions and Equations updates and extends the author's previous monograph - Boolean Functions and Equations.

The Boolean Differential Calculus (BDC) is a very powerful theory that extends the structure of a Boolean Algebra significantly. Based on a small number of definitions, many theorems have been proven. The available operations have been efficiently implemented in several software packages. There is a very wide field of applications. While a Boolean Algebra is focused on values of logic functions, the BDC allows the evaluation of changes of function values. Such changes can be explored for pairs of function values as well as for whole subspaces. Due to the same basic data structures, the BDC can be applied to any task described by logic functions and equations together with the Boolean Algebra. The BDC can be widely used for the analysis, synthesis, and testing of digital circuits. Generally speaking, a Boolean differential equation (BDE) is an equation in which elements of the BDC appear. It includes variables, functions, and derivative operations of these functions. The solution of such a BDE is a set of Boolean functions. This is a significant extension of Boolean equations, which have sets of Boolean vectors as solutions. In the simplest BDE a derivative operation of the BDC on the left-hand side is equal to a logic function on the right-hand side. The solution of such a simple BDE means to execute an operation which is inverse to the given derivative. BDEs can be applied in the same fields as the BDC, however, their possibility to express sets of Boolean functions extends the application field significantly.

This book is about the logic of Boolean equations. Such equations were central in the "algebra of logic" created in 1847 by Boole [12, 13] and devel oped by others, notably Schroder [178], in the remainder of the nineteenth century. Boolean equations are also the language by which digital circuits are described today. Logicians in the twentieth century have abandoned Boole's equation based logic in favor of the more powerful predicate calculus. As a result, digital engineers-and others who use Boole's language routinely-remain largely unaware of its utility as a medium for reasoning. The aim of this book, accordingly, is to is to present a systematic outline of the logic of Boolean equations, in the hope that Boole's methods may prove useful in solving present-day problems. Two Logical Languages Logic seeks to reduce reasoning to calculation. Two main languages have been developed to achieve that object: Boole's "algebra of logic" and the predicate calculus. Boole's approach was to represent classes (e. g. , happy creatures, things productive of pleasure) by symbols and to represent logical statements as equations to be solved. His formulation proved inadequate, however, to represent ordinary discourse. A number of nineteenth-century logicians, including Jevons [94], Poretsky [159], Schroder [178], Venn [210], and Whitehead [212, 213], sought an improved formulation based on ex tensions or modifications of Boole's algebra. These efforts met with only limited success.

The Boolean Differential Calculus (BDC) is a very powerful theory that extends the basic concepts of Boolean Algebras significantly. Its applications are based on Boolean spaces and n, Boolean operations, and basic structures such as Boolean Algebras and Boolean Rings, Boolean functions, Boolean equations, Boolean inequalities, incompletely specified Boolean functions, and Boolean lattices of Boolean functions. These basics, sometimes also called switching theory, are widely used in many modern information processing applications. The BDC extends the known concepts and allows the consideration of changes of function values. Such changes can be explored for pairs of function values as well as for whole subspaces. The BDC defines a small number of derivative and differential operations. Many existing theorems are very welcome and allow new insights due to possible transformations of problems. The available operations of the BDC have been efficiently implemented in several software packages. The common use of the basic concepts and the BDC opens a very wide field of applications. The roots of the BDC go back to the practical problem of testing digital circuits. The BDC deals with changes of signals which are very important in applications of the analysis and the synthesis of digital circuits. The comprehensive evaluation and utilization of properties of Boolean functions allow, for instance, to decompose Boolean functions very efficiently; this can be applied not only in circuit design, but also in data mining. Other examples for the use of the BDC are the detection of hazards or cryptography. The knowledge of the BDC gives the scientists and engineers an extended insight into Boolean problems leading to new applications, e.g., the use of Boolean lattices of Boolean functions.

The Boolean Differential Calculus (BDC) is a very powerful theory that extends the structure of a Boolean Algebra significantly. Based on a small number of definitions, many theorems have been proven. The available operations have been efficiently implemented in several software packages. There is a very wide field of applications. While a Boolean Algebra is focused on values of logic functions, the BDC allows the evaluation of changes of function values. Such changes can be explored for pairs of function values as well as for whole subspaces. Due to the same basic data structures, the BDC can be applied to any task described by logic functions and equations together with the Boolean Algebra. The BDC can be widely used for the analysis, synthesis, and testing of digital circuits. Generally speaking, a Boolean differential equation (BDE) is an equation in which elements of the BDC appear. It includes variables, functions, and derivative operations of these functions. The solution of such a BDE is a set of Boolean functions. This is a significant extension of Boolean equations, which have sets of Boolean vectors as solutions. In the simplest BDE a derivative operation of the BDC on the left-hand side is equal to a logic function on the right-hand side. The solution of such a simple BDE means to execute an operation which is inverse to the given derivative. BDEs can be applied in the same fields as the BDC, however, their possibility to express sets of Boolean functions extends the application field significantly.

Boolean Algebra and Combinational NetworksPrinciple of Duality; Boolean Formulas and Functions : Normal Formulas; Canonical Formulas : Minterm Canonical Formulas, m-Notation; Manipulations of Boolean Formulas: Equation Complementation, Expansion about a Variable, Equation Simplification, The Reduction Theorems, Minterm Canonical Formulas, Maxterm Canonical Formulas, Complements of Canonical Formulas; Gates and Combinational Networks : Gates, Combinational Networks, Analysis Procedure, Synthesis Procedure, A Logic Design Example; Incomplete Boolean Functions and Don't Care Conditions : Describing Incomplete Boolean Functions, Don't Care Conditions in Logic Design; Additional Boolean Operations and Gates : The NAND-Functions, The NOR-Functions, Universal Gates, NAND-Gate Realizations, NOR-Gate Realizations, The Exclusive-OR-Function, The Exclusive-NOR Function.Simplification of Boolean ExpressionsFormulation of the Simplification Problem : Criteria of Minimality, The Simplification Problem; Prime Implicants and Irredundant Disjunctive Expressions : Implies, Subsumes, Implicants and Prime Implicants, Irredundant Disjunctive Normal Formulas; Prime Implicants and Irredundant Conjunctive Expressions; Karnaugh Maps : One-Variable and Two-Variable Maps, Three-Variable and Four-Variable Maps, Karnaugh Maps and Canonical Formulas, Product and Sum Term Representations on Karnaugh Maps; Using Karnaugh Maps to Obtain Minimal Expressions for Complete Boolean Functions : Prime Implicants and Karnaugh Maps, Essential Prime Implicants, Minimal Sums, Minimal Products; Minimal Expressions of Incomplete Boolean Functions : Minimal Sums, Minimal Products; The Quine-McCluskey Method of Generating Prime Implicants and Prime Implicates : Prime Implicants and the Quine - McCluskey Method, Algorithm for Generating Prime Implicants, Prime Implicates and the Quine - McCluskey Method; Prime Implicant/Prime-Implicate Tables and Irredundant Expressions; Petrick's Method of Determining Irredunant Expressions, Prime-Implicate Tables and Irredundant Conjunctive Normal Formulas; Prime Implicant/Prime-Implicate Table Reductions : Essential Prime Implicants, Column and Row Reductions, A Prime - Implicant Selection Procedure; Decimal Method for Obtaining Prime Implicants; Map Entered Variables.Logic Levels and FamiliesLogic Levels, Integration Levels; Output Switching Times, The Propagation Delay, Fan-out and Fan-in, Extension to Other Logic Gates, Logic Cascades.Transistor-Transistor logic; Wired logic, TTL with Totem-Pole output, Thee-state output TTL, Schottky TTL; The MOS Field-Effect-Transistor : Operation of n-Channel, Enhancement-Type MOSFET, The n-Channel Depletion-Type MOSFET, The p-channel MOSFETs, Circuit Symbols, The MOSFET as a Resistor; NMOS and PMOS Logic : The NMOS Inverters, NMOS NOR-Gate, NMOS NAND-Gate, PMOS Logic, performance; The CMOS Inverter, CMOS NOR-Gate, CMOS NAND-Gate, performance, Comparison of the above logic families.Logic Design with MSI Components and Programmable Logic DevicesBinary Adders and Subtractors; Binary Subtractors, Carry Lookahead Adders; Decimal Adders; Comparators; Decoders; Logic Design Using Decoders; Decoders with an Enable Input; Encoders; Multiplexers; Logic Design with Multiplexers; Programmable Logic Devices (PLDs); PLD Notation; Programmable Read-Only Memories (PROMs); Programmable Logic Arrays (PLAs); Programmable Array Logic (PAL) Devices.Flip-Flops and Simple Flip-Flop ApplicationsThe Basic Bistable Element; Latches; The SR Latch, An Application of the SR Latch : A Switch Debouncer, The SR Latch, The Gated SR Latch, The Gated D Latch; Master-Slave Flip-Flops (Pulse-Triggered Flip-Flops); The Master-Slave SR Flip-Flop; The Master-Slave JK Flip-Flop; Edge-Triggered Flip-Flop; The Positive Edge-Triggered D Flip-Flop; Negative Edge-Triggered D flip-flops; Characteristic Equations; Registers; Counters : Binary Ripple Counters, Synchronous Binary Counters, Counters Based on Shift Registers ; Design of Synchronous Counters : Design of a Synchronous Mod-6 Counter Using Clocked JK Flip-Flops, Design of a Synchronous Mod-6 Counter Using Clocked D,T or SR Flip-Flops.Synchronous Sequential NetworksStructure and Operation of Clocked Synchronous Sequential Networks; Analysis of Clocked Synchronous Sequential Networks; Excitation and Output Expressions, Transition Equations, Transition Tables, Excitation Tables, State Tables, State Diagrams Network Terminal Behavior.