1 logica clasica proposicional web

7/29/2019 1 Logica Clasica Proposicional WEB

1/180

Logica para la Computacion

I) Logica Clasica Proposicional

Alfredo Burrieza Muniz

Manuel Ojeda Aciego

Inmaculada Perez de Guzman Molina

Agustn Valverde Ramos


2/180


3/180

i

La Logica es aquello

que resbala en la inteligencia de las masas

como las gotas de lluvia en un impermeable.

Este documento presenta la Logica Proposicional Clasica y su objetivo es presentar la l ogicacomo una atractiva y util herramienta en las aplicaciones informaticas.

Aunque ha sido pensado para los alumnos de la titulacion de Informatica, sera de interes paratodos aquellos que deseen conocer como la logica puede ser usada para representar y procesar elconocimiento.


4/180

ii

Agradecimientos

A los alumnos de la titulacion de Informatica de la Universidad de Malaga que en los ultimos anoshan ido configurando con sus inquietudes y sugerencias el contenido de este libro.

A todos los componentes del grupo GIMAC, que da a da profundizan en los diversos aspectos dela logica de cara a aplicaciones de interes.


5/180

Indice general

1. Preliminares 1

1.1. Relaciones y Funciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1

1.2. Numeros Naturales y Numerabilidad . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.3. Relaciones de Equivalencia y Relaciones de Orden . . . . . . . . . . . . . . . . . . . 6

1.4. Secuencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.5. Alfabeto y Cadenas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.6. Arboles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.7. Conjuntos Inductivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.7.1. Funciones Recursivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

1.8. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2. Logica y Computacion 23

2.1. Objetivo de la logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2. Tipos de Logicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.3. Expectativas y Limitaciones de la Logica en Computacion . . . . . . . . . . . . . . 262.3.1. El Lengua je . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

2.3.2. La Semantica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

2.3.3. Teora de la Demostracion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.3.4. La Automatizacion de las Deducciones . . . . . . . . . . . . . . . . . . . . . . 35

2.4. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3. Logica Proposicional 39

3.1. El Lenguaje Lprop de la Logica Proposicional . . . . . . . . . . . . . . . . . . . . . . 39

3.1.1. Arbol Sintactico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

3.2. Semantica para la logica clasica proposicional . . . . . . . . . . . . . . . . . . . . . . 443.2.1. Clasificacion semantica de las fbs: Satisfacibilidad y Validez . . . . . . . . . . 47

3.2.2. Relacion de igualdad semantica: Equivalencia Logica . . . . . . . . . . . . . . 49

3.3. Formas Normales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

3.3.1. Forma Normal Negativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

3.3.2. Formas Normales Disyuntivas y Conjuntivas . . . . . . . . . . . . . . . . . . . 62

3.4. Propiedad de Compacidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

3.5. Consecuencia Logica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

3.6. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

iii


6/180

iv INDICE GENERAL

4. Teora de la Demostracion para la Logica Proposicional 774.1. Un Sistema Axiomatico para la Logica Proposicional . . . . . . . . . . . . . . . . . . 78

4.1.1. El Sistema L de Lukasiewicz . . . . . . . . . . . . . . . . . . . . . . . . . . . 784.1.2. Correccion y Completitud de L . . . . . . . . . . . . . . . . . . . . . . . . . . 86

4.1.3. Independencia de los Axiomas de L . . . . . . . . . . . . . . . . . . . . . . . . 884.2. Deduccion Natural . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 914.3. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

5. Razonamiento Automatico en la logica proposicional 1035.0.1. Algoritmo de Quine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

5.1. Sistemas de refutacion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055.1.1. Las Tablas de Verdad como Sistema de refutacion . . . . . . . . . . . . . . . 107

5.2. Metodo de las Tablas Semanticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1085.2.1. Reglas de Extension . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.2.2. Descripcion del metodo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

5.3. Metodos que requieren que la entrada este en forma clausal . . . . . . . . . . . . . . 1155.3.1. Algoritmo de Quine como metodo de refutacion . . . . . . . . . . . . . . . . . 1165.3.2. El metodo Davis-Putnam . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1185.3.3. Metodo de Resolucion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1215.3.4. Resolucion como algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1285.3.5. Resolucion Lineal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1305.3.6. Resolucion Lineal Ordenada . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1315.3.7. Complejidad del Metodo de Resolucion . . . . . . . . . . . . . . . . . . . . . 135

5.4. Clausulas de Horn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1395.5. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

6. El metodo TAS 1476.1. -arboles como representacion de FNNs . . . . . . . . . . . . . . . . . . . . . . . . . 1496.1.1. -listas: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1496.1.2. Transformando -arboles en fnns . . . . . . . . . . . . . . . . . . . . . . . . . 1506.1.3. Transformando fnns en -arboles . . . . . . . . . . . . . . . . . . . . . . . . . 1526.1.4. Operaciones basicas con -arboles . . . . . . . . . . . . . . . . . . . . . . . . 1536.1.5. -arboles restringidos: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

6.2. Reglas de transformacion del metodo TAS . . . . . . . . . . . . . . . . . . . . . . . . 1586.2.1. Regla de Reduccion Completa . . . . . . . . . . . . . . . . . . . . . . . . . . . 1586.2.2. Regla del literal puro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1606.2.3. Regla de Reduccion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

6.3. El Algoritmo TAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1616.4. Ejemplo 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1636.5. Ejemplo 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1656.6. Ejemplo 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1666.7. Ejemplo 4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1686.8. Ejemplo 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1706.9. Ejercicios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172


7/180

Captulo 1

Preliminares

El concepto de conjunto o colleccion es una de las ideas mas destacadas en las matematicas delsiglo XX.1 Desde el trabajo pionero del matematico aleman Georg Cantor (1845-1918) a finales del

siglo XIX, la sencilla nocion de conjunto ha tenido una profunda influencia en todos los aspectos yniveles de la investigacion matematica.

El hecho que diferencia mas claramente el tratamiento matematico de los conjuntos es el usode notacion simbolica. Un ejemplo importante de esta notacion es la de relacion de pertenencia,x A denota que x es un elemento del conjunto A. x A denota que x no es un elemento delconjunto A.

Para especificar un conjunto hemos de nombrar cuales son sus elementos. Podemos definirlo porextension(enumerando sus elementos; solo si es finito) o por comprehension{x N|x es primo y x 10}.

Una cuestion fundamental que podemos preguntarnos sobre los conjuntos es cuando son iguales.Definimos que dos conjuntos son iguales cuando tienen los mismos elementos, es decir,

si x A entonces x BA = B si y solo si y

si x B entonces x A

As pues, un conjunto esta determinado unicamente por sus elementos (es decir, por su caracterextensional) y no por el modo en que los nombremos (no por su caracter intensional).

En este tema introducimos las nociones, notaciones y resultados preliminares que vamos a utili-zar en el resto del desarrollo. Suponemos conocidas las nociones intuitivas de conjunto, subconjunto,conjunto vaco y las definiciones de union e interseccion de conjuntos. No incluimos demostraciones,ya que consideramos que el lector es conocedor de todo lo expuesto en este captulo y el ob jetivode su inclusion no es otro que hacer el documento autocontenido en la medida de lo posible.

1.1. Relaciones y Funciones

Las nociones de relacion y funcion formalizan, respectivamente, los conceptos utilizados en lavida real de relaciones entre objetos y asignaciones de unos objetos a otros. La formalizaci onde ambos conceptos se basa en la construccion estandar de conjuntos conocida con el nombre deproducto cartesiano.

1No deja de ser sorprendente, ya que no establece nada cuantitativo o geometrico.

1


8/180

2 CAPITULO 1. PRELIMINARES

Dados dos conjuntos A, B = , los objetos de la forma (a, b) con a A y b B se llaman paresordenados de A y B. Para dos conjuntos A y B (posiblemente vacos) se define el productocartesiano de A por B, denotado A B, como sigue:

A B = {(a, b) | a A, b B}

El producto cartesiano de n conjuntos se define mediante la extension natural de la nocion de parordenado al de n-upla ordenada:

Dados n conjuntos A1, A2, . . . , An, el producto cartesiano A1 A2 An se define comosigue:

A1 A2 An = {(a1, . . . , an) | ai Ai, 1 i n}

Si los n conjuntos son iguales, A1 = A2 = = An = A, el producto cartesiano se denota por An.

Relaciones

Dados dos conjuntos A y B, una relacion de A en B es cualquier subconjunto R (posiblementevaco) de A B.Dada una relacion R de A en B, el conjunto {x A | existe y B tal que (x, y) R} se llamadominio de R, y se denota Dom(R), y el conjunto {y B | existe x A tal que (x, y) R} sellama imagen de R, y se denota Im(R).

En particular, si B = A, una relacion de A en A se llama relacion binaria en A. En general,para todo numero natural n 2, una relacion n-aria en A (tambien llamada relacion dearidad n en A), es cualquier subconjunto de An.

Si R es una relacion binaria en A, como alternativa a (x, y) R, es frecuente usar las notaciones:

xRy, leda x esta relacionado con y,

y R(x), leda y es accesible desde x mediante R. Para cada x A, definimos el conjuntoR(x) = {y | (x, y) R}.

Damos a continuacion definiciones de nuevas relaciones obtenidas a partir de otras relaciones:

Si R y S son relaciones de A en B entonces R S y R S son relaciones de A en B llamadasunion e interseccion de R y S, respectivamente.

Sea R una relacion de A en B y S una relacion de B en C, la relacion de A en C denotadaR S y definida por

(a, c) R S si y solo si existe un b B tal que (a, b) R y (b, c) S

se denomina composicion de R y S.

Si R es una relacion de A en B entonces R1 es la relacion de B en A definida por

aR1b si y solo si bRa

y se llama inversa de R.

Ejemplo 1.1


9/180

1.1. RELACIONES Y FUNCIONES 3

1. Dado un conjunto cuyos elementos denotan personas, la union de las relaciones binarias ma-dre y padre es la relacion progenitor, la composicion de las relaciones binarias madrey padre es la relacion abuelo y la inversa de la relacion padre es la relacion hijo.

2. Dado un conjunto arbitario, A, la interseccion de las relaciones binarias y en P(A)2

, quesin duda son bien conocidas para el lector, es la relaci on binaria de igualdad de subconjuntosde A.

Funciones

Una relacion R de un conjunto A en un conjunto B se dice que es una funcion, cuando cumplela condicion siguiente:

