✦ LIBER ✦
Sur le cardinal maximum de la base complete d'une fonction booleenne, en fonction du nombre de conjonctions de l'une de ses formes normales.
✍ Scribed by Jean-Marie Laborde
- Publisher
- Elsevier Science
- Year
- 1980
- Tongue
- English
- Weight
- 271 KB
- Volume
- 32
- Category
- Article
- ISSN
- 0012-365X
No coin nor oath required. For personal study only.
✦ Synopsis
A.K. Chandra et G. Markowski [I] ont montre qu'une fonction booleenne somme de k monomes. posside au plus f(k) monomes premiers 06 f(k) verifie: 31k13' <f(k)6 2'. On montre ici que f(k) = 2': -1 et que ce maximum est atteint et ne peut &tre atteint que par des fonctions d'au moins 2k -1 variables. A.K. Chandra et G. Markowski [l] showed that any Boolean expression in disjunctive normal form naving k conjuncts can have at most f(k) implicants, where f(k) satisfies 3tk'3J sf(&)s2k
We prove here that f(k) = 2' -I and that this maximum is obtained by and only by functions of at least 2k -1 variables.