Regras e Estruturas Lógicas

Prévia do material em texto

Prof. João Giardulli
UNIDADE II
Lógica
 Apresentar regras e estruturas adicionais sobre o uso de proposições.
 Conceituar implicação lógica 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.
Objetivo
 Nesta unidade, serão apresentados temas mais avançados sobre proposições, o que 
permitirá ao aluno conhecer técnicas adicionais às já estudadas na unidade anterior, 
possibilitando assim lidar com operações lógicas mais complexas.
Introdução
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
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
Exemplo de implicação lógica
A tabela-verdade da proposição (p ∨ q) ∧ ~ p:
 Essa 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
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
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:
SeP (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
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:
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 → 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ó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 (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
p ~p ~~p
V F V
F V F
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
p ~p ~p → p
V F V
F V F
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
p q p →q ~p ~p ˅ q
V V V F V
V F F F F
F V V V V
F F V V V
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
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çã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.
Operações Adicionais sobre Proposições
Qual das afirmações abaixo é verdadeira?
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 anteriores
Interatividade 
Qual das afirmações abaixo é verdadeira?
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 anteriores
Resposta 
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
p q p →q q→p ~p→ ~q ~q→ ~p
V V V V V V
V F F V V F
F V V F F V
F F V V V V
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
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.
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.
Em símbolos: p ↓ q ⇔ ~p ∧ ~ q
Operações Adicionais sobre Proposições
Tabela-verdade da negação conjunta “p ↓ q”:
Operações Adicionais sobre Proposições
p q p ↓q
V V F
V F F
F V F
F F V
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”:
Operações Adicionais sobre Proposições
p q p ↑q
V V F
V F V
F V V
F F V
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 ⇔ c
Propriedades das Proposições e Fundamentos da Dedução
p t c p ˄ t p ˄ cp ˄ t ↔ p p ˄ c ↔ c
V V F V F V V
F V F F F V V
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)
Propriedades das Proposições e Fundamentos da Dedução
Propriedades da disjunção: (associativa)
(p ∨ q) ∨ r ⇔ p ∨ (q ∨ r)
Propriedades das Proposições e Fundamentos da Dedução
p q r p ˅ q (p ˅ c) ˅ r q ˅ r p ˅ (q ˅ r)
V V V V V V V
V V F V V V V
V F V V V V V
V F F V V F V
F V V V V V V
F V F V V V V
F F V F V V V
F F F F F F F
Qual das alternativas abaixo é verdadeira?
a) p v q ⇔ p ∧ q
b) p v q ⇔(p → q) ∧ (q → p)
c) p v q ⇔ ~p → q
d) p v q ⇔ p v (p ∧ q)
e) p v q ⇔ p
Interatividade 
Qual das alternativas abaixo é verdadeira?
a) p v q ⇔ p ∧ q
b) p v q ⇔(p → q) ∧ (q → p)
c) p v q ⇔ ~p → q
d) p v q ⇔ p v (p ∧ q)
e) p v q ⇔ p
Resposta
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);
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);
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
p q r q ˄ r p ˅ (q ˄ r) p ˅ q p ˅ r (p ˅ q) ˄ (p ˅ r)
V V V V V V V V
V V F F V V V V
V F V F V V V V
V F F F V V V V
F V V V V V V V
F V F F F V F F
F F V F F F V F
F F F F F F F F
Propriedades da conjunção e da disjunção:
 Sejam p, q e r proposições simples quaisquer.
Absorção:
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.
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
p q p ˄ q ~ (p ˄ q) ~ p ~ q ~ p ˅ ~q
V V V F F F F
V F F V F V V
F V F V V F V
F F F V F V V
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)
Propriedades das Proposições e Fundamentos da Dedução
Das equivalências abaixo:
I. - (p → q) ⇔ (~p v q)
II. - (p ↔ q) ⇔ (p → q) ∧ (q → p)
III. - (p v q) ⇔ ~(p ↔ q)
a) As afirmativas I e II são verdadeiras.
b) As afirmativas I e III são verdadeiras.
c) As afirmativas II e III são verdadeiras.
d) As afirmativas I, II e III são verdadeiras.
e) As afirmativas I, II e III são falsas.
Interatividade 
Das equivalências abaixo:
I. - (p → q) ⇔ (~p v q)
II. - (p ↔ q) ⇔ (p → q) ∧ (q → p)
III. - (p v q) ⇔ ~(p ↔ q)
a) As afirmativas I e II são verdadeiras.
b) As afirmativas I e III são verdadeiras.
c) As afirmativas II e III são verdadeiras.
d) As afirmativas I, II e III são verdadeiras.
e) As afirmativas I, II e III são falsas.
Resposta 
 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ó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;
 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
p c t c → p p → t
V F V V V
F F V V V
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
Método Dedutivo
Demonstrar a implicação
p ⇒ p ∨ q (adição).
Demonstração:
p → p ∨ q ⇔
⇔ ~ p ∨ (p ∨ q) ⇔
⇔ (~ p ∨ p) ∨ p ⇔
⇔ 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
Método Dedutivo
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 →
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)
Redução do número de conectivos
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:
Toda proposição pode ser levada para uma FN equivalente pela redução do número 
de conectivos.
Forma normal das proposições
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)
Princípio de dualidade
Qual das alternativas abaixo não é tautológica?
a) (p → q) ∧ ~ q → ~p
b) (p ∨ q) ∧ ~p → q
c) p ∧ q → p ∨ q
d) (p → q) → (p ∧ r) → q
e) p ∧ q ↔ p ∨ q
Interatividade 
Qual das alternativas abaixo não é tautológica?
a) (p → q) ∧ ~ q → ~p
b) (p ∨ q) ∧ ~p → q
c) p ∧ q → p ∨ q
d) (p → q) → (p ∧ r) → q
e) p ∧ q ↔ p ∨ q
Resposta
ATÉ A PRÓXIMA!