Algebra de boole

Disponível somente no TrabalhosFeitos
  • Páginas : 14 (3290 palavras )
  • Download(s) : 0
  • Publicado : 24 de julho de 2012
Ler documento completo
Amostra do texto
Prof. Eric Fagotto

texto não revisado, pode conter erros fev./1998 - V. 1.0

Álgebra de Boole O postulado básico da álgebra de Boole é a existência de uma variável boolena tal que: x≠0 ⇔ x=1 x≠1 ⇔ x=0 A álgebra de Boole é um sistema algébrico que consiste do conjunto {0,1}, duas operações binárias chamadas OR (operador: +) e AND (.) e uma operação unária NOT ( ). A operação OR é chamada de somalógica ou união, a operação AND é conhecida por produto lógico ou interseção e a operação NOT é dita complementação ou ainda inversão (não confundir com a soma de números binários). Estas operações são definidas conforme as tabelas a seguir: Operação OR 0+0=0 0+1=1 1+0=1 1+1=1 AND 0⋅0=0 0 ⋅1 = 0 1⋅0=0 1⋅1=1 NOT 0 =1 1= 0

Estas operações podem ser representadas por circuitos lógicos elementaresdenominados portas ou gates:

OR

AND

NOT

(Atenção! Ler "+” como “ou” e “.” como “AND”, ressaltando a diferença com a aritmética binária) Um circuito de composto de gates é chamado de circuito lógico. O circuito mostrado abaixo realiza a expressão lógica A . B + C + D . E

A B C D E

AB

AB+C

AB+C + DE

DE

1

Prof. Eric Fagotto

texto não revisado, pode conter erros fev./1998 - V. 1.0Acrescentar a simbologia para as negações de OR e de AND! Circuito Ou-Exclusivo (X-OR) A tabela verdade para a função que o X-OR executa é: A B 0 0 0 1 1 0 1 1 S 0 1 1 0

Uma expressão booleana para esta função seria (ela não é única!) S = AB + AB . Peça aos alunos para montar o circuito. Utiliza-se o seguinte operador para denotar a operação de X-OR: ⊕. Logo, para a tabela anterior S =A⊕B
A B SComplementando o X-OR obtemos o circuito que é conhecido como coincidência, nome que vem do fato de sua saída ser somente igual a “1” quando existir coincidência nas suas entradas, i.e.: A B S 0 0 1 0 1 0 1 0 0 1 1 1 Símbolo: acrescentar um inversor à saída do X-OR Operador: , operação: S=A B. Propriedades Básicas Sendo x uma variável booleana, então: • x+1=1 • x .0=0 • x+0=x • x.1=x • x+x=x • x.x=x

Aálgebra booleana é comutativa e associativa com relação às duas operações binárias. Sendo x, y, z variáveis booleanas, então

2

Prof. Eric Fagotto

texto não revisado, pode conter erros fev./1998 - V. 1.0

Comutativa

x + y = y+ x x . y= y. x

Associativa

( x + y) + z = x + ( y + z ) ( x . y) . z = x . ( y . x )
x + x =1 x. x=0

Complemento

Na álgebra booleana, a soma é distributiva sobre oproduto e o produto é distributivo sobre a soma,
Distributiva x + ( y . z ) = ( x + y) . ( x + z ) x . ( y + z) = x . y + x . z

Notemos que estas propriedades apresentam-se aos pares e que em cada par, uma equação pode ser obtida da outra mediante a troca de 1 por 0 e 0 por 1 além de permutarmos os AND’s pelos OR’s . Isto é conhecido como princípio da dualidade da álgebra de Boole (obs: todas estasexpressões podem ser provadas por indução finita, bastando provar uma equação e a sua dual estará provada). Expressões Booleanas Define-se expressão booleana como a combinação de um número finito de variáveis booleanas (0,1) através das operações booleanas (+), (.) e ( ). Qualquer constante ou variável booleana é uma expressão booleana, e se T1 e T2 são expressões booleanas, o mesmo acontecerá paraT1, T 2 , T1+T2, T1.T2 . As propriedades a seguir formam o conjunto fundamental de ferramentas básicas para a simplificação de expressões booleanas.
x ( x+y ) = x x+xy = x + y x x+y = xy
xy+xz+yz=xy+xz

x+xy=x

propriedades de absorção

(

)

propriedades de consenso

( x+y ) ( x+z ) ( y+z ) = ( x+y ) ( x+z )

3

Prof. Eric Fagotto

texto não revisado, pode conter erros fev./1998 - V. 1.0

Ex1:Simplifique a expressão F(x,y,z) = x y z + yz + xz
= z( x y + y + x) = z( x + y + x)

= z( y + 1) = z.1 = z

Ou seja, F(x,y,z) independe dos valores de x e y, i.e., F(x,y,z) é F(x)! É muito importante notar que na álgebra de Boole não são definidas operações inversas e portanto, não são permitidos cancelamentos. Por exemplo, se A+B=A+C, não significa que B=C. De fato, se A=B=1 e C=0 1+1=1+0,...
tracking img