Metoda iteracyjnego konsensusu

Z Wikipedii

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:

gdzie A i B są iloczynami nie zawierającymi literału ani .

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.

[edytuj] Przykład

Niech będzie dana funkcja:

przedstawiona w postaci:

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

Krok 2. oraz tworzą konsensus , który dodajemy do postaci dysjunkcyjnej, otrzymując:

Krok 1`. Konsensus pokrywa oraz , dlatego usuwamy je z postaci dysjunkcyjnej otrzymując:

Krok 2`. oraz tworzą konsensus , który dodajemy do postaci dysjunkcyjnej, otrzymując:

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 algorym się kończy.

[edytuj] Zobacz też

• funkcja boolowska
• konsensus