2.2.1 Notación Polaca

La notación polaca, también conocida como notación prefija, es un tipo de notación que se aplica en lógica, aritmética y álgebra. Fue creada por Jan Łukasiewicz allá por los años 20 del siglo XX. Su principal característica, y por lo que se la conoce como notación prefija, es que los operadores preceden a los operandos, lo que significa, traducido al ámbito de la lógica, que las conectivas preceden a las variables.

El alcance de un operador queda perfectamente determinado por su posición en la fórmula, cuanto más a la izquierda se haye un operador mayor alcance tiene. Del mismo modo, la conectiva principal de una fórmula en notación polaca es la situada más a la izquierda.

Este tipo de notación evita por tanto el uso de símbolos auxiliares (paréntesis, corchetes…) para establecer el alcance de las conectivas, a diferencia de la notación estándar. Esta notación puede leerse sin ambigüedad sin recurrir a estos símbolos. Esta característica hace su escritura más compacta.

Por ejemplo, el axioma de no contradicción, que en notación estándar escribimos ¬(p ∧ ¬ p), en notación polaca lo expresaríamos así: NKpNp.

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)

Algoritmo