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:

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

gdzie ${\displaystyle A}$ i ${\displaystyle B}$ są iloczynami niezawierającymi literału ${\displaystyle x}$ ani ${\displaystyle {\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.

Niech będzie dana funkcja:

${\displaystyle f(abcd)=\sum (1,6,7,8,10,14,15)}$

przedstawiona w postaci:

${\displaystyle 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. ${\displaystyle {\overline {a}}bc}$ oraz ${\displaystyle abc}$ tworzą konsensus ${\displaystyle bc,}$ który dodajemy do postaci dysjunkcyjnej, otrzymując:

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

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

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

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

${\displaystyle 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.

• funkcja boolowska
• konsensus