Método de Petrik

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de octubre de 2021; las comprobaciones requieren 3 ediciones .

El método de Petrik es un método para obtener todos los DNF mínimos de una tabla de implicantes primos . Fue propuesto en 1956 por el científico estadounidense Stanley Roy Petrik (1931-2006) [1] . El método de Petrik es bastante difícil de aplicar para tablas grandes, pero es muy fácil de implementar mediante programación.

Algoritmo

Simplifique la tabla de implicantes primos eliminando los implicantes necesarios y sus términos correspondientes.
Designe las filas de la tabla simplificada: , etc. ${\ estilo de visualización P_{1},P_{2},P_{3},P_{4))$
Forme una función booleana que sea verdadera cuando todas las columnas estén cubiertas. consiste en un CNF en el que cada conjunto tiene la forma , donde cada variable es una fila que cubre una columna . $PAGS$ $PAGS$ $(P_{i0}+P_{i1}+\cdots +P_{iN})$ ${\ Displaystyle P_ {ij}}$ $i$
Simplifique al mínimo DNF multiplicando y aplicando , y . $PAGS$ ${\ estilo de visualización X + XY = X}$ ${\ estilo de visualización XX = X}$ ${\ estilo de visualización X + X = X}$
Cada cláusula en el resultado representa una solución, es decir, un conjunto de filas que cubren todos los minitérminos en la tabla de implicantes primos.
Luego, para cada solución encontrada en el paso 5, debe contar la cantidad de literales en cada implicante primo.
Seleccione un término (o términos) que contengan el número mínimo de literales y escriba el resultado.

Ejemplo

Existe una función booleana de tres variables, dada por la suma de minitérminos:

$f(A,B,C)=\sum m(0,1,2,5,6,7)\,$ Tabla de implicantes primos del método de Quine-McCluskey :

	0	una	2	5	6	7
k ( ) ${\ estilo de visualización {\ bar {a}} {\ bar {b}}}$	✓	✓
L ( ) ${\ estilo de visualización {\ bar {a}} {\ bar {c}}}$	✓		✓
M ( ) ${\ estilo de visualización {\ bar {b}} c}$		✓		✓
norte ( ) $b{\bar {c))$			✓		✓
pag ( ) $C.A$				✓		✓
Q ( ) $abdominales$					✓	✓

Según las notas en la tabla anterior, escribimos el CNF (se agregan filas, sus sumas se multiplican):

${\ estilo de visualización (K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)}$

Usando la propiedad de distributividad, invertimos la expresión en DNF. También usaremos las siguientes equivalencias para simplificar la expresión: , y . ${\ estilo de visualización X + XY = X}$ ${\ estilo de visualización XX = X}$ ${\ estilo de visualización X + X = X}$

{\ estilo de visualización = (K + L) (K + M) (L + N) (M + P) (N + Q) (P + Q)}

{\ estilo de visualización = (K + LM) (N + LQ) (P + MQ)}

{\ estilo de visualización = (KN + KLQ + LMN + LMQ) (P + MQ)}

{\ estilo de visualización = KNP + KLPQ + LMNP + LMPQ + KMNQ + KLMQ + LMNQ + LMQ}

Ahora usamos de nuevo para una mayor simplificación: ${\ estilo de visualización X + XY = X}$

{\ estilo de visualización = KNP + KLPQ + LMNP + LMQ + KMNQ}

Elegimos productos con el menor número de variables y son . ${\ Displaystyle KNP}$ ${\ estilo de visualización LMQ}$

Elegimos el término con el menor número de literales. En nuestro caso, ambos productos se expanden a seis literales:

${\ Displaystyle KNP}$ se expande en ${\bar {a}}{\bar {b}}+b{\bar {c}}+ac$
${\ estilo de visualización LMQ}$ se expande en ${\bar {a}}{\bar {c}}+{\bar {b}}c+ab$

Por lo tanto, ambos términos son mínimos.

Notas

↑ Nota biográfica . Archivado desde el original el 13 de abril de 2017. (indefinido)