Saiba tudo sobre a logica booleana

Você já se perguntou como um computador é capaz de fazer coisas como controle do orçamento doméstico jogar xadrez, ou verificar a ortografia em um documento? Há bem pouco tempo, essas coisas só podiam ser feitas por humanos. Agora, os computadores as fazem com aparente facilidade. Como um "chip" feito de silício e fios pode fazer algo que, aparentemente, só poderia ser realizado pelo cérebro humano?
Para entender a resposta para essa pergunta, primeiro você precisa conhecer algo chamado lógica booleana.
A lógica booleana, originalmente desenvolvida por George Boole em meados de 1800, permite que uma série de coisas pouco prováveis sejam mapeadas em bits e bytes.
O que há de genial sobre a lógica booleana é que, uma vez entendido seu processo, ela (ou pelo menos a parte necessária para compreender as operações de um computador) é absurdamente simples. Neste artigo, vamos
começar discutindo "portas" lógicas simples, e depois veremos como transformá-las em algo útil.



Portas simples




Há três, cinco ou sete portas simples que precisamos conhecer, dependendo de como se queira contá-las (logo veremos o motivo). Com elas, podem-se construir combinações que implementarão qualquer componente digital imaginável. Essas portas parecerão um pouco limitadas e incrivelmente simples, mas veremos algumas combinações interessantes nas seções seguintes que as tornarão bem mais inspiradoras. Se você ainda não leu Como funcionam os bits e os bytes, será útil fazê-lo antes de continuar. A porta mais simples chama-se "inversor", ou porta NOT.
Ela usa um bit como entrada e produz seu oposto como saída. Segue abaixo, a tabela lógica para a porta NOT e seu símbolo comummente usado em diagramas de circuitos:

Porta NOT
A Q 0 1 1 0

Nesta figura, perceba que a porta NOT tem uma entrada chamada A e uma saída chamada Q
("Q" é usada para a saída porque se usarmos "O" (do inglês "output") ela pode se confundir com zero). A tabela mostra o comportamento da porta. Ao atribuirmos o valor 0 a A, Q produz um 1. Ao
atribuirmos o valor 1 a A, Q produz um 0. Simples.
A porta AND executa uma operação lógica "e" sobre duas entradas, A e B:

Porta AND
A B Q 0 0 0 0 1 0 1 0 0 1 1 1

A idéia por trás de uma porta AND é, "Se A = 1 E
B = 1, então Q = 1." Podemos notar este comportamento na tabela lógica desta porta. A tabela deve ser lida linha por linha, assim:

Porta AND

A B Q 0 0 0 Se A = 0 E B = 0, Q = 0. 0 1 0 Se A = 0 E B = 1, Q = 0. 1 0 0 Se A = 1 E B = 0, Q = 0. 1 1 1 Se A = 1 E B = 1, Q = 1.

A próxima é a porta OR. Sua idéia básica é "Se A = 1 OU B = 1 (ou se ambas forem iguais a 1), então Q = 1."

Porta OR
A B Q 0 0 0 0 1 1 1 0 1 1 1 1

Essas são as três portas básicas (uma maneira de contá-las). É bastante comum que se reconheçam outras duas também: a porta NAND e a porta NOR.
Essas são combinações simples da porta AND ou da porta OR com a porta NOT. Se as incluirmos, a contagem subirá para cinco. Este é o funcionamento básico das portas NAND e NOR (elas são apenas inversões
das portas AND e OR):

Porta NOR
A B Q 0 0 1 0 1 0 1 0 0 1 1 0

Porta NAND
A B Q 0 0 1 0 1 1 1 0 1 1 1 0

As duas últimas portas que podem aparecer na lista são as portas XOR e XNOR, também conhecidas como portas "OR exclusivo" e "NOR exclusivo", respectivamente. Estas são suas tabelas:

Porta XOR
A B Q 0 0 0 0 1 1 1 0 1 1 1 0

Porta XNOR
A B Q 0 0 1 0 1 0 1 0 0 1 1 1

A idéia por trás da porta XOR é: "se A= 1 OU B = 1, mas NÃO
ambas, então Q = 1." O motivo pelo qual XOR pode não constar de uma lista de portas é porque ela pode ser facilmente implementada com o uso das três portas listadas originalmente. Esta é uma implementação:
Se tentarmos todos os quatro padrões diferentes para A e B e os rastrearmos através do circuito, veremos que Q se comporta como uma porta XOR. Como existe um símbolo bastante compreensível para as portas XOR, costuma ser mais fácil pensar em XOR como uma "porta padrão" e usá-la da mesma maneira que as portas AND e OR nos diagramas de
circuitos.



