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:
- 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.
[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.