BCC101
Matemática Discreta I
Lógica Proposicional
Dedução
1
Implicação e Dedução
Tabela-verdade de 
False  False = True False  True = True
True  True = True
True  False = False
 Raciocínio Dedutivo: das hipóteses para a conclusão
 Hipótese 1: x = True, Hipótese 2: x  y = True
 Conclusão: y = True
 Porque? Bem … suponha y = False {suposição}
 Então poderíamos provar que False = True, pelo seguinte argumento
False
= True  False
{ tabela-verdade}
= x  False
{hipótese 1}
=xy
{suposição}
= True
{hipótese 2}
 Não podemos aceitar a equação True = False
 Portanto, devemos aceitar que y = True se x  y = True e x = True
 Implicação possibilita dedução
 Deduzimos y = True de x = True e x  y = True
 Esta "regra de inferência” é chamada "modus ponens”
 Tautologia: ((x  (x  y))  y) = True
2
Regras de Inferência
e tautologias correspondentes
Regras de Eliminação
x
xy
xy
{E} (modus ponens)
y
((x  (x  y))  y) = True
xy
tautologia
{E1}
x
correspondente
((x  y)  x) = True
xy
{E2}
y
((x  y)  y) = True
[x] |– z [y] |– z
{E}
z
(((x  y)  (x  z)  (y  z))  z) = True
Outras Regras
x
x
{ID}
(x  x) = True
False
{CTR}
x
(False  x) = True
Regras de Introdução
[x] |– y
x  y {I}
((x  y)  (x  y)) = True
x y
{I}
xy
((x  y)  (x  y)) = True
x
{I1}
xy
(x  (x  y)) = True
y
{I2}
xy
(y  (x  y)) = True
[x] |– False
{RAA}
x
(((x)  False)  x) = True
3
Teorema e Prova
Teorema ( Comuta)
casa com a
hipótese  a  b |– b  a
Prova
hipótese
prova de
(a  b) |– b
é OK reusar uma
hipótese do teorema
2 provas para
aplicar a regra I
ab
ab
{E2}
{E1}
prova de
(a  b) |– a
b
a
 {I}
ba
Usa a regra E2
Dedução
Natural
Provas acima da linha
{regra}
Conclusão abaixo da
Provas formam
uma estrutura de árvore:
linha
a
b
 {I}
ab
Folhas = hipóteses
Raiz = conclusão
Regras de Inferência = ramos
4
Transitividade da Implicação
Teorema (Transitividade da Implicação)
ab, bc |– ac
 Suponha que podemos obter uma prova para: a |– c
 Então a regra I nos permitiria concluir ac
 Estratégia
 Suponha a
 Prove: a |– c
 Conclua ac (aplicando a regra I)
prova
hipótese admitida
temporariamente
descarregada
por I
folhas restantes
a ab
são as hipóteses
{E}
bc
b
{E}
c
{I}
ac
a raiz é a conclusão
5
Ou Comuta
Teorema (Ou Comuta) a  b |– b  a
Suponha
 Que podemos provar o teorema:
a |– b  a
 E podemos também provar o teorema: b |– b  a
 Então, aplicando a regra E, concluímos b  a de a  b
premissas
a
b
temporárias

{I2}

{I1}
hipótese
ab
ba
ba
{E}
restante
ba
descarregada
conclusão
por E
x
{I1}
xy
Ou Intro 1
y
{I2}
xy
Ou Intro 2
x  y [x] |– z [y] |– z
{E}
z
Ou Eliminação
6
Modus Tollens
Teorema (Modus Tollens)
 a  b, b |– a
 Convenção do sistema de dedução natural
 a é uma abreviação para a  False
ab
b  False
a  False
{ transitividade}
x -> y ¬y
 {modus tollens}
¬x
regra derivada
7
Negação
Convenção de dedução natural
a é uma abreviação para a  False
x
xy
{E}
y
[x] |– y
{I}
xy
x
x  False
{E}
False
[x] |– False
{I}
x  False
x
x
{E}
False
Não Eliminação
[x] |– False
{I}
x
Não Introdução
8
Exercício
Regras de Inferência
Prove o seguinte sequente: a  b, b  c |– c
xy
x
xy
{E}
y
xy
{E1}
x
xy
{E2}
y
[x] |– z
z
False
{CTR}
x
x
{ID}
x
[x] |– False
{RAA}
x
[y] |– z
{E}
[x] |– y
x  y {I}
x y
{I}
xy
x
{I1}
xy
y
{I2}
xy
x é uma abreviação para xFalse
ab
{E2}
b c
b
c
{ E}
9
Exercício
Regras de Inferência
Prove o seguinte sequente: a  b, a  c, b  d |– c  d
xy
x
xy
{E}
y
xy
{E1}
x
xy
{E2}
y
[x] |– z
z
False
{CTR}
x
x
{ID}
x
[x] |– False
{RAA}
x
[y] |– z
{E}
ab
{E2}
a c
a
c
[x] |– y
x  y {I}
x y
{I}
xy
x
{I1}
xy
y
{I2}
xy
x é uma abreviação para xFalse
{ E}
cd
ab
{E2}
b d
b
d
{ E}
{I}
10