Lo tomaron Flashcards

1
Q

def de conjuntos independientes y bases

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

probar halt no es computable

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

enunciar y demotrar teorema de la decuccion

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

dar la definicion de conjunto finitamente satisfasible

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

dar la definicion de la regala de modus pones y de prueba

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

desmostrar que si la funcion se obtiene mediante un ERI a aprtir de un afuncion que computable, entonces es computable

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

definir esquema recursivo tipo II y funcion recursiva primitiva

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

final 14 julio de 2022 ejer 1

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

definir la algebra de bool y motrar que algunas operaciones estan bien definidas

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

porbar que la funcion halt no es computable

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Dar la definicion de cadena de formacion

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Definicion de ERII

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Demostrar el cardinal [0,1] es mayor que aleph_0

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

final 12 de dicimbre, ejer 1

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

teorema de la decicion version semantica y demostrarlos

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

definicion de recursiva primitiva

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

definir prueba y demotrar mediante una pruba que (α → α ) es demostrable

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

porbar que si α es demostrable entonces α es tauto

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

definir iso

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

dar la definicion de teminos y de las formulas en los lenguajes de primer orden

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

X < #P(X)

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

probar el teorema de la deducion version semantica

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

definir funciones inciales, funciones recursiva primitiva y esquema recurisvo tipo 2

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

definir lenguaje de primer orden, alfabeto tambein

A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
de la logica proporcional definir las subformulas
26
dentro de la logica proposicional, conjuntos consistente y maximal consistente
27
probar que exieten funciones computables
28
Dada f ∶ VAR → {0, 1} función. Existe una única valuación vf ∶ FORM → {0, 1} que extiende a f.
29
definir cadena de formacion y cadena de formacion minimal
30
probar que si α es demostrable entonces es tauto
31
definicion de iso
32
probar que α ∈ C(Γ) ⇒ ∃ Γ′ finito tal que Γ′ ⊆ Γ y α ∈ C(Γ′) impleica el teorema de compasidad
33
Definir el ERII y funcion recurisva
34
probar el teorme de la deducion verison semantica
35
definir funciones iniciales, funciones recursivas primitivas , ERII
36
Definir lenjugaje de primer orden para ello definir el alfabato tambein
37
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
38
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
39
Probar el teorema de la deducion verison semantica
40
PRobar que si gama es satisfacibles => es consistente
41
definir prueba de la logica proposicional
42
definir base y conjunto independinte
43
Ejercico2 final de 17 de dicimbre 2018
44
definir cadena de formacion y cadena de formacion minimal
45
definir iso
46
Sean Γ ⊆ FORM, α ∈ FORM α ∈ C(Γ) ⇐⇒ Γ ∪ {¬α} es insatisfacible. DEMO
47
definir, prueba y formlas demotrable
48
definir subformulas
49
definir conjusntos consistentes y maximal consistentes
50
Dada f ∶ VAR → {0, 1} función. Existe una única valuación vf ∶ FORM → {0, 1} que extiende a f.
51
Existen funciones no computables Teorema 42
52
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.
53
Si h se obtiene a partir de g por un ERI y g es computable, entonces h es computable.
54
si gama es satisfacible entonces gama es consistemte
55
sea Gama instatisfasible demotrar y finito, demostra que es maximal con respecto a la independencia
56
1. Si X es infinito no numerable y A es numerable ⇒ X ∪ A ∼ X 2. Si X es infinito no numerable y A es numerable ⇒ X − A ∼ X
57
Base finita e insatisfasible
58
dar ejemplo de una base instatisfasible e infinita
59
base, infinita y satisfasible
60
ejemplos de base finita y satisfasible
61
ejemplo de maximal consistente finito
62
dar ejemplo de m.c infitinto
63
Sea α ∈ F, (p1 → α) tautología. Si p1 ∉ var(α) ⇒ α es tautología
64
[0,1] no es numerable
65
#x < #P(x)
66
Sea α ∈ F. Sea var(α) = {pj ∈ VAR/pj aparece en α} Si v, w son valuaciones tales que v∣var(α) = w∣var(α) ⇒ v(α) = w(α)
67
Teorema de la deduccion (version axiomática)
68
Teorema de compacidad implica α ∈ C(Γ) Ô⇒ ∃ Γ′ finito tal que Γ′ ⊆ Γ y α ∈ C(Γ')
69
teorema de completitud
70
si gama es mc => exite una unica v valuacion / V(gama) =1
71
teorema de la correctitud
72
#programas = X_0
73
teorema de compacidad
74
demo que composicion de funciones computables son computables
75
comoposicon de funciones RP es RP