Método de Quine McCluskey

Prévia do material em texto

Simplificação de Funções Lógicas pelo Método de Quine‑McCluskey 
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 o de Karnaugh, para se chegar ao resultado, é necessário, via de regra, mais tempo. Este método é eficiente quando implementado em computadores. 
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 um mesmo 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 as seguintes 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ônicos ou Soma de Mintermos. Se a função não estiver nesta forma deve-se convertê-la pelo métodos já estudados.
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, conforme ilustrado a seguir.
	Mintermo
	Representação Binária
	Número de 1's
	m0
	0 0 0 0
	0
	m1
	0 0 0 1
	1
	m5
	0 1 0 1
	2
	m6
	0 1 1 0 
	2
	m7
	0 1 1 1
	3
	m8
	1 0 0 0 
	1
	m9
	1 0 0 1 
	2
	m10
	1 0 1 0 
	2
	m11
	1 0 1 1
	3
	m14
	1 1 1 0
	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's em 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ção binária
	Cubos-0
	0
	m0
	0 0 0 0
	1
	m1
	0 0 0 1
	
	m8
	1 0 0 0 
	
	m5
	0 1 0 1
	
	m6
	0 1 1 0
	2
	m9
	1 0 0 1
	
	m10
	1 0 1 0
	
	m7
	0 1 1 1
	3
	m11
	1 0 1 1
	
	m14
	1 1 1 0
