Primterm

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Als Primterm oder Primimplikant einer Booleschen Funktion bezeichnet man solche Terme einer Disjunktion von Konjunktionstermen, die nicht mehr verkürzt werden können und folglich minimale Länge aufweisen. Primterme sind also kürzeste Konjunktionsterme. Unter der Länge eines Terms wird dabei die Anzahl der enthaltenen Konjunktionen und Disjunktionen verstanden (innerhalb eines Konjunktionsterms sind dabei freilich nur Konjunktionen interessant). Das Auffinden von Primtermen ist von hoher Bedeutung für die Minimierung von Funktionsausdrücken (etwa im Rahmen des Entwurfes von Schaltnetzen). Es kann für Funktionen mit geringer Variablenzahl grafisch mittels Karnaugh-Veitch-Diagrammen erfolgen. Für größere Variablenzahlen eignet sich das Verfahren von Quine und McCluskey zu diesem Zweck. Als Faustregel gilt: Karnaugh-Veitch-Diagramm für 1-5 Variablen, Quine/McCluskey für 6 oder mehr Variablen.

Primterme garantieren jedoch an sich noch keine minimale disjunktive Normalform, da sie zwar minimal, aber überflüssig sein können. Solche Primterme, die zur Darstellung der Funktion nicht überflüssig sind, bezeichnet man als Kernprimterme, Kern-Primimplikanten, Kernimplikanten, wesentliche Primimplikanten oder essentielle Primimplikanten.