análisis lógico -...

Análisis lógicoNotas de clase

Francisco Hernández Quiroz

Mayo de 2002

Índice general

Introducción 5

1. Inducción y recursión 91.1. Relaciones e inducción bien fundadas . . . . . . . . . . . . . 91.2. Conjuntos definidos inductivamente . . . . . . . . . . . . . 151.3. Funciones recursivas y conjuntos inductivos . . . . . . . . . 18

2. Lenguajes de programación 272.1. Programación imperativa . . . . . . . . . . . . . . . . . . . 28

2.1.1. Semántica operacional estructural . . . . . . . . . . 282.1.2. No determinismo . . . . . . . . . . . . . . . . . . . . 31

2.2. Un lenguaje funcional . . . . . . . . . . . . . . . . . . . . . 332.3. Procesos concurrentes . . . . . . . . . . . . . . . . . . . . . 36

3. Cálculo de proposiciones 393.1. Sintaxis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.2. Semántica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 393.3. Tautologías . . . . . . . . . . . . . . . . . . . . . . . . . . . 413.4. Sistemas formales de demostración. Ejemplo de Łukasiewiecz 413.5. Propiedades de los sistemas de demostración . . . . . . . . 423.6. Deducción natural . . . . . . . . . . . . . . . . . . . . . . . 42

4. Cálculo de predicados 454.0.1. Sustitución de variables por términos: . . . . . . . . 45

4.1. Sistemas formales de demostración y sus propiedades . . . . 464.2. Deducción natural . . . . . . . . . . . . . . . . . . . . . . . 46

3

4 ÍNDICE GENERAL

5. Programación lógica 495.1. Unificación . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.2. Un lenguaje de programación lógica . . . . . . . . . . . . . 525.3. Resolución . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.4. Modelos de Herbrand mínimos . . . . . . . . . . . . . . . . 565.5. Negación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

6. Bases de datos relacionales 596.1. El modelo relacional . . . . . . . . . . . . . . . . . . . . . . 596.2. Consultas y programas lógicos para bases de datos . . . . . 59

7. Verificación de programas imperativos 617.1. Corrección parcial de programas . . . . . . . . . . . . . . . 61

8. Lógicas no clásicas 678.1. Lógica modal . . . . . . . . . . . . . . . . . . . . . . . . . . 678.2. Lógica modal y sistemas concurrentes . . . . . . . . . . . . 67

Introducción

Se ha dicho que el papel de la lógica en las ciencias de la computaciónes análogo al del cálculo en la física y en la ingeniería. Sin embargo, estatesis no se refleja adecuadamente en el contenido de muchos planes deestudio en el área. El objetivo de la materia de Análisis lógico es subsanaresta deficiencia.

El cálculo de proposiciones es la base de la lógica, pero el cálculo depredicados constituye el núcleo de una buena parte de las aplicaciones enciencias de la computación: la especificación y la verificación de programas,la axiomatización de álgebras abstractas (subyacentes a los distintos tiposde datos de los lenguajes de programación), la programación lógica, lasbases de datos relacionales, etc. Por esta razón, el estudio del cálculo depredicados es el tema principal del curso.

Sin embargo, otras ramas de la lógica también tienen su lugar. Por unaparte, el cálculo de predicados de primer orden es insuficiente para forma-lizar todos los objetos que aparecen en la ciencia de la computación. Por laotra, el uso de las lógicas no clásicas se extiende cada vez más en la forma-lización de sistemas concurrentes o en la elaboración de sistemas expertos,por citar sólo dos ejemplos. El curso concluye con una breve introduccióna estas lógicas.

Qué es la lógica

Uno de los objetivos centrales de la lógica es la teoría de la demostra-ción, que intuitivamente se puede ver como el estudio de los argumentoscorrectos. Sin embargo, la corrección de un argumento (al menos para lalógica) no depende del contenido de éste, sino de su forma. Consideremosel ejemplo clásico de argumento correcto:

5

6 ÍNDICE GENERAL

Todos los hombres son mortales.

Sócrates es un hombre.

En consecuencia

Sócrates es mortal.

En el cual en realidad no nos importan el significado de las palabras“hombre”, “mortal” o “Sócrates”, sino la forma de los enunciados que lascontienen: el también clásico “silogismo” Darii. Aquí tenemos otro ejemplodel mismo silogismo:

Todos los borogovos son frumosos.

El Jabberwock es un borogovo.

En consecuencia

El Jabberwock es frumoso.

Que también es correcto, a pesar de que no tenemos ni la más remotaidea de qué son las palabras “borogovo”, “frumoso” y “Jabberwock” (aun-que Lewis Carroll las “define” en La caza del snark).

Un lenguaje lógico consta normalmente de los tres elementos siguien-tes:

Una sintaxis formal, es decir, con reglas precisas que permiten deter-minar sin ambigüedad qué cadenas de símbolos de un alfabeto dadopertenecen al lenguaje.

Una semántica matemática: el significado de los enunciados del len-guaje se define por medio de interpretaciones, las cuales son funcionesque relacionan los símbolos del lenguaje con elementos de un domi-nio matemático.

Reglas de inferencia (o derivación) que permiten obtener enunciadosverdaderos a partir de enunciados verdaderos llamados teoremas.

Los matemáticos (y mucha gente de computación) están especialme-ne interesados en el último elemento. En particular se preocupan por lossistemas de demostración que contienen una o más reglas de inferencia y

ÍNDICE GENERAL 7

que permiten demostrar teoremas de un lenguaje lógico particular (porejemplo, una formalización de la aritmética de los números naturales). Lossistemas de demostración tienen un poder variable que depende en partede decisiones de diseño y en parte de limitaciones absolutas. En general sebusca que posean las siguientes propiedades:

Consistencia: no es posible que un enunciado y su negación sean teo-remas del sistema al mismo tiempo.

Corrección (soundness): los teoremas del sistema son enunciados váli-dos (es decir, verdaderos en cualquier interpretación).

Completitud: se puede dar en dos versiones: (a) como una propiedadrecíproca de la corrección, a saber: todos los enunciados válidos sonteoremas; (b) como la propiedad de que dado un enunciado sin varia-bles libres, o bien éste es un teorema del sistema o bien su negaciónlo es.

Decidibilidad: existe un método efectivo (es decir, que siempre termi-na) para determinar si un enunciado es o no es un teorema.

Sin embargo, la norma es que no se cuente con todas las anteriores.Las dos primeras deben estar presentes en todo sistema que se respete,pero la completitud (b) es inalcanzable para todo lenguaje de complejidadsuficiente como para expresar las verdades de la aritmética de númerosnaturales. La decidibilidad está ausente incluso en el cálculo de predicadossin axiomas especiales.

Lógica y computación

Sin embargo, hasta el momento no se ha explicado de manera más pre-cisa cuál es la relación entre la lógica y la computación. Esta relación lapodemos ver en tres niveles al menos:

1. Ambas tratan de lenguajes formales.

2. Como ya se dijo, la lógica se aplica en áreas específicas de la compu-tación: especificación, verificación y transformación de programas;programación lógica y bases de datos; sistemas expertos e inteligen-cia artificial, etc.

8 ÍNDICE GENERAL

