Slides Unidade 2 Lógica UNIP EAD

Prévia do material em texto

Unidade II
LÓGICA
Prof. João Giardulli
Objetivo
 Apresentar regras e estruturas 
adicionais sobre o uso de proposições.
 Conceituar implicação lógica, 
tautologias, e as propriedades sobre 
proposições.
 Apresentar os fundamentos da dedução, 
métodos dedutivos e técnicas de 
redução da quantidade de conectivos.
Introdução
Nesta unidade, serão apresentados temas 
mais avançados sobre proposições, o que 
permitirá ao aluno, técnicas adicionais às já 
estudadas na unidade anterior, 
possibilitando assim lidar com operações 
lógicas mais complexaslógicas mais complexas.
Operações adicionais sobre 
proposições
Implicação lógica:
 Definição: Uma proposição P (p, q, r,...) 
implica logicamente uma proposição 
Q (p, q, r,...) se Q (p, q, r,...) é verdadeira 
todas as vezes que P (p, q, r,...) for 
verdadeira.
Operações adicionais sobre 
proposições
Implicação lógica:
 Definição: Uma proposição P (p, q, r,...) 
implica logicamente uma proposição 
Q (p, q, r,...) se Q (p, q, r,...) é verdadeira 
todas as vezes que P (p, q, r,...) for 
verdadeira.
 Notação: 
P (p, q, r,...) ֜ Q (p, q, r,...)
Operações adicionais sobre 
proposições
Exemplo de implicação lógica:
A tabela-verdade da proposição 
(p ש q) ר ~ p:
Operações adicionais sobre 
proposições
Exemplo de implicação lógica:
A tabela-verdade da proposição 
(p ש q) ר ~ p:
Operações adicionais sobre 
proposições
Exemplo de implicação lógica:
A tabela-verdade da proposição 
(p ש q) ר ~ p:
Essa proposição é verdadeira somente naEssa proposição é verdadeira somente na 
linha 3 e, nessa mesma linha, a proposição 
“q” também é verdadeira.
Então: (p ש q) ר ~p ֜ q
Operações adicionais sobre 
proposições
Propriedades da implicação lógica.
Reflexiva: 
 P (p, q, r,...) ֜ P (p, q, r,...)
Operações adicionais sobre 
proposições
Propriedades da implicação lógica.
Reflexiva:
 P (p, q, r,...) ֜ P (p, q, r,...)
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,...)
Operações adicionais sobre 
proposições
Exemplo de implicação lógica:
A tabela-verdade da proposição p ר q, p ש q, 
p ↔ q é:
Operações adicionais sobre 
proposições
Exemplo de implicação lógica:
A tabela-verdade da proposição p ר q, p ש q, 
p ↔ q é:
Operações adicionais sobre 
proposições
Exemplo de implicação lógica:
A tabela-verdade da proposição p ר q, p ש q, 
p ↔ q é:
A proposição p ר q é verdadeira somente naA proposição p ר q é verdadeira somente na 
linha 1 e, nessa linha, as proposições p ש q 
e p ↔ q também são verdadeiras.
Logo, a primeira proposição implica cada 
uma das outras duas proposições.
Operações adicionais sobre 
proposições
Exemplo de implicação lógica.
Em símbolos:
p ר q ֜ p ש q 
e
p ר q ֜ p ↔ q
Operações adicionais sobre 
proposições
Tautologias e implicação lógica.
A proposição P (p, q, r,...) implica a 
proposição Q (p, q, r,...), isto é: 
 P (p, q, r,...) ֜ Q (p, q, r,...)
Se e somente se a condicional:Se, e somente se, a condicional:
 P (p, q, r,...) → Q (p, q, r,...) é tautológica.
Operações adicionais sobre 
proposições
Tautologias e implicação lógica.
A toda implicação lógica corresponde uma 
condicional tautológica e vice-versa.
(ALENCAR FILHO, 2002).
Operações adicionais sobre 
proposições
Observação
Os símbolos (→) e (֜) são distintos.
(→) é de operação lógica.
Aplicado às proposições p e q, dá a nova 
proposição P: p qproposição P: p → q.
Operações adicionais sobre 
proposições
Observação
Os símbolos (→) e (֜) são distintos.
(֜) é de relação.
Estabelece que a condicional P (p, q, r,...) → 
Q (p q r ) é tautológicaQ (p, q, r,...) é tautológica.
Operações adicionais sobre 
proposições
Equivalência lógica:
 Definição: Uma proposição P (p, q, r,...) é 
logicamente equivalente ou apenas 
equivalente a uma proposição Q (p, q, 
r,...) se as tabelas-verdade dessas duas 
proposições são idênticas.
 Notação 
