Eletronica Digital

Simplificação de Funções Lógicas pelo Método de Quine-McCluskey
1. Introdução:

O método de simplificação de funções lógicas, proposto por Quine-McCluskey, diferente do método de Karnaugh, não apresenta limitação no número de variáveis de entrada e, por ser um algoritmo, sempre irá levar a obtenção da Mínima Soma de Produtos ou do Mínimo Produto de Somas. Por não ser um método gráfico como ode Karnaugh, para se chegar ao resultado, é necessário, via de regra, mais tempo. Este método é eficiente quando implementado em computadores. 2. O Método de Simplificação de Quine-McCluskey

Como será visto, o algoritmo, proposto por Quine-McCluskey para a simplificações de funções lógicas, consistirá em:

Selecionar o menor subconjunto de objetos, D, de um conjunto de objetos, A, tal que ummesmo critério f seja satisfeito.
Para chegar à expressão Mínima Soma de Produtos, a partir do conjunto, A, formado por todos os implicantes primos contidos pela função f, deve-se obter o subconjunto, D, que consistirá dos produtos que a determinarão e que deverão estar de acordo com a definição dada a seguir.

Definição 1: Uma expressão lógica soma de produtos será dita mínima se satisfizer asseguintes condições: (1) não existe nenhuma outra expressão equivalente envolvendo um menor número de produtos; (2) não existe nenhuma expressão equivalente envolvendo o mesmo número de produtos, porém com menor número de variáveis.
O primeiro passo para obtenção da Mínima Soma de Produtos consistirá em determinar os implicantes primos, a partir de uma expressão lógica Soma de Produtos Canônicosou Soma de Mintermos. Se a função não estiver nesta forma deve-se convertê-la pelo métodos já estudados.

Criado por Prof. Evandro Vieiralves

1

Definição 2: Um implicante primo é qualquer cubo-r, constituído de agrupamentos de 1’s , de uma função que não está contido em um cubo de maior dimensão.
Vamos ilustrar o método desenvolvido por Quine-McCluskey através de exemplos. Exemplo 1.Considere a função, dada a seguir f (A,B,C,D) = Σ m (0,1,5,6,7,8,9,10,11,14) O primeiro passo a ser realizado, é converter os mintermos em suas correspondentes formas binárias. Para sistematizar este procedimento utiliza-se uma tabela de conversão dos mintermos nas correspondentes representações binárias e coloca-se na coluna ao lado da representação binária o número de 1's do mintermo, conformeilustrado a seguir.

Mintermo Representação Binária Número de 1's m0 0000 0 m1 0001 1 m5 0101 2 m6 0110 2 m7 0111 3 m8 1000 1 m9 1001 2 m10 1010 2 m11 1011 3 m14 1110 3
Tabela 1

Uma vez determinadas suas formas binárias, os mintermos serão agrupados em uma tabela de cubos-0 de acordo com os seguintes critérios: • A Tabela-2 é formada por grupos de mintermos que apresentam o mesmo números de 1'sem sua representação binária. Os grupos informam o número de 1's dos mintermos, os mintermos propriamente ditos e suas respectivas representações binárias; • O primeiro grupo é iniciado pelo(s) mintermo(s) que apresenta(m) o menor número de 1's, ordenados em ordem crescente, em suas respectivas representações binárias; • Os grupos são separados por uma linha horizontal.
No de 1’s na representaçãobinária Cubos-0

Criado por Prof. Evandro Vieiralves

2

0 1

2

3 Tabela 2

m0 m1 m8 m5 m6 m9 m10 m7 m11 m14

0000 0001 1000 0101 0110 1001 1010 0111 1011 1110

O método proposto por Quine-McCluskey consiste em combinar cubos-0 para formar cubos-1 (pares); cubos-1 para formar cubos-2 (quadras), cubos-2 para formar cubos-3 (oitavas), e assim sucessivamente. Partindo-se da Tabela2, deve-se pesquisar a possibilidade de combinação de cada um dos cubos-0 de um grupo com os cubos-0 do grupo imediatamente inferior, de forma a obter-se cubos-1. Como foi visto no Método Karnaugh, os mintermos que diferem somente no valor de uma variável são combinados em pares (cubos-1). Obtêm-se a Tabela 3 que é construída de acordo com o seguinte critério. Os mintermos combinados em pares...