3. En un sentido teórico (y técnico) son equivalentes: los enunciadosdemostrables en el cálculo de predicados son equivalentes a las fun-ciones computables por una máquina de Turing o por los formalismosequivalentes a éstas. En pocas palabras, su poder “computacional” esel mismo.

Durante el curso se dará más sustancia a las afirmaciones anteriores. Porlo pronto conviene ya entrar en materia y se comenzará con los conceptosde inducción y recursión.

Capítulo 1

Inducción y recursión

En este capítulo se estudiarán los conjuntos inductivos y las funcionesrecursivas definidas en éstos. Dichos conjuntos y funciones serán los ele-mentos básicos de todos los lenguajes que se verán en el resto del curso.

1.1. Relaciones e inducción bien fundadas

Si dos elementos a, b de un conjunto están en una relación R se escribirá(a, b) ∈ R, a R b o R(a, b).

Definición 1.1.1 Sea A un conjunto y sea R ⊆ A × A. Se dice que R es:

1. Reflexiva sii ∀a ∈ A . R(a, a).

2. Simétrica sii ∀a, b ∈ A . R(a, b) ⇒ R(b, a).

3. Antisimétrica sii ∀a, b ∈ A . R(a, b) ∧ R(b, a) ⇒ a = b.

4. Transitiva sii ∀a, b, c ∈ A . R(a, b) ∧ R(b, c) ⇒ R(a, c).

5. Total sii ∀a, b ∈ A . a 6= b ⇒ R(a, b) ∨ R(b, a).

Dada una relación R en A × A se puede construir sus cerraduras transi-tiva y reflexiva y transitiva, denotadas por R+ y R∗, respectivamente:

R0 = {(a, a) | a ∈ A}R1 = R

9

10 CAPÍTULO 1. INDUCCIÓN Y RECURSIÓN

Rn+1 = Rn ∪ {(a, c) | ∃b . (a, b) ∈ Rn ∧ (b, c) ∈ Rn}

R+ =⋃

n∈N

Rn+1

R∗ =⋃

n∈N

Rn

En matemáticas hay un tipo de relaciones muy comunes llamadas órde-nes. Sin embargo, los órdenes vienen en distintos sabores.

Definición 1.1.2 Una relación R es un pre-orden (o cuasi orden) sii es refle-

xiva y transitiva.

Un orden parcial (o poset, por el inglés partially ordered set) es una rela-

ción reflexiva, transitiva y antisimétrica.

Un orden total o lineal es simplemente una relación total. Obsérvese cómo

no se supone que tenga ninguna otra propiedad.

El orden parcial más conocido es ≤ en N. En el mismo conjunto, < esun orden total. Un ejemplo de pre-orden en P(N) es la siguiente relación

A ⊑L B sii ∀a ∈ A . ∃b ∈ B . a ≤ b,

llamada el preorden inferior o de Hoare. Se tiene que {0, 1, 2} ⊑L {1, 2} y{1, 2} ⊑L {0, 1, 2} pero {0, 1, 2} 6= {1, 2}.

Se usarán con frecuencia los símbolos ≺ y ≻ para denotar relaciones deorden arbitrarias.

Una relación de orden en un conjunto A se puede extender a An almenos de dos formas:

1. Orden lexicográfico. Sea ≺⊆ A × A un orden. La relación ≺lex⊆ (A ×A) × (A × A) se define así:

(a, b) ≺lex (a′, b′) sii a ≺ a′ oa = a′ y b ≺ b′.

La definición anterior se extiende a An de la misma forma en que seextiende el concepto de par ordenado a n-adas arbitrarias.

2. Orden por coordenadas. ≺coor es la siguiente relación:

(a, b) ≺coor (a′, b′) sii a ≺ a′ y b ≺ b′,

que se extiende del mismo modo a n-adas arbitrarias.

1.1. RELACIONES E INDUCCIÓN BIEN FUNDADAS 11

Conviene dar nombre a algunos elementos especiales de un conjuntoordenado:

Definición 1.1.3 Sea ≺ una relación en A×A y sea X ⊆ A. Se dice que x ∈ X

es un:

1. mínimo sii ∀y ∈ X . x 6= y ⇒ x ≺ y.

2. máximo sii ∀y ∈ X . x 6= y ⇒ y ≺ x.

3. minimal sii ¬∃y ∈ X . x 6= y ∧ y ≺ x.

4. maximal sii ¬∃y ∈ X . x 6= y ∧ x ≺ y.

Ejemplos. Sea A = {0, 1, 2}. Si se ordena P(A) con la relación ⊆ entonces∅ y A son el mínimo y el máximo de ⊆. En cambio, P(A) − {∅} no tienemínimo, pero si tres minimales: {0}, {1} y {2}. Por su parte, P(A) − {A}no tiene máximo, pero sí tres maximales: {0, 1}, {0, 2} y {1, 2}.

En un orden parcial, un mínimo es un minimal, pero esto no es necesa-riamente el caso en un preorden. Más adelante se verán otros órdenes enlos que los mínimos son siempre minimales.

Definición 1.1.4 Sea ≺ un orden en U×U y sea C ⊆ U. Decimos que C es una

cadena sii ∀x, y ∈ C es el caso que x ≺ y o y ≺ x. Una cadena descendente

infinita es una cadena C tal que ∀x ∈ C, ∃y ∈ C tal que y ≺ x. De manera

dual, una cadena infinita ascendente C tiene la propiedad de que ∀x ∈ C,

∃y ∈ C tal que x ≺ y.

Obsérvese cómo una cadena C ⊆ X es un subconjunto de X que vistode manera aislada forma un orden total. Las cadenas descendentes nospermiten caracterizar los órdenes bien fundados.

Definición 1.1.5 Sea ≺⊆ U × U una relación. Decimos que ≺ es un bienfundada sii no existen cadenas infinitas descendentes en U.

El ejemplo clásico de una relación bien fundada es< en N. Si denotamospor ≺suc la relación inducida por suc : N → N ( la función sucesor)

x ≺suc y sii y = suc(x),


esta relación también es bien fundada. Por cierto, a diferencia de <, no estransitiva.

Un ejemplo de importancia en lenguajes formales es la relación basadaen el concepto de prefijo. Un alfabeto es un conjunto no vacío finito Σ.Una cadena α es un sucesión finita (posiblemente vacía) de símbolos deΣ. La cadena vacía se representa con el símbolo ǫ. El conjunto de cadenases Σ∗ y el de cadenas no vacías es Σ+. Hay una operación binaria en Σ∗:la concatenación, y no se usará ningún signo especial para marcarla. Larelación ≺pre está determinada por la regla:

α ≺pre β sii ∃γ . β = αγ ∧ γ 6= ǫ.

Puede verificarse fácilmente que ≺pre es un orden bien fundado y que sumínimo en Σ∗ es ǫ, mientras que en Σ+ no tiene mínimo sino varios mini-males, a saber, los elementos de Σ.

Teorema 1.1.6 Sea ≺ una relación bien fundada. Entonces: (a) ≺ no es refle-

xiva ni simétrica; (b) su cerradura transitiva es bien fundada; (c) los órdenes

lexicográfico y por coordenadas basados en ≺ son bien fundados; (d) ≺∗ es un

orden parcial.

Demostración: (a) Si ≺ fuera reflexiva, entonces es muy fácil formar unacadena infinita descendente a partir de un solo elemento:

