Lógica Proposicional

Question 1

Satisfacibilidad

Answer 1

Una fórmula α es satisfacible si existe una valuación σ tal que σ(α) = 1

Question 2

Contradicción

Answer 2

Una fórmula α es una contradicción si no es satisfacible, es decir ∀ σ se tiene que σ(α) = 0

Question 3

Tautología

Answer 3

Una fórmula es una tautología si para toda valuación σ se tiene que σ(α) = 1

Question 4

Equivalencia lógica

Answer 4

Dos fórmulas α, β ∈ L(P) son lógicamente equivalentes si α ⇔ β es una tautología

Question 5

DNF

Answer 5

Disyunción de conjunciones

Question 6

CNF

Answer 6

Conjunción de disyunciones

Question 7

Toda fórmula tiene un equivalente en ____ y ____.

Answer 7

CNF y DNF

Question 8

Una fórmula α es consecuencia lógica de Σ si…

Answer 8

Si se tiene que para cada valuación σ tal que σ(Σ) = 1, se tiene que σ(α) = 1

∀ σ, σ(Σ) = 1 ⟹ σ(α) = 1

Question 9

Un conjunto Σ es satisfacible si…

Answer 9

Existe una valuación σ tal que σ(Σ) = 1

En otro caso, es inconsistente.

Question 10

Un conjunto Σ es inconsistente si…

Answer 10

No es satisfacible, o bien si y solo sí Σ ⊨ ■

Question 11

¿Cómo demostrar Σ ⊨ α?

Answer 11

Por inconsistencia de Σ ∪ {¬ α}

Question 12

Equivalencia lógica de conjuntos

Answer 12

Σ₁ ≡ Σ₂ ssi para toda valuación σ se tiene que σ(Σ₁) = σ(Σ₂)

Question 13

Teorema de correctitud para conjuntos

Answer 13

Σ ⊢ ■ ⟹ Σ ⊨ ■ (Σ es inconsistente)

Question 14

Teorema de correctitud para conjuntos

Answer 14

Σ ⊢ ■ ⟹ Σ ⊨ ■ (Σ es inconsistente)

Question 15

Teorema de completitud para conjuntos

Answer 15

Σ ⊨ ■ ⟹ Σ ⊢ ■ (Σ se resuelve a una claúsula vacía)

Question 16

Ejemplo de conectivos funcionalmente completos

Answer 16

{¬, ∧}

Question 17

Algoritmo CNF

Answer 17

Question 18

Modus Ponens

Answer 18

{p, p → q} |= q