Nombre moyen de majorants d’une fonction Booléenne incomplète. Remarques concernant le nombre moyen de monômes premiers. (French) Zbl 0154.41601

English summary: The preliminary computation of the “majorants” enables the determination of the minimal or quasi-minimal disjunctive irredundant forms of an incompletely specified function [Rev. Franç. Inform. Rech. Opér. 1, No. 4, 73–86 (1967; Zbl 0189.29205)]. In practical cases, the search algorithm for the disjunctive irredundant form is applicable only if the number of “majorants” is not too large.
In this paper formulas are derived to determine the average value of this number. Then the computation of the average number of prime implicants, already given by F. Mileto and G. Putzolu [IEEE Trans. Electron. Comput. 13, 87–92 (1964; Zbl 0163.25803)], is rederived in a new form. The result is used to built functions having a great number of prime implicants and yields, for a function of \(n\) variables, a lower bound of the maximal number of prime implicants.


94C11 Switching theory, applications of Boolean algebras to circuits and networks
Full Text: DOI


[1] Grasselli A. Un procedimento per la sintesi di reti logiche combinatorie, Alta Frequenza,31, (1962), 673–84.
[2] Kazakov V. D. The minimization of logical functions of a large number of variables. Article original dans Avtomatika i Telemekhanika, 11 janvier 1962. Traduction anglaise dans Automation and Remote Control,23 (1962), 1237–42.
[3] Lapscher F. Fonctions booléennes très incomplètes. Représentation par des sommes de monómes. Séminaire d’Algèbre de Boole, Inst. Math. Appl., Fac. Sci. Grenoble,24 Janvier 1966.
[4] Mileto F., Putzolu G. Average values of quantities appearing in boolean function minimization. IEEE Trans,13, Avril 1964, 87–92. · Zbl 0163.25803
[5] Mileto F., Putzolu G. Statistical Complexity of Algorithms for Boolean function minimization. J. Ass. Computg Machin.,12, (1965), 364–75. · Zbl 0139.32604
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.