Slides Aula 3 Raciocínio Lógico

Prévia do material em texto

Raciocínio Lógico
Prof. André Roberto Guerra
Aula 3
Organização da Aula
Proposições compostas
• Tautologia 
• Contradições 
• Contingências
Propriedades Semânticas
• Propriedades semânticas básicas da Lógica Proposicional (LP):
• Tautologia
• Contradição
• Contingência
• Tautologia (ou fórmula válida)
• Uma fórmula A é uma tautologia, se, e somente se, para toda
interpretação I, 
I[A] = V
Tautologia
• Tautologia é toda proposição composta cujo conjunto resposta da tabela-
verdade é formado em sua totalidade por V (verdadeiro)
� Em outros termos, é toda proposição
composta por 
P (p, q, r, …) cujo valor lógico é sempre
V (verdade), quaisquer sejam os 
valores lógicos das proposições simples 
componentes
p, q, r, …
• É imediato que as proposições p → p e p ↔ p são tautológicas (princípio de 
identidade para as proposições)
• Exemplo: A proposição
“~(p ^ ~p)” (princípio da não contradição) é tautologia, conforme 
mostra a sua tabela-verdade:
• Portanto, dizer que uma proposição não pode ser simultaneamente
verdadeira e falsa é sempre verdadeiro
p ~p p ^ ~p ~(p ^ ~p)
V F F V
F V F V
p ~p p v ~p
V F V
F V V
� A proposição “p v ~p” 
(princípio do terceiro
excluído) é tautologia, como 
comprovado na tabela-verdade
• Portanto, o conceito de que 
uma proposição ou é 
verdadeira ou é falsa é válido
• Uma fórmula A é insatisfazível (insatisfatível) ou uma contradição 
(contraválida), se, e somente se, para toda interpretação I, I[A] = F
Contradição
• Contradição é toda proposição composta cujo conjunto resposta da tabela-
verdade é formado em sua totalidade por F (falso)
� Em outros termos, é toda proposição
composta 
P(p, q, r, …) cujo valor lógico é sempre
F (falso), quaisquer sejam os valores 
lógicos das proposições simples 
componentes p, q, r, …
• Como a tautologia é sempre verdadeira (V), a negação de uma tautologia
é sempre falsa (F), ou seja, é uma contradição, e vice-versa
• Portanto, dizer que uma proposição pode ser simultaneamente
verdadeira e falsa é sempre falso
p ~p p ^ ~p
V F F
F V F
� Exemplo: a proposição
“p ^ ~p”
� A proposição (p^q)^ ~(p v q) é 
uma contradição como 
comprovado na 
tabela-verdade:
p q p ^ q p v q ~(p v q) (p ^ q) ^ ~(p v q)
V V V V F F
V F F V F F
F V F V F F
F F F F V F
� Uma fórmula A é uma contingência se, e somente se, os valores do seu conjunto 
resposta são diferentes entre si
Contingência
• Em outros termos, é toda proposição composta 
P(p, q, r, …) cujo valor lógico é alternado entre V (verdadeiro) e F (falso), 
quaisquer sejam os valores lógicos das proposições simples componentes p,
q, r, …
• Simplificando, contingência é toda proposição composta cujo conjunto 
resposta
• não é tautologia e 
• não é contradição
� A proposição ~(p v q) é uma
contingência como comprovado
na tabela-verdade
p q p v q ~(p v q)
V V V F
V F V F
F V V F
F F F V
� Uma fórmula A é falsificável, se, e somente se, os valores do seu conjunto resposta 
são F (falsos)
• A fórmula sob a condição de contradição também é falsificável
Propriedades Semânticas LP
� Uma fórmula A é satisfazível, se, e somente se, os valores do seu conjunto resposta 
são V (verdade)
• A fórmula sob a condição de tautologia também é satisfazível
Relações entre fórmulas da LP
• Toda fórmula válida (tautologia) é satisfazível
• Toda fórmula contraditória (insatisfazível) é falsificável
• Uma fórmula não pode ser satisfazível e contraditória
• Uma fórmula não pode ser uma tautologia e falsificável
• Se A é uma tautologia, então ~A é contraditória
• Se A é contraditória, então, ~A é uma tautologia
• Se A é satisfazível, então ~A é falsificável, e vice-versa
• Há fórmulas que são tanto satisfazíveis quanto falsificáveis, i.e., são 
contingências ou fórmulas indeterminadas
• Curiosidade
• A classificação de fórmulas extensas não é um processo trivial
• Um dos grandes desafios da computação é encontrar métodos (algoritmos) 
eficientes para decidir se uma fórmula é:
• satisfazível — falsificável
• contradição — tautologia
Classificação de Fórmula LP
Falsificável
Contradição
0 0
0 0 0
0 0 00
0
0
0
00
00
0
0
00 0
0
0 0
0
0
0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
00
0
0
0
00
0 0
0
0
00
0
0
0
0
0
0
0
0
000
0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0 0
0
0
0
0
0 0
0
Satisfazível
Tautologia
1
1
111
1
1
1
1 1
1 1
1 1
1
1
1
1 11
1 1 1 11
1
1
1
1
1
1
1
1 1
1
1
1
1 1
1
1
1
1 1
11
1
1 1
1
1
1
11
1
1
1
11
1
1
1
1
11
1
1
1
1
1
1
1
1
1
1
1
1
1
1
0 10
0 0 0
0 0 00
0
0
0
00
00
0
0
00 0
0
0 0
0
0
0
0
0
0 0
0
0
0
0
0
0
0
0
0
0
0
0
0
00
0
0
0
00
0 0
0
0
00
0
0
0
0
0
0
0
0
0
000
0
0
0
0 0
0
1
111
1
1
1
1 1
1 1
1 1
1
1
1
1 11
1 1 1 11
1
1
1
1
1
1
1
1 1
1
1
1
1 1
1
1
1
1 1
11
1
1 1
1
1
1
11
1
1
1
1
1
1
1
1
11
1
1
1
1
0
0
00
0
0 0
0
00
0
0
0 0
0
1
1
1
1
1Contradição Tautologia
Falsificável Satisfazível
C
o
n
t
i
n
g
ê
n
c
i
a
Síntese
Raciocínio Lógico
• Propriedades semânticas básicas da Lógica Proposicional (LP)
• Tautologia
• Contradição
• Contingência
• Satisfazível
• Falsificável
Referências de Apoio
• SANT'ANNA, A. S. O que é um Axioma. Capítulo 3. Barueri: Editora Manoele, 
2003.
Site para consulta
� Noções de Lógica Matemática — PUC–SP. Disponível em: 
<http://www.pucsp.br/~logica/>.