La notaciones de prefijo (o polaca, en homenaje a Jan Łukasiewicz), de infijo y de postfijo (o polaca inversa) son formas de escritura de expresiones algebraicas que se diferencian por la posición relativa que toman los operadores y los operandos. En la notación de prefijo, el operador se escribe delante de los operandos (+ 3 4), entre los operandos en la notación de infijo (3 + 4) y tras los operandos en la de posfijo (3 4 +).
La notación de prefijo fue propuesta en 1924 por el matemático, lógico y filósofo polaco Jan Łukasiewicz (1878-1956), de allí el nombre alternativo por la que se conoce.
Al igual que la de postfijo, la notación polaca permite prescindir de los paréntesis en el caso de operadores de aridad fija conocida. Por ejemplo, la operación 5 * (12 + 4).puede escribirse en prefijo como: * 5 (+ 12 4); o sencillamente: * 5 + 12 4 (y como 5 12 4 + *en postfijo).
Conectivas en notación polaca
Tradicionalmente, la notación polaca usa letras mayúsculas para expresar conectivas, tomando normalmente la primera letra del nombre de la conectiva en polaco. Aquí tenemos una lista con los símbolos más comunes:
Conectiva | Notación estándar | Notación polaca |
Negación | ¬ | N |
Implicación | → | C |
Conjunción | ∧ | K |
Disyunción | ∨ | A |
Bicondicional | ↔ | E |
Posibilidad | ⋄ | M |
Necesidad | ◻ | L |
Cuantificador universal | ∀ | Π |
Cuantificador existencial | ∃ | Σ |
Definición de fórmula bien formada en notación polaca
Tomando la lista anterior de conectivas en notación polaca más un conjunto de variables proposicionales como alfabeto de un lenguaje, tenemos la siguiente definición recursiva de fórmula bien formada en dicho lenguaje:
· Sea α una variable proposicional. α es una fórmula bien formada.
· Sean α, β fórmulas bien formadas. Nα, Cαβ, Kαβ, Aαβ, Eαβ, Mα, Lα, Πα, Σα son fórmulas bien formadas.
Método para traducir una fórmula en notación estándar a notación polaca
(1) Buscamos la conectiva principal y escribimos la equivalente en notación polaca.
(2) Si la conectiva es unaria, tomamos su argumento como una subfórmula y aplicamos (1).
(3) Si la conectiva es binaria, (3a) tomamos el primer argumento y aplicamos (1), a continuación tomamos el segundo argumento y aplicamos (1).
(4) Si el símbolo es una variable proposicional, la escribimos a continuación.
El procedimiento acaba en un número finito de pasos dado que en sucesivas aplicaciones de (1) la complejidad de la fórmula disminuye. Si se trata de una fórmula bien formada, el procedimiento acabará por darnos otra fórmula bien formada en notación polaca. Baste esta descripción para mostrar el carácter formal del procedimiento.
En la práctica, resultaría tedioso aplicar este procedimiento paso por paso. Resulta más adecuado entender la mecánica por medio de ejemplos y aplicarla directamente; con cierto entrenamiento la traducción se hace de manera casi automática.
Como ejemplo de este procedimiento vamos a utilizar una instancia de la ley de De Morgan, que en notación estándar escribiríamos así: ¬(p ∧ q) → (¬p ∨ ¬q). En este ejemplo la conectiva principal es la implicación, una conectiva binaria, cuyos argumentos tienen como conectiva principal la negación y la disyunción respectivamente. Tendremos que traducir las sucesivas subfórmulas hasta las variables variables proposicionales.
Notación estándar | Notación polaca | Operación |
¬(p ∧ q) → (¬p ∨ ¬q) | C | (1), (3) |
¬(p ∧ q) → (¬p ∨ ¬q) | C_____ _____ | (3a) |
¬(p ∧ q) | CN | (1) |
¬(p ∧ q) | CN____ | (2) |
p ∧ q | CNK_ _ | (1), (3) |
p ∧ q | CNKp | (3a), (4) |
p ∧ q | CNKpq | (3b), (4) |
¬(p ∧ q) → (¬p ∨ ¬q) | CNKpq_____ | (3b) |
¬p ∨ ¬q | CNKpqA__ __ | (1), (3) |
¬p ∨ ¬q | CNKpqA__ __ | (3a) |
¬p | CNKpqAN_ | (1), (2) |
¬p | CNKpqANp | (4) |
¬p ∨ ¬q | CNKpqANp__ | (3b) |
¬q | CNKpqANpN_ | (1), (2) |
¬q | CNKpqANpNq | (4) |
No hay comentarios.:
Publicar un comentario