Vorlesung TdL FAQ

• F: Es wurde gezeigt, dass es Funktionen gibt, die ca. 3ⁿ/n viele Primimplikanten haben. Andererseits soll in Aufgabe 8 gezeigt werden, dass ein Minimalpolynom nur 2^n-1 Primimplikanten enthalten kann. Ist das kein Widerspruch?
• A: Nein, denn Minimalpolynome müssen ja nicht unbedingt alle Primimplikanten enthalten. Zum Beispiel für f= x1 x2 ODER x2quer x3 enthält die Menge der Primimplikanten von f neben x1x2 und x2quer x3 auch noch das Monom x1x3 !

• F: Wie kann man effizient entscheiden, ob eine Funktion monoton ist?
• A: Das kann man vermutlich nicht. Siehe: PS-File