Somadores simples




No artigo sobre bits e bytes, você conheceu a adição binária.
Nesta seção, você verá como podemos criar um circuito capaz de executar a adição binária com o uso das portas descritas na seção anterior. Comecemos com um somador de um único bit.
Digamos que, em um dado projeto, seja necessária a adição de bits para que se obtenha uma resposta. Começamos a projetar o circuito verificando todas as combinações lógicas. Podemos fazer isso a partir das quatro seguintes somas:

0	0	1	1
+ 0	+ 1	+ 0	+ 1
0	1	1	10

Tudo vai bem, até que aparece 1 + 1. Nesse caso, você terá de se preocupar com aquele carry bit
(bit de transporte) irritante. Se não se importar em transportá-lo (pois, afinal, trata-se de um problema de adição de 1 bit), você poderá resolver esse problema com uma porta XOR. Do contrário, talvez possa reescrever as equações de modo que sempre sejam incluídos 2 bits de saída, assim:

0	0	1	1
+ 0	+ 1	+ 0	+ 1
00	01	01	10

A partir dessas equações, podemos formar a tabela lógica:

Somador de 1 bit com Carry-Out

A B Q CO 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1

Observando a tabela, vemos que é possível de se implementar Q com a porta XOR e CO (carry-out) com a porta AND. Simples.
E se quisermos somar dois bytes de 8 bits? Aí fica um pouco mais complicado. A solução mais simples é modularizar o problema em componentes reutilizáveis e replicar os componentes. Nesse caso, é necessária a criação de apenas um componente: um somador binário completo.
A diferença entre um somador completo e o somador que vimos anteriormente é que o somador completo aceita uma entrada A e uma B junto com uma entrada carry-in (CI - "vem um"). Com um somador completo, poderemos enfileirar oito deles para criar um somadorda largura de
um byte e deixar transitar o bit de transporte, em cascata, de um somador para o próximo.
A tabela lógica para um somador completo é um pouco mais complicada do que as tabelas que usamos antes, porque agora temos 3 bits de entrada. Fica assim:

Somador Completo de 1 bit com Carry-In e Carry-Out

CI A B Q CO 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1

Há
muitas maneiras de se implementar essa tabela. Vamos apresentar um método de fácil compreensão. Verificando o bit Q, vemos que os 4 bits superiores comportam-se como uma porta XOR com relação a A e B, enquanto os 4 bits inferiores comportam-se como uma porta XNOR com relação a A e B. Da mesma maneira, os 4 bits superiores de CO comportam-se como uma porta AND com relação a A e B, e os 4 bits inferiores comportam-se como
uma porta OR. Levando em consideração os fatos, o seguinte circuito implementa um somador completo:
Definitivamente, esse não é o método mais eficiente para se implementar um somador completo, mas é de fácil compreensão e bastante lógico. Se for do seu interesse, veja o que se pode fazer para implementar a mesma lógica com
menos portas.
Agora, temos uma peça funcional chamada "somador completo". Um engenheiro de computação, então, desenvolve uma "caixa preta", para que os dados fiquem registrados e ele possa deixar de se preocupar com os detalhes do componente. Uma caixa preta para um somador completo seria assim:
Com a caixa preta, é fácil desenvolver um somador completo de 4 bits:
Neste diagrama, o carry-out de cada bit alimenta diretamente o carry-in do próximo bit. Um 0 é conectado ao primeiro bit do tipo carry-in. Se inserirmos dois números de 4 bits nas linhas A e B, a soma de 4 bits aparecerá nas linhas Q com um 1 bit adicional para o último bit do tipo carry-out. Esse encadeamento pode se estender tanto quanto desejável, usando 8, 16 ou 32 bits.
O somador de 4 bits que acabou de ser criado é chamado de somador com propagação do carry (ripple-carry
adder). Ele tem esse nome porque os bits de transporte "propagam" de um somador até o próximo. Essa execução é vantajosa por sua simplicidade, mas inconveniente pelos problemas de velocidade. Em um circuito real, as portas levam tempo para mudarem de estado (uma questão de nanossegundos, mas, em computadores de alta velocidade, nanossegundos são significativos). Assim, somadores com propagação do carryde 32 ou 64 bits devem levar de 100 a 200 nanossegundos para terminar sua soma final por causa da propagação do carry. Por esse motivo, os engenheiros criaram somadores mais avançados chamados somadores com carry antecipado (carry-lookahead adders). O número de portas necessárias para implementar o somador com carry antecipado é grande, mas seu tempo para terminar a soma é muito menor.