P (p, q, r,...) ֞ Q (p, q, r,...)
Operações adicionais sobre 
proposições
Propriedades da equivalência lógica
Reflexiva:P (p, q, r,...) ֞ P (p, q, r,...)
Simétrica:
 Se P (p, q, r,...) ֞ Q (p, q, r,...) então
 Q (p, q, r,...) ֞ P(p, q, r,...)
Transitiva:
 Se P (p, q, r,...) ֞ Q (p, q, r,...) e
 Q (p, q, r) ֞ R (p, q, r,...) então
P ( ) R ( ) P (p, q, r) ֞ R (p, q, r,...)
Operações adicionais sobre 
proposições
Exemplos de equivalência lógica:
As proposições ~~p e p são equivalentes, 
isto é, ~~p ֞ p (regra da dupla negação).
É o que demonstra a tabela-verdade:
Operações adicionais sobre 
proposições
Exemplos de equivalência lógica:
As proposições ~p → p e p são 
equivalentes, isto é, ~p → p ֞ p é o que 
demonstra a tabela:
Operações adicionais sobre 
proposições
Exemplos de equivalência lógica:
A condicional p → q e a disjunção ~p ש q 
têm tabelas-verdade idênticas:
Operações adicionais sobre 
proposições
Tautologias e equivalência lógica:
A proposição P (p, q, r,...) é equivalente à 
proposição Q (p, q, r,...), isto é:
 P (p, q, r,...) ֞ Q (p, q, r,...)
Se e somente se a bicondicional:Se, e somente se, a bicondicional:
 P (p, q, r,...) ↔ Q (p, q, r,...) é tautológica.
Operações adicionais sobre 
proposições
Observação:
Os símbolos ↔ e ֞ são distintos.
(↔) é de operação lógica.
Aplicado às proposições p e q , dá a nova 
proposiçãoproposição.
Operações adicionais sobre 
proposições
Observação:
Os símbolos ↔ e ֞ são distintos.
(֞) é de relação.
Estabelece que a bicondicional
P (p , q, r,...) ↔ Q (p, q , r,...) é tautológica.
Interatividade
Qual das alternativas abaixo é tautológica?
a) p ר (p v q) ֞ p
b) (p → q) ר (q → p) ֞ (p ↔ q)
c) (~p v q) ר (~q v p) ֞ (p ↔ q)
d) p v (p ר q) ֞ p
e) Todas as alternativas anteriores estão 
corretas.
Operações adicionais sobre 
proposições
Proposições associadas a uma condicional:
Dada a condicional (p→q), chamam-se 
proposições associadas a (p→q) as três 
seguintes proposições condicionais que 
contêm p e q:
 Recíproca de p → q: q → p
 Contrária de p → q: ~p → ~q
 Contrapositiva de p → q: ~q → ~ p
Operações adicionais sobre 
proposições
Proposições associadas a uma condicional:
As tabelas-verdade dessas quatro 
proposições são:
Operações adicionais sobre 
proposições
Proposições associadas a uma condicional:
 A condicional: p → q
 E a sua contrapositiva ~q → ~p
São equivalentes.
 Ou seja: p → q ֞ ~q → ~p
Operações adicionais sobre 
proposições
Proposições associadas a uma condicional:
 A recíproca q → p
 E a contrária ~p → ~q
São equivalentes, ou seja:
 q → p ֞ ~p → ~q
Operações adicionais sobre 
proposições
Exemplos:
 Seja a condicional relativa a um 
quadrilátero Q:
 p → q: se Q é quadrado, então Q é 
retângulo.retângulo.
 A recíproca dessa proposição é:
 q → p: se Q é retângulo, então é 
quadrado.
Aqui, a condicional p → q é verdadeira, mas 
a sua recíproca q → p é falsa.
Operações adicionais sobre 
proposições
Exemplos:
 Seja a proposição relativa à lei de 
trânsito:
 p → q: Se eu bebo, então eu não 
dirijo.dirijo.
 A contrapositiva dessa proposição é:
 ~q → ~p: Se eu dirijo, então eu não 
bebo.
Aqui, a condicional p → q e a sua 
contrapositiva ~q → ~p são equivalentes e 
ambas verdadeiras.
Operações adicionais sobre 
proposições
Negação conjunta de duas proposições:
 A conjunção de duas proposições p e q 
negadas é a proposição “não p e não q”.
 Esse tipo de negação é denominado de 
negação conjunta.negação conjunta.
 Em símbolos: p ↓ q ֞ ~p ר ~ q