Si xRu y xRv, entonces u = v

es decir, cada elemento del dominio de R esta relacionado con un unico elemento del conjunto

imagen.

Para denotar funciones se utilizan habitualmente letras minusculas tales como f , g , . . ., y paraindicar que f es una funcion de A en B, se utiliza la notacion f : A B.

Una funcion f : A B se dice parcial si Dom(f) A y se dice total cuando Dom(f) = A.

Para toda funcion f : A B y para todo x Dom(f), el elemento y B tal que (x, y) f, sedenota por f(x) y se llama la imagen de x por f.

En todo lo que sigue, funcion significara funcion total.

Para todo conjunto A, toda funcion f : An A (con n natural 1 y A1 = A) se dice que f esuna funcion n-aria o de aridad n (o de n argumentos) sobre A. En particular, cuando n = 2, y en

un contexto algebraico, se dice que f es una operacion interna en A. En tal caso, es costumbredenotar xf y (notacion infija) en vez de f(x, y) (notacion prefija).

Una funcion f : A B se dice:

inyectiva si, para todo x, y A se tiene que si f(x) = f(y), entonces x = y.

sobreyectiva si Im(f) = B.

biyectiva si es inyectiva y sobreyectiva.

Notacion:

El conjunto de todas las funciones de un conjunto A en un conjunto B se denotara por BA.

Ejemplo 1.2

1. Para todo conjunto A, la funcion f : A A definida por f(x) = x es biyectiva, se denotapor idA y se llama identidad de A.

2. Dado A, para todo subconjunto B de A definimos XB : A {0, 1} por

2conjunto de todos los subconjuntos de a, tambien denotado 2A.


10/180


XB(x) =

1 si x B

0 si x B

A XB se le llama funcion caracterstica de B.

Si denotamos por P(A) el conjunto cuyos elementos son los subconjuntos de A, la funcion

: P(A) {0, 1}A

definida por (B) = XB, es biyectiva. Por ello, es costumbre denotar al conjunto de las partesde un conjunto A por 2A.

Extension y restriccion de una funcion

Sean f : B C y g : X C con X B. Si para todo x X se verifica que g(x) = f(x). Se diceque g es una restriccion de f a X y que f es una extension de g a B.

Observese que cualquier restriccion de una funcion inyectiva es inyectiva y que cualquier exten-sion de una funcion sobreyectiva es sobreyectiva.

Por ultimo, como en el caso de las funciones, veamos c omo definir nuevas funciones a partir deotras dadas:

Dadas las funciones f : A B y g : B C, la composicion de ambas es una funcion de Aen C, la cual se denota por g f, se lee f compuesta con g,3 y viene dada por

(g f)(x) = g(f(x))

g f hereda las propiedades comunes de f y g, Es decir, si f y g son ambas inyectivas, sobre-yectivas o biyectivas, entonces g f es inyectiva, sobreyectiva o biyectiva, respectivamente.

Si f : A B es biyectiva, la relacion f1 es una funcion biyectiva de B en A llamada lainversa de f. Es inmediato que en tal caso, f1 f = idA y f f

1 = idB .

1.2. Numeros Naturales y Numerabilidad

La caracterstica basica de un conjunto finito es su tamano, es decir, el numero de elementosque posee. Este concepto y sus propiedades mas basicas (si A B, entonces el numero de elementos

de A no supera al numero de elementos de B, etc) son adquiridos a muy temprana edad por el serhumano. Por el contrario, la extension del concepto de tamano a conjuntos infinitos no esta exentade dificultades y no se adecua al uso de la intuicion. En esta seccion revisaremos las nociones yresultados basicos acerca del tamano de los conjuntos, que utilizaremos en adelante.

El conjunto de los naturales, {0, 1, 2, . . .}, se denota por N. Denotaremos por N el conjuntoN {0} y por [n] el conjunto {1, 2, . . . , n}.

3Algunos autores prefieren usar la notacion f g. Nosotros utilizaremos la notacion g f porque, posiblemente,sea la mas extendida, y porque coincide con el orden de escritura de la notacion prefija, es decir, (g f)(x) = g(f(x)).


11/180

1.2. NUMEROS NATURALES Y NUMERABILIDAD 5

Un conjunto A se dice numerable si existe una funcion sobreyectiva h : N A. En casocontrario, se dice que A es no numerable. Si la funcion h es ademas inyectiva, se dice que A es

infinito numerable. Si consideramos idN, concluimos que N es infinito numerable.

Si A es numerable pero no infinito numerable, entonces existe un n N y una funcion biyectivah : [n] A. En este caso, se dice que A es finito y que su numero de elementos es n.

Si A es numerable, la biyeccion h : N A (o h : [n] A en el caso finito) proporciona unaenumeracion de sus elementos:

A = {a1, a2, . . . , an, . . . } para el caso infinito.

A = {a1, a2, . . . , an} para el caso finito

Los conjuntos infinitos numerables y los no numerables no son finitos, y por esta razon decimosque son conjuntos infinitos.

Para comparar entre s a los conjuntos infinitos se introduce la nocion de cardinal de un

conjunto. Nos limitaremos al respecto a decir que a cada conjunto A se le asocia un ente llamadocardinal de A, denotado |A|, tal que

1. |A| = 0 si A = .

2. Si A es finito, |A| = numero de elementos de A.

3. Si existe una funcion inyectiva f : A B entonces decimos que |A| es menor o igual que|B| y se denota |A| |B|.

4. Si |A| |B|, pero no existe una funcion inyectiva de B en A, se dice que |A| < |B|.

5. Si existen funciones inyectivas f : A B y g : B A, o equivalentemente, existe unabiyeccion h : A B, entonces decimos que |A| es igual que |B| y se denota |A| = |B|.

6. El cardinal de un conjunto infinito numerable se denota por 0.

El cardinal de A se dice finito si A es finito e infinito en caso contrario. El menor cardinalinfinito es 0 y para todo conjunto finito, A, se tiene |A| < 0.

El siguiente teorema de Cantor asegura la existencia de cardinales tan grandes como se quiera.

Teorema 1.1 Para todo conjunto A se verifica que |A| < |2A|.

En relacion a la cardinalidad de los conjuntos numericos, se tiene que |Z| = |Q| = 0, es decir,los enteros y los racionales son infinitos numerables, mientras que para el conjunto R de los numerosreales, se tiene que 0 < |R|. El cardinal de R se denota por 1.

Principio de Induccion

El principio de induccion (IND) es una propiedad caracterstica del conjunto N y constituye unaimportante herramienta matematica.

IND (Formulacion 1)

Sea P una propiedad relativa a los numeros naturales tal que:


12/180


1. 0 verifica P. (Caso base)

2. Para cada natural n, si n verifica P entonces n + 1 verifica P. (Hipotesis de Induccion)

En tales condiciones, todos los naturales verifican P.

En numerosas argumentaciones es util aplicar la siguiente formulacion.

IND (Formulacion 2)

Sea P una propiedad relativa a los naturales tal que

1. 0 verifica P. ( Caso base)

2. Para cada natural n > 0, si todos los naturales anteriores a n verifican P entonces n verificaP. (Hipotesis de Induccion)

En tales condiciones, todos los naturales verifican P.

A veces, cierta propiedad P solo se verifica a partir de un cierto natural k, es decir, para todon N tal que n k. En tales condiciones, es obvio que es posible aplicar el Principio de Induccionen cualquiera de las dos formulaciones anteriores sin mas que modificar el caso base, sustituyendo0 verifica P, por k verifica P. Se tiene as el Principio de Induccion a partir de k.

1.3. Relaciones de Equivalencia y Relaciones de Orden

Las relaciones de equivalencia y las relaciones de orden, formalizan, respectivamente, los procesosnaturales de clasificacion y ordenacion de los elementos de un conjunto.

Una relacion binaria R sobre un conjunto A puede verificar, entre otras, las siguientes propie-dades:

Reflexiva: Para todo x A, se tiene que xRx.

Simetrica: Dados x, y A, si xRy, entonces yRx.

Antisimetrica: Dados x, y A, si xRy e yRx, entonces x = y.

Transitiva Dados x,y ,z A, si xRy e yRz, entonces xRz.

Relaciones de Equivalencia

Una relacion binaria R sobre A se dice de equivalencia si es reflexiva, simetrica y transitiva.Dada una relacion de equivalencia sobre A, para todo x A se define el conjunto

[x] = {y A|xRy}

que se denomina clase de equivalencia de x. El conjunto {[x] | x A} de todas las clases deequivalencia se llama conjunto cociente de A por R y se denota A/R.

Puesto que para todo x A se tiene que x [x], podemos asegurar que A =

xA[x]. Ademas,es inmediato comprobar que, para todo x, y A, se tiene que o bien [x] = [y] o bien [x] [y] = .Por lo tanto, A/R es una particion o clasificacion del conjunto A.


13/180

1.3. RELACIONES DE EQUIVALENCIA Y RELACIONES DE ORDEN 7

Clausuras

Dada una relacion binaria R sobre un conjunto A, definida mediante la propiedad P, en ocasionesinteresa describir, en terminos de R, la mnima relacion (en el sentido de la inclusion de conjuntos),R, tal que:

R contiene a R,

R satisface P.

Una tal relacion, si existe, se denomina P-clausura de R.

Vamos a definir algunas de las P-clausuras mas utilizadas. Comencemos dando la definicion depotencia de exponente natural de una relacion:

Definicion 1.1 Para toda relacion binaria, R, sobre A,

R0 = idA y Rn+1 = Rn R

e er r Observese que x Rn y si y solo si existen n1 elementos, a1, . . . , an1 ,de A tal que x R a1, a1 R a2, . . .y an1 R y.

Definicion 1.2 Si R es una relacion binaria en un conjunto A:

1. Llamamos clausura reflexiva de R a la union Rr = R IA.

2. La union R+ =

n1 Rn, se llama la clausura transitiva (o cierre transitivo) de R y es

la menor relacion transitiva que contiene a R.

3. La uni on R = n0 Rn, se llama la clausura reflexiva y transitiva (o cierre reflexivoy transitivo) de R y es la menor relacion reflexiva y transitiva que contiene a R.4. la union Rs = R R1, se llama clausura simetrica de R.

5. Por utimo, llamamos clausura de equivalencia de R a la relacion Req = (R)s y es lamenor relacion de equivalencia que contiene a R.