· · · ≺ a ≺ a.

Del mismo modo, si ≺ fuera simétrica, basta con tomar dos elementos a yb tales que a ≺ b:

· · · ≺ b ≺ a ≺ b,

para tener otra cadena infinita.(b) Supongamos que la relación ≺ es bien fundada. Si tenemos una

cadena· · · ≺+ ai ≺

+ · · · ≺+ a0,

y suponemos que es descendente infinita, entonces para todo i existen ai0 =ai, . . . , aim = ai+1 tales que

aim ≺ · · · ≺ ai

1.1. RELACIONES E INDUCCIÓN BIEN FUNDADAS 13

es decir, la misma cadena de ≺+ se puede transformar en una cadena de ≺,por lo que tenemos una cadena infinita descendente en ≺, lo cual es unacontradicción.

(c) Sea C una cadena en A × A con el orden ≺coor:

· · · ≺coor (a1, b1) ≺coor (a0, b0).

Si esta cadena fuera infinita, sería posible construir dos cadenas infinitasen ≺

· · · ≺ b1 ≺ b0 y · · · ≺ a1 ≺ a0,

por lo que C no puede ser infinita descendente. En cuanto a ≺lex, considé-rese la siguiente cadena descendente infinita:

· · · ≺lex (a1, b1) ≺lex (a0, b0).

En consecuencia, es posible construir una cadena en ≺ usando el siguientemétodo: el primer elemento es a0, el segundo es el primer ai tal que a0 6= ai.Si no existe tal elemento, entonces, por la definición de ≺lex tenemos unacadena descendente infinita en ≺

· · · ≺ b1 ≺ b0,

lo cual no es posible. Por otro lado, suponer que podemos encontrar unnúmero infinito de diferentes ai nos lleva a otra cadena infinita

· · · ≺ a1 ≺ a0,

lo que tampoco es posible. Por lo tanto, ≺lex tampoco contiene cadenasinfinitas descendentes.

(d) Es claro que la cerradura transitiva y reflexiva tiene dos de las pro-piedades de un orden parcial. La antisimetría viene del hecho de que sitenemos que a ≺∗ b y b ≺∗ a y no fuera el caso que a = b, se podría formaruna cadena descendente infinita en ≺ siguiendo el método de (a).

El teorema 1.1.7 nos da una caracterización alternativa de las relacionesbien fundadas.

Teorema 1.1.7 Una relación ≺ es bien fundada en A × A sii todo X ⊆ A

(X 6= ∅) tiene un minimal.


Demostración. a) Supongamos que ≺ es bien fundada y que ∅ 6= X ⊆ A.Ahora bien, si X no tiene un elemento minimal, entonces ∀m ∈ X . ∃b ∈X . b ≺ m. Iterando este razonamiento, podemos construir una cadenadescendente infinita de elementos en X, lo cual es una contradicción.

Si ahora suponemos que todo subconjunto no vacío de A tiene un mini-mal y además tenemos una cadena descendente

· · · ≺ ai ≺ · · · ≺ a0,

basta con que tomemos el conjunto de elementos en la cadena que porhipótesis debe de tener un elemento minimal y, en consecuencia, la cadenano puede descender infinitamente.

Sea P una propiedad de elementos de A y sea ≺⊆ A × A. La siguienteafirmación se conoce como el principio de inducción:

(∀a ∈ A . P(a)) ⇔ (∀a ∈ A .((∀b ∈ A . b ≺ a ⇒ P(b)) ⇒ P(a))).

Este principio se aplica en conjuntos donde ≺ es un orden bien fundado:

Teorema 1.1.8 Sea ≺⊆ A × A una relación bien fundada y sea P : A →{V, F} un predicado. Entonces el principio de inducción vale.

Demostración. La implicación ⇒ es inmediata, así que procederemos conla inversa. Supongamos, por reducción al absurdo, que ∃a ∈ A.¬P(A). SeaQ = {a ∈ A | ¬P(A)} y, dado que ≺ es bien fundada, entonces existe unelemento minimal m de Q. Aquí hay dos opciones:

(i) ∃b ∈ A . b ≺ m;

(ii) ¬∃b ∈ A . b ≺ m.

En el primer caso, por hipótesis b ≺ m ⇒ P(b) y, dada la hipótesis prin-cipal, P(m), lo que contradice la suposición. En el segundo, el enunciado

