O que é expressões Booleanas


O que é Expressões booleanas


 
Pesquisa refinada

Dica!
É interessante combinar as várias expressões. Você pode buscar, por exemplo, carros AND reparo NOT venda.
Você precisa fazer uma pesquisa sobre carros. Digitou a palavra, clicou em Enter e decepção. Milhares de sites vendendo carros, um ou outro de conserto e reparo perdido no meio daquela confusão. Não é hora de desespero, mas de limitar um pouco o campo de busca. Para isso, usaremos mais uma palavra-chave e as expressões booleanas.

Veja como é fácil:

• AND / E
Esses símbolos permitem que você encontre resultados que contenham obrigatoriamente as duas palavras. Em nosso exemplo, você poderia digitar carros AND reparo ou carro E conserto.
• OR / OU
A busca com or / ou fornece endereços com uma das palavras digitadas. Com carros OR conserto ou carros OU reparo você encontrará sites que têm a palavra "carros" e também sites com a palavra "reparo".

• NOT / NÃO
Essa é uma busca exclusiva. Se você sabe que ao buscar "carros" muitos sites de vendas de carro podem surgir em sua frente, digite carros NOT vendas ou carros NÃO vendas. Serão listados sites com a palavra "carros", mas sem a palavra "venda".

• Aspas
Escreva a expressão entre aspas quando quiser encontrar as palavras juntas e na mesma seqüência. Um exemplo? "carros reparo". Todos os sites encontrados terão, necessariamente, essa expressão.

• Asteriscos
O uso de asterisco permite a busca de uma parte da palavra. Assim, se você digitar carros*, vai encontrar resultados como: tunado, rapido, carro de rua etc.



 NOÇÕES DE ÁLGEBRA BOOLEANA


O conceito de Álgebra Booleana foi formulado pelo matemático inglês George Boole em 1850.
foi um matemático e filósofo britânico, criador da Álgebra Booleana, base da atual aritmética computacional.
Suas teorias têm implicações no desenvolvimento do computador, baseado em dígitos binários.

Nascimento: 2 de novembro de 1815 em Lincoln, Lincolnshire, Inglaterra
Faleceu: 8 de dezembro de 1864 em Ballintemple, County Cork, Irlanda

Nasce em Lincoln, em família pobre, e estuda por conta própria, dedicando-se ao latim e ao grego. Aos 16 anos, começa a trabalhar como professor de escolas elementares. Quatro anos depois, fundou um colégio particular, que dirigio por vários anos. Interessa-se por matemática e, depois de ler obras de franceses como Laplace e Legendre, passa a redigir artigos para o Jornal de Matemática da Universidade de Cambridge.
Em 1847, no artigo Análise Matemática da Lógica, introduz o uso de símbolos para expressar processos lógicos que podem então ser lidos com o mesmo rigor de uma equação algébrica. Com isso, dá origem à lógica moderna. É condecorado pela Royal Society, em 1844, por suas contribuições ao desenvolvimento da análise matemática. Em 1848 publica Os Cálculos da Lógica e, em 1854, Uma Investigação das Leis do Pensamento.
George Boole aproximou a lógica em uma nova forma de reduzi-la a uma Álgebra simples, incorporando a lógica em matemática. Ele também trabalhou em equações diferenciais, cálculo de diferenças finitas e métodos gerais de probabilidade.


http://media-2.web.britannica.com/eb-media/68/6768-004-1F2EC5E9.jpg
George Boole



Álgebra booleana tem larga aplicação em comutação telefônica e ao design dos computadores modernos. O trabalho de Boole tem de ser visto como um passo fundamental na revolução dos computadores de hoje.


Citações de George Boole


Não importa como corrigir um teorema matemático pode parecer ser, um nunca deveria estar convencido de que não havia algo imperfeito sobre isso até que ele também dá a impressão de ser bonito.
Citado em D MacHale, secções Comic (Dublin 1993)

Presumo que poucos que têm dado atenção à história da análise matemática, vai duvidar que tem sido desenvolvido em uma determinada ordem, ou que a ordem tem sido, em grande medida, necessária - a ser determinado, quer por etapas de dedução lógica, ou pela introdução sucessiva de novas idéias e concepções, quando o prazo para a sua evolução havia chegado.