En el caso de que A sea finito, se demuestra que la clausura transitiva, R+, de una relacionbinaria R en A puede expresarse como union de una familia finita. Concretamente, si |A| = n,entonces

R+ =n

i=1 RiRelaciones de Orden

Una relacion R sobre el conjunto A se dice de orden parcial si es reflexiva, antisimetrica ytransitiva. En tal caso, el par (A, R) se dice que es un conjunto parcialmente ordenado. Porejemplo, para todo conjunto A se tiene que (2A, ) es un conjunto parcialmente ordenado.

Las relaciones de orden parcial son frecuentemente denotadas por el smbolo , y as lo haremosen todo lo que sigue.


14/180


Sea (A, ) un conjunto parcialmente ordenado. Un subconjunto X no vaco de A, se dicetotalmente ordenado, si para todo x, y X, se tiene que x y o y x.

Un orden parcial se dice que es un orden total (o un orden lineal) si el propio A estotalmente ordenado. Obviamente, si es un orden total sobre A, todo subconjunto X de A estotalmente ordenado.

(N, ), (Z, ), (Q, ) y (R, ), donde es la relacion de precedencia habitual, son conjuntostotalmente ordenados.

Definicion 1.3 Sea (A, ) un conjunto parcialmente ordenado y X un subconjunto no vaco deA. Entonces,

1. un elemento b X se dice que es el mnimo de X (o el primer elemento de X), si b xpara todo x X.

2. un elemento b X se dice que es el maximo de X (o el ultimo elemento de X), si x bpara todo x X.

3. un elemento b X se dice que es un elemento maximal de X si para todo x X se tiene quesi x b entonces x = b.

4. un elemento b X se dice que es un elemento minimal de X, si para todo x X se tieneque si x b entonces x = b.

Definicion 1.4 Una relacion de orden parcial sobre A se dice que es un buen orden sobreA o bien que (A, ) es un conjunto bien ordenado, si todo subconjunto X de A tiene primerelemento.

(N, ) es un conjunto bien ordenado, de hecho, en N son equivalentes el principio de induccion,

enunciado anteriormente, y su buena ordenacion. Por el contrario, (Z, ), (Q, ) y (R, ) no sonconjuntos bien ordenados.

1.4. Secuencias

En esta seccion presentamos la nocion quizas mas utilizada en las Ciencias de la Computacion:la nocion de secuencia, introducida para describir una coleccion de objetos de algun tipo, cuyoorden es importante.

Utilizamos secuencias finitas, por ejemplo, para especificar que cuatro tareas concretas t, u, v yw del conjunto de tareas que intervienen en una aplicacion determinada, han de ser realizadas en

un cierto orden (debido, por ejemplo, a los recursos que estas necesitan). Por otra parte, algunasaplicaciones requieren el uso de secuencias infinitas. Por ejemplo, la descripcion de la imparcialidadde planificacion de un sistema operativo, por tratarse de una propiedad en el lmite, reclama el usode secuencias infinitas. Presentaremos en primer lugar las secuencias en general y en la siguienteseccion nos centraremos en las secuencias finitas.

En determinadas ocasiones se utiliza la siguiente nomenclatura para las funciones:

Dados dos conjuntos I y A, se llama secuencia indizada porI de elementos de A, atoda funcion X : I A.


15/180

1.4. SECUENCIAS 9

La secuencia indizada, X : I A, se denota por (ai)iI (donde ai = X(i) A) y al conjuntoI se le llama conjunto de ndices. En particular, si A 2B (es decir, los elementos de Ason subconjuntos de B), a las secuencias indizadas de elementos de A se les llama familias deconjuntos.

Una secuencia (ai)iI se dice numerable (respectivamente, no numerable) si el conjunto I dendices es numerable (respectivamente, no numerable). El conjunto de ndices frecuentemente usadopara indizar secuencias finitas es [n] y para las secuencias infinitas numerables es N.

Las secuencias infinitas numerables de elementos de A se denominan sucesiones de elementosde A. Es costumbre denotar las secuencias finitas por [a1, . . . , an] y las sucesiones por a1, . . . , an, . . .o {an}nN.

En relacion al cardinal del conjunto AI (de todas las secuencias sobre A indizadas por I) setiene:

Si |I| es infinito y |A| > 1, entonces |AI| > 0.

Si I es finito y |A| 0, entonces |AI| 0. En particular, si |A| = 0 se tiene que |A

I| = 0.

Las familias de conjuntos permiten generalizar la union e interseccion de conjuntos: Sean A1, A2subconjuntos de A, entonces

A1 A2 = {x A| existe un i [2] tal que x Ai}

A1 A2 = {x A| para todo i [2] tal que x Ai}

Para una familia cualquiera de subconjuntos de A, (Ai)iI, definimos la union (resp. intersec-cion) de dicha familia, denotada

iIAi (resp.

iIAi), por

iI

Ai = {x A | existe un i I tal que x Ai}

iI

Ai = {x A | para todo i I, x Ai}

En relacion a la numerabilidad de la union de una familia de conjuntos, se tiene que:

La union numerable de una familia de conjuntos numerables es numerable

En particular, la union numerable de conjuntos numerables, (Ai)iI, es infinito numerable en lossiguientes casos:

1. Uno al menos de los elementos de la familia es infinito numerable.

2. El conjunto de ndices I es infinito numerable, todos los elementos, Ai, de la familia son finitosy Ai Aj = para todo par de elementos distintos de la familia.


16/180


1.5. Alfabeto y Cadenas

Sea a un conjunto numerable y no vaco al que llamamos alfabeto. Una cadena sobre el alfabetoa es toda secuencia finita u : [n] a. El natural n se llama longitud de u y se denota long(u).

Las cadenas (tambien llamadas palabras) se denotan por yuxtaposicion de sus elementos, es decir,u1u2 un (cadena de longitud n). Introducimos la cadena vaca o cadena nula, denotada a osimplemente , por la funcion : a. Si convenimos en denotar el conjunto vaco por [0],entonces : [0] a.

Definicion 1.5 Para todo natural n, sea an el conjunto de las cadenas de longitud n sobre a. Launion de la familia (an)nN, esto es,

nN a

n, se llama el lenguaje universal sobre el alfabeto ay se denota por a.

Definicion 1.6 Dadas dos cadenas u : [m] a y v : [n] a, se define la concatenacion de u yv, denotada uv, como la cadena w : [m + n] a definida por

w(i) = u(i) si 1 i mv(i m) si m + 1 i m + nLa concatenacion es una operacion internasobre el lenguaje universal a. La cadena vaca es el

elemento neutro para dicha operacion (u = u = u), es asociativa y si |a| > 1, no es conmutativa.

Definicion 1.7 Dada una cadena u, una cadena v se dice es unprefijo deu, si existe una cadenaw tal que u = vw. Una cadena v es un sufijo de u, si existe una cadena w tal que u = wv. Unacadena v es una subcadena de u, si existen cadenas x e y tales que u = xvy. Un prefijo, sufijo osubcadena v de una cadena u se dice propia si v = u.

1.6. Arboles

En nuestro estudio la estructura de arbol que vamos a introducir sera una herramienta basica.Usaremos los arboles para representar objetos, para expresar la semantica de objetos, espacios debusqueda de demostraciones y como base de las demostraciones en s.

En esta seccion introducimos la nocion de arbol debida a Gorn 4 y las nociones basicas so-bre arboles. El punto de partida es fijar un conjunto infinito numerable A y una enumeracion{a1, a2, . . . , an, . . .} de A.

Definicion 1.8 Un dominio de arbol, D, es un conjunto de cadenas sobre A (subconjunto de

A

) que satisface las siguientes condiciones:

1. Existe D sin prefijo, la raz del arbol.

2. Para todo u D, todo prefijo de u pertenece a D.

3. Para todo u D tal que uai D, se tiene que uaj D para todo j tal que 1 j < i.

4G. Huet and E. Shapiro et al. Fundamentals of Artificial Intelligence. Springer Verlag, 1986.


17/180

1.6. ARBOLES 11

e er r Observese que por la segunda condicion, para todo dominio de arbol D no vaco se tiene que D.

Ejemplo 1.3 El dominio de arbol

D = {, a1, a2, a3, a1a1, a1a2, a2a1, a2a2, a3a1, a3a1a1}

se representa como aparece en la Figura 1.1:

a1a1

a1

a1a2 a2a1

e

a2

a2a2

a3

a3a1

a3a1a1

Figura 1.1:

Definicion 1.9 Sea un conjunto no vaco a cuyos elementos llamamos etiquetas. Un -arbol(brevemente un arbol) es una funcion T : D donde D es un dominio de arbol. Las cadenasu Dom(T) se acostumbran a llamar los nodos o las direcciones del arbol t. Si D = , la funcionT se denomina arbol vaco. Para todo arbol T no vaco, el nodo se llama la raz de T.

Ejemplo 1.4 Sea = {f,g,h,a,b}. El arbol T : D , donde D es el dominio de arbol delejemplo 1.3 anterior y T es la funcion dada por

{(, f), (a1, h), (a2, g), (a3, b), (a1a1, a), (a1a2, b)(a2a1, b), (a2a2, a), (a3a1, f), (a3a1a1, g)}

se representa como aparece en la Figura 1.2.

Definicion 1.10 El grado de ramificacion de un nodo u es el cardinal del conjunto {ai A |uai Dom(T)} y se denota por d(u). Los nodos u tales que d(u) = 0 se llaman hojas.

Definicion 1.11 Un arbol T se dice de ramificacion finita si d(u) es un natural para todonodo u. Un arbol T se dice binario si para todo nodo u se tiene que d(u) 2 y se dice completosi para todo nodo no hoja, u, se tiene que d(u) = 2.

Un arbolT se dicefinito si Dom(T) es finito y se diceinfinito en caso contrario. Obviamentetodo arbol finito es de ramificacion finita. Los arboles de un solo nodo se llaman arboles hoja.

Los nodos de la forma uai, con ai A, se llaman descendientes inmediatos (o hijos) de u,y al nodo u el ascendiente inmediato (o padre) de cualquiera de sus descendientes inmediatosuai. Si el arbol es binario y d(u) = 2, los descendientes inmediatos de u se denominan descendienteizquierdo y descendiente derecho respectivamente.

Cuando se trabaja con -arboles para un determinado, es costumbre referirse a los nodos porsus etiquetas, y as utilizar expresiones como:


18/180


f

h

a b b

g

a

b

f

g

Figura 1.2:

