Aula 16 setembro

Prévia do material em texto

30/9/2008
1
1
O que é Lógica
Tarefa do lógico
Um argumento ocorre somente quando se pretende 
sustentar ou provar uma conclusão a partir de um 
conjunto de premissas.
Quando ocorre um argumento
Distinguir os argumentos 
corretos dos incorretos
Suas premissas e conclusões
2
O que é Lógica
As crianças nem sempre sabem cuidar de si mesmas. Logo, 
é preciso que alguém se responsabilize por elas.
“O mau humor consegue dominar sua consciência quando 
você está num estado mental negativo ou passivo. Portanto, 
pensamento positivo é o melhor antídoto contra o mau 
humor.” Yogananda
• Indicadores de conclusão
– portanto, logo, daí, assim, por isso, conseqüentemente
• Indicadores de premissas
– porque, desde que, como, dado que
30/9/2008
2
3
O que é Lógica
Proposição 1
Proposição 2
Proposição n
Proposição X
.
.
.
Argumento
Premissas
(verdadeiras)
ConclusãoProcesso de 
Inferência
4
O que é Lógica
Proposições
•Todas as baleias são mamíferos (P1)
•Todos os mamíferos têm pulmões (P2)
•Portanto, todas as baleias têm pulmões (Q)
ArgumentosVerdadeiras
Falsas
Válidos
Inválidos
A1
verdadeira
verdadeira
Inferida a partir 
de P1 e P2
A1 é um 
argumento 
válido
P1
P2
Q
30/9/2008
3
5
O que é Lógica
• Todas as aranhas têm 6 patas (P1)
• Todos os seres de 6 patas têm asas (P2)
• Portanto, todas as aranhas têm asas (Q)
A2
A2 é um argumento ?
A2 é um argumento válido?
A validade de um argumento não determina a verdade da conclusão
6
O que é Lógica
A3
• Se eu possuísse todo o ouro do mundo, seria muito 
rico (P1)
• Eu não possuo todo o ouro do mundo (P2)
• Portanto, não sou muito rico (Q)
A3 é um argumento ?
A3 é um argumento válido?
• Se Bill Gates possuísse todo o ouro do mundo, 
seria muito rico (P1)
• Bill Gates não possui todo o ouro do mundo (P2)
• Portanto, Bill Gates não é muito rico (Q)
30/9/2008
4
7
� Para ser um argumento válido, se as premissas 
forem verdadeiras, a conclusão, obrigatoriamente, 
tem que ser verdadeira
� A verdade ou falsidade da conclusão não determina 
a validade ou invalidade do argumento
� A validade do argumento determina a verdade da 
conclusão, se as premissas forem verdadeiras
O que é Lógica
8
� Determinar a verdade ou falsidade das 
premissas, é uma tarefa da ciência em geral
� O lógico está interessado nas relações lógicas
entre as proposições
O que é Lógica
Determinam a correção ou 
incorreção dos argumentos
30/9/2008
5
9
� Determinar a correção ou incorreção dos raciocínios está 
dentro do domínio da lógica
� Até mesmo daqueles argumentos cujas premissas podem ser 
falsas 
� No nosso dia a dia, calculamos as conseqüências de cada uma 
das diferentes opções que temos
O que é Lógica
Supomos premissas (que poderão ser falsas ou 
verdadeiras) e avaliamos suas conclusões
Raciocinar corretamente é fundamental
10
Tipos de Raciocínio Lógico
Os argumentos estão, tradicionalmente, divididos em:
Dedutivos e Indutivos
Todo argumento implica a 
pretensão de que suas 
premissas forneçam a prova 
da verdade da conclusão
Somente o argumento dedutivo
envolve a pretensão de que 
suas premissas fornecem uma 
prova conclusiva
Um raciocínio dedutivo é válido quando suas premissas, se 
verdadeiras, fornecem provas convincentes para a conclusão
É impossível que as premissas sejam 
verdadeiras se a conclusão for falsa
30/9/2008
6
11
Tipos de Raciocínio Lógico
Lógica Dedutiva
Tem como tarefa esclarecer a 
natureza da relação entre as 
premissas e a conclusão
Discriminar os argumentos 
válidos dos inválidos
Envolve a pretensão de que suas premissas forneçam 
algumas provas da verdade da conclusão, mas não 
necessariamente convincentes
Raciocínio Indutivo
VÁLIDOS ou INVÁLIDOS
MELHORES ou PIORES
MAIS PROVÁVEIS ou MENOS PROVÁVEIS
12
Tipos de Raciocínio Lógico
Indução
As premissas não implicam logicamente a conclusão, mas, se forem 
verdadeiras, há uma probabilidade de que a conclusão também o seja
Um argumento indutivo é bom se tal probabilidade é alta
Exemplo de indução:
No dia 1 de março houve uma chuva muito forte na cidade. Várias ruas 
foram observadas e estavam bastante congestionadas, dentre elas a 
Vasco da Gama, a Paralela, o Vale do Ogunjá, a Garibaldi e a Avenida 
ACM. Concluiu-se que todas as grandes avenidas da cidade estavam com 
um trânsito caótico. 
30/9/2008
7
13
Tipos de Raciocínio Lógico
Prática: Distinguir os argumentos indutivos e dedutivos:
1. Como os testes demonstraram que foram precisos, pelo menos 2,3 
segundos para manobrar a culatra do rifle de Oswald, é óbvio que 
Oswald não poderia ter disparado 3 vezes - atingindo Kennedy 2 
vezes e Connally 1 vez - em 5,6 segundos ou menos.
2. Não acreditamos que José tenha possuído, em qualquer altura, 
uma considerável soma em títulos ou outros valores, pois nunca 
pareceu um homem rico,e ao morrer, deixou poucos bens.
3. A nenhum homem é consentido ser juiz em causa própria; porque 
seu interesse certamente influirá em seu julgamento, e corromperá 
a sua integridade.
(Copi)
14
Tipos de Raciocínio Lógico
Raciocínio Abdutivo
•Conceito muito próximo da indução, ambas (indução e 
abdução) formulam julgamentos (conclusões) a partir de 
premissas
•Ambas levam à aceitação de uma hipótese porque os fatos 
observados são exatamente aqueles que provavelmente 
resultariam como conseqüência daquela hipótese 
FATO 1
FATO 2
...
FATO n
HIPÓTESE
Indução Abdução
30/9/2008
8
15
Tipos de Raciocínio Lógico
� A indução inicia de uma hipótese e persegue os 
fatos
HIPÓTESE FATOS
� A abdução inicia a partir dos fatos e persegue uma 
hipótese
FATOS HIPÓTESE
� A abdução é a inferência que segue do efeito para a 
causa; a finalidade é fornecer explicação para fatos 
observados, considerando-se um conhecimento prévio 
(background)
16
Tipos de Raciocínio Lógico
� Todos os feijões deste saco são brancos (regra)
� Estes feijões provêm deste saco (caso)
� Estes feijões são brancos (resultado)
� Estes feijões provêm deste saco (caso)
� Estes feijões são brancos (resultado)
� Todos os feijões deste saco são brancos (regra)
� Todos os feijões deste saco são brancos (regra)
� Estes feijões são brancos (resultado)
� Estes feijões provêm deste saco (caso)
Dedução
Indução
Abdução
30/9/2008
9
17
Tipos de Raciocínio Lógico
� Todo homem é mortal (regra)
� Sócrates é homem (caso)
� Sócrates é mortal (resultado)
� Sócrates é homem (caso)
� Sócrates é mortal (resultado)
� Todo homem é mortal (regra)
� Todo homem é mortal (regra)
� Sócrates é mortal (resultado)
� Sócrates é homem (caso)
Dedução
Indução
Abdução
18
Tipos de Raciocínio Lógico
� Pessoa A apresenta sintoma X (resultado)
� Pessoa A tem doença 1 (caso)
� Pessoa B apresenta sintoma X (resultado)
� Pessoa B tem doença 1 (caso)
� Pessoa C apresenta sintoma X (resultado)
� Pessoa C tem doença 1 (caso)
....
� Doença 1 apresenta sintoma X (regra)
Indução
Cria as regras
30/9/2008
10
19
Tipos de Raciocínio Lógico
� Doença 1 apresenta sintoma X (regra) 
� Pessoa A apresenta sintoma X (resultado)
� Doença 1 apresenta sintoma Y (regra)
� Pessoa A apresenta sintoma Y (resultado)
� Doença 1 apresenta sintoma Z (regra) 
� Pessoa A apresenta sintoma Z (resultado)
....
� Pessoa A tem doença 1 (caso)
Abdução
Faz suposições a partir das regras
20
Tipos de Raciocínio Lógico
� Doença 1 apresenta sintoma W (regra) 
� Pessoa A tem doença 1 (caso)
� Pessoa A tem sintoma W (resultado)
....
� Já que a pessoa A não tem sintoma W, a hipótese da 
pessoa A ter a doença 1 não pode ser confirmada.Dedução
Elimina as impossibilidades testando as hipóteses
30/9/2008
11
21
Tipos de Raciocínio Lógico
Na lógica clássica, dedutiva, as inferências tidas como válidas 
denominam-se dedução, as inferências não dedutíveis são chamadas 
paralogismos
•Ciência � vasto sistema conceitual que nos permite, 
entre outras coisas, sistematizar o real
•Dado um sistema conceitual de categorias, em geral, 
tem-se uma lógica associada a ele
Determinar as inferências válidas relativas ao sistema considerado
22
� A dedução é utilizada para se obter as 
conseqüências de uma teoria ou hipótese
� A importância dos paralogismos e das 
lógicas não clássicas (heterodoxas)
� na vida cotidiana
� quando se faz suposições
� grande parte das inferências do dia a dia
� nas ciências empíricas
� quando se formulam leis e teorias
� quando se faz avançar a ciência
Tipos de Raciocínio Lógico
30/9/2008
12
23
� A importância da indução
� o conhecimento só pode ser gerado através de 
fatos observáveis e suas conseqüências
� grande relação com probabilidade
� as teorias propostas são classificadas com um 
certo grau de possibilidade
� O processo de indução
� coleta fatos
� constrói uma teoria
� tenta comprová-la (em certo grau) a partir de 
novos fatos
Tipos de Raciocínio Lógico
24
Noções de Conseqüência Lógica
Uma proposição (ou fórmula) é conseqüência lógica
de um conjunto de proposições se esse conjunto
implica logicamente a proposição em questão
• Todas as baleias são azuis (A)
• Mobby Dick é uma baleia (B)
• Então, Mobby Dick é azul (C)
Se A e B são verdade,
eu posso garantir C
C é conseqüência 
lógica de A e B
A conclusão de um argumento é conseqüência lógica de suas premissas 
(LÓGICA DEDUTIVA)
30/9/2008
13
25
Lógica como um Sistema Formal 
Porque não usar a linguagem natural ?
� A linguagem natural é tão rica que não pode ser 
descrita formalmente
� Ambigüidade
� Não é concisa
� A compreensão depende do contexto
Objetivo da lógica formal:
• Formalizar um raciocínio e verificar sua validade
• Formalizar o conceito de prova e conseqüência lógica
Preocupação 
do 
lógico
26
Lógica como um Sistema Formal 
Precisamos de uma linguagem cuja sintaxe possa ser 
completamente descrita em poucas regras e cuja 
semântica possa ser definida sem ambigüidade
Sistema de Provas ou Sistema Dedutivo 
Construir provas ou refutações
Mostrar que uma fórmula é inconsistente
Proposição em linguagem formal
(Galier)
30/9/2008
14
27
Lógica como um Sistema Formal 
São hipóteses que são 
aceitas sem prova 
Formular um conjunto de fatos chamados axiomas e um 
conjunto de regras de dedução (regras de inferência)
Objetivo:
determinar quais fatos seguem dos axiomas e 
das regras de inferência
Esquece-se o significado e preocupa-se apenas com a 
possibilidade de construir provas ou refutações
(Galier)
28
Lógica como um Sistema Formal 
“Na matemática, é impossível provar todas as leis. As primeiras leis 
que são aceitas não podem ser provadas, já que não há leis 
anteriores a partir das quais se possa construir uma prova” 
(Shoenfield)
O uso de uma notação lógica formal não é peculiar à lógica moderna. O 
próprio Aristóteles (fundador da lógica na antigüidade) usou certas 
variáveis para facilitar o trabalho (Copi)
30/9/2008
15
29
Lógica como um Sistema Formal 
A substituição dos números romanos 
pelos números árabes 
A verdadeira vantagem se encontra 
no cálculoA formalização da lógica
Facilita imensamente a derivação de inferências e a 
avaliação de argumentos
(Copi)
30
Lógica como um Sistema Formal 
A lógica formal é o estudo das formas de argumentos , modelos abstratos 
comuns a muitos argumentos distintos
Se P então Q ou
Q porque P ou
P →→→→ Q
(Nolt)
Forma típica:
P e Q podem ser substituídos por qualquer par 
de proposições para formar um argumento 
(generalizações)
30/9/2008
16
31
Lógica como um Sistema Formal 
Conectivos Lógicos:
∧ e (conjunção)
∨ ou (disjunção)
~ não (negação)
→ implica (implicação)
•Hoje é segunda-feira
•Hoje não é terça-feira
•Hoje é segunda-feira ou terça-feira
A
~B
A ∨ B
Proposições:
Letras maiúsculas : A, B, C, ...
P, Q, R ....
32
Lógica como um Sistema Formal
Prática: Interprete a letra C como “Está chovendo” e a letra N 
como “Está nevando”, e formalize as seguintes sentenças:
1. Está chovendo.
2. Não está chovendo.
3. Está chovendo ou nevando.
4. Está chovendo e nevando.
5. Está chovendo mas não está nevando.
6. Não é o caso que está chovendo e nevando.
7. Se está chovendo, então não está nevando.
8. Não é o caso que se está chovendo não está nevando.
9. Ou está chovendo e nevando, ou está nevando mas não 
está chovendo
30/9/2008
17
33
Lógica como um Sistema Formal 
•Se T é um triângulo, então T é um polígono
de 3 lados
•T é um triângulo
•Logo, T é um polígono de 3 lados
•Se abril precede maio então maio segue abril
•Abril precede maio
•Então, maio segue abril
A → B
A
B
A → B
A
B
•Rembrandt pintou a Monalisa ou 
Michelangelo a pintou
•Rembrandt não pintou a Monalisa
•Logo, Michelangelo a pintou
A ∨ B
~A
B
34
Lógica e a Ciência da Computação
� Tradicionalmente, a lógica simbólica foi estudada com 
orientação filosófica e matemática
� Mas, ela pode também ser usada para representar 
problemas Ciência da Computação
F1: Se está quente e úmido, vai chover
F2: Se está úmido, então está quente
F3: Está úmido agora Vai Chover?
Formalizando:
F1: (P ∧ Q) → R
F2: Q → P
F3: Q
F4: R
Regras de inferência
(Chang e Lee)
30/9/2008
18
35
Lógica e a Ciência da Computação
Formalizando:
F1: P(Sócrates)
F2: (∀∀∀∀x)P(x) → Q(x) 
F4: Q(Sócrates)Regras de inferência
F1: Sócrates é homem
F2: Todo homem é mortal Sócrates é mortal?
P(x) : x é um homem
Q(x) : x é mortal
∀∀∀∀x : para todo x
Construção de uma prova de que uma fórmula é 
conseqüência lógica de outra
Teorema (Chang e Lee)
36
Lógica e a Ciência da Computação
A demonstração de que um teorema é verdade
Considera métodos automáticos de encontrar 
provas para teoremas
Prova do Teorema Prova Automática de Teoremas
• Os computadores são usados para processamentos complexos ou 
processamento de muitos dados
• Execução de tarefas chamadas inteligentes ==>Inteligência Artificial
• Responder perguntas (deduções lógicas)
• Provar teoremas
30/9/2008
19
37
Lógica e a Ciência da Computação
• Os fundamentos da prova automática de teoremas foi desenvolvido por 
Herbrand (1930) 
• Algoritmo de refutação - prova que a negação da fórmula é inconsistente
• Não existiam computadores - impossível de ser aplicado
• 1960 - Gilmore - primeira implementação do procedimento de Herbrand 
- ineficiente
• 1965 - Robinson propõe o Princípio da Resolução - mais eficiente
• Baseado nesse princípio é que foram implementados os provadores 
automáticos de teoremas
(Chang e Lee)
38
Lógica e a Ciência da Computação
• Sistemas de perguntas e respostas 
• fatos podem ser representados por fórmulas lógicas; 
então, para responder uma pergunta sobre fatos, nós 
provamos que uma fórmula correspondendo à resposta 
é derivável de fórmulas representando os fatos
• Análise de programas
• pode-se descrever a execução de um programa por 
uma fórmula A e a condição de que o programa termina 
por outra fórmula B. Verificar se aquele programa vai 
terminar é provar que B é conseqüência lógica de A
30/9/2008
20
39
Lógica e a Ciência da Computação
• Isomorfismo de grafos 
• Queremos saber se um grafo é isomorfo de outro grafo 
(ex. a estrutura de um componente orgânico). Os grafos 
podem ser descritos como fórmulas e o problema passa 
a ser provarque a fórmula que representa um grafo é 
conseqüência lógica da fórmula que representa o outro 
grafo.
• Especificação formal de sistemas
• busca inserir no processo de desenvolvimento de 
softwares uma etapa de especificação (estruturação do 
objetivo) utilizando uma linguagem formal (lógica 
matemática, teorias algébricas, teoria dos conjuntos, 
etc.) e derivar o sistema a partir de sua especificação 
provando que ele é correto (com relação à 
especificação)
40
Lógica Proposicional
• A lógica simbólica considera linguagens cujo propósito essencial é simbolizar o 
raciocínio
• A Lógica Proposicional - trata de sentenças declarativas (proposições) que 
podem ser verdadeiras (V) ou falsas (F), mas não ambas
(Casanova)
valor verdade da proposição
• A origem da Lógica Proposicional remota aos trabalhos de Boole e Morgan -
álgebra boleana - ligada a teorias matemáticas
• O enfoque da Lógica Proposicional como ferramenta para formalizar princípios 
lógicos se deve a Frege (Begriffsschrift)
30/9/2008
21
41
Lógica Proposicional
Proposições simples ou fórmulas atômicas ou átomos
• A neve é branca e o céu é azul
• A neve é branca
• As folhas são vermelhas
Proposições compostas - formadas com os conectivos lógicos
~ não (negação)
∨∨∨∨ ou (disjunção)
∧∧∧∧ e (conjunção)
→→→→ implica (implicação)
↔↔↔↔ implica (dupla implicação)
duplamente
Ordem de 
aplicação
42
Definição recursiva de WFF :
1. Um átomo é uma fórmula.
2. Se G é uma fórmula, então (~G) é uma fórmula
3. Se G e H são fórmulas, então (G ∧∧∧∧ H), (G ∨∨∨∨ H), 
(G →→→→ H) e (G ↔↔↔↔ H) são fórmulas
4. Todas as fórmulas são geradas a partir da aplicação das regras acima
Lógica Proposicional
Fórmulas bem formadas (WFF - Well Formed Formulas)
Os parênteses - explicitar ou trocar a ordem de aplicação 
P →→→→ Q ∧∧∧∧ R ≡≡≡≡ P →→→→ (Q ∧∧∧∧ R)
P →→→→ Q ∧∧∧∧ ~ R ∨∨∨∨ S ≡≡≡≡ P →→→→ (Q ∧∧∧∧ (( ~ R) ∨∨∨∨ S))
30/9/2008
22
43
Lógica Proposicional 
P ~P
V F
F V
• Está chovendo P
• Não está chovendo ~P
Negação: ~P é F quando P é V; ~P é V quando P é F
44
Lógica Proposicional 
• Isso é uma fruta P
• Isso é uma maçã Q
• Isso é uma fruta e é uma maçã (P ∧∧∧∧ Q) 
Conjunção:
P Q (P ∧∧∧∧ Q) 
V V V
V F F
F V F
F F F
(P ∧∧∧∧ Q) é V se P e Q são ambos V; 
caso contrário, (P ∧∧∧∧ Q) é F
30/9/2008
23
45
Lógica Proposicional 
• Maria é uma mulher P
• Maria é uma aluna Q
• Maria é uma mulher ou uma aluna (P ∨∨∨∨ Q) 
Disjunção:
P Q (P ∨∨∨∨ Q) 
V V V
V F V
F V V
F F F
(P ∨∨∨∨ Q) é V se pelo menos um de P ou Q é V; 
caso contrário, (P ∨∨∨∨ Q) é F
46
Lógica Proposicional
• Disjunção Inclusiva ou débil 
• “Se você é idoso ou deficiente, pode entrar no caixa 
preferencial”
• UM OU OUTRO OU AMBOS
• Disjunção Exclusiva ou forte
• “O acompanhamento do prato é arroz ou salada”
• UM OU OUTRO MAS NÃO AMBOS
30/9/2008
24
47
Lógica Proposicional 
• Isso é uma maçã P
• Isso é uma banana Q
• Isso é uma maçã ou uma banana (P ⊗⊗⊗⊗ Q) 
Disjunção
Exclusiva:
P Q (P ⊗⊗⊗⊗ Q) 
V V F
V F V
F V V
F F F
(P ⊗⊗⊗⊗ Q) é V se um de P ou Q é V, mas não ambos; caso 
contrário, (P ⊗⊗⊗⊗ Q) é F
48
Lógica Proposicional 
1. (C ∨∨∨∨ Z) ∧∧∧∧ (Y ∨∨∨∨ B)
2. (A ∧∧∧∧ B) ∨∨∨∨ (X ∧∧∧∧ Y)
3. ~(B ∨∨∨∨ X) ∧∧∧∧ ~(Y ∨∨∨∨ Z)
4. ~B ∨∨∨∨ C
5. ~((~X ∨∨∨∨ A) ∨∨∨∨ (~A ∨∨∨∨ X))
6. ~((~B ∨∨∨∨ A) ∧∧∧∧ (~A ∨∨∨∨ B))
7. (A ∧∧∧∧ (B ∨∨∨∨ C)) ∧∧∧∧ ~((A ∧∧∧∧ B) ∨∨∨∨ (A ∧∧∧∧ C))
8. (A ∧∧∧∧ (B ∨∨∨∨ X)) ∧∧∧∧ ~((Y ∧∧∧∧ B) ∨∨∨∨ (A ∧∧∧∧ C))
Prática: Calcule o valor verdade das fórmulas abaixo, 
considerando que A, B e C são V e X, Y e Z são F
30/9/2008
25
49
Lógica Proposicional 
Implicação: Se P então Q
Consequente 
ou implicado
Antecedente 
ou implicante
A implicação não afirma que seu antecedente é V, mas apenas que se seu 
antecedente for V então seu consequente também será V
Para (P →→→→ Q) ser V
(P ∧∧∧∧ ~Q) deve ser F
logo, ~(P ∧∧∧∧ ~Q) deve ser V
50
Lógica Proposicional 
• Está chovendo P
• As plantas estão molhadas Q
• Se está chovendo, então as 
plantas estão molhadas (P →→→→ Q) 
Implicação:
P Q ~Q (P ∧∧∧∧ ~Q) ~(P ∧∧∧∧ ~Q) (P →→→→ Q)
V V F F V V
V F V V F F
F V F F V V
F F V F V V
(P →→→→ Q) é F se P é V e Q é F; 
caso contrário, (P →→→→ Q) é V
30/9/2008
26
51
Lógica Proposicional 
• Hoje é segunda-feira P
• Amanhã é terça-feira Q
• Hoje é segunda-feira se e somente se
amanhã é terça-feira (P ↔↔↔↔ Q) 
Dupla
Implicação:
P Q (P →→→→ Q) (Q →→→→ P) (P ↔↔↔↔ Q)
V V V V V
V F F V F
F V V F F
F F V V V
(P ↔↔↔↔ Q) é V quando P e Q têm o mesmo valor verdade; caso 
contrário, (P ↔↔↔↔ Q) é F
52
Lógica Proposicional 
1. (C ∨∨∨∨ Z) →→→→ (Y ∨∨∨∨ B)
2. (A ∧∧∧∧ B) ∨∨∨∨ (X →→→→ Y)
3. ~(B ∨∨∨∨ X) →→→→ ~(Y ∨∨∨∨ Z)
4. ~B →→→→ C
5. ~((~X ∨∨∨∨ A) →→→→ (~A ∨∨∨∨ X))
6. ~((~B →→→→ A) ∧∧∧∧ (~A ∨∨∨∨ B))
7. (A ∧∧∧∧ (B ∨∨∨∨ C)) ∧∧∧∧ ~((A →→→→ B) ∨∨∨∨ (A →→→→ C))
8. (A ∧∧∧∧ (B →→→→ X)) ∧∧∧∧ ~((Y ∧∧∧∧ B) ∨∨∨∨ (A ∧∧∧∧ C))
Prática: Calcule o valor verdade das fórmulas abaixo, 
considerando que A, B e C são V e X, Y e Z são F
30/9/2008
27
53
Lógica Proposicional 
1. (C ∨∨∨∨ Z) →→→→ (Y ↔↔↔↔ B)
2. (A ∧∧∧∧ B) ↔↔↔↔ (X →→→→ Y)
3. ~(B ∨∨∨∨ X) →→→→ ~(Y ↔↔↔↔ Z)
4. ~B ↔↔↔↔ X
5. ~((~X ∨∨∨∨ A) ↔↔↔↔ (~A ∨∨∨∨ X))
6. ~((~B ↔↔↔↔ A) ∨∨∨∨ (~A ∨∨∨∨ B))
7. (A ∧∧∧∧ (B ∨∨∨∨ C)) ↔↔↔↔ ~((A →→→→ B) ∨∨∨∨ (A →→→→ C))
8. (A ∧∧∧∧ (B →→→→ X)) ∧∧∧∧ ~((Y ↔↔↔↔ B) ∨∨∨∨ (A ↔↔↔↔ C))
Prática: Calcule o valor verdade das fórmulas abaixo, 
considerando que A, B e C são V e X, Y e Z são F
54
Interpretação de Fórmulas
• Atribuição de valores
• O valor verdade de uma fórmula pode ser avaliado a partir 
do valor verdade dos átomos que compõem a fórmula
• Se G = P →→→→ (P ∧∧∧∧ Q); e a P é atribuído o valor V e a Q é 
atribuído o valor F então:
P Q (P ∧∧∧∧ Q) P →→→→ (P ∧∧∧∧ Q)
V F F F
• Então a fórmula G é falsa se a P é atribuído o valor V e a Q é atribuído o valor 
F.
30/9/2008
28
55
Interpretação de Fórmulas
• A atribuição de valores V e F a P e Q respectivamente é chamada de 
uma interpretação de G
• Sob essa interpretação G é falsa
• Temos 22 possíveis interpretações para a fórmula G
• A tabela verdade de G mostra todas as possíveis interpretações para 
G
P Q (P ∧∧∧∧ Q) P →→→→ (P ∧∧∧∧ Q)
V V V V
V F F F
F V F V
F F F V
56
Interpretação de Fórmulas
Definição: Dada uma fórmula proposicional G, sejam 
A1,A2,...,An os átomos que ocorrem em G. 
Então, uma interpretação de G é uma 
atribuição de valores verdade a A1,A2,...,An na 
qual a todo Ai é atribuído o valor V ou o valor F, 
mas não ambos.
Definição: A fórmula G é dita ser verdadeira sob uma interpretação se e somente 
se G é avaliada como V na interpretação; caso contrário, G é dita 
ser falsa sob aquela interpretação.
30/9/2008
29
57
Interpretação de Fórmulas
Prática: 
1 Avaliar a fórmula G = (P ∧∧∧∧ Q) →→→→ (R ↔↔↔↔ (~S)) sob a 
interpretação {P,~Q,R,S}, ou seja, atribuindo os valores 
{V,F,V,V} a {P,Q,R,S}.
2. Construir a tabela verdade para as seguintes fórmulas:
a) (P ∧∧∧∧ Q) →→→→ (R ↔↔↔↔ (~S))
b) ~B ↔↔↔↔ X
c) ~((~X ∨∨∨∨ A) ↔↔↔↔ (~A ∨∨∨∨ X))
d) ~((~B ↔↔↔↔ A) ∨∨∨∨ (~A ∨∨∨∨ B))
58
Validade e Inconsistência
Seja a fórmula G = ((P →→→→ Q) ∧∧∧∧ P) →→→→ Q
P Q (P →→→→ Q) (P →→→→ Q) ∧∧∧∧ P) (P →→→→ Q) ∧∧∧∧ P) →→→→ Q
V V V V V
V F F F V
F V V F V
F F V F V
O valor verdade de G sob qualquer interpretação é V
G é uma fórmula válida ou tautologia
30/9/2008
30
59
Validade e Inconsistência
Seja a fórmula G = (P →→→→ Q) ∧∧∧∧ (P ∧∧∧∧ ~Q)
P Q ~Q (P →→→→ Q) (P ∧∧∧∧ ~Q) (P →→→→ Q) ∧∧∧∧ (P ∧∧∧∧ ~Q)
V V F V F F
V F V F V F
F V F V F F
F F V V F F
O valor verdade de G sob qualquer interpretação é F
G é uma fórmulainconsistente ou contradição
60
Validade e Inconsistência
Definição: Uma fórmula é dita válida se e somente se é V 
sob qualquer interpretação. Uma fórmula é dita 
inválida se e somente se não é válida.
Definição: Uma fórmula é dita inconsistente ou insatisfatível se e 
somente se é falsa sob qualquer interpretação. Uma 
fórmula é dita consistente ou satisfatível se e somente se 
não é inconsistente .
30/9/2008
31
61
Validade e Inconsistência
Observações: 
1. Uma fórmula é válida se e somente se sua negação é 
inconsistente.
2. Uma fórmula é inconsistente se e somente se sua negação é 
válida.
3. Uma fórmula é inválida se e somente se existe pelo menos 
uma interpretação sob a qual a fórmula é F.
4. Uma fórmula é consistente se e somente se existe pelo 
menos uma interpretação sob a qual a fórmula é V.
5. Se uma fórmula é válida, então ela é consistente, mas não 
vice-versa.
6. Se uma fórmula é inconsistente, então ela é inválida, mas 
não vice-versa.
62
Validade e Inconsistência
Definição: Se uma fórmula G é V sob uma interpretação I, então 
é dito que I satisfaz a fórmula G.
Definição: Se uma fórmula G é falsa sob uma interpretação 
I, então é dito que I falsifica G.
Definição: Quando uma interpretação I satisfaz uma fórmula 
G, então I é dita um modelo de G.
Na Lógica Proposicional, já que o número de possíveis interpretações de 
uma fórmula é finito (2n - onde n é o número de átomos da fórmula), é 
sempre possível decidir se uma fórmula é válida ou inconsistente; basta 
examinar exaustivamente todas as possíveis interpretações.
Observação
30/9/2008
32
63
Validade e Inconsistência
Prática: 
1. Mostre, usando a tabela verdade que:
a) (P ∧∧∧∧ ~P) é inconsistente
b) (P ∨∨∨∨ ~P) é uma tautologia
2. Classifique as fórmulas como válidas, inconsistentes ou 
apenas satisfatíveis, usando a tabela verdade:
a) ((P →→→→ (P →→→→ Q)) →→→→ P)
b) (P →→→→ Q) ↔↔↔↔ (~Q →→→→ ~P)
c) P ↔↔↔↔ (P ∧∧∧∧ (P ∨∨∨∨ Q))
d) (P ∧∧∧∧ Q) ∧∧∧∧ (P →→→→ ~Q)