'
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)
Imagem:Homo2.jpg
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))
Referências (Em PDF)
Ganesh Gopalakrishnan. Computation engineering: applied automata theory and logic, pg. 82. Xindong Wu. IEEE Knowledge and Data Engineering Exchange Workshop, pg. 160. Hannu Kangassalo. Information Modelling and Knowledge Bases IV: Concepts, Methods and Systems, pg 245. Gérard Huet, G. Plotkin. Logical Environments, pg 8.
Categoria:Lógica Categoria:Ciência da computação