Das muitas formas de falsa cultura, uma prematura convence com abstrações, é talvez a maior probabilidade de ser fatal para o crescimento de um vigor masculino do intelecto.
Preface to A treatise on differential equations (1859) Prefácio a um tratado sobre equações diferenciais (1859)

Probabilidade é a expectativa fundada no conhecimento parcial. Um conhecimento perfeito com todas as circunstâncias que afetam a ocorrência de um evento, mudar a expectativa em segurança, e deixar espaço nem inferiores a procura de uma teoria das probabilidades.
An Investigation of the Law of Thought (New York, 1951). Uma investigação da lei do pensamento (Nova Iorque, 1951).

Para desdobrar as leis secretas e as relações dessas faculdades alta de pensamento pelo qual todos além do conhecimento meramente perceptivo do mundo e de nós mesmos é atingido ou amadurecido, é um objeto que não se encontra em necessidade de recomendação para uma mente racional.

Não é da essência da matemática para estar familiarizado com as idéias de número e quantidade.
An investigation of the laws of thought (New York, 1951). Uma investigação das leis do pensamento (Nova Iorque, 1951).



Expressões booleanas e ÁLGEBRA BOOLEANA

A lógica booleana para criar instruções de validação/substituição. A expressão de lógica booleana é uma estrutura lógica que pode ser verdadeira ou falsa. As expressões podem ser ligadas através de operadores (como AND, OR e NOR) para possibilitar a criação de expressões complexas.

A lógica booleana usa tabelas verdade (TRUE ou FALSE) para determinar o valor verdade (TRUE ou FALSE) das expressões. Uma tabela verdade atribui o valor T (TRUE) ou F (FALSE) a cada parte de uma expressão complexa e, em seguida, determina se a expressão combinada é verdadeira ou falsa.

A figura a seguir utiliza uma tabela verdade para o operador AND (conjunção) para determinar se um valor deve ser substituído.




Nesse exemplo, se o movimento tem a conta 500000 e o centro de custo 150, a expressão combinada será verdadeira e o valor será substituído. Se o movimento não tem a conta 500000 nem o centro de custo 150, a expressão combinada será falsa e o valor não será substituído.
O usuário pode utilizar uma expressão booleana em um processo e, em seguida, utilizar a mesma expressão em outro processo ao ligar a expressão a outra. Para usar uma expressão booleana em um processo ou em outra expressão, o usuário deve criar uma regra.

Regras

A regra é uma expressão booleana que pode ser utilizada como pré-requisito ou verificação em outra regra. As regras permitem que o usuário consulte expressões booleanas utilizadas com freqüência através do nome da regra.

As regras são utilizadas em:

  • Validações
  • Substituições
  • Seleção de ledger
  • Report writer
  • Rollups




Simplificando a Lógica Booleana 

x, y e z são variáveis que podem ser True ou False (Verdadeiro ou Falso)
"!" significa "Not" (Não)
"|" significa "Or" (Ou)
"&" significa "And" (E)
"==" significa "Igual"

!(!x) == x
x | x == x
x | !x == true
!x | !y == !(x & y) - DeMorgan's Theorem
!x & !y == !(x | y) - DeMorgan's Theorem
x & x == x
x & !x == false
x | y == y | x - Commutative Law
x & y == y & x - Commutative Law
(x | y) | z == x | (y | x) - Associative Law
(x & y) & z == x & (y & z) - Associative Law
x & y | x & z == x & (y | z) - Distributive Law
(x | y) & (x | x) == x | (y & z) - Distributive Law
x | x & y == x
x & y | x & !y == x
(x & y) | (!x & z) | (y & z) == (x & y) | (!x & z)
(x | y) & (!x | z) & (y | z) == (x | y) & (!x | z)
x & (x | y) == x
(x | y) & (x | !y) == x

Simplificando a Lógica Booleana

Seria mais acurado chamar de  álgebra booleana, mas os conceitos são intercambiáveis. A lógica envolvida é a  proposicional. Uma expressão algébrica desse tipo equivale a uma proposição lógica que pode ser sempre posta na forma canônica (expressa apenas com disjunção "ou", conjunção "e" e negação "~").

É sempre possível  simplificar uma expressão booleana. Isso é equivalente ao processo de otimização (no sentido de simplificação) de circuitos digitais, que é importantíssimo na arquitetura de microprocessadores, por exemplo.

