Aula7 Implicacao Logica

Prévia do material em texto

Implicac¸a˜o Lo´gica
Professor:
Silvio Luiz Bragatto Boss
e-mail:
silvioboss@utfpr.edu.br
Universidade Tecnolo´gica Federal do Parana´ - UTFPR
Coordenac¸a˜o de Informa´tica - COINF
Curso de Engenharia de Computac¸a˜o
Disciplina de Lo´gica para Computac¸a˜o
Implicac¸a˜o Lo´gica
Suma´rio
1 Implicac¸a˜o Lo´gica
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Revisando...
Vamos iniciar esta aula relembrando a operac¸a˜o lo´gica da
condicional p → q (le^-se: se p ent~ao q)
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Revisando...
Vamos iniciar esta aula relembrando a operac¸a˜o lo´gica da
condicional p → q (le^-se: se p ent~ao q)
Voceˆ esta´ lembrado quando estudamos as proposic¸o˜es
condicionais e utilizamos o s´ımbolo →? Vamos recordar!
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Revisando...
Vamos iniciar esta aula relembrando a operac¸a˜o lo´gica da
condicional p → q (le^-se: se p ent~ao q)
Voceˆ esta´ lembrado quando estudamos as proposic¸o˜es
condicionais e utilizamos o s´ımbolo →? Vamos recordar!
Na condicional p → q, p e´ chamado de antecedente e q e´ o
consequente;
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Revisando...
Vamos iniciar esta aula relembrando a operac¸a˜o lo´gica da
condicional p → q (le^-se: se p ent~ao q)
Voceˆ esta´ lembrado quando estudamos as proposic¸o˜es
condicionais e utilizamos o s´ımbolo →? Vamos recordar!
Na condicional p → q, p e´ chamado de antecedente e q e´ o
consequente;
O s´ımbolo → representa uma operac¸a˜o matema´tica entre as
proposic¸o˜es p e q que tem como resultado a proposic¸a˜o p →
q, como valor lo´gico V ou F.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
A proposic¸a˜o condicional se p ent~ao q e´ uma proposic¸a˜o
composta que so´ admite valor lo´gico falso no caso em que a
proposic¸a˜o p e´ verdadeira e a proposic¸a˜o q e´ falsa, sendo
verdade nas demais situac¸o˜es.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
A proposic¸a˜o condicional se p ent~ao q e´ uma proposic¸a˜o
composta que so´ admite valor lo´gico falso no caso em que a
proposic¸a˜o p e´ verdadeira e a proposic¸a˜o q e´ falsa, sendo
verdade nas demais situac¸o˜es.
O valor lo´gico da condicional de duas proposic¸o˜es e´ definido
pela seguinte tabela-verdade:
p q p → q
1 V V V
2 V F F
3 F V V
4 F F V
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos rever esta operac¸a˜o lo´gica por meio de uma situac¸a˜o:
Suponha que um determinado pai faz a seguinte promessa
para seu filho:
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos rever esta operac¸a˜o lo´gica por meio de uma situac¸a˜o:
Suponha que um determinado pai faz a seguinte promessa
para seu filho:
Se fizer sol amanh~a, ent~ao viajaremos para a praia.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos rever esta operac¸a˜o lo´gica por meio de uma situac¸a˜o:
Suponha que um determinado pai faz a seguinte promessa
para seu filho:
Se fizer sol amanh~a, ent~ao viajaremos para a praia.
Ha´ 4 possibilidades:
1 Fez sol e viajaram para a praia.
2 Fez sol e na˜o viajaram para a praia.
3 Na˜o fez sol e viajaram para a praia.
4 Na˜o fez sol e na˜o viajaram para a praia.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
p q p → q
Se Enta˜o Se fizer sol amanha
fizer sol Viajaremos para enta˜o viajaremos para
amanha a praia a praia
1 V V V
2 V F F
3 F V V
4 F F V
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
p q p → q
Se Enta˜o Se fizer sol amanha
fizer sol Viajaremos para enta˜o viajaremos para
amanha a praia a praia
1 V V V
2 V F F
3 F V V
4 F F V
Vamos comparar cada uma das possibilidades levantadas
anteriormente com os valores lo´gicos colocados na tabela e
responder a seguinte pergunta:
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Em qual das possibilidades a situac¸a˜o foi descumprida?
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Em qual das possibilidades a situac¸a˜o foi descumprida?
Na˜o e´ dif´ıcil concluir que na possibilidade 2, a situac¸a˜o foi
descumprida;
Voceˆ deve estar se perguntando sobre a possibilidade 3.
Afinal, se na˜o fez sol, como viajaram para a praia? Parece
estranho, na˜o?
Na verdade, temos que tomar um certo cuidado, o pai so´ disse
o que fariam se fizesse sol, mas na˜o disse o que fariam se na˜o
fizesse sol.
Esta e´ raza˜o da condicional na linha 3 ser logicamente
verdadeira. Temos que ter muita atenc¸a˜o, especialmente
nesta parte.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vejamos um outro exemplo:
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vejamos um outro exemplo:
Se chover hoje, ent~ao vou ficar em casa
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vejamos um outro exemplo:
Se chover hoje, ent~ao vou ficar em casa
Vamos ver as quatro possibilidades para esta situac¸a˜o:
1 Choveu e fiquei em casa.
2 Choveu e na˜o fiquei em casa.
3 Na˜o choveu e fiquei em casa.
4 Na˜o choveu e na˜o fiquei em casa.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
p q p → q
Se Enta˜o Se chover hoje
chover vou ficar enta˜o vou ficar
hoje em casa em casa
1 V V V
2 V F F
3 F V V
4 F F V
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
p q p → q
Se Enta˜o Se chover hoje
chover vou ficar enta˜o vou ficar
hoje em casa em casa
1 V V V
2 V F F
3 F V V
4 F F V
E´ importante entender que na lo´gica matema´tica apenas nos
preocupamos com a relac¸a˜o entre os valores lo´gicos.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Neste exemplo, ficou claro que apenas na possibilidade 2, a
situac¸a˜o foi descumprida;
Isto e´, choveu e n~ao fiquei em casa.
E´ prova´vel surgir du´vidas com relac¸a˜o a` possibilidade 3.
Afinal, Se n~ao choveu, como fiquei em casa?;
Voltamos a dizer, sendo o antecedente (p) logicamente falso,
na˜o importa o valor lo´gico do consequente (q), pois o valor
lo´gico da condicional sera´ sempre verdadeiro!
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Mas qual a raza˜o de retomarmos a operac¸a˜o condicional?
A raza˜o esta´ no fato de que podemos dizer que a operac¸a˜o
que traduz, em termos de Lo´gica Matema´tica, a ideia de uma
frase condicional e´ a implicac¸a˜o.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
E qual e´ a importaˆncia da implicac¸a˜o?
A implicac¸a˜o e´ muito importante na linguagem matema´tica
porque aparece sistematicamente nos teoremas que
constituem as teorias matema´ticas.
Um teorema e´ uma proposic¸a˜o do tipo p ⇒ q, onde p e´ uma
proposic¸a˜o verdadeira na teoria em questa˜o.
Demonstrar um teorema na˜o e´ mais do que provar que a
proposic¸a˜o p ⇒ q e´ verdadeira e sendo p verdadeira, por
hipo´tese, implica dizer que q e´ tambe´m verdadeira.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Veremos este sentido de implicac¸a˜o com um pouco mais de
detalhes;
Retomamos a operac¸a˜o lo´gica da condicional e agora vamos
retomar o conceito de tautologia visto am aula anterior,que
sera´ importante para o entendimento das implicac¸o˜es lo´gicas.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Veremos este sentido de implicac¸a˜o com um pouco mais de
detalhes;
Retomamos a operac¸a˜o lo´gica da condicional e agora vamos
retomar o conceito de tautologia visto am aula anterior, que
sera´ importante para o entendimento das implicac¸o˜es lo´gicas.
Relembrando...
Quando uma proposic¸a˜o composta e´ sempre verdadeira, enta˜o
teremos uma tautologia. De outra forma, podemos afirmar que
numa tautologia a proposic¸o˜es compostas sera˜o logicamente
verdadeiras (V).
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
O s´ımbolo P ⇒ Q (P implica Q) representa a implicac¸a˜o
lo´gica;
Observe neste conceito que aparecem dois s´ımbolos
matema´ticos → e ⇒.
Vamos diferencia´-los!
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Diferenciac¸a˜o dos s´ımbolos → e ⇒
1 O s´ımbolo → (p → q) Le^-se: se p . . . ent~ao q
representa uma operac¸a˜o matema´tica entre as proposic¸o˜es p e
q que tem como resultado a proposic¸a˜o p → q, com valor
lo´gico V ou F.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Diferenciac¸a˜o dos s´ımbolos → e ⇒
1 O s´ımbolo → (p → q) Le^-se: se p . . . ent~ao q
representa uma operac¸a˜o matema´tica entre as proposic¸o˜es p e
q que tem como resultado a proposic¸a˜o p → q, com valor
lo´gico V ou F.
2 O s´ımbolo ⇒ (P ⇒ Q) Le^-se: P implica Q
representa a na˜o ocorreˆncia de VF na tabela-verdade de P →
Q, ou ainda que o valor lo´gico da condicional P → Q sera´
sempre V, ou enta˜o que P → Q e´ uma tautologia.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos ver agora, o s´ımbolo ⇒, com mais detalhes;
Tenha sempre em mente que o s´ımbolo ⇒ representa uma
implicac¸a˜o, cuja condicional sera´ sempre tautolo´gica, isto e´,
sera´ sempre logicamente verdadeira;
Vejamos alguns exemplos e verificando a implicac¸a˜o lo´gica
indicada em cada caso.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Exemplos
Implicac¸o˜es Leitura
1 p ∧ q ⇒ p p e q implica p
2 p ⇒ q → p p implica a condicional, se q enta˜o p
3 p ∧ q ⇒ p ∨ q (p e q) implica (p ou q)
4 p ⇒ p ∨ q p implica (p ou q)
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Exemplos
Implicac¸o˜es Leitura
1 p ∧ q ⇒ p p e q implica p
2 p ⇒ q → p p implica a condicional, se q enta˜o p
3 p ∧ q ⇒ p ∨ q (p e q) implica (p ou q)
4 p ⇒ p ∨ q p implica (p ou q)
Atenc¸a˜o!!
Devemos ter em mente que uma proposic¸a˜o P implica uma
proposic¸a˜o Q, se Q e´ verdadeira todas as vezes que P e´ verdadeira.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos comprovar isto para o 1o exemplo dado: p ∧ q ⇒ p
Considere a situac¸a˜o:
p: Marina Silva vencera´ as eleic¸o˜es para a Presideˆncia do
Brasil.
q: A taxa de desemprego caira´ nos pro´ximos treˆs anos.
p ∧ q: Marina Silva vencera´ as eleic¸o˜es para a Presideˆncia do
Brasil e a taxa de desemprego caira´ nos pro´ximos treˆs anos.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos agora verificar como ficam os poss´ıveis valores lo´gicos
das proposic¸o˜es:
p q p ∧ q
Marina Silva A taxa de Marina Silva vencera´
vencera´ as desemprego as eleic¸o˜es para a
eleic¸o˜es para caira´ nos Presideˆncia do Brasil
a Presideˆncia do pro´ximos e a taxa de desemprego
Brasil neste ano treˆs anos caira´ nos pro´ximos treˆs anos
1 V V V
2 V F F
3 F V F
4 F F F
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Perceba que quando p ∧ q e´ verdadeira (1a possibilidade), p e´
verdadeira tambe´m, logo dizemos que p ∧ q implica p e, tem a
seguinte notac¸a˜o: p ∧ q ⇒ p.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Perceba que quando p ∧ q e´ verdadeira (1a possibilidade), p e´
verdadeira tambe´m, logo dizemos que p ∧ q implica p e, tem a
seguinte notac¸a˜o: p ∧ q ⇒ p.
E mais, se voceˆ fizer a condicional (p ∧ q) → p, ela sera´
sempre verdadeira, ou seja uma tautologia.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos verificar a implicac¸a˜o: p ⇒ q → p
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos verificar a implicac¸a˜o: p ⇒ q → p
Observe que...
A intenc¸a˜o aqui, e´ perceber que o ponto fundamental da
implicac¸a˜o lo´gica (P implica uma proposic¸a˜o Q, indica-se por
P ⇒ Q), sempre que temos um antecedente verdadeiro, teremos
um consequente verdadeiro tambe´m.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Vamos verificar a implicac¸a˜o: p ⇒ q → p
Observe que...
A intenc¸a˜o aqui, e´ perceber que o ponto fundamental da
implicac¸a˜o lo´gica (P implica uma proposic¸a˜o Q, indica-se por
P ⇒ Q), sempre que temos um antecedente verdadeiro, teremos
um consequente verdadeiro tambe´m.
Vamos verificar se p de fato implica a proposic¸a˜o composta q → p,
ou seja, (p ⇒ q → p).
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
p q q → p p → (q → p)
1 V V V V
2 V F V V
3 F V F V
4 F F V V
p ⇒ q → p, pois o condicional p → (q → p) e´ tautolo´gica;
Perceba que quando p e´ verdadeira (1a e 2a colunas), q → p
e´ verdadeira tambe´m, logo dizemos que p implica a
proposic¸a˜o composta q → p. (p ⇒ q → p).
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Mostraremos a implicac¸a˜o do 3o exemplo: p ∧ q ⇒ p ∨ q
p q p ∧ q p ∨ q (p ∧ q) → (p ∨ q)
1 V V V V V
2 V F F V V
3 F V F V V
4 F F F F V
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Mostraremos a implicac¸a˜o do 3o exemplo: p ∧ q ⇒ p ∨ q
p q p ∧ q p ∨ q (p ∧ q) → (p ∨ q)
1 V V V V V
2 V F F V V
3 F V F V V
4 F F F F V
Podemos verificar a implicac¸a˜o p ∧ q ⇒ p ∨ q, por meio da
condicional (p ∧ q) → (p ∨ q), pois, e´ uma tautologia.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Mostraremos a implicac¸a˜o do 3o exemplo: p ∧ q ⇒ p ∨ q
p q p ∧ q p ∨ q (p ∧ q) → (p ∨ q)
1 V V V V V
2 V F F V V
3 F V F V V
4 F F F F V
Podemos verificar a implicac¸a˜o p ∧ q ⇒ p ∨ q, por meio da
condicional (p ∧ q) → (p ∨ q), pois, e´ uma tautologia.
Pode-se verificar a implicac¸a˜o dada observando que quando a
proposic¸a˜o p ∧ q e´ verdadeira, temos que p ∨ q, tambe´m, e´
verdadeira (1a linha). Logo, esta´ verificada a implicac¸a˜o dada.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Implicac¸a˜o do 4o exemplo: p ⇒ p ∨ q
p q p ∨ q p → (p ∨ q)
1 V V V V
2 V F V V
3 F V V V
4 F F F V
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Implicac¸a˜o do 4o exemplo: p ⇒ p ∨ q
p q p ∨ q p → (p ∨ q)
1 V V V V
2 V F V V
3 F V V V
4 F F F V
Neste exemplo, tambe´m verificamos a implicac¸a˜o p ⇒ p ∨ q,
pois a condicional p → (p ∨ q) e´ tautolo´gica.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Implicac¸a˜o do 4o exemplo: p ⇒ p ∨ q
p q p ∨ q p → (p ∨ q)
1 V V V V
2 V F V V
3 F V V V
4 F F F V
Neste exemplo, tambe´m verificamos a implicac¸a˜o p ⇒ p ∨ q,
pois a condicional p → (p ∨ q) e´ tautolo´gica.
Observe que quando a proposic¸a˜o p e´ verdadeira, temos que
p ∨ q, tambe´m, e´ verdadeira (1a e 2a linhas). Logo, esta´
verificada a implicac¸a˜o dada.
UTFP RImplicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Observac¸a˜o
O fato de dizer que uma proposic¸a˜o P implica uma proposic¸a˜o
Q,na˜o garante dizer o caminho inverso, isto e´, que Q tambe´m
implica P;
Estudaremos, nas pro´ximas aulas, as situac¸o˜es que envolvem o
caminho de ida e de volta quando consideramos as
implicac¸o˜es. Neste caso chamaremos de equivaleˆncias
lo´gicas.
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Implicac¸a˜o Lo´gica
Exerc´ıcios
1 Mostrar que p ↔ ¬q na˜o implica p → q.
2 Mostrar que p na˜o implica p ∧ q e que p ∨ q na˜o implica p.
3 Mostrar que (p ∧ q) ⇒ (p ↔ q)
UTFP R
Implicac¸a˜o Lo´gica LATEX
Implicac¸a˜o Lo´gica
Operac¸o˜es Lo´gicas
Refereˆncias Bibliogra´ficas
☞ FARO, S.D. Racioc´ınio Lo´gico Matema´tico - Cap. 4 -
Implicac¸a˜o Lo´gica. Notas de aula.
☞ ALENCAR FILHO, Edgard de. Iniciac¸a˜o a` lo´gica
matema´tica. Sa˜o Paulo: Nobel, c1975. 203 p.
UTFP R
Implicac¸a˜o Lo´gica LATEX