En álgebra de Boole , el método de Petrick [1] (también conocido como función de Petrick [2] o método de ramificación y enlace ) es una técnica descrita por Stanley R. Petrick (1931-2006) [3] [4] en 1956 [5 ] [6] para determinar todas las soluciones de suma mínima de productos a partir de un gráfico de implicantes primos . [7] El método de Petrick es muy tedioso para gráficos grandes, pero es fácil de implementar en una computadora. [7] El método fue mejorado por Insley B. Pyne y Edward Joseph McCluskey en 1962. [8] [9]
Algoritmo
- Reduzca la tabla de implicantes primos eliminando las filas de implicantes primos esenciales y las columnas correspondientes. [7]
- Etiquete las filas del gráfico de implicantes primos reducidos , , , , etc. [7]
- Forma una función lógica lo cual es cierto cuando se cubren todas las columnas. P consiste en un producto de sumas donde cada término de suma tiene la forma, donde cada representa una columna que cubre una fila . [7]
- Reducir a una suma mínima de productos multiplicando [nb 1] y aplicando la ley de absorción . [7]
- Cada término del resultado representa una solución, es decir, un conjunto de filas que cubre todos los términos mínimos de la tabla. Para determinar las soluciones mínimas, primero encuentre aquellos términos que contengan un número mínimo de implicantes primos. [7]
- Luego, para cada uno de los términos encontrados en el paso cinco, cuente el número de literales en cada implicante primo y encuentre el número total de literales. [7]
- Elija el término o términos compuestos por el número total mínimo de literales y escriba las sumas correspondientes de los implicantes primos. [7]
Ejemplo del método de Petrick
A continuación se muestra la función que queremos reducir: [10]
El gráfico de implicantes principales del algoritmo de Quine-McCluskey es el siguiente:
0 1 2 5 6 7 ⇒ A B C K = m (0,1) ⇒ 0 0 - L = m (0,2) ⇒ 0 - 0 M = m (1,5) ⇒ - 0 1 N = m (2,6) ⇒ - 1 0 P = m (5,7) ⇒ 1 - 1 Q = m (6,7) ⇒ 1 1 -
Con base en las marcas ✓ en la tabla anterior, construya un producto de las sumas de las filas donde se agrega cada fila y las columnas se multiplican juntas:
(K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)
Usa la ley distributiva para convertir esa expresión en una suma de productos. También use las siguientes equivalencias para simplificar la expresión final: X + XY = X y XX = X y 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
Ahora use nuevamente la siguiente equivalencia para reducir aún más la ecuación: X + XY = X
= KNP + KLPQ + LMNP + LMQ + KMNQ
Elija productos con menos términos, en este ejemplo, hay dos productos con tres términos:
KNP LMQ
Elija término o términos con la menor cantidad de literales totales. En nuestro ejemplo, los dos productos se expanden a seis literales en total cada uno:
KNP se expande a a'b '+ bc' + acLMQ se expande a a'c '+ b'c + ab
Entonces se puede usar cualquiera de los dos. En general, la aplicación del método de Petrick es tediosa para gráficos grandes, pero es fácil de implementar en una computadora. [7]
Notas
- ^ Esto provoca una explosión exponencial en el número de columnas.
Referencias
- ^ Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1 de abril de 1977). "2.3.6. Selección de los implicantes primos requeridos" . Análisis y Diseño de Sistemas Digitales Secuenciales . Ingeniería eléctrica y electrónica (1 ed.). Londres y Basingstoke, Reino Unido: The Macmillan Press Ltd. págs. 19, 77. doi : 10.1007 / 978-1-349-15757-0 . ISBN 0-333-19266-4. Archivado desde el original el 30 de abril de 2020 . Consultado el 30 de abril de 2020 . (4 + viii + 146 + 6 páginas)
- ^ Svoboda, Antonín ; White, Donnamaie E. (2016) [2012, 1985, 1 de agosto de 1979]. "9.9. La solución de la función de Petrick para la forma ΣΠ mínima de y" (PDF) . Técnicas avanzadas de diseño de circuitos lógicos (PDF) (reedición electrónica reescrita ed.). Garland STPM Press (edición original) / WhitePubs Enterprises, Inc. (reedición). págs. 148–150. ISBN 978-0-8240-7014-4. LCCN 78-31384 . Archivado (PDF) desde el original el 14 de abril de 2017 . Consultado el 15 de abril de 2017 . [1] [2]
- ^ "Nota biográfica" . Archivado desde el original el 13 de abril de 2017 . Consultado el 12 de abril de 2017 .
Stanley R. Petrick nació en Cedar Rapids, Iowa el 16 de agosto de 1931. Asistió a la Escuela Secundaria Roosevelt y recibió una licenciatura en Matemáticas de la Universidad Estatal de Iowa en 1953. Durante 1953 a 1955 asistió al MIT mientras estaba en servicio activo como un oficial de la Fuerza Aérea y recibió el título de SM del Departamento de Ingeniería Eléctrica en 1955. Fue elegido miembro de Sigma Xi en 1955. El
Sr. Petrick ha estado asociado con la Junta de Matemáticas Aplicadas del Laboratorio de Ciencias de Datos en los Laboratorios de Investigación de Cambridge de la Fuerza Aérea desde 1955 y sus estudios recientes en el MIT han sido apoyados parcialmente por AFCRL. Durante 1959-1962 ocupó el cargo de profesor de matemáticas en la División de Graduados de la tarde de la Northeastern University .
El Sr. Petrick es actualmente miembro de la Linguistic Society of America , The Linguistic Circle of New York , The American Mathematical Association , The Association for Computing Machinery y Association for Machine Translation and Computational Linguistics . - ^ "Obituarios - Cedar Rapids - Stanley R. Petrick" . La Gaceta . 2006-08-05. pag. 16. Archivado desde el original el 13 de abril de 2017 . Consultado el 12 de abril de 2017 .
[...] CEDAR RAPIDS Stanley R. Petrick, 74, antes de Cedar Rapids, murió el 27 de julio de 2006 en Presbyterian / St. Luke's Hospital, Denver, Colorado, luego de una batalla de 13 años contra la leucemia. Se llevará a cabo un servicio conmemorativo el 14 de agosto en la Iglesia Presbiteriana Unida en Laramie, Wyo., Donde vivió durante muchos años. [...] Stan Petrick nació en Cedar Rapids el 6 de agosto de 1931 de Catherine Hunt Petrick y Fred Petrick. Se graduó de Roosevelt High School en 1949 y recibió una licenciatura en matemáticas de la Universidad Estatal de Iowa . Stan se casó con Mary Ethel Buxton en 1953.
(NB. Incluye una foto de Stanley R. Petrick.)
Se unió a la Fuerza Aérea de los EE. UU. Y fue asignado como oficial estudiante de computación digital en el MIT , donde obtuvo una maestría. Luego fue asignado a la Rama de Matemáticas Aplicadas del Laboratorio de Investigación de Cambridge de la Fuerza Aérea y mientras estuvo allí obtuvo un doctorado. en lingüística.
Pasó 20 años en el Grupo Computacional Lingüística Teórica y del Departamento de Ciencias Matemáticas de IBM 's TJ Watson Research Center , la realización de investigaciones en la teoría del lenguaje formal. Se había desempeñado como subdirector del Departamento de Ciencias Matemáticas, presidente del Grupo de Interés Especial sobre Manipulación Simbólica y Algebraica de la Asociación de Maquinaria de Computación y presidente de la Asociación de Lingüística Computacional . Es autor de muchas publicaciones técnicas.
Enseñó tres años en la Northeastern University y 13 años en el Pratt Institute. El Dr. Petrick se unió a la Universidad de Wyoming en 1987, donde jugó un papel decisivo en el desarrollo e implementación del Ph.D. programa en el departamento y se desempeñó como asesor de tesis para muchos estudiantes de posgrado. Se jubiló en 1995. [...] - ^ Petrick, Stanley R. (10 de abril de 1956). Una determinación directa de las formas irredundantes de una función booleana a partir del conjunto de implicantes primos . Bedford, Cambridge, Massachusetts, EE.UU .: Centro de Investigación de Cambridge de la Fuerza Aérea . Informe técnico AFCRC TR-56-110.
- ^ Lewin, Douglas (1974) [1968]. Diseño lógico de funciones de conmutación (1981 7ª edición reimpresa de la 2ª ed.). Thomas Nelson and Sons Ltd / Van Nostrand Reinhold Co., Ltd. p. 60. ISBN 0-442-30747-0. ISBN 0-17-771044-6 . NCN 420-5805-4.
- ^ a b c d e f g h yo j Roth, Jr., Charles H. (1992). Fundamentos del diseño lógico (4 ed.). ISBN 0-31492218-0.
- ^ Pyne, Insley B .; McCluskey, Jr., Edward Joseph (1962). "La reducción de la redundancia en la resolución de tablas de implicantes primos". Transacciones IRE en computadoras electrónicas . EC-11 (4): 473–482.
- ^ Choudhury, Arun K. (febrero de 1968). "IB Pyne y EJ McCluskey Jr., La reducción de la redundancia en la resolución de tablas de implicantes primos. Transacciones IRE en computadoras electrónicas, vol. EC-11 (1962), págs. 473-482" . El diario de la lógica simbólica . Reseñas. Asociación de Lógica Simbólica (ASL). 32 (4): 540–541. doi : 10.2307 / 2270229 . JSTOR 2270229 .
- ^ Frenzel, James "Jim" F. (2007). "Conferencia # 10: Método de Petrick" . ECE 349 - Estudio de antecedentes sobre los fundamentos de la informática digital . Moscú, Idaho, EE.UU .: Departamento de Ingeniería Eléctrica e Informática, Universidad de Idaho . Archivado desde el original el 12 de abril de 2017 . Consultado el 8 de agosto de 2019 . [3]
Otras lecturas
- Krambeck, Donald (17 de febrero de 2016). "Simplificación del primer implicante utilizando el método de Petrick" . Todo sobre circuitos . EETech Media, LLC. Archivado desde el original el 12 de abril de 2017 . Consultado el 3 de abril de 2020 .
- Petrick, Stanley R. (1965). Un procedimiento de reconocimiento para gramáticas transformacionales (tesis doctoral). Instituto de Tecnología de Massachusetts .
- Bolton, Martin (1990). "4. Minimización". Escrito en la Universidad de Bristol, Bristol, Reino Unido. En Dagless, Erik L. (ed.). Diseño de Sistemas Digitales con Lógica Programable . Serie de Ingeniería de Sistemas Electrónicos (1 ed.). Wokingham, Reino Unido: Addison-Wesley Publishers Ltd. págs. 100–101, 115. ISBN 0-201-14545-6. LCCN 90000007 . ISBN 978-0-201-14545-8 arca: / 13960 / t2f83p38r . Consultado el 17 de abril de 2021 . (xiv + 379 + 1 páginas)
enlaces externos
- Tutorial sobre el método de Quine-McCluskey y Petrick
- Implementación de Petrick C ++ basada en el tutorial anterior