lógica de primer orden

Question 1

Alfabeto

Answer 1

El alfabeto que utilizamos para lógica de primer orden se define como:
AF,C,P = VAR ∪ CONECTIVOS ∪ { ( , ) } ∪ F ∪ C ∪ P

Donde:
- VAR = {x0, x1, x2, . . . } Notación: xi, yi,zi,wi
- CONECTIVOS = {∧,∨, →,¬} ∪ {∀, ∃}
- F = es un conjunto cuyos elementos se llaman símbolos de función. F podría ser vacío. Notación: …
- C = es un conjunto cuyos elementos se llaman símbolos de constantes. Podría ser vacío.
Notación: ci, di, ki
P = es un conjunto cuyos elementos se llaman símbolos de predicado. P ≠ ∅
Notación: …

Question 2

Término a partir de un alfabeto

Answer 2

Sea A un alfabeto.
1. Toda variable es un término.
2. Toda constante es un término.
3. Si t1, t2, . . . , tk son términos y f^k ∈ F ⇒ f^k (t1, t2, . . . , tk) es un término
4. Cualquier expresión de A^∗ que se obtiene aplicando finitas veces (1), (2) y (3) es un término.
Notación: TERM

Question 3

Término cerrado

Answer 3

Un término se llama cerrado si no tiene variables.

Question 4

Fórmula a partir de un alfabeto

Answer 4

Sea A un alfabeto.
1. Si t1, . . . , tk ∈ TERM y P^k ∈ P ⇒ P^k(t1, . . . , tk) es una fórmula. (Esta se denomina fórmula atómica.)

2. α ∈ FORM ⇒ ¬α ∈ FORM
3. α, β ∈ FORM ⇒ (α ∧ β), (α ∨ β), (α → β) ∈ FORM
4. α ∈ FORM, x ∈ VAR ⇒ ∀x α ∈ FORM
5. α ∈ FORM, x ∈ VAR ⇒ ∃ x α ∈ FORM
6. Cualquier expresión de A^∗ que se obtiene aplicando finitas veces (1), (2), (3), (4) y (5) es una fórmula.

Notación: F = FORM

Question 5

Lenguaje de 1er. orden

Answer 5

Dado un alfabeto A, L ⊆ A^∗ es un lenguaje de primer orden si L = FORM ∪ TERM

Notación: L =< C, F,P >

Question 6

Enunciado

Answer 6

Una fórmula se llama enunciado o sentencia si todas sus variables están
ligadas.

Question 7

Valuaciones

Answer 7

Dado un lenguaje de primer orden y una interpretación I de L, definimos
valuación como una función v ∶ VAR → UI.

Question 8

Interpretación

Answer 8

Dado un alfabeto A y un lenguaje L de primer orden, una interpretación I de L consiste en:

1. U ≠ ∅ Siendo U un conjunto llamado universo.
2. Si c ∈ C, entonces c se interpreta como c_I ∈ U.
3. f^k ∈ F, entonces f^k se interpreta como una función cuyo dominio es U^k y el codominio U.
4. P^k ∈ P, entonces P^k se interpreta como una relación k−aria en U. Es decir, P{^K, _I} ⊆ U^k

I se llama interpretación de L o L−estructura.

Question 9

Valuación extendida

Answer 9

Dada v una valuación, definimos v¯ ∶ TERM → UI que verifica:

1. v¯(xi) = v(xi) , xi ∈ VAR
2. v¯(c) = cI , c ∈ C
3. v¯(f^k(t1, . . . , tk)) = f^kI f (v¯(t1), . . . , v¯(tk)) f^k ∈ F y t1, . . . , tk ∈ TERM

Entonces decimos que v¯ es extensión de v.

Question 10

Valuación modificada

Answer 10

dificil de poner aca

Question 11

Fórmula verdadera y falsa

Answer 11