Flip-flops




Uma das coisas mais interessantes que podemos fazer com portas booleanas é criar memória. Se as portas forem dispostas corretamente, elas vão se lembrar do valor de entrada. Este conceito simples é a base da RAM (memória de acesso randômico) dos computadores e também possibilita a criação de uma ampla variedade de circuitos úteis. A memória é baseada em um conceito chamado realimentação (feedback), o que significa que o valor de saída de uma porta retorna à sua entrada. O mais simples circuito com realimentação com o uso de dois inversores está exemplificado abaixo:
Ao acompanhar o caminho da realimentação, nota-se que, se o valor de Q for igual a 1, ele sempre será 1. Se por acaso for 0, sempre será 0. Embora
esse circuito em particular não tenha muito uso, é possível ver como a realimentação funciona.
Em circuitos "reais", o uso dessa abordagem simples de realimentação do inversor é perfeitamente possível.
Um circuito com realimentação de mais utilidade com o uso de duas portas NAND está exemplificado abaixo:
Esse circuito tem duas entradas (R e S) e duas saídas (Q e Q'). Por causa da realimentação, sua tabela lógica fica um pouco incomum se a compararmos àquelas vistas anteriormente:

R	S	Q	Q'
0	0		Inválida
0	1	1	0
1	0	0	1
1	1		Retém

O que a tabela lógica mostra é que:

• se R e S tiverem valores opostos, Q acompanha S e Q' é o inverso de Q;
  
• se tanto R quanto S recebem valor 1 simultaneamente, então o circuito retém o que foi apresentado anteriormente em R e S.
  

Há ainda o estado inválido.
Nesse estado, tanto R quanto S valerão 0, o que não tem significado em aplicação de memória, enquanto memória, nada vale. Para prevenir esse estado ilegal, costuma-se acrescentar uma pequena lógica condicional no lado da entrada, conforme abaixo: Neste circuito, há duas entradas (D e E). Podemos pensar em D como "Data" (dado) e E como "Enable" (habilitar). Se E valer 1, Q acompanhará D. Se E mudar para 0, no entanto, Q lembrará do que tiver sido visto por último em D.
Um circuito com este comportamento costuma ser conhecido como flip-flop.
Um flip-flop bastante comum é o flip-flop J-K. Não está claro de onde veio o nome "J-K", mas ele costuma ser representado em um quadro como este:
Neste diagrama, P significa "Preset" (pré-definido), C significa "Clear" (limpar) e Clk significa "Clock" (relógio). A tabela lógica fica assim:

P	C	Clk		J	K	Q	Q'
1	1	1-para-0		1	0	1	0
1	1	1-para-0		0	1	0	1
1	1	1-para-0		1	1		Alterna
1	0	X		X	X	0	1
0	1	X		X	X	1	0

A tabela informa que: primeiro, Preset e Clear ignoram J, K e Clk completamente. Se o valor de Preset for modificado para 0, então o valor de Q será modificado para 1; e se o valor de Clear for modificado para 0, então o valor de Q será modificado para 0, não importando o que J, K e Clk estiverem fazendo. No entanto, se Preset e Clear tiverem valor igual a 1, então J, K e Clk poderão operar. A notação 1-para-0 significa que, quando o relógio mudar de 1 para 0, os valores de J e de K, caso sejam opostos, serão memorizados. J e K ficam armazenados na borba da descida do relógio (a transição de 1 para 0). Porém, se tanto o valor de J
quanto o de K equivalerem a 1 borba da descida do relógio, então Q simplesmente alterna, ou seja, muda de seu estado atual para o estado oposto.
Agora,você deve estar se perguntando: "e para que serve isso?". Na verdade, o conceito de "disparo por borda" é muito útil. O fato de o flip-flop J-K apenas "armazenar" (latching) as entradas J-K em uma transição de 1 para 0 faz com que ele seja muito mais útil como dispositivo de memória.
Os flip-flops J-K também são bastante úteis em contadores (muito usados na criação de relógios digitais). Aqui está o exemplo de um contador de 4 bits usando flip-flops J-K:
As saídas para este circuito são A, B, C e D, que representam um número binário de 4 bits. Na entrada do relógio do flip-flop, mais à esquerda, aparece um sinal mudando de 1 para 0 e de volta para 1 repetidamente (um sinal oscilatório). O contador contará com as bosrdas de descida que vê neste sinal, ou seja, a cada vez que este sinal que chega mudar de 1 para 0, o número de 4 bits representado por A, B, C e D será incrementado em 1. Então, o contador irá de 0 a 15 e retornará a 0.
Podemos acrescentar quantos bits quisermos a este contador e contarmos o que quisermos. Por exemplo, com o uso de uma chave magnética em uma porta, o contador registrará o número de vezes que a porta se abre e se
fecha. Com um sensor ótico colocado na estrada, o contador poderá registrar o número de carros que passarem.
Outro uso do flip-flop J-K é na criação de um latch disparado por borda, conforme abaixo:
Neste arranjo, o valor de D é armazenado quando o nível do clock vai de baixo para o alto. Os latches têm extrema importância no projeto de unidades centrais de processamento (CPUs) e periféricos em computadores.



Implementação de portas




Nas seções anteriores, vimos que, com o uso de portas booleanas simples, podemos implementar somadores, contadores, latches e assim por diante. É um avanço e tanto pois, até pouco tempo atrás, só os seres humanos
sabiam somar dois números. Sem muito trabalho, é possível projetar circuitos Booleanos que implementem subtração, multiplicação, divisão...
veja que estamos próximos de uma calculadora de bolso. A partir dela, não é longo o caminho até as CPUs usadas nos computadores. E como implementar essas portas na vida real? O Sr. Boole as concebeu no papel e no papel elas parecem ótimas. No entanto, precisamos implementá-las fisicamente para que as portas possam executar sua lógica
efetivamente. Feita a transição, teremos nos lançado à criação de verdadeiros dispositivos computacionais.
O modo mais simples de se entender a execução física da lógica booleana é com o uso de relés.
Essa é a forma pela qual foram implementados os primeiros computadores.
Atualmente, os relés foram substituídos pelos sub-microscópicos transistores criados em chips de silício. Esses transistores são incrivelmente pequenos e rápidos, e consomem bem pouca energia se comparados a um relé. No entanto, os relés são incrivelmente fáceis de se entender, e podem implementar lógica booleana de forma muito simples.
Por causa dessa simplicidade, você será capaz de ver que o mapeamento, desde as "portas na teoria" até "ativar portas implementadas em realidade física", é algo possível e simples. Realizar o mesmo
mapeamento com transistores é tão fácil quanto.
Vamos começar com um inversor. É fácil implementar uma porta NOT com um relé: iremos usar voltagens que representam estados de bit. Atribuímos ao binário 1 o valor de 6 volts, e ao binário 0 o valor de zero volts (terra). Usamos uma bateria de 6 volts para prover os circuitos de energia. A porta NOT, portanto, terá a seguinte aparência:
Se esta figura não faz sentido para você, leia Como funciona o relé para obter uma explicação.
Neste circuito, você verá que, se atribuirmos zero volts a A, Q receberá 6 volts; e se atribuirmos 6 volts a A, Q receberá zero volts. É muito fácil de se implementar um inversor com um relé.
Também é fácil implementar uma porta AND com dois relés:
Aqui, note que, se atribuirmos 6 volts para A e B, Q receberá 6 volts. Do contrário, Q receberá zero volts. Este é exatamente o comportamento que se espera de uma porta AND. A porta OR é ainda mais simples: é só juntar dois fios, A e B, para criá-la. Você também poderá utilizar dois relés paralelos, se assim o desejar.
Partindo desse axioma, é possível criar três portas básicas: E, OU ou NÃO (são mais comuns os seus equivalentes em inglês: AND, OR e NOT), a partir dos relés. Podemos juntar estas portas físicas usando os diagramas lógicos acima para criar um somador físico de 8 bits (ripple-carry adder). Se usarmos chaves simples (interruptores) para aplicar entradas A e B ao somador e juntarmos todas as oito linhas Q a lâmpadas, poderemos somar quaisquer dois números e ler os resultados nas lâmpadas ("acesas" = 1,
"apagadas" = 0).
A lógica booleana sob a forma de portas simples é bastante direta. A partir delas, criam-se funções mais
complexas, como a soma. A implementação física dessas portas é fácil e possível. Desses três fatores, obtemos o coração da revolução digital e podemos entender, em profundidade, como funcionam os computadores.







fonte: [Tens de ter uma conta e sessão iniciada para poderes visualizar este link]