Despedida

MÉTODO DE QUINE McCLUSKEY
________________________________________
Introducción
En matemáticas las expresiones booleanas se simplifican por numerosas razones:
- Una expresión más simple es más fácil de entender y tiene menos posibilidades de error a la hora de su interpretación.
- Una expresión simplificada suelen ser más eficiente y efectiva cuando se implementan en la práctica, como en elcaso de circuitos eléctricos o en determinados algoritmos.
El método de Quine-McCluskey es particularmente útil cuando se tienen funciones con un gran número de variables, no es el caso del método de Karnaugh, que se hace impracticable con más de cinco variables. En nuestro caso, como el máximo número de variables será cuatro podremos utilizar conjuntamente ambos métodos.
Una expresiónbooleana se compone de variables y términos. Para este método las variables sólo podrán tener un valor numérico de cero (el correspondiente al valor de verdad false) o uno (el correspondiente al valor de verdad true) y se designarán mediante una letra.
Como notación se designará x si la variable contiene el valor uno, x’ en caso de que contenga el valor cero.
Por otra parte, las variables serelacionarán entre sí únicamente mediante operaciones lógicas and para formar términos y mediante or para relacionarse con otros términos constituyendo una suma de productos. Ésta debe de ser canónica, es decir:
- Cada variable se usa una vez en cada término. A dichos términos se les llama términos canónicos.
P.ejemplo f(x,y,j) = x’y z +x y’z
x’y z se representa con 011, donde x = 0, y = 1, z= 1
x y’z se representa con 101, donde x = 1, y = 0, z = 1

Metodo de Quine-McCluskey
Il metodo di Quine-McCluskey (o metodo degli implicanti primi) è un algoritmo sviluppato da Willard Van Orman Quine ed Edward McCluskey che viene utilizzato nelle reti combinatorie a due livelli di logica per la minimizzazione di una funzione booleana di n variabili. Il metodo è funzionalmente identico allamappa di Karnaugh, ma la sua forma tabellare lo rende più efficiente per essere realizzato al computer; inoltre fornisce anche un modo deterministico per testare la minimizzazione di una funzione booleana.
Il metodo consiste in due passi:
1. Identificare tutti gli implicanti primi della funzione.
2. Riportare gli implicanti primi trovati in una tabella per ricavare gli implicanti primiessenziali della funzione.
Complessità
Sebbene sia più pratico rispetto alle mappe di Karnaugh per funzioni con più di 4 variabili, il metodo di Quine-McCluskey ha comunque un intervallo limitato di utilizzo, poiché il problema che l'algoritmo risolve (la soddisfacibilità booleana) è NP-difficile: il suo runtime cresce esponenzialmente all'aumentare del numero degli ingressi. Si può dimostrare cheper una funzione di n variabili il limite superiore sul numero di implicanti primi è 3n/n. Se n = 32 ci possono essere più di 6.5 * 1015 implicanti primi. Pertanto, le funzioni con un grande numero di variabili booleane deve essere minimizzato con metodi euristici, come ad esempio il minimizzatore logico Espresso.
Metodo
Il metodo consiste in due fasi principali: la ricerca degli implicantiprimi e la successiva ricerca della copertura ottimale. Consideriamo la minimizzazione in forma di somma di prodotti (detta anche SOP, dall'acronimo inglese sum of products), ma il tutto è facilmente estendibile alla forma di prodotto di somme (o POS, product of sums).
Nella prima fase si applica sistematicamente la semplificazione del tipo:

cioè la proprietà distributiva del prodotto rispettoalla somma, dove P indica un qualsiasi termine prodotto (mintermine). Ovviamente il metodo è estendibile anche a funzioni non completamente specificate e anche a circuiti multiuscita. La prima fase consiste dei passi:
1. tabellare tutti i mintermini della funzione in forma binaria, in ordine crescente come per la tabella della verità;
2. confrontare tra loro tutti i termini esaustivamente: si...