Aula 2
(Equivalência e Implicação lógica aula 10
Professor: Renê Furtado Felix - Faculdade: UNIP
E-mail: [email protected] - Site: renecomputer.net
Equivalência em Lógica
Logica - Professor Renê F Felix
2
Definição
Há equivalência entre as proposições p e q somente quando a
bicondicional p ↔ q for uma tautologia ou
quando p e q tiverem a mesma tabela-verdade.
p ⇔ q (p é equivalente a q) é o símbolo que representa a
equivalência lógica.
Do ponto de vista da teoria da demonstração, p e q são
equivalentes se cada uma delas pode ser derivada a partir da
outra.
Semanticamente, p e q são equivalentes se elas têm os
mesmos valores para qualquer interpretação.
Logica - Professor Renê F Felix
3
Símbolo
Diferenciação dos símbolos ↔ e ⇔
O símbolo ↔ representa uma operação entre as
proposições p e q, que tem como resultado uma nova
proposição p ↔ q com valor lógico V ou F.
O símbolo ⇔ representa a não ocorrência de VF e
de FV na tabela-verdade P ↔ Q, ou ainda que o valor
lógico de P ↔ Q é sempre V, ou então P ↔ Q é uma
tautologia.
Logica - Professor Renê F Felix
4
Símbolo
Os símbolos ↔ e ⇔ são distintos!
↔ indica uma operação lógica.
o Aplicado
às proposições P e Q, resulta em uma nova
proposição.
⇔ indica uma relação.
o Estabelece que a bi-condicional é tautológica.
Logica - Professor Renê F Felix
5
Equivalência Lógica
• Propriedades
– Reflexiva
•P⇔P
– Simétrica
• Se P ⇔ Q então Q ⇔ P
– Transitiva
• Se P ⇔ Q e Q ⇔ R, então P ⇔ R
Logica - Professor Renê F Felix
6
Equivalência Lógica - Revisando
Algumas das equivalências mais importantes da
Lógica:
Leis da Comutatividade
• P ∧Q ⇔Q ∧ P
• P ∨Q ⇔Q ∨ P
Obs.: Cada uma das equivalências pode ser provada,
simplesmente mostrando que a bi-condicional correspondente
é uma tautologia, bastando, para isso, construir sua Tabela
Verdade.
Logica - Professor Renê F Felix
7
Exemplos
As seguintes sentenças são logicamente equivalentes:
P(d , f): Se hoje é sábado, então hoje é fim de semana.
P(d , f): Se hoje não é fim de semana, então hoje não é sábado.
Em símbolos:
d : "Hoje é sábado“
f : "Hoje é fim de semana"
Sintaticamente, (d) e (f) são equivalentes pela Lei da Contraposição.
Semanticamente, (d) e (f) têm os mesmos valores nas mesmas
interpretações.
Logica - Professor Renê F Felix
8
Exemplos
P(p , q): se eu nasci, então papai nasceu
p→q
é equivalente a:
p→q
~q → ~p
papai não nasceu, então eu não nasci
Logica - Professor Renê F Felix
9
Proposições associadas a uma condicional
Definição: Dada a condicional p  q, chamam- se
PROPOSIÇÕES ASSOCIADAS a p  q, as 3
seguintes proposições condicionais que contêm p e q:
• Proposição RECÍPROCA de p  q: q  p
• Proposição CONTRÁRIA de p  q: ~p  ~q
• Proposição CONTRAPOSITIVA de p  q: ~q  ~p
Logica - Professor Renê F Felix
10
Proposições associadas a uma condicional
As tabelas-verdade dessas 4 proposições:
p
q p→q q→p
Logica - Professor Renê F Felix
~p → ~q
~q → ~p
11
Equivalência Lógica
– Leis da Associatividade
(P ∧ Q) ∧ R ⇔ P ∧ (Q ∧ R)
(P ∨ Q) ∨ R ⇔ P ∨ (Q ∨ R)
– Leis da Distributividade
• P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)
• P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)
Logica - Professor Renê F Felix
12
Equivalência Lógica
– Leis de De Morgan
∀¬ (P ∧ Q) ⇔ ¬ P ∨ ¬ Q
∀¬ (P ∨ Q) ⇔ ¬ P ∧ ¬ Q
– Leis da Idempotência
•P∧P⇔P
•P∨P⇔P
Logica - Professor Renê F Felix
13
Equivalência Lógica
– Lei da Dupla Negação
P
~P
~~P
∀ ¬ (¬ P) ⇔ P
– Lei da Condicional
• P →Q ⇔¬ P ∨Q
– Lei da Bi-condicional
• P ↔ Q ⇔ (P → Q) ∧ (Q → P)
• P ↔ Q ⇔ (P ∧ Q) ∨ ( ¬ P ∧ ¬ Q)
Logica - Professor Renê F Felix
14
Equivalência Lógica
– Lei da Contraposição
•P→Q⇔¬Q→¬P
– Lei de Clavius
•
Lei de Clavius
P ~P ~P→P
∀¬P→P⇔P
– Lei da Refutação por Absurdo
• (p → q) ∧ (p → ¬ q) ⇔ ¬ p
Logica - Professor Renê F Felix
15
Equivalência Lógica
– Lei da Absorção
•p→p∧q⇔p→q
p
q
p∧q
Logica - Professor Renê F Felix
p→p∧q
p→p
16
Equivalência Lógica
– Lei do Dilema
• (P → Q) ∧ (¬ P → Q) ⇔ Q
– Lei da Demonstração por Absurdo (onde F é uma
contradição)
•P∧¬Q→F⇔P→Q
– Lei de Exportação - Importação
• P → (Q → R) ⇔ P ∧ Q → R
Logica - Professor Renê F Felix
17
Equivalência Lógica
O conceito de equivalência nos permite mostrar que
são suficientes as operações de negação e uma das
duas, conjunção ou disjunção, para representar
qualquer expressão proposicional:
– Eliminando o bi-condicional:
• P ↔ Q ⇔ (P ∧ Q) ∨ ( ¬ P ∧ ¬ Q)
Logica - Professor Renê F Felix
18
Equivalência Lógica
– Eliminando o condicional:
• P →Q ⇔¬ P ∨Q
– Escrevendo a disjunção em termos de conjunção:
• P ∨ Q ⇔ ¬ (¬ P ∧ ¬ Q)
– Escrevendo a conjunção em termos de disjunção:
• P ∧ Q ⇔ ¬ (¬ P ∨ ¬ Q)
Logica - Professor Renê F Felix
19
Equivalência Lógica
Ex.: Escrever a proposição
(P ↔ Q) → ¬ P
em termos da negação e disjunção
Logica - Professor Renê F Felix
20
Equivalência Lógica
Passos:
(P ↔ Q) → ~ P
Eliminando o condicional
~(P ↔ Q) ∨ ~ P
Eliminando o bi-condicional
~( (P ∧ Q) ∨ ( ~ P ∧ ~ Q) ) ∨ ~ P
Conjunção em termos de
~ ( ~ (~ P ∨ ~ Q) ∨ ~ (P ∨ Q) ) ∨ ~ P disjunção
Logica - Professor Renê F Felix
21
Exemplos
A tabela da bicondicional (p → q) ↔ (~q → ~p) será:
p
q
V
V
V
F
F
V
F
F
~q
~p
p→q
~q → ~p
(p → q) ↔ (~q → ~p)
Portanto, p → q é equivalente a ~q → ~p, pois estas proposições possuem a mesma
tabela-verdade ou a bicondicional (p → q) ↔ (~q → ~p) é uma tautologia.
Logica - Professor Renê F Felix
22
Exemplos
A tabela da bicondicional (p → q) ↔ (~q → ~p) será:
Portanto, p → q é equivalente a ~q → ~p, pois estas
proposições possuem a mesma tabela-verdade ou a
bicondicional (p → q) ↔ (~q → ~p) é uma tautologia.
Logica - Professor Renê F Felix
23
Exemplos
A
B
V
V
V
F
F
V
F
F
Logica - Professor Renê F Felix
A˄B
A→A ˄ B
A→B
24
Equivalência Lógica
Teoremas
A proposição P é logicamente equivalente à
proposição Q, ou seja, (P  Q), sempre que o
bicondicional (P  Q) é uma tautologia.
Logica - Professor Renê F Felix
25
Exemplos
Mostrar que (p  q) ^ (q  p) e (p  q) são equivalentes.
p
q
V
V
F
F
V
F
V
F
p → q q → p (p  q) ^ (q  p) (p  q)
Logo, (p  q) ^ (q  p)  (p  q)
Logica - Professor Renê F Felix
Tabelas-verdade idênticas
26
Exemplos
Mostrar que (p ^ q)  ~(~p v ~q).
p q p^q ~p ~q
V
V
F
F
~p v ~q
~(~p v ~q)
pq
V
F
V
F
Como (p ^ q)  ~(~p v ~q) é uma tautologia, então
(p ^ q)  ~(~p v ~q), isto é, ocorre a equivalência lógica.
Logica - Professor Renê F Felix
27
Implicação Lógica
Logica - Professor Renê F Felix
28
Implicação Lógica
Definição
Diz-se que uma proposição P implica logicamente uma
proposição Q, se Q é verdadeira todas as vezes que P é
verdadeira:
• Dizemos que P implica Q e escrevemos P => Q
Logica - Professor Renê F Felix
29
Implicação Lógica
modus ponens: (significa modo de afirmar)
p ˄ (p → q) => q (forma clássica)
(p → q) ˄ p => q (pode ser apresentada nesta outra forma).
(p → q) p implica em q, ou seja acontecendo p, q
necessariamente ocorrerá.
˄𝒑
. ͘. 𝒒
p aconteceu, então q ocorreu também.
Nós tivemos p, então houve q.
Logica - Professor Renê F Felix
30
Implicação Lógica
modus tollens: (significa modo de negar)
~q ˄ (p → q) => ~p (forma clássica)
(p → q) ˄ ~q => ~p (pode ser apresentada nesta outra forma).
(p → q) p implica em q, q não ocorreu, então também não
ocorreu p.
˄ ~𝐪
. ͘ . ~p
q não aconteceu, então p também não
ocorreu.
Logica - Professor Renê F Felix
31
Implicação Lógica
Exemplo:
A
B
V
V
V
F
F
V
F
F
A˄B
A ∧ B => A ∨ B
Logica - Professor Renê F Felix
AVB
A↔B
A proposição A ˄ B é
verdadeira somente na linha 1
e, nesta linha, as proposições
A V B e A ↔ B também são
verdadeiras. Logo, a primeira
posição implica cada uma das
outras posições, isto é:
p^q pvq e p^qpq
A ∧ B => A ↔ B
32
Implicação Lógica
As mesmas tabelas-verdade também demonstram as
importantes Regras de Inferência:
p q p^q pvq pq
(Adição)
ppvq e qpvq
(Simplificação)
p^qp e p^qq
Logica - Professor Renê F Felix
33
Implicação Lógica
2. As tabelas-verdade das proposições p  q, p  q, q  p
são:
p q p q p→ q q→ p
A proposição “p  q” é
verdadeiras nas linhas 1 e 4 e,
nestas linhas, as proposições
“p  q” e “q  p” também são
verdadeiras. Logo, a primeira
posição implica cada uma das
outras duas posições, isto é:
pq pq e pqqp
Logica - Professor Renê F Felix
34
Implicação Lógica
3. As tabelas-verdade das proposições
p q p v q ~ p (p v q) ^ ~p
“(p v q) ^ ~p” são:
Esta
proposição
é
verdadeira somente na
linha 3 e, nesta linha, a
proposição “q” também
é verdadeira. Logo,
subsiste a implicação
lógica:
(p v q) ^ ~p  q
Logica - Professor Renê F Felix
35
Implicação Lógica
4. A tabelas-verdade da proposições
p q pq
(p  q) ^ p
“(p  q) ^ p” são:
Esta
proposição
é
verdadeira somente na
linha 1 e, nesta linha, a
proposição “q” também
é verdadeira. Logo,
subsiste a implicação
lógica:
(p  q) ^ p  q
denominada Regra Modus ponens.
Logica - Professor Renê F Felix
36
Implicação Lógica
5. A tabelas-verdade da proposições
“(p  q) ^ ~q” e “~p” são:
p q p q ~q (p  q) ^ ~q ~p
Esta
proposição
é
verdadeira somente na
linha 4 e, nesta linha, a
proposição “~p” também
é verdadeira. Logo,
subsiste a implicação
lógica:
(p  q) ^ ~q  ~p ,
denominada Regra do Modus tollens.
Logica - Professor Renê F Felix
As mesmas tabelas-verdade também mostram
que “~p” implica “p  q”, isto é: ~p  p  q
37
Implicação Lógica
Exemplo:
p
V
q
p˄q
V
pVq
p↔q
Regras
Formulas atômicas
Modus Ponens
Modus Tollens
p ˄ (p → q) => q
~q ˄ (p → q) => ~p
Silogismo Hipotético (p → q) ˄ (q → r) =>(p → r)
V
F
F
V
Simplificação
(p V q) ˄ ~p => q
p ˄ q => p
F
F
Adição
p => p V q
Logica - Professor Renê F Felix
Silogismo Disjuntivo
38
Implicação Lógica
Teorema
A proposição P implica a proposição Q, isto é:
P => Q
se e somente se a condicional:
P → Q (1)
é tautológica.
Logica - Professor Renê F Felix
39
Implicação Lógica
• Se P implica Q, então, não ocorre que os valores lógicos
simultâneos
destas
duas
proposições
sejam
respectivamente V e F, e por conseguinte a última coluna
da tabela-verdade da condicional (1) apresenta somente
a letra V, isto é, esta condicional é tautológica.
• Reciprocamente, se a condicional (1) é tautológica,
então, não ocorre que os valores lógicos simultâneos das
proposições P e Q sejam respectivamente V e F, e por
conseguinte a primeira proposição implica a segunda.
Logica - Professor Renê F Felix
40
Exemplo
A
B
V
V
V
F
F
V
F
F
A ∧ B => A ↔ B
Logica - Professor Renê F Felix
A˄B
A↔B
(A ˄ B) → (A↔B)
(A ∧ B) → (A ↔ B)
41
Implicação Lógica
Propriedades
Reflexa
- P => P
Transitiva
- Se P => Q e Q => R, então P => R
Logica - Professor Renê F Felix
42
Implicação Lógica
Algumas das implicações mais importantes da
Lógica:
– Regra da Adição
• P => P ∨ Q
Obs.: Cada uma das implicações pode ser provada,
bastando para isso construir a Tabela Verdade da
condicional correspondente; se a condicional for
tautológica, será uma inferência.
Logica - Professor Renê F Felix
43
Implicação Lógica
– Regra da Simplificação
• P ∧ Q => P
– Regra da Simplificação Disjuntiva
• (P ∨ Q) ∧ (P ∨ ~Q) => P
– Regra da Absorção
• P → Q => P → (P ∧ Q)
Logica - Professor Renê F Felix
44
Implicação Lógica
– Regra do Silogismo Hipotético (ou Condicional)
• (P → Q) ∧ (Q → R) => P → R
– Regra do Silogismo Disjuntivo (ou Alternativo)
• (P ∨ Q) ∧ ~P => Q
– Regra do Silogismo
Incompatibilidade)
• ~(P ∧ Q) ∧ Q => ~P
Logica - Professor Renê F Felix
Conjuntivo
(ou
45
Implicação Lógica
– Dilema Construtivo
• (P → Q) ∧ (R → S) ∧ (P ∨ R) => Q ∨ S
– Dilema Destrutivo
• (P → Q) ∧ (R → S) ∧ (~Q ∨ ~S) => ~P ∨ ~R
– Regra da Inconsistência (de uma contradição se
conclui qualquer proposição)
• (P ∧ ~P) => Q
Logica - Professor Renê F Felix
46
Implicação Lógica
– Modus Ponens
• (P → Q) ∧ P => Q
– Modus Tollens
• (P → Q) ∧ ~Q => ~P
– Regra da Atenuação
• P → Q => P → Q ∨ R
– Regra da Retorsão
• ~P → P => P
Logica - Professor Renê F Felix
47
Implicação Lógica e equivalência
Uma diferença importantíssima entre a implicação
e equivalência reside no fato de que, na implicação,
só há o caminho de ida, não existe o de volta. Ou
melhor, toda equivalência é uma implicação lógica
por natureza. Diferentemente, a implicação não se
trata necessariamente de uma equivalência lógica.
Podemos então dizer que toda equivalência é uma
implicação lógica, mas nem toda implicação é
uma equivalência lógica.
Logica - Professor Renê F Felix
48
Implicação Lógica e equivalência
Assim: p ^ q  p (certo)
O caminho de volta pode estar errado se desejado:
p  p ^ q (errado)
Na equivalência, pode-se ir e vir entre duas
proposições. Temos:
(~p v q)  (p → q)
O caminho de volta seria perfeitamente válido:
(p → q)  (~p v q)
Logica - Professor Renê F Felix
49
Implicação Lógica e equivalência
Em outras palavras:
Dizer que p ^ q  p é a mesma coisa que afirmar
que p ^ q  p
Porém, p ^ q  p não é a mesma coisa de dizer que
pp^q
Logica - Professor Renê F Felix
50
Equivalência Lógica
As proposições P e Q são equivalentes quando
apresentam tabelas verdades idênticas.
Indicamos que p é equivalente a q do seguinte
modo: p  q.
Exemplos:
(p  q) ^ ( q  p)  p  q
p  q  ~( p ^ ~ q )  ~p v q
Logica - Professor Renê F Felix
51
Equivalência Lógica
Exercício:
Dizer que “André é artista ou Bernardo não é engenheiro” é
logicamente equivalente a dizer que:
a) André é artista se e somente Bernardo não é engenheiro.
b) Se André é artista, então Bernardo não é engenheiro.
c) Se André não é artista, então Bernardo é engenheiro.
d) Se Bernardo é engenheiro, então André é artista.
e) André não é artista e Bernardo é engenheiro.
Resolução: Na expressão temos ~p v q  p  q  ~q  ~p Temos duas
possibilidades de equivalência p  q: Se André não é artista , então Bernardo
não é engenheiro. Porém não temos essa opção.
~q  ~p: Se Bernardo é engenheiro, então André é artista. Logo reposta letra d).
Logica - Professor Renê F Felix
52
Equivalência Lógica
Exercício:
Dizer que “Pedro não é pedreiro ou Paulo é paulista,” é do ponto de
vista lógico, o mesmo que dizer que::
a) Se Pedro é pedreiro, então Paulo é paulista.
b) Se Paulo é paulista, então Pedro é pedreiro.
c) Se Pedro não é pedreiro, então Paulo é paulista.
d) Se Pedro é pedreiro, então Paulo não é paulista.
e) Se Pedro não é pedreiro, então Paulo não é paulista.
Resolução: Na expressão temos ~p v q  p  q
p  q: Se Pedro é pedreiro, então Paulo é paulista. Letra a).
Logica - Professor Renê F Felix
53
Equivalência Lógica
Exercício:
Dizer que não é verdade que Pedro é pobre e Alberto é alto, é
logicamente equivalente a dizer que é verdade que:
a) Pedro não é pobre ou Alberto não é alto.
b) Pedro não é pobre e Alberto não é alto.
c) Pedro é pobre ou Alberto não é alto.
d) se Pedro não é pobre, então Alberto é alto.
e) se Pedro não é pobre, então Alberto não é alto.
p: Pedro é pobre
q: Alberto é alto
A proposição é Pedro é pobre e Alberto é alto.
Logica - Professor Renê F Felix
(p ^ q)
54
Equivalência Lógica
Logo, dizer que não é verdade que Pedro é pobre e Alberto
é alto é negar toda a proposição Pedro é pobre e Alberto é
alto. Aí, escrevendo a nossa proposição composta em
linguagem simbólica:
~(p ^ q)
Agora, vamos demonstrar na tabela-verdade...
Logica - Professor Renê F Felix
55
Equivalência Lógica
Resposta correta: a) ~(p ^ q)  ~p v ~q
Ou, no bom português, podemos dizer que:
Não é verdade que Pedro é pobre e Alberto é alto é logicamente
equivalente a dizer que Pedro não é pobre ou Alberto não é alto
Logica - Professor Renê F Felix
56
Exercícios - Equivalência Lógica
1. A negação da afirmação condicional
chovendo, eu levo o guarda-chuva" é:
"se
estiver
a) se não estiver chovendo, eu levo o guarda-chuva
b) não está chovendo e eu levo o guarda-chuva
c) não está chovendo e eu não levo o guarda-chuva
d) se estiver chovendo, eu não levo o guarda-chuva
e) está chovendo e eu não levo o guarda-chuva
Logica - Professor Renê F Felix
57
Exercícios - Equivalência Lógica
2.Chama-se tautologia a toda proposição que é sempre
verdadeira, independentemente da verdade dos termos
que a compõem. Um exemplo de tautologia é:
a) se João é alto, então João é alto ou Guilherme é gordo
b) se João é alto, então João é alto e Guilherme é gordo
c) se João é alto ou Guilherme é gordo, então Guilherme
é gordo
d) se João é alto ou Guilherme é gordo, então João é
alto e Guilherme é gordo
e) se João é alto ou não é alto, então Guilherme é gordo
Logica - Professor Renê F Felix
58
Exercícios - Equivalência Lógica
3. Considere as afirmações: A) se Patrícia é uma boa amiga, Vítor diz a
verdade; B) se Vítor diz a verdade, Helena não é uma boa amiga; C)
se Helena não é uma boa amiga, Patrícia é uma boa amiga. A análise
do encadeamento lógico dessas três afirmações permite concluir que
elas:
a) implicam necessariamente que Patrícia é uma boa amiga
b) são consistentes entre si, quer Patrícia seja uma boa amiga, quer
Patrícia não seja uma boa amiga
c) implicam necessariamente que Vítor diz a verdade e que Helena não
é uma boa amiga
d) são equivalentes a dizer que Patrícia é uma boa amiga
e) são inconsistentes entre si
Logica - Professor Renê F Felix
59
Exercícios - Equivalência Lógica
4. Se Rodrigo mentiu, então ele é culpado. Logo:
a)
b)
c)
d)
e)
Rodrigo é culpado.
se Rodrigo não mentiu, então ele não é culpado.
Rodrigo mentiu.
se Rodrigo não é culpado, então ele não mentiu.
se Rodrigo é culpado, então ele mentiu.
Logica - Professor Renê F Felix
60
Exercícios - Equivalência Lógica
4. Se Rodrigo mentiu, então ele é culpado. Logo:
a)
b)
c)
d)
e)
Rodrigo é culpado.
se Rodrigo não mentiu, então ele não é culpado.
Rodrigo mentiu.
se Rodrigo não é culpado, então ele não mentiu.
se Rodrigo é culpado, então ele mentiu.
Logica - Professor Renê F Felix
61
Exercícios - Equivalência Lógica
5. Se você se esforçar, então irá vencer. Logo:
a)
b)
c)
d)
e)
mesmo que se esforce, você não vencerá.
seu esforço é condição necessária para vencer.
se você não se esforçar, então não irá vencer.
você vencerá só se se esforçar.
seu esforço é condição suficiente para vencer.
Logica - Professor Renê F Felix
62
Exercícios - Equivalência Lógica
5. Se você se esforçar, então irá vencer. Logo:
a)
b)
c)
d)
e)
mesmo que se esforce, você não vencerá.
seu esforço é condição necessária para vencer.
se você não se esforçar, então não irá vencer.
você vencerá só se se esforçar.
seu esforço é condição suficiente para vencer.
Logica - Professor Renê F Felix
63
Implicação Lógica
Conectivos lógicos
Logica - Professor Renê F Felix
64
Dúvidas ?
Uma pessoa será tão feliz quanto a sua
mente decidir.
Abraham Lincoln
Logica - Professor Renê F Felix
65