El nodo a, cuando debera decirse el nodo etiquetado con a.

El arbol o arboles cuyos nodos son elementos de , cuando debera decirse El arbolo arboles cuyos nodos estan etiquetados con elementos de

Utilizamos el ejemplo 1.3 para ilustrar este uso:

1. En el arbol 1.3 todos los nodos a son hojas.

2. En el arbol 1.3 uno de los nodos f es la raz del arbol.

Caminos

Definicion 1.12 Sea T un arbol y u, v Dom(T). Un camino desde u hasta v es una secuenciafinita de nodos u1, u2, . . . , un+1 tal que:

u = u1 y v = un+1.

Para todo j (2 j n), uj = uj1akj para algun akj A.

El natural n se llama longitud del camino.

En arboles infinitos, cabe considerar caminos infinitos.

Definicion 1.13 Un camino infinito desde el nodo u es una sucesion de nodos u1, u2, . . . , un, . . .tal que:

u = u1.

Para todo j > 1, uj = uj1akj para algun akj A

Una rama es un camino infinito desde la raz o un camino desde la raz a una hoja. As, lasramas se clasifican en finitas e infinitas. Obviamente, en un arbol finito solo existen ramas finitasy su numero coincide con el numero de hojas.

Dado un arbol T, para todo nodo u de T existe un unico camino desde la raz al nodo u. Lalongitud de dicho camino se llama la profundidad o el nivel de u. La nocion de profundidad


19/180

1.6. ARBOLES 13

de un nodo estratifica los nodos de un arbol en: nodos de profundidad 0 (la raz), profundidad 1,profundidad 2, etc.

La profundidad o altura de un arbol T es el maximo del conjunto {nivel(u)|u Dom(T)},cuando T no tiene ramas infinitas, e infinito en caso contrario.

El siguiente resultado establece una condicion suficiente para la existencia de ramas infinitas.

Lema 1.1 (Konig) En todo arbol infinito de ramificacion finita existe al menos una rama infinita.

A continuacion presentamos una curiosa aplicacion del Lema de Konig. 5

Vamos a jugar con un conjunto de bolas etiquetadas con numeros naturales, sin restriccionessobre el numero de bolas y sin restricciones sobre los numeros que aparecen en las etiquetas. Supon-gamos que, al inicio del juego, tenemos una caja con una sola bola. Tenemos permiso para sacar labola de la caja y reemplazarla por tantas bolas como queramos, siempre que esten etiquetadas connumeros menores que el de la bola retirada. Esta es toda la mecanica del juego, tomar una bola de

la caja, retirarla y sustituirla por bolas con numeros menores. Por ejemplo, podramos retirar unabola con el numero 30 y sustituirla por cien mil bolas con etiquetas menores que treinta.

El problema consiste en demostrar que, sin importar como actuemos (de acuerdo con las reglas),finalmente acabaremos quedandonos sin bolas en la caja.

Subarboles

Definicion 1.14 SeaT un arbol y u un nodo de T. El subarbol de raz u es el arbol Tu definidocomo sigue:

Dom(Tu) = {v| uv Dom(T)}.

Tu(v) = T(uv).

Para todo arbol T y para todo nodo no hoja u de T, los subarboles cuya raz son los descendientesinmediatos deu se llamansubarboles de u. En particular, sid(u) = 2 se llaman subarbol izquierdoy subarbol derecho respectivamente.

Es inmediato que si Tes de ramificacion finita, todos sus subarboles son tambien de ramificacionfinita. Si ademas T es infinito, por el Lema de Konig, T tiene subarboles infinitos.

Recorridos de un arbol

Describimos a continuacion dos modos habituales de ordenar, enumerar o recorrer los nodos deun -arbol finito. Dichas enumeraciones proporcionan una secuencia de sus nodos contempladoscomo elementos de .

Primero en Profundidad: En todo arbol finito T, la relacion en Dom(T) definida a continuaciones de orden total. Diremos que u v si se cumple alguna de las condiciones siguientes:

1. u es prefijo de v

2. Existen cadenas x,y,z A y elementos ai, aj A con i < j tales que u = xaiy y v = xajz5Ver R. Smullyan. Trees and balls games. Annals of the New York Academy of Sciences, 321:8690, 1979.


20/180


La enumeracion de los nodos de T proporcionada por dicha relacion se llama recorrido primeroen profundidad. Si u v por la primera condicion, se dice que u es un ascendiente de v y quev es un descendiente de u.

Primero en Anchura: En todo arbol finito T, la relacion en Dom(T) definida a continuacion esde orden total. Diremos que u v si se cumple alguna de las condiciones siguientes:

1. long(u) < long(v)

2. Existen cadenas x,y ,z A con long(y) = long(z) y elementos ai, aj A con i < j tales queu = xaiy y v = xajz.

La enumeracion de los nodos de T proporcionada por dicha relacion se llama recorrido primeroen anchura.

Ejemplo 1.5 Para el arbol

f

g

i j h

h

g

k g

i

k

j

el recorrido primero en profundidad viene dado por la siguiente secuencia de sus nodos:

f,g,i,j,h,i,h,k,g,g,k,j

y el recorrido primero en anchura viene dado por la siguiente secuencia de sus nodos:

f,g,h,i,i,j,h,g,k,g,k,j

1.7. Conjuntos InductivosEn diferentes areas de las Ciencias de la Computacion es frecuente introducir objetos mediante

la definicion inductiva de conjuntos. Se entiende por ello la definicion de un conjunto caracterizadopor satisfacer las propiedades siguientes:

es el menor conjunto que contiene a un conjunto dado X llamado conjunto base o conjuntode atomos.

es cerrado para un conjunto F de funciones llamado conjunto de constructores.


21/180

1.7. CONJUNTOS INDUCTIVOS 15

Antes de describir formalmente estos conjuntos, vamos a describir un caso sencillo en el quetanto el conjunto base, como el conjunto de constructores consta de un solo elemento. Se trata dela definicion inductiva de los numeros naturales.

Consideremos el alfabeto a = {O, (, ), } y el lenguaje universal sobre el alfabeto a, es decir,a. Consideremos el operador C : a a definido por C(u) = (u). Entonces:

El subconjunto de a generado a partir del conjunto base X = {O} y el constructor C es

B = {O, (O), ((O)), (((O))), . . .}

Si interpretamos O por el 0 de N y por la funcion sucesor en N, es decir (n) = n + 1, seobtiene el conjunto de los naturales {0, 1, 2, . . . . . .}

e er r Observese que:

1. El conjunto B es el menor subconjunto de a que contiene a O y es cerrado para C, esdecir, para todo u B, se tiene que C(u) = (u) B

2. El conjunto B es la union de la sucesion de conjuntos (Xn) descritos como sigue:X1 = {O}

Xn+1 = Xn {(u)|u Xn}

Pasamos ya a establecer que se entiende por conjunto definido inductivamente.

Definicion 1.15 Sea A un conjunto no vaco, X un subconjunto no vaco de A y F un conjuntode funciones sobre A. 6 F = {fni : A

n A | (i, n) I J} donde I es un conjunto arbitrario novaco y J un subconjunto no vaco deN.

Un subconjunto Y de A se dice inductivo sobre X para F, si verifica las dos condicionessiguientes:

1. X Y

2. Y es cerrado para F, es decir, para toda f : An A en F y para todo (y1, . . . , yn) Yn, se

tiene que f(y1, . . . , yn) Y.

La interseccion de todos los conjuntos inductivos sobre X para F, al que denotaremos por X+, estambien un conjunto inductivo sobre X para F y se llama la clausura inductiva de X paraF.

e er r Tenemos que asegurar que la definicion dada de clausura inductiva de X para F es correcta.Para ello, puesto que tal clausura, a la que hemos denotado X+, la hemos definido como lainterseccion de todos los conjuntos inductivos sobre X para F, tenemos que asegurarnos existen

tales conjuntos. Efectivamente es as , ya que A es inductivo sobre X para F.

Vamos a dar una descripcion constructiva de X+:

Sea (Xi) una sucesion creciente de subconjuntos de A definida como sigue:

X1 = X

Xi+1 = Xi {f(x1, . . . , xn) | f F y (x1, . . . , xn) Xni }

6Advirtamos que no exigimos que todos los elementos de F tengan la misma aridad, es decir, F puede contenerfunciones monarias, binarias, . . . .


22/180


Entonces,

X+ =i1

Xi

e er r Advirtamos que cada elemento de X+

, puede ser representado por un conjunto de arboles delsiguiente modo:

- Cada elemento x X (elemento del conjunto base) se representa por un arbol de un solonodo etiquetado con x.

- Cada elemento a = f(x1, . . . , xn) Xi por cualquier arbol tal que:

(i) su raz es f y su grado de ramificacion es n.

(ii) cada descendiente inmediato de la raz es la raz de un arbol que representa a xj .

As pues, es posible que un elemento a X+ pueda ser representado por diferentes arboles,dependiendo de la n-upla (x1, . . . , xn) elegida (basta que a = f(x1, . . . , xn) Xi).

Ahora tenemos los elementos necesarios para advertir que el principio de induccion no es mas que

la lectura para N del siguiente resultado.

Teorema 1.2 (Principio de Induccion Estructural) SeaX+ la clausura inductiva de X paraun conjunto de constructores F. SeaP una propiedad relativa a X+ tal que:

1. Todo elemento de X verifica P.

2. F respeta la propiedad P, es decir, para todo f F de aridad n se tiene que:

Si x1, . . . , xn X+ verifican P, entonces f(x1, . . . , xn) verifica P.

En tales condiciones, todos los elementos de X+ verifican P.

1.7.0.1. Clausuras Inductivas Libremente Generadas

Un tipo de clausura inductiva de particular interes (por su adecuacion para ser manipulada compu-tacionalmente) lo forman las clausuras inductivas libremente generadas, que son aquellasen las que los elementos de X+ son generados de forma unica a partir del conjunto base X y delconjunto de constructores F, es decir, aquellas en las que todo elemento a de X+ es representadopor un unico arbol. Mas formalmente:

Definicion 1.16 Sea A un conjunto, X un subconjunto de A, F un conjunto de funciones sobreA y X+ la clausura inductiva de X para F. Se dice que X+ es libremente generada si cumplelas siguientes condiciones:

1. Para toda f : Am A de F, su restriccion a X+ es inyectiva, es decir, todo constructorgenera elementos distintos desde elementos distintos.

