| Valuación modificada | Dada una val v:Var->Ui, la val modificada en la variable xi por a∈Ui es v_xi=a (xj) = |
| Alfabeto de la log de 1er orden | -Var
-Paréntesis
-Conectivos
-Cuantificadores
-Símbolos de constante
-Símbolos de función
-Símbolos de predicado |
| Términos | El conjunto de términos de L leng de primer orden cumple:
-Las var son términos
-Los símbolos de cte son términos
-Si fk es un símbolo de función y t1,...,tk son términos ---> fk(t1,...,tk) es término |
| Fórmulas | El conjunto de fórmulas de L (leng de 1er orden) cumple:
- Si Pk es un símbolo de predicado y t1,...,tk son términos ---> Pk(t1,...,tk) es una fórmula
- Si α, β son fórmulas ---> (α^β), (αvβ), (α->β), ¬α son fórmulas
-Si α es fórmula y xi∈Var ---> ∀xiα, ∃xiα son formulas |
| Variable libre | Sea xi una variable que aparece en un término de α. Decimos que xi es libre si no es alcanzada por un cuantificador (∃ o ∀) en NINGUNA aparición |
| Variable ligada | Sea xi una variable que aparece en un término de α. Decimos que xi es ligada si es alcanzada por un cuantificador (∃ o ∀) en TODAS sus apariciones |
| Término cerrado | No tiene variables |
| Sentencia/Enunciado | Fórmula en la cual todas las variables son ligadas |
| Interpretación | Una interpretación I de un lenguaje de 1er orden L es:
- un conjunto Ui no vacío (universo de la interpretación)
- para cada c símbolo de cte, un elemento ci∈Ui
- para cada fk símbolo de función, una funció n fik:Uik->Ui
- para cada Pk símbolo de predicado, una relación Pik⊆Uik
I=<Ui, {ci}, {fik}, {Pik}> |
| Valuación en I | Una valuación en una interpretación I de L es una función v:Var->Ui
Podemos extenderla de manera única a una funcion v':Term(L)->Ui |
| Valuación modificada | Dada una val v:Var->Ui, la val modificada en la variable xi por a∈Ui es |
| Valor de verdad | El valor de verdad de una fórmula es una funcion Vi,v : Form(L)->{0,1} tal que:
- α=Pk(t1,...,tk): Vi,v(α)=|1 si (v'(t1),...,v'(tk))∈Pik
| 0 si no
- α=∀xi β : Vi,v(α) = |1 si ∀a∈Ui Vi,v_xi=a (β) = 1
|0 si no
- α=∃xi β : Vi,v(α) = |1 si ∃a∈Ui / Vi,v_xi=a (β) = 1
|0 si no
- α=(α1^α2): Vi,v(α) = min{Vi,v(α1); Vi,v(α2)}
- α=(α1vα2): Vi,v(α) = max{Vi,v(α1); Vi,v(α2)}
- α=(α1->α2): Vi,v(α) = max{1-Vi,v(α1); Vi,v(α2)}
- α=¬α1: Vi,v(α) = 1-Vi,v(α1) |
| Satisfacible | α es satisfacible si existen I y v tal que I⊧α[v], es decir, tal que Vi,v(α)=1 |
| Válida/verdadera | α es válida o verdadera en I si ∀v valuación en I sucede que I⊧α (Vi(α)=1 para cualquier valuación) |
| Universalmente válida | α es universalmente valida si ∀I interpretacion ⊧α (V(α)=1) |
| Consecuencia | α es consecuencia de Γ si ∀I interpretación y ∀v val con I⊧γ[v] ∀γ∈Γ ---> I⊧α[v]
Se escribe Γ⊧α |
