| Alfabeto | Conjunto A no vacío |
| Expresión | Una expresión en el alfabeto A es una sucesión finita de elementos de A |
| Longitud | La longitud de una expresión es la cantidad de símbolos del alfabeto que posee la expresión |
| A^n | El conjunto de todas las expresiones de longitud n |
| A* | Todas las expresiones del alfabeto A |
| Lenguaje | Un lenguaje en el alfabeto A es un conjunto Σ⊆A* |
| Alfabeto de la lógica proposicional | Esta dado por:
-los PARENTESIS
-las VARIABLES
-los CONECTIVOS |
| Fórmulas | El conjunto de fórmulas FORM es el conjunto que cumple:
-si pi∈Var ---> pi∈Form
-si α∈Form ---> ¬α∈Form
-si α,β∈Form ---> (α^β), (αvβ), (α->β) ∈Form |
| Cadena de formación | Secuencia X1,...,Xn de expresiones proposicionales tal que para cada eslabón Xi:
1) Xi = pk para algun pk∈Var
2) Xi = ¬Xj para algun 1≤j<i
3)Xi = (Xj*Xk) con *∈{^,v,->} para algunos 1≤j,k<i |
| Subcadena | Sea C=X1,...,Xn una cadena de formación. Xi1,...Xik es subcadena de C si:
-es cadena de formación
-Xik = Xn
-respeta el orden creciente de C |
| Cadena de formación minimal | Tiene una única subcadena que es si misma |
| Complejidad | c(α) = #conectivos que aparecen en α |
| Complejidad binaria | cb(α) = #conectivos binarios (^,v,->) que aparecen en α |
| Peso | p(α) = #parentesis que abren en α - #parentesis que cierran en α |
| Subfórmulas | s(α) es el conjunto definido por:
- Var(α)={pk/pk aparece en α} son subfórmulas
- si α=¬β ---> s(α)={α} u s(β)
- si α=(β1*β2) ---> s(α)={α} u s(β1) u s(β2) |
| Valuación | Una valuación es una función v:Form--->{0,1} tal que:
- v(¬β) = 1 - v(β)
- v((β1^β2)) = min{v(β1); v(β2)}
- v((β1vβ2)) = max{v(β1); v(β2)}
- v((β1->β2)) = max{1-v(β1); v(β2)} |
| Tautología | α es tautología si v(α) = 1 para toda valuación |
| Contradicción | α es contradicción si v(α) = 0 para toda valuación |
| Contingencia | α es contingencia si NO es tautología ni contradicción |
| Equivalentes | Dos formulas α y β se dicen equivalentes si v(α) = v(β) para toda v val
α ≡ β |
| Función booleana | Una función f:{0,1}^n ---> {0,1} |
| Conectivos adecuados | C conjunto de conectivos es adecuado si ∀ α∈Form existe β∈Formc con α ≡ β |