Esse problema (simplificação de expressão booleana) é  NP-hard e é equivalente à simplificação de expressões em uma lógica proposicional. O fato de ele ser computável garante que toda proposição nessa lógica é demonstrável, uma vez que basta simplificar a expressão que contém todas as hipóteses conjuntas entre si e com a negação da tese (H1 e H2 e H3 e ... e Hn e ~T -- em uma espécie de prova geral por absurdo). É por isso que pode existir a linguagem de programação  Prolog.

Essa matéria faz uma ligação com muita coisa que a gente vê em  Ciência da Computação e é muito boa para perceber a superposição das áreas. Daqui podemos ir para a  Inteligência Artificial (que é onde eu gosto de estar) e além.



O texto é sobre robótica, mas vale também para outras áreas.



Tome o conjunto booleano B:={0,1} com os operadores binários "ou" e "e" que você apresentou (representados por "|" e "&", respectivamente). Represente o operador  ou-exclusivo por "#". Assim, x # y := (!x & y) | (x & !y) (definição de ou-exclusivo, na forma canônica).

Perceba que a tripla (B,#,&), isto é, o conjunto B e esses dois operadores (ou-exclusivo e conjunção), forma uma estrutura algébrica de  anel (ring) e, em particular, de  corpo (field).

Mais interessante ainda é que esse corpo é  isomorfo ao Z2 (anel das  classes de equivalência módulo 2 sobre os inteiros -- o mesmo que o anel quociente Z/2Z). Olhe onde a gente acaba parando, aliás, chegando, porque não para por aí.

Os operadores "!", "|", "&", "||", "&&", "==", "!=" "~", e "^" São da linguagem de programação  C# que é uma evolução do  C++ (e do  Java) que por sua vez é uma evolução da  Linguagem C.

Esses símbolos também são usados ao todo ou em parte em outras linguagens tais como:  ActionScript,  JavaScript,  PHP,  Python,  Perl,  Ruby e outras.




Expressões booleanas


"Uma das características da investigação científica é procurar padrões ou semelhanças entre fenômenos observados"(livro I). Vimos que o Cálculo Proposicional e a Teoria dos Conjuntos possuem algumas propriedades em comum ou sejam são estruturas matemáticas que, juntamente com operações ou relações entre seus objetos obedecem certas regras." Podemos comparar uma estrutura matemática a um esqueleto humano pois, embora as aparências externas das pessoas sejam diferentes, a forma e a disposição dos ossos são as mesmas."(livro I). Assim, vamos definir, uma estrutura matemática, Álgebra Booleana, que incorpora as propriedades básicas do Cálculo Proposicional e da Teoria dos Conjuntos, ou seja, é um outro modelo de uma mesma estrutura matemática. O conceito de Álgebra Booleana foi formulado pelo matemático inglês George Boole por volta de 1850.

Por ÁLGEBRA BOOLEANA entendemos um conjunto B={p, q, r , ..} junto com duas operações binárias + e · em B, uma operação singular em B e dois elementos distintos 0 e 1 de B tais que valem as seguintes propriedades: (para todo p , q , r em B ) :
 

Associativa (p + q) + r = p + (q + r) (p · q) · r = p · (q · r)
Comutativa p + q = q + p p · q = q · p
Idempotente p + p = p p · p = p
Absorção (p · q) + p = p (p + q) · p = p
Distributiva p + (q · r) = (p + q) · (p + r) p · (q + r) = (p · q) + (p · r)
Propriedades do 0 p + 0 = p p · 0 = 0
Propriedades do 1 p + 1 = 1  p · 1 = p
Quaisquer que seja p em B, existe p’ em B tal que p + p’ = 1 p · p’ = 0

Indicamos uma Álgebra Booleana por [ B , + , · , ’ , 0 , 1 ].

Álgebra Booleana

Para descrever os circuitos que podem ser construídos pela combinação de portas lógicas, um novo tipo de álgebra é necessário, uma em que as variáveis e funções podem ter apenas valores 0 e 1. Tal álgebra é denominada álgebra booleana, devido ao seu descobridor, o matemático inglês George Boole (1815 - 1864).
Do mesmo modo que existem funções em álgebra "comum", também existem funções na álgebra booleana. Uma função booleana tem uma ou mais variáveis de entrada e fornece somente um resultado que depende apenas dos valores destas variáveis.
Como uma função de n variáveis possui apenas 2n conjuntos possíveis de valores de entrada, a função pode ser descrita completamente através de uma tabela de 2n linhas, cada linha mostrando o valor da função para uma combinação diferente dos valores de entrada. Tal tabela é denominada tabela verdade.

A B C 0 0 0 0 1 0 1 0 0 1 1 1
Acima temos a tabela verdade de uma função básica a função AND , ela e um conjunto de funções da álgebra booleana têm implementação eletrônica através de transistores e são conhecidas como portas lógicas.
Um circuito digital é regido pela álgebra de Boole, e com as portas lógicas existentes é possível implementar qualquer função da álgebra booleana. A seguir veremos as principais portas lógica, simbologia e tabela verdade.

-NOT

A função NOT é implementada na conhecida porta inversora.

A B 0 1 1 0 (a)

(b)

(a) tabela verdade, (b) símbolo


-AND

A função AND pode ser definida em linguagem natural como 1 se todas as entradas forem 1 e 0 se apenas uma das entradas for 0.

A B S 0 0 0 0 1 0 1 0 0 1 1 1

-OR

A função OR também pode ser definida em linguagem natural ela é 0 se todas as entradas forem 0 e 1 se existir uma entrada em 1.

A B C 0 0 0 0 1 1 1 0 1 1 1 1

-XOR

A função XOR conhecida como exclusive OR é muito parecido com a OR.

A B C 0 0 0 0 1 1 1 0 1 1 1 1 Temos acima algumas das principais portas lógicas existente, não são as únicas mas as outras portas existentes são combinações destas portas básicas, e todos os circuitos digitais podem ser montados somente com estas portas.




FUNÇÕES LÓGICAS – PORTAS LÓGICAS  

       Existe na matemática eletrônica digital um modelo de sistema lógico para cálculos e formações de sistemas digitais. Esse modelo matemático chama-se álgebra de Boole. Conjuntamente com esse modelo, temos as funções lógicas que vão dar formas estruturadas às expressões geradas pela álgebra de Boole.

      Nas funções lógicas, teremos apenas dois estados:

    • estado 0 (zero);
    • estado 1 (um).

    Esses estados são níveis de eventos opostos entre si, isto é, se o estado zero representa uma torneira fechada, o estado um representa a mesma aberta; se o estado zero representa uma luz apagada, o estado um representa uma luz acesa. 

Função E ou AND 

A função E é aquela que representa a multiplicação booleana de duas ou mais variáveis, e sua representação algébrica igual a S = A x B x ....N., que é o mesmo que S = A and B and  ... N , sendo S o resultado da expressão. Abaixo temos a tabela verdade dessa função e a direita temos o símbolo da porta AND com duas variáveis de entrada.

A                  B

S

 
 
                   S

            A                                        S

          

            B


0 
    1. 1
 
    1. 0
 
1                    1
0 

0 

0 

1

 
 
 
 

Função OU ou OR 

A função OU (OR) é aquela que representa a soma booleana de duas ou mais variáveis, e sua representação algébrica igual a S = A + B + .... N., sendo S o resultado da expressão, que é o mesmo que S = A ou B ou .... N. Abaixo temos a tabela verdade dessa função e a direita temos o símbolo da porta OU com duas variáveis de entrada. 

A                  B

S

 
 
           A 

                                                   S

            B

0                    0 
0                    1 

1                    0 

1                    1   

0 

1 

1 

1

 
 
 

Função NÃO ou NOT 

A função NÃO (NOT) é aquela que representa a inversão do estado de entrada da variável, isto é, se na entrada a variável é zero, na saída ficará um; se na entrada a variável é um, na saída ficará zero a S = Ā ou S = A’, sendo S o resultado da expressão. Abaixo temos a tabela verdade dessa função e a direita temos o símbolo da porta NOT. 

A

S

 
 
           A                                     S          

                                                 

           

0 
1 
1 

0 
 
 

 
 
 
 
 
 

Função NE ou NAND 

A função NE ou NAND é aquela que representa a negativa ou inversão da multiplicação booleana de duas ou mais variáveis, e sua representação algébrica igual a S = A x B x ....N., que é o mesmo que S = A nand B nand  ... N , sendo S o resultado da expressão. Abaixo temos a tabela verdade dessa função e a direita temos o símbolo da porta NAND com duas variáveis de entrada.

A                  B

S

 
 
                   S

            A                                       

                                                       S

            B

0                   0 
0                   1 

1                   0 

1                    1

1 

1 

1 

0

 
 
 

Função NOU ou NOR 

A função NOU (NOR) é aquela que representa a negativa ou inversão da soma booleana de duas ou mais variáveis, e sua representação algébrica igual a S = A + B + .... N., sendo S o resultado da expressão, que é o mesmo que S = A ou B ou .... N. Abaixo temos a tabela verdade dessa função e a direita temos o símbolo da porta NOR com duas variáveis de entrada. 

A                  B

S

 
 
           A 

                                                   S

            B

0                    0 
0                    1 

1                    0 

1                    1   

1 

0 

0 

0

 
 
 
 
 
 

BLOCOS LÓGICOS BÁSICOS

PORTA

SÍMBOLO

TABELA

VERDADE

FUNÇÃO

LÓGICA

E 

AND

  A          B S Função E: Assume valor 1 quando todas as variáveis forem iguais a 1, e valor zero nos outros casos possíveis.
0           0

0           1

1           0

1           1

0

0

0

1

OU 

OR

  A         B S Função OU: Assume valor 0 quando todas as variáveis forem iguais a 0, e valor um nos outros casos possíveis.
0           0

0           1

1           0

1           1

0

1

1

1

NE 

NAND

  A         B S  
Inverso da Função E (AND)
0           0

0           1

1           0

1           1

1

1

1

0

NOU 

NOR

  A         B S  
Inverso da Função OU (OR)
0           0

0           1

1           0

1           1

1

0

0

0

 

NÃO

NOT

INVERSOR

 

A

Ā Função NÃO: Inverte a variável aplicada a sua entrada
           0

           1

1

0

 
 
 
  1. CIRCUITOS LÓGICOS, EXPRESSÕES BOOLEANAS E TABELA VERDADE
 

    Através de um ou mais circuitos lógicos associados entre si teremos uma expressão booleana equivalente. O objetivo será exatamente formar um complexo eletrônico no qual busca-se uma solução digital para um ou mais eventos eventos binário na entrada, através de variáveis. 

4.1  – Expressões booleanas geradas por circuitos interligados 

Exemplificando, temos o seguinte circuito 1):

 

