Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

01.02.2021 | Ausgabe 1/2021

Journal of Applied and Industrial Mathematics 1/2021

Connected Boolean Functions with a Locally Extremal Number of Prime Implicants

Zeitschrift:
Journal of Applied and Industrial Mathematics > Ausgabe 1/2021
Autor:
I. P. Chukhrov
Wichtige Hinweise
Translated by Ya.A. Kopylov

Abstract

The well-known lower bound for the maximum number of prime implicants of a Boolean function (the length of the reduced DNF) differs by \(\Theta (\sqrt {n}) \) times from the upper bound and is asymptotically attained at a symmetric belt function with belt width \(n/3 \). To study the properties of connected Boolean functions with many prime implicants, we introduce the notion of a locally extremal function in a certain neighborhood in terms of the number of prime implicants. Some estimates are obtained for the change in the number of prime implicants as the values of the belt function range over a \(d \)-neighborhood. We prove that the belt function for which the belt width and the number of the lower layer of unit vertices are asymptotically equal to \(n/3 \) is locally extremal in some neighborhood for \(d \le \Theta (n) \) and not locally extremal if \(d \ge 2^{\Theta (n)} \). A similar statement is true for the functions that have prime implicants of different ranks. The local extremality property is preserved after applying some transformation to the Boolean function that preserves the distance between the vertices of the unit cube.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 69.000 Bücher
  • über 500 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 50.000 Bücher
  • über 380 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Weitere Artikel der Ausgabe 1/2021

Journal of Applied and Industrial Mathematics 1/2021 Zur Ausgabe

Premium Partner

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen. 

    Bildnachweise