Secuencia X1,...,Xn de expresiones proposicionales tal que para cada eslabón Xi: 1) Xi = pk para algun pk∈Var 2) Xi = ¬Xj para algun 1≤j<i 3)Xi = (Xj*Xk) con *∈{^,v,->} para algunos 1≤j,k<i

Subcadena

Sea C=X1,...,Xn una cadena de formación. Xi1,...Xik es subcadena de C si: -es cadena de formación -Xik = Xn -respeta el orden creciente de C

Cadena de formación minimal

Tiene una única subcadena que es si misma

Complejidad

C(α) = #conectivos que aparecen en α

Complejidad binaria

Cb(α) = #conectivos binarios (^,v,->) que aparecen en α

Peso

P(α) = #parentesis que abren en α - #parentesis que cierran en α

Subfórmulas

S(α) es el conjunto definido por: - Var(α)={pk/pk aparece en α} son subfórmulas - si α=¬β ---> s(α)={α} u s(β) - si α=(β1*β2) ---> s(α)={α} u s(β1) u s(β2)

Valuación

Una valuación es una función v:Form--->{0,1} tal que: - v(¬β) = 1 - v(β) - v((β1^β2)) = min{v(β1); v(β2)} - v((β1vβ2)) = max{v(β1); v(β2)} - v((β1->β2)) = max{1-v(β1); v(β2)}

Tautología

Α es tautología si v(α) = 1 para toda valuación

Contradicción

Α es contradicción si v(α) = 0 para toda valuación

Contingencia

Α es contingencia si NO es tautología ni contradicción

Equivalentes

Dos formulas α y β se dicen equivalentes si v(α) = v(β) para toda v val α ≡ β

Función booleana

Una función f:{0,1}^n ---> {0,1}

Conectivos adecuados

C conjunto de conectivos es adecuado si ∀ α∈Form existe β∈Formc con α ≡ β

Satisfacible

Un conjunto Γ es SATISFACIBLE si existe v val tal que v satisface a Γ v val SATISFACE a Γ si v(α)=1 ∀α∈Γ v val satisface a α si v(α)=1

Insatisfacible

Un conjunto Γ es insatisfacible si no existe ninguna v val tal que v satisfaga a Γ

Consecuencia

Α es consecuencia de Γ si: ∀v val que satisface a Γ ---> v(α)=1

Finitamente satisfacible

Γ es f.s. si para cada conjunto finito Γ'⊆Γ, Γ' es satisfacible

Axiomas

1) ( α -> ( β -> α )) 2) (( α -> ( β -> γ )) -> (( α -> β ) -> ( α -> γ ))) 3) (( ¬α -> ¬β ) -> (( ¬α -> β ) -> α ))

Prueba

Una prueba de α es una sucesión de fórmulas α1,...,αn con: - α = αn - αi tiene dos opciones: 1) es una instancia de axioma 2) existen αj, αk con j,k<i tal que αj = αk->αi. Entonces αi se obtiene por Modus Ponens de αj y αk

Demostrable

Α es demostrable si existe una prueba de α

Prueba a partir de Γ (Γ⊢α)

Α se prueba a partir de Γ si existe una prueba α1,...,αn tal que: - α = αn - αi tiene dos opciones: 1) αi es una instancia de axioma 2) αi ∈ Γ 3) αi se obtiene por MP de αj, αk con j,k<i

Inconsistente

Un conjunto Γ es inconsistente si existe φ tal que Γ⊢φ y Γ⊢¬φ

Consistente

Un conjunto Γ es consistente si no es inconsistente

Maximal consistente

Γ es m.c. si: - Γ es consistente - ∀φ∈Form: φ∈Γ ó {φ}uΓ es inconsistente

Independiente

Γ es independiente si ∀α∈Γ, α∉C(Γ-{α})

Dependiente

Γ es dependiente si ∃α∈Γ tal que α∈C(Γ-{α})

Base

Γ es base si y solo si: 1) Γ es independiente 2) Si ∃Σ conjunto independiente tal que Σ⊆Γ ---> Σ = Γ

Valuación modificada

Dada una val v:Var->Ui, la val modificada en la variable xi por a∈Ui es v_xi=a (xj) =

Alfabeto de la log de 1er orden

-Var -Paréntesis -Conectivos -Cuantificadores -Símbolos de constante -Símbolos de función -Símbolos de predicado

Términos

El conjunto de términos de L leng de primer orden cumple: -Las var son términos -Los símbolos de cte son términos -Si fk es un símbolo de función y t1,...,tk son términos ---> fk(t1,...,tk) es término

Fórmulas

El conjunto de fórmulas de L (leng de 1er orden) cumple: - Si Pk es un símbolo de predicado y t1,...,tk son términos ---> Pk(t1,...,tk) es una fórmula - Si α, β son fórmulas ---> (α^β), (αvβ), (α->β), ¬α son fórmulas -Si α es fórmula y xi∈Var ---> ∀xiα, ∃xiα son formulas

Variable libre

Sea xi una variable que aparece en un término de α. Decimos que xi es libre si no es alcanzada por un cuantificador (∃ o ∀) en NINGUNA aparición

Variable ligada

Sea xi una variable que aparece en un término de α. Decimos que xi es ligada si es alcanzada por un cuantificador (∃ o ∀) en TODAS sus apariciones

Término cerrado

No tiene variables

Sentencia/Enunciado

Fórmula en la cual todas las variables son ligadas

Interpretación