A

                                S1                                         S   

B

 

C 
 

Qual seria a expressão booleana? 

    • Temos S1 = A x B
    • Temos S = S1 + C
    • Logo, substituindo S1 , teremos S = A x B + C
 

Circuito 2) 

A 

B 
 

C 

D 

S =  (A+B) x (C+D) 
 
 
 

Circuito 3) 

A 

B 
 

C 
 

D 
 

S = (AxB) + C’ + (CxD)’ 
 

Circuito 4) 

A 

B 
 

C 
 
 
 

D 

S = { [ (A’ x  B) x (B x C)’ x (B + D)’ ]’ } 
 
 
  Circuitos obtidos de expressões booleanas:


     Neste caso teremos uma expressão booleana e formaremos o diagrama do circuito equivalente: 

Expressão 1)     S = (A+B) x C x (B+D) 

A 
 

B 
 

C 
 
 

D 
 
 
 

Expressão 2)     S = A x B + (A+B) x C’

A 

B 
 
 
 

C 
 

Expressão 3)  S = [ (A x B)’ + (C X D)’ + D] 

A 
 

B 
 

C 
 

D 

Expressão 4)  ALUNO FAZER     

  S = { [(A’ + B)’ + (C’ x D)’]’   x  E  + [ (A  x D’ x E’) + (C x D x E)] x A’ } 
 
 
  Tabela verdade obtida de expressões booleanas: 

