Lo tomaron Flashcards
def de conjuntos independientes y bases
probar halt no es computable
enunciar y demotrar teorema de la decuccion
dar la definicion de conjunto finitamente satisfasible
dar la definicion de la regala de modus pones y de prueba
desmostrar que si la funcion se obtiene mediante un ERI a aprtir de un afuncion que computable, entonces es computable
definir esquema recursivo tipo II y funcion recursiva primitiva
final 14 julio de 2022 ejer 1
definir la algebra de bool y motrar que algunas operaciones estan bien definidas
porbar que la funcion halt no es computable
Dar la definicion de cadena de formacion
Definicion de ERII
Demostrar el cardinal [0,1] es mayor que aleph_0
final 12 de dicimbre, ejer 1
teorema de la decicion version semantica y demostrarlos
definicion de recursiva primitiva
definir prueba y demotrar mediante una pruba que (α → α ) es demostrable
porbar que si α es demostrable entonces α es tauto
definir iso
dar la definicion de teminos y de las formulas en los lenguajes de primer orden
X < #P(X)
probar el teorema de la deducion version semantica
definir funciones inciales, funciones recursiva primitiva y esquema recurisvo tipo 2
definir lenguaje de primer orden, alfabeto tambein
de la logica proporcional definir las subformulas
dentro de la logica proposicional, conjuntos consistente y maximal consistente
probar que exieten funciones computables
Dada f ∶ VAR → {0, 1} función.
Existe una única valuación vf ∶ FORM → {0, 1} que extiende a f.
definir cadena de formacion y cadena de formacion minimal
probar que si α es demostrable entonces es tauto
definicion de iso
probar que
α ∈ C(Γ) ⇒ ∃ Γ′ finito tal que Γ′ ⊆ Γ y α ∈ C(Γ′)
impleica el teorema de compasidad
Definir el ERII y funcion recurisva
probar el teorme de la deducion verison semantica
definir funciones iniciales, funciones recursivas primitivas , ERII
Definir lenjugaje de primer orden para ello definir el alfabato tambein
Corolario 24.2
Sea L de primer orden.
Sea I interpretación de L con universo U.
F ∶ U → U isomorfismo.
Entonces, si a ∈ U es distinguible Ô⇒ F(a) = a
DEMO
Sea L un lenguaje de primer orden y sea I una interpretación de L con
universo U.
Sea F ∶ U → U un isomorfismo.
Probar que si A ⊆ U, es expresable ⇒ F(A) ⊆ A
Probar el teorema de la deducion verison semantica
PRobar que si gama es satisfacibles => es consistente
definir prueba de la logica proposicional
definir base y conjunto independinte
Ejercico2 final de 17 de dicimbre 2018
definir cadena de formacion y cadena de formacion minimal
definir iso
Sean Γ ⊆ FORM, α ∈ FORM
α ∈ C(Γ) ⇐⇒ Γ ∪ {¬α} es insatisfacible.
DEMO
definir, prueba y formlas demotrable
definir subformulas
definir conjusntos consistentes y maximal consistentes
Dada f ∶ VAR → {0, 1} función.
Existe una única valuación vf ∶ FORM → {0, 1} que extiende a f.
Existen funciones no computables
Teorema 42
Sea g ∶ N
n+2 → N
Sea q ∶ N
n → N
Sea h ∶ N
n+1 → N tal que se obtiene por ERII a partir de q y g.
Si q y g son computables Ô⇒ h es computable.
Si h se obtiene a partir de g por un ERI y g es computable, entonces h
es computable.
si gama es satisfacible entonces gama es consistemte
sea Gama instatisfasible demotrar y finito, demostra que es maximal con respecto a la independencia
- Si X es infinito no numerable y A es numerable ⇒ X ∪ A ∼ X
- Si X es infinito no numerable y A es numerable ⇒ X − A ∼ X
Base finita e insatisfasible
dar ejemplo de una base instatisfasible e infinita
base, infinita y satisfasible
ejemplos de base finita y satisfasible
ejemplo de maximal consistente finito
dar ejemplo de m.c infitinto
Sea α ∈ F, (p1 → α) tautología.
Si p1 ∉ var(α) ⇒ α es tautología
[0,1] no es numerable
x < #P(x)
Sea α ∈ F.
Sea var(α) = {pj ∈ VAR/pj aparece en α}
Si v, w son valuaciones tales que
v∣var(α) = w∣var(α) ⇒ v(α) = w(α)
Teorema de la deduccion (version axiomática)
Teorema de compacidad implica
α ∈ C(Γ) Ô⇒ ∃ Γ′ finito tal que Γ′ ⊆ Γ y α ∈ C(Γ’)
teorema de completitud
si gama es mc => exite una unica v valuacion / V(gama) =1
teorema de la correctitud
programas = X_0
teorema de compacidad
demo que composicion de funciones computables son computables
comoposicon de funciones RP es RP
