Conjuntos livremente gerados
# Conjuntos livremente gerados

    Esse artigo será melhor compreendido se você tiver conhecimento sobre conjuntos indutivamente definidos.
    A lógica simbólica nos permitir avaliar a validade de argumentos e a consistência de um conjunto de sentenças. Para que isso seja possível, é preciso que as expressões simbólicas sejam livre de ambiguidades, isso significa que o conjunto das expressões deve ser livremente gerado.

## Definição

    Desejamos caracterizar precisamente (i.e. matematicamente) o conjunto das palavras sobre o alfabeto simbólico (união de variáveis, constantes, operadores, símbolos auxiliares) que sejam expressões da lógica proposicional. Para isso, precisaremos dos conceitos vistos nos conjuntos indutivos.
Seja A um conjunto, e X um sub-conjunto próprio de A, suponha que F seja um conjunto de funções sobre A. Então o fecho indutivo de X sobre F (X+) é dito livremente gerado se:
* Todas as funções de F são injetoras quando aplicadas aos elementos de X+.
*   * Para toda f ϵ F, com aridade n, se α e β são n-uplas de elementos de X+ e α ≠ β, então f(α) ≠ f(β).
    2. Para qualquer par de funções f e g de F os conjuntos-imagem de f e g são disjuntos.
      * Não importa se f e g possuem aridades diferentes.
    3. Nenhum elemento da base X pertence ao conjunto imagem de f, onde f ϵ F.

## Definição recursiva de funções sobre conjuntos livremente gerados

    Quando um conjunto indutivamente definido é livremente gerado temos a possibilidade de definir funções por recursão sobre esse conjunto com a garantia de que a definição por recursão dará origem a uma função legítima. Existe diversas funções, como contar o número de operadores, contar o número de símbolos, contar número de parentêses, calcular o número de subexpressões, calcular o posto, a árvore sintática, etc.
Exemplos:
1) A função que conta o número de símbolos de uma expressão.
PROP é o conjunto de proposições.
f: PROP→N(Naturais)
          f(φ) = 1 se φ for senteça atômica
          f((ρ ^ θ)) = 3 + f(ρ) + f(θ)
          f((ρ v θ)) = 3 + f(ρ) + f(θ)
          f((ρ → θ)) = 3 + f(ρ) + f(θ)
          f((¬Ψ)) = 3 + f(Ψ)
2) A função que conta o número de parênteses de uma dada expressão:
esq: PROP→N
          esq(φ) = 0 se φ for senteça atômica
          esq((ρ ^ θ)) = 2 + esq(ρ) + esq(θ)
          esq((ρ v θ)) = 2 + esq(ρ) + esq(θ)
          esq((ρ → θ)) = 2 + esq(ρ) + esq(θ)
          esq((¬Ψ)) = 2 + esq(Ψ)
Lema: Para toda proposição φ o número de parênteses de φ é par.
Podemos provar cada uma dessas funções por indução matemática. Demonstraremos logo abaixo a prova para a função que conta o número de parênteses.
    Prova: A função f conta o número de parênteses de uma dada expressão.
1) Caso Base: φ é atômica
* f(φ) = 0 e 0 é par c.q.d. (como queria demonstrar)
2) Casos Indutivos:
* φ é da forma (¬ψ):
       Hipótese de indução: f(ψ) é par.
       Tese: f((¬ψ)) é par.
       Como f(ψ) é par, então f(ψ) + 2 também é.
       Como f((¬ψ)) = f(ψ) + 2.
       Logo, f((¬ψ)) também é par. c.q.d.
* φ é da forma (ρ □ ω):
Onde □ = ^, v, →
       Hipótese de indução: f(ρ) é par e f(ω) é par.
       Tese: f((ρ □ ω)) é par.
       Da definição de f:
       f((ρ □ ω)) = f(ρ) + f(ω) + 2
       Como f(ρ) é par, f(ω) também é par.
       Então f(ρ) + f(ω) + 2 também é par.
       Logo f((ρ □ ω)) é par. c.q.d.

## Teorema da extensão homomórfica única

Seja A um conjunto, X subconjunto A, e F um conjunto de funções sobre A. Seja B um outro conjunto, e G um conjunto de funções sobre B tal que existe uma associação d: F → G entre cada função de F com uma função de G com mesma aridade. Se o fecho indutivo de X sobre F, isto é, X+, for livremente gerado então, para toda função h: X → B existe uma única função ĥ: X+ → B tal que:
I. ĥ(x) = h(x), para todo x є X;
    Para toda função f ϵ F, aridade de (f) = k, toda k-upla, f1,f2,...,fk ϵ X+.
II. ĥ(f(x1, ..., xk) ) = g( ĥ(x1), ..., ĥ(xk) ), onde g = d(f)
    F = {f¬(-), f^ (-, -), fv (-, -), f→ (-, -)}
    G = {NÃO(-), E(-, -), OU(-, -), SE-ENTÃO(-, -)}
    d(f¬) = NÃO,d(f^) = E, d(fv) = OU, d(f→) = SE-ENTÃO
       A função: ĥ :X+→B, será a função que associa a cada expressão da lógica proposicional um valor booleano, tal que confirme o teorema da extensão homomórfica única:
* para toda expressão atômica φ: ĥ(φ) = h(φ)
* (i) ĥ(f¬(w)) = NÃO (ĥ (w))
       (ii) ĥ(f^(w1, w2)) = E (ĥ (w1), ĥ (w2))
       (iii) ĥ(fv(w1, w2)) = OU (ĥ (w1), ĥ (w2))
       (iv) ĥ(f→ (w1, w2)) = SE-ENTÃO (ĥ (w1), ĥ (w2))