Ciência da Computação 2010.1
Estruturas e
Subestruturas
Por:
Jefferson de Menezes (jmmf)
Ricardo Salomão (rssj2)
Lógica de Predicados
 Até 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 Predicados
 Com 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ática
 Uma estrutura matemática é dada por 4 componentes:
 1 –Conjunto Domínio
 2 –Conjunto Predicados
 3 -Conjunto de Elementos Destacados
 4 –Conjunto de Funções
 Obs.:O conceito de Valoração-verdade por si só não
serve para resolver satisfatibilidade.
Estrutura Matemática
 Ex.:
Domínio
IN
Predicados
Funções
Primo(-)
Menor que(-,-)
Quadrado(-)
Soma(-,-)
1
Elementos
Destacados
Estrutura Matemática
 Ex.:
 O número 3 é primo.
 4 não é menor que 1.
 Todo elemento menor que 2, seu quadrado é igual a ele
mesmo.
Estrutura Matemática
 Codificando:
 Predicados -> P(-) [Primo]; M(-,-)[Menor que]
 Destacados -> a = 1
 Funções -> q(-)[quadrado]; s(-,-)[soma]
Estrutura Matemática
 Resposta:
 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.
A Noção de Subestrutura
• 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
sse
<==> (f(a1), f(a2), ..., f(an)) Є RB
 Isomorfismo: Se f for uma imersão e for sobrejetora
(bijetiva).
A Noção de Subestrutura
 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
Subestrutura Gerada
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;
Dúvidas?