PROFILPELAJAR.COM

У булевій алгебрі метод Патрика — техніка для визначення всіх мінімальних ДНФ рішень для таблиці простих імплікант, яку запропонував Стенлі Р. Петрик (1931–2006)^[1]^[2] у 1956^[3] році. Метод Петрика дуже стомливий для великих таблиць, але його дуже просто реалізувати на комп'ютері.

Зменшити таблицю простих імплікант шляхом виключення рядків основних простих імплікантів (ядер) і відповідних стовпців.
Помітити рядки зменшеної таблиці простих імплікант $P_{1}$ , $P_{2}$ , $P_{3}$ , $P_{4}$ і т.д..
Сформувати логічну функцію $P$ яка приймає значення 1 коли всі стовпці покриті. P є КНФ де кожна диз'юнкція має таку форму $(P_{i0}+P_{i1}+$ $\cdots$ $+P_{iN})$ , де кожна $P_{ij}$ представляє рядок, що покриває стовпець $i$ .
Зменшити $P$ до мінімальної ДНФ множенням і застосуванням $X+XY=X$ .
Кожний терм в результаті представляє розв'язок, набір рядків, які покривають всі мінтерми в таблиці. Для визначення мінімального розв'язку спочатку знаходяться ті терми, які містять мінімальну кількість простих імплікант.
Далі, для кожного терма знайденого на попередньому кроці, підраховуються кількість літералів в кожній основній імліканті і знаходять загальну кількість літералів.
Обирають терм або терми, що утворені мінімальною кількістю літералів, і записують відповідні диз'юнкції основних імплікант.

Приклад методу Патрика (скопійовано з http://www.mrc.uidaho.edu/mrc/people/jff/349/lect.10)

Наступну функцію ми бажаємо зменшити:

f(A,B,C)=\sum m(0,1,2,5,6,7)\,

Таблиця основних імплікантів отримана методом Куайна — Мак Класкі наступна:

                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'+ ac
LMQ    розкладається в    a'c'+ b'c + ab

Таким чином один з них може бути використаний. Взагалі застосування методу Петрика стомлююче для великих таблиць, але легко реалізується на комп'ютері.

Примітки

↑ (Unknown). Biographical note. Архів оригіналу за 13 квітня 2017. Процитовано 12 квітня 2017. Stanley R. Petrick was born in Cedar Rapids, Iowa on August 16, 1931. He attended the Roosevelt High School and received a B. S. degree in Mathematics from the Iowa State University in 1953. During 1953 to 1955 he attended MIT while on active duty as an Air Force officer and received the S. M. degree from the Department of Electrical Engineering in 1955. He was elected to Sigma Xi in 1955.
Mr. Petrick has been associated with the Applied Mathematics Board of the Data Sciences Laboratory at the Air Force Cambridge Research Laboratories since 1955 and his recent studies at MIT have been partially supported by AFCRL. During 1959-1962 he held the position of Lecturer in Mathematics in the Evening Graduate Division of Northeastern University.
Mr. Petrick is currently a member of the Linguistic Society of America, The Linguistic Circle of New York, The American Mathematical Association, The Association for Computing Machinery, and the Association for Machine Translation and Computational Linguistics.
↑ Obituaries - Cedar Rapids - Stanley R. Petrick. The Gazette. 5 серпня 2006. с. 16. Архів оригіналу за 13 квітня 2017. Процитовано 12 квітня 2017. […] CEDAR RAPIDS Stanley R. Petrick, 74, formerly of Cedar Rapids, died July 27, 2006, in Presbyterian/St. Luke's Hospital, Denver, Colo., following a 13-year battle with leukemia. A memorial service will be held Aug. 14 at the United Presbyterian Church in Laramie, Wyo., where he lived for many years. […] Stan Petrick was born in Cedar Rapids on Aug. 6, 1931 to Catherine Hunt Petrick and Fred Petrick. He graduated from Roosevelt High School in 1949 and received a B.S. degree in mathematics from Iowa State University. Stan married Mary Ethel Buxton in 1953.
He joined the U.S. Air Force and was assigned as a student officer studying digital computation at MIT, where he earned an M.S. degree. He was then assigned to the Applied Mathematics Branch of the Air Force Cambridge Research Laboratory and while there earned a Ph.D. in linguistics.
He spent 20 years in the Theoretical and Computational Linguistics Group of the Mathematical Sciences Department at IBM's T.J. Watson Research Center, conducting research in formal language theory. He had served as an assistant director of the Mathematical Sciences Department, chairman of the Special Interest Group on Symbolic and Algebraic Manipulation of the Association for Computing Machinery and president of the Association for Computational Linguistics. He authored many technical publications.
He taught three years at Northeastern University and 13 years at the Pratt Institute. Dr. Petrick joined the University of Wyoming in 1987, where he was instrumental in developing and implementing the Ph.D. program in the department and served as a thesis adviser for many graduate students. He retired in 1995. […] (NB. Includes a photo of Stanley R. Petrick.)
↑ Petrick, Stanley R. (10 квітня 1956). A Direct Determination of the Irredundant Forms of a Boolean Function from the Set of Prime Implicants. Bedford, Cambridge, MA, USA: Air Force Cambridge Research Center. AFCRC Technical Report TR-56-110.