Expressões Booleanas e Circuitos de Lógica Combinatória

Expressões Booleanas e Circuitos de Lógica Combinatória

Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br

Teoria 4Expressões Booleanas

Circuitos de Lógica Combinatória

4.1 Expressões Booleanas Geradas por Circuitos Lógicos:

Todo circuito de lógica combinatória, por mais complexo que possa parecer é na verdade o resultado de um arranjo de interligações de blocos que executam funções booleanas elementares (Portas Lógicas). Um exemplo de circuito de lógica combinatória e sua respectiva expressão de saída são mostrados a seguir:

Podemos fazer a análise desse circuito escrevendo as expressões parciais na saída de cada porta lógica, como se mostra a seguir:

Elaborando-se a tabela da verdade do circuito, podemos conhecer o estado da saída para todas as possíveis combinações de entrada:

Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br

Também podemos fazer a tarefa inversa, ou seja, a partir de uma dada expressão booleana, construir o circuito lógico que a implementa, como veremos a seguir.

4.2 Circuitos Lógicos Elaborados a Partir de Expressões Booleanas:

Dada uma equação Booleana qualquer, é possível implementar-se o circuito lógico o qual ela representa. Um circuito lógico é composto de um arranjo combinatório de portas lógicas, as quais estão relacionadas às operações lógicas que são realizadas pela expressão sobre as variáveis de entrada.

O procedimento para se desenhar o circuito lógico a partir de uma expressão booleana, é praticamente o mesmo usado na avaliação da expressão e consiste em se identificar as operações lógicas que aparecem na expressão e substituí-las por portas lógicas com as respectivas ligações a partir das variáveis de entrada.

Deve-se respeitar a hierarquia das operações (precedência dos operadores) para que o circuito lógico realize fielmente a expressão desejada. Por exemplo, a operação de produto lógico (operação E) tem precedência sobre a operação de soma lógica (operação OU), no entanto com o uso de parênteses podemos quebrar esta ordem, pois a operação que estiver entre parênteses tem prioridade maior.

Os resultados de cada operação, ou seja, o sinal elétrico na saída de cada porta, são conduzidos por fios, os quais, no desenho, são representados por linhas simples.

Tomemos como exemplo a expressão:

independentes que aparecem na expressão, que neste caso são três: A, B e C, e as possíveis ocorrências de operação de negação aplicada diretamente sobre alguma dessas variáveis, por exemplo, na expressão ocorre A, que é a variável A sob o operador de negação (inversão), o qual é implementado por uma porta NÃO.

Repare que há duas ocorrências de variáveis diretamente invertidas: A e B (somente a variável C não ocorre invertida na expressão). Assim vamos precisar de duas portas NÃO, uma para a variável A e outra para a variável B. Estas operações de negação diretamente sobre as variáveis são as operações mais internas da expressão:

2- Em seguida, vamos decompondo a expressão em subexpressões, quebrando-a em partes, a partir da última operação na ordem natural de precedência dos

Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br

Repare que as duas subexpressões são unidas por uma operação E. Esta operação é implementada por uma porta E, de duas entradas.