Para obtermos a tabela verdade, isto é,  qual a saída S para todas as combinações nas entradas pelas variáveis, fazemos da seguinte forma: 

  1. Montamos o quadro de combinações das variáveis de entrada;
  2. Montamos as colunas com os agrupamentos da equação, podendo ter colunas auxiliares,  e uma coluna para o resultado final;
  3. Preenchemos essas colunas independentemente com resultados obtidos das variáveis;
  4. Preenche-se a coluna do resultado final obedecendo os operandos dos agrupamentos da expressão.
 

Exemplo 1)  S = A’ +  AB  + AB’C    (Obs.: Quando coloca-se as variáveis juntas, como AB, é o mesmo que A x B) : 

A   B   C 1o Membro

A’

2o Membro

AB

Auxiliar

B’

3o Membro

AB’C

Resultado

S

0    0     0

0    0     1

0    1     0

0    1     1

1    0     0

1    0     1

1    1     0

1    1     1

1

1

1

1

0

0

0

0

0

0

0

0

0

0

1

1

1

1

0

0

1

1

0

0

0

0

0

0

0

1

0

0

1

1

1

1

0

1

1

1

 
 

Exemplo 2)   S  =  A’B  + BC    

A   B   C

Auxiliar

             A’

1o Membro

A’B

