BCC101
Matemática Discreta I
Lógica Proposicional
Álgebra de Boole
1
Algumas Equações da Álgebra Numérica
a+0=a
(-a) + a = 0
a1=a
a0=0
a+b=b+a
a + (b+c) = (a+b) + c
a(b+c) = ab + ac
{+ identidade}
{+ complemento}
{ identidade}
{ zero}
{+ comutatividade}
{+ associatividade}
{distributividade}
Equações valem nos dois sentidos
2
Negativo

Negativo = Positivo
equações básicas
(axiomas)
(-1)  (-1) = 1
(-1)  (-1)
= ((-1)  (-1)) + 0
{+ id}
= ((-1)  (-1)) + ((-1) + 1)
{+ comp}
= (((-1)(-1)) + (-1)) + 1
{+ assoc}
= (((-1)(-1)) + (-1)1) + 1
{ id}
… and+ then
= ((-1)((-1)
1)) + x
1 miracle happened
{dist} …
= ((-1)0) + 1
{+ comp}
=0+1
= 1{ zero}
=1+0
{+ comm}
=1
{+ id}
x+0=x
(-x) + x = 0
x1=x
x0=0
x+y=y+x
x + (y+z) = (x+y) + z
x(y+z) = (xy) + (xz)
{+ id}
{+ comp}
{ id}
{ zero}
{+ comm}
{+ assoc}
{dist }
3
Equações Básicas da Álgebra Booleana
x  False = x
x  True = True
xy=yx
(x  y)  z = x  (y  z)
x  (y  z) = (x  y)  (x  z)
(x  y) = ( x)  ( y)
xx=x
x  x = True
( x) = x
x  y = ( x)  y
x ⟷ y = (x  y)  (y x)
{ identiddade}
{ zero}
{ comutatividade}
{ associatividade}
{ distributividade}
{ deMorgan}
{ idempotência}
{auto-implicação}
{dupla negação}
{implicação}
{bi-implicação}
4
Equação do Contrapositivo
um teorema derivado dos axiomas
p  q = (q)  (p)
equações
regra]
pq
= (p)  q
= (p)  ((q))
= ((q))  (p)
= (q)  (p)
{regra} substituição [formula na eq / variável na
{implic} [p /x] [q /y]
{dupla neg} [q /x]
{ comut} [p /x] [((q)) /y]
{implic} [q /x] [p /y]
5
Tabela-verdade da Negação
x
x
False
True
True
False
outro teorema
False = True provado
True = False provado
equações
x  False = x
x  True = True
xy=yx
(x  y)  z = x  (y  z)
x  (y  z) = (x  y)  (x  z)
x  y = ( x)  y
(x  y) = ( x)  ( y)
xx=x
x  x = True
( x) = x
{ identidade}
{ zero}
{ comutatidade}
{ associatidade}
{ distributidade}
{impliçação}
{ deMorgan}
{ idempotência}
{auto-implicação}
{dupla negação}
{regra} substituição
False
= (False)  False
= False  False
= True
{ id} [False /x]
{imp} [False /x] [False /y]
{auto-imp} [False /x]
True
= (False)
= False
{tabela verdade} [True/True]
{dupla negação} [True/x]
6
 Zero
outro teorema
p  False = False
equações
p  False
= p  ((False))
= ((p))  ((False))
= ((p)  (False))
= ((p)  True)
= True
= False
x  False = x
x  True = True
xy=yx
(x  y)  z = x  (y  z)
x  (y  z) = (x  y)  (x  z)
x  y = ( x)  y
(x  y) = ( x)  ( y)
xx=x
x  x = True
( x) = x
{ identidade}
{ zerro}
{ comutatividade}
{ associatividade}
{ distributividade}
{implicação}
{ deMorgan}
{ idempotência}
{auto-implicação}
{dupla negação}
{regra} substituição
{dupla neg} [False /x]
{dupla neg} [p /x]
{deMorgan} [p /x] [False /y]
{ tabela} …citando um teorema…
{ zero}[p /x]
{ tabela} …citando um teorema…
7
Absorção
outro teorema
(p  q)  q = q
x  False = x
x  True = True
xy=yx
(x  y)  z = x  (y  z)
x  (y  z) = (x  y)  (x  z)
x  y = ( x)  y
(x  y) = ( x)  ( y)
xx=x
x  x = True
( x) = x
{ identidade}
{ null}
{ comutatividade}
{ associatividade}
{ distributividade}
{implicação}
{ deMorgan}
{ idempotência}
{auto-implicação}
{dupla negação}
equações
{regra} substituição
(p  q)  q
= (p  q)  (q  False)
= (q  p)  (q  False)
= q  (p  False)
= q  False
=q
{ id} [q /x]
{ comut} [p /x] [q /y]
{ distrib} [q /x] [p /y] [False /z]
{ zero} [p /x] …citando um teorema…
{ id} [q/x]
QED
8
Tabela Verdade de
False  False = True
True  True = True
False  True = True
True  False = False
False  False
= True

x  False = x
x  True = True
xy=yx
(x  y)  z = x  (y  z)
x  (y  z) = (x  y)  (x  z)
x  y = ( x)  y
(x  y) = ( x)  ( y)
xx=x
x  x = True
( x) = x
{ identidade}
{ null}
{ comutatividade}
{ associatividade}
{ distributividade}
{implicação}
{ deMorgan}
{ idempotência}
{auto-implicação}
{dupla negação}
{auto-imp} [False /x]
False  True
= (False)  True
= True
{imp} [False /x, True /y]
{ zero} [False /x]
True  False
= (True)  False
= True
= False
{imp} [False /x , True /y]
{ id} [True /x]
{ tabela}
True  True = True
{exercício}
9
Álgebra Booleana – equações derivadas
x  True = x
x  False = False
xy=yx
(x  y)  z = x  (y  z)
x  (y  z) = (x  y)  (x  z)
(x  y) = ( x)  ( y)
xx=x
{ identiddade}
{ zero}
{ comutatividade}
{ associatividade}
{ distributividade}
{ deMorgan}
{ idempotência}
10
Álgebra Booleana – equações derivadas
(a =b) = (b = a)
{= comut}}
((a = b) = c) = (a = (b = c)) {= assoc}
true = a = a
{true}
¬a = a = false
{false}
p ∨ (q = r) = p ∨ q = p ∨ r
{distributividade}
a∧b=a=b=a∨b
a⇒b=b=a∨b
{definição do ∧}
{definição do ⇒}
11