Metoda iteracyjnego konsensusu

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:

$Ax+B{\overline {x}}=Ax+B{\overline {x}}+AB,$

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:

1. Usuń z postaci dysjunkcyjnej wszystkie pokryte implikanty.
2. 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(abcd)=\sum (1,6,7,8,10,14,15)$

przedstawiona w postaci:

$f(abcd)={\overline {a}}{\overline {b}}{\overline {c}}d+{\overline {a}}bc+abc+a{\overline {b}}{\overline {d}}.$

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

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

$f(abcd)={\overline {a}}{\overline {b}}{\overline {c}}d+{\overline {a}}bc+abc+a{\overline {b}}{\overline {d}}+bc.$

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

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

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

$f(abcd)={\overline {a}}{\overline {b}}{\overline {c}}d+a{\overline {b}}{\overline {d}}+bc+ac{\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.

Zobacz też

• funkcja boolowska
• konsensus