Lógica Proposicional

Question 1

Alfabeto

Answer 1

Sea A un conjunto, con A ≠ ∅.
El conjunto A se llama alfabeto.

Question 2

Expresión

Answer 2

Sea A un alfabeto
Una expresión es una sucesión finita de elementos de A o la cadena vacía, a la cual llamamos λ.

Question 3

Lenguaje

Answer 3

Dado A un alfabeto.

Un lenguaje Σ sobre A, con Σ ≠ ∅, es un subconjunto de A^∗

Question 4

Alfabeto de la lógica proposicional

Answer 4

A = VAR ∪ {(, )} ∪ C
Siendo:
VAR = {pn/n ∈ N} = {p0, p1, p2, . . . }
Y los elementos del conjunto de conectivos C = {∧,∨, →,¬}:
∧: Conjunción
∨: Disyunción
→: Implicación
¬: Negación

OBS: Card(VAR) = ℵ0

Question 5

Fórmula

Answer 5

Definimos fórmula como:
1. VAR ⊆ FORM
2. α ∈ F ⇒ ¬α ∈ F
3. α, β ∈ F ⇒ (α ∧ β), (α ∨ β), (α → β) ∈ F
4. α ∈ A^∗ es fórmula si se obtiene aplicando finitas veces 1., 2. y 3.

Notación: Al conjunto de fórmulas del lenguaje proposicional lo llamamos FORM o F ⊂ A^∗

Question 6

Lenguaje de lógica proposicional

Answer 6

El lenguaje de lógica proposicional son las fórmulas.

Question 7

Cadena de formación

Answer 7

Una sucesión finita X1, X2, . . . , Xn de expresiones de A^∗ es una cadena de formación (CF) si:

Caso 1) Xi ∈ VAR (1≤ i ≤ n)
Caso 2) ∃ j < i/Xi = ¬Xj (1 ≤ i, j ≤ n )
Caso 3) ∃ s, t < i/Xi = (Xs ∗ Xt) (1 ≤ s, t, j ≤ n, ∗ ∈ {∧,∨, →})

Cada Xi se llama eslabón.

Question 8

Teorema de CF y FORM

Answer 8

α ∈ FORM ⇐⇒ ∃ X1, . . . , Xn = α CF

Question 9

Subcadena CF

Answer 9

Sea la cadena de formación X1, . . . Xn.
Decimos que Xi1, Xi2, . . . , Xik es una subcadena si:
1. Es cadena de formación.
2. Xik = Xn
3. 1 ≤ i1 < i2 < ⋅ ⋅ ⋅ < ik = n

“El último eslabón tiene que ser el mismo”

Question 10

Cadena de formación minimal

Answer 10

Una cadena de formación es minimal si la única subcadena que tiene es ella misma.

Prop:
-#S(α) ≤ cantidad de eslabones
util para demostrar que es minimal -> si tiene #S(α) = 4 = cantidad de eslabones -> es minimal
- β ∈ S(α) ⇒ β esta en toda CF de α

Observación:
1. Toda fórmula tiene una cadena minimal.
2. Puede tener más de una subcadena minimal.
3. Notemos que “minimal” implica la existencia de una relación de orden. En las cadenas de formación, esta relación de orden está definida como sigue:

Question 11

Subfórmula (no la de CF)

Answer 11

Sea α ∈ F.
- Si c(α) = 0 ⇒ α = pj
En este caso, el conjunto de subfórmulas de α es: S(α) = {pj}

• Si c(α) > 0
  1. α = ¬β -> S(α) = {α} ∪ S(β)
  2. α = (β1 ∗ β2) -> S(α) = {α} ∪ S(β1) ∪ S(β2)

Notación: S(α) es el conjunto de subfórmulas de α.

¡Atención! prop:
- #S(β) ≤ C(β) + #VAR(β)
- #S((β1 ∗ β2)) ≤ #S(β1) + #S(β2) + 1

Question 12

Valuaciones

Answer 12

Una valuación (o asignación) es una función v ∶ FORM → {0, 1} que verifica:
∀α ∈ F 1) V(¬α) = 1 − v(α)
∀α, β ∈ F 2) v (α ∧ β) = mın{v(α), v(β)}
∀α, β ∈ F 3) V(α ∨ β) = max{v(α), v(β)}
∀α, β ∈ F 4) V(α → β) = max{1 − v(α), v(β)}

Teorema 10
Dada f ∶ VAR → {0, 1} función.
Existe una única valuación vf ∶ FORM → {0, 1} que extiende a f.

Teorema 11
Sea α ∈ F, var(α) = {pj ∈ VAR/pj aparece en α}

Si v, w son valuaciones tales que v∣var(α)
= w∣var(α) ⇒ v(α) = w(α)

Question 13

Clasificación semántica de las fórmulas

Answer 13