2. Para todo par f : Am A, g : An A de F, sus imagenes f((X+)m) y g((X+)n) sondisjuntas cuando f = g, es decir, constructores distintos generan elementos distintos.

3. Para toda f : Am A de F y para todo (x1, . . . , xm) de (X+)m, se tiene quef(x1, . . . , xm) /

X, es decir, ningun constructor genera elementos del conjunto base.

Es obvio que el conjunto de los naturales, como clausura inductiva, es libremente generado.


23/180

1.7. CONJUNTOS INDUCTIVOS 17

e er r En el caso de las clausuras inductivas libremente generadas, X+ sera siempre infinito.

En las clausuras libremente generadas, los conjuntos Xi satisfacen la siguiente propiedad:

Si (x1, . . . , xn) Xn

i

Xni1

, entonces f(x1, . . . , xn) Xi.

Por lo tanto, X+ es la union de la sucesion estrictamente creciente de conjuntos Yi definidos comosigue:

Y1 = X

Y2 = Y1 {f(y1, . . . , yn) | f F e (y1, . . . , yn) Yn

1 }

. . . . . .

Yi+1 = Yi {f(y1, . . . , yn) | f F e (y1, . . . , yn) Yni Y

ni1}

1.7.1. Funciones Recursivas

Dado un conjunto no vaco A y X A, bajo ciertas condiciones, es posible extender una funciondefinida sobre X, de forma unica, a X+. Sean:

Un conjunto B y un conjunto G de funciones de alguna aridad sobre B.

Una funcion d : F G tal que, para todo f F, d(f) tiene la misma aridad que f.

En tales condiciones, si X+ es libremente generada, entonces para toda funcion h : X B existeuna unica funcionh : X+ B tal que:

1. h es una extension de h, es decir,h(x) = h(x) para todo x X.2. h(f(x1, . . . , xn)) = d(f)(h(x1), . . . ,h(xn)) para toda funcion f de F y para todo (x1, . . . , xn) (X+)n.La segunda condicion puede expresarse diciendo que el diagrama

Bn

d(f)B

(X+)n X+f

hn h

es conmutativo, es decir,h f = d(f) hn, siendohn la funcion definida por:hn(x1, . . . , xn) = (h(x1), . . . ,h(xn))La extensionh definida se dice que es una funcion recursiva o tambien definida inductivamente.as pues, conocido el valor deh sobre los elementos del conjunto base, la extensionh se define sobreun elemento a de X+ en terminos de s misma sobre elementos deh que son mas simples que a. 7

7Por esta razon, se suele decir que h se llama a s misma.


24/180


Ejemplo 1.6 La potencia de exponente natural de una relacion binaria R en un conjunto A (quehemos introducido en la seccion 1.1) es la funcion recursiva

h : N 2AA

extension de h : {0} 2AA, con h(0) = idA, definida por h((n)) = d()(h(n)) donde d() :2AA 2AA con d()(S) = S R, es decir,

h((n)) =h(n) RSi denotamosh(k) = Rk para todo k N, se tiene la definicion ya presentada

R0 = idA y Rn+1 = Rn R


25/180

1.8. EJERCICIOS 19

1.8. Ejercicios

1. Sean X ,Y,S,T conjuntos tales que X Y = T S y X Y = T S = . Demuestre que

X = si y solo si T = (X S) (Y T)

2. Demuestre que una relacion binaria R en un conjunto A es transitiva si y solo si R+ = R.

3. Dadas dos relaciones binarias R y S en un conjunto A, demuestre que

a) (R+)1 = (R1)+

b) Si R S = S R, entonces (R S)+ = R+ S+

4. Dada la relacion en C definida por z1 z2 si y solo si z1 z2 R. demuestre que es unarelacion de equivalencia.

5. Proporcione un ejemplo de relacion binaria no reflexiva, cuya clausura transitiva s sea refle-xiva.

6. Sea A un conjunto arbitrario. Demuestre que si B A, entonces (B) = B.

7. Sea (Ai)iI una familia de subconjuntos de un conjunto A. Pruebe que:

a) (

iIAi)c =

iIA

ci

b) (

iIAi)c =

iIA

ci

donde, dado un conjunto X, hemos denotado por Xc el conjunto complementario de X.

8. Sea una funcion f : A B, I un conjunto no vaco y, para cada i I, Ai A. Demuestre

que:

a) f(

iIAi) =

iIf(Ai).

b) f(

iIAi)

iIf(Ai).

c) f(

iIAi) =

iIf(Ai), si f es inyectiva.

9. Sea f : R R definida por f(x) = x2

x2+1. Demuestre que f(R) = [0, 1) y que f no es

inyectiva.

10. Sean A,B,C conjuntos no vacos y f : A B y f : B C. Contruya un ejemplo en elque f sea sobreyectiva, g inyectiva y g f ni sobreyectiva ni inyectiva.

11. Demuestre por induccion que para todo n N se tiene que:

a) n5 n es divisible por 5.

b)n

k=0 ak = a

n+1 1a 1 para cualquier a R \ {0, 1}.

12. Sea = {a1, . . . , a26} = {a , . . . , z}, el alfabeto romano. Defina rigurosamente la relacionbinaria orden lexicografico sobre , tal que, si la denotamos por ,

u v se lee: u precede a v en el diccionario.


26/180


13. Sean (A, 1) y (B, 2) dos conjuntos parcialmente ordenados. Una funcion f : A B se diceque es monotona si para cualesquiera a, b A tales que a 1 b se tiene que f(a) 2 f(b).Demuestre que:

a) La composicion de dos funciones monotonas es monotona.

b) Si f es monotona y es el mnimo elemento de un subconjunto X no vaco de A, entoncesf() es el mnimo elemento de f(X).

c) Proporcione un contraejemplo para mostrar que si f es monotona y es el mnimoelemento de A, entonces f() no es necesariamente el mnimo elemento de B.

14. a) Defina una tabla 2-dimensional de elementos de un conjunto A, como una secuencia defilas, siendo cada fila una secuencia de elementos de A.

b) Dada una tabla 2-dimensionalde elementos de un conjunto A, TA, Defina funciones sobreTA que seleccionen la i-esima fila, la j-esima columna y el elemento aij , respectivamente.

c) Demuestre que la funcion que selecciona la j-esima columna es una secuencia.

15. Demuestre que en un arbol binario T

a) El numero de nodos en el nivel k es menor o igual que 2k.

b) Si h es la altura de T, entonces el numero de hojas es menor o igual que 2h.

c) Si h es la altura de T, entonces el numero de nodos de T es menor o igual que 2h+1 1.

d) Si n es el numero de nodos de T con n 1, entonces la altura de T es mayor o igual quelog

2n.

16. Sea B la clase de los arboles binarios y sea f : B N, definida por

f(T) = 0 si T es vacomax{f(TL), f(TR)} si f(TL) = f(TR)

f(TR) + 1 si f(TL) = f(TR)

donde TL y TR son los subarboles izquierdo y derecho de T, respectivamente. f(T) es llamadoel numero Strahler de T.

a) Determine el numero Strahler de un arbol binario completo de altura h.

b) Proporcione una relacion general entre la altura de un arbol binario y su numero Strahler.

17. a) Demuestre el lema de Konig.

b) Use el lema de Konig para demostrar que el juego citado como ejemplo de su uso debeterminar. (Indicacion: supongamos que creamos un arbol como sigue: los nodos son lasbolas que han pasado por la caja. El nodo raz es la bola con la que comenzamos a jugar.Los hijos de una bola son las bolas que introducimos cuando la reemplazamos).

18. Defina inductivamente el conjunto {n N | n es multiplo de 3 y de 7}, usando (para definirlos constructores) solamente la suma en N.

19. a) Defina inductivamente el conjunto S de las secuencias finitas de elementos de un conjuntoA. Razonar si S es o no libremente generado.


27/180

1.8. EJERCICIOS 21

b) Demuestre por induccion estructural que la longitud de una secuencia s coincide con lalongitud de su inversa (secuencia obtenida tomando los elementos de s en orden inverso).

20. Sea A = {a,b,c} y : A A A la funcion definida por la tabla siguiente:

a b c

a a b cb b c ac c a b

a) Demuestre que A es la clausura inductiva de X = {b} para .

b) Demuestre que existe una funcion h : X N que no tiene ninguna extension g a A talque g es un homomorfismo de (A, ) en (N, +), es decir, tal que g(x y) = g(x) + g(y).

21. Defina recursivamente la funcion nivel de un nodo en un arbol.

22. Dadas las siguientes definiciones recursivas de funciones, busque para cada una de ellas unaformula simple para su definicion y pruebe por induccion que la respuesta es correcta

a) f : N N, definida por

f(n) =

1 si n = 1f(n 1) + 2n + 1 en caso contrario

b) g : N N N, definida por

g(n, m) = 1 si m = 1

g(n, m 1) n en caso contrario


28/180



29/180

Captulo 2

Logica y Computacion

2.1. Objetivo de la logica

La importancia de la Logica viene siendo reconocida desde la antiguedad, ya los griegos saban queel razonamiento es un proceso sujeto a ciertos esquemas y que, al menos parcialmente, est a go-bernado por leyes perfectamente formulables (Aristoteles fue el primero en intentar describir lasleyes de la logica). Pero su importancia en la actualidad se debe sin duda al destacado papel queha tomado recientemente en los mas diversos campos de las Ciencias de la Computacion. 1 Nodebemos sorprendernos por este hecho, ya que, como expone magistralmente Hofstadter en su libroGodel, Escher y Bach. Un Eterno y Gracil Bucle,2

... la logica nacio como un intento de mecanizar los procesos intelectivos del razonamiento . . .

De hecho, si se pretenden mecanizar tareas tales como:

- Calculos basados en operaciones aritmeticas (que el hombre puede memorizar y aplicar sinnecesidad de razonar).

- Busqueda de datos (por simple comparacion con un patron dado).

- Clasificacion u ordenacion de datos (siguiendo un criterio establecido).

no es necesario aplicar la Logica (en el sentido de ciencia). Pero si pretendemos mecanizar tareasinteligentes, tareas en las que interviene destacadamente la capacidad deductiva del hombre, comolas involucradas en los campos de las Ciencias de la Computacion citados, se requiere:

- Tener conocimiento sobre el dominio.

- Razonar con tal conocimiento.

- Conocer como dirigir o guiar tal razonamiento

