| dbo:abstract
|
- In Boolean algebra, Petrick's method (also known as Petrick function or branch-and-bound method) is a technique described by Stanley R. Petrick (1931–2006) in 1956 for determining all minimum sum-of-products solutions from a prime implicant chart. Petrick's method is very tedious for large charts, but it is easy to implement on a computer. The method was improved by and Edward Joseph McCluskey in 1962. (en)
- Il metodo di Petrick è un algoritmo di risoluzione dei mintermini contenuti in una tabella degli implicanti primi ricavata con il metodo di Quine-McCluskey. Tale metodo, che semplifica la copertura trasponendola in forma algebrica, risulta scomodo per tabelle molto grandi, in quanto valuta tutte le possibili soluzioni, ma è facilmente implementabile in un computer tramite algoritmi di branch and bound. Il metodo di Petrick opera seguendo questi passaggi: 1.
* Riduzione della tabella degli implicanti primi eliminando le righe contenenti implicanti primi essenziali (e le rispettive colonne); 2.
* Etichettatura delle righe della tabella ridotta ; 3.
* Costruzione di una funzione logica tale che sia vera quando tutte le colonne sono coperte ( è costituita da un prodotto di somme, dove ogni termine di somma ha la forma , in cui rappresentano una riga che copre la colonna ); 4.
* Minimizzazione di in somma di prodotti applicando l'equivalenza (ciascun termine nel risultato rappresenta una soluzione, ovvero un insieme di righe che copre tutti i mintermini della tabella); 5.
* Determinazione delle soluzioni minime individuando quei termini che contengono il minor numero di implicanti primi; 6.
* Conteggio del numero dei letterali in ciascun implicante primo dei termini trovati precedentemente e ricerca del numero totale di letterali; 7.
* Scelta dei termini formati dal minor numero totale di letterali e scrittura delle corrispondenti somme di implicanti primi. (it)
- Metoda Petricka znana również jako w algebrze Boole’a została opisana przez (1931–2006) w 1956 roku do określenia wszystkich rozwiązań minimalnych sum iloczynów metody Quine’a-McCluskeya. Metoda Petricka jest bardzo żmudna dla dużej liczby zmiennych, ale jest łatwa do implementacji na komputerze. 1.
* Redukujemy wykres implikantów prostych przez eliminację istotnych implikantów prostych – ich wierszy i odpowiednich kolumn. 2.
* Oznaczamy wiersze zredukowanego wykresu przez itd. 3.
* Tworzymy funkcję logiczną która jest true, kiedy wszystkie kolumny są pokryte. P składa się z iloczynu sum, gdzie każda suma ma postać gdzie każdy reprezentuje wiersz pokrywający kolumnę 4.
* Redukujemy do minimalnej sumy iloczynów przez wymnożenie i zastosowanie 5.
* Każdy człon rezultatu prezentuje rozwiązanie, to znaczy zbiór wierszy, które pokrywają wszystkie iloczyny zupełne tabeli. Aby określić minimalne rozwiązania, najpierw znajdujemy te człony, które zawierają minimalną liczbę implikantów prostych. 6.
* Następnie dla każdego członu znalezionego w kroku 6, zliczamy liczbę literałów w każdym implikancie prostym i znajdujemy ogólną liczbę literałów. 7.
* Wybieramy ten człon albo człony, które są złożone z minimalnej ogólnej liczby literałów i zapisujemy odpowiednie sumy implikantów prostych. Przykład metody Petricka Zredukujmy następującą funkcję: Wykres implikantów prostych z metody Quine’a-McCluskeya przedstawia się: (uwaga, inaczej niż w punkcie 2, oznaczyliśmy wiersze literami K..Q) | 0 1 2 5 6 7 ---------------|------------ K (0,1) a'b' | X X L (0,2) a'c' | X X M (1,5) b'c | X X N (2,6) bc' | X X P (5,7) ac | X X Q (6,7) ab | X X Bazując na znaku X-tej tabeli, budujemy iloczyn sum wierszy, gdzie każdy wiersz jest dodawany, a kolumny są mnożone razem: (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) Używamy prawa rozdzielności, aby uzyskać sumę iloczynów. Również używamy następujących równoważności do uproszczeń: X + XY = X i XX = X i X+X=X. Z tych uproszczeń wynika, że (A+B)(A+C) = AA+BA+AC+BC = A+BA+AC+BC = A+AC+BC = A+BC, których użyjemy na początku, aby zredukować liczbę elementów iloczynu. Poza tym A(A+B)=A (A+B)(A+CD)=A+BCD (A+B)(A+C+D) = A+BC+BD = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+LM)(N+LQ)(P+MQ) To pierwsze przekształcenie można wykonać, tworząc tablicę N×N, gdzie N to liczba kolumn |0 1 2 5 6 7 ----|------------ 0 |\_X X 1 | \_ X 2 | \_ X 5 | \_ X 6 | \_X 7 | \ Oznaczamy przez X wiersz n, kolumnę m, gdy literał występuje zarówno w n, jak i m. Mając teraz zaznaczone, wybieramy (0,1) , wykreślamy rząd 0 i 1, następnie (2,6), wykreślamy 2 i 6 i zostaje (5,7).Mając (2,6), mnożymy 2-gą i 6-tą sumę przez siebie. = (KN+KLQ+LMN+LMQ)(P+MQ) Mnożymy pierwszą i drugą sumę, każdy z każdym. Na razie nic nie da się uprościć w pierwszym nawiasie, bo żaden człon nie zawiera w całości innego (aby zastosować X + XY = X)Mnożymy ostatecznie to co w nawiasie przez ostatni człon: = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ Teraz używamy znowu X + XY = X do uproszczania = KNP + KLPQ + LMNP + KMNQ + LMQ skracamy, bo LMPQ,KLMQ i LMNQ zawierają LMQ. Wybieramy iloczyny z minimalną liczbą składników. W tym przypadku będą dwa iloczyny z trzema składnikami: KNP LMQ Wybieramy iloczyny z najmniejszą liczbą literałów razem. W naszym przypadku obydwa iloczyny będą miały po 6 literałów: KNP rozwija się do a'b'+ bc'+ acLMQ rozwija się do a'c'+ b'c + ab Może być użyty albo jeden, albo drugi. (pl)
- Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 1956 году американским учёным Стэнли Роем Петриком (1931—2006). Метод Петрика довольно сложно применять для больших таблиц, но очень легко реализовать программно. (ru)
- У булевій алгебрі метод Патрика — техніка для визначення всіх мінімальних ДНФ рішень для таблиці простих імплікант, яку запропонував (1931–2006) у 1956 році. Метод Петрика дуже стомливий для великих таблиць, але його дуже просто реалізувати на комп'ютері. 1.
* Зменшити таблицю простих імплікант шляхом виключення рядків основних простих імплікантів (ядер) і відповідних стовпців. 2.
* Помітити рядки зменшеної таблиці простих імплікант , , , і т.д.. 3.
* Сформувати логічну функцію яка приймає значення 1 коли всі стовпці покриті. P є КНФ де кожна диз'юнкція має таку форму , де кожна представляє рядок, що покриває стовпець . 4.
* Зменшити до мінімальної ДНФ множенням і застосуванням . 5.
* Кожний терм в результаті представляє розв'язок, набір рядків, які покривають всі мінтерми в таблиці. Для визначення мінімального розв'язку спочатку знаходяться ті терми, які містять мінімальну кількість простих імплікант. 6.
* Далі, для кожного терма знайденого на попередньому кроці, підраховуються кількість літералів в кожній основній імліканті і знаходять загальну кількість літералів. 7.
* Обирають терм або терми, що утворені мінімальною кількістю літералів, і записують відповідні диз'юнкції основних імплікант. Приклад методу Патрика (скопійовано з http://www.mrc.uidaho.edu/mrc/people/jff/349/lect.10) Наступну функцію ми бажаємо зменшити: Таблиця основних імплікантів отримана методом Куайна — Мак Класкі наступна: 0 1 2 5 6 7 ---------------|------------ K (0,1) a'b' | X X L (0,2) a'c' | X X M (1,5) b'c | X X N (2,6) bc' | X X P (5,7) ac | X X Q (6,7) ab | X X Ґрунтуючись на позначках Х в попередній таблиці, будуємо КНФ згідно з третім кроком: (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) Використовуємо дистрибутивний закон, щоб перевести цей вираз в ДНФ. Також використовуємо такі еквівалентності для спрощення результату: X + XY = X і XX = X і X+X=X = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+LM)(N+LQ)(P+MQ) = (KN+KLQ+LMN+LMQ)(P+MQ) = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ Тепер знову використовуємо X + XY = X для подальшого спрощення. = KNP + KLPQ + LMNP + LMQ + KMNQ Обираємо добутки з найменшою кількістю термів, в нашому випадку це два добутки по три терма: KNP LMQ Обираємо терми з найменшою кількістю літералів. В нашому випадку обидва добутки розкладаються в 6 літералів кожен: KNP розкладається в a'b'+ bc'+ acLMQ розкладається в a'c'+ b'c + ab Таким чином один з них може бути використаний. Взагалі застосування методу Петрика стомлююче для великих таблиць, але легко реалізується на комп'ютері. (uk)
|
| rdfs:comment
|
- In Boolean algebra, Petrick's method (also known as Petrick function or branch-and-bound method) is a technique described by Stanley R. Petrick (1931–2006) in 1956 for determining all minimum sum-of-products solutions from a prime implicant chart. Petrick's method is very tedious for large charts, but it is easy to implement on a computer. The method was improved by and Edward Joseph McCluskey in 1962. (en)
- Метод Петрика — метод для получения всех минимальных ДНФ из таблицы простых импликант. Предложен в 1956 году американским учёным Стэнли Роем Петриком (1931—2006). Метод Петрика довольно сложно применять для больших таблиц, но очень легко реализовать программно. (ru)
- Il metodo di Petrick è un algoritmo di risoluzione dei mintermini contenuti in una tabella degli implicanti primi ricavata con il metodo di Quine-McCluskey. Tale metodo, che semplifica la copertura trasponendola in forma algebrica, risulta scomodo per tabelle molto grandi, in quanto valuta tutte le possibili soluzioni, ma è facilmente implementabile in un computer tramite algoritmi di branch and bound. Il metodo di Petrick opera seguendo questi passaggi: (it)
- Metoda Petricka znana również jako w algebrze Boole’a została opisana przez (1931–2006) w 1956 roku do określenia wszystkich rozwiązań minimalnych sum iloczynów metody Quine’a-McCluskeya. Metoda Petricka jest bardzo żmudna dla dużej liczby zmiennych, ale jest łatwa do implementacji na komputerze. Przykład metody Petricka Zredukujmy następującą funkcję: Wykres implikantów prostych z metody Quine’a-McCluskeya przedstawia się: (uwaga, inaczej niż w punkcie 2, oznaczyliśmy wiersze literami K..Q) (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) = (K+LM)(N+LQ)(P+MQ) KNP LMQ (pl)
- У булевій алгебрі метод Патрика — техніка для визначення всіх мінімальних ДНФ рішень для таблиці простих імплікант, яку запропонував (1931–2006) у 1956 році. Метод Петрика дуже стомливий для великих таблиць, але його дуже просто реалізувати на комп'ютері. Приклад методу Патрика (скопійовано з http://www.mrc.uidaho.edu/mrc/people/jff/349/lect.10) Наступну функцію ми бажаємо зменшити: Таблиця основних імплікантів отримана методом Куайна — Мак Класкі наступна: Ґрунтуючись на позначках Х в попередній таблиці, будуємо КНФ згідно з третім кроком: (K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q) KNP LMQ (uk)
|