2o Membro

BC

Resultado

          S

0    0     0

0    0     1

0    1     0

0    1     1

1    0     0

1    0     1

1    1     0

1    1     1

1

1

1

1

0

0

0

0

0

0

1

1

0

0

0

0

0

0

0

1

0

0

0

1

0

0

1

1

0

0

0

1

 
 
 Tabela verdade obtida de circuitos: 

 

Basta em primeiro lugar achar a expressão booleana do circuito para depois montar a tabela verdade




Álgebra Booleana 


Variáveis só podem assumir 1 entre 2 valores
Uso de tabelas (tabela verdade) para listar combinações de valores de entrada e os correspondentes valores de saída 
 
 
 

Álgebra Booleana 


Proposição – todo enunciado que pode se afirmar ser verdadeiro ou falso.
  • Exemplo

    • Amanhã vai chover – não constitui uma proposição, pois existe mais de duas respostas possíveis: Sim, Talvez e Não
    • Lisboa é a capital de Portugal é uma proposição
 
 
 
 

Princípios da Álgebra Booleana 


  • Não contradição: uma proposição não pode ser simultaneamente verdadeira e falsa
 
  • Terceiro excluído: uma proposição só pode tomar um dos dois valores possíveis, ou é verdadeira ou falsa, não sendo possível terceira hipótese.
 
 
 
 

Álgebra Booleana 

  • Operações Básicas

    • OU (OR) - Adição Lógica  F = X + Y
 
 

X     Y      

0      0

0      1 

1      0 

1      1       

F 

0

1

1

1 

 
 
 
 

Álgebra Booleana 

Operações Básicas


    • E (AND) - Multiplicação Lógica F = X . Y
 

X     Y      

0      0

0      1 

1      0 

1      1       

F 

0

0

0

1

Álgebra Booleana 

Operações Básicas


    • Não (NOT) - Complemento (Negação) F = X´ ou F = X
 

X 

0

1          

F 

1

0 

 
 
 
 

Tabela Verdade 

  • Cada entrada = 1 coluna
  • Cada saída     = 1 coluna
  • As possíveis Combinações entradas podem assumir: N = 2n, onde n = quantidade de variáveis de entrada e N as combinações entre zeros (0) e uns (1).
 
 Tabela Verdade 

S = A + B . C 

A     B     C

0      0      0

0      0      1

0      1      0

0      1      1

1      0      0

1      0      1

1      1      0

1      1      1 

S

0

0

1

0

1

1

1

1

Portas Lógicas 

Porta AND (Função Multiplicação Lógica (E)) 

F 

A 

B 

F = A . B

 
 
 
 

Portas Lógicas 

  • Portas lógicas são dispositivos ou circuitos lógicos que operam um ou mais sinais lógicos de entrada para produzir uma e somente uma saída, a qual é dependente da função implementada no circuito.
 
 
 
 

Portas Lógicas 

  • Um computador é constituído por uma infinidade de circuitos lógicos, que executam as seguintes funções básicas:
 
a.realizam operações matemáticas

b.controlam o fluxo dos sinais

c.armazenam dados  
 
 
 

Portas Lógicas 

  • Naturalmente, a cada operação lógica estudada na Álgebra de Boole está associada a respectiva porta lógica.
 
 
 
 

Portas Lógicas 

Porta OR (Função Adição Lógica (OU)) 

F 

A 
 

B 

F = A + B

 
 
 
 

Portas Lógicas 

Porta NOT (Função Negação Lógica (Complemento)) 

F = A

 
 
 
 

