El método de Petrick

Algoritmo de minimización para el álgebra de Boole

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 acotación ) 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 diagrama de implicantes primos . ^[7] El método de Petrick es muy tedioso para diagramas 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

1. Reducir la tabla de implicantes primos eliminando las filas de implicantes primos esenciales y las columnas correspondientes. ^[7]
2. Etiqueta las filas de la tabla de implicantes primos reducida como , , , , etc. ^[7] ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle P_{3}}$ ${\displaystyle P_{4}}$
3. Forme una función lógica que sea verdadera cuando todas las columnas estén cubiertas. P consiste en un producto de sumas donde cada término de suma tiene la forma , donde cada uno representa una fila que cubre la columna . ^[7] ${\displaystyle P}$ ${\displaystyle (P_{i0}+P_{i1}+}$ ${\displaystyle \cdots }$ ${\displaystyle +P_{iN})}$ ${\displaystyle P_{ij}}$ ${\displaystyle i}$
4. Aplicar las leyes de De Morgan para expandir en una suma de productos ^{[nb 1]} y minimizar aplicando la ley de absorción . ^[7] ${\displaystyle P}$ ${\displaystyle X+XY=X}$
5. Cada término del resultado representa una solución, es decir, un conjunto de filas que cubre todos los mintérminos de la tabla. Para determinar las soluciones mínimas, primero hay que encontrar aquellos términos que contienen un número mínimo de implicantes primos. ^[7]
6. A continuación, 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]
7. Elija el término o términos compuestos por el número total mínimo de literales y escriba las sumas correspondientes de implicantes primos. ^[7]

Ejemplo del método de Petrick

La siguiente es la función que queremos reducir: ^[10]

