Sistemas formales de Post
Roberto Moriyón
Sistemas Formales de Post
• Los introdujo Emile Post en la década de
1920 para estudiar propiedades de las
funciones computables
• Se utilizan como formalismo básico de la
Lógica Formal
Sistemas formales: Reglas
• Reglas de producción
– <patrones-cond>  <cadena-concl>
• Ejemplo (sistema MIU)
- xI  xIU
- xIIIy  xUy
// x,y(M+I+U)*
- Mx  Mxx
- xUUUy  xy
• Producción: Lo escribiremos usando 
– Ejemplo: MI  MIUIUIUIU
(MI  MIU  MIUIU  MIUIUIUIU)
Sistemas formales:
Aplicación de reglas
• AplRegla(u, v, c) = Aplica(Encaje(u, c), v)
• Ejemplo sencillo:
– xIIIy  xUy, MIIII  MUI, MIU
• Otro ejemplo:
– xIIIx  AxxxB, UUIIIUU  AUUUUUUB
Aplicación de reglas: Ejercicio
• [APLICA] Construir cuatro programas que
implementen las funciones encaje, aplica,
aplRegla y  anteriores, y otro que a
partir de una sucesión de especificaciones
de aplicación de la forma Ai  Bi
comprueba que mediante ellas se
consigue la producción    (sus tres
argumentos deben ser la especificación y
las cadenas  y )
Sistemas formales: Axiomas
• Los axiomas son cadenas de partida para
las cadenas producidas por el sistema
• Ejemplo: MI
• Se puede generar MU a partir del sistema
anterior?
Sistemas formales: Axiomas
• Los axiomas son cadenas de partida para
las cadenas producidas por el sistema
• Ejemplo: MI
– MU no es producido por el sistema anterior
– Todas las cadenas producidas por el sistema
anterior tienen un número de Ies que no es
múltiplo de 3
• Ejercicio: Caracterizar las cadenas
producidas por el sistema anterior
Sistemas formales:
Axiomas, II
• Los axiomas pueden ser conjuntos
infinitos si están definidos mediante
patrones u otros sistemas formales
• Ejemplo: El conjunto infinito de axiomas xx
se puede generar a partir de las reglas
– xx  0x0x
xx  1x1x
y de los axiomas
– 00
11
Sistemas formales: Ejemplos
• Dada una gramática hay un sistema
formal que genera el mismo lenguaje
Ejemplo:
S ::= aSb | bSa | SS
xSy  xaSby, xSy  xbSay, xSy  xSSy
• Generación a partir de símbolos iguales:
– En una gramática dos símbolos terminales
iguales pueden generar subpalabras distintas
– En un sistema formal dos variables de patrón
iguales dan lugar subpalabras iguales
Sistemas formales: Ejemplos, II
• Suma (x, y, z  -*)
– Regla: x+y=z  x+y-=z– Axiomas: x+=x
• Multiplicación (x, y, z  -*)
– Regla: x*y=z  x*y-=zx
– Axiomas: x*=
Sistemas formales
• Las cadenas aceptadas por el sistema son
las producidas por sus reglas que tienen
determinados símbolos (alfabeto final)
• Por lo tanto, en un sistema formal hay que
decir qué cadenas pueden sustituir a las
variables y cuál es el alfabeto final
• Ejemplo: Números compuestos (números
que no son primos):
Sistemas formales: Ejemplo III
• Números compuestos (x, y, z  -*)
– Reglas:
Las de la Multiplicación
x--*y--=z  Cz
– Axiomas: Los de la Multiplicación
– Alfabeto final: {C, -}
Sistemas formales: Reglas con
cabecera múltiple
Ejemplo:
• I  uvabuv
I  cuvd
xabx, cxd  exe
I  euve
Sistemas formales: Ejemplos, V
• No divide (x, y  -+)
– Regla: xNDy  xNDxy
– Axiomas: xyNDx
– Alfabeto final: {ND, -}
• Sin divisores menores no triviales (x, z  -+)
– Reglas:
Las de No divide
--NDz  zSDM--zSDMx , xNDz  zSDMx– Axiomas: Los de No divide
– Alfabeto final: {S, D, M, -} // Excluido el caso xSDM--
Sistemas formales: Ejemplos VI
• Ejemplo: 5 no tiene divisores menores que 4
--ND(A1)
--ND--(R1)
--ND----(R1)
-----SDM--- (R2)
[4]
---ND-(A1)
---ND----(R1)
[6]
-----SDM---- ([4], [6], R3)
Sistemas formales: Ejemplos VII
• Primo (x, y  -+)
– Reglas:
Las de Sin divisores menores
zSDMz  Pz
– Axiomas:
Los de Sin divisores menores
P-– Alfabeto final: {P, -}
Reglas con patrones como
consecuentes
• Ejemplo:
xx  xy
• La variable de patrón y puede ser
cualquier cadena compatible con las
restricciones impuestas por el sistema
• Los axiomas se pueden escribir como
reglas sin antecedente (axioma)
• No es lo mismo que una regla con
antecedente vacío (consecuente)
Sistemas formales:
Definición final
• Conjunto de reglas de la forma 
– Consecuente: Patrón, (V)*
– Antecedente: Cero, uno o más patrones
separados por comas
• Conjunto de restricciones sobre las
variables de patrones: cada variable tiene
asociado un sistema formal
• Alfabeto final f
Capacidad expresiva de los
sistemas formales
• Los sistemas formales permiten expresar su
propia capacidad de producción:
Si a un sistema formal le añadimos el axioma
xx
y, por regla suya de la forma AB, la regla
xA  xB
siendo x una variable nueva, el sistema formal
resultante es capaz de computar formalmente
cuándo una cadena de caracteres se puede
producir a partir de otra.
Capacidad expresiva de los
sistemas formales: Ejemplo
• Se puede demostrar formalmente que en
el sistema MIU
MI  MIUIUIUIU,
pues en este caso las reglas para  son
- zxI  zxIU
- zxIIIy  zxUy
- zMx  zMxx
- zxUUUy  zxy
por lo que el sistema ampliado genera
MIMIUIUIUIU
Sistema formal universal
• Se puede definir un sistema formal
universal, capaz de emular cualquier otro
sistema formal, mediante una sola regla:
X, XY  Y
En este sistema los axiomas están
formados por los del sistema formal que
se pretende emular más sus reglas,
escritas en la forma XY.
Sistema formal universal, II
• Por ejemplo, para emular el sistema MIU
mediante el sistema formal universal se utilizan
los siguientes axiomas:
–
–
–
–
–
xIxIU
MxMxx
xIIIyxUy
xUUUyxy
MI
• Un sistema formal puede incluir la regla de
emulación universal además de otras, así como
reglas que permiten construir reglas nuevas en
base a otras cadenas de caracteres.
Sistemas formales:
Potencia computacional
• Las reglas de producción de sistemas
formales permiten definir los mismos
lenguajes que las gramáticas generales
(todos los recursivamente enumerables)
• En muchos casos permiten hacerlo de
manera mucho más sencilla
• Los lenguajes aceptados por sistemas
formales son aceptados por máquinas de
Turing (y viceversa)
Sistemas formales:
Consideraciones informales
• Los lenguajes producidos por sistemas
formales se pueden representar de
manera informal como conjuntos
ramificados, al estilo de un árbol, en el
que las ramas hijas surgen de las
antecesoras al aplicar las reglas
• El complementario del lenguaje producido
por un sistema formal no tiene por qué ser
producido por otro sistema formal
(ejemplo: lenguaje asociado al problema
de la parada)
Interpretación de un lenguaje
formal
• En todos los ejemplos que hemos visto
(salvo el primero) las palabras producidas
por un sistema formal se pueden
interpretar como afirmaciones.
– Ejemplos: suma, multiplicación, composición,
no divide, sin divisores menores, primo,
produce
• La interpretación nos indica el significado
de las “frases” escritas en el lenguaje
producido por el sistema.
Dominio de una interpretación de
un lenguaje formal
• A menudo una interpretación asigna objetos de un conjunto a partes de la palabra
de partida (ejemplo: en todos los sistemas
que hemos visto aparecen números,
excepto en el sistema extendido a partir
de otro, en el que aparecen cadenas
producidas), y afirmaciones acerca de
esos objetos a las palabras completas.
• El conjunto de objetos asociado a una
interpretación se llama el dominio de la
misma.
Certeza de afirmaciones bajo una
interpretación.
• Dada una interpretación de un sistema
formal, se dice que una palabra producida
por el sistema es cierta bajo ella si lo es
su interpretación.
• Las palabras producidas por un sistema
no son ciertas o falsas intrínsicamente,
pues son simples cadenas de caracteres,
sino dependiendo de su interpretación.
Interpretación y certeza: Ejemplo
• Consideramos el sistema formal siguiente:
– Axioma:
01<0
– Reglas:
x<yx1<y1
x<yx1<y
Interpretación y certeza: Ejemplo, II
• Bajo la interpretación de que cada palabra
representa una desigualdad (mediante la
relación “menor”) entre números naturales, que
forman el dominio, ni el axioma ni ninguna de
las palabras producidas son ciertos.
• La misma interpretación con “mayor” en vez de
“menor”, hace que el axioma y todas las
palabras producidas sean ciertos.
Consistencia, modelos
• Dado un sistema formal, es fundamental
disponer de una interpretación en la que los
axiomas y todas las palabras producidas sean
ciertos. En ese caso se dice que la
interpretación es un modelo del sistema.
Ejemplo: Postulados de Euclides
• Más adelante veremos que se puede
definir un sistema formal que genera
afirmaciones geométricas. En ese sistema
los axiomas son los postulados de
Euclides.
• El sistema formal de Euclides produce
teoremas como la existencia de un punto
común a las tres alturas de un triángulo y
todas las propiedades de la Geometría
plana habitualmente conocidas.
Interpretación habitual de los
postulados de Euclides (adaptados)
• El dominio habitual de la geometría euclídea
plana son los puntos, segmentos, rectas,
semirrectas, circunferencias, ángulos y
congruencias del plano. En el modelo habitual
los postulados se interpretan como sigue:
1. Dados dos puntos hay un único segmento que los
une.
2. Todo segmento está contenido en una recta única.
3. Dados dos puntos hay una circunferencia única con
centro en el primero y que pasa por el segundo.
4. Dos ángulos rectos son congruentes.
5. Dados un punto y una recta hay otra recta única que
pasa por el punto y no corta a la recta inicial.
Interpretación: Ejemplo, II
• Durante siglos los geómetras intentaron
demostrar que el último axioma es
consecuencia de los anteriores.
• En el siglo XVIII, G. Saccheri intentó
demostrarlo viendo que a partir de su negación
y de los axiomas previos se llega a una
contradicción. Desarrolló una geometría
nueva, sin darse cuenta de ello, y finalmente
decidió que sus conclusiones eran
contradictorias con la idea de recta.
Interpretación: Ejemplo, III
• En el siglo XIX J. Bolyai y N. Lobachevski
descubrieron que por ese procedimiento
se definían geometrías nuevas de interés.
Con ello se descubrió la Geometría
Hiperbólica.
• A partir de un estudio sistemático de las
geometrías posibles se descubrió también
la Geometría Elíptica.
Validez de los postulados de Euclides
en la Geometría Hiperbólica
• En el sistema formal asociado a los postulados
de Euclides, el quinto postulado no es cierto
bajo la interpretación de la Geometría
Hiperbólica, pero sí lo es bajo la de la
Geometría Euclídea.
• El espacio hiperbólico es un modelo de un
sistema formal basado en los cuatro primeros
postulados de Euclides y en la negación del
quinto.
Geometría elíptica
• El espacio elíptico se puede representar con un
dominio cuyos puntos son las direcciones del
espacio tridimensional.
• Las rectas del espacio elíptico corresponden a
las direcciones de un plano.
• El espacio elíptico es otro modelo del sistema
formado por los cuatro primeros postulados de
Euclides, pero no satisface el quinto postulado.
• Lo anterior demuestra que a veces puede haber
más de un modelo, y eligiendo un axioma más
se puede eliminar alguno de ellos.
Ejercicios obligatorios
•
•
•
•
Construir sistemas formales que produzcan
los siguientes lenguajes:
[FM3] Multiplicación por 3 en base 2 (ejemplo:
T101=1111).
[FM] Multiplicaciones en base 2 (ejemplo:
101*101=11001)
[F0] x>y, donde y es 0 si x tiene algún 0 y 1 en
caso contrario (ejemplo: 101>0; 111>1).
[FS] x.y.z>u, donde y es un símbolo y u es el
resultado de sustituir sus apariciones en x por z
(ejemplo: 01101.1.11>01111011).
Ejercicios optativos
•
•
•
•
•
Construir sistemas formales que produzcan los
siguientes lenguajes:
[F1] x.y, donde y está formada por los unos de x.
[FS] x.y, donde y es la palabra simétrica de x
(estudiar el problema con distintos alfabetos).
[FD] xRy=z, donde x e y son números
representados por guiones y z es el resto de la
división de x por y.
[FMCD] xMyDz, donde x e y son números
representados por guiones, y z es el máximo
común divisor de x e y.
[FF] xFy, donde x e y son números representados por guiones e y es el factorial de x.
Descargar

Sistemas formales de Post