aula2 Conjuntos Indutivos e Fechos Indutivos2

Prévia do material em texto

Monitoria de Lógica
para Computação
Conjuntos Indutivos e
Fechos Indutivos
Por
Dayvid Victor (dvro)
Ricardo Salomão (rssj2) [SAL]
Vinícius Cantarelli (vhco) [Bolinha]
Ciência da Computação 2010.1
Motivação
O conjunto de todas as palavras da Lógica proposicional é construído sobre o alfabeto Σ = {x, y, z, 0, 1, (, ), ^ , v , →, ¬}
Mas nem todas as palavras sobre esse alfabeto representam expressões bem-formadas. Ex.: (x ¬ ν), ¬).
Motivação
Como definir o Conjuntos das Expressões Bem-Formadas da lógica proposicional ?
Conjuntos Indutivos
Seja A um conjunto e X um subconjunto de A (X ⊂ A). Considere F um conjunto de funções cada uma com sua aridade.
Dizemos que um subconjunto Y de A (Y ⊆ A) é indutivo em relação à base X e a F se:
I) Y contém a base X. (X ⊂ Y)
II) Y é fechado sobre todas as funções de F.
F = {f(), g(),...}
 é um conjunto indutivo em relação a X e a F.
Y
Y
A
X
Fecho Indutivo
Como nós chegamos ao menor conjunto indutivo ? 
Há duas formas de chegarmos ao fecho indutivo:
1) De baixo para cima (bottom-up)
2) De cima para baixo (top-down)
 
Fecho Indutivo – Bottom-up
Sejam f e g funções de F:
f(-, -) binária;
g(-) unária;
a b c
f(a,b) 
f(b,a) f(a,c) 
 f(c,a) 
 f(b,c) 
f(c,b) g(a) g(b) 
g(c)
 
a b c
			 f(a,f(a,b)) f(a,f(b,a)) 
		 f(a,f(a,c)) f(a,f(c,a)) f(a,f(b,c)) f(a,f(c,b)) 
		f(a,g(a)) f(a,g(b)) f(a,g(c)) f(f(a,b),a) f(f(b,a),a) f(f(a,c),a) 
	 f(f(c,a),a) f(f(b,c),a) f(f(c,b),a) f(g(a),a) f(g(b),a) f(g(c),a) 
 f(b,f(a,b)) f(b,f(b,a)) f(b,f(a,c)) f(b,f(c,a)) f(b,f(b,c)) f(b,f(c,b)) f(b,g(a)) f(b,g(b)) 
	f(b,g(c)) f(f(a,b),b) f(f(b,a),b) f(f(a,c),b) f(f(c,a),b) f(f(b,c),b) f(f(c,b),b) f(g(a),b) 
 f(g(b),b) f(g(c),b) f(c,f(a,b)) f(c,f(b,a)) f(c,f(a,c)) f(c,f(c,a)) f(c,f(b,c)) f(c,f(c,b)) 
 f(c,g(a)) f(c,g(b)) f(c,g(c)) f(f(a,b),c) f(f(b,a),c) f(f(a,c),c) f(f(c,a),c) f(f(b,c),c) f(f(c,b),c) 
 f(g(a),c) f(g(b),c) f(g(c),c) f(f(a,b),f(a,b)) f(f(a,b),f(b,a)) f(f(a,b),f(a,c)) f(f(a,b),f(c,a)) f(f(a,b),f(b,c)) 
 f(f(a,b),f(c,b)) f(f(a,b),g(a)) f(f(a,b),g(b)) f(f(a,b),g(c)) f(f(b,a),f(a,b)) f(f(a,c),f(a,b)) f(f(c,a),f(a,b)) 
	 f(f(b,c),f(a,b)) f(f(c,b),f(a,b)) f(g(a),f(a,b)) f(g(b),f(a,b)) f(g(c),f(a,b)) f(f(b,a),f(b,a)) 
		f(f(b,a),f(a,c)) f(f(b,a),f(c,a)) f(f(b,a),f(b,c)) f(f(b,a),f(c,b)) f(f(b,a),g(a)) f(f(b,a),g(b)) 
		 f(f(b,a),g(c)) f(f(a,c),f(b,a)) f(f(c,a),f(b,a)) f(f(b,c),f(b,a)) f(f(c,b),f(b,a)) f(g(a),f(b,a)) 
		 f(g(b),f(b,a)) f(g(c),f(b,a)) f(f(a,c),f(a,c)) f(f(a,c),f(c,a)) f(f(a,c),f(b,c)) 
		 f(f(a,c),f(c,b)) f(f(a,c),g(a)) f(f(a,c),g(b)) f(f(a,c),g(c)) f(f(c,a),f(a,c)) 
		 f(f(b,c),f(a,c)) f(f(c,b),f(a,c)) f(g(a),f(a,c)) f(g(b),f(a,c)) f(g(c),f(a,c)) 
		 f(f(c,a),f(c,a)) f(f(c,a),f(b,c)) f(f(c,a),f(c,b)) f(f(c,a),g(a)) f(f(c,a),g(b)) 
		f(f(c,a),g(c)) f(f(b,c),f(c,a)) f(f(c,b),f(c,a)) f(g(a),f(c,a)) f(g(b),f(c,a)) 
	 f(g(c),f(c,a)) f(f(b,c),f(b,c)) f(f(b,c),f(c,b)) f(f(b,c),g(a)) f(f(b,c),g(b)) f(f(b,c),g(c)) 
 	f(f(c,b),f(b,c)) f(g(a),f(b,c)) f(g(b),f(b,c)) f(g(c),f(b,c)) f(f(c,b),f(c,b)) f(f(c,b),g(a)) 
	 f(f(c,b),g(b)) f(f(c,b),g(c)) f(g(a),f(c,b)) f(g(b),f(c,b)) f(g(c),f(c,b)) 
		f(g(a),g(a)) f(g(a),g(b)) f(g(a),g(c)) f(g(b),g(a)) f(g(c),g(a)) 
		 f(g(b),g(b)) f(g(b),g(c)) f(g(c),g(b)) f(g(c),g(c))
