Abstract
A new notation for a NAND operator is proposed, based on the prefix Polish notation following the style of Lukasiewicz. There is a direct one-to-one correspondence between the operators in the resulting system and gates in a circuit realization if identical subfunctions are recognized. An axiom set for the Boolean algebra based on this operator is given, and the axiomatic derivation of the algebra is demonstrated. A number of results concerning circuit manipulation, redundant sets of gate inputs, and necessary and sufficient conditions for the relocation of certain gate inputs are presented, and their use demonstrated by a number of examples.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
D. F. Barnard and D. F. Holman, “The use of Roth's decomposition algorithm in multilevel design of circuits,”Comput. J. 11:269–276 (1972).
D. L. Dietmeyer and Y. H. Su, “Logic design automation of fan-in limited NAND networks,”IEEE Trans. Comput. EC-18:11–22 (1969).
D. T. Ellis, “A synthesis of combinational logic with NAND or NOR elements,”IEEE Trans. Comput. EC-14:701–705 (1965).
D. D. Givone,Introduction to Switching Circuit Theory (McGraw-Hill, New York, 1970).
L. Hellerman, “A catalog of three-variable or-invert and and-invert logical circuits,”IEEE Trans. Comput. EC-12:198–223 (1963).
E. V. Huntington, “Sets of independent postulates for the algebra of logic,”Trans. Am. Math. Soc. 5:288–309 (1904).
H. C. Lai, T. Nakagawa, and S. Muroga, “Redundancy check technique for designing optimal networks by branch- and-bound method,”Int. J. Comput. Inf. Sci. 3:251–271 (1974).
H. P. Lee and E. S. Davidson, “A transform for NAND network design,”IEEE Trans. Comput. C-21:12–20 (1972).
G. A. Maley and G. Earle,The Logic Design of Transistor Digital Computers (Prentice-Hall, Englewood Cliffs, N.J., 1963).
E. J. McCluskey, Jr., “Logical Design Theory of NOR Gate Networks with No Complemented Inputs,”Proceedings of the Fourth Annual Symposium on Switching Circuit Theory and Logical Design (1963), pp. 137–148.
J. C. Muzio, “The Use of a NAND Operator in Boolean Manipulation,” Scientific Report No. 60, Department of Computer Science, University of Manitoba (1972).
J. P. Roth, R. M. Karp, F. M. McFarlin, and J. R. Wilts, “A Computer Program for the Synthesis of Combinatorial Switching Circuits,”Proceedings of the Second Annual Symposium on Switching Circuit Theory and Logical Design (1961), pp. 182–194.
H. M. Sheffer, “A set of five independent postulates for Boolean algebras, with application to logical constants,”Trans. Am. Math. Soc. 14:481–488 (1913).
D. Zissos and F. G. Duncan, “NOR and NAND operators in Boolean algebras applied to switching circuit design,”Comput. J. 14:413–417 (1971).
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Muzio, J.C. A prefix operator for a switching algebra. International Journal of Computer and Information Sciences 6, 151–163 (1977). https://doi.org/10.1007/BF00999303
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00999303