Sean L un lenguaje de 1er. orden, v ∶ VAR → UI, α ∈ FORM y VI,v(α) ∶ FORM → {0, 1}

• α es verdadera en la interpretación I con valuación v: * VI,v(α) = 1 * I ⊧ α[v]

α es falsa en la interpretación I con valuación v: VI,v(α) = 0

Question 12

Conjuntos expresables

Answer 12

Sea L un lenguaje de primer orden.
Sea I una interpretación de L con universo U.
Sea A ⊆ U.

Decimos que A es expresable o definible en I si existe α ∈ FORM con
una única variable libre y todas las demás variables ligadas tal que
VI,vx=a (α(x)) = 1 ⇐⇒ x ∈ A
Dicho de otro modo:
A = {a ∈ UI/VI,vx=a (α(x)) = 1}
Es decir
Si x ∈ A ⇒ VI,vx=a (α(x)) = 1
Si x ∉ A ⇒ VI,vx=a (α(x)) = 0

Notación: α(x), donde x es la variable libre.

prop
1. A ⊆ U, A es expresable Ô⇒ A
c
es“Si un conjunto es expresable, entonces su
complemento también
lo es.”
expresable.
2. A, B ⊆ U expresables Ô⇒ A∩B, A∪B, A−B y A△B son expresables.
3. ∅ es expresable y U es expresable.

Question 13

Elementos distinguibles

Answer 13

Sea L un lenguaje de primer orden.
Sea I una interpretación de L con universo U.
Sea a ∈ U.

Decimos que a es distinguible si {a} es expresable.

Question 14

Isomorfismo

Answer 14

Sea L un lenguaje de primer orden. Sean I1 e I2 interpretaciones de L
con universos U1 y U2 respectivamente.

Una función F ∶ U1 → U2 se llama isomorfismo si:

1. F es biyectiva.
2. c ∈ C y cI1 ∈ U2 y cI2 ∈ U2 son respectivas interpretaciones, entonces F(cI1) = cI2
3. Dada f^k ∈ F entonces
4. Dado P^k∈ P entonces

Notación: I1 ≈ I2
A veces también se nota I1 ≈F≈ I2, que significa que ambas interpretaciones son isomorfas y, además, F es un isomorfismo.

Lema 23.1
Sea L un lenguaje de primer orden.
Sean I1 e I2 interpretaciones de L.
Sea h un isomorfismo de I1 a I2.
Sea v una valuación en I1.
Entonces
h ○ v = h ○ v

Teorema 24
Sea L un lenguaje de primer orden.
Sean I1 e I2 interpretaciones.
Sea h un isomorfismo de I1 a I2.
Sea v una valuación en I1.
Sea α ∈ FORM.
Entonces
I1 ⊧ α[v] ⇐⇒ I2 ⊧ α[h ○ v]

Question 15

Fórmulas equivalentes

Answer 15

Dos fórmulas son equivalentes en lenguaje de primer orden sí y sólo sí su valor de verdad es el mismo para cualquier interpretación y cualquier valuación.

Corolario 24.1
Sea L de primer orden. I1 e I2 interpretaciones de L: I1 ≈h≈ I2.
α enunciado de L

Entonces I1 es un modelo de α ⇐⇒ I2 es un modelo de α.

Es decir I1 ⊧ α[v] ∀v val. en I1 ⇐⇒ I2 ⊧ α[w] ∀w val. en I2

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

Corolario 24.3
Sea L un lenguaje de primer orden y sea I una interpretación de L con
universo U.
Sea F ∶ U → U un isomorfismo.

Entonces si A es expresable ⇒ F(A) ⊆ A (F(a) ∈A ∀a∈A) ∀A ⊆ U

Corolario 24.4
Sea L un lenguaje de primer orden.
Sean I1 e I2 interpretaciones e I1 ≈ I2.
Si a ∈ U1 es distinguible en I1 ⇒ h(a) ∈ U2 es distinguible en I2