1Comprension del Lenguaje Natural, Teora de Automatas y Lenguajes Formales, Diagnosis, Simulacion de Circui-tos Digitales, Planificacion, Control Automatico, Analisis, Sntesis y Verificacion de Programas, Programacion logica,Inteligencia Artificial, Control de Procesos, Robotica, Bases de Datos.. .

2D.R. Hofstadtter. Godel, Escher y Bach. Un Eterno y Gracil Bucle. TUSQUETS Eds. 4a ed. 1992.


30/180

24 CAPITULO 2. LOGICA Y COMPUTACION

para todo ello es preciso definir (con claridad y precisi on) y analizar los procesos inferenciales queel hombre ejercita de modo natural. Este es el objetivo de la l ogica.

Sin embargo, las inquietudes teoricas en el campo de la automatizacion del razonamiento, distanmucho temporalmente de las consecuciones. As, la idea de crear un lenguaje simbolico aparece en la

Edad Media con Raimundo Lulio,3 pero no tuvo exito en la epoca. La razon, como indican Gochety Gribomont,4 es que:

. . . desgraciadamente, el nivel de la Ciencia y en particular de las Matematicas era muybajo en la epoca . . .

La historia de la Logica Computacional puede ser trazada al menos desde Hobbes y Leibniz en elsiglo XVII, Boole y Frege en el siglo XIX, Herbrand y Gentzen en 1930 y Robinson en 1960, todosellos matematicos.5 Sus trabajos constituyen la base de lo que hoy se entiende por Ciencias de laComputacion.

Son muchas las definiciones posibles para la logica y quizas la mas estandar es la siguiente:

. . . la l ogica es la ciencia que tiene como objetivo el analisis de los metodos de razona-miento ...

Desde su papel crucial en computacion, encontramos nuevas definiciones que reflejan nuestro interes.Recogemos la de Johan van Benthem (junto con otros autores) en su texto Logic in Action 6 :

La logica es una teora de tareas informacionales claves ejecutadas por actores cognitivosque razonan, aprenden, actuan e interactuan con otros de modo inteligente.

En este texto, estudiaremos la logica que analiza la validez de las construcciones del lenguajenatural llamadas razonamientos deductivos (o inferencias deductivas), es decir, construccionesque responden al esquema:

Si .. . y . . . y . . . y . . . y . . . , entonces .. .

y que utilizamos para establecer que cierta afirmacion (la conclusion) se deriva, deduce o infieredeductivamente de otras (las hipotesis).

En todo su quehacer, como ya destaco Aristoteles, la logica se interesa en la forma y no enel contenido de los razonamientos. Por ejemplo, consideremos los dos razonamientos deductivossiguientes, cuya validez nadie pondra en duda:

1. Si Pars es la capital de Espana y Roma es la capital de Italia, entonces Pars es la capital

de Espana.

2. Todos los malaguenos miden mas de dos metros. Juan es malagueno. Por lo tanto, Juan midemas de dos metros.

3I.M. Bochenski. Historia de la Logica Formal. Ed. Gredos. 1976.4P. Gochet, E.Gregoire y P. Gribomont. From Standard Logic to Logic Programming. Introducing a Logic Based

Approach to Artificial Intelligence. A.Thayse Editors JOHN WILEY & SONS. 1988.5J.W. Lloyd.Ed. Computational Logic. Symposium Proceedings Brussels. Basic Research Series. Springer Ver-

lag.1990.6van Benthem, J; van Ditmarsch, H; van Eijck, J and Jaspars, J., Logic in Action. Springer-Verlag. 1980.


31/180

2.2. TIPOS DE LOGICAS 25

El primero tiene la forma: si A y B, entonces A, y el segundo, que responde al tipo derazonamiento referido por los griegos como silogismo , tiene la forma:

Todos los A son B, C es un A. Por lo tanto, C es un B

La validez de estas formas de argumentacion es el objetivo de la logica deductiva. La verdad ofalsedad de las hipotesis y de la conclusion (como ocurre en el primer ejemplo) no conciernen a lalogica. Su objetivo es unicamente:

conocer si de las hipotesis es lcito inferir la conclusion, si la informacion que recoge la con-clusion esta implcita en la informacion que recogen las hipotesis, y

establecer metodos validos de inferencia, es decir, poder contestar a las preguntas siguientes:

es lcito inferir de las hipotesis H1, H2, . . . , H n la conclusion C?,

Existen metodos lcitos de inferencia?;

Existen metodos lcitos de inferencia que son automatizables?.

Con esta concepcion como punto de partida, para contestar a las anteriores preguntas, habr a queestablecer con claridad:

1. El tipo de construcciones del lenguaje natural que aceptamos como hipotesis y como conclu-sion.

2. El grado de analisis sobre tales construcciones.

3. El planteamiento de partida sobre la nocion de verdad o falsedad.

Todo ello, dara lugar a diversos tipos de logicas.

2.2. Tipos de Logicas

Entre las diversas logicas, y como referencia y fundamento de todas las demas, se encuentra la

logica clasica o estandar, la mas ampliamente estudiada desde que George Boole expusiera susLeyes de la Verdad en 1854 7 y a la que en sntesis podemos describir como sigue:

considera unicamente frases declarativas del lenguaje natural, las cuales consideramos quesolo admiten dos posibles valores de verdad: o son verdaderas o son falsas (es decir, la l ogicaclasica es bivaluada).

considera que podemos pronunciarnos acerca del valor de verdad de una frase declarativa deun modo absoluto, sin recurrir a consideraciones de contexto alguno. Nos pronunciamos sobresu valor de verdad sin tener en cuenta en que momento se declaran, ni en que lugar, ni cuales nuestro grado de conocimiento previo, . . .

contempla la verdad composicionalmente, es decir, el valor de verdad de una frase compuestaqueda totalmente determinado por la verdad de las frases simples componentes (es decir, lalogica clasica es veritativo-funcional o extensional).

7George. Boole. An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories ofLogic and Probabilities. Dover, New York, 1958.


32/180


El estudio sobre tales construcciones se realiza en dos niveles de analisis estructural, segunse contemplen unicamente construcciones declarativas simples y compuestas o bien, en cadaafirmacion simple se distinga que se declara y de que o quien se declara. Estos dos niveles danlugar a la logica clasica proposicional y a la logica clasica de predicados, respectivamente.

El termino logica no clasica, es un termino generico usado para referir a cualquier logica di-ferente a una logica que posea las caractersticas que acabamos de senalar. Por lo tanto, sera noclasica cualquier logica que, al analizar la correccion de los razonamientos, permita considerar con-textos (temporales, de creencia, de necesidad y posibilidad, . . . ); no se limite a contemplar comovalores de verdad unicamente el 0 y el 1; no sea veritativo-funcional; . . .

Aunque las logicas no clasicas han adquirido mayor protagonismo por su papel en las Ciencias dela Computacion, surgieron antes de la existencia de los ordenadores. Los filosofos griegos ya cuestio-naban el etiquetar los enunciados de verdaderos sin contemplar la verdad por necesidad o la verdadpor posibilidad o sin contemplar que existen enunciados cuya verdad es temporal. . . Smullyan 8

afirma sobre la necesidad de las logicas no clasicas:

. . . no es que la logica clasica de respuestas incorrectas a ciertas cuestiones, sino queciertas cuestiones no pueden ser expresadas en ella facilmente , de modo natural o enun modo computacionalmente eficiente . . .

Hoy da es una cuestion abierta conseguir una rigurosa clasificacion de las logicas no clasicas.Siguiendo a Susan Haak 9, la mayora de las logicas no clasicas, son:

- Extensiones de la logica clasica: Pueden hablar y analizar razonamientos que la logicaclasica no puede, extendiendo el vocabulario basico de esta. Ejemplos de este tipo de logicasson aquellas en las que el analisis de los razonamientos consideran contextos de tiempo (logicastemporales), de conocimiento (logicas epistemicas), de creencia (logicas doxasticas), etc.

- Desviaciones o rivales de la logica clasica: Utilizan el mismo vocabulario que lalogica clasica, pero no mantienen algunas de las leyes de esta. Un ejemplo significativo delogica rival es el de la logica Intuicionista o constructivista, que no contempla como leyla ley del tercero excluido (A A siempre es verdadera). Esta logica fue introducida porBrouwer. Para un intuicionista, A es verdadero solo si es posible dar constructivamenteuna realizacion de A o probar constructivamente la existencia de A y, obviamente, existenafirmaciones para las que no es posible dar constructivamente una realizacion ni de ella nide su negacion.

Otras logicas de este tipo son las logicas difusas, abductivas, paraconsistente, probabilstica,etc. A todas ellas les prestaremos atencion en sucesivos textos. En este solo trataremos lalogica clasica proposicional.

2.3. Expectativas y Limitaciones de la Logica en Computacion

La vision de la logica que hemos adoptado, enfocada al analisis de razonamientos o inferenciasy con el ob jetivo final de aplicaciones computacionales conlleva, como destaca el logico matematicoMartin-Lof 10, los cuatro aspectos siguientes:

8En R. M. Smullyan. First-Order Logic. Springer-Verlag, 1968. Vuelto a publicar por Dover en 1995.9Susan Haak. Philosophy of Logics. Cambridge University Press. 1978.10P. Martin-Lof. Truth of a proposition, evidence of a judgement, validity of a proof. Synthese, 73, 1987.


33/180

2.3. EXPECTATIVAS Y LIMITACIONES DE LA LOGICA EN COMPUTACION 27

el lenguaje,

la semantica,

una teora de la demostracion, y

la automatizacion de las deducciones.

En esta seccion, describimos cada uno de estos cuatro aspectos enmarcandolos en un contextogeneral y, particularizando a la logica clasica, comentamos brevemente los resultados que generanexpectativas y los que establecen limitaciones respecto al uso de la l ogica en computacion.

2.3.1. El Lenguaje

Todo metodo formal para abordar una tarea, requiere la eleccion de las cadenas de smbolosque constituiran el lenguaje utilizado para describir el conocimiento sobre el dominio en el que seenmarca dicha tarea. Ello conlleva la descripcion de los smbolos y las palabras (combinacionespermitidas de smbolos) que se utilizaran para representar las construcciones del lenguaje naturalde forma no ambigua y de modo que quede reflejado el grado de analisis pretendido. Este aspectose recoge mediante lo que se denomina lenguaje formal que definimos en esta seccion.

