Upload
phunghanh
View
252
Download
0
Embed Size (px)
Citation preview
LÓGICA APLICADA A COMPUTAÇÃO
Aquiles Burlamaqui2009.3
Ementa
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Unidade 2
Lógica de Predicados: Linguagem e Semântica
Tradução do português para a Lógica
Quantificadores e Tipos
Quantificadores como Conjunções e Disjunções Infinitas
Linguagem de Primeira Ordem
Verdade
A Teoria Formal da Lógica de Predicados
Teoria Formal do Calculo de Predicados
Teorema da Dedução
Computação na Lógica de Predicados
Resolução
Resultados de Completude
Lógica de Predicados:
Linguagem e Semântica
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Introdução
Tradução do Português para a Lógica
Quantificadores e Tipos
Quantificadores como Conjuções e Disjunções Infinitas
Linguagem de 1º Ordem
Verdade
Introdução
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Como analizar expressões como:
“Todo estudante gosta de tirar boas notas”
“Algo está errado”
Constante
“o gato é magro”
magro(gato)
Variável
“algo é magro”
magro(algo) - errado
x.magro(x) - certo
Introdução
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Quantificador
existêncial, universal
Quantificação
x , x
Uso do quantificador
x.(magro(x) ^ faminto(x)) – x mesmo valor
(, ) delimitam o escopo do x
x.magro(x) ^ y.faminto(y)
Quantificadores de mesmo tipo podem ser trocados de ordem, e não mudam o significado
Quantificadores de tipos diferentes, a ordem influência.
Tradução do Português para a Lógica
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Como na lógica proposicional, liga-se as sentençasatômicas com os conectivos e, ou, se...então,não, se e somente se.
Com os quantificadores e variáveis se aplica o mesmo princípio.
Tradução do Português para a Lógica
Traduzindo pronomes: “algo”, “todo mundo”, “nada”, “ele”, “ela”
Jose gosta de Maria e ela o adora
Regra: se os pronomes estão ligados por um conectivo trate dos
pronomes antes do conectivo
Quantificadores e Tipos
Como se referir a um certo conjunto de coisas e não a todas as coisas? “todos os seres racionais odeiam violência”
“Maria gosta de alguém que gosta de lógica”
A resposta é: qualificando o quantificador.
Qualificando o quantificador: Universal Utilizando uma implicação
(racional)x.(x odeia violência)
x.(racional(x)odeia-violência(x))
Existencial Utilizando uma conjunção
(uma pessoa que gosta de lógica)y. gosta (Maria, y)
y.(pessoa(y)^gosta(y,lógica)^gosta(Maria,y))
Quantificadores e Tipos
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Notação para facilitar o uso de qualificativos
Quantificadores tipados(tipos)
x:nome-do-tipo x:nome-do-tipo
Quantificadores como
Conjunções e Disjunções Infinitas
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Quantificadores podem ser utilizados na
representação de conjunções e disjunções infinitas.
“todo número natural tem a propriedade P”
x.P(x)
Quantificador universal ligado a variável
Conjunção infinita
Linguagem de 1º Ordem
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Expressa idéias mais complexas
“se x é par então x+1 é impar”
“x.(par(x)impar(x+1))”
Sentença pode ser verdadeira ou falsa dependendo
da interpretação
Linguagem de 1º Ordem
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Teorias de 1º ordem
Argumentos dos predicados podem ser constantes,
variáveis, funções.
Linguagens de predicados, são extensões das
linguagens proposicionais
Alfabeto de 1º ordem
Alfabeto = X U {f1,f2,...,R1,R2,...não,e,ou, implica, se
somente se, para todo,existe, (,),.,,)
Linguagem de 1º Ordem
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Linguagem dos termos
Linguagem de predicados
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
14
Linguagem de 1º Ordem
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Análise de quantificações
R(x,y,z) = {(x,y,z) N3/ x+y=z}
x+y=z aplicar quantificações
Linguagem de 1º Ordem
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Formula fechada
Variável livre e ligada
Exemplos
Termo livre
Exemplos
Linguagem de 1º Ordem
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
18
Verdade
Dado uma linguagem de 1º ordem, um interpretação para essa linguagem é um sigma domínio.
Verdade
Interpretação
Verdade
Valoração verdade
Verdade
Valoração verdade
Verdade
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Modelo
Satisfatível
Insatisfatível
Verdade
Verdade
Verdadeira numa dada interpretação
Falsa numa dada interpretação
Universalmente válida
Verdade
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Verdade
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
Consequencia Lógica
Lógica de Predicados
Exercícios
Aulas de Lógica Aplicada a Computação - Aquiles Burlamaqui
1, 2, 3, 4, 5, 6
Referencias
Callejas, Bedregal. Acióly, Bendito. Lógica para a
Ciência da Computação, Natal, 2001.
http://pt.wikipedia.org/wiki/L%C3%B3gica
http://www.pucsp.br/~logica/