Mapas de Karnaugh, tabelas da verdade e expressões booleanas

Quem desenvolveu o mapa de Karnaugh?

Maurice Karnaugh, um engenheiro de telecomunicações, desenvolveu o mapa de Karnaugh no Bell Labs em 1953 enquanto projetava circuitos de comutação telefônica baseados em lógica digital.

O uso do mapa de Karnaugh

Agora que desenvolvemos o mapa de Karnaugh com a ajuda dos diagramas de Venn, vamos colocá-lo em uso. Mapas de Karnaugh reduzir funções lógicas mais rápida e facilmente em comparação com álgebra booleana. Por reduzir queremos dizer simplificar, reduzindo o número de portas e entradas.

Gostamos de simplificar a lógica para um custo mais baixo forma de economizar custos por eliminação de componentes. Definimos o custo mais baixo como sendo o menor número de portas com o menor número de entradas por porta.

Dada a escolha, a maioria dos alunos faz simplificação lógica com mapas de Karnaugh em vez de álgebra booleana, uma vez que aprendem esta ferramenta.







Mostramos cinco itens individuais acima, que são apenas maneiras diferentes de representar a mesma coisa:uma função lógica digital arbitrária de 2 entradas. Primeiro é a lógica ladder do relé, depois as portas lógicas, uma tabela verdade, um mapa de Karnaugh e uma equação booleana.

A questão é que qualquer um deles é equivalente. Duas entradas A e B pode assumir valores de 0 ou 1 , alto ou baixo, aberto ou fechado, verdadeiro ou falso, conforme o caso. Existem 2 ² =4 combinações de entradas que produzem uma saída. Isso se aplica a todos os cinco exemplos.

Essas quatro saídas podem ser observadas em uma lâmpada na lógica ladder do relé, em uma sonda lógica no diagrama da porta. Essas saídas podem ser registradas na tabela verdade ou no mapa de Karnaugh. Veja o mapa de Karnaugh como uma tabela de verdade reorganizada.

A saída da equação booleana pode ser calculada pelas leis da álgebra booleana e transferida para a tabela verdade ou mapa de Karnaugh.

Qual das cinco descrições lógicas equivalentes devemos usar? Aquele que é mais útil para a tarefa a ser realizada.







As saídas de uma tabela verdade correspondem uma a uma às entradas do mapa de Karnaugh. Começando do topo da tabela verdade, as entradas A =0, B =0 produzem uma saída α.

Observe que esta mesma saída α é encontrada no mapa de Karnaugh no endereço da célula A =0, B =0, canto superior esquerdo do mapa K onde a linha A =0 e a coluna B =0 se cruzam. As outras saídas da tabela verdade β, χ, δ das entradas AB =01, 10, 11 são encontradas nas localizações correspondentes do K-map.

Abaixo, mostramos as regiões adjacentes de 2 células no mapa K de 2 variáveis ​​com a ajuda do diagrama retangular de Venn anterior, como as regiões booleanas.







As células α e χ são adjacentes no K-map como elipses no K-map mais à esquerda abaixo. Referindo-se à tabela verdade anterior, esse não é o caso. Existe outra entrada da tabela verdade (β) entre eles. O que nos leva a todo o ponto de organizar o K-map em uma matriz quadrada, as células com quaisquer variáveis ​​booleanas em comum precisam estar próximas umas das outras para apresentar um padrão que salta para nós.

Para células α e χ, eles têm a variável booleana B ’ em comum. Sabemos disso porque B =0 (igual a B ’ ) para a coluna acima das células α e χ. Compare isso com o diagrama de Venn quadrado acima do K-map.

Uma linha de raciocínio semelhante mostra que β e δ têm o Booleano B (B =1) em comum. Então, α e β têm o Booleano A ’ (A =0) em comum. Finalmente, χ e δ têm o booleano A (A =1) em comum. Compare os dois últimos mapas com o diagrama de Venn do quadrado do meio.

Para resumir, estamos procurando uniformidade de variáveis ​​booleanas entre as células. O mapa de Karnaugh é organizado de forma que possamos ver essa semelhança. Vamos tentar alguns exemplos.

Exemplos

Exemplo:

Transfira o conteúdo da tabela verdade para o mapa de Karnaugh acima.





Solução:

A tabela verdade contém dois 1 s. o K-map deve ter os dois. localize o primeiro 1 na 2ª linha da tabela verdade acima.

• observe o endereço AB da tabela verdade
• localize a célula no K-map com o mesmo endereço
• coloque um 1 naquela célula

Repita o processo para o 1 na última linha da tabela verdade.



Exemplo:

Para o mapa de Karnaugh no problema acima, escreva a expressão booleana. A solução está abaixo.