En adelante, llamaremos alfabeto a un conjunto numerable de smbolos a. Un lenguaje Lsobre a es un subconjunto no vaco del lenguaje universal sobre a, es decir

L a =nN

an

Llamaremos a los elementos de L palabras o formulas bien formadas (en adelante, fbfs). As pues,un lenguaje L viene determinado por:

(i) Un conjunto numerable, a, de smbolos, llamado alfabeto del lenguaje.

(ii) Un conjunto de reglas de formacion que determinan que cadenas de smbolos del alfabe-to son palabras o fbfs del lenguaje. Estas reglas de formaci on constituyen la gramatica osintaxis del lenguaje.

Si ambos conjuntos estan definidos sin hacer referencia alguna al significado de los smbolos, ellenguaje se denomina lenguaje formal.

e er r Puesto que el alfabeto a es numerable, podemos asegurar que el cardinal del lenguaje universalsobre a es infinito numerable, es decir, |a| = 0, en consecuencia, podemos asegurar que elnumero de palabras o fbfs de cualquier lenguaje, L, sobre a es, a lo sumo infinito numerable, esdecir, |L| 0

El estudio de los lenguajes formales tiene un papel destacado en la construccion de compiladores

para lenguajes de programacion. En efecto, habitualmente, la sintaxis de un lenguaje de progra-macion viene dada como una gramatica, es decir, mediante un conjunto de reglas que describenque programas son sintacticamente lcitos. Por ejemplo, en el lenguaje Pascal, las declaraciones ifvienen definidas por la regla

if-declaracion := if-expresionthen-declaracion[else-declaracion]

Las propiedades de estas gramaticas se estudian en el marco de los lenguajes formales.


34/180


e er rAdviertase que diversos lenguajes pueden tener el mismo alfabeto (su diferencia la establecensus diferentes reglas de formacion).

Ejemplo 2.1

1. Dado el conjunto a = {, }, definimos el siguiente lenguaje L1 sobre a:

(i) y , son fbfs de L1.

(ii) Si es una fbf de L1 entonces es tambien una fbf de L1.

(iii) Si es una fbf de L1 entonces es tambien una fbf de L1.

Por lo tanto, y son palabras de L1 y no es una palabra deL1.

2. El lenguaje MIU: 11Dado el conjunto a = {M , I , U }, L2 = a es un lenguaje sobre a. Es

decir, cualquier cadena finita que consta de los smbolos M, I, y U es una palabra de L2.

3. El lenguaje mg: Dado el conjunto a = {, m, g}, L3 a es el lenguaje sobre a definido como

sigue: Las fbfs son las cadenas de a que satisfacen

- su primer y ultimo smbolo es .

- tanto m como g intervienen exactamente una vez en la cadena y la ocurrencia dem es anterior a la ocurrencia de g

Por lo tanto, mg y m g son palabras de L3 y las cadenas m g ym g m no son cadenas de L3.

Lenguaje y Metalenguaje

A un lenguaje formal se le denomina lenguaje objeto y al lenguaje utilizado para describirlose le denomina metalenguaje. La logica utiliza como metalenguaje el lenguaje natural, la teoraintuitiva de conjuntos. . . .

Ejemplo 2.2 Cuando en el lenguaje mg (introducido en el ejemplo anterior 2.1) utilizamos ex-presiones como: sea m g una fbf del lenguaje, tenemos que ser conscientes de que , y no son smbolos del lengua je (recordemos que solo , m y g lo son), sino que son smbolos delmetalenguaje. Utilizamos una cadena como m g para representar cualquier fbf del lenguaje yen ella , y denotan cadenas de guiones. Por lo tanto, (de acuerdo con la definici on del lenguajemg) tendremos que poner una restriccion a y : que ambas sean cadenas no vacas de guiones(sin embargo, s puede ser una cadena vaca de guiones).

11D. Hofstadter. Godel, Escher, Bach, un gracil y eterno bucle. Ed. Tusquets, 1992.


35/180


2.3.2. La Semantica

En la logica clasica proposicional que vamos a considerar en este texto, la semantica tiene comofin dar significado a las fbfs del lenguaje a partir de su estructura sint actica y establecer la nocion(semantica) de deduccion.

Cuando ponemos en relacion las fbfs del lenguaje con los entes (concretos o abstractos) porellas designados (a los que consideramos sus significados o valores semanticos), damos el paso dela sintaxis a la semantica. Establecer esta relacion requiere como herramientas los conceptos deinterpretacion, modelo, . . . , que vamos a introducir a continuacion.

Definicion 2.1 Dado un conjunto de valores semanticos o significados, S, una interpretacion,I, para un lenguaje L es una funcion que asocia un significado o valor semantico a cada fbf de L,es decir, una interpretacion es una aplicacion I : L S.

El problema en estudio, el ambito en el que queramos razonar, determinara un subconjun-to, D S que destaca un subconjunto de valores semanticos. A este subconjunto, D, se ledenomina conjunto de los valores semanticos (o significados) destacados. Como vere-mos, sera este conjunto el que nos permitira introducir el concepto de razonamiento valido.

En la logica clasica, el conjunto de valores semanticos es {verdad, falsedad} y verdad es elvalor semantico destacado.

As pues, cada interpretacion nos permite una lecturade las fbfs del lenguaje formal, le asignaun significado a cada fbf. Denotaremos por I el conjunto de interpretaciones consideradas, esdecir, I SL. En definitiva, I es el conjunto de posibles lecturas que consideramos para laspalabras del lenguaje.

Dado un lenguaje formal L, a una terna (S,D,I) se le denomina una semantica para L.

Para establecer la nocion de razonamiento valido, nos interesa conocer que interpretacionlee o interpreta la fbf con un valor semantico destacado:

Definicion 2.2 Sea L un lenguaje formal y (S,D,I) una semantica para L.

Una interpretacion, I I, es un modelo para una fbf A del lenguaje L, si asigna a A unvalor destacado, es decir, si I(A) D. El conjunto de modelos de A se denota Mod(A) y nosdetalla toda la informacion contenida en A, todas las formas posibles de modelizarla.

Una interpretacion, I I, es uncontramodelo para una fbf A del lenguajeL, si asigna aA un valor no destacado, es decir, si I(A) D. El conjunto de contramodelos de A se denotaContramod(A).

Una interpretacion, I I, es un modelo para un conjunto de fbfs L del lenguajeL si es un modelo de todas y cada una de las fbfs de , es decir, I(A) D para toda A (I asigna a todas la fbfs en un valor destacado). El conjunto de modelos de se denotaMod().

Una interpretacion, I I, es uncontramodelo modelo para un conjunto de fbfs dellenguaje L si es un contramodelo de alguna fbf de , es decir, existe A tal que I(A) D(I asigna a alguna fbf en un valor no destacado). El conjunto de contramodelos de sedenota Contramod()

Definicion 2.3


36/180


Una fbf, A L se dice modelizable o satisfacible si existe al menos una interpretacionI I tal que I(A) D, es decir, Mod(A) = .

En consecuencia, una fbf, A L, es no modelizable o insatisfacible si para toda inter-pretacion I I se tiene que I(A) D, es decir, Mod(A) = .

Un conjunto de fbfs, L, se dice modelizable o satisfacible si tiene al menos unmodelo, es decir, Mod() = .

Un conjunto de fbfs, L, es no modelizable o insatisfacible si no tiene modelos, esdecir, Mod() = .

Una vez dada la nocion de modelo, se dispone de todo lo requerido para establecer las nocionesde validez, e inferencia semantica (que entendemos al decir que unas fbfs son deducidas o derivadasde otras).

Definicion 2.4

Una fbf, A L, se dice valida, denotado |= A, si toda interpretacion es un modelo para A,es decir, Mod() = I.

Dado un conjunto de fbfs L y una fbf C L, se dice que C se deriva, deduce oinfiere semanticamente de , denotado |= C, si todo modelo para es un modelo paraC, es decir, Mod() Mod(C).

Denominamos Teora de Modelos para un lenguaje L, a un par (L, S), donde S = (S,D,I) esuna semantica para L, es decir:

S es el conjunto de valores semanticos,

D S el conjunto de valores destacados, y

I el conjunto de interpretaciones

De nuevo, en el campo de la programacion, la formalizacion de la semantica de programaspermite, dada una especificacion formal de la computacion deseada, demostrar la correccion de unprograma respecto a la especificacion.

Ejemplo 2.3 Vamos a dar una teora de modelos para el lengua je mg del ejemplo 2.1.

Definimos el conjunto de valores semanticos como S = {(n,m,l) | n,m,l N} y el conjunto devalores semanticos destacados D, como el siguiente subconjunto de S:

D = {(n,m,l) S | n + m = l}

As pues, (3, 24, 27) D (es un valor semantico destacado) y (3, 24, 21) D (es un valor semanticono destacado).

Ahora definimos el conjunto de interpretaciones.

I = {Ik | k N}; Ik : L3 S

donde Ik( m g ) = (a,b,c), con a = k long(), b = k long() y c = k long().

Con esta definicion, se tiene que I6(mg ) = (18, 6, 12), I3(mg) = (9, 3, 12)y I0( m g ) = (0, 0, 0).

Tenemos pues que:


37/180


La interpretacion I0 es un modelo para m g , porque I0( m g ) =(0 3, 0 1, 0 2) = (0, 0, 0) D,

La interpretacion I3 no es un modelo para m g , porque I3 es un contramodelo

para ella. En efecto, I3( m g ) = (9, 3, 6) D (9 + 3 = 12), y

La fbf m g es valida, ya que para todo k N, se tiene que

Ik( m g ) = (3k,k, 4k) D (3k + k = 4k)

Todas las fbfs son modelizables, ya que I0 es un modelo para toda fbf del lenguaje.

e er r Conviene destacar que el conjunto de fbfs modelizables y el conjunto de fbfs v alidas depende decada uno de los elementos de la terna (S,D,I).

Consideremos de nuevo el ejemplo anterior. Mantenemos el mismo conjunto de valores semanti-cos, S = {(n,m,l) | n,m,l N}, y el mismo conjunto de valores semanticos destacadosD = {(n,m,l) S | n + m = l}. Pero ahora consideramos el conjunto de interpretaciones

I = {Ik | k N, k = 0}; Ik : L3 S}

donde cada Ik se define de igual modo, es decir, Ik( m g ) = (a,b,c), con a = k long(),b = k long() y c = k long().

Ahora tenemos que:

