Algebra booleana - portas logicas3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Álgebra booleana
Teoremas e propriedades
Propriedades da operação OR
X + 0 = X
X + 1 = 1
X + X = X
X + !X = 1
Exemplo: F = A.(B + B)
↔ F = A.B
Álgebra booleana
Teoremas e propriedades
Propriedades da operação AND
X . 0 = 0
X . 1 = X
X . X = X
X . !X = 0
Exemplo: F = A + (B.!B) 
↔ F = A + 0 
↔ F = A 
Álgebra booleana
Teoremas e propriedades
X (nas propriedades) pode representar uma variável ou uma expressão
Exemplo 1: X representando a variável B
F = A + (B.!B) ↔ F = A + 0 ↔ F = A
Exemplo 2: X representando expressão C.D
F = A.B + (C.D) . !(C.D) ↔ F = A.B + 0 ↔ F = A.B
↔
X
X
C e D não influenciam no valor de F
Álgebra booleana
Teoremas e propriedades
Complementação (óbvia)
!!X = X
Comutatividade (ordem das variáveis não altera o resultado)
X + Y = Y + X (“a ordem das parcelas não altera a soma”)
X . Y = Y . X (“a ordem dos fatores não altera o produto”)
X
!X
!!X = X
↔
↔
Álgebra booleana
Teoremas e propriedades
Associatividade (ordem de avaliação não altera o resultado)
X + (Y + Z) = (X + Y) + Z = X + Y + Z
X.(Y.Z) = (X.Y).Z = X.Y.Z
↔
↔
↔
↔
Álgebra booleana
Teoremas e propriedades
Distributividade (expansão/fatoração)
Uma das mais utilizadas na simplificação de equações booleanas
X.(Y + Z) = X.Y + X.Z		(operação AND distribuída)
X + Y.Z = (X + Y) . (X + Z)	(operação OR distribuída)
Exemplo 1
F = A.B.C + A.B.D
F = A.B.(C + D)	 (distributividade) 
Exemplo 2
F = A.B.C + !A.B.!C
F = B.A.C + B.!A.!C	(comutatividade)
F = B.(A.C + !A.!C) 	(distributividade)
Expansão
Fatoração (colocar termo em evdência)
Álgebra booleana
Teoremas e propriedades
Absorção
X + X.Y = X (Cuidado! Não é trivial)
Exemplo: X = 1
1 + 1.Y = 1
Exemplo: X = 0
0 + 0.Y = 0
S depende só de A
S = A + A.B
Álgebra booleana
Teoremas e propriedades
Absorção
X + X.Y = X (Cuidado! Não é trivial)
Prova algébrica
F = X + X.Y
F = X.1 + X.Y	(propriedade do AND: X.1 = X)
F = X.(1 + Y)	(distributividade)
F = X.(1)		(propriedade do OR: X + 1 = 1)
F = X		(propriedade do AND: X.1 = X)
Álgebra booleana
Teoremas e propriedades
Exemplos
F = A.B.C + A.B.!C	(versão 1)
F = A.(B.C + B.!C) 	(distributividade)
F = A.(B.(C + !C))	(distributividade)
F = A.(B.(1)) 		(propriedade do OR: X + !X = 1)
F = A.B		(propriedade do AND: X.1=X)		
C não influencia no valor de F
Álgebra booleana
Teoremas e propriedades
Exemplos
F = A.B.C + A.B.!C	(versão 2)
F = A.B.(C + !C)	(distributividade)
F = A.B.(1)		(propriedade do OR: X + !X = X)
F = A.B		(propriedade do AND: X.1=X)
C não influencia no valor de F
Álgebra booleana
Teoremas e propriedades
Exemplos
F = H.!C + !H.P.!C
F = !C.H + !C.!H.P		(comutatividade)
F = !C.(H + !H.P)		(distributividade)
F = !C.( (H + !H) . (H + P) ) 	(distributividade)
F = !C.( (1) . (H + P) )		(propriedade do OR: X + !X = 1)
F = !C.(H + P) 		(propriedade do AND: X.1 = X)
Álgebra booleana
Teoremas e propriedades
Exemplos
F = (!A + B).(A + B)		(versão 1)
F = A.(!A + B) + B.(!A + B)	(distributividade)
F = A.!A + A.B + B.!A + B	(distributividade)
F = 0 + A.B + B.!A + B	(propriedade do AND: X.!X = 0)
F = A.B + B.!A + B		(propriedade do OR: X + 0 = X)
F = B + A.B + !A.B		(comutatividade)
F = B.1 + A.B + !A.B		(propriedade do AND: X.1 = X)
F = B.(1 + A) + !A.B		(distributividade)
F = B.(1) + !A.B		(propriedade do OR: X + 1 = 1)
F = B + !A.B			(propriedade do AND: X.1 = 1)
F = B.1 + !A.B		(propriedade do AND: X.1 = 1)
F = B.(1 + !A)		(distributividade)
F = B.(1)			(propriedade do OR: X + 1 = 1)
F = B			(propriedade do AND: X.1 = 1)
Álgebra booleana
Teoremas e propriedades
Exemplos
F = (!A + B).(A + B)		(versão 2)
F = A.(!A + B) + B.(!A + B)	(distributividade)
F = A.!A + A.B + B.!A + B	(distributividade)
F = 0 + A.B + B.!A + B	(propriedade do AND: X.!X = 0)
F = A.B + B.!A + B		(propriedade do OR: X + 0 = X)
F = B + A.B + !A.B		(comutatividade)
F = B.1 + A.B + !A.B		(propriedade do AND: X.1 = X)
F = B.(1 + A + !A)		(distributividade)
F = B.(1)			(propriedade do OR: X + 1 = 1)
F = B			(propriedade do AND: X.1 = 1)
Álgebra booleana
Teoremas e propriedades
Exemplos
F = (!A + B).(A + B)		(versão 3)
F = A.(!A + B) + B.(!A + B)	(distributividade)
F = A.!A + A.B + B.!A + B	(distributividade)
F = 0 + A.B + B.!A + B	(propriedade do AND: X.!X = 0)
F = A.B + B.!A + B		(propriedade do OR: X + 0 = X)
F = B + A.B + !A.B		(comutatividade)
F = B + !A.B			(absorção: X + X.Y = X)
F = B			(absorção: X + X.Y = X)
Álgebra booleana
Teoremas e propriedades
OR			AND
X + 0 = X		X . 0 = 0
X + 1 = 1		X . 1 = X
X + X = X		X . X = X
X + !X = 1		X . !X = 0
!!X = X					(Complementação)
X + Y = Y + X				(Comutatividade)
X . Y = Y . X	 			(Comutatividade)
X + (Y + Z) = (X + Y) + Z = X + Y + Z	(Associatividade)
X.(Y.Z) = (X.Y).Z = X.Y.Z			(Associatividade)
X.(Y + Z) = X.Y + X.Z			(Distributividade)
X + Y.Z = (X + Y) . (X + Z)		(Distributividade)
X + X.Y = X				(Absorção)