Metoda iteracyjnego konsensusu

Szablon:Dopracować Metoda iteracyjnego konsensusu – iterative consensus, metoda minimalizacji funkcji boolowskiej. Metoda to rozpoczyna się od implikantów funkcji (mogą to być iloczyny zupełne, implikanty proste lub inne implikanty).

Nazwa metody pochodzi od iteracyjnego stosowania zależności:

A x + B \overline{x} = A x + B \overline{x} + A B,

gdzie $A$ i $B$ są iloczynami niezawierającymi literału $x$ ani $\overline{x} .$

Metoda iteracyjnego konsensusu to iteracyjne wykonanie następujących kroków:

Usuń z postaci dysjunkcyjnej wszystkie pokryte implikanty.
Wygeneruj wszystkie (niepuste i różne od 0) konsensusy z par iloczynów. Dodaj je do postaci dysjunkcyjnej. Przejdź do kroku 1.

Algorytm kończy się w momencie, gdy nie możemy wygenerować nowych konsensusów, ponieważ uzyskane iloczyny to implikanty proste.

Przykład

Niech będzie dana funkcja:

f (a b c d) = \sum (1, 6, 7, 8, 10, 14, 15)

przedstawiona w postaci:

f (a b c d) = \overline{a} \overline{b} \overline{c} d + \overline{a} b c + a b c + a \overline{b} \overline{d} .

Krok 1. Nie ma implikantów pokrywanych przez inne implikanty.

Krok 2. $\overline{a} b c$ oraz $a b c$ tworzą konsensus $b c,$ który dodajemy do postaci dysjunkcyjnej, otrzymując:

f (a b c d) = \overline{a} \overline{b} \overline{c} d + \overline{a} b c + a b c + a \overline{b} \overline{d} + b c .

Krok 1′. Konsensus $b c$ pokrywa $\overline{a} b c$ oraz $a b c,$ dlatego usuwamy je z postaci dysjunkcyjnej, otrzymując:

f (a b c d) = \overline{a} \overline{b} \overline{c} d + a \overline{b} \overline{d} + b c .

Krok 2′. $a \overline{b} \overline{d}$ oraz $b c$ tworzą konsensus $a c \overline{d},$ który dodajemy do postaci dysjunkcyjnej, otrzymując:

f (a b c d) = \overline{a} \overline{b} \overline{c} d + a \overline{b} \overline{d} + b c + a c \overline{d} .

Krok 1″. Nie ma implikantów pokrywanych przez inne implikanty.

Krok 2″. Nie można wygenerować konsensusu różnego od pustego bądź różnego od 0, czyli algorytm się kończy.