Sea α ∈ F.
1. α es tautología si v(α) = 1 ∀v valuación.
2. α es contradicción si v(α) = 0 ∀v valuación.
3. α es contingencia si:
- ∃ v valuación/v(α) = 1
- ∃ w valuacíon/w(α) = 0

Proposición 2
Sea α ∈ F, (p1 → α) tautología.
Si p1 ∉ var(α) ⇒ α es tautología

Ejemplos
α = (p1 ∧ ¬p1) es una contradicción.
α = (p1 ∨ ¬p1) es una tautología

Question 14

Equivalencia

Answer 14

Sean α, β ∈ F.
Decimos que α es equivalente a β si v(α) = v(β), ∀v valuación.

Notación: α ≡ β

Question 15

Conectivos adecuados

Answer 15

Sea C un conjunto de conectivos.
FC = { fórmulas que tienen conectivos de C} ∪ VAR
C es adecuado si
∀α ∈ FORM, ∃ β ∈ FC/β ≡ α

Question 16

satisfacible e insatisfacible de conjuntos

Answer 16

Sea Γ ⊆ F.
Decimos que Γ es satisfacible si ∃ v valuación tal que v(α) = 1 ∀α ∈ Γ.
Notación: v(Γ) = 1

Decimos que Γ es insatisfacible si ∄ v valuación tal que v(Γ) = 1.
Es decir, ∀v val. ∃ α ∈ Γ / v(α) = 0

OBS:
- v(Γ) = 0 NO existe
- Γ = ∅ es satisfacible por todas las valuaciones.
- Γ = FORM es insatisfacible.

Question 17

Consecuencias

Answer 17

Sean Γ ⊆ FORM, α ∈ FORM
- α ∈ C(Γ) si ∀v valuación (v(Γ) = 1 ⇒ v(α) = 1 )
- α∉ C(Γ) si ∃ v valuación/v(Γ) = 1 y v(α) = 0

propiedades:
- Γ⊂ C(Γ)
- Γ1⊂ Γ2 => C(Γ1)⊂ C(Γ2)
- C(C(Γ)) = C(Γ)
- C(Γ1) ∩ C(Γ1) = C(Γ1∩ Γ1) OJO creo que es asi

OBS
- C(∅) = tautologías = {α ∈ F/α es tautología}
- Γ insatisfacible, C(Γ) = FORM
-Tautologías ⊆ C(Γ), Γ ⊆ FORM
- Γ ⊆ FORM, C(Γ) es dependiente
- Γ santificable => C(Γ) santificable
- Γ tauto => C(Γ) = Γ ????

Question 18

Los 3 teoremas y demos

Answer 18

Sea Γ ⊆ FORM, α ∈ FORM
α ∈ C(Γ) ⇐⇒ Γ ∪ {¬α} es insatisfacible.

Sean Γ = {γ1, . . . , γn} ⊆ FORM, α ∈ FORM
α ∈ C(Γ) ⇐⇒ ((γ1 ∧ ⋅ ⋅ ⋅ ∧ γn) → α) es tautología

Question 19

Teorema de la deducción (versión semántica) ##

Answer 19

Sean Γ ⊆ FORM, α, β ∈ FORM.
(α → β) ∈ C(Γ) ⇐⇒ β ∈ C(Γ ∪ {α})

DEMO

Question 20

Conjunto de fórmulas independientes

Answer 20

Sea Γ un conjunto de fórmulas.
Decimos que Γ es un conjunto de fórmulas independientes si para todo
α ∈ Γ se tiene que α ∉ C(Γ − {α}).
En caso contrario, Γ es dependiente

• si es independiente:
  ∀α ∈ Γ, ∃ v valuación / V(Γ − {α})=1y V(α)=0
  . no lo es
• Exite..

Como pensar:
si la formula la pude deducir con las de mas form de Γ no es independiente

obs
- Γ = {p1, (p1 → p2)} independientes.
- Γ = {p1, p2, (p1 → p2)} no es independiente.
- Γ contiene tauto ⇒ Γ dependinete
- Γ es independiente y Σ ⊆ Γ ⇒ Σ es independiente

Conjuntos infintios independientes
- Γ = VAR
- Γ =¬VAR

Question 21

Base

Answer 21

Sea Γ ⊆ Form
Decimos que Γ es una base si:
1. Es independiente.
2. Es maximal con respecto a la independencia:
- supongo que ∃ α ∈ FROM y α ∉Γ / Γ ∪ {α} independiente
- Γ ⊆ Σ y Σ es indep => Γ= Σ
- Σ= Γ ∪ {α}, con α ∉ Γ => Σ es dependiente.

Propiedades:
- Γ finito y base => Γ es instatisfacible
- VAR son base

• si Γ es insatisfasible e independiente => entonces no se puede agregar nada sin que deje de ser independiente

