Upload
lise
View
28
Download
1
Embed Size (px)
DESCRIPTION
Monitoria de Lógica para Computação. Ciência da Computação 2010.1. Estruturas e Subestruturas Por: Jefferson de Menezes ( jmmf ) Ricardo Salomão (rssj2). Lógica de Predicados. - PowerPoint PPT Presentation
Citation preview
Estruturas eSubestruturas
Por: Jefferson de Menezes (jmmf)
Ricardo Salomão (rssj2)
Ciência da Computação 2010.1Ciência da Computação 2010.1
Lógica de PredicadosAté agora utilizamos a chamada “lógica
proposicional” para formalizar sentenças e argumentos, tal formalização perde muita informação, pois uma sentença(atômica) é representada por uma única variável, embora seja composta por um sujeito(objeto) e predicado...
Lógica de PredicadosCom a linguagem simbólica enriquecida de
símbolos para objetos e símbolos para predicados Frege definiu o que se chama de “Lógica de predicados” ou “Lógica de Primeira Ordem”.
Ex.: O unicórnio é lenda. Objeto = unicórnio Predicado = lenda
Estrutura MatemáticaUma estrutura matemática é dada por 4
componentes:
1 –Conjunto Domínio2 –Conjunto Predicados3 -Conjunto de Elementos Destacados4 –Conjunto de Funções
Obs.:O conceito de Valoração-verdade por si só não serve para resolver satisfatibilidade.
Estrutura MatemáticaEx.:
IN
Domínio
Funções
1Elementos Destacados
Primo(-)Menor que(-,-)
Predicados
Quadrado(-)Soma(-,-)
Estrutura MatemáticaEx.:
O número 3 é primo.
4 não é menor que 1.
Todo elemento menor que 2, seu quadrado é igual a ele mesmo.
Estrutura MatemáticaCodificando:
Predicados -> P(-) [Primo]; M(-,-)[Menor que]
Destacados -> a = 1
Funções -> q(-)[quadrado]; s(-,-)[soma]
Estrutura MatemáticaResposta:
P(s(a,s(a,a)))
¬M(q(s(a,a)),a)
x(M(x,s(a,a)) -> q(x)=x)
Assinatura de uma Estrutura Assinatura: A assinatura de uma estrutura
matemática A é dada “necessidade” simbólica para fins de codificação de sentenças sobre A. Em outras palavras a assinatura de A é dada por:
- Um conjunto de símbolos de predicado - Um conjunto de símbolos de constante - Um conjunto de símbolos de função
Estrutura Matemática
Obs.: Duas estruturas A e B podem ter a mesma assinatura e ainda assim terem naturezas bem diferentes.
A Noção de Subestrutura
A e B são L-estruturas e f é uma função (f: dom(A)->dom(B))
Homomorfismo: Dizemos que f preserva os “componentes lógicos” de A(de A para B) se: f é um homomorfismo.
• Homomorfismo(cont.):I. Preserva os Destaques:
f(cA) = cB
II. Preserva as Relações:Se (a1, a2, ..., an) Є RA --> (f(a1), f(a2), ..., f(an)) Є
RB
III. Preserva as Funções:
f(gA (a1, a2, ..., an)) = gB(f(a1), f(a2), ..., f(an))
A Noção de Subestrutura
Imersão: Dizemos que f é uma imersão se f for injetiva e for um homomorfismo que preserva os predicados indo e voltando.
O item II. seria substítuido por:
(a1, a2, ..., an) Є RA <==> (f(a1), f(a2), ..., f(an)) Є RB
Isomorfismo: Se f for uma imersão e for sobrejetora (bijetiva).
A Noção de Subestrutura
sse
Endomorfismo: Se f for um homomorfismo e f: A->A.
Automorfismo: Se f for um endomorfismo e for um isomorfismo.
A Noção de Subestrutura
Dadas duas estruturas A e B:A é uma subestrutura de B se (B é uma
expansão de A):
I. A e B são L-estruturas(possuem a mesma assinatura);
II. dom(A) dom(B);
III. A função f: A -> B é um homomorfismo imersor;
A Noção de Subestrutura
Qual será a menor subestrutura de B cujo domínio tem x?
I. O domínio de A deve conter todos os destaques de B;
II.As relações de sobre A são calculadas assim: RA = RB dom(A)n, n = aridade.
III.Destaques em A = destaques em B;
IV.As funções são definidas assim: para todo símbolo de f de L, fA deve estar definida em todos os pontos do domínio de A;
A Noção de Subestrutura Subestrutura Gerada
Dúvidas?