Direkt zum Inhalt

Lexikon der Mathematik: reduzierte Primimplikantentafel

eine Primim- plikantentafel A(f) einer Booleschen Funktion f, auf die keine der drei folgenden Reduktionsregeln angewendet werden kann.

  1. Für jeden wesentlichen Primimplikanten q von f streiche alle Spalten α mit A(f)(q, α) = 1. Streiche die Zeile q ebenfalls.
  2. Streiche jede Spalte α, für die es eine Spalte β (βα) gibt, die wenigstens eine 1 enthält und komponentenweise kleiner als α ist.
  3. Streiche jede Zeile q, zu der es eine Zeile r gibt, die komponentenweise größer als q ist, und deren Kosten nicht größer als die Kosten von q sind.

Die erste Reduktionsregel trägt der Tatsache Rechnung, daß jeder wesentliche Primimplikant in einem Minimalpolynom (Minimalpolynom einer Booleschen Funktion) von f enthalten sein muß. Ein wesentlicher Primimplikant q kann dementsprechend aus der Primimplikantentafel gestrichen werden, ebenso alle die Elemente der ON-Menge von f, die von q überdeckt werden.

Die zweite Reduktionsregel nutzt aus, daß jede Zeile, die eine 1 in Spalte β hat, auch eine 1 in Spalte α hat. Spalte α braucht also im Rahmen der Konstruktion eines Minimalpolynoms von f nicht weiter betrachtet zu werden.

Die dritte Reduktionsregel sagt aus, daß eine Zeile q bei der Konstruktion eines Minimalpolynoms nicht weiter betrachtet zu werden braucht, wenn es eine Zeile r gibt, die alle Spalten überdeckt, die auch Zeile q überdeckt, und die Kosten von q nicht echt kleiner als die Kosten von r sind.

Lesermeinung

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnervideos