Conjuntos livremente gerados

Adicionar hiperligações
Origem: Wikipédia, a enciclopédia livre.

'

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[editar | editar código-fonte]

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:

  1. 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[editar | editar código-fonte]

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[editar | editar código-fonte]

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:
  1. para toda expressão atômica φ: ĥ(φ) = h(φ)
  2. (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))

Referências[editar | editar código-fonte]

«Apostila do professor Ruy de Queiroz» (PDF)  (Em PDF)

Obtida de "https://pt.wikipedia.org/w/index.php?title=Conjuntos_livremente_gerados&oldid=63862614"