algebra booleana

Álgebra booleana
Teoremas e propriedades
Teoremas de De Morgan
!(X + Y) = !X . !Y
!(X . Y) = !X + !Y

Exemplo
F
F
F
F

=
=
=
=

!( (!A + C).(B + !D) )
!(!A + C) + !(B + !D)
!!A.!C + !B.!!D
A.!C + !B.D

(De Morgan)
(De Morgan)
(Complementação)

Pode ser estendido para mais de duas variáveis
!(X + Y + Z) = !X . !Y . !Z
!(X . Y . Z) = !X + !Y + !Z

123

Álgebra booleana
Teoremas e propriedades
Exemplo
F
F
F
F
F
F
F
F

=
=
=
=
=
=
=
=

!(A + B).(!A + !B)
(!A.!B).(!A + !B)
(!A.!B).!A + (!A.!B).!B
!A.(!A.!B) + !B.(!A.!B)
!A.!A.!B + !B.!A.!B
!A.!A.!B + !B.!B.!A
!A.!B + !A.!B
!A.!B

(Versão 1)
(De Morgan)
(Distributividade)
(Comutatividade)
(Associatividade)
(Comutatividade)
(AND: X.X = X)
(OR: X + X = X)

124

Álgebra booleana
Teoremas e propriedades
OR
X+
X+
X+
X+

0=X
1=1
X=X
!X = 1

AND
X.0=0
X.1=X
X.X=X
X . !X = 0

!!X = X
X+Y=Y+X
X.Y=Y.X
X + (Y + Z) = (X + Y) + Z = X + Y + Z
X.(Y.Z) = (X.Y).Z = X.Y.Z
X.(Y + Z) = X.Y + X.Z
X + Y.Z = (X + Y) . (X + Z)
X + X.Y = X
!(X + Y) = !X . !Y
!(X . Y) = !X + !Y

(Complementação)
(Comutatividade)
(Comutatividade)
(Associatividade)
(Associatividade)
(Distributividade)
(Distributividade)
(Absorção)
(De Morgan)
(De Morgan)
125

Álgebra booleana
Teoremas e propriedades
Exercício
F
F
F
F
F
F

=
=
=
=
=
=

!( !(A + B).!(!C+ B) )
!!(A + B) + !!(!C + B)
(A + B) + (!C + B)
A + B + !C + B
A + B + B + !C
A + B + !C

(De Morgan)
(Complementação)
(Comutatividade)
(Comutatividade)
(OR: X + X = X)

126

Álgebra booleana
Teoremas e propriedades
Exercício
F
F
F
F
F
F
F
F
F
F
F

=
=
=
=
=
=
=
=
=
=
=

A.B.!(!A + B.C)
A.B.(!!A.!(B.C))
A.B.(A.!(B.C))
A.B.(A.(!B + !C))
A.B.(A.!B + A.!C)
A.B.A.!B + A.B.A.!C
A.A.B.!B + A.A.B.!C
A.B.!B + A.B.!C
A.0 + A.B.!C
0 + A.B.!C
A.B.!C

(De Morgan)
(Complementação)
(De Morgan)
(Distributividade)
(Distributividade)