...
X+
f(a,b) 
f(b,a) f(a,c) 
 f(c,a) 
 f(b,c) 
f(c,b) g(a) g(b) 
g(c)
Fecho Indutivo – Bottom-up
Vamos construir o fecho indutivo a partir da base:
Onde aridade(f) = k e x1, x2, ..., xk ∊ Xn e ∊ F 
Fecho Indutivo – Top-down
Considere a família C de conjuntos indutivos em relação a X e F.
Perceba que C não é vazia pois contém pelo menos A.
Considere X+= ∩ C o conjunto formado pela intersecção de todos os conjuntos de C.
Temos que X+ é o menor conjunto indutivo em relação a X e F (fecho indutivo)
Conjunto EBF
Base:
{x, y, z, 0, 1}
Os elementos da base também pertencem ao conjunto.
No caso do conjunto EBF, os elementos da base devem ser expressões bem-formadas.
Funções – F = {f,g,h,i}
f: EBF→ EBF
f(w) = (¬w)
g: EBF x EBF → EBF
g(w1,w2) = (w1 ^ w2)
h: EBF x EBF → EBF
h(w1,w2) = (w1 v w2)
i: EBF x EBF → EBF
i(w1,w2) = (w1 → w2)
Conjuntos Livremente Gerados
Definição:
Sejam A e X conjuntos, X está contido em A, e seja F um conjunto de funções que recebem como parâmetro elementos de A: O fecho indutivo de X+ de X sob F será livremente gerado se e somente se:
 Todas as funções de F forem injetoras.
 Sejam f e g funções de F sobre X+, o conjunto imagem de f e g são disjuntos.
 Nenhum elemento da base X é resultado de aplicações de f sobre o fecho de X.
 Todo CLG tem a propriedade de leitura única, ou seja, só existe uma forma de, aplicando funções de F, se “chegar” a elementos do conjunto CLG.
	 f(a,b) != g(a,b) != f(g(a),f(a,b)) !=(...)
Exemplinhuxxx
1. Dê a base e as funções dos conjuntos indutivos propostos abaixo e diga se eles são livremente gerados.
Conjunto das cadeias binárias de tamanho par;
Conjunto dos números primos;
Conjunto das cadeias binárias que têm a quantidade de 1’s maior que a quantidade de 0’s e os 0’s aparecem antes dos 1’s;
Conjunto dos números múltiplos de n.
	2. 	Considere o conjunto C das cadeias binárias que comecem 1 (ex. 10010). Dê uma definição indutiva para C, e identifique: o conjunto ‘base’ da geração indutiva (i.e., X), e o conjunto de funções geradoras (i.e., F). (Dica: a função de concatenação, ao tomar duas palavras w e v como argumentos de entrada, retorna a palavra wv.)
 1
Base B:
B = { 1 }
Funções :
	f(-) unária; 
	g(-) unária;
f(w) = w0;
g(w) = w1;
F = { f(-) , g(-)}
(i) Descreva em poucas palavras quais são: o menor e o maior conjunto indutivo de X sob F.
O menor:
		X0 = B;
		Xi+1 = Xi U {f(w1,...,wn)| f є F e w1,...,wn є Xi 
						e n = aridade de f}
1000
 1010 11000 
 1001
1011
 1101 1111
 
100
101
110
111
 
		
	
 
10 
 11
 
1
...
X+
O maior:
		Conjunto de todas as cadeias de bits
--
(ii) Considerando suas definições de quem é X e quem são as funções de F, podemos dizer que o conjunto C é livremente gerado?