Una interpretación I de un lenguaje de 1er orden L es: - un conjunto Ui no vacío (universo de la interpretación) - para cada c símbolo de cte, un elemento ci∈Ui - para cada fk símbolo de función, una funció n fik:Uik->Ui - para cada Pk símbolo de predicado, una relación Pik⊆Uik I=<Ui, {ci}, {fik}, {Pik}>

Valuación en I

Una valuación en una interpretación I de L es una función v:Var->Ui Podemos extenderla de manera única a una funcion v':Term(L)->Ui

Valuación modificada

Dada una val v:Var->Ui, la val modificada en la variable xi por a∈Ui es

Valor de verdad

El valor de verdad de una fórmula es una funcion Vi,v : Form(L)->{0,1} tal que: - α=Pk(t1,...,tk): Vi,v(α)=|1 si (v'(t1),...,v'(tk))∈Pik | 0 si no - α=∀xi β : Vi,v(α) = |1 si ∀a∈Ui Vi,v_xi=a (β) = 1 |0 si no - α=∃xi β : Vi,v(α) = |1 si ∃a∈Ui / Vi,v_xi=a (β) = 1 |0 si no - α=(α1^α2): Vi,v(α) = min{Vi,v(α1); Vi,v(α2)} - α=(α1vα2): Vi,v(α) = max{Vi,v(α1); Vi,v(α2)} - α=(α1->α2): Vi,v(α) = max{1-Vi,v(α1); Vi,v(α2)} - α=¬α1: Vi,v(α) = 1-Vi,v(α1)

Satisfacible

Α es satisfacible si existen I y v tal que I⊧α[v], es decir, tal que Vi,v(α)=1

Válida/verdadera

Α es válida o verdadera en I si ∀v valuación en I sucede que I⊧α (Vi(α)=1 para cualquier valuación)

Universalmente válida

Α es universalmente valida si ∀I interpretacion ⊧α (V(α)=1)

Consecuencia

Α es consecuencia de Γ si ∀I interpretación y ∀v val con I⊧γ[v] ∀γ∈Γ ---> I⊧α[v] Se escribe Γ⊧α

Expresable

Un conjunto A es expresable por una fórmula α si α tiene una única variable libre y se cumple: a∈A ⇔ I⊧α[v_x=a] A={a∈U/α(a)}

Distinguible

Un elemento u∈Ui es distinguible si {u} es expresable

Modelo

Una interpretación I es un modelo de un conjunto Γ∈Form(L) si I⊧α ∀α∈Γ

Isomorfismo

Sean I1 e I2 dos interpretaciones con universos Ui1 y Ui2 F:Ui1->Ui2 función de dice isomorfismo si cumple: 1) F es biyectiva 2) F(ci1)=ci2 3) F(fi1k(t1,...,tk))=fi2k(F(t1),...,F(tk)) 4) (t1,...,tk)∈Pi1k ⇔ (F(t1),...,F(tk))∈Pi2k

Programa

Un programa es una lista de instrucciones I1,...,In

Macro

Un macro es una pseudoinstrucción que es un reemplazo por un programa en S que ejecuta dicha pseudoinstrucción. Al proceso de cambiar la pseudoinstrucción por las instrucciones del programa se llama "expansión del macro"

Estado

Un estado de un programa P es una lista de ecuaciones de la forma V=k (V variable que aparece en P) con k∈N

Descripción instantanea (SNAPSHOT)

Dado P = I1,...,I2 es un par (i, σ) con 1≤i≤n+1 y σ un estado Si i=n+1 la descripción es terminal

Computo

Un computo es una secuencia de descripciones d1, d2,...,dk donde dk es terminal y dj+1 es sucesor de dj con k>j≥1

Descripción inicial

Una descripción es inicial si d=(1, σ) y σ es estado con ecuación de todas las variables auxiliares y de salida V=0

Parcial computable

F:Nk -> N función es parcial computable si existe un programa P tal que

Total computable

F:Nk -> N es total computable si es parcial computable y Dom(f)=Nk

Recursión primitiva de tipo 1

Sean h:N->N y g:N2->N. Decimos que h se obtiene de g por RP de tipo 1 o tiene un esquema recursivo de tipo 1 (ERP1) si cumple: -h(0) = k∈N -h(n+1) = g(n, h(n))

Recursión primitiva de tipo 2

Sean g:Nn+2 -> N, f:Nn -> N funciones. Decimos que h:Nn+1 -> N se obtiene de recursión primitiva de tipo 2 de f y g (ERP2) si h cumple: -h(x1,...,xn,0) = f(x1,...,xn) -h(x1,...,xn,t+1) = g(x1,...,xn,t,h(x1,...,xn,t))

Funciones iniciales

Cero:N->N / cero(n)=0 suc:N->N / suc(n)=n+1 πin:Nn->N / πin(x1,...,xn)=xi (función proyección)

Función recursiva primitiva

Una función es recursiva primitiva si se obtiene por finitos pasos de las funciones iniciales a partir de composición, ERP1 y ERP2

Predicado recursivo primitivo

Un predicado RP k-ario es una relación P⊆/Nk Le podemos asignar su función característica Cp(x1,...,xn) = |1 si (x1,...,xn)∈P |0 si no

Codificación de pares (<,>)

La codificación de pares es la función <,>:NxN->N / <x,y> = 2^x (2+1) - 1

Numeración de Godel

Sea k∈/N

Función |.|

Dado x = [a1,...,ak] |.|:N->N / ||x|=long[a1,...,ak]=k ||0| = 0 ||1| = 1

Función .[.]

.[.]:N->N / x[i] = v_pi(x)