Solução:

Procure células adjacentes, ou seja, acima ou ao lado de uma célula. As células diagonais não são adjacentes. As células adjacentes terão uma ou mais variáveis ​​booleanas em comum.

• Agrupe (circule) os dois 1 s na coluna
• Encontre a (s) variável (s) superior e / ou lateral que são iguais para o grupo, escreva isso como o resultado booleano. É B no nosso caso.
• Ignore as variáveis ​​que não são iguais para um grupo de células. Em nosso caso, A varia, é 1 e 0, ignore o booleano A.
• Ignore qualquer variável não associada a células contendo 1s. B ’ não tem ninguém sob ele. Ignorar B ’
• Resultado Out =B

Isso pode ser mais fácil de ver comparando com os diagramas de Venn à direita, especificamente o B coluna.



Exemplo:

Escreva a expressão booleana para o mapa de Karnaugh abaixo.







Solução: (acima)

• Agrupe (circule) os dois 1s na fila
• Encontre as variáveis ​​que são iguais para o grupo, Out =A ’

Exemplo:

Para a tabela de verdade abaixo, transfira as saídas para o Karnaugh e, a seguir, escreva a expressão booleana para o resultado.







Solução:

Transfira o 1 s dos locais na tabela Verdade para os locais correspondentes no K-map.

• Agrupe (circule) os dois 1s na coluna em B =1
• Agrupe (circule) os dois 1s na linha à direita de A =1
• Escreva o termo do produto para o primeiro grupo = B
• Escreva o termo do produto para o segundo grupo = A
• Escreva a soma de produtos dos dois termos acima Saída =A + B

A solução do K-map no meio é a solução mais simples ou de menor custo. Uma solução menos desejável está na extrema direita. Depois de agrupar os dois 1 s, cometemos o erro de formar um grupo de 1 célula. A razão pela qual isso não é desejável é que:

• A única célula tem um termo de produto de AB ’
• A solução correspondente é Saída =AB ’+ B
• Esta não é a solução mais simples

A maneira de escolher este único 1 é formar um grupo de dois com o 1 à direita dele, conforme mostrado na linha inferior do K-map do meio, embora este 1 já foi incluído no grupo de colunas ( B ) Podemos reutilizar células para formar grupos maiores. Na verdade, é desejável porque leva a um resultado mais simples.

Precisamos apontar que qualquer uma das soluções acima, saída ou saída errada, são logicamente corretas. Ambos os circuitos produzem a mesma saída. É uma questão de o primeiro circuito ser a solução de menor custo.



Exemplo:

Preencha o mapa de Karnaugh para a expressão booleana abaixo e, a seguir, escreva a expressão booleana para o resultado.







Solução: (acima)

A expressão booleana possui três termos de produto. Haverá um 1 inserido para cada termo do produto. Embora, em geral, o número de 1 s por termo de produto varia com o número de variáveis ​​no termo de produto em comparação com o tamanho do K-map.

O termo do produto é o endereço da célula onde o 1 é introduzido. O primeiro termo do produto, A’B , corresponde ao 01 célula no mapa. A 1 é inserido nesta célula. Os outros dois termos P são inseridos para um total de três 1s

Em seguida, prossiga com o agrupamento e extração do resultado simplificado como no problema anterior da tabela verdade.



Exemplo:

Simplifique o diagrama lógico abaixo.







Solução: (Figura abaixo)

• Escreva a expressão booleana para o diagrama lógico original, conforme mostrado abaixo
• Transfira os termos do produto para o mapa de Karnaugh
• Forme grupos de células como nos exemplos anteriores
• Escreva uma expressão booleana para grupos como nos exemplos anteriores
• Desenhe um diagrama lógico simplificado

Exemplo: Simplifique o diagrama lógico abaixo.







Solução:

• Escreva a expressão booleana para o diagrama lógico original mostrado acima
• Transfira os termos do produto para o mapa de Karnaugh.
• Não é possível formar grupos.
• Nenhuma simplificação é possível; deixe como está.

Nenhuma simplificação lógica é possível para o diagrama acima. Isso às vezes acontece. Nem os métodos dos mapas de Karnaugh nem a álgebra booleana podem simplificar ainda mais essa lógica.

Mostramos um símbolo esquemático Exclusive-OR acima; no entanto, esta não é uma simplificação lógica. Isso apenas torna um diagrama esquemático mais bonito.

Por não ser possível simplificar a lógica Exclusive-OR e por ser amplamente utilizada, ela é fornecida pelos fabricantes como um circuito integrado básico (7486).



PLANILHAS RELACIONADAS:

• Planilha de mapeamento de Karnaugh
• Planilha de álgebra booleana
• Planilha de portas lógicas básicas