Operações adicionais sobre 
proposições
Tabela-verdade da negação conjunta 
“p ↓ q”:
Operações adicionais sobreproposições
Negação disjunta de duas proposições:
 A negação disjunta de duas proposições 
p e q é a proposição “não p ou não q”.
 Em símbolos: p ↑ q ֞ ~p v ~ q
Operações adicionais sobre 
proposições
Tabela-verdade da negação disjunta
“p ↑ q”:
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção:
Sejam p, q e r proposições simples 
quaisquer e sejam t e c proposições 
também simples, cujos valores lógicos 
respectivos são (V) verdadeiro e (F) falso.
Idempotente: p ר p ֞ p
Identidade: p ר t ֞ p e p ר c ֞ c
Associativa: (p ר q) ר r ֞ p ר ( q ר r)
Comutativa: p ר q ↔ q ר p
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção:
A demonstração da identidade pode ser 
feita com a construção da tabela-verdade e 
a verificação da tautologia.
p ר t֞ p e p ר c֞ cp ר t ֞ p e p ר c ֞ c
Propriedades das proposições e 
fundamentos da dedução
Propriedades da disjunção:
Sejam p, q e r proposições simples 
quaisquer e sejam t e c proposições 
também simples, cujos valores lógicos 
respectivos são V (verdadeiro) e F (falso).
Idempotente: p ש p ֞ p
Identidade: p ש t ֞ t e p ש c ֞ p
Associativa: (p ש q) ש r ֞ p ש (q ש r)
Comutativa: p ש q ֞ q ש p
Propriedades das proposições e 
fundamentos da dedução
Propriedades da disjunção:
A demonstração da propriedade associativa
pode ser feita com a construção da tabela-
verdade e a verificação da tautologia.
(p ש q) ש r֞ p ש (q ש r)(p ש q) ש r ֞ p ש (q ש r)
Propriedades das proposições e 
fundamentos da dedução
Propriedades da disjunção: (associativa)
(p ש q) ש r ֞ p ש (q ש r)
Interatividade
Qual das alternativas abaixo é tautológica:
a) p v q ֞ p v q
b) p v q ֞(p → q) ר (q → p)
c) p v q ֞ (p v q) ר ~(p ר q)
d) p v q ֞ p v (p ר q)
e) p v q ֞ p
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção e da disjunção:
 Sejam p, q e r proposições simples 
quaisquer.
Distributivas:
 p ר (q ש r)֞ (p ר q) ש (p ר r); p ר (q ש r) ֞ (p ר q) ש (p ר r);
 p ש (q ר r) ֞ (p ש q) ר (p ש r);
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção e da disjunção:
 Sejam p, q e r proposições simples 
quaisquer.
Distributivas:
 p ר (q ש r)֞ (p ר q) ש (p ר r); p ר (q ש r) ֞ (p ר q) ש (p ר r);
 p ש (q ר r) ֞ (p ש q) ר (p ש r);
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção e da disjunção:
p ר (q ש r) ֞ (p ר q) ש (p ר r);
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção e da disjunção:
 Sejam p, q e r proposições simples 
quaisquer.
Absorção:
 p ר (p ש q)֞ p p ר (p ש q) ֞ p
e
 p ש (p ר q) ֞ p
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção e da disjunção:
 Sejam p e q proposições simples 
quaisquer.
Regras de Morgan:
 ~ (p ר q)֞ ~ p ש ~q; ~ (p ר q) ֞ ~ p ש ~q;
 ~(p ש q) ֞ ~ p ר ~q.
Propriedades das proposições e 
fundamentos da dedução
Propriedades da conjunção e da disjunção:
~ (p ר q) ֞ ~ p ש ~q
Propriedades das proposições e 
fundamentos da dedução
Negação da condicional:
Como:
p → q ֞ ~ p ש q,
Negando-se a condicional, tem-se:
~(p → q ) ֞
֞ ~ (~p ש q ) ֞
֞ ~~p ר ~q ֞
֞ p ר ~q
Propriedades das proposições e 
fundamentos da dedução
Negação da bicondicional:
Como:
p ↔ q ֞ (p → q) ר (q → p), então,
p ↔ q ֞ (~p ש q) ר (~q ש p)
Negando-se a bicondicional, tem-se:
~(p ↔ q) ֞ ~[(~p ש q) ר (~q ש p)]
~(p ↔ q) ֞ ~(~p ש q) ש ~(~q ש p)
~(p ↔ q) ֞ (p ר ~q) ש (q ר ~p)
Interatividade 
Das proposições compostas abaixo:
I. - (p → q) ֞ (~p v q)
II. - (p ↔ q) ֞ (p → q) ר (q → p)
III. - (p v q) ֞ ~(p ↔ q)
a) As alternativas I e II são verdadeiras.
b) As alternativas I e III são verdadeiras.
c) As alternativas II e III são verdadeiras.
d) As alternativas I, II e III são verdadeiras.d) s a te at as , e são e dade as
e) As alternativas I, II e III são falsas.
Método dedutivo
Para auxílio nas demonstrações, serão 
realizadas as seguintes suposições:
 Serão dadas as proposições simples p, 