A subexpressão )(CBA++ é trivial, pois trata-se de uma série de duas operações de soma lógica, podendo ser implementada por uma porta OU de três entradas.

Assim podemos atualizar o circuito lógico:

(operação E entre dois termos) de somas (operação OU, dentro dos parênteses), que por fim é negado. Entretanto esta subexpressão deve ainda ser decomposta em novas subexpressões, para que possamos solucionar individualmente cada um dos termos:

Deste modo fica evidente que tanto a 3ª quanto a 4ª subexpressões podem ser implementadas com portas OU de duas entradas. Assim podemos por fim completar o circuito lógico:

3ª subexpressão 4ª subexpressão Operação NÃO-E

Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br

4.3 Álgebra Booleana:

Definir a estrutura matemática da Álgebra Booleana significa incorporar as propriedades básicas do Cálculo Proposicional e da Teoria dos Conjuntos, ou seja, ela é um outro modelo mas de uma mesma estrutura matemática. O conceito de Álgebra Booleana foi formulado pelo matemático inglês George Simon Boole (1815-1864), por volta de 1850, que imaginou um conjunto de símbolos matemáticos para substituir as sentenças declarativas. Boole propôs através da publicação do trabalho intitulado “An investigation of the laws of thought”, numa notação numérica e algébrica, aquilo que até aquele momento somente era tratado de modo discursivo: a lógica.

Apesar da gritante aplicabilidade da álgebra booleana, até a década de 1930, engenheiros eletricistas podiam construir circuitos eletrônicos com relés para resolver problemas lógicos e matemáticos, mas a maioria o fazia sem qualquer processo, de forma particular, e sem rigor teórico para tal. Tal fato mudou com a tese de mestrado de Claude E. Shannon de 1937: “A Symbolic Analysis of Relay and Switching Circuits”. Enquanto tomava aulas de Filosofia, Shannon foi exposto ao trabalho de George Boole, e percebeu que tal conceito poderia ser aplicado em conjuntos eletromecânicos para resolver problemas de lógica. Tal idéia, que utiliza propriedades de circuitos eletrônicos para a lógica e, apesar da área de telefonia ter sido a pioneira em beneficiar-se deste conceito, ele tornou-se desde então, a base de todos os computadores digitais.

A álgebra de Boole é caracterizada por uma estrutura muito simples, que consiste em atribuir o valor 1 a uma proposição verdadeira e o valor 0, a uma proposição falsa. Aplicando-se esse conceito a um circuito elétrico, pode-se associar, por exemplo, aos atributos apresentados na tabela ao lado:

Expressões e equações booleanas podem ser manipuladas quase que da mesma maneira que expressões algébricas ordinárias, segundo leis bastante similares. Usualmente

Nível lógico 0 Nível lógico 1 aberto fechado sem tensão com tensão desligado ligado apagado aceso

Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br manipulamos as expressões booleanas quando precisamos obter uma forma simplificada da mesma.

Fazendo uso das propriedades básicas da álgebra booleana, aliado a alguns postulados e teoremas, podemos simplificar tais expressões, e se lembrarmos que para cada circuito lógico temos uma expressão booleana correspondente, entenderemos que simplificar expressões implica também em simplificar os circuitos lógicos correspondentes.

4.4 Propriedades da Álgebra Booleana:

As principais expressões resultantes das propriedades, dos postulados e dos teoremas das funções lógicas booleanas, são apresentadas na tabela a seguir (é possível provar todas as propriedades da álgebra booleana usando os teoremas e postulados, mas não iremos realizar provas formais de todas elas):

P1: A0A=+
P5: 00A=×
P11:C)(BACB)(A++=++
P2: 11A=+
P6: A1A=×
P12:C)(BACB)(A×=×
P3:A=+
P7:A=×
P13:CABAC)(BA×+×=+×
P4:1AA=+
P8:0AA=×
P9:ABBA+=+
P10:ABBA×=×
P15:B)A(CCBCA+×=×+×
P16:A=
P23:A)BA(B)(A=+×+
P17:ABAA=×+
P24:ABABA=×+×
P18:BABAA+=×+
P25:ACCBBAACBBA×+×+×=×+×+×C
P19:ABAA=×+
P21:BAB)A(A×=+×
P20:AB)A(A=+×
P22:A)BA(A=+×
Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br

P26:BABA×=+ DEMORGAN
P27:BABA+=× DEMORGAN
P28:B=×+×AAA OU-XCLUSIVO
P29:BABABABABA=×+×=×+× NÃO-OU-EXCLUSIVO (E-COINCIDÊNCIA)
P30:B)(ACC)(ABC)(BA== ASSOCIATIVA

4.5 Simplificação Algébrica de Expressões Booleanas (Manipulação de Expressões Booleanas):

Podemos transformar uma expressão booleana em uma expressão equivalente mais simples por aplicar a mesma os postulados e teoremas e propriedades da álgebra booleana. Isto é importante se quisermos converter uma dada expressão para uma forma canônica (uma forma padronizada) ou quisermos minimizar o número de literais ou termos em uma expressão.

Minimizar expressões ou seus termos é importante porque os circuitos lógicos freqüentemente consistem de componentes individuais que implementam cada termo ou cada literal para uma dada expressão. Minimizar expressões permite que o projetista utilize menos componentes eletrônicos e, então, possa reduzir o custo do sistema.

O procedimento é intuitivo, não há regras fixas que possamos aplicar para otimizar uma dada expressão. Se existirem n maneiras de iniciarmos o processo de manipulação da expressão, para cada uma dessas maneiras existirão m outras maneiras de prosseguir com o processo. Semelhante à construção de provas matemáticas, a manipulação das expressões visando a simplificação é uma habilidade individual que vem geralmente em função de experiência. Todavia, uns poucos exemplos, como o apresentado a seguir, podem mostrar um bom número de possibilidades:

Exemplo 1: Consideremos a expressão original:

Que equivale ao seguinte circuito lógico:

OR4

Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br

Aqui temos uma típica expressão de soma de produtos composta de 4 termos. Olhando para os dois primeiros termos temos o literal C como termo comum, o qual podemos colocar em evidência. Já nos dois últimos termos temos C como termo comum. Assim:

Podemos prosseguir verificando que dentro do primeiro parênteses temos: BABA×+× e que isso equivale a BA. De modo semelhante, no segundo parênteses temos: BABA×+×

Usando a estratégia da substituição de BA por X temos:

Se retornarmos a substituição de X, chegamos a:

Y U1

AND3

U1EOR3 U1 EOR2

EOR2

Serviço Nacional ESCOLA SENAI “MARIANO FERRAZ"CEP: 05311-020 - São Paulo - SP

SENAI Rua Jaguaré Mirim, 71 - Vila Leopoldina” de Aprendizagem Fone/Fax: (011)3641-0024

Industrial NAI E-Mail: ahp106@sp.senai.br

Temos uma expressão de produto de somas a qual podemos simplificar:

P08: AY= Que equivale ao circuito:

A Y É isso mesmo, o circuito todo é simplificado para apenas um fio.

4.5.1 Exercícios de simplificação algébrica de expressões: Dada as expressões:

Y = ABC + 321CDBA + {CBA + {CBA Simplifique-as algebricamente andrellenz@hotmail.com

Comentários