Upload
internet
View
105
Download
0
Embed Size (px)
Citation preview
Edward Hermann Lógica e Computação 1
Lógicas em Dedução Natural
Lógica Minimal : Todas as regras para e
LLógica Intuicionista : LLógica Minimal + Abs. Intuic.
Lógica Clássica : Lógica Minimal + Abs. Clássico
Edward Hermann Lógica e Computação 2
Consequência Dedutiva
Sejam um conjunto de fórmulas e uma fórmula.
Existe uma dedução de a partir de
Cn() = { / }
Cn() = ?
Edward Hermann Lógica e Computação 3
O que se espera de um sistema dedutivo?
Corretude : Se então .
Completude : Se então .
Teorema : Dedução Natural é um sistema dedutivo correto e completo com relação à semântica clássica.
Edward Hermann Lógica e Computação 4
O que se pode expressar na linguagem da
lógica proposicional ?
Como expressar propriedades ?
Como qualificar objetos ?
Como generalizar conceitos ?
Edward Hermann Lógica e Computação 5
A Linguagem de primeira ordem
é Mortal
propriedade
Predicado
Todo
Conjunto
Homem
objeto deuma classe
Conjunto Toda
ref.
Toda referência ao conjunto dos homens pertenceao conjunto dos mortais.
Edward Hermann Lógica e Computação 6
Interpretação em aberto...
Toda referência ao conjunto denotado por Homem pertence ao conjunto denotado por Mortal.
x ( H (x) M (x) )
referência conjunto conjunto
Edward Hermann Lógica e Computação 7
Funções e Relações
pai de João é colega de Denise
João Denise
colega(Denise, pai(João))
Edward Hermann Lógica e Computação 8
Formalizando
Alfabeto
Símbolos lógicos
Símbolos não lógicos = definidos pelo usuário
~}
variáveis
constantes símbolosfuncionais
símbolospredicativos
Edward Hermann Lógica e Computação 9
Termos (Denotam objetos) :Toda variável ou constante é um termo. Se t1, ..., tn são termos e f é um símbolo funcional de aridade n, então :
f(t1, ..., tn) é um termo.
Fórmulas atômicas ou Átomos : Se t1, ..., tn são termos e P é um símbolo
predicativo de aridade n, então :
P(t1, ..., tn) é uma fórmula atômica.
Se é uma fórmula, então :
xe xsão fórmulas
Edward Hermann Lógica e Computação 10
Conceitos Sintáticos Importantes
- Variáveis Livres x Variáveis Ligadas
- Parâmetros
- uma categoria sintática para representar variáveis livres
- x(p(x) q(y)) - xp(x) q(x)
Edward Hermann Lógica e Computação 11
Dedução Natural para primeira ordem
Intro
a)--------------xx
xx-----------------
t
Elim
a não pode ocorrer em nenhuma hipótese da qual adependa
Edward Hermann Lógica e Computação 12
- Intro
t)-----------------
xx
xx---------------------------------
[a
- Elim
a não pode ocorrer em xx nem em nem em qualquer fórmula da qual a dedução deste dependa.
Edward Hermann Lógica e Computação 13
Semântica
Como interpretar os símbolos não lógicos ?
Onde estão os objetos ?
Qual a denotação dos s. funcionais e predicativos ?
No universo do discurso.
- s. funcionais denotam objetos referenciados a partir de outros objetos. Funções (n-árias) sobre o Domínio.
Domínio)
- s. predicativos denotam propriedades ou relações
Relações sobre o Domínio.
Edward Hermann Lógica e Computação 14
Uma estrutura para interpretar um linguagem L
de primeira ordem é um objeto do tipo :M = [ D, Pred, Func ]
onde :
D é um conjunto
Para cada s. funcional f, de aridade n, de L M associa uma função F : D
nD em Func.
Para cada s. predicativo p, de aridade n, de L
Massocia uma relação P Dassocia uma relação nem Pred.
Edward Hermann Lógica e Computação 15
Exemplo Seja a linguagem L com : - Constantes : 0
- Funcionais : s, +, * , E
- Predicativos : <
Uma possível estrutura é : M = [N, <, 0, suc, +, *, E ]
com E sendo a função de expoenciação.
obs: Constantes podem ser vistas como Funcionais de aridade 0
Edward Hermann Lógica e Computação 16
Outros exemplos
1- L=<, >
O que pode-se expressar nesta linguagem ?Quem pode ser estrutura para esta linguagem ?
2a- L=< {v0},{2}>
O que pode-se expressar nesta linguagem ?Quem pode ser estrutura para esta linguagem ?
3- L=< , {E2,D2,V0}>
O que pode-se expressar nesta linguagem ?Quem pode ser estrutura para esta linguagem ?
2b- L=<{2,i0}, >
Edward Hermann Lógica e Computação 17
Como atribuir valor verdade às fórmulas ? P(t1, ..., tn) é verdadeira em uma estrutura
M sse, a interpretação da n-upla <t1, ..., tn> pertence a relação que denota P, em M.
Como interpretar variáveis ? Associa-se a cada variável um elemento do domínio, via uma funcão Assim :
P(t1, ..., tn) é verdadeira em uma estrutura M sob uma função sse, a interpretação da n-upla <t1, ..., tn> pertence a relação que denota P, em M. (< M,> P(t1, ..., tn))
Edward Hermann Lógica e Computação 18
Fórmulas existênciais e universais
a/x](y) =
(y) se y x
a se y = x
< M, > x, sse para todo a Dom( M ) < M, a/x] >
< M, > x, sse existe a Dom( M ) < M, a/x] >
Edward Hermann Lógica e Computação 19
Exemplos de fórmulas verdadeiras em
[N, <, 0, s, +, *, E ]
Sendo : Div(x,y) x 0 ) k( k*x = y)
Par(x) Div(s(s(0)),x)
Primo(x) x s(0)) y( Div(y,x) y = s(0) y = x)
n (Primo(n) Par(n))
Edward Hermann Lógica e Computação 20
Outra estrutura para a mesma linguagem[Q, <, 0, suc, +, *, E ]
com :
Q Racionais, < é a ordem usual, s (m/n) = m/n + 1, E( m/n , k/j )= m k
+ e * usuais.
S =
S xyk(x k y k x < k k < y)
Obs : Omitimos a função quando a relação semântica se dá para todas as funções.
Edward Hermann Lógica e Computação 21
Entendendo o par <M, > como uma interpre-tação :
Dedução Natural clássica é correta e completa para a linguagem de primeiraordem.
Compacidade].
- , sse para algum finito, .
- é satisfatível, sse, todo finito é satisfatível.
Edward Hermann Lógica e Computação 22
Mundo "real"Mundo Linguistico M
M
Th(M)
Cn
Cn
Cn
Cn