((∀b ∈ A . b ≺ a ⇒ P(b))

sería verdadero por vacuidad, y como P(m) es falso, entonces todo el enun-ciado sería falso. Pero en ese caso, sabemos que no existiría a ∈ A tal queP(A) y, en consecuencia,

(∀a ∈ A . P(a))

1.2. CONJUNTOS DEFINIDOS INDUCTIVAMENTE 15

sería falso también, con lo que tendríamos la otra implicación.

El principio de inducción nos da una estrategia para demostrar una pro-piedad P en un conjunto A con una relación bien fundada ≺;

1. Se demuestra que todos los elementos minimales cumplen P.

2. Se asume como hipótesis inductiva ∀b ∈ A . b ≺ a ⇒ P(b).

3. Se demuestra que entonces P(a).

Más adelante habrá oportunidad de usar esta estrategia.

1.2. Conjuntos definidos inductivamente

En matemáticas es muy común definir un conjunto de manera “circu-lar”. Por ejemplo, las fórmulas del cálculo de proposiciones:

“Si φ y ψ son proposiciones, entonces ¬φ y φ ∨ ψ son proposiciones”.

Por supuesto, si la definición anterior fuera realmente circular, sería in-correcta. En realidad, lo que se hace en los textos de lógica es definir elconjunto anterior de manera inductiva, lo que evita la circularidad aparen-te.1 Una definición inductiva parte de un conjunto básico y de un conjuntode funciones que generan nuevos elementos a partir del conjunto básico,como se verá en las siguientes definiciones.

Definición 1.2.1 Sea A ⊆ U un conjunto y sea F = { fni : Un → U} un

conjunto de funciones. Decimos que A es cerrado bajo F sii ∀ fnk ∈ F y ∀a1,

. . . an ∈ A resulta que fnk (a1, . . . , an) ∈ A.

Sea X ⊆ U. Entonces, un conjunto Y ⊆ U es inductivo en X bajo F sii

X ⊆ Y y Y es cerrado bajo F.

De todos los conjuntos inductivos en X nos interesa uno en particular alque llamaremos la cerradura inductiva. Existen dos métodos para definirla:

1En algunos textos se llama recursivas a las definiciones como la anterior. Sin embargo,esto es un error terminológico (¡pero un error muy común!). La confusión surge de que enlos conjuntos inductivos se pueden definir funciones recursivas de manera muy natural,como se verá más adelante.


Definición 1.2.2 Sea X ⊆ U y sea F = { fni : Un → U} un conjunto de

funciones. La cerradura inductiva de X bajo F, construida de abajo haciaarriba, se define de este modo:

X0 = X

Xi+1 = Xi ∪ { fnk (x1, . . . , xn) | fn

k ∈ F ∧ x1, . . . , xn ∈ Xi}

X+ =⋃

i∈N

Xi.

Definición 1.2.3 Sea X ⊆ U y sea F = { fni : Un → U} un conjunto de

funciones y sea X la familia de conjuntos inductivos en X bajo F. La cerradurainductiva de X bajo F, construida de arriba hacia abajo es el conjunto

X+ =⋂

Y∈X

Y.

Los dos métodos se usan con frecuencia. El teorema 1.2.4 nos dice queson equivalentes.

Teorema 1.2.4 Ambas definiciones son equivalentes, es decir X+ = X+.

Demostración. Es claro que X+ es inductivo en X y, dado que X+ es la in-tersección de los conjuntos inductivos en X, se tiene que X+ ⊆ X+. La otracontención se demostrará por inducción matemática:

Caso base. X0 = X ⊆ X+.Hipótesis inductiva. Xi ⊆ X+. Por demostrar que Xi+1 ⊆ X+. Pero esto

último se sigue del hecho de que X+ es cerrado. Por inducción, ∀n ∈ N.Xn ⊆X+. Entonces X+ ⊆ X+.

El ejemplo del cálculo de proposiciones se puede ahora plantear de lasiguiente forma. Sea Σ = {p, q, r, p1, . . .} ∪ {(, )} ∪ {∨,¬} un alfabeto y sea¬S : Σ∗ → Σ∗ y ∨S : Σ∗ × Σ∗ → Σ∗ las funciones definidas de la siguienteforma:

¬S(α) = ¬α∨S(α, β) = (α ∨ β).

Sea Pa = {p, q, r, p1, . . .} el conjunto básico. Entonces el conjunto fórmulasdel cálculo de proposiciones, P, se puede definir usando los dos métodos:

P0 = Pa

1.2. CONJUNTOS DEFINIDOS INDUCTIVAMENTE 17

P = P+ = P+

P+ =⋂

Y∈P

Y,

donde P es la familia de conjuntos inductivos en Pa.Los conjuntos definidos por medio de la notación Backus-Naur (BNF en

adelante) se pueden transformar fácilmente en conjuntos inductivos. Porejemplo, las expresiones aritméticas del conjunto EA se definen así:

A ::= N | X | A + A | A × A | A − A

donde A ∈ EA y N es un entero (Z) y X una variable (Var). Estos dos con-juntos se pueden considerar como conjuntos ya dados o se pueden definirde manera similar:

N ::= 0 | suc(N) | pred(N),

con suc y pred las funciones de sucesor y predecesor, respectivamente. Lasvariables se definirán así:

X ::= x | y | z | xN | yN | zN

con N ∈ Z. Este último conjunto no es inductivo en realidad (su construc-ción se realiza en un solo paso), pero Z y EA sí lo son. Veamos el caso deEA. Nuevamente, se comienza con un conjunto básico: EA0 = Z∪ Var y unconjunto de funciones que nos dan nuevas expresiones a partir de otras yaexistentes:

+S(α, β) = α + β×S(α, β) = α× β−S(α, β) = α− β.

y se obtienen así las expresiones aritméticas EA = EA+ = EA+.En algunos casos, el conjunto inductivo se genera a partir de un con-

junto básico y otro conjunto ajeno. Un ejemplo es el conjunto de listas denaturales L(N). En este caso partimos de un conjunto básico con un soloelemento, la lista vacía: [ ] y las funciones de agregación de elementos yconcatenación de listas:

n :: [n1 . . .nn] = [n n1 . . . nn][ ] ++ l = l ++ [ ] = l


(n :: l) ++ l′ = n :: (l ++ l′)

donde ::: N × L(N) → L(N) y ++: L(N) × L(N) → L(N). Obsérvese cómola operación de agregación de elementos tiene dos argumentos, el primerode los cuales no es una lista. Hay dos formas de ajustar las listas a lasdefiniciones 1.2.2 y 1.2.3:

1. N es un conjunto ajeno a las listas de naturales (pues un número natu-ral no es una lista). En ese sentido, al tomar naturales para construirlistas no cambiamos la esencia de una definición inductiva, a saber, lageneración de nuevos elementos a partir del conjunto básico (en estecaso, a partir de las lista vacía), pues N ya está dado y no se generani por la operación de agregación ni por la de concatenación.

2. Se puede suponer que no existe una sola función de agregación, sinouna por cada natural. Por ejemplo,

::1 ([2 3]) = [1 2 3] y ::0 ([2 3]) = [0 2 3]

y el conjunto L(N) es generado por todas estas funciones, con lo queno habría diferencia con respecto a las expresiones aritméticas o alcálculo de proposiciones.

En cualquiera de los dos casos, L(N) = {[ ]}+ = {[ ]}+.

1.3. Funciones recursivas y conjuntos inducti-vos

Una forma muy común de definir funciones en conjuntos es por enu-meración. Por ejemplo, la función identidad en el conjunto {1, 2} se puedeexpresar como un conjunto de pares ordenados: {(1, 1), (2, 2)}. No obstan-te, con conjuntos de gran tamaño (y no se diga con los infinitos) esto espoco práctico. Cuando contamos con una regla que nos permite calcular elvalor de una función en un elemento dado es mejor usar una ecuación:

f(x) = x2

o varias ecuaciones!0 = 1

1.3. FUNCIONES RECURSIVAS Y CONJUNTOS INDUCTIVOS 19

!(n + 1) = !n × (n + 1)

El último ejemplo ilustra además una posibilidad más: las definiciones pue-den ser recursivas, es decir, la función definida puede aparecer no sólo dellado izquierdo, sino también del lado derecho de la ecuación que la define.Sin embargo, es muy fácil cometer “errores” en las definiciones recursivas:

g(x) = g(x + 1)

es una “función” que nunca nos da un resultado. Aunque este ejemplo esmuy obvio, en general no es posible decir si una función recursiva condominio y contradominio en los naturales da un resultado o no (la preguntaes equivalente al famoso problema de la detención en máquinas de Turing).Un problema adicional es cuando se puede obtener más de un resultado,dependiendo del orden en que se apliquen las ecuaciones que definen lafunción. Supóngase que se desea evaluar las expresiones aritméticas EA

tal y como se definieron en la sección anterior. Para esto, se partirá de unaasignación de valores a las variables por medio de una función e : Var → Z,es decir, se supondrá que para toda x ∈ Var, e(x) ya está dado. También setendrá que e(n) = n, para todo n ∈ Z. Ahora hay que extender e al conjuntode elementos de EA:

e(x) = m ya está dado ∀x ∈ Vare(n) = n ∀n ∈ Z

e(α + β) = e(α) +Z e(β)e(α× β) = e(α) ×Z e(β)e(α− β) = e(α) −Z e(β)

donde +Z, ×Z y −Z son las operaciones de suma, multiplicación y resta enlos enteros y no los símbolos sintácticos respectivos. Con estas ecuaciones,queremos evaluar la expresión 2+3×2. Como las ecuaciones no establecenningún orden especial para la evaluación de las expresiones, existen dosposibilidades:

e(2 + 3 × 2) = e(2) +Z e(3 × 2) = 2 +Z (e(3) ×Z e(2)) = 2 +Z (3 ×Z 2)= 2 +Z 6 = 8

y también

e(2 + 3 × 2) = e(2 + 3) ×Z e(2) = (e(2) +Z e(3)) ×Z 2 = (2 +Z 3) ×Z 2


= 5 ×Z 2 = 10

Aunque no hay condiciones necesarias para saber si una función recursivaestá bien definida, la definición 1.3.1 y el teorema 1.3.2 nos dan condi-ciones suficientes. El concepto clave es la generación libre de un conjuntoinductivo:

Definición 1.3.1 Sean A un conjunto, X ⊆ A y F = { fni : An → A} un

conjunto de funciones. Se dice que X+ (o X+) es generado libremente por X y

F sii se cumplen las siguientes condiciones:

(i) La restricción de toda fn ∈ F a Xn+ es inyectiva.

(ii) Para todas fmk y fn

i ∈ F, si fmk 6= fn

i entonces fmk (X+) ∩ fn

i (X+) = ∅.

(iii) Los elementos de X son realmente básicos, es decir, para toda fni ∈ F y

para todas x1, . . . , xn ∈ X+, se tiene que fni (x1, . . . , xn) 6∈ X.

En el caso de EA, el conjunto no se generó libremente, pues no se cum-ple con la condición (ii). Por ejemplo, la expresión 2 + 3 × 2 se puedegenerar de dos maneras, a saber, +S(2, 3 × 2) y ×S(2 + 3,×2), por lo quelas imágenes de +S y ×S no son ajenas. Este problema es muy común cuan-do se trata de evaluar operaciones con más de un argumento. La soluciónmás general consiste en encerrar entre paréntesis las expresiones genera-das por las funciones de tal forma que se impone un orden de evaluación.De esta manera, se redefinen las funciones para expresiones aritméticas:

+S(α, β) = (α + β)×S(α, β) = (α× β)−S(α, β) = (α− β)

y la ambigüedad desaparece. Se deja como ejercicio para el lector que lanueva definición cumple con las condiciones (i)–(iii) de la definición 1.3.1.

En cuanto a las listas, la definición que se dio no cumple ni con (i) nicon (ii):

l ++ [ ] = [ ] ++ l = l

0 :: [ ] = [ ] ++ [0]

Aquí el problema es la función ++. Una nueva definición de listas en la quela única función constructora es :: resuelve el problema (y el lector puedeverificarlo en un ejercicio fácil).


La definición de funciones recursivas en conjuntos generados libre einductivamente se puede realizar sin problemas gracias al siguiente hecho:

Teorema 1.3.2 Sea X+ (o X+) un conjunto generado libremente por X y el

conjunto de funciones F y sea B un conjunto cualquiera distinto de ∅, acom-

pañado por un conjunto de funciones G = {gni : Bn → B}. Sea δ : F → G una

función tal que δ( fni ) = gm

i implica que n = m. Finalmente, sea h : X → B

una función. Entonces, existe una única h : X+ → B tal que:

(i) Para todo x ∈ X . h(x) = h(x)

(ii) Para toda fnk ∈ F y para todas x1, . . . , xn ∈ X+ se tiene que

h( fni (x1, . . . , xn)) = gm

k (h(x1), . . . , h(xn)),

donde δ( fni ) = gm

k .

En álgebra, una función como h se conoce como un homomorfismo. Loshomomorfismos se pueden explicar por medio de diagramas conmutativos.Sea ι : X → X+ la función inclusión (i.e., ∀x ∈ X . ι(x) = x). Entonces, lacláusula (i) de la definición dice lo siguiente:

X X+

B

ι

hh

Que quiere decir que para llegar al vértice marcado con B partiendo delvértice X se puede ir directamente a través de h o indirectamente a travésde i, primero, y h, después, y el resultado será el mismo. La cláusula (ii)del teorema dice, a su vez:


Xn+ X+

Bn X+

fni

hn

δ( fni )

h

Antes de demostrar el teorema anterior, veamos el siguiente lema.

Lema 1.3.3 Sea X+ un conjunto generado libre e inductivamente por X y F.

Para toda fnk ∈ F, si x1, . . . , xn ∈ Xi, entonces fn

k (x1, . . . , xn) 6∈ Xi.

Demostración. Se aplicará inducción sobre i.Caso base: i = 0. Por la condición (iii) de la definición, es verdad que

∀ fnk ∈ F y x1, . . . , xn ∈ X0 se tiene que fn

k (x1, . . . , xn) /∈ X0.Hipótesis inductiva: ∀ fn

k ∈ F, x1, . . . , xn ∈ Xi . fnk (x1, . . . , xn) /∈ Xi. Se

debe demostrar que lo mismo vale en Xi+1. Para esto, hay que consideraruna función fn

k y elementos x1, . . . , xn ∈ Xi+1 − Xi (pues si los elementosestuvieran también en Xi, quedarían cubiertos por la hipótesis inductiva).

Supóngase que fnk (x1, . . . , xn) = x y que x ∈ Xi+1. Entonces, por defi-

nición de Xi+1, hay dos opciones (a) x ∈ Xi; (b) existen gmq ∈ F y y1, . . . ,

ym ∈ Xi tales que x = gmq (y1, . . . , ym). La opción (a) es imposible, pues

contradiría la hipótesis inductiva. Pero (b) contradiría la condición (i) dela definición si fn

k = gmq o la condición (ii) si fn

k 6= gmq . En cualquiera de los

casos, no es posible que x ∈ Xi+1 y, por inducción matemática, esto valepara toda Xn.

Con el lema 1.3.3 ya se puede demostrar el teorema 1.3.2:

Demostración de 1.3.2. Considérese la siguiente sucesión de funciones:

h0 = h

hi+1 = hi ∪ {( fni (x1, . . . , xn), gn

k(hi(x1), . . . , hi(xn))) | x1, . . . , xn ∈ dom(hi)}

h =⋃

i∈N

hi


Obsérvese primero que, dado que X+ es generado libremente, dom(hi) ⊆

Xi. Por otro lado, queremos demostrar que h es en realidad una función, esdecir, si (x, y) ∈ h y (x, z) ∈ h, entonces y = z. Lo haremos por inducción.

Caso base: x ∈ X. En este caso, como X+ es generado libremente, noexisten fm

q ∈ F ni x1, . . . , xm ∈ X+ tales que x = fmq (x1, . . . , xn). Como

h0(x) = h(x) y no asignamos ningún nuevo valor a x en las futuras hi

(i ≥ 1), entonces h(x) tiene una asignación única.Hipótesis inductiva: ∀m ≤ i + 1 tenemos que si x ∈ Xm y (x, y) ∈ h

y (x, z) ∈ h, entonces y = z. Sea ahora x ∈ Xi+1 − Xi. Es decir, por lascondiciones (i) y (ii) de 1.3.1, existen x1, . . . , xn ∈ Xi y fn

q ∈ F únicos talesque fn

q (x1, . . . , xn) = x. El lema 1.3.3 nos dice que fnq (x1, . . . , xn) 6∈ Xi y

por esta razón, hi no está definida en x. Entonces, tenemos que aplicar ladefinición de h,

h(x) = y = gnk(hi(x1), . . . , hi(xn))

h(x) = z = gnk(hi(x1), . . . , hi(xn))

Pero por hipótesis inductiva, h es una función en x1, . . . , xn y, por tanto,y = z. Es decir, h también es una función en x ∈ Xi+1 y, por inducción, loes en todo X+.

Finalmente, se verá la unicidad de h. Supóngase que h′ : X+ → B cum-ple con las condiciones (i) y (ii) del teorema. Demostraremos por inducciónen X+ que h y h′ son iguales.

Caso base: sea x ∈ X0. Por la condición (i), h(x) = h(x) = h′(x).Hipótesis inductiva: ∀m ≤ i+1, tenemos que si x ∈ Xm, entonces h(x) =

h′(x). Sea x ∈ Xi+1 − Xi, es decir, existen x1, . . . , xn ∈ Xi y fnq ∈ F únicos

tales que fnq (x1, . . . , xn) = x. Sea δ( fn

q ) = gnk. Por la condición (ii):

h(x) = = h( fnq (x1, . . . , xn)) = gn

k(h(x1), . . . , h(xn))

h′(x) = = h′( fnq (x1, . . . , xn)) = gn

k(h(x1), . . . , h(xn))

y, por hipótesis inductiva, h(x1) = h′(x1), . . . , h(xn) = h′(xn). En conse-cuencia, h(x) = h′(x) y, por inducción, h = h′.

Como se recordará, la función de evaluación de expresiones aritméticase : EA → Z no funcionó con la definición original de EA. Sin embargo,este último conjunto se redefinió de forma que era generado libremente


por Z∪Var y las nuevas funciones +S, ×S y −S, por lo que el teorema 1.3.2permite asegurar que la función de evaluación siguiente está bien definida:

e(n) = n ∀n ∈ Z

e(x) = e(x) ∀x ∈ Vare((α + β)) = e(α) +Z e(β)e((α× β)) = e(α) ×Z e(β)e((α− β)) = e(α) −Z e(β)

En cuanto a las listas de enteros generadas libremente por ::, tambiénse pueden definir funciones recursivas de manera natural. Por ejemplo, setiene la función long : L(N) → N:

long([ ]) = 0long(n :: l) = 1 + long(l)

La generación libre también nos da un orden natural para estos conjun-tos, como se muestra en la siguiente definición.

Definición 1.3.4 Sea X+ un conjunto generado libre e inductivamente por el

conjunto básico X y las funciones F y sean α, β ∈ X+. Entonces

α ≺S β sii ∃ fni ∈ F ∧ x1, . . . , xn−1 ∈ X+ . β = fn

i (x1, . . . ,α, xn−1).

≺S se conoce como el orden sintáctico o estructural y es claramente unarelación bien fundada. Por esta razón, se puede usar como base de un mé-todo de demostración llamado inducción estructural. Veamos un ejemplo.

Considérese nuevamente EA, con la nueva definición. A simple vistaparece que toda expresión de EA tiene paréntesis balanceados, es decir,a un paréntesis que se abre corresponde siempre uno que se cierra. Estaconjetura se demostrará por inducción estructural. Sea α ∈ EA

Caso base: α ∈ Z o α ∈ Var. Entonces, como las variables y los enterosno incluyen paréntesis, la proposición es trivialmente cierta.

Hipótesis inductiva: α y β tienen paréntesis balanceados. Se debe de-mostrar ahora que (α + β), (α × β) y (α − β) también tienen paréntesisbalanceados, pues

α, β ≺S (α+ β), (α× β), (α− β).

Supóngase que (α+ β) tiene más paréntesis que se abren de los que se cie-rran. Dado que el primer paréntesis y el último de la expresión se cancelan


mutuamente, entonces el problema debe estar en α o en β, lo que contra-dice la hipótesis inductiva. Entonces, (α+ β) tiene paréntesis balanceados.Con un razonamiento análogo se demuestran los casos de (α×β) y (α−β).

Capítulo 2

Lenguajes de programación

Con el fin de ilustrar algunas aplicaciones de la lógica a la computación,presentaremos tres tipos de lenguajes. El primer tipo consiste en dos len-guajes imperativos: IMP y el lenguaje de comandos custodiados de Dijkstra.En estas notas se sigue la notación que aparece en [10], pero ambos len-guajes aparecieron antes ([6] y [4]).

El segundo comprende dos lenguajes funcionales. La sintaxis de los doses igual y se distinguen únicamente por su semántica. La notación presen-tada está tomada también de [10].

El tercero no es exactamente un lenguaje de programación, sino de des-cripción de procesos concurrentes (es decir, procesos que actúan de manerasimultánea e intercambian información entre sí): CCS (calculus of concu-

rrent systems). Este lenguaje es el tema de [9].

La notación de Backus-Naur (BNF) es ya un estándar para la presen-tación de la sintaxis de lenguajes de programación. Sin embargo, en elterreno de la semántica siguen predominando las explicaciones informales.Aquí, en cambio, se usará una notación formal de aceptación creciente: lasemántica operacional estructural. Aunque no es el único formalismo paradescribir los lenguajes de programación (por ejemplo, la semántica denota-cional es una opción matemáticamente más elegante) sí es el más cercanoa las intuiciones del programador típico.

27

28 CAPÍTULO 2. LENGUAJES DE PROGRAMACIÓN

2.1. Programación imperativa

La sintaxis del lenguaje IMP se describe a continuación en la notaciónde Backus-Naur. Empezaremos con las expresiones aritméticas (que ya sepresentaron antes):

a ::= n | x | (a + a′) | (a − a′) | (a × a′)

donde n ∈ Z, x ∈ Var y a, a′ ∈ EA.Tenemos ahora las expresiones booleanas EB:

b ::= V | F | a0 = a1 | a0 ≤ a1 | ¬b | (b ∧ b′) | (b ∨ b′)

donde a0, a1 ∈ EA y b, b′ ∈ EB. Finalmente, los comandos del lenguaje sedefinen así:

c ::= skip | x := a | (c ; c′) | (if b then c else c′) | (while b do c)

2.1.1. Semántica operacional estructural

La forma más común de definir el significado de las construcciones deun lenguaje es por medio de explicaciones en una lengua natural (inglés,generalmente). Sin embargo, el lenguaje natural se presta a las ambigüe-dades y éstas, a su vez, a los errores o a las divergencias entre las diferentesimplementaciones de un mismo lenguaje. Para evitar estos problemas, aquíse usarán reglas de semántica operacional estructural o SOE, para abreviar.

Una regla de inferencia tiene la forma siguiente:

p1, . . . , pn

q

donde p1, . . . , pn son las premisas y q es la conclusión. Las reglas de SOE

son un tipo particular de reglas de inferencia en las que las premisas y laconclusión son transiciones. Una transición tiene la forma

α→ β

La forma concreta de las expresiones α y β, así como las transiciones acep-tables, se definirán más adelante.

IMP es un lenguaje imperativo típico: el comando básico es la asignaciónde valor a las variables de la memoria de la computadora. Para definir

2.1. PROGRAMACIÓN IMPERATIVA 29

el significado de una asignación se puede partir de la existencia de unamáquina virtual que posee una memoria con localidades con nombre: x,y, etc. Para simplificar, se puede pensar que el conjunto de localidades dela memoria coincide con el conjunto Var y que estas localidades puedentomar valores de Z.

Un estado de la memoria es una función σ : Var → Z. La expresiónσ(x) nos dice que valor contiene la localidad x en el estado σ. La alteracióndel valor de una sola localidad de la memoria cuando ésta se encuentraen el estado σ se representa por medio de la función σ[m/x], donde x es lalocalidad cuyo valor se modifica y m es el nuevo valor. Más formalmente,se tiene que:

σ[m/x](y) ={

σ(y) si x 6= y

m en caso contrario.El conjunto de estados es Σ.

En el caso de las expresiones aritméticas, las transiciones α → β tienela forma

〈a, σ〉 → n

donde a ∈ EA, σ ∈ Σ y n ∈ Z. En este caso diremos que “evaluar operacio-nalmente la expresión a en el estado σ da como resultado el valor n”. Dichaevaluación se realiza de acuerdo con las siguientes reglas:

〈n, σ〉 → n 〈x, σ〉 → σ(X)

〈a0, σ〉 → n0 〈a1, σ〉 → n1 n0 op n1 = n

〈a0 op a1, σ〉 → n

En esta regla op puede ser +, − o × y op, +Z, −Z o ×Z (por conveniencia,ambos operadores deben coincidir).

En las expresiones booleanas, una transición es 〈b, σ〉 → T, con b ∈ EB,σ ∈ Σ y T ∈ {V, F}. Las reglas operacionales son:

〈V, σ〉 → V 〈F, σ〉 → F

〈a0, σ〉 → n 〈a1, σ〉 → m

〈a0 = a1, σ〉 → Vsii n y m son iguales

〈a0, σ〉 → n 〈a1, σ〉 → m

〈a0 = a1, σ〉 → Fsii n y m no son iguales


〈a0, σ〉 → n 〈a1, σ〉 → m

〈a0 ≤ a1, σ〉 → Vsii n es menor o igual a m

〈a0, σ〉 → n 〈a1, σ〉 → m

〈a0 ≤ a1, σ〉 → Fsii n no es menor o igual a m

〈b, σ〉 → V

〈¬b, σ〉 → F

〈b, σ〉 → F

〈¬b, σ〉 → V

〈b0, σ〉 → T0 〈b1, σ〉 → T1

〈b0 ∧ b1, σ〉 → T

con T = V si T0, T1 = V y T = F

en caso contrario

〈b0, σ〉 → T0 〈b1, σ〉 → T1

〈b0 ∧ b1, σ〉 → T

con T = V si T0 = V o T1 = V yT = F en caso contrario

Las reglas de transición de los comandos son así:

〈c, σ〉 → σ′,

donde c ∈ IMP y σ, σ′ ∈ Σ. El valor de σ′ se infiere de este modo:

Comandos atómicos

〈skip , σ〉 → σ〈a, σ〉 → m

〈X := a, σ〉 → σ[m/X]

Composición secuencial

〈c0, σ〉 → σ′′ 〈c1, σ′′〉 → σ′

〈c0 ; c1, σ〉 → σ′

Condicionales

〈b, σ〉 → V 〈c0, σ〉 → σ′

〈if b then c0 else c1, σ〉 → σ′

〈b, σ〉 → F 〈c1, σ〉 → σ′

〈if b then c0 else c1, σ〉 → σ′

Ciclos

〈b, σ〉 → F

〈while b do c, σ〉 → σ

〈b, σ〉 → V 〈c, σ〉 → σ′′ 〈while b do c, σ′′〉 → σ′

〈while b do c, σ〉 → σ′

2.1. PROGRAMACIÓN IMPERATIVA 31

Dadas las reglas anteriores, no es difícil ver que el programa de IMP

siguiente calcula el factorial del número n (si n ≥ 0) y lo guarda en lalocalidad y:

x := 1;y := 1;while x ≤ n do

(x := x + 1;y := y × x)

2.1.2. No determinismo

Como primera aproximación a la computación, IMP es bastante bueno.No obstante, hay una serie de “fenómenos” computacionales que no pue-den modelarse con IMP. Uno de estos es el no determinismo, es decir, laposibilidad de que la ejecución de un programa (o un conjunto de ellos) déresultados distintos en distintas ocasiones a pesar de que recibe los mismosdatos de entrada siempre.

El no determinismo puede surgir en diversas situaciones. La más comúnes la concurrencia de procesos (como se verá más adelante), pero tambiénpuede presentarse por una decisión en el diseño mismo de los lenguajesde programación. En este caso, el lector que se enfrenta por primera vezal no determinismo podrá pensar que se trata de una maniobra artificialsin justificación. Pero sí hay un motivo para introducir voluntariamenteno determinismo en un lenguaje: al presentarlo al margen de sus causas(como la concurrencia) es mucho más fácil entender su naturaleza pues noaparece entremezclada con características propias de otras situaciones (denuevo, como en la concurrencia).

Así que ahora se presentará un lenguaje imperativo con no determinis-mo explícito. Para esto necesitaremos una categoría especial de comandosllamados comandos resguardados (guarded commands). La sintaxis es

g ::= b → c | g g′

donde g y g′ son comandos resguardados y b ∈ EB.Como los comandos resguardados son básicos en nuestro lenguaje, lo

llamaremos GCL: guarded command language. He aquí la sintaxis de GCL:

c ::= skip | abort | x := a | (c ; c′) | if g fi | do g od


donde abort es un nuevo programa primitivo, g es un comando resguarda-do y c, c′ ∈ GCL.

Nuevamente, la mejor forma de explicar el significado de los coman-dos de GCL es por medio de reglas operacionales. Comencemos con las decomandos resguardados:

〈b, σ〉 → V

〈b → c, σ〉 → 〈c, σ〉〈b, σ〉 → F

〈b → c, σ〉 → fail

〈g0, σ〉 → 〈c, σ′〉

〈g0 g1, σ〉 → 〈c, σ′〉

〈g1, σ〉 → 〈c, σ′〉

〈g0 g1, σ〉 → 〈c, σ′〉

〈g0, σ〉 → fail 〈g1, σ〉 → fail〈g0 g1, σ〉 → fail

Ahora seguimos con las reglas para comandos generales:

〈skip , σ〉 → σ〈a, σ〉 → m

〈X := a, σ〉 → σ[m/X]

〈c0, σ〉 → σ′′ 〈c1, σ′′〉 → σ′

〈c0 ; c1, σ〉 → σ′

〈c0, σ〉 → 〈c′0, σ′〉

〈c0 ; c1, σ〉 → 〈c′0 ; c1, σ′〉

〈g, σ〉 → 〈c, σ′〉

〈if g fi , σ〉 → 〈c, σ′〉

〈g, σ〉 → fail〈do g od , σ〉 → σ

〈g, σ〉 → 〈c, σ′〉

〈do g od , σ〉 → 〈c ; do g od , σ′〉

El lector puede verificar, haciendo uso de las reglas anteriores y de suconocimiento del viejo algoritmo de Euclides, que el siguiente programacalcula el máximo común divisor de los enteros positivos n y m y lo guardaen las localidades x y y.

x := n;y := m;do

x > y → x := x − y

y > x → y := y − x

od

2.2. UN LENGUAJE FUNCIONAL 33

Nota: x > y es una abreviatura, obviamente, de y ≤ x ∧ ¬(x = y).

2.2. Un lenguaje funcional

Un estilo de programación radicalmente distinto al imperativo es el fun-cional. A riesgo de simplificar, la idea básica es que en lugar de programascon instrucciones detalladas a la computadora, se deben usar definicionesde funciones y aplicaciones de éstas a argumentos dados. Para evitar con-fusiones, es mejor entrar en materia y presentar la sintaxis de un lenguajefuncional simple:

t ::= n | x | t + t′ | t − t′ | t × t′ | if t then t′ else t′′ | fi(t1, . . . , tn)

t, t′ y t′ designan términos de nuestro lenguaje funcional. Obsérvese co-mo en el condicional no se usan expresiones booleanas sino términos comocondición. Como se verá más adelante en la presentación formal de la se-mántica, el valor 0 tendrá el papel de verdadero y cualquier otro valor seconsiderará falso.

El estilo funcional de programación permite prescindir de la referenciaa una máquina virtual y su memoria. En su lugar, las funciones tomarán susignificado a partir de declaraciones. Una declaración es un conjunto finitode ecuaciones donde, del lado izquierdo, aparace una función con varia-bles como argumentos y, del lado derecho, aparecen términos del lenguajefuncional.

f1(x1, . . . , xn1) = d1...

fk(x1, . . . , xnk) = dk

donde d1, . . . , dk son términos del lenguaje funcional. No se permite más deuna ecuación por cada función, pero sí se acepta la recursividad, es decir,que una función aparezca del lado derecho de la ecuación que la define.Las transiciones ahora son de la forma

t →ds t′

donde t y t′ son términos del lenguaje, d es una declaración (y, por tanto,las transiciones dependen de declaraciones específicas) y s puede tomar


el valor v (llamada por valor) o n (llamada por nombre), que designana dos estilos semánticos posibles. En el estilo de llamada por valor, losargumentos de las funciones son evaluados antes de evaluar la funciónmisma. En el estilo de llamado por nombre, la evaluación se pospone hastaque se evalúa el cuerpo mismo de la función. La diferencia entre los dosestilos se manifiestan sólo en una regla de evaluación de términos y, poreste motivo, es mejor pasar directamente a las reglas antes de profundizaren las diferencias semánticas:

Reglas con llamada por valor

Números

n →dv n

Operadores

t0 →dv n0 t1 →d

v n1

t0 op t1 →dv n0 op n1

Condicional verdadero

t0 →dv 0 t1 →d

v n1

if t0 then t1 else t2 →dv n1

Condicional falso

t0 →dv n0 t2 →d

v n2 n0 6= 0if t0 then t1 else t2 →d

v n2

Funciones

t1 →dv n1 · · · tmi

→dv nmi

di[n1/x1,...,nmi/xmi

] →dv n

fi(t1, . . . , tmi) →d

v n

Conviene prestar atención a la última regla, pues es la que varía con res-pecto a la llamada por nombre.

2.2. UN LENGUAJE FUNCIONAL 35

Reglas con llamada por nombre

Números

n →dn n

Operadores

t0 →dn n0 t1 →d

n n1

t0 op t1 →dn n0 op n1

Condicional verdadero

t0 →dn 0 t1 →d

n n1

if t0 then t1 else t2 →dn n1

Condicional falso

t0 →dn n0 t2 →d

n n2 n0 6= 0if t0 then t1 else t2 →d

n n2

Funciones

di[t1/x1,...,tmi/xmi

] →dn n

fi(t1, . . . , tmi) →d

n n

Es momento de presentar un ejemplo de programa. Supóngase que setiene la siguiente declaración:

f1(x) = if x then 1 else f1(x − 1) × x

f2(x, y) = x

f3(x) = f3(x + 1)

Entonces el programa f1(n) calcula el factorial de n, en cualquiera de losdos estilos de programación. En cambio, considérese el programa

f2(2, f3(1)).

De acuerdo con las reglas de llamado por nombre, para realizar la evalua-ción del programa debemos evaluar la expresión

x[x/2,y/ f3(1)] = 2


que, de acuerdo con la regla para números, nos da 2. En cambio, las reglasde llamada por valor nos piden que primero evaluemos los términos

2 y f3(1)

el segundo de los cuales nunca nos da un resultado, como puede deducirsede la tercera ecuación de la declaración.

Nota: si se adopta el estilo de llamada por valor, el lenguaje funcionalse asemeja a un subconjunto de ML. Si se adopta llamada por nombre, seráparecido a Haskell.

2.3. Procesos concurrentes

La idea de que un sistema de cómputo se basa en la ejecución secuencialde una serie de instrucciones por parte de un ente aislado hace mucho quees obsoleta.

La mayoría de los sistemas actuales contiene, en mayor o menor medi-da, subsistemas que actúan de manera simultánea (real o simuladamente)y que intercambian información entre sí. Estos sistemas se llaman concu-

rrentes.Hay varios modelos de cómo se realiza el intercambio de información

entre subsistemas, pero dos son los fundamentales: (a) memoria comparti-da; (b) envío de mensajes. En el primero, se supone que hay un área de lamemoria (variables, buffers, etc.) a la que varios sistemas concurrentes tie-nen acceso para guardar o leer datos. Por su parte, el envío de mensajes serealiza por un medio abierto (difusión) o por medio de canales específicos.

En los 80, Robin Milner propuso un lenguaje de especificación para pro-cesos concurrentes: CCS (Communicating Concurrent Systems). Dicho len-guaje consta de:

Un conjunto de valores (enteros, por ejemplo) que se envían o recibena través de canales α, β, etc.

Operadores para la composición secuencial o paralela de procesos.

Un operador de “elección”

Operaciones para reetiquetar canales y restringir el acceso a éstos.

2.3. PROCESOS CONCURRENTES 37

Para comenzar, tenemos las acciones de comunicación entre procesosbásicas:

λ ::= τ | α!m | α?m

τ es la acción nula, α!m es el envío de m por el puerto de salida del canalα y α?m es la recepción de m por el puerto de entrada del mismo canal.

Recurriendo de nuevo a la notación BNF, los procesos de CCS se definenasí:

p ::= nil | λ . p |∑

i∈I

pi | p ‖ p′ | p\L | p[ f ] | P

En términos informales, la sintaxis contienen los siguientes elementos:

nil es un proceso que no realiza ninguna acción y se considera primi-tivo;

λ es una acción;∑

es la elección arbitraria de un proceso tomado del conjunto deprocesos indexado por I;

‖ es la composición paralela de procesos (intuitivamente, ambos pro-cesos pueden realizarse simultáneamente);

L es un conjunto de canales (cuyo acceso se restringirá a otros proce-sos, como se verá más adelante en las reglas);

P designa a un proceso definido por medio de una expresión del tipo

P ≡def p

que puede tener carácter recursivo.

Las ideas anteriores se pueden expresar con más claridad por medio dereglas SOE:

Procesos resguardados

λ . pλ

−→ p

Sumas


p jλ

−→ q∑

i∈I piλ

−→ qj ∈ I

Composición

p0λ

−→ p′

0

p0 ‖ p1λ

−→ p′

0 ‖ p1

p1λ

−→ p′

1

p0 ‖ p1λ

−→ p0 ‖ p′

1

p0λ

−→ p′

0 p1λ

−→ p′

1

p0 ‖ p1τ

−→ p′

0 ‖ p′

1

Restricción

pλ

−→ q

p\Lλ

−→ q\Lλ 6∈ L ∪ L

Reetiquetamiento

pλ

−→ q

p[ f ]f(λ)−→ q[ f ]

Identificadores

pλ

−→ q

Pλ

−→ qdonde P ≡def p.

análisis lógico -...

Documents