Circuitos Lógicos 

  • Representação
    • Produto de Somas
      • lista todas as combinações das variáveis de entrada para as quais a função de saída vale 0

    • Soma de Produtos
      • lista todas as combinações das variáveis de entrada para as quais a função de saída vale 1
 

Definição de uma função booleana através de uma tabela-verdade 

Expressão algébrica da função

 
 
 
 

Soma de Produtos 

Mintermo = termo-produto no qual cada variável aparece exatamente 1 vez,   complementada (se bit da tabela = 0) ou não (se bit da tabela = 1) 

X     Y      Z

0      0      0

0      0      1

0      1      0

0      1      1

1      0      0

1      0      1

1      1      0

1      1      1 

Termo-produto

    X   Y   Z

    X   Y   Z

    X   Y   Z

    X   Y   Z

    X   Y   Z

    X   Y   Z

    X   Y   Z

    X   Y   Z  

mintermo

      m0

      m1

      m2

      m3

      m4

      m5

      m6

      m7

 
 
 
 

Produto de Somas 

  Maxtermo =  termo-soma no qual cada variável aparece exatamente 1 vez,

    complementada (se bit da tabela = 1)  ou não (se bit da tabela = 0) 

X     Y      Z

0      0      0

0      0      1

0      1      0

0      1      1

1      0      0

1      0      1

1      1      0

1      1      1 

Termo-soma

X + Y + Z

X + Y + Z

X + Y + Z

X + Y + Z

X + Y + Z

X + Y + Z

X + Y + Z 
X + Y + Z

 

maxtermo

      M0

      M1

      M2

      M3

      M4

      M5

      M6

      M7

 
 
 
 

Notações 

X     Y      Z

0      0      0

0      0      1

0      1      0

0      1      1

1      0      0

1      0      1

1      1      0

1      1      1 

F

1

0

1

0

0

1

0

1 

F = XYZ + XYZ + XYZ + XYZ = m0 + m2 + m5 + m7 = m (0,2,5,7) 

Soma de Produtos 

Produto de Somas  

F = (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) = M1 . M3 . M4 . M6 = M(1,3,4,6) 

 
 
 
 

Simplificação de Expressões Booleanas 

  • Usada para economizar componentes, tornar o circuito mais rápido, mais simples de fabricar e de manutenção, além de diminuir seu tamanho.

  • Tipos:

    • Postulados da Álgebra Booleana 
    • Mapas de Karnaugh
 
 
 
 

Postulados da Álgebra Booleana 


  • Identidades Booleanas

     A + 0 = A  1 A . 0 = 0  5  A = A  9

    A + 1 = 1   A . 1 = A  6   

    A + A = 1  3 A . A = 0  7

    A + A = A  4  A . A = A  8 


  • Propriedade Comutativa
 

    A + B = B + A 10  A . B = B . A 11

 
 
 
 

Postulados da Álgebra Booleana 

  • Propriedade Associativa

    (A + B) + C = A + (B + C) 12 (A. B) . C = (B. C) . A 13


  • Propriedade Distributiva 

    A . (B + C) = A . B + A . C 14


  • Consenso
   A . B + A’ . C + B . C = A . B + A’ . C 15

   (A+B) . (A’+C) . (B+C) = (A+B) . (A’+C) 16


  • Teorema de De Morgan

    A . B... = A + B + ...  A + B + ... = A . B ... 17

 
 
 
 

Expressões Auxiliares 


( A + B ) . ( A + B’ ) = A 

22 

( A . B ) + ( A . B’ ) = A 

21 

( A + B’ ) . B = A . B 

20 

A + ( A’ . B ) = A + B 

19 

A + ( A . B ) = A 

18

 
 
 
 

Simplificação pelos Postulados da Álgebra Booleana 

Pela prop. (6),  

Pela prop. (4),   

Pela prop. (14),   

Soma de Produtos

simplificada

 
 
 
 

Simplificação pelos Postulados da Álgebra Booleana 




O termo poderia ter sido simplificado com o termo


Utilizando a propriedade (3), que permite a seguinte manipulação:

 

 
 
 
 

Simplificação pelos Postulados da Álgebra Booleana 

Soma de Produtos simplificada (mínima, no caso) 

Pela prop. (3),   

Pela prop. (14)   

Pela prop. (4)   

Pela prop. (6)

 
 
 
 

