Primterm

aus Wikipedia, der freien Enzyklopädie

Als Primterm oder Primimplikant einer Booleschen Funktion bezeichnet man solche Terme einer Disjunktion von Konjunktionsterme, 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-Diagrammen erfolgen. Für größere Variablenzahlen eignet sich das Verfahren von Quine und McCluskey zu diesem Zweck.

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 oder essentielle Primimplikanten.