Question 22

Conjunto finitamente satisfacible

Answer 22

Γ es finitamente satisfacible (f.s.) si todo subconjunto finito de Γ es
satisfacible.

si no es f.s
∃ Γ’ ⊆ Γ / Γ’ es finito e insatisfacible

Lema 16.1
Sea Γ f.s., pi ∈ VAR
Entonces Γ ∪ {pi} es f.s. o Γ ∪ {¬pi} es f.s.

Question 23

Literal

Answer 23

Se denomina literal a las fórmulas que son variables o variables negadas.

Question 24

Teorema de Compacidad

Answer 24

Sea Γ un conjunto.
Γ es satisfacible ⇐⇒ Γ es finitamente satisfacible

Propocisión 3
Son equivalentes:
1 Teorema de Compacidad
2 Γ es insatisfacible ⇐⇒ ∃ Γ′ ⊆ Γ finito tal que Γ ′es insatisfacible.
3 α ∈ C(Γ) ⇒ ∃ Γ′ finito tal que Γ′⊆ Γ y α ∈ C(Γ′)

Question 25

Definición 49: Axiomas

Answer 25

Sean α, β, γ ∈ F, se definen los siguiente axiomas:
Axioma 1) (α → (β → α))
Axioma 2) ((α → (β → γ)) → ((α → β) → (α → γ)))
Axioma 3) ((¬α → ¬β) → ((¬α → β) → α))

Observación:
Los axiomas de la Definición 49 son tautologías.

Question 26

Regla MODUS PONENS

Answer 26

1 α → β
2 α
———————-
3 β

Decimos que 3 se obtiene por MODUS PONENS (MP) a partir de 1 y 2 .

Question 27

Sistema axiomático

Answer 27

Está formado por los tres Axiomas y por la Regla MODUS PONENS.

Question 28

Prueba y formula demostrable

Answer 28

Sea α ∈ F.
Una prueba para α es una suseción finita de fórmulas α1, α2, . . . , αn tal
que:
1. αn = α
2. Cada αk es un axioma, o se obtiene aplicando MP a αi y αj . Es decir, αk es axioma o αj = (αi → αk).

Definición 53: Teorema
Sea α ∈ F.
α es demostrable si existe una prueba de α.
En este caso, α se llama teorema

Question 29

Prueba de α a partir de Γ

Answer 29

Sea Γ ⊆ FORM, α ∈ F.
Decimos que α se deduce de Γ si existe una sucesión finita de fórmulas α1, α2, . . . , αn = α que verifica alguno de los siguientes casos

Caso 1) αi ∈ Γ1
Caso 2) αi es un axioma
Caso 3) αi se obtiene por MP a partir de anteriores: j = (αk → αi) y
αk, siendo j, k ≤ i.

A α1, α2, . . . , αn = α la denominamos prueba de α a partir de Γ.
Cuando decimos que αi ∈ Γ decimos que αi es un dato.

Notación: Γ ⊢ α

Question 30

Teorema de la deducción (versión axiomática)

Answer 30

Sea Γ ⊆ FORM, α, β ∈ FORM

Γ ⊢ (α → β) ⇐⇒ Γ ∪ {α} ⊢ β

Question 31

Teorema de correctitud

Answer 31

Sea Γ ⊆ FORM, α ∈ F.
Versión débil:
α demostrable (⊢γ) ⇒ α tautología (α∈C(∅))

Versión fuerte:
Γ ⊢ α Ô⇒ α ∈ C(Γ)

Question 32

Consistente

Answer 32

Sea Γ ⊆ FORM
Γ es consistente si
∄ φ ∈ FORM/Γ ⊢ φ y Γ ⊢ ¬φ

Por otra parte, decimos que Γ es inconsistente si
∃ φ ∈ FORM/Γ ⊢ φ y Γ ⊢ ¬φ

Question 33

Maximal consistente

Answer 33

Sea Γ ⊆ FORM.
Decimos que Γ es maximal consistente (m.c.) si Γ es consistente y
∀α ∈ FORM:
Caso 1) α ∈ Γ
Caso 2) ∃ φ ∈ F/Γ ∪ {α} ⊢ φ y Γ ∪ {α} ⊢ ¬φ

Question 34

Teorema de completitud

Answer 34

α ∈ C(Γ) ⇒ Γ ⊢ α

Question 35

Definición satisface y satisfacible de las formulas

Answer 35

Sean α ∈ F y v valuación.
Decimos que v satisface α si v(α) = 1

Definicion 42
Sea α ∈ F.
Decimos que α es satisfacible si ∃ v valuación tal que v(α) = 1.

Otra manera (equivalente) de escribir esta definición es:
∃ v valuación (α ∈ Γ ⇒ v(α) = 1)

Question 36

Comparación de semantica y axiomatica