Definiciones_de_Logica_y_Computabilidad

Vista previa del material en texto

Logica Computacional: Definiciones
Giuliano Scaglioni
2016
1 Cardinales
1.1 Coordinable
Sean A y B conjuntos, decimos que A es coordinable con B (A ∼ B) si existe una función f : A → B
biyectiva.
1.2 Sección Inicial (In)
Al conjunto In = {1, 2, 3, ..., n} se lo denomina sección inicial ∀n ∈ N
1.3 Finito
A conjunto. Decimos que A es finitio si A = ∅ o existe n ∈ N|A ∼ In
1.4 Cardinal
• Card(∅) = 0
• Card(In) = n
• Card(N) = ℵ0
• Card([0, 1]) = c
Notación: card(A) = #A = |A|
1.5 Comparación de cardinales
Sea A conjunto
• #A ≤ #B si existe f : A→ B inyectiva.
• #A ≥ #B si existe f : A→ B sobreyectiva.
• #A = #B si existe f : A→ B biyectiva.
• #A < #B si #A ≤ #B y #A 6= #B.
• #A > #B si #A ≥ #B y #A 6= #B.
1.6 Numerable
A es numerable si A es finito o A ∼ N
2 Lenguajes
2.1 Alfabeto
Sea A conjunto, A 6= ∅, A es un alfabeto.
2.2 Expresión
Una expresión es una secuencia finita de elementos de A o una cadena vacia que representamos con λ
2.3 long(E)
Sea E = a0a1...an una expresión sobre A, se define long(E) = n+ 1 y long(λ) = 0
1
2.4 A*
A∗ =
⋃
n∈N
An, donde An es el conjunto de todas las expresiones sobre A de longitud n, y A0 = λ. A∗ es el
conjunto de todas las expresiones posibles sobre A.
2.5 Lenguaje
A alfabeto, un lenguaje sobre A es un subconjunto Σ 6= ∅ de A∗, (Σ ⊂ A∗)
2.6 Concatenación
A alfabeto, E,F ∈ A∗|E0 = a0...an, F = b0...bs se define EF = a0...anb0...bs
3 Lógica Proposicional: Sintaxis
3.1 Fórmula
Se denomina fórmula de la lógica proposicional a una expresión sobre A (el alfabeto de la lógica proposicional)
que cumple:
• Pi ∈ Form = F
• α ∈ F =⇒ ¬α ∈ F
• α, β ∈ F =⇒ (α ∗ β) ∈ F, ∗ ∈ {∧,∨,→}
3.2 Cadena de formación
Una cadena de formación es una sucesión finita X1, ..., Xn de elementos de A
∗ que verifica la siguiente
propiedad:
Sea 1 ≤ i ≤ n
• Xi ∈ V ar ó
• (∃ 1 ≤ j < i ≤ n|Xi = ¬Xj) ó
• (∃ 1 ≤ j, k < i ≤ n|Xi = (Xj ∧Xk)) ó
• (∃ 1 ≤ j, k < i ≤ n|Xi = (Xj ∨Xk)) ó
• (∃ 1 ≤ j, k < i ≤ n|Xi = (Xj → Xk))
3.3 Eslabón
Se denomina eslabón a un elemento de una cadena de formación.
3.4 Subcadena
Sea X1, ..., Xn una cadena de formación.
Decimos que Xi1 , ..., Xik es una subcadena de la anterior si:
• Xi1 , ..., Xik es una cadena de formación
• 1 ≤ Xi1 < ... < Xik = n
3.5 Cadena de formación minimal
Una cadena de formación es minimal si la unica subcadena que tiene es ella misma.
2
3.6 Complejidad
Sea E una expresión, se define complejidad de E (C(E)) a la cantidad de apariciones de los conectivos
¬,∧,∨,→
3.7 Complejidad binaria
Sea E una expresión, se define complejidad binaria de E (Cb(E)) a la cantidad de apariciones de los conectivos
∧,∨,→
3.8 Peso
Sea E una expresión, se define peso de E (C(E)) a la cantidad de paréntesis que abren menos la cantidad de
paréntesis que cierran.
3.9 Subfórmula
Sea α ∈ F , definimos subfórmulas de α (s(α)) de forma inductiva.
CB) Si C(α) = 0 =⇒ α = Pj ∈ V ar
s(α) = {α}
HI) Si C(α) ≤ n =⇒ conocemos s(α)
TI) Si C(α) = n+ 1
• α = ¬β, defino s(α) = α ∪ s(β)
• α = (β1 ∗ β2), defino s(α) = α ∪ s(β1) ∪ s(β2) ∗ ∈ {→,∧,∨}
4 Lógica Proposicional: Semántica
4.1 Valuación
Una función v : Form→ {0, 1} se llama valuación si:
• v(¬α) = 1− v(α)
• v(α ∧ β) = min{v(α), v(β)}
• v(α ∨ β) = max{v(α), v(β)}
• v(α→ β) = max{1− v(α), v(β)}
4.2 Tautoloǵıa
Sea α ∈ F , decimos que α es una tautoloǵıa si v(α) = 1 ∀v valuación.
4.3 Contradicción
Sea α ∈ F , decimos que α es una contradicción si v(α) = 0 ∀v valuación.
4.4 Contingencia
Sea α ∈ F , decimos que α es una contingencia si no es tautoloǵıa ni contradicción, es decir: ∃ v val. | v(α) = 1
y ∃ w val. | w(α) = 0
4.5 Equivalente
Sea α, β ∈ F . Decimos que α y β son equivalentes si v(α) = v(β), ∀v valuación
Notación: α ≡ β
3
4.6 Función booleana
Es una función f : {0, 1}k → {0, 1} con n ∈ N>0
4.7 Adecuado
Sea C un conjunto de conectivos, C es adecuado si ∀β ∈ F, ∃α ∈ FC | α ≡ β
4.8 Satisface
Sea α ∈ F , V val., decimos que V satisface α si V (α) = 1.
4.9 Satisfacible
Sea α ∈ F es satisfacible si no es una contradiccion. Sea Γ ⊂ F es satisfacible si ∃ v val. | v(α) = 1, ∀α ∈ Γ
4.10 Insatisfacible
Decimos que Γ es insatisfacible si ∀v val, ∃α ∈ Γ |v(α) = 0
4.11 Consecuencia
Sea Γ ⊂ F, α ∈ F . α es consecuencia de Γ si cumple:
• v(Γ) = 1 =⇒ v(α) = 1 ∀v val.
Notación: C(Γ)
4.12 Finitamente satisfacible (f.s.)
Sea Γ ⊂ F . Γ es finitamente satisfacible si todo subconjunto finito de Γ es satisfacible.
4.13 Literal
Un literal es una formula que es una variable o una variable negada.
5 Teoŕıa Axiomática
5.1 Axiomas
Axioma 1 (α→ (β → α))
Axioma 2 (α→ (β → γ))→ ((α→ β)→ (α→ γ))
Axioma 3 ((¬α→ ¬β)→ ((¬α→ β)→ α))
α, β, γ ∈ F
5.2 Prueba
Una prueba es una sucesión finita de fórmulas α1, ..., αn = α tal que αi es un axioma o existe 1 ≤ j, k ≤
i | αk = (αj → αi)
5.3 Modus Ponens
Datos: αj , (αj → αi) obtenemos αi
5.4 Teorema
α ∈ F | α es demostrable.
4
5.5 α se deduce a partir de Γ
Γ ⊂ F, α ∈ F . Decimos que α es demostrable a partir de Γ si existe una prueba de α a partir de Γ α1, ..., αn
tal que:
• αi es un axioma ó
• αi se obtiene a partir de m.p. de dos anteriores ó
• αi ∈ Γ, con 1 ≤ i ≤ n
Notación: Γ ` α (si ∅ ` α =⇒ α es un teorema)
5.6 Consistente
Γ es consistente si @ϕ ∈ F | Γ ` α y Γ ` ¬α
5.7 Maximal Consistente (m.c.)
Γ es maximal consistente si ∀ϕ ∈ F , ϕ ∈ Γ ó Γ ∪ {ϕ} no es consistente.
5.8 Sistema Axiomático Consistente
Un sistema axiomático es consistente si @ϕ ∈ F | `s ϕ y `s ¬ϕ
6 Lenguajes de 1o Orden: Sintaxis
6.1 Alfabeto
Conjunto C de simbolos de constantes C = {c0, c1...}
Conjunto F de funciones F = {fk00 , f
k1
1 ...}
Conjunto P 6= ∅ de predicados P = {P k00 , P
k1
1 ...}
Común para todos los lenguajes de 1o orden:
Variables var = {X0, X1...}
Conectivos {∧,∨,→,¬,∀}
Paréntesis {(, )}
6.2 Término
1. Toda variable es un término
2. Toda constante es un término
3. Si fk ∈ F es un simbolo de función y t1, ..., tk son términos =⇒ fk(t1, ..., tk) es un término
4. t es un término si se construye aplicando 1, 2 y 3 finitas veces.
Notación: term(L)
5
6.3 Fórmula
1. Si P k ∈ P es un śımbolo de predicado y t1, ..., tk son términos =⇒ P k(t1, ..., tk) es una fórmula.
2. Si α es una fórmula =⇒ ¬α es una fórmula.
3. Si α, β son formulas =⇒ (α ∧ β), (α ∨ β) y (α→ β) son fórmulas.
4. Si α es una fórmula y X es una variable =⇒ ∀Xα es una fórmula.
5. α es una fórmula si se construye aplicando 1, 2, 3 y 4 finitas veces.
Convención: escribimos ∃Xα en lugar de ¬∀X¬α
6.4 Término cerrado
Un término es cerrado si no tiene variables.
6.5 Variable ligada
Una aparición de una variable esta ligada si esta al alcance de un cuantificador. Si todas sus apariciones son
ligadas entonces es una variable ligada.
6.6 Variable libre
Una aparición de una variable esta libre si no esta ligada. Si todas las apariciones son libres la variable esta
libre.
6.7 Enunciado o sentencia
Un enunciado o sentencia es una formula con todas sus variables ligadas.
7 Lenguajes de 1o Orden: Semántica
7.1 Interpretación
I de un lenguaje de primer L orden consta de:
1. Un conjunto no vaćıo UI llamado universo o dominio.
2. Las siguientes interpretaciones para los simbolos de L:
(a) Si c ∈ C =⇒ c se interpreta como un elemento cI ∈ UI fijo.
(b) Si fk ∈ F =⇒ fk se interpreta como una función fkI : UkI → UI
(c) Si P k ∈ P =⇒ P k se interpreta como un predicado P kI ⊂ UI
7.2 Valuación
Fijada un interpretación I una valuación para I es una función v : var → UI .
Para interpretar términos extendemos v a v̄ : term→ UI y sea t término:
1. Si t ∈ var =⇒ v̄(t) = v(t)
2. Si t ∈ C =⇒ v̄(t) = cI
3. Si t = fk(t1, ..., tk), f
k ∈ F =⇒ v̄(t) = fkI (v̄(t1), ..., v̄(tk))
6
7.3 Vxi=a
Sea v una valuación para I, y sea a ∈ UI , definimos la valuación
Vxi=a : var → UI/Vxi=a(y) =
{
v(y) y 6= xi
a y = xi
7.4 Interpretación de fórmulas
Sea I de L de primer orden y v una valuación para esa I. Decimos que α ∈ Form(L) es verdaderaen I
bajo la valuación v si:
1. VI,v(Pk(t1, ..., tk))
2. vI,v(¬α) = 1− vI,v(α)
3. vI,v(α1 ∧ α2) = min{vI,v(β1), vI,v(β2)}
4. vI,v(α1 ∨ α2) = max{vI,v(β1), vI,v(β2)}
5. vI,v(α1 → α2) = max{1− vI,v(β1), vI,v(β2)}
6. vI,v(∀xiα) = 1↔ vI,vxi=a(α), ∀a ∈ UI
7. vI,v(∃xiα) = 1↔ vI,vxi=a(α), para algún a ∈ UI
7.5 Satisfacible
Sea L de primer orden y α ∈ F . α es satisfacible si ex́ıste una I de L y una v val. v : var → UI | vI,v(α) = 1
7.6 Verdadera o válida en I
α es verdadera o válida en I si vI,v(α) = 1∀v val.
7.7 Universalmente válida
α es universalmente válida si vI,v(α) = 1∀I,∀v
7.8 Consecuencia semántica
Γ ⊂ F, α ∈ F, α es consecuencia semántica de Γ si vI,v(Γ) = 1 =⇒ vI,v(α) = 1
Notación: Γ |= α
7.9 Lenguaje con igualdad
Es un lenguaje de primer orden que tiene un predicado binario que siempre se interpreta con la igualdad.
7.10 Expresa
L de primer orden. I, α fórmula con una única variable libre α(x). A = {t ∈ UI |vI,vx=t(α(x)) = 1 } Decimos
que α expresa A.
7.11 Expresable
Decimos que A conjunto es expresable en I si ∃α(x) ∈ F que lo exprese.
7.12 Distinguible
L de primer orden, I interpretación con universo UI , a ∈ UI , se dice que a es distinguible si {a} es expresable.
7
7.13 Isomorfismo
L de primer orden, I1, I2 interpretaciones con universos U1 y U2.
Una función F : U1 → U2 es isomorfismo si
1. F es biyectiva
2. Sea c ∈ C y cI1 , cI2 sus respectivas interpretaciones =⇒ F (cI1) = cI2
3. fk ∈ F =⇒ F (fkI1(t1, ..., tk)) = f
k
I2(F (t1), ..., F (tk))
4. P ∈ P =⇒ (a1, ..., ak) ∈ P kI1 ↔ (F (a1), ..., F (ak)) ∈ P
k
I2
8 Lenguaje S
8.1 Recursión Primitiva Tipo I (ERI)
Sea f : N→ N, decimos que f se obtiene por un ERI a partir de g : N2 → N si: f(0) = k y f(n+1) = g(n, f(n))
8.2 Recursion Primitiva Tipo II (ERII)
Sean f : Nn+1 → N, g : Nn+2 → N y h : Nn → N funciones.
Decimos que f se obtiene por un ERII a partir de g y h si:
f(x1, ..., xn, 0) = h(x1, ..., xn)
f(x1, ..., xn, t+ 1) = g(x1, ..., xn, t, f(x1, ..., xn, t))
8.3 Funciones iniciales
• cero : N→ N/cero(n) = 0
• suc : N→ N/suc(n) = n+ 1
• Πki : Nk → N/Πki (x1, ..., xn) = xi
8.4 Clase PRC
Una clase C de funciones totales es PRC si
1. Las funciones iniciales estan en C
2. Si f se obtiene a partir de funciones que estan en C mediante composición o recursion primitiva =⇒
f ∈ C
8.5 Funcion RP
Una función es RP si se puede obtener a partir de las funciones iniciales aplicando un número finito de
composiciones y/o recursiones primitivas.
8.6 Funciones de Gödel
Sea k ∈ N ≥ 1, para cada k se define la función
[·, ..., ·] : Nk+1 → N/[(a0, ..., ak)] = P a00 · ... · P
ak
k
Con Pj < Pj+1 primos consecutivos
8
8.7 Indicadores de Gödel
| · | : N→ N/|n| =

long(n) n > 1
0 n = 0
1 n = 1
·[·] : N2 → N/x[i] =
{
VPi x 6= 0
0 x = 0
Nota: Sea n > 0, n = P a00 · ... · P
ak
k , long(n) = k + 1
8.8 Halt
Halt : N2 → N/Halt(x, y) =

1 si el programa de código y
termina ante la entrada x
0 sino
8.9 Programas Universales
Para cada n > 0 se define
Φn(x1, ..., xn, e) = Ψ
n
P (x1, ..., xn) =

y si y es la salida del programa
P ante la entrada (x1, ..., xn)
↑ sino
Donde P es el programa de código e
9