Recent Developments in Switching Theory

Contents

List of Contributors

Preface

Acknowledgments

I. Complete Sets of Logic Primitives

I. Introduction

II. Iteratively Closed System of Functions

III. Characterization of Weak Complete Set of Logic Primitives

IV. Reduction Theorems

V. Theorem of Post

VI. Bases and Simple Bases

VII. Almost Complete Sets of Logic Primitives

Appendix. Proof of Theorem 7.1

References

II. Combinational Circuits with Feedback

I. Introduction

II. Circuit Visualization of Markov's Result

III. A Circuit with a Single Not-Element Which Inverts Two Variables

IV. The Design of "Multi-Inversion" Circuits Which Use Only One Inverter

V. Proof of the Necessity of Unstable Circuit Equilibria

VI. A "Multi-Inversion" Circuit Which Is Stable

VII. Summary and Conclusions

References

III. Lupanov Decoding Networks

I. Introduction

II. Disjunctive and Nondisjunctive Complete Decoding Networks

III. The Case When r≠2ᴷ

IV. The Optional Terms

V. Toward a General Theory

VI. Conclusions

References

IV. Counting Theorems and their Applications to Classification of Switching Functions

I. Introduction to Boolean Functions and Classification Problems

II. Group Theory and Polya's Theorem

III. Some Applications of Polya's Theorem to Switching Functions

IV. Structure Theorems for Permutation Groups and the Determination of Cycle Indices

V. Operations on the Range, Genera, and a Lower Bound

Appendix 1. Cycle Index Polynomials for Sn

Appendix 2. Cycle Index Polynomials for Gn

Appendix 3. Cycle Index Polynomials for GLn(W2)

Appendix 4. Cycle Index Polynomials for An(Z2)

References

V. Harmonic Analysis of Switching Functions

I. Summary

II. Survey of Abstract Harmonic Analysis

III. Combinatorial Applications

IV. Analysis of the Prototype Equivalence Relation

V. Synthesis of Encoded Input Logic

References

VI. Universal Logic Modules

I. Statement of the Problem

II. Bounds for M(n)

III. The Construction of ULM'S for Small n

IV. Other Approaches to the Universal Module Problem

V. Historical References

References

VII. Cellular Logic

I. Introduction

II. Single-Rail Cascades

III. Two-Rail Cascades

IV. Two-Dimensional Arrays

V. Minimization of Cellular Arrays

VI. Review of Other Works in Cellular Area

References

VIII. The Theory of Multirail Cascades

I. Introduction

II. Decomposition Theory of Group Functions

III. Synthesis of Multirail Cascades

References

IX. Programmable Cellular Logic

I. Introduction

II. Programmable Cellular Arrays

III. Arrays for Arbitrary Logic

IV. Special-Purpose Arrays

V. Conclusion

References

Author Index

Subject Index