Álgebra booleana

Álgebra booleana

(Parte 1 de 2)

Álgebra Booleana, Revisão Portas Lógicas e Mapas de Karnaugh

1) Álgebra Booleana:

Em 1854, George Boole introduziu o formalismo que até hoje se usa para o tratamento sistemático da lógica, que é a chamada Álgebra Booleana. Em 1938, C. E. Shannon aplicou esta álgebra para mostrar que as propriedades de circuitos elétricos de chaveamento podem ser representadas por uma álgebra Booleana com dois valores (estado “ligado”e “desligado”associado a 0 e 1)..

Em particular, na álgebra Booleana de dois valores, cada variável pode assumir um dentre dois valores possíveis, os quais podem ser denotados por [F,V] (falso ou verdadeiro), [H,L] (high and low) ou ainda [0,1]. Nesta disciplina, adotaremos a notação [0,1], a qual também é utilizada em eletrônica digital. Como o número de valores que cada variável pode assumir é finito (e pequeno), o número de estados que uma função Booleana pode assumir também será finito, o que significa que podemos descrever completamente as funções Booleanas utilizando tabelas. Devido a este fato, uma tabela que descreva uma função Booleana recebe o nome de tabela verdade, e nela são listadas todas as combinações de valores que as variáveis de entrada podem assumir e os correspondentes valores da função (saídas).

Na álgebra Booleana, existem três operações ou funções básicas. São elas, operação

OU, operação E e complementação. Todas as funções Booleanas podem ser representadas em termos destas operações básicas.

Axiomas e propriedades: comutatividade, associatividade, distributividade

FUNÇÃO OU / OR Tabela Verdade:

Representação da porta lógica

(a) Função OU de 2 entradas (b) Função OU de 3 entradas

FUNÇÃO E / AND Tabela Verdade:

Representação da porta lógica

(a) Função E de 2 entradas (b) Função E de 3 entradas

FUNÇÃO COMPLEMENTAR Tabela Verdade:

Representação da porta lógica

Para desenhar um circuito a partir da equação Booleana, seguir a ordem de avaliação de expressões: 1. Parêntesis (dos mais internos para os mais externos); 2. Operações E;

3. Operações OU

1. Criar colunas para as variáveis de entrada e listar todas as combinações possíveis, utilizando a fórmula:

no de combinações = 2n (onde n é o número de variáveis de entrada);

2. Criar uma coluna para cada variável de entrada que apareça complementada na equação e anotar os valores resultantes;

3. Avaliar a equação seguindo a ordem de precedência, a partir do nível de parênteses mais interno:

1o negação de variáveis, i.e., operador complementação 2o multiplicação lógica, i.e., operador E

3o adição lógica, i.e., operador OU

Exercício:

Dada a função Booleana F= (A+B).C./A.D, determinar a tabela verdade e o circuito lógico associado a equação.

Representação gráfica: 1 porta E de 4 entradas onde a entrada A é invertida por um inversor.

2) Leis Fundamentais da Álgebra Booleana:

Seja A uma variável Booleana. Então:

Se A ? 0 Þ A = 1

Se A ? 1 Þ A = 0 (definição do espaço de uma variável Booleana)

Propriedades da Operação OU

Propriedade da Complementação

Propriedade Comutativa

Propriedade Associativa

Propriedade Distributiva

A×B×C×...=A+B+C+(2.1)

Para duas variáveis

A+B+C+...=A×B×C×(2.2)

Derivação das Expressoes Booleanas: Tabela Verdade, Simplificação, Equação Lógica através da soma de produtos (Lista todas as combinações das variáveis de entrada para os quais a função vale 1) ou produto de somas (Lista todas as combinações das variáveis de entrada para os quais a função vale 0). Construção do circuito lógico.

3) Simplificação de Funções Booleanas usando Mapas de Karnaugh