${\displaystyle f(A,B,C)=\sum m(0,1,2,5,6,7)=A'B'C'+A'B'C+A'BC'+AB'C+ABC'+ABC}$

El gráfico de implicantes primos del algoritmo de Quine-McCluskey es el siguiente:

Con base en las marcas ✓ de la tabla anterior, construya un producto de sumas de las filas. Cada columna de la tabla forma un término de producto que suma las filas que tienen una marca ✓ en esa columna:

(K+L)(K+M)(L+N)(M+P)(N+Q)(P+Q)

Utilice la ley distributiva para convertir esa expresión en una suma de productos. Utilice también 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 utilice 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:

PNC LMQ

Tomando como referencia la tabla de implicantes primos, transforma cada producto reemplazando los implicantes primos por su expresión como variables booleanas y sustituye el producto por una suma. Luego, elige el resultado que contenga la menor cantidad de literales totales (variables booleanas y sus complementos). Tomando como referencia nuestro ejemplo:

KNP se expande a A'B' + BC' + AC donde K se convierte en A'B', N se convierte en BC', etc.LMQ se expande a A'C' + B'C + AB

Ambos productos se expanden a seis literales cada uno, por lo que se puede utilizar cualquiera de ellos. 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

1. Esto provoca un aumento exponencial en el número de columnas: expandir el producto de sumas que tienen términos generalmente da como resultado una suma con términos. ${\displaystyle k}$ ${\displaystyle n_{1},n_{2},...,n_{k}}$ ${\displaystyle n_{1}n_{2}...n_{k}}$

Referencias

1. 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-4Archivado desde el original el 30 de abril de 2020. Consultado el 30 de abril de 2020 .(4+viii+146+6 páginas)
2. Svoboda, Antonín ; White, Donnamaie E. (2016) [2012, 1985, 1979-08-01]. "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) (edición reeditada electrónicamente). Garland STPM Press (edición original) / WhitePubs Enterprises, Inc. (reedición). pp. 148–150. ISBN 978-0-8240-7014-4LCCN  78-31384. Archivado (PDF) del original el 14 de abril de 2017. Consultado el 15 de abril de 2017 .[1] [2]
3. "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 Roosevelt High School y recibió una licenciatura en Matemáticas de la Iowa State University en 1953. Durante 1953 a 1955 asistió al MIT mientras estaba en servicio activo como oficial de la Fuerza Aérea y recibió el título de S. M. 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 parcialmente financiados por AFCRL. Entre 1959 y 1962 ocupó el cargo de profesor de matemáticas en la División de Posgrado Nocturna de la Universidad de Northeastern . Actualmente, el Sr. Petrick es miembro de la Sociedad Lingüística de Estados Unidos , el Círculo Lingüístico de Nueva York , la Asociación Matemática Estadounidense , la Asociación para Maquinaria Computacional y la Asociación para la Traducción Automática y la Lingüística Computacional .
   
   
4. "Obituarios - Cedar Rapids - Stanley R. Petrick". The Gazette . 2006-08-05. p. 16. Archivado desde el original el 2017-04-13 . Consultado el 2017-04-12 . [...] CEDAR RAPIDS Stanley R. Petrick, de 74 años, ex residente de Cedar Rapids, murió el 27 de julio de 2006 en el Presbyterian/St. Luke's Hospital, Denver, Colorado, después 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, hijo de Catherine Hunt Petrick y Fred Petrick. Se graduó de la Roosevelt High School en 1949 y recibió una licenciatura en matemáticas de la Iowa State University . Stan se casó con Mary Ethel Buxton en 1953. Se unió a la Fuerza Aérea de los EE. UU. y fue asignado como oficial estudiante estudiando 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 estaba allí obtuvo un doctorado en lingüística. Pasó 20 años en el Grupo de Lingüística Teórica y Computacional del Departamento de Ciencias Matemáticas en el Centro de Investigación TJ Watson de IBM , realizando investigaciones en 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 para Maquinaria Computacional y presidente de la Asociación para Lingüística Computacional . Fue autor de muchas publicaciones técnicas. Enseñó tres años en la Universidad Northeastern y 13 años en el Instituto Pratt. El Dr. Petrick se unió a la Universidad de Wyoming en 1987, donde fue fundamental en el desarrollo e implementación del doctorado. Programa en el departamento y se desempeñó como asesor de tesis para muchos estudiantes de posgrado. Se jubiló en 1995. [...]
   
   
   (NB. Incluye una foto de Stanley R. Petrick.)
5. Petrick, Stanley R. (1956-04-10). 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 la Fuerza Aérea de Cambridge . Informe técnico TR-56-110 del AFCRC.
6. 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ág. 60. ISBN 0-442-30747-0. ISBN 0-17-771044-6 . NCN 420-5805-4. 
7. Roth, Jr., Charles H. (1992). Fundamentos del diseño lógico (4.ª edición). West Publishing Company. ISBN 0-31492218-0.
8. Pyne, Insley B.; McCluskey, Jr., Edward Joseph (1962). "La reducción de redundancia en la resolución de tablas de implicantes primos". IRE Transactions on Electronic Computers . EC-11 (4): 473–482.
9. 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". The Journal of Symbolic Logic . Reseñas. 32 (4). Association for Symbolic Logic (ASL): 540–541. doi :10.2307/2270229. JSTOR  2270229. S2CID  57871609.
10. Frenzel, James "Jim" F. (2007). "Conferencia n.° 10: El método de Petrick". ECE 349: estudio de antecedentes sobre los fundamentos de las computadoras digitales . Moscú, Idaho, EE. UU.: Departamento de Ingeniería Eléctrica y Computacional, Universidad de Idaho . Archivado desde el original el 12 de abril de 2017. Consultado el 8 de agosto de 2019 .[3]

Lectura adicional

• Krambeck, Donald (17 de febrero de 2016). "Simplificación de implicantes primos mediante 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 Tecnológico 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. pp. 100–101, 115. ISBN 0-201-14545-6. LCCN  90000007. ISBN 978-0-201-14545-8 ark:/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