Click here to load reader
Upload
trandung
View
213
Download
1
Embed Size (px)
Citation preview
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
Universidade Federal do Espírito SantoCentro de Ciências Agrárias – CCA UFESDepartamento de Computação
Lógica Computacional 1Site: http://jeiks.net E-mail: [email protected]
Implicação Lógica
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
2
Implicação Lógica
● Definição– A proposição P(p,q,r,...) implica logicamente a proposição
Q(p,q,r,...) quando Q é verdadeira todas as vezes que P é verdadeira.
● Notação:
P(p,q,r,...) Q(p,q,r,...)
● Exemplo:
p q p q p q p ↔ q
V V V V V
V F F V F
F V F V F
F F F F V
Obtém-se:
p q p q
p q p ↔ q
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
3
Exercícios
● Efetue a tabela verdade para as seguintes sentenças e indique quais as implicações lógicas existentes:
a) p q
b) p q ~p
c) q → p
d) p → p q
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
4
Implicação Lógica
● Toda proposição implica uma Tautologia:
p p ~p● Somente uma contradição implica uma contradição:
p ~p p ~p → p ~p
p p ~p
V V
F V
p ~p p ~p p ~p → p ~p
V F F F
F V F F
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
5
Propriedades
● Reflexiva:
– P(p,q,r,...) P(p,q,r,...)
– Uma proposição complexa implica ela mesma.
● Transitiva:
– Se P(p,q,r,...) Q(p,q,r,...) e
Q(p,q,r,...) R(p,q,r,...), então
P(p,q,r,...) R(p,q,r,...)
– Se P Q e Q R, então P R
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
6
Regras de Inferência
● Inferência– Ato ou processo de derivar conclusões lógicas de proposições
conhecidas ou decididamente verdadeiras.
– Em outras palavras: é a obtenção de novas proposições a partir de proposições verdadeiras já existentes.
● Regras de Inferência obtidas da implicação lógica:– Adição:
p p q e q p q
– Simplificação:
p q q e p q q.
.
p q p q p q p ↔ q
V V V V V
V F F V F
F V F V F
F F F F V
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
7
Regras de Inferência
● Silogismo Disjuntivo
(p q) ~p q
(p q) ~q p
● Modus Ponens
(p → q) p q
p q p q ~p (p q) ~p
V V V F F
V F V F F
F V V V V
F F F V F
p q p → q (p → q) p
V V V V
V F F F
F V V F
F F V F
(p q), ~p (p q), ~q
q p
(p q), ~p (p q), ~q
q p
(p →q), p
q
(p →q), p
q
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
8
Regras de Inferência
● Modus Tollens
(p → q) ~q ~p
p q p → q ~q (p → q) ~q ~p
V V V F F F
V F F V F F
F V V F F V
F F V V V V
(p →q), ~q
~p
(p →q), ~q
~p
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
9
Tautologias e Implicação Lógica
● Teorema
P(p,q,r,..) Q(p,q,r,...)
se e somente se
P(p,q,r,...) → Q(p,q,r,...)
● Observe que:
→ indica uma operação lógica entre as proposições.● Ex.: das proposições p e q, dá-se a nova proposição p → q.
indica uma relação.● Ex.: estabelece que a condicional P → Q é tautológica.
p q (p → q) p ((p → q) p) → q
V V V V
V F F V
F V F V
F F F V
(p → q) p q e ((p → q) p) →q
Unive rsidad e F
ede ral do Espír ito S
a nto – CC
A U
FE
S
10
Inferências
● Regra do Silogismo Hipotético
(p → q) (q → r) p → r
● Princípio da inconsistência
– Como “p ~p → q” é tautológica, subsiste a implicação lógica p ~p q
– Assim, de uma contradição p ~p se deduz qualquer proposição q.
● A proposição “(p ↔ q) p” implica a proposição “q”, pois a condicional “(p ↔ q) p → q” é tautológica.
(p ↔ q) p q
p →q, q → r
p → r
p →q, q → r
p → r
p ↔ q, p
q
p ↔ q, p
q