Tabela 2
	 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 Tabela 2, 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 são colocados entre parênteses e repete-se a forma binária destes mintermos colocando-se um X na posição dos valores que são diferentes. Os mintermos combinados são marcados com símbolo (( ) para indicar que fazem parte de um cubo de maior dimensão
.
	
	Cubos-1
	
	
	 (0,1) 
	0
	0
	0
	X
	(
	
	 (0,8) 
	X 
	0
	0
	0
	(
	*
	 (1,5) 
	0
	X
	0
	1
	
	
	 (1,9) 
	X
	0
	0
	1
	(
	
	(8,9)
	1
	0
	0
	X
	(
	
	(8,10)
	1
	0
	X
	0
	(
	*
	(5,7)
	0
	1
	X
	1
	
	*
	(6,7)
	0
	1
	1
	X
	
	*
	(6,14)
	X
	1
	1
	0
	
	
	(9,11)
	1
	0
	X
	1
	(
	
	(10,11)
	1
	0
	1
	X
	(
	*
	(10,14)
	1
	X
	1
	0
	
Tabela 3
	Voltamos a ressaltar que só é possível a combinação de mintermos que diferem entre si de uma potência inteira de 2. É importante frisar que este processo só é válido para comparação entre mintermos de dois grupos subseqüentes, isto é, comparação de mintermos de um grupo com outro grupo imediatamente posterior. É necessário que o mintermo do grupo de baixo seja maior do que o grupo de cima, para que seja possível a combinação. Veja o exemplo, o mintermo m9 que pertence ao grupo com dois 1's na forma binária difere do mintermo m7 do grupo de mintermos com três 1's na representação binária, de uma potência inteira de 2, mas não podem ser combinados. Para os mintermos já combinados que voltam a ser repetidos deve-se simplesmente marcá-los com (( ) para indicar que fazem parte de um cubo de ordem superior. Os elementos de um grupo que não foram combinados, não estão marcados com (( ), devem ser assinalados de forma que sejam facilmente identificados. Marcaremos estes elementos com um asterisco (*) à sua esquerda. Estes elementos são os implicantes primos, a Mínima Soma de Produto será obtida a partir destes. Deve-se continuar a pesquisa a partir da tabela de cubos-1, para investigar aqueles que podem ser combinados para formarem cubos-2. O processo já visto na obtenção da Tabela 3 é repetido. Porém, só serão investigados os elementos de um grupo com os do grupo imediatamente subseqüente que apresentam um X na mesma posição em suas representações binárias. Posto isto, obtêm-se a Tabela 4, de cubos-2, mostrada a seguir.
	
	Cubos-2
	
	*
	 (0,1,8,9) 
	X
	0
	0
	X
	
	*
	8,9,10,11
	1
	0
	X
	X
	
Tabela 4
	A comparação de números em suas representações binárias é adequada para sistemas que realizam este procedimento de forma automatizada, isto é, utilizam computadores como ferramenta de apoio. A utilização manual deste método em longas listas de cubos, provavelmente, induzirão a erros. Esta dificuldade é consideravelmente reduzida pela utilização de um método alternativo, no qual utiliza-se somente a notação decimal. Vamos explicar este método fazendo uso da mesma função usada na notação binária. Novamente, o processo é iniciado pela obtenção da tabela de conversão dos mintermos em suas representações binárias, com os respectivos números de 1's em suas representações. Os mintermos são separados em grupos, de acordo com os números de 1's. O primeiro grupo é formado pelos mintermos com o menor número de 1's em sua representações binárias. Os grupos são constituídos exatamente da mesma maneira vista na representação binária. Entretanto, na tabela de cubos-0 são colocados somente o número decimal do mintermo, conforme mostrado a seguir.
	Para realizarmos a comparação utilizamos a condição de que só é possível a combinação de mintermos que diferem entre si de uma potência inteira de 2. Como exemplo considere os mintermos m0 0000 e m8 1000, que podem ser representados por potências de 2 mostradas a seguir
(0) = 0 ( 23 + 0 ( 22 + 0 ( 21 + 0 ( 20 
(8) = 1 ( 23 +0 ( 22 + 0 ( 21 + 0 ( 20 
	Cada um dos algarismos binários tem um peso numérico que é uma potência de 2. Pode-se realizar a combinação dos mintermos que tem os mesmos 1's e 0's, e diferem somente em uma posição. Para representar os cubos-1, na Tabela-6, escreve-se a notação decimal dos dois mintermos separados por uma vírgula e coloca-se entre parênteses a potência de inteira de 2 que diferencia os referidos mintermos. Para o exemplo dado o cubo-1 será identificado por 0,8 (8). O número entre parênteses indicará a posição do X na representação binária. O dígito tem peso 8, isto significa que o X está na quarta posição a partir da direita na notação binária 0,8 (X000). Apesar da mudança de notação, o processo é exatamente igual ao descrito para notação binária. A seguir é mostrado o processo de identificação dos implicantes primos, utilizando a notação decimal.
	Mintermo
	Representação Binária
	Número de 1's
	m0
	0 0 0 0
	0
	m1
	0 0 0 1
	1
	m5
	0 1 0 1
	2
	m6
	0 1 1 0 
	2
	m7
	0 1 1 1
	3
	m8
	1 0 0 0 
	1
	m9
	1 0 0 1 
	2
	m10
	1 0 1 0 
	2
	m11
	1 0 1 1
	3
	m14
	1 1 1 0
	3
Tabela 5
	No método que utiliza a notação binária, vimos que os cubos-1 que podem ser combinados em cubos-2, são aqueles que apresentam o X na mesma posição. Como na notação decimal o número entre parênteses indica a posição de X, da mesma forma na notação binária, os cubos-1 que podem ser combinados são aqueles que têm o mesmo número entre parênteses. Evidentemente, a formação de um cubo-2 a partir de dois cubos-1, implica, como foi visto, que tenham o X na mesma posição e os mintermos devem diferir de uma outra potência inteira de 2. A notação utilizada para esta representação é listar os mintermos agrupados e colocar entre parênteses as duas potências inteiras de 2 que estes quatro mintermos diferem entre si. Por exemplo, o cubo-2 formado pelos mintermos 0,1,8, e 9 é representado por 0,1,8,9 (1,8).
	Cubos-0
	
	
	Cubos-1
	
	
	Cubos-2
	
	0
	0
	(
	
	0,1(1)
	(
	*
	0,1,8,9(1,8)
	a
	1
	1
	(
	
	0,8(8)
	(
	*
	8,9,10,11(1,2)
	b
	
	8
	(
	*
	1,5(4)
	c
	
	
	
	
	5
	(
	
	1,9(8)
	(
	
	
	
	2
	6
	(
	
	8,9(1)
	(
	
	
	
	
	9
	(
	
	8,10(2)
	(
	
	
	
	
	10
	(
	*
	5,7(2)
	d
	
	
	
	
	7
	(
	*
	6,7(1)
	e
	
	
	
	3
	11
	(
	*
	6,14(8)
	f
	
	
	
	
	14
	(
	
	9,11(2)
	(
	
	
	
	
	
	
	
	10,11(1)
	(
	
	
	
	
	
	
	*
	10,14(4)
	g
	
	
	
Tabela 6
Obtenção da Mínima Soma de Produtos 
	Após obtidos os implicantes primos, têm-se como objetivo obter o subconjunto, D, a partir destes. Este passo terá como suporte teórico o Teorema 1, provado Quine, que veremos a seguir. Todos os implicantes primos determinados no exemplo visto são mostrados pelos quatro agrupamentos no mapa de Karnaugh dado seguir. 
	
	
	
	<A,B>
	
	
	
	
	00
	01
	11
	10
	
	00
	1 0
	0 4
	0 12
	1 8
	<C,D>
	01
	1 1
	1 5
	0 13
	1 9
	
	11
	0 3
	1 7
	0 15
	1 11
	
	10
	0 2
	1 6
	1 14
	1 10
	A interpretação dos cubos-k de conjuntos de 1's em mapas de Karnaugh é a seguinte: cada cubo-k irá representar um produto com (n-k) variáveis para realização da função em termos de somas de produtos; os conjuntos de cubos-k escolhidos devem conter todos os cubos-0 (mintermos) da função Soma de Produtos Canônicos.
Teorema 1: Qualquer realização soma de produtos será mínima de acordo com a Definição 1 se for constituída de somas de implicantes primos. 
	O Teorema 1 indica que se deve concentrar os esforços na determinação implicantes primos, que conduzirão a realização da soma com um menor número de produtos. Entretanto, o Teorema 1 não estabelece que qualquer soma de produtos constituída por implicantes primos que cobrem a função é mínima. A sistematização para obtenção da Mínima Soma de Produto é feita em várias etapas, que é iniciada a partir da construção de uma Tabela de implicantes primos.
	A Tabela de Implicantes primos será construída da seguinte forma: a primeira coluna é destinada aos implicantes primos; existirá uma coluna para cada mintermo, que serão listados no topo da tabela; nas linhas da tabela serão colocados os implicantes primos, que deverão ser listados a partir do topo da tabela, os cubos de ordem mais elevada, quando ocorre mudança na dimensão do cubo, sinaliza-se este fato com uma linha horizontal dupla. Existe uma linha ao final da tabela, cuja função será descrita, posteriormente. O exemplo a seguir ilustra a criação de uma tabela de implicantes primos. 
	O preenchimento da tabela é feito da seguinte forma: em cada linha exceto a última, são assinalados todos os mintermos correspondentes ao implicante primo, utiliza-se como marca o símbolo (( ). Por exemplo, o primeiro implicante primo da tabela contém os mintermos 0,2,8 e 10, então de acordo com estabelecido marca-se com (( ). na primeira linha as colunas 0,2,8 e 10, conforme mostrado a seguir.
	
	0
	2
	3
	6
	7
	8
	9
	10
	13
	0,2,8,10 (2,8)
	(
	(
	
	
	
	(
	
	(
	
	2,3,6,7 (1,4)
	
	(
	(
	(
	(
	
	
	
	
	8,9 (1)
	
	
	
	
	
	(
	(
	
	
	9,13 (4)
	
	
	
	
	
	
	(
	
	(
	
	
	
	
	
	
	
	
	
	
Tabela 7
	Após concluído o preenchimento da tabela de Implicantes primos, inspeciona-se as colunas para sejam identificadas as que tem somente uma única marca (( ). Neste exemplo, verifica-se que a primeira coluna de mintermos apresenta uma única marca relativa ao primeiro implicante primo. Isto significa que o implicante primo constituído pelos mintermos 0,2,8,10 (2,8) é o único que contém o mintermo m0, e, portanto, deve obrigatoriamente ser incluído na realização da soma de produtos mínima. Diz-se, então, que este é um implicante primo essencial e identifica-se esta condição, através de um asterisco (*) à esquerda do implicante primo. Os mintermos que compõem este implicante primo essencial são assinalados na última linha da Tabela com a marca (() estabelecida, para indicar que estes mintermos já foram cobertos por implicantes primos essenciais. Após isto, a tabela ficará conforme mostrado a seguir.
	
	0
	2
	3
	6
	7
	8
	9
	10
	13
	* 0,2,8,10 (2,8)
	(
	(
	
	
	
	(
	
	(
	
	2,3,6,7 (1,4)
	
	(
	(
	(
	(
	
	
	
	
	8,9 (1)
	
	
	
	
	
	(
	(
	
	
	9,13 (4)
	
	
	
	
	
	
	(
	
	(
	
	(
	(
	
	
	
	(
	
	(
	
Tabela 8
	Continuando-se a inspeção, observa-se que a coluna 3, também apresenta uma única marca ( ( ), o que como vimos, indica que o implicante primo 2,3,6,7 (1,4) é o único que cobre o cubo-0 m3. Identifica-se, novamente, com um asterisco (*), à esquerda do implicante primo para indicar a sua condição de essencial . E marca-se na última linha os mintermos cobertos. Serão assinalados somente os mintermos cobertos pelo implicante primo que ainda não assinalados em outros implicantes primos essenciais, identificado em inspeções anteriores. Finalmente, identifica-se que 9,13 (4) também é um implicante primo essencial, pois é o único que cobre o mintermo m13, da mesma forma marca-se com um asterisco (*) na coluna mais à esquerda e assinala-se com (( ) na última linha as colunas referentes aos mintermos deste implicante primo essencial. A tabela preenchida ficará conforme mostrada a seguir.
	
	
	0
	2
	3
	6
	7
	8
	9
	10
	13
	*
	0,2,8,10 (2,8)
	(
	(
	
	
	
	(
	
	(
	
	
	2,3,6,7 (1,4)
	
	(
	(
	(
	(
	
	
	
	
	
	8,9 (1)
	
	
	
	
	
	(
	(
	
	
	
	9,13 (4)
	
	
	
	
	
	
	(
	
	(
	
	
	(
	(
	(
	(
	(
	(
	(
	(
	(
Tabela 9
	Todos os implicantes primos essenciais e observamos que estes cobrem a função dada. Deve-se então, obter a expressão referente a Mínima Soma de Produtos. Para fazer isto, relembramos que os números entre parênteses ao lado de cada implicante primo indicam as variáveis que foram eliminadas. Escreve-se o equivalente binário de qualquerum dos mintermos de um implicante primo, retirando-se os bits, cujas posições estão indicadas pelos números dentro do parêntese, e colocam-se os literais apropriados aos dígitos restantes. Então, o produto será obtido assim: a variável assumindo o valor 0 aparecerá complementada e assumindo valor 1 aparecerá a própria variável. Têm-se, então, a seguir os produtos: 
	 0,2,8,10 (2,8) = 
	X 0 X 0 
	(
�
	2,3,6,7 (1,4) = 
	0 X 1 X 
	(
�
	 9,13 (4) = 
	1 X 0 1 
	(
�
		Q
Assim a Mínima Soma de Produtos é
f(A,B,C,D) = ( m(0,2,3,6,7,8,9,10,13)= 
� + 
� + 
�
	O exemplo escolhido é antes de tudo uma ilustração prática do valor da técnica, e sua simplicidade (do exemplo) permitiu que ficassem bem claras as várias etapas envolvidas para que chegássemos à Soma de produto desejada. O exemplo mostrado a seguir é mais completo e permitirá que sejam investigadas outras situações.
	Exemplo 2: Determine a mínima soma de produtos para a função
f (A,B,C,D,E) = ( m(0,6,8,10,12,14,17,19,20,22,25,27,28,30)
cuja a tabela de cubos é dada a seguir.
	
�
Solução: Observar que foram atribuídas letras para representar os implicantes primos de forma a simplificar a tabela, eliminou-se também a coluna de identificação dos implicantes primos essenciais. Então,
	Cubos-0
	Cubos-1
	Cubos-2
	0
	0
	(
	* 0,8 (8)
	f
	* 8,10,12,14 (2,4)
	a
	1
	8
	(
	8,10 (2)
	(
	* 6,14,22,30 (8,16)
	b
	
	6
	(
	8,12 (4)
	(
	* 2,14,28,30 (2,16)
	c
	
	10
	(
	6,14 (8)
	(
	* 17,19,25,27 (2,8)
	d
	2
	12
	(
	6,22 (16)
	(
	* 20,22,28,30 (2,8)
	e
	
	17
	(
	10,14 (4)
	(
	
	
	
	20
	(
	12,14 (2)
	(
	
	
	
	14
	(
	17,19 (2)
	(
	
	
	
	19
	(
	17,25 (8)
	(
	
	
	3
	22
	(
	20,22 (2)
	(
	
	
	
	25
	(
	20,28 (8)
	(
	
	
	
	28
	(
	14,30 (16)
	(
	
	
	4
	27
	(
	19,27 (8)
	(
	
	
	
	30
	(
	22,30 (8)
	(
	
	
	
	
	
	25,27 (2)
	(
	
	
	
	
	
	28,30 (2)
	(
	
	
Tabela 10
	Tabela de Implicantes primos
	
	0
	6
	8
	10
	12
	14
	17
	19
	20
	22
	25
	27
	28
	30
	* a
	
	
	(
	(
	(
	(
	
	
	
	
	
	
	
	
	 * b
	
	(
	
	
	
	(
	
	
	
	(
	
	
	
	(
	c
	
	
	
	
	(
	(
	
	
	
	
	
	
	(
	(
	* d
	
	
	
	
	
	
	(
	(
	
	
	(
	(
	
	
	* e
	
	
	
	
	
	
	
	
	(
	(
	
	
	(
	(
	* f
	(
	
	(
	
	
	
	
	
	
	
	
	
	
	
	
	(
	(
	(
	(
	(
	(
	(
	(
	(
	(
	(
	(
	(
	(
Tabela 11
	Exemplo 3: Nos dois primeiros exemplos, os implicantes primos essenciais cobriram todos os mintermos, porém nem sempre este será o caso. A figura dada a seguir fornece a tabela de implicantes primos para a função
 f (A,B,C,D,E) = ( m(1,2,3,5,9,10,11,18,19,20,21,23,25,26,27)
	
	1
	2
	3
	5
	9
	10
	11
	18
	19
	20
	21
	23
	25
	26
	27
	* a
	
	(
	(
	
	
	(
	(
	(
	(
	
	
	
	
	(
	(
	 * b
	
	
	
	
	(
	
	(
	
	
	
	
	
	(
	
	(
	c
	(
	(
	
	
	(
	
	(
	
	
	
	
	
	
	
	
	 d
	(
	
	
	(
	
	
	
	
	
	
	
	
	
	
	
	 e
	
	
	
	(
	
	
	
	
	
	
	(
	
	
	
	
	* f
	
	
	
	
	
	
	
	
	
	(
	(
	
	
	
	
	g
	
	
	
	
	
	
	
	
	(
	
	
	(
	
	
	
	h
	
	
	
	
	
	
	
	
	
	
	(
	(
	
	
	
	
	(
	(
	
	(
	(
	(
	(
	(
	(
	(
	(
	
	(
	(
	(
Tabe]
la 12
	Após a seleção dos implicantes primos essenciais da Tabela-12, observa-se que nem todos os mintermos foram cobertos. Deve-se, então, estabelecer um critério que considere o custo, de forma a permitir a seleção apropriada dos mintermos não essenciais.
	Para facilitar a seleção dos implicantes apropriados faz-se uma tabela reduzida de implicantes primos, na qual devem constar somente os mintermos que não foram cobertos pelos implicantes primos essenciais, estes mintermos são identificados pela última linha da tabela de implicantes primos, no exemplo em questão a Tabela-13, observando-se quais colunas não estão assinaladas nesta última linha. Portanto, devem aparecer na tabela reduzida de implicantes primos os mintermos que não foram identificados como essenciais. A tabela reduzida de implicantes primos para o exemplo dado é mostrada na Tabela-13.
	
	1
	5
	23
	c
	(
	
	
	d
	(
	(
	
	e
	
	(
	
	g
	
	
	(
	h
	
	
	(
	
	
	
	
Tabela 13
	Analisando-se a Tabela-13 observa-se que não existe vantagem em selecionar o implicante primo e, já que este cobre somente o mintermo m5 , enquanto o implicante primo d, com o mesmo custo cobres os mintermos m1 e m5. Por isso, remove-se da tabela reduzida o implicante primo e, pois não participará da Mínima Soma de Produtos procurada. 
	Observa-se também que os implicantes primos g e h cobrem cs mesmos mintermos com o mesmo custo. Desta forma, um dos dois é retirado da tabela reduzida, a escolha foi feita de forma arbitrária e selecionou-se o implicante primo g. Faz-se uma outra tabela, na qual os implicantes primos eliminados não aparecem. A Tabela-14 mostra esta etapa para o exercício em questão.
	
	1
	5
	23
	c
	(
	
	
	**d
	(
	(
	
	**g
	
	
	(
	
	(
	(
	(
Tabela 14
	Nesta nova tabela observa-se que o implicante primo d cobre dois mintermos da função, m1 e m5, enquanto o implicante primo c cobre somente um mintermo, o m1, por questões de custo seleciona-se o implicante primo d. Observa-se também que somente o implicante primo g cobre o mintermo m23, logo este implicante primo deve ser selecionado. Os implicantes primos selecionados são assinalados com dois asteriscos (**) e são denominados de implicantes primos essenciais secundários. Com a determinação dos implicantes primos essenciais secundários todos os mintermos da função foram cobertos, logo resta-nos escrever a Soma de Produtos Mínima a partir dos implicantes primos selecionados.
	f(A,B,C,D,E) =
	a + b + f
	+
	d + g
	
	
	Essenciais
	
	essenciais
secundários
�
	Os procedimentos vistos são formalizados pelas Definições 2 e 3 e pelo Teorema 2 dados a seguir.
Definição 2: duas linhas, a e b de uma tabela reduzida de implicantes primos que cobrem os mesmos mintermos, isto é, possuem marcas nas mesmas colunas, são ditas equivalentes
Definição 3: dadas duas linhas, a e b de uma tabela reduzida de implicantes primos, diz-se que a linha a domina a linha b se a linha a está assinalada em todas as colunas em que a linha b possui marcas e possui marca em, no mínimo, em uma coluna em que a linha b não está marcada.
	
Teorema 2: sejam a e b duas linhas de uma tabela reduzida de implicantes primos, tal que o custo de a é menor ou igual ao de b. Então se a domina b ou se a e b são equivalentes, existe uma Mínima Soma de Produtos na qual b não participa.
	Deve-se ter em conta a definição de Mínima Soma para escolha dos implicantes primos apropriados, considerando-se as Definições 2 e 3 e o Teorema 2.
	Exemplo 4: dada a função a seguir, pede-se obter a Mínima Soma de Produto.
f (A,B,C,D,E,F) = ( m(1,2,3,4,5,8,9,10,17,20,21,24,25,32,33,34,36,37,40,41,42,43,44,45,46,47,48,56,59,62)
	Os implicantes primos da função foram obtidos utilizando-se os procedimentos já vistos. Após a identificação dos implicantes primos essenciais obtêm-se a tabela reduzida de implicantes primos que é dada a seguir.
	
	1
	2
	3
	8
	9
	10
	17
	24
	25
	27
	33
	34
	36
	37
	59
	a
	
	
	
	
	
	
	
	
	
	
	(
	
	(
	(
	
	c
	(
	
	
	
	
	
	(
	
	
	
	
	
	
	
	
	d
	(
	
	
	
	
	
	
	
	
	
	(
	
	
	(
	
	 e
	(
	
	
	
	(
	
	
	
	
	
	(
	
	
	
	
	f
	(
	
	
	
	(
	
	
	
	
	
	(
	
	
	
	
	g
	
	(
	
	
	
	(
	
	
	
	
	
	(
	
	
	
	i
	
	
	
	
	
	
	
	
	
	
	
	
	(
	(
	
	j
	
	
	
	(
	(
	
	
	(
	(
	
	
	
	
	
	
	k
	
	
	
	(
	(
	
	
	
	
	
	
	
	
	
	
	l
	
	
	
	(
	
	(m
	
	
	
	(
	
	
	
	(
	
	
	
	
	
	
	
	n
	
	
	
	
	
	
	
	
	
	
	
	(
	
	
	
	q
	(
	
	(
	
	
	
	
	
	
	
	
	
	
	
	
	r
	
	(
	(
	
	
	
	
	
	
	
	
	
	
	
	
	s
	
	
	
	
	
	
	
	
	(
	(
	
	
	
	
	
	t
	
	
	
	
	
	
	
	
	
	(
	
	
	
	
	(
	u
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	(
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
Tabela 15
	Observa-se que o implicante primo n cobre somente o mintermo m34 enquanto o o implicante primo g cobre os mintermos m2 , m10 e m34. Então, de acordo com a Definição 3 g domina n, portanto o implicante primo n pode ser retirado da tabela reduzida. Similarmente, e domina c, a domina i, j domina k, m e, finalmente, t domina u. A figura a seguir mostra a nova tabela de implicantes primos, na qual os implicantes primos foram removidos.
	
	1
	2
	3
	8
	9
	10
	17
	24
	25
	27
	33
	34
	36
	37
	59
	** a
	
	
	
	
	
	
	
	
	
	
	(
	
	(
	(
	
	d
	(
	
	
	
	
	
	
	
	
	
	(
	
	
	(
	
	 ** e
	(
	
	
	
	(
	
	(
	
	(
	
	
	
	
	
	
	f
	(
	
	
	
	(
	
	
	
	
	
	(
	
	
	
	
	 ** g
	
	(
	
	
	
	(
	
	
	
	
	
	(
	
	
	
	** j
	
	
	
	(
	(
	
	
	(
	(
	
	
	
	
	
	
	l
	
	
	
	(
	
	(
	
	
	
	
	
	
	
	
	
	q
	(
	
	(
	
	
	
	
	
	
	
	
	
	
	
	
	r
	
	(
	(
	
	
	
	
	
	
	
	
	
	
	
	
	s
	
	
	
	
	
	
	
	
	(
	(
	
	
	
	
	
	** t
	
	
	
	
	
	
	
	
	
	(
	
	
	
	
	(
	
	(
	(
	
	(
	(
	(
	(
	(
	(
	V
	(
	(
	(
	(
	V
Tabela 16
	
	Pesquisa-se à tabela para identificação dos implicantes primos essenciais secundários, que são aqueles que apresentam uma única marca na coluna. Estes implicantes primos são a, e, g, j e t. Após a seleção dos implicantes primos essenciais secundários, observa-se que o mintermo m3 não foi coberto por nenhum implicante primos, e analisando-se a tabela identificamos que este mintermo é coberto pelos implicantes primos q e r, que apresentam o mesmo custo para realização do produto. Então, arbitrariamente, escolhe-se qualquer um destes. A nossa opção recaiu no implicante primo q. Obtêm-se, então, a Soma de Produtos Mínima para a função é dada a seguir.
	SPM = a + e + g + j + t + q + implicantes primos essenciais 
�
Método de Petrick
	No exemplo 3 a aplicação do conceito de dominação foi suficiente para determinar o número mínimo de produtos que cobrem a função. Em alguns casos, após a seleção dos implicantes primos essenciais secundários ainda podem ter sobrado mintermos que não foram cobertos. Nestes casos, deve-se, simplesmente, repetir o processo, isto é, retirar as linhas referentes aos implicantes primos essenciais secundários e, novamente, aplicar o conceito de dominação e equivalência. Este processo pode ser repetido quantas vezes for necessário. Se em determinado ponto não se consegue identificar implicantes primos essenciais secundários e ainda restarem mintermos a serem cobertos deve-se então utilizar o método de Petrick para determinar a escolha dos implicantes primos que comporão a Soma de Produtos Mínima. Estudaremos o método de Petrick através do exemplo a seguir.
	Exemplo 5. Considere a tabela reduzida de implicantes primos dada a seguir. Esta tabela não pode ser reduzida, visto que não existe nenhum implicante primo dominando outro.
	
	6
	7
	15
	38
	46
	47
	a
	(
	(
	
	
	
	
	b
	
	
	(
	
	
	(
	c
	
	(
	(
	
	
	
	d
	
	
	
	
	(
	(
	e
	
	
	
	(
	(
	
	f
	(
	
	
	(
	
	
	
	
	
	
	
	
	
Tabela 17
	Nesta tabela aparecem todos os possíveis conjuntos redundantes de implicantes primos que incluem os mintermos não cobertos. As letras que representam os implicantes primos remanescentes são interpretadas como variáveis booleana, que assumirá valor 1 se o implicante primo for selecionado e valor lógico 0, em caso contrário. Para a primeira coluna, se selecionarmos as linhas a e f para cobrir m6, podemos escrever
( a + f ) = 1
Similarmente, a e c devem ser selecionados para cobrir m7, então 
( a + f ) ( a + c )= 1
da mesma forma, obtêm-se o produto de somas. Onde cada soma é constituída por todos os implicantes primos que contêm um mintermo particular. Neste caso, a expressão completa será
( a + f ) ( a + c ) ( b + c ) ( e + f ) ( d + e ) ( b + d ) = 1
Aplicando-se a propriedade distributiva, obtêm-se
abe + abdf + acde + bcef + cdf = 1
	Para que a equação seja satisfeita é necessário que, pelo o menos, um dos produtos seja 1. Os produtos com um menor número de variáveis, no caso abe e cdf, determinarão o menor conjunto de implicantes primos que cobrirão os mintermos da função. Deve-se verificar quais das soluções está de acordo com a definição da Mínima Soma de Produtos SPM para efetuar a seleção. 
	Avaliando-se os implicantes primos, conclui-se que o conjunto abe tem custo menor que o conjunto cdf, logo a Mínima Soma de Produtos será constituída por: 
	SPM 
	=
	a + b + e + implicantes primos essenciais + implicantes essenciais secundários selecionados em etapas anteriores
�
Simplificação de funções que têm condições irrelevantes (don’t care)	
		Pode-se adaptar de forma muito simples o método de Quine​‑McCluskey para realizar simplificações em funções que apresentam condições irrelevantes (don’t care ). As condições irrelevantes são incluídas na determinação dos implicantes primos, desta forma, assegura-se que todos os implicantes primos estarão relacionados. Entretanto, na tabela de implicantes primos só serão listados os mintermos, as condi
ções irrelevantes não aparecerão. Isto assegura que somente os implicantes primos necessários para cobrirem todos os mintermos serão selecionados. Vamos fixar os procedimentos através de um exemplo.
	Exemplo 6. Simplificar a função dada a seguir.
 f (A,B,C,D) = ( m (0,1,8, 12,13,15) + d (2,5, 9,10,11,14)
	Mintermo
	Representação Binária
	Número de 1's
	m0
	0 0 0 0
	0
	m1
	0 0 0 1
	1
	d2
	0 0 1 0
	1
	d5
	0 1 0 1 
	2
	m8
	1 0 0 0 
	1
	d9
	1 0 0 1 
	2
	d10
	1 0 1 0 
	2
	d11
	1 0 1 1
	3
	m12
	1 1 0 0
	2
	m13
	1 1 0 1
	3
	d14
	1 1 1 0
	3
	m15
	1 1 1 1
	4
Tabela 18
�
	Cubos-0
	
	Cubos-1
	Cubos-2
	
	Cubos-3
	
	(
	0
	(
	 0,1 (1)
	(
	* 0,1,8,9 (1,8)
	b
	* 8,9,10,11,12,13,14,15(1,2,4)
	a
	(
	1
	(
	0,2(2)
	(
	* 0,2,8,10 (2,8)
	c
	
	
	(
	2
	(
	0,8(8)
	(
	* 1,5,9,13(4,8)
	d
	
	
	(
	8
	(
	1,5(4)
	(
	8,9,10,11(1,2)
	(
	
	
	(
	5
	(
	1,9(8)
	(
	8,9,12,13(1,4)
	(
	
	
	(
	9
	(
	2,10(8)
	(
	8,10,12,14(24)
	(
	
	
	
	10
	(
	8,9(1)
	(
	9,11,13,15(2,4)
	(
	
	
	
	12
	(
	8,10(2)
	(
	12,13,14,15(1,2)
	(
	
	
	
	11
	(
	8,12(4)
	(
	10,11,14,15(1,4)
	(
	
	
	3
	13
	(
	5,13(8)
	(
	
	
	
	
	
	14
	(
	9,11(2)
	(
	
	
	
	
	4
	15
	(
	9,13(4)
	(
	
	
	
	
	
	
	
	10,11(1)
	(
	
	
	
	
	
	
	
	10,14(2)
	(
	
	
	
	
	
	
	
	12,13(1)
	(
	
	
	
	
	
	
	
	12,14(2)
	(
	
	
	
	
	
	
	
	11,15(4)
	(
	
	
	
	
	
	
	
	13,15(2)
	(
	
	
	
	
	
	
	
	14,15(1)
	(
	
	
	
	
Tabela 1 9
	Tabela de Implicantes primos e Tabela reduzida de implicantes primos são dadas a seguir.
	
	0
	1
	8
	12
	13
	15
	
	0
	1
	
	* a
	
	
	(
	(
	(
	(
	** b
	(
	(
	
	b
	(
	(
	(
	
	
	
	c
	
	(
	dominado por b
	c
	
	(
	
	
	
	
	d
	(
	
	dominado por b
	d
	(
	
	(
	
	
	
	
	(
	(
	
	
	
	
	(
	(
	(
	(
	
	(
	(
	
Tabela 20
	A Mínima Soma de Produtos para a função dada é :
	SPM = a + b
�
Referências Bibliográficas
HILL, Frederick J, PETERSON, Gerald R.Switching Theory & Logic Design, USA, Jonh Wiley & Sons, 1981
DIAS, Francisco José de Oliveira. Circuitos de Chaveamento, São Paulo,Escola Politécnica da Universidade de São Paulo, 1981.
�PAGE �
�PAGE �12�
Criado por � AUTHOR �Prof. Evandro Vieiralves�
_890433874.unknown
_890433875.unknown
_890570757.unknown
_890433872.unknown
_890433873.unknown
_890433870.unknown
_890433868.unknown