O método de simplificação apresentado na seção 2.6 é de aplicabilidade limitada, uma vez que é bastante difícil certificar-se que todos os pares de mintermos que podiam ser simplificados foram determinados. Alternativamente àquele método, há outro método de simplificação baseado na identificação visual de grupos de mintermos passíveis de serem simplificados. No entanto, para que se possa identificar tais grupos, é necessário que os mintermos sejam dispostos de maneira mais conveniente, o que será explicado a seguir. Na descrição do método de simplificação literal, foi mencionado que os pares de mintermos que se diferenciam de somente uma variável são passíveis de simplificação. Observando a ordem com que os mintermos de uma função Booleana qualquer (com, por exemplo, 3 variáveis) aparecem na tabela verdade, vemos que, se trocarmos o

3° mintermo com o 4° e trocarmos também o 7° mintermo com o 8°, obteremos uma nova ordem, na qual quaisquer dois mintermos adjacentes são passíveis de simplificação. É interessante notar também que o 1° mintermo pode ser simplificado com o 5°, o 2° mintermo pode ser simplificado com o 6° e assim por diante.

Repare que nessa nova tabela, quaisquer dois mintermos adjacentes (na horizontal ou na vertical) são passíveis de serem simplificados, pois só se diferenciam de uma variável. É importante ressaltar que esse conceito de adjacência não está restrito aos limites da tabela, uma vez que os elementos extremos de uma mesma linha (ou de uma mesma coluna) também são simplificáveis. Isto implica que a tabela de adjacências de mintermos da figura 2.1 pode e deve ser encarada como uma figura geométrica tridimensional do tipo “toróide” (ou uma “rosquinha”). A figura a seguir explicita as relações de adjacência dos mintermos para uma função de três variáveis.

É importante ressaltar que o conceito de adjacência é aplicável na horizontal e na vertical, mas nunca na diagonal. Por exemplo, observe que m0 e m5 não são adjacentes, pois não estão nem na mesma linha, nem na mesma coluna. O processo de simplificação usando a nova disposição inicia pela construção da tabela em si: os valores da função que se quer simplificar devem ser preenchidos conforme a nova ordem. Após, identificam-se todos os grupos de mintermos-1 adjacentes entre si.

Cada grupo origina um termo produto, no qual somente as variáveis comuns a todos os mintermos-1 permanecem. Desde que os grupos de mintermos-1 adjacentes tenham sido corretamente identificados, a simplificação se torna trivial.

Exemplo 2.3: simplificar a função F, cuja tabela verdade encontra-se no item 2.5.2. O primeiro passo é construir uma tabela para F, usando a nova disposição dos mintermos.

Após, deve-se identificar todos os grupos de mintermos-1 adjacentes entre si. Cada grupo de mintermos-1 originará um produto, conforme indicado na figura 213. A equação em soma de produtos simplificada será o OU entre os produtos encontrados:

Mapas de Karnaugh e Subcubos

A tabela modificada usada para a identificação dos mintermos-1 adjacentes no exemplo anterior é denominada mapa de Karnaugh (no caso, para 3 variáveis). Na figura 2.14 são mostrados os mapas de Karnaugh para funções de 2, 3 e 4 variáveis.

O primeiro passo para simplificar-se uma função usando mapa de Karnaugh é escolher o mapa conforme o número de variáveis da função e preencher os valores dos mintermos conforme a tabela verdade fornecida, ou conforme a equação fornecida. O segundo passo é identificar grupos de mintermos adjacentes que formem grupos de 2m elementos adjacentes entre si, com 0_m_n, onde n é o número de variáveis da função. Estes grupos são denominados subcubos.

No caso de se querer encontrar uma expressão em soma de produtos, estaremos interessados nos subcubos de mintermos-1. Então, cada subcubo contendo mintermos-

1 irá originar um produto, no qual uma ou mais variáveis poderão estar ausentes devido à simplificação que é obtida. Os produtos associados aos subcubos de mintermos-1, simplificados ou não, são denominados implicantes. É importante ressaltar que quanto maior o número de elementos do subcubo, maior será a simplificação obtida.

(Parte 1 de 2)

Comentários