q, r, a proposição t sempre é verdadeira 
e a proposição c é sempre falsa. 
 Elas serão substituídas, 
respectivamente, por proposições 
compostas P, Q, R; T (tautologia) e C 
(contradição) quando for o caso.
Método dedutivo
Demonstrar as implicações:
 c ֜ p; (c → p é tautológica)
 p ֜ t; (p → t é tautológica)
Onde p é uma proposição qualquer, c e t 
são proposições cujos valores lógicossão proposições cujos valores lógicos 
respectivos são F e V.
 V(c) = F 
 V(t) = V
Método dedutivo
Demonstração:
 Sabe-se, que p → q e ~p ש q são 
proposições equivalentes.
 Uma implicação é verdadeira se a 
condicional é tautológica.condicional é tautológica.
 Se provamos que a condicional referente 
à implicação é tautológica, então 
provamos que a proposição é válida.
Método dedutivo
Demonstração:
p → q ֞ ~p ש q;
V(c) = F;
V(t)=V
Então:
c → p ֞ ~c ש p ֞ t ש p ֞ t (cqd)
p → t ֞ ~p ש t ֞ t (cqd)
Método dedutivo
Demonstração:
Método dedutivo
Demonstrar a implicação
p ר q ֜ p (simplificação)
Demonstração:
p ר q → p ֞
֞ ~(p ר q) ש p ֞
֞ (~p ש ~q) ש p ֞
֞ (~p ש p) ש ~ q ֞
֞ T ש ~q ֞
T֞ T
Método dedutivo
Demonstrar a implicação
p ֜ p ש q (adição).
Demonstração:
p → p ש q ֞
֞ ~ p ש (p ש q) ֞
֞ (~ p ש p) ש q ֞
֞ T ש q ֞
֞ T
Método dedutivo
Demonstrar a implicação
(p → q) ר p ֜ q (modus ponens)
Demonstração:
(p → q) ר p ֞
֞ p ר (~ p ש q) ֞
֞ (p ר ~p) ש (p ר q) ֞
֞ C ש (p ר q) ֞
֞ p ר q ֜ q
Redução do número de conectivos
Conectivos fundamentais: (~, ר, ש, →, ↔)
Demonstra-se que é possível que três deles 
podem ser expressos em termos de apenas 
dois dos seguintes pares:
~ e ש e ש
~ e ר
~ e →
Redução do número de conectivos
Demonstração:
ר, → e ↔ em função de ~ e ש:
p ר q ֞
֞ ~~ p ר ~~ q ֞
֞ ~ (~ p ש ~ q)
p → q ֞ ~p ש q
p ↔ q ֞
֞ (p → q) ר (q → p) ֞
( ) ( ))֞ ~(~ p ש q) ש ~( ~q ש q))
Redução do número de conectivos
Demonstração:
ש, → e ↔ em função de ~ e ר:
p ש q ֞ ~~p ש ~~q ֞ ~(~p ר ~ q)
p → q ֞ ~p ש q ֞ ~(p ר ~q)
p ↔ q ֞
֞ (p → q) ר (q → p) ֞
֞ ~(p ר ~q) ר~(~p ר q)
Forma normal das proposições
Definição:
 Uma proposição está na forma normal 
(FN) se, e somente se, a proposição 
contém apenas os conectivos ~, ר e ש.
Observação:Observação:
 Toda proposição pode ser levada para 
uma FN equivalente pela redução do 
número de conectivos.
Princípio de dualidade
Princípio de dualidade: 
 Se P e Q são proposições equivalentes 
que só contêm os conectivos ~, ר e V, 
então as suas duais respectivas P1 e Q1
também são equivalentes.
Exemplo:
 Como p ר (p ש q) ֞ p
 Então p ש (p ר q) ֞ p
 (pelo princípio da dualidade)
Interatividade
Qual das alternativas abaixo não é 
tautológica:
a) (p → q) ר ~ q → ~p
b) (p ש q) ר ~p → q
c) p ר q p ש qc) p ר q → p ש q
d) (p → q) → (p ר r) → q
e) p ר q ↔ p ש q
ATÉ A PRÓXIMA!