La fbf m g es insatisfacible, es decir, no tiene ningun modelo, porque paratodo k = 0, se tiene que Ik( m g ) = (3k,k, 2k) D, ya que 3k + k = 2k.

La fbf m g es valida, ya que para todo k N

, k = 0, se tiene que

Ik( m g ) = (3k,k, 4k) D (3k + k = 4k)

2.3.3. Teora de la Demostracion

Especificar un mecanismo deductivo para el lenguaje formal, es decir, un mecanismo quepermita obtener una fbf de otras, sin hacer referencia a interpretacion alguna, nos lleva a la teorade la demostracion.

En particular, en los llamados Sistemas Axiomaticos sobre un lenguaje L, el mecanismo de-

ductivo viene dado por:

1. Un conjunto finito o infinito numerable, Axiom, de fbfs de L, llamadas axiomas (es decir,Axiom L).

2. Un conjunto de reglas de inferencia, deduccion o transformacion que establecen cuandouna fbf de L es consecuencia inmediata de una o varias fbfs de L.

Los axiomas pueden ser considerados como reglas de inferencia sin hip otesis. Las reglas deinferencia suelen ser introducidas como patrones formales o esquemas y, si bien su eleccion


38/180


viene dictada por la semantica, en su uso se realiza una abstraccion total de los significados, esdecir, se manipulan las componentes del lenguaje de un modo puramente sint actico. 12

Definicion 2.5 Una demostracion en un sistema axiomatico, SAxiom es una secuencia finita de

fbfs del lenguaje formal asociado, en la cual cada fbf es o un axioma de SAxiom o una consecuenciainmediata (segun dictan las reglas de inferencia) de una o mas fbfs precedentes en la secuencia. Sila ultima fbf de una demostracion es A, se dice que la secuencia es una demostracion de A enSAxiom.

Definicion 2.6 Una fbf, A, se dice es un teorema en un sistema axiomatico SAxiom, denotadoSAxiom A (o simplemente A, si no hay lugar a confusion), si existe para ella una demostracion.Obviamente, los axiomas de SAxiom son teoremas de SAxiom. Podemos caracterizar el conjunto delos teoremas como un conjunto minimal de fbfs que contiene al conjunto de los axiomas y es cerradopara las reglas de inferencia.

e er r As pues, los teoremas son los productos manufacturados de una fabrica peculiar, en la quela materia prima son los axiomas y las maquinas las reglas de inferencia.

e er r De la definicion anterior se tiene que en una demostracion de longitud n, si m < n y consideramoslos m primeros elementos de la secuencia, tenemos una demostracion del m-esimo elemento dela secuencia. Por tanto todas las fbfs de una demostracion son teoremas.

Definicion 2.7 Unadeduccion de una fbfA desde un conjunto de fbfs en un sistema axiomaticoSAxiom, denotado SAxiom A, es una secuencia finita de fbfs del lenguaje formal asociado, en lacual cada fbf es o un axioma de SAxiom, una fbf de o una consecuencia inmediata (segun dictan

las reglas de inferencia) de una o mas fbfs precedentes en la secuencia.Las fbfs de se suelen llamar hipotesis o premisas, en cuyo caso decimos que A es una

conclusion de las hipotesis.

e er r As pues, en una deduccion, los productos manufacturados por una deduccion (en nuestra pe-culiar fabrica), utilizan como materia prima no solo los axiomas, sino tambien las hipotesis,es decir, las fbfs de (las maquinas siguen siendo las reglas de inferencia).

e er r Es obvia, por tanto la relacion existente entre demostraciones y deducciones. Si en un sistemaaxiomatico SAxiom se tiene que A entonces toda deduccion de A desde es una demostracion

de A en un sistema S

Axiom tal que S

Axiom tiene las mismas reglas de inferencia que S y susaxiomas son los axiomas de SAxiom junto con todas las fbfs de .

La nocion de demostracion como deduccion logica de un teorema a partir de un conjunto deaxiomas fue divulgada por primera vez por Euclides en sus Elementos, 13sin embargo no sedispone de una definicion rigurosa hasta Leibniz en el siglo XVII.

12El nivel puramente sintactico es la base de la fuerte conexion entre Logica y Computacion, ya que en esta ultima,los procesos simbolicos juegan un destacado papel.

13Euclides. The Thirteen Books of The Elements. Dover, New York, 1956.


39/180


Propiedad de Monotona

En el Ejercicio 3 se propone demostrar una propiedad destacada del concepto de deduccion, lapropiedad de monotona:

Si y A entonces A.

Es decir: si aumentamos el conjunto de hipotesis, se mantiene o aumenta el conjunto de conclu-siones. Las logicas que poseen esta propiedad se denominan logicas no monotonas. La Logicaclasica es monotona. Sin embargo, existen logicas (no clasicas) que no son monotonas y que sonutiles (mas aun, imprescindibles) para modelizar el razonamiento del sentido comun, en el que enocasiones hemos de revisar nuestras conclusiones al aumentar nuestro conocimiento.

La relacion de consecuencia deductiva que acabamos de definir, tiene tambien otras dos propiedadesinmediatas:

es reflexiva, es decir: para toda fbf A se tiene que A

es transitiva, es decir: Si A y {A} B, entonces B

Ejemplo 2.4 footnoteD. Hofstadter. Godel, Escher, Bach, un gracil y eterno bucle. Ed. Tusquets,1992. Definamos un sistema axiomatico sobre el lenguaje MIU (dado en el ejemplo 2.1), al quetambien llamaremos el sistema MIU:

Axioma: MI

Reglas de inferencia:

R1. De una fbfI, se tiene como consecuencia inmediata IU.

R2. De una fbfM , se tiene como consecuencia inmediata M .

R3. De una fbfIII, se tiene como consecuencia inmediata U .

R4. De una fbfUU, se tiene como consecuencia inmediata .

donde y representan cualquier cadena de smbolos del alfabeto {M , I , U } (incluida la cadenavaca).

Veamos que MUIUI es un teorema del sistema axiomatico MIU. Para comprobarlo, todo loque tenemos que hacer es dar una demostracion, es decir, mostrar como generarlo a partir delaxioma MI y las reglas de inferencia: :

1. MI Ax.1

2. MII De 1. y R2

3. MIIII De 2. y R2

4. MUI De 3. y R3

5. MUIUI De 4. y R2


40/180


Ahora podemos afirmar que MUIUI es un teorema del Sistema MIU. Este enunciado noes un teorema de MIU, sino una afirmacion verdadera acerca del sistema MIU, es decir, es un

metateorema acerca de MIU.

Con este ejemplo, reflejamos las acciones en el sistema como un juego puramente sintactico,sin pretender reflejar aspecto alguno de la realidad, sin esperar que los teoremas tengan ning unsignificado (no hemos dotado al lenguaje MIU de ninguna semantica).

Ejemplo 2.5 [De Hofstadter 14] Definamos ahora un sistema axiomatico sobre el lenguaje mg(dado en el ejemplo 2.1), al que llamamos asimismo el sistema mg:

Axiomas: Toda fbf de mg que responde al esquema m g es un axioma.

Regla de inferencia: De una fbf de mg que responde al esquema mg, se tiene como conse-cuencia inmediata m g.

A diferencia de MIU, para el lenguaje mg, hemos definido una semantica y un sistema axiomati-co. Los tres aspectos expuestos hasta ahora (lenguaje, semantica y teora de la demostracion), suelenser agrupados diciendo que disponemos de una teora formal.

Definicion 2.8 Sea una teora formal T = (L, (S,D,I), SAxiom), donde (S,D,I) es una semanti-ca para el lenguaje L y SAxiom es un sistema axiomatico para el lenguaje L. Una interpretacion,I I es un modelo para la teora T, si es un modelo para el conjunto de teoremas de T.

En una teora formal, la teora de modelos (descrita por (S,D,I)) y la teora de la demostracion(descrita por SAxiom), se desarrollan con el objetivo (no siempre alcanzable) de que coincidan, esdecir, de modo que si una fbf es derivable semanticamente tambien sea derivable sintacticamente,y viceversa. Esta interaccion es precisamente lo que hace de la logica una herramienta atractiva.

Las propiedades que relacionan una teora de modelos y una teora de la demostracion sobreun lenguaje formal son referidas como correccion de la teora (la derivabilidad sintactica asegu-ra la derivabilidad semantica) y completitud de la teora (la derivabilidad semantica asegura laderivabilidad sintactica).

Definicion 2.9 Una teora formal se dice correcta si cumple que

Si A entonces |= A

En particular, en una teora correcta todo teorema es una fbf valida.

Una teora formal se dice completa si cumple que

Si |= A entonces A

En particular, en una teora completa toda fbf valida es un teorema.

14D. Hofstadter. Godel, Escher, Bach, un gracil y eterno bucle. Ed. Tusquets, 1992.


41/180


e er r Conseguir una teora correcta es un objetivo facilmente alcanzable, basta elegir como axiomasfbfs validas y exigir que las reglas de inferencia respeten la validez, es decir, que las con-secuencias inmediatas de fbfs validas sean fbfs validas 15. Por el contrario, la completitud esmas difcil ya que hemos de asegurar que no hemos olvidado ningun axioma, ni ninguna reglanecesaria para la completitud. Aun mas, la completitud no siempre es alcanzable, ello se debea que con ella se pretende (nada menos!) caracterizar sintacticamente la validez, esdecir caracterizar sintacticamente nuestra comprension (recogida en la semantica) sobre ciertosaspectos del mundo real; lo cual es a veces imposible, por excesivamente ambicioso.

Ejemplo 2.6

- El lenguaje mg dado en el ejemplo 2.1, con la semantica dada en el ejemplo 2.3 y el sistemaaxiomatico dado en el ejemplo 2.4, es una teora correcta y completa.

- Como probaremos mas adelante, tanto la logica clasica proposicional como la logica de pre-dicados de primer orden, disponen de sistemas axiomaticos correctos y completos.

- El Teorema de incompletitud de Godel 16afirma que no existe ningun sistema axiomatico enel que todas las verdades de la teora de numeros sean demostrables. 17

Aun cuando dispongamos de una teora completa, desafortunadamente, la mayora de los teore-mas de completitud para un sistema de demostracion dado, prueban que si una fbf (o inferencia) esvalida, existe para ella una demostracion (o deduccion) en el sistema, pero no indican como encon-trarla. Consecuentemente, para hacer de la logica una herramienta no solo atrac

1 logica clasica proposicional web

Documents