Lógica Proposicional Flashcards
Alfabeto
Sea A un conjunto, con A ≠ ∅.
El conjunto A se llama alfabeto.
Expresión
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 λ.
Lenguaje
Dado A un alfabeto.
Un lenguaje Σ sobre A, con Σ ≠ ∅, es un subconjunto de A^∗
Alfabeto de la lógica proposicional
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
Fórmula
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^∗
Lenguaje de lógica proposicional
El lenguaje de lógica proposicional son las fórmulas.
Cadena de formación
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.
Teorema de CF y FORM
α ∈ FORM ⇐⇒ ∃ X1, . . . , Xn = α CF
Subcadena CF
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”
Cadena de formación minimal
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:
Subfórmula (no la de CF)
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
Valuaciones
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(α)
Clasificación semántica de las fórmulas
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
Equivalencia
Sean α, β ∈ F.
Decimos que α es equivalente a β si v(α) = v(β), ∀v valuación.
Notación: α ≡ β
Conectivos adecuados
Sea C un conjunto de conectivos.
FC = { fórmulas que tienen conectivos de C} ∪ VAR
C es adecuado si
∀α ∈ FORM, ∃ β ∈ FC/β ≡ α
satisfacible e insatisfacible de conjuntos
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.
Consecuencias
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(Γ) = Γ ????
Los 3 teoremas y demos
Sea Γ ⊆ FORM, α ∈ FORM
α ∈ C(Γ) ⇐⇒ Γ ∪ {¬α} es insatisfacible.
Sean Γ = {γ1, . . . , γn} ⊆ FORM, α ∈ FORM
α ∈ C(Γ) ⇐⇒ ((γ1 ∧ ⋅ ⋅ ⋅ ∧ γn) → α) es tautología
Teorema de la deducción (versión semántica) ##
Sean Γ ⊆ FORM, α, β ∈ FORM.
(α → β) ∈ C(Γ) ⇐⇒ β ∈ C(Γ ∪ {α})
DEMO
Conjunto de fórmulas independientes
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
Base
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
Conjunto finitamente satisfacible
Γ 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.
Literal
Se denomina literal a las fórmulas que son variables o variables negadas.
Teorema de Compacidad
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(Γ′)
Definición 49: Axiomas
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.
Regla MODUS PONENS
1 α → β
2 α
———————-
3 β
Decimos que 3 se obtiene por MODUS PONENS (MP) a partir de 1 y 2 .
Sistema axiomático
Está formado por los tres Axiomas y por la Regla MODUS PONENS.
Prueba y formula demostrable
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
Prueba de α a partir de Γ
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: Γ ⊢ α
Teorema de la deducción (versión axiomática)
Sea Γ ⊆ FORM, α, β ∈ FORM
Γ ⊢ (α → β) ⇐⇒ Γ ∪ {α} ⊢ β
Teorema de correctitud
Sea Γ ⊆ FORM, α ∈ F.
Versión débil:
α demostrable (⊢γ) ⇒ α tautología (α∈C(∅))
Versión fuerte:
Γ ⊢ α Ô⇒ α ∈ C(Γ)
Consistente
Sea Γ ⊆ FORM
Γ es consistente si
∄ φ ∈ FORM/Γ ⊢ φ y Γ ⊢ ¬φ
Por otra parte, decimos que Γ es inconsistente si
∃ φ ∈ FORM/Γ ⊢ φ y Γ ⊢ ¬φ
Maximal consistente
Sea Γ ⊆ FORM.
Decimos que Γ es maximal consistente (m.c.) si Γ es consistente y
∀α ∈ FORM:
Caso 1) α ∈ Γ
Caso 2) ∃ φ ∈ F/Γ ∪ {α} ⊢ φ y Γ ∪ {α} ⊢ ¬φ
Teorema de completitud
α ∈ C(Γ) ⇒ Γ ⊢ α
Definición satisface y satisfacible de las formulas
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)
Comparación de semantica y axiomatica