Circuito Lógico 

Complexidade:

4x3 + 1x4 = 16 

Soma de mintermos 

Circuito com (lógica de ) 2 níveis

 
 
 
 

Circuito Lógico Expressão Simplificada 

Complexidade:

2x2 + 2X3 = 10 

Soma de produtos

(simplificada) 

Circuito com (lógica de ) 2 níveis

 
 
 
 

Simplificação por Mapa de Karnaugh 

  • Cada célula corresponde a um mintermo
  • Representa a função como soma de produtos
  • Para 2 variáveis
 

Y 

XY

m0 

XY

m2 

XY

m3 

XY

m1 

X 

0          1 

0

 

1 

  • Exemplo:
 

F = m(1,2,3) = XY + XY + XY 

0 

Y 

X 

0         1 

0

 

1 

1 

1 

1 

Y

 
 
 
 

Simplificação por Mapa de Karnaugh 

  • Simplificação algébrica é de difícil automatização
  • Simplificação por mapa fornece uma maneira “visual” para a simplificação
  • Baseia-se na identificação de produtos vizinhos
 
 
 
 

Simplificação por Mapa de Karnaugh 

m0 

m2 

m3 

m1 

Y 

X 

0        1 

0

 

1 

região onde X = 1 

região onde Y = 1 

Junta-se 2n posições

      20 = 1  23 = 8

      21 = 2

      22 = 4

 
 
 
 

Simplificação por Mapa de Karnaugh 

  • Mapa com 3 variáveis
 

Concatenar bit da linha com bits da

coluna para identificar mintermo 

m0 

m1 

m3 

m6 

m2 

m4 

m5 

m7 

00        01        11        10 

0

1 

YZ 

X 

  • Mintermos não seguem a ordem crescente útil para simplificação
  • 2 células vizinhas (adjacentes): mintermos diferem por uma variável
 

m5        e      m7 

XYZ 

XYZ 

única diferença é Y

 
 
 
 

Simplificação por Mapa de Karnaugh 


  • Atenção para a vizinhança entre bordas
  • Região com 2 células adjacentes termo com 2 literais...
 
 
 

m0 

m4 

m6 

m2 

m0 

m1 

m3 

m6 

m2 

m4 

m5 

m7 

00        01        11        10 

0

1 

YZ 

X

 
 
 
 

Simplificação por Mapa de Karnaugh 

F = m(2,3,4,5) 

  • Exemplo de simplificação
 

0 

0 

1 

0 

1 

1 

1 

0 

00         01      11       10 

0 

1 

YZ 

X 

F = XY + XY 

0 

0 

1 

1 

0 

1 

0 

1 

00        01       11      10 

0 

1 

YZ 

X 

F = m(3,4,6,7) 

F = YZ + XZ

 
 
 
 

Simplificação por Mapa de Karnaugh 

  • Mapa com 4 variáveis
 

m0 

m1 

m3 

m2 

m6 

m11 

m15 

m7 

m9 

m13 

m5 

m8 

m12 

m4 

m14 

m10 

00      01       11        10 

00 

01 

11 

10 

YZ 

WX 

  • Notar adjacências através das bordas
 

m0 

m1 

m9 

m8 

m4 

m6 

m2 

m0

 
 
 
 

Simplificação por Mapa de Karnaugh 

  • Exemplo de simplificação
 

1 

1 

1 

1 

1 

1 

1 

1 

1 

1 

  00         01           11           10 

00 

01 

11 

10 

YZ 

WX 

1 

WZ 

XZ 

F = Y + WZ + XZ 

célula isolada 

região com 2 células 

região com 4 células 

região com 8 células 

termo com 4 literais 

termo com 3 literais 

termo com 2 literais 

termo com 1  literal 

Y

Simplificação por Mapa de Karnaugh 



  • Mapas com mais de 4 variáveis tornam-se difíceis de manipular

Don´t Cares 

  • Saída :não importa o valor da saída gerado por determinada combinação de entradas
  • Entrada: é indiferente o valor da entrada para determinar um valor na saída
 
 
 
 



1 

X 

X 

X 

X 

X 

X 

1 

1 

1 

00      01      11      10   

00  

01 

11 

10 

CD 

AB 

  • X pode ser 0 ou 1 => o que for mais conveniente para simplificar a função
 

F = CD + CD
















Comments