Matematicas Discretas (in progress)

MD

Matematicas Discretas

Abdiel E. Caceres [email protected]

Mayo 7, 2013

-AbC

Preeliminares

-AbC

Porque estudiar Matematicas Discretas

Hay varias razones por las cuales un aspirante a trabajar en Ciencias Computacionales debeaprender Matematicas Discretas, algunas de estas razones son las siguientes:

I Se desarrollan habilidades para entender y crear argumentos formales.

I La MD es la base para otras areas de estudio como estructuras de datos, algoritmos,teora de bases de datos, lenguajes formales y automatas, compiladores, sistemasoperativos, entre otros.

I Con el conocimiento de MD se tiene una base para resolver problemas en investigacionoperativa, en qumica, fsica, biologa, etc.

El enfoque particular de este curso es sin duda alguna la programacion. Estudiar MD,programando ofrece varias ventajas (especialmente para los estudiantes de cienciascomputacionales):

I Se desarrollan las habilidades de abstraccion.

I Se aprende un lenguaje de programacion no convencional, pero potente, flexible,completo y adecuado (DrRacket).

I Los conceptos matematicos son parte del aprendizaje significativo y duradero.

I Mejora las habilidades de programacion en cualquier otro lenguaje.

I Se adquiere el concepto de calculo lambda (que es util para describir cualquierproblema computacional).

-AbC

Recomendaciones generales

1. Imprime este material y escribe tus notas sobre el documento.

2. Tomate un buen tiempo para leer y estudiar el material.

3. Practica en el lenguaje.

4. Cumple con tus tareas.

Las calificaciones quedan determinadas bajo el siguiente criterio:

1. La calificacion final del ordinario puede obtenerse de dos maneras:

1.1 Excentando. La calificacion debe ser mayor o igual a 6.0 en el promedio de lascalificaciones parciales.

1.2 Aplicando el examen ordinario en las fechas estabecidas. La calificacion de los parcialesno aplica.

Las calificaciones de cada parcial queda determinada bajo el siguiente criterio:

1. Las tareas entregadas a tiempo y bien hechas, tienen el valor del 60% de la calificacionparcial.

1.1 Cada tarea entregada a tiempo y correctamente hecha, vale 1.1.2 Cada tarea entregada parcialmente correcta, vale 0.51.3 Cada tarea no entregada o entregada pero incorrecta, vale 0.

2. Responder correctamente unos ejercicios en el examen parcial, corresponde al otro 40%

-AbC

Bibliografa y herramientas necesarias

Matematica Discreta. Kenneth H. Rosen.5Ed. McGrawHill. Disponible (paraevaluacion personal) en formato PDF.

.

Ademas del libro de texto, es necesario una computadora con especificaciones comunes,+2GbRAM, +50GbHD, SO(MacOSX.x,Ubuntu,Fedora,Linux,WinXp,Win7,Win8).

Instalar el lenguaje DrRacket, en la version mas actual (v5.3.5 al momento de hacer estadiapositiva). DrRacket se puede adquirir gratuitamente desdehttp://racket-lang.org/download/ para diferentes plataformas, mac, linux o windows.

-AbC

Primeros pasos en DrRacket

-AbC

DrRacket-Indroduccion

-AbC

Primeros pasos con DrRacket: Datos primitivos

En la parte de interacciones, DrRacket funciona como una calculadora, se introduce laoperacion que se desea, DrRacket la evalua y ofrece la respuesta inmediatamente alterminar de evaluar.

DrRacket tiene algunos datos primitivos, es decir, aquella informacion que no requiere deninguna evaluacion (como los instintos primitivos en los seres vivos).

En DrRacket hay varios datos primitivos, como los numeros, las cadenas de texto, losvalores booloeanos, y todo aquellos que no queramos evaluar (anteponiendo un apostrofe):

> 50

50

> "hola mundo"

"hola mundo"

> #f

#f

> #t

#t

> Esto-no-se-evalua

Esto-no-se-evalua

>

-AbC

Primeros pasos con DrRacket: Funciones primitivas

En DrRacket, las funciones son ciudadanos de primera clase, lo que significa que todo giraen torno a las funciones, y se tratan de igual modo que los datos, de hecho no haydiferencia entre datos y funciones.

> +

#

> -

#

> *

#

> /

#

>

El uso de las funciones es diferente a otros lenguajes de programacion en que enDrRacket se utilizan encerrando entre parentesis tanto el operador como losoperandos enforma prefija.

(+ 5 23)

-AbC

EJERCICIO

[Escritura en prefijo] Escribe en notacion prefija las siguientes expresiones matematicas:

I 34 28

I 34/28

I 34 (28/3)

I 34 (28/(302))

Ventajas de la notacion prefija

1. Se puede utilizar recursivamente en expresiones complejas.

2. Se pueden utilizar en operaciones con 0, 1, 2 o mas operadores.

-AbC

Evaluacion de una R-expresion (expresion en DrRacket)

Supongamos que se desea evaluar la expresion (2 + (4 6)) (3 + 5 + 7). Esta expresionpuede escribirse como R-exresion como:

(* (+ 2 (* 4 6)) (+ 3 5 7))

-AbC

Definiendo conceptosUn aspecto muy importante de los lenguajesde programacion es la manera queproporcionan para nombrar a los objetoscomputacionales.

Decimos que un nombre (una cadena decaracteres) identifica un concepto, y eseconcepto tiene un significado.

Otro modo de entenderlo, es visualizar unasemejanza con el diccionario, pues en eldiccionario se encuentran enlistados losconceptos y su significado.

En DrRacket, que es un dialecto de Scheme, que a su vez es un dialecto de Lisp, se definenlos conceptos por medio de define. Por ejemplo, al escribir

1 (define longitud-lado 20)

el interprete crea una nueva relacion entre el valor 20 con el nombre longitud-lado. Unavez que esta relacion existe, es posible referirse al valor 20 por su nuevo nombrelongitud-lado:

-AbC

Practiquemos esto con las siguientes definiciones:

1 (define pi 3.14159)

2 (define radio 10)

Y en la seccion de interacciones

> (* pi (* radio radio))

31.4159

>

-AbC

Procedimientos y procedimientos compuestos

Ademas de poder utilizar los procedimientos primitivos con datos primitivos (hasta ahoracon numeros), es posible crear nuevas abstracciones para crear procedimientos a partir dedatos primitivos y procedimientos primitivos.

1 (define cuadrado ( (n) (* n n)))

Los espacios en blanco sirven para escribir mas claramente las definiciones

1 (define cuadrado ; Definimos el cuadrado

2 ( (n) ; el procedimiento que requiere de un numero 3 (* n n))) ; como el producto del numero por si mismo

Una vez definido el concepto cuadrado ya se conoce su significado ( (n) (* n n)), yse puede utilizar como si fuera cualquier funcion primitiva.

> (cuadrado 10)

100

> (cuadrado (* 5 2))

100

> (cuadrado (cuadrado 5))

625

> (cuadrado longitud-lado)

400

>

-AbC

Con este nuevo conocimiento (el del cuadrado de un numero) podemos escribir nuevosbloques de construccion. Por ejemplo, para programar la suma de cuadrados:

x2 + y2

La suma de cuadrados es un objeto muy util en modelacion matematica, tiene aplicacionesen muchas areas, por ejemplo, mediante teorema de Pitagoras sabemos que la suma de loscuadrados de las longitudes de los lados catetos de un triangulo rectangulo, representa elmismo valor que el cuadrado de la longitud del lado hipotenusa.

x2 + y2 = c2

As, la suma de cuadrados se puede expresar como:

(+ (cuadrado x) (cuadrado y))

1 (define suma-cuadrados

2 ( (x y)3 (+ (cuadrado x) (cuadrado y))))

En lenguaje natural podramos decir Definimos el concepto suma-cuadrados como elprocedimiento que requiere los argumentos x y y y esta definido como la suma delcuadrado de x con el cuadrado de y.

-AbC

Cuando se adquiere nuevo conocimiento, este forma parte ya de la coleccion de elementosconstructivos, que sirven para generar procesos mas complejos, como una nueva funcionque lleve a cabo algun procedimiento que involucre el conocimiento recien adquirido.

EJERCICIO

Utilizando las definiciones ya conocidas, escribe una definicion para definir el nuevoconcepto de una funcion f definida en terminos matematicos como:

f(x) = (x+ 1)2 + (x 2)2

-AbC

Expresiones condicionales:if

La forma especial if sirve para evaluar una R-expresion en dependencia del valor de verdadde un predicado (cierto o falso).

La estructura sintactica de la R-expresion if es como sigue:(if )

EJERCICIO

1. Traduce a DrRacket, la expresion Si x es mayor que 10, entonces suma 30 con 50;de otro modo suma 30 con 60.

2. Cual es el resultado de evaluar la R-expresion (if #t (+ 45 10) (- 45 10))3. Cual es el resultado de evaluar la R-expresion (if #f (+ 45 10) (- 45 10))

-AbC

Expresiones condicionales:cond

Frecuentemente tendremos la necesidad de decidir entre mas de dos alternativas, para estoscasos se ha creado la forma especial cond, cuya sintaxis es:

(cond ( )

( )

:

:

[(else )])

-AbC

Un procedimiento que calcule el valor absluto de un numero, probando si es posiivo,negativo, o cero y tomando diferentes acciones de cuerdo al caso que se presente, siguiendola regla:

|x| =

x si x > 0;0 si x = 0;x si x < 0;

Construcciones como la anterior se llaman analisis de casos, y en Racket hay una formaespecial de escribir estos analisis de casos. En Racket se utiliza cond (de condicional), y seutiliza como sigue:

1 (define valor-absoluto

2 ( (x)3 (cond ((> x 0) x)

4 ((= x 0) 0)

5 ((< x 0) (- x)))))

-AbC

TAREA

1. x+ 2x+ 6x2 + 4x3. Solamente se require la traduccion, no la evaluacion.

2. Comprueba la traduccion hecha en el punto anterior, haciendo x = 7, has la evaluacionde la expresion y verifica que el resultado sea 1687.

3. En la pagina 14 se encuentra la definicion del cuadrado de un numero. Utiliza ahoraesa definicion (si no lo hiciste ya) para traducir la misma expresion x+ 2x+ 6x2 + 4x3,y verifica que el resultado sea el mismo cuando x = 7.

4. Define ahora el concepto cubo, recordando que definimos el cubo de un numero como elproducto de un numero por s mismo tres veces.

5. Define el volumen-esfera como el producto del area de una circunferencia de radio r, porun tercio del valor del mismo radio r. Para lograr esta definicion, primero debes definirarea-circunferencia, como el producto pi r2, claro que para esta definicion se requiereconocer el valor de pi, como se definio en la pagina 13.

6. Define un procedimiento para determinar la raz positiva de una ecuacion de segundogrado ax2 + bx+ c, recuerda que la raz positiva se puede calcular mediante:

x =b+b2 4ac

2a,

sin embargo debes considerar los siguientes casos:6.1 si a = 0, entonces la raz no esta definida, en este caso debes devolver ERR-NoDef;6.2 si a 6= 0 entonces si puedes utilizar la expresion b+

b24ac2a .

Es importante que cada definicion tenga los comentarios adecuados (de otro modo la tarea esta incompleta.)

-AbC

Logica proposicional

-AbC

La logica proposicional es un sistema formal que permite obtener conclusiones acerca deproposiciones inicialmente establecidas.

En este captulo se estudiaran las proposiciones, los principales operadores entre lasproposiciones, las equivalencias logicas entre proposiciones, cuantificadores que permitenhacer proposiciones generales o especficas; y a medida que se avanza en el estudio, seproporcionan definiciones en DrRacket que permiten una mayor comprension de losconceptos. Tambien estudiaremos las bases de la teora de conjuntos.

La teora de conjuntos es particularmente util en muchas areas de las cienciascomputacionales, por ejemplo, se requieren estos conocimientos para determinar que tipode problemas se pueden resolver mediante algoritmos (el conjunto de los problemasTuring-computables); para determinar la complejidad algortmica de las solucionespropuestas mediante unprograma de computadora se utilizan conjuntos, cuando se habla deque un algoritmo es de complejidad O(n2) significa que el desempeno del algoritmo sepuede representar mediante una funcion que pertenece al conjunto de funciones que crecen(en el tiempo) por debajo de una funcion de orden n2.

La teora de conjuntos y la logica proposicional forman la base de todas las construccionesrealizadas en este curso.

-AbC

Proposiciones

Una proposicion logica, o simplemente proposicion, es una sentencia de la cual se puededecir que es verdadera o falsa, pero no ambas; los valores verdadero y falso se conocencomo valores de verdad; de modo que las proposiciones son aquellas sentencias quetienen alguno de los valores de verdad: verdadero o falso; y la logica proposicional se refiereal sistema formal que nos permite deducir proposiciones basadas en los valores de verdad deotras proposiciones con valor de verdad ya conocido.

En DrRacket los valores de verdad falso y verdadero se representan por los smbolos #fpara el valor falso y #t para el valor verdadero (true en inges).

Los valores #f y #t son datos primitivos en el lenguaje, de modo que el resultado de suevaluacion es ellos mismos, como se aprecia en el siguiente ejemplo de interaccion conDrRacket.

>#f

#f

>#t

#t

>

-AbC

En el lenguaje natural espanol, es posible construir proposiciones, como ejemplos podemosescribir los siguientes:

I El viernes empiezan las vacaciones.

I Los domingos son das de la semana.

I Siempre llueve en vacaciones.

I Una taza es una medida de capacidad.

I Un litro equivale a un metro.

Podemos traducir estas expresiones en R-expresiones, definiendo un concepto nuevo yasignando un significado, por ejemplo en la primera expresion

1 (define El-viernes-empiezan-las-vacaciones #t)

y cuando interactuamos

> El-viernes-empiezan-las-vacaciones

#t

>

-AbC

En DrRacket se utilizan smbolos para representar todos los objetos computacionales,incluyendo las proposiciones. En DrRacket cualquier secuencia de letras y smbolosespeciales (menos el espacio) pueden ser considerados como simbolos.

Trabajemos con la proposicion 14 + 16 = 20, que efectivamente es una proposicion porquetiene un valor de verdad falso, ya que 14 + 16 es 30 y no 20 como se declara.

Hagamos que el smbolo 14+16=20 represente la proposicion 14 + 16 = 20. De modo que enadelante, al menos hasta que se diga algo diferente, el smbolo 14+16=20 tendra un valor deverdad #f, puesto que 14 + 16 = 20 es falso.

1 (define 14+16=20 (= (+ 14 16) 20))

Al interactuar con DrRacket, se puede consultar el valor del smbolo 14+16=20.

> 14+16=20

#f

>

-AbC

Predicados

Un predicado es una proposicion que adquiere su valor de verdad en dependencia del valorde verdad de una o mas variables. Frecuentementese utilizan variables para declarar valoresque pueden ser modificados, o que en el momento son desconocidos.Los siguientes son ejemplos de predicados:

1. 2x+ 10 > 20, es un predicado pues el valor de verdad depende del valor asignado a lavariable x, que aunque no se ha declarado se supone que debe ser un numero (estaaclaracion es importante para los programadores).

2. 10x2 + 7y = z, es un predicado, pues en el momento no se puede determinar su valorde verdad, a menos que se sepa el valor de verdad de las variables x, y y z

En breve, la diferencia entre una proposicion y un predicado es que en la primera s seconoce el valor de verdad, mientras que en la segunda, el valor de verdad depende de una omas variables.

En este curso trataremos de manera indistinta a las proposiciones logicas y a los predicadosy a ambas les llamaremos proposiciones.

-AbC

TAREA

[Proposiciones]

1. Cuales de las siguientes sentencias son predicados? Marca el cuadro si la sentencia esun predicado, y dejalo en blanco si no lo es. En cada caso menciona la razon de tudecision.

2 + 3 = 5 Nuestro sistema solar tiene 8 planetas. 3 x = 5 Que idiomas hablas? Haga una caminata diaria de 30 minutos. La temperatura en la superficie del sol es de 6 106 C. El sol sale por el oriente 20 45 25 + 35 = 50 + 10 Si hoy es lunes, entonces trabajo el doble. Todos los martes hay promociones en las pizzas. En anos biciestos febrero tiene 29 das, y 2056 es un ano biciesto. 2x2 + 3x 16 = 0


-AbC

Operadores logicos

En la programacion de software para computadoras, es muy frecuente el uso deproposiciones, por ejemplo, en la elaboracion de ciclos, se debe determinar cuando setermina de hacer la tarea repetitiva, esto se realiza al verificar cierta condicion de paro dadaen forma de una proposicion; o como otro ejemplo en bases de datos, es posible seleccionaro modificar algunos de los registros almacenados, y la seleccion se hace mediante unaproposicion.

Estas proposiciones pueden ser simples como las que hemos visto hasta ahora, o bienpueden ser combinaciones de proposiciones, que generan a su vez nuevas proposiciones mascomplejas. Las proposiciones se pueden combinar haciendo uso de los operadores logicos.Frecuentemente se crean predicados en base a proposiciones, estos predicados son muyutiles en programacion, pues pueden determinar el fin de un ciclo, seleccionar aquellosregistros en la base de datos que deben ser modificados, y en general, pueden establecer losvalores de un computo en diferentes casos.

En las siguientes secciones estudiaremos los principales operadores logicos que permitengenerar combinaciones y hacer deducciones logicas.

-AbC

La negacion

El operador logico negacion, o brevemente la negacion es un rpedicado que adquiere elvalor de verdad contrario a la proposicion que es pasada como su unico argumento.

Definicion (La negacion)Si p es una proposicion, la negacion de p es un predicado basado en el valor de p y sedenotada frecuentemente por p. El valor de p es verdadero si p es falso, y es falso si pes verdadero.

En otras palabras, p tiene el valor de verdad diferente a la proposicion p.Una implementacion del procedimiento que cambia el valor de verdad de una proposicion enDrRacket es como sigue:

1 (define neg ; Se define la negacion

2 ( (p) ; como un predicado cuyo valor de verdad3 (if p #f #t))) ; es #f si es #t, y es #t si es #f.

Debido a la diferencia entre la notacion matematica y la notacion DrRacket, puede haberconfusion, sin embargo ambas notaciones: p y (not p) son equivalentes y se puedenutilizar indistintamente, siempre que se mantenga un mismo criterio.

-AbC

En el cuadro se muestra una comparacion entre la escritura del concepto de la negacion enespanol en la columna izquierda y en DrRacket, en la columna derecha.

Espanol DrRacketSea neg el predicado que recibeuna proposicion llamada p (deproposicion) de tal modo que siel valor de verdad de p es ver-dadero, la evaluacion resultante es#f, y en caso contrario, la evalu-acion que resulta es #t

(define neg

( (p)(if p #f #t)))

-AbC

La interaccion con DrRacket permite verificar que el procedimiento recien creado tenga elcomportamiento esperado.

> (neg #t)

#f

>

En el ejemplo (neg #t), se solicita la evaluacion del predicado neg, cuando la variable p quedaligada (o relacionada) al valor #t, lo que en adelante denotaremos como p #t. En elambito de la definicion de neg, el valor de p se ajusta al valor #t, por lo que al evaluar laforma if se devuelve #f.

> (neg #f)

#t

>

Cuando hablamos (usando el lenguaje natural), frecuentemente hacemos uso deproposiciones como el plomo flota en el agua, es posible crear una frase en lenguajenatural que signifique lo mismo que la negacion de esa proposicion. Para crear una primeraaproximacion a una negacion en lenguaje natural, basta anteponer la frase no es verdadque a la frase que se desea negar, en este ejemplo escribiramos

no es verdad que el plomo flota en el agua,

claro que una frase mas natural puede ser el plomo no flota en el agua.

-AbC

Tablas de verdad

Para tener un panorama general del comportamiento de los predicados logicos, es utilmostrar tanto los valores de verdad alcanzados junto con los argumentos que originarontales resultados. A esta manera de presentar el comportamiento de los operadores logicosse le conoce como tabla de verdad.

As, la tabla de verdad para el predicado neg es la que se muestra en el cuadro

Valor de la proposicion Valor de verdad

p (neg p)

#t #f

#f #t

En el lenguaje formal de matematicas, el predicado de negacion tiene varios smbolos, as, sip es una proposicion, se puede encontrar generalmente como p, o con una barra sobre elsmbolo, como en p, o incluso como p.

-AbC

La conjuncion

Definicion (La conjuncion logica)Si p y q son dos proposiciones, el predicado (y p q) es verdadero si ambas proposiciones p y qson verdaderas, y (y p q) es falso en cualquier otro caso.

En smbolos matematicos la conjuncion de dos proposiciones p y q se denota por p q.

La conjuncion de dos proposiciones determina que el nuevo valor de verdad es verdaderounicamente en el caso en que ambas proposiciones sean verdaderas. Cualquier otro caso essuficiente para determinar un valor de verdad falso, as, formalmente escribimos:

1 (define y

2 ( (p q)3 (if p q #f)))

El nueva definicion y puede leerse como: Definamos y como el predicado que recibe dosparametros, llamados p y q, de tal modo que si el valor de verdad de la proposicion p esverdadero, se devolvera el valor de verdad de la proposicion q, y de otro modo se devolverael valor de verdad #f.

-AbC

1 (define y

2 ( (p q)3 (if p q #f)))

Aunque parezca complicado, en realidad no lo es tanto, pero s se requiere una lecturacuidadosa. La tabla de verdad mostrada en el cuadro, nos ayudara a comprender mejor elcomportamiento de la proposicion y.

p q (y p q)

#t #t #t

#t #f #f

#f #t #f

#f #f #f

> (y #t #t)

#t

> (y #t #f)

#f

> (y #f #t)

#f

> (y #f #f)

#f

>

-AbC

Hasta ahora tenemos unicamente dos definiciones en nuestro nuevo lenguaje de MD. Paramantener bien informado a los usuarios de este lenguaje, se deben agregar algunoscomentarios.

1 ; Def #001

2 ; objetivo: Modelar el operador logico de negacion

3 ; formato: neg: ->

4 ; ejemplos:

5 ;> (neg #t)

6 ;#f

7 ;>

8 (define neg

9 ( (p)10 (if p #f #t)))

11

12 ; Def #002

13 ; objetivo: Modelar el operador logico de conjuncion

14 ; formato: y: ->

15 ; ejemplos:

16 ;> (y #t #t)

17 ;#t

18 ;> (y #f #t)

19 ;#f

20 ;>

21 (define y

22 ( (p q)23 (if p q #f)))

-AbC

La disyuncion

Definicion (La disyuncion)Si p y q son proposiciones, la disyuncion es el predicado que devuelve verdadero si algunaproposicion p o q o ambas, son veraderas, y devuelve falso en caso contrario.

En matematicas se escribe p q para representar la disyuncion de las proposiciones p y q.

La tabla de verdad de la disyuncion ofrece un panorama completo del comportamiento encada uno de los posibles casos de las proposiciones de entrada.

p q (o p q)

#t #t #t

#t #f #t

#f #t #t

#f #f #f

-AbC

Es de notable que el caso cuando ambas proposiciones son verdaderas, unicamente serequiere evaluar la primera proposicion, ya que eso basta para que el resultado de laevaluacion sea verdadero.Las interacciones son las siguientes:

> (o #t #t)

#t

> (o #t #f)

#t

> (o #f #t)

#t

> (o #f #f)

#f

>

Veamos otras interacciones utilizando ejemplos numericos.

> (define p (= 30 (+ 10 10 10)))

> (define q (= 40 (* 2 30)))

> p

#t

> q

#f

> (o p q)

#t

>

-AbC

La disyuncion exclusiva

Definicion (Disyuncion exclusiva)Si p y q son proposiciones logicas, la disyuncion exclusiva de p y q, denotada por (ox p q) esverdadero cuando p es verdadero, o bien cuando q es verdadero; y devuelve falso cuandoambas proposiciones son verdaderas o cuando ambas proposiciones son falsas.

En matematicas, la disyuncion exclusiva usualmente se denota mediante el smbolo ,donde p q significa la disyuncion exclusiva de p y q. La tabla de verdad de la disyuncion

exclusiva es como se muestra:

p q (ox p q)

#t #t #f

#t #f #t

#f #t #t

#f #f #f

-AbC

El concepto de la disyuncion exclusiva puede ampliarse hasta su uso en el lenguaje natural,y es que en el lenguaje natural, frecuentemente se confunde la disyuncion con la disyuncionexclusiva, por ejemplo, la frase:

A las 5:00 pm, Roberto1 siempre esta en casa o en el deportivo

Esta frase se puede separar en dos:

1. A las 5:00 pm, Roberto siempre esta en casa y

2. A las 5:00 pm, Roberto siempre esta en el deportivo.

Como ambas frases estan unidas por una disyuncion, la frase completa puede ser verdaderacuando a las 5:00 pm, Joaqun esta en casa y tambien a esa misma hora Joaqun esta en eldeportivo, como es claro que Joaqun no puede estar en ambos lugares al mismo tiempo(suponiendo que la casa de Joaqun no es el deportivo), entonces deberamos concluir deque en realidad no es una disyuncion, sino una disyuncion exclusiva.

1Generalmente se utilizan los nombres de Alicia y Roberto (Alice y Bob, en ingles) como nombresgenericos, particularmente en textos de criptografa y de fsica. Nosotros aprovechamos esto para elegirel nombre.

-AbC

Aunque el lenguaje natural permite estas abuguedades, es mejor no provocarlas, as que unasolucion podra ser decir algo como

A las 5:00 pm, Roberto siempre esta en o casa o en el deportivo,

cuando se trate de situaciones que se asemejan mas a una disyuncion exclusiva.

EJERCICIO

En las siguientes proposiciones, decubre cual es una disyuncion exclusiva y cual no lo es.Marca solamente aquellas casillas que s son disyunciones exclusivas.

asd

-AbC

XXXXJJJXJJJJ

]

S

S\

XXXXJXJXXJJJ

XXJXJXJXXJJJ

TAREA

1. Escribe una definicion en DrRacket, para la disyuncion. Debes definir el conceptosiguiendo el formato: o : -> . De modoque puedas probar la definicion con cada una de las combinaciones dadas en la tablade verdad para la disyuncion, por ejemplo

> (o #t #f)

#t

>

2. Escribe una definicion en DrRacket, para la disyuncion. Debes definir el conceptosiguiendo el formato: ox : -> . De modoque puedas probar la definicion con cada una de las combinaciones dadas en la tablade verdad para la disyuncion, por ejemplo

> (ox #t #f)

#t

>


-AbC

La implicacion

Definition (La implicacion)Sean p y q dos proposiciones. La implicacion de p y q, escrita como p q, o en codigofuente como (-> p q), es un predicado con valor falso cuando p es verdadera y q es falsa, y encualquier otro caso la implicacion es verdadera.

En la implicacion, el primer operando se llama antecedente (tambien se puede llamarhipotesis) y el segundo operando se llama consecuente (tambien se puede llamar tesis, oconclusion). En ocasiones se llama a la implicacion como condicional. En la tabla semuestra su tabla de verdad.

p q (-> p q)

#t #t #t

#t #f #f

#f #t #t

#f #f #t

-AbC

Notemos en la tabla de verdad (y como dice la definicion), que el unico caso en que laimplicacion es falsa, es cuando su antecedente p es verdadera y el consecuente q es falso.

Cuando se describen procedimientos matematicos, o bien cuando se describen conceptosmatematicos, frecuentemente se generan expresiones que se pueden modelar con laimplicacion logica. En particular en expresiones como Si p, entonces q; p implica q, psolo si q y muchas parecidas.

Todos los lenguajes de programacion de proposito general, utilizan una forma parecida a laimplicacion. Sin embargo el principio que subyace es el mismo. Ya hemos utilizado la formaespecial if. En programacion la clausula IF se utiliza como una condicional, pero en lugarde devolver falso o verdadero, en caso de que el antecendente sea verdadero se realizan lasacciones consecuentes.

1 // Java

2 void applyBrakes() {

3 if (isMoving) {

4 currentSpeed--;

5 } else {

6 System.err.println("The bicycle has already stopped!");

7 }

8 }

-AbC

1 // C#

2 bool flagCheck = true;

3 if (flagCheck == true)

4 {

5 Console.WriteLine("The flag is set to true.");

6 }

7 else

8 {

9 Console.WriteLine("The flag is set to false.");

10 }

1 {* Pascal *}

2 if color = red then

3 writeln(You have chosen a red car)

4 else

5 writeln(Please choose a color for your car);

1 # Python

2 var1 = 100

3 if var1:

4 print "1 - Got a true expression value"

5 print var1

6 else:

7 print "1 - Got a false expression value"

8 print var1

-AbC

p q (-> p q)

#t #t #t

#t #f #f

#f #t #t

#f #f #t

Analicemos los cuatro casos de la implicacion con ejemplos de interacciones en DrRacket:

El primer ejemplo es determinar p q, cuando p es 30 = (15 2) y q es 4 = (2 + 2),notamos que de manera separada, p es verdadero y q tambien es verdadero. De modo quede acuerdo a la tabla de verdad, la implicacion 30 = (15 2) 4 = (2 + 2), tambien esverdadera.

> (= 30 (* 15 2))

#t

> (= 4 (+ 2 2))

#t

> (-> (= 30 (* 15 2)) (= 4 (+ 2 2)))

#t

-AbC

p q (-> p q)

#t #t #t

#t #f #f

#f #t #t

#f #f #t

El segundo ejemplo, es cuando el consecuente es una proposicion falsa, mientras que elantecedente es verdadero. El siguiente ejemplo ilustra el caso.

> (= 4 (+ 2 3))

#f

> (-> (= 30 (* 15 2))

(= 4 (+ 2 3)))

#f

>

-AbC

p q (-> p q)

#t #t #t

#t #f #f

#f #t #t

#f #f #t

El tercer caso es cuando el primer operando de la implicacion es falso y el segundooperando es verdadero, por ejemplo:

> (= 30 (* 15 3))

#f

> (= 4 (+ 2 2))

#t

> (-> (= 30 (* 15 3))

(= 4 (+ 2 2)))

#t

>

-AbC

p q (-> p q)

#t #t #t

#t #f #f

#f #t #t

#f #f #t

Finalmente, cuando ambas proposiciones son falsas, la proposicion resultante de laimplicacion es verdadera.

> (= 4 (+ 2 3))

#f

> (-> (= 30 (* 15 3))

(= 4 (+ 2 3)))

#t

>

-AbC

"XEFPEZIVHEH4VXXXXJXJXXJJX

"

La implicacion funciona como una promesa, donde el antecedente es la condicion que sedebe cumplir para obtener lo que se ha prometido que es el consecuente, por ejemplo:

Si es tu cumpleanos, hay fiesta

Analicemos en que casos, el festejado pordra sentirse defraudado al no tener su fiesta decumpleanos prometida:Para hacer mas personal el ejemplo, supongamos que la persona se llama Alicia2:

1. Supongamos que NO es el cumpleanos de Alicia, y NO hay fiesta. Alicia no tieneporque sentirse defraudada y tendra una reaccion positiva, esto corresponde al caso(-> #f #f)#t.

2. Supongamos ahora que SI es el cumpleanos de Alicia, y que SI hay fiesta. Porsupuesto que Alicia no se sentira defraudada, pues la promesa se cumplio y tendrauna reaccion positiva, esto corresponde al caso (-> #t #t)#t.

3. Supongamos que NO es el cumpleanos de Alicia y SI hay fiesta. Claramente tampocose sentira defraudada Alicia, es mas, hasta se sentira contenta y tendra una reaccionpositiva, porque le gusta asistir a una fiesta de cumpleanos, aunque no sea sucumpleanos; esto corresponde al caso (-> #f #t)#t.

4. Por ultimo, supongamos que Alicia SI cumple anos y NO hay fiesta. En este ultimocaso Alicia se sentira defraudada al notar que no se cumplio la promesa y causara enella una reaccion negativa. Esto corresponde al caso (-> #t #f)#f.

2Companera de Roberto (vease la nota al pie de la pagina 39)-AbC

La implicacion en programacion

En programacion de computadoras se utiliza frecuentemente las condicionales en la formade una sentencia if, en el lenguaje , por ejemplo, existe una instruccion condicional quepermite realizar una accion consecuente si un predicado es verdadero; o bien realizarlaaccion alternativa en caso de que el predicado fuera evaluado como falso:

; Ejemplo en C estandar

#include

int main (void){

int x=10;

x>20 ? printf("consecuente") : printf("alternativa");

return (0);

}

En este ejemplo, el predicado a ser evaluado es x > 20, que es falso, considerando el valorinicial de x = 10. En los lenguajes de programacion que siguen el mismo paradigma de C, alser verdadero el predicado, se deben ejecutar la secuencia de ordenes que se colocan en laparte del consecuente; mientras que cuando el predicado es falso, se deben ejecutar lasordenes colocadas en la parte de la alternativa. En el codigo ejemplo se imprime en elmonitor la leyenda alternativa, pues x > 20 es falso.En los lenguajes funcionales, la evaluacion del predicado no decide el flujo de operaciones,sino que decide que expresion debe ser evaluada.

-AbC

El siguiente ejemplo esta escrito en PROLOG y tiene una lectura diferente, pero se basa enel mismo principio:

1 padre(javier,eduardo).

2 padre(javier,ramon).

3 padre(mariano,javier).

4 padre(gustavo,mariano).

5

6 antecesor(A, B) :- padre(A, B).

7 antecesor(A, B) :- padre(A, C),

8 antecesor(C, B).

En la primera parte (lneas 1 - 4) se declaran las proposiciones verdaderas (no hayproposiciones falsas), y la segunda parte (lneas 6 - 8) se declaran las reglas, estas reglasson predicados condicionales, cuyo antecedente se encuentra a la derecha del smbolo :-,mientras que el consecuente se encuentra a la izquierda del smbolo :-.La lectura de la primera regla (lnea 6) es: A es antecesor de B es verdadero cuando A espadre de B. Algo similar la siguiente regla, considerando que la coma es una conjuncion.

-AbC

La doble implicacion

Definicion (La doble implicacion)Si p y q son proposiciones logicas, la doble implicacion o bicondicional, es un predicado quees verdadero cuando tanto p como q son o ambas verdaderas, o ambas falsas, y es falsa enlos otros casos.

p q ( p q)

#t #t #t

#t #f #f

#f #t #f

#f #f #t

De la tabla de verdad nos damos cuenta de que cuando p es verdadero, el valor de la dobleimplicacion es el mismo que el valor que actualmente tiene la proposicion q; mientras quecuando la proposicion p es falsa, la doble implicacion tiene valores diferentes que q, dehecho es la propia negacion de q.

-AbC

TAREA

1. Escribe una definicion en DrRacket, para la implicacion. Debes definir el conceptosiguiendo el formato: -> : --> . De modoque puedas probar la definicion con cada una de las combinaciones dadas en la tablade verdad para la implicacion, por ejemplo

> (-> #t #f)

#f

>

2. Escribe una definicion en DrRacket, para la doble implicacion. Debes definir elconcepto siguiendo el formato: : -> .De modo que puedas probar la definicion con cada una de las combinaciones dadas enla tabla de verdad para la doble implicacion, por ejemplo

> ( #t #f)

#f

>


-AbC

Equivalencias logicas

En la practica cotidiana de la programacion y de las matematicas, es util sustituirexpresiones por otras menos complejas pero que conserven los mismos valores logicos ynumericos.

Definicion (Equivalencia logica)Cuando dos predicados p1 y p2 son logicamente equivalentes lo denotamos comop1 p2, y es una proposicion verdadera si ambas proposiciones tienen el mismo valor antelos mismos valores de sus argumentos.

EJEMPLO

Sea p1 el predicado (a b) y p2 el predicado (a b). Calculemos ahora la tabla deverdad de cada predicado

a b (-> a b) (neg a) (o (neg a) b)

#t #t #t #f #t

#t #f #f #f #f

#f #t #t #t #t

#f #f #t #t #t

Las columnas marcadas con flechas son iguales, notemos que se debe preservar el orden enlos valores de los argumentos de los predicados (las proposiciones a y b. Como lasexpresiones marcadas con flechas, ocasionan el mismo comportamiento, podemos decir que(-> a b) y (o (neg a) b) son logicamente equivalentes.

-AbC

"XEFPEZIVHEHSEF"EF

XXXXJJJXXJJX

"XEFPEZIVHEHSEFSRIKEF

XXXXJJJXXJJX

"

Contradiccion

Definicion (Contradiccion)Si a es una expresion proposicional cuyo valor de verdad es falso sin importar el valor deverdad de las proposiciones que la constituyen, entonces decimos que a es unacontradiccion.

EJEMPLO

Este es un ejemplo para demostrar una contradiccion.Si (define a (y p ( p))) es una expresion proposicional, el valor de verdad de a para cadavalor de las proposiciones que la constituyen se muestra en la siguiente tabla de verdad:

p ( p) (y p ( p)) a#t #f (y #t #f) #f

#f #t (y #f #t) #f

Como el valor de verdad de p es #f sin importar el valor de verdad de sus componentes,entonces podemos afirmar que (o p ( p)) es una contradiccion.

-AbC

Contingencia

Definicion (Contingencia)Si el valor de verdad de una expresion proposicional a puede ser verdadera o falso, entonceses una contingencia.

En programacion, las expresiones proposicionales por lo general son contingencias, pues elvalor de verdad de sus componentes es asignado a variables cuyo valor se determina entiempo de ejecucion.Un ejemplo de contingencia es la proposicion (o p q), o bien (y p q), cuyo valor de verdaddepende de los valores de verdad de las proposiciones p y q.

-AbC

Introduccion - conjuntos

-AbC

Nocion de elemento y conjunto

Tanto elemento como conjunto son dos conceptos que no tienen una definicion formal, y seconsidera que el significado es obvio y claro, a pesar de no tener una definicion formal paraesos terminos. Sin embargo, el diccionario del espanol s da definiciones, veamos:

Elemento: 9. m. Mat. Cada uno de los componentes de un conjunto.

Conjunto: 10. m. Mat. Totalidad de los entes matematicos que tienen una propiedadcomun. El conjunto de los numeros primos.

La teora de conjuntos se desarrollo gracias a los trabajos de Georg Cantor3. Cantor entreotras cosas creo la nocion de infinito, y de los conjuntos bien ordenados.

Georg Ferdinand Ludwig Philipp Cantor(1845 1918) Fue un notable matematicoaleman que es conocido por ser el creadorde la teora de conjuntos.

3Fuente: http://www.math.uni-hamburg.de/home/grothkopf/fotos/math-ges/-AbC

De estas definiciones se muestra que para definir elemento, se requiere conocer que es unconjunto, y para definir un conjunto hace falta conocer que es un ente matematico(sinonimo de elemento), ademas de que en realidad los elementos agrupados en unconjunto pueden compartir la unica propiedad de estar en el mismo conjunto, unapropiedad bastante arbitraria, pero completamente valida.

EJEMPLO

Algunos ejemplos de conjuntos:

I El conjunto de las vocales en el espanol.

I El conjunto de las consonantes en el espanol.

I El conjunto de los numeros enteros pares.

I El conjunto con los elementos 1, 3, 5, 7, 8 y 10.

-AbC

En general hay dos maneras de describir un conjunto, una de ellas es enunciando lapropiedad que hace que un ente matematico sea incluido en el conjunto; y la otra forma esmencionar cada elemento que debe ser parte del conjunto.En matematicas se puede reconocer un conjunto porque la descripcion del conjunto seencuentra delimitada por llaves { y }, por ejemplo:

EJEMPLO

Algunos ejemplos de conjuntos:

I El conjunto de las vocales en el espanol: {w|w es una vocal}I El conjunto de las consonantes en el espanol: {b,c,d,f,g,h,j,k,,m,n,n,p,q,r,s,t,v,w,x,y,z}I El conjunto de los numeros enteros pares: {x|x mod 2 = 0}I El conjunto con los elementos {1, 3, 5, 7, 8, 10}.

-AbC

Hay dos observaciones importantes acerca de los conjuntos:

1. Los elementos de un conjunto no se repiten. Es suficiente nombrar solamenteuna vez cada elemento, nombrarlos dos o mas veces es redundate. Sin embargo hayconjuntos especiales donde s se permiten las repeticiones, aunque estrctamente sehabla de la primera ocurrencia de un elemento, la segunda ocurrencia, etc.

2. El orden en que aparecen los elementos del conjunto no es importante. Dadoque lo importante en el conjunto es precisamente que ocurran, no importa el lugar queocupen.

-AbC

Listas en DrRacket

Las lista son los ciudadanos de primera clase en DrRacket, a menos de que seanexpresiones primitivas, todas las combinaciones y formas especiales se escriben con listas.Ahora vamos a introducir el concepto de lista, para poder implementar los conjuntos.

Definition (Lista)Un objeto L es una lista si cumple alguna de las siguientes dos condiciones:

1. L es de la forma ()

2. Si L NO ES de la forma (), deben identificarse los dos siguientes elementos:

2.1 El car de la lista, que es el primer elemento, aquel situado mas a la izquierda.2.2 El cdr de la lista, que es una lista que contiene a el resto de los elementos.

-AbC

Conjuntos como listas

A diferencia de los conjuntos que son agrupaciones sin orden preferente de sus elementos,las listas son secuencias ordenadas de elementos, esto es que si la lista tiene elementos, hayun primer elemento (el car de la lista), puede haber un segundo, un tercero y as.

Otra diferencia importante entre los conjuntos y las listas, es que en los conjuntos no sepermiten las repeticiones de elementos, mientras que en las listas si pueden haber elementosrepetidos, recordemos que lo irrepetible son los ndices de las posiciones de los elementos.

Considerando estas diferencias vamos a modelar los conjuntos mediante listas (aunqueDrRacket tiene un tipo de dato especial para conjuntos). Para modelar conjuntos vamos ahacer lo siguiente:

1. el conjunto vaco corresponde a la lista vaca (), como se haba anotadoanteriormente.

2. como los conjuntos son desordenados, el orden que se establece en las listas no esimportante, as que esa caracterstica se puede pasar por alto.

3. al menos por ahora, supondremos que una lista sin elementos repetidos es un conjunto.Mas adelante haremos un procedimiento para verificar que una lista no tiene elementosrepetidos.

Nota sobre la notacion: Si A es un conjunto, si A tiene 1 o mas elementos, A se puedeescribir como (a0 A), donde a0 es el car de A y A es el cdr de A.

-AbC

TAREA

1. Marca las casillas de las expresiones que SI son listas. () a b c ((a b) (c d) e) (((a) (b)) ((c) ((d e))) (a b ((c) (d)))

2. Cuenta el numero de elementos de cada una de las listas (de las que s son listas).(hola mundo como te va)

(+ 30 (* 10 20))

((a b) (x (z) e))

(((a) (b)) ((c) ((d e))))

(a b ((c) (d)))

3. ?Cual es el car de cada una de las siguientes listas?()

((a b) (c d) e)

((((3 8)) ((9 3))) ((p) (((8) 9))))

((((2 s)) (j)) ((w) (k f s i)))

4. Subraya el cdr de cada una de las siguientes listas()

((a b) (c d) e)

((((3 8)) ((9 3))) ((p) (((8) 9))))

((((2 s)) (j)) ((w) (k f s i)))


-AbC

Como se menciono anteriormente, hay dos maneras de definir un conjunto4:

intensional cuando se describe una regla o condicion que permite decidir si un elementodebe pertenecer o no al conjunto;

extensional donde se define elconjunto mencionando explcitamente cada uno de loselementos del conjunto.

EJEMPLO

Sea A el conjunto de los numeros 6, 7, 8, 9, 10, 11, 12, 13, 14.

> (define A (6 7 8 9 10 11 12 13 14))

> A

(6 7 8 9 10 11 12 13 14)

>

EJEMPLO

Sea A el conjunto de los numeros enteros mayores que 5 y menores que 15. Lo que sepuede escribir como A , {x|(x > 5) (x < 15)}

> (define A (filter ( (x) (y (> x 5) (< x 15)))(build-list 100 values)))

> A

(6 7 8 9 10 11 12 13 14)

>

4En este curso, todas las definiciones de conjuntos se van a hacer de manera extensional.-AbC

TAREA

Traduce las siguientes sentencias en lenguaje DrRacket

1. Sea A1 , {q, e, t, y, z}2. Sea A2 el conjunto de las personas adrian, esteban, karla e isidoro.

3. Sea A3 el conjunto de los numeros enteros positivos menores que 20, que seandivisibles por 4.

4. Sea A4 el conjunto de las palabras de 3 letras donde la letra de enmedio es una vocal,y las otras dos letras son las consonantes f o g.

5. Si A5 , {a, b, e, t, i, s, k} y A6 , {a, e, i, k,m, c, p, q}, define el conjunto A6 quecontiene los elementos de A5 que no aparecen en A6.

6. Supongamos que , {0, 1}, escribe en DrRacket, el conjunto A6 que es definidocomo el conjunto de las palabras de 6 letras en que empiezan con un 0 y no tienendos 1s seguidos.


-AbC

Conjunto vaco

Definicion (Conjunto vaco)El conjunto vaco es el conjunto que no tiene elementos. En matematicas se denota como{}, o bien como ; en DrRacket el conjunto vaco se denota como ().Para implementar el conjunto vaco en DrRacket, podemos crear una definicion como esta:

> (define vacio ())

> vacio

()

>

El lenguaje DrRacket ofrece un predicado que determina si un identificador esta asociadocon el conjunto vaco.

> (empty? vacio)

#t

>

En DrRacket existen varios predicados que determinan si un identificador esta asociadocon cierto tipo de elementos, un predicado se puede identificar por el ultimo caracter delidentificador del predicado, nos referimos al smbolo ?. Este smbolo no es restrictivo paradefinir nuevos predicados,es solamente una convencion que puede guiar la interpretacion delprograma por parte de los programadores. Es recomendable que al definir nuevos predicadosse terminen con un smbolo ?, a menos de que sea completamente claro el significado.

-AbC

La cardinalidad

Definicion (Cardinalidad)Si A es un conjunto, la cardinalidad del conjunto A es la cantidad de elementos quecontiene. En matematicas la cardinalidad del conjunto A se denota como |A|, y si |A| = n,n debe ser un numero entero no negativo. Si A , , entonces |A| = 0, y si A 6= ,entonces |A| > 0.

Es posible dar una definicion efectiva (en DrRacket) para determinar la cardinalidad de unconjunto. La idea fundamental de la cardinalidad es contar los elementos del conjunto.

El caso mas simple es cuando el conjunto no tiene elementos, la cardinalidad es 0.

Cuando el conjunto no esta vaco, lo que conocemos del conjunto es que tiene un primerelemento (el car del conjunto) y el resto del conjunto (el cdr) que no sabemos cuantoselementos tiene.

As que el numero de elementos de un conjunto A esta dado por la expresion de casos:

|A| ,{

Si A = entonces 0Si A = (a0 A) entonces 1 + |A|

-AbC

Es notable que cuando A 6= que podemos escribirlo como (A0|A), entonces A tiene unprimer elemento A0, y una lista con el resto de los elementos A

.

Cuando esto sucede (A 6= ), la cardinalidad del conjunto es apenas 1 mas la cardinalidaddel resto de los elementos.

La definicion efectiva luce como el siguiente codigo:

1 (define card-v1 ; la version 1 de la cardinalidad

2 ( (A) ; un conjunto en forma de lista, como (a b c d e f)3 (if (empty? A)

4 0

5 (+ 1 (card-v1 (cdr A))))))

Este codigo es un ejemplo de codigo bello, este codigo es legible, es tan claro que se podraescribir y leer desde su definicion formal en matematicas. Sin embargo no es muy elegante.La elegancia en el codigo tiene que ver con diversos factores de eficiencia como optimizar lamemoria, mantener la correctitud de la solucion y minimizar el tiempo de ejecucion.

-AbC

1 (define card-v1 ; la version 1 de la cardinalidad

2 ( (A) ; un conjunto en forma de lista, como (a b c d e f)3 (if (empty? A)

4 0

5 (+ 1 (card-v1 (cdr A))))))

EJEMPLO

Cual es la cardinalidad del conjunto A , {w, r, q, p}?

-AbC

Recursion de cola

Veamos esta otra implementacion. Esta version 2 de la cardinalidad, tiene dos argumentos,en lugar de solamente uno de la primera version:

1 (define card-v2 ; la segunda version de la cardinalidad

2 ( (A res) ; un conjunto de la forma (a b c d e f)3 (if (empty? A)

4 res

5 (card-v2 (cdr A) (+ res 1)))))

Comparemos lado a lado las dos implementaciones (encuentra las diferencias):

1 (define card-v1

2 ( (A)3 (if (empty? A)

4 0

5 (+ 1 (card-v1 (cdr A))))))

1 (define card-v2

2 ( (A res)3 (if (empty? A)

4 res

5 (card-v2 (cdr A) (+ res 1)))))

-AbC

1 (define card-v2 ; la segunda version de la cardinalidad

2 ( (A res) ; un conjunto de la forma (a b c d e f)3 (if (empty? A)

4 res

5 (card-v2 (cdr A) (+ res 1)))))

Ahora estudiemos el comportamiento con la misma entrada A , {w, r, q, p}. Nos interesaobservar cuantas llamadas a la misma funcion se tienen que invocar para lograr el resultado.Otra cosa que hay que onservar es en donde se realizan los calculos:

EJEMPLO

Cual es la cardinalidad del conjunto A , {w, r, q, p}?

-AbC

HIRIGEVHZS%%IWYRGSRNYRXSMJIWZEGMS#%GEVHZGHV%

HIRIGEVHZS%VIW%IWYRGSRNYRXSMJIWZEGMS#%VIWGEVHZGHV%VIW

Para lograr esta lectura tenemos que agregar una nueva definicion que invoque la funcionde cardinalidad:

1 (define card ( (A) (card-v2 A 0)))

Ahora si, la lectura es como se desea. El objetivo de esta funcion es calcular lacardinadlidad de un conjunto, y eso lo hace delegando la responsabilidad a la funcion card-v2mediante la invocacion (card-v2 A 0).

1 ; objetivo: Determinar el numero de elementos de un conjunto

2 ; formato: cardinalidad: -->

3 ; ejemplos:

4 ; > (cardinalidad (3 8 2 9))

5 ; 4

6 ; >

7 (define cardinalidad

8 ( (A)9 (define card-v2

10 ( (A res)11 (if (empty? A)

12 res

13 (card-v2 (cdr A) (+ res 1)))))

14 (card-v2 A 0)))

-AbC

HIRIGEVHS%?VIWA%IWYRGSRNYRXSMJIWZEGMS#%VIWGEVHGHV%VIW

Hay conjuntos que tienen tantos elementos que no pueden enlistarse, como el conjunto delos numeros pares, este tipo de conjuntos tiene una cardinalidad infinita.

El infinito no es un numero sino es una manera de decir que siempre se puede encontrarun numero que esta despues del que supusimos es el ultimo.

El smbolo que se ha asociado a este termino en matematicas es . En DrRacket hay unpar de smbolos que tienen el significado de infinito.

El infinito positivo +inf.0 y el infinito negativo -inf.0. En DrRacket, estos smbolos son detipo number?.

> (> +inf.0 99999999999999999999999999999999999999999999999999999)

#t

> (< -inf.0 -9999999999999999999999999999999999999999999999999999)

#t

>

A pesar de que un conjunto tenga un numero infinito de elementos, es posible enumerarlos,si los elementos de ese conjunto se pueden poner en correspondencia 1 a 1 con los numerosnaturales (Z). Este tipo de conjuntos se llaman conjuntos numerables. Otros conjuntosno son numerables, como el conjunto de los numeros reales (R). En este curso estudiaremosunicamente los conjuntos finitos y numerables, definidos de manera extensional.

-AbC

> (number? 4)

#t

> (number? +inf.0)

#t

> (number? -inf.0)

#t

> (- +inf.0 +inf.0)

+nan.0

> (+ -inf.0 +inf.0)

+nan.0

> (* +inf.0 2)

+inf.0

> (/ +inf.0 +inf.0)

+nan.0

> (* +inf.0 0)

0

>

-AbC

TAREA

1. Compara el numero de evaluaciones hechas cuando se invoca (card-v1 (e o p j k s w)),con el numero de evaluaciones hechas cuando se invoca (card-v2 (e o p j k s w)):

1.1 Escribe cada evaluacion detalladamente, llamada por llamada. Has esto para cadainvocacion.

1.2 Cuenta cuantas llamadas al mismo procedimiento se hacen en cada caso.

2. Escribe una definicion recursiva-de-cola que calcule el numero factorial de un numeroentero. La defincion matematica del factorial de un numero n entero positivo es:

n! =

{1 cuando n = 1;n(n 1)! cuando n > 1;

Esta definicion debe llamarse fact, y tiene el formato fact: --> .


-AbC

Pertenencia

Es muy util poder determinar si un elemento pertenece a un conjunto, en particular cuandolos conjuntos se han definido de manera intencional. La pertenencia es un predicado, demodo que es un valor verdadero o falso, dependiendo de que el elemento buscado este o noentre los miembros del conjunto.

Como los conjuntos que estudiaremos en este curso son definidos extensionalmente, unamanera de determinar si un elemento pertenece al conjunto es buscarlo en la lista deelementos. As se puede enunciar un algoritmo para determinar si un elemento pertenece aun conjunto.

En matematicas la pertenencia de un elemento a a un conjunto A es un predicado que sedenota por a A, cuyo valor de verdad es #t, si a ocurre en la lista de elementos delconjunto A; y es #f, si el elemento a no ocurre en la lista de elementos del conjunto A.

Cuando a A es falso, el predicado a 6 A es verdadero y cuando a A es verdadero, elpredicado a 6 A es falso.

-AbC

Modelando la pertenencia en DrRacket

Este problema requiere un elemento e y un conjunto C, la respuesta debe ser #t si e C,y debe ser #f si e 6 C.

La idea general es seguir los siguientes pasos:

1. Si C = , entonces e C #f2. Si C 6= c0 = e, entonces e C #t; cuando C = (c0 C )3. e C ; en otro caso.

-AbC

Para implementar el predicado pertenece?, hay que considerar que los elementos enlistados enel conjunto no tienen algun orden en particular, de modo que es necesario comparar elelemento buscado con cada uno de los elementos del conjunto, y detener la busquedacuando se determine mediante la igualdad, que el elemento buscado s pertenece alconjunto.

1 (define pertenece?

2 ( (a A)3 (cond ((empty? A) #f)

4 ((equal? a (car A)) #t)

5 (else (pertenece? a (cdr A))))))

Probemos el codigo con algunos ejemplos:

> (pertenece? 3 (2 4 6 8 10))

#f

> (pertenece? 10 (2 4 6 8 10))

#t

> (pertenece? 3 ())

#f

>

-AbC

TAREA

1. Escribe una definicion para el concepto conjunto? que reciba como entrada una lista, yque devuelva verdadero si la lista no tiene elementos repetidos, y devuelva falso si lalista tiene elementos repetidos. El conjunto vaco s debe devolver verdadero.El formato es conjunto? : --> .


> (conjunto? (a b c d e f))

#t

> (conjunto? ())

#t

> (conjunto? (a b c a d e f))

#f

>

-AbC

Diagramas de Venn

Los diagramas de Venn son representaciones graficas que permiten observar los elementosde un conjunto,ya que se reserva un espacio bien delimitado que encierra a los elementosdel conjunto.

EJEMPLO

Sean A y B dos conjuntos. A , {2, 4, 6, 8, 10} y B , {a, e, i, o, u}. Representa losconjuntos A y B mediante un diagrama de Venn.Las interacciones se pueden escribir formalmente como:

I 3 6 {2, 4, 6, 8, 10}I 10 {2, 4, 6, 8, 10}I 3 6

Los diagramas de Venn son particularmente utiles cuando se consideran conjuntospequenos, o bien para ilustrar cuando dos o mas conjuntos tienen elementos en comun.

-AbC

Conjuntos iguales

Definicion (Conjuntos iguales)Si A y B son conjuntos, decimos que A es igual al conjunto B cuando ambos conjuntostienen exactamente los mismos elementos. Si A y B no tienen exactamente los mismoselementos, entonces decimos que A es diferente a B, y lo escribimos como A 6= B.

La definicion anterior dice que para que los conjuntos A y B sean iguales, los elementos delconjunto A deben pertenecer al conjunto B, pero eso no es todo, desde la perspectiva delconjunto B debe suceder algo similar, todos los elementos del conjunto B deben perteneceral conjunto A.

-AbC

Subconjuntos

Definicion (Subconjunto)Si A y B son conjuntos, decimos que A es un subconjunto de B, escribiendolo comoA B, cuando todos los elementos de A pertenecen tambien al conjunto B. Si A no es unsubconjunto de B, se escribe como A 6 B.

Si A B recprocamente podemos decir que el conjunto B es un superconjunto delconjunto A; esto significa que el conjunto B puede tener elementos que no pertenecen alconjunto A, dicho de otro modo, la cardinalidad del conjunto B puede ser mayor que lacardinalidad del conjunto A.

-AbC

Implementacion del concepto subconjunto?

Como se estudio, si A y B son sonjuntos, A B es un predicado, de modo que elproblema queda resuelto al proporcionar un valor de verdad.Se procede deacuerdo al siguiente algoritmo:

1. Si A = , entonces A B #t: El conjunto vaco es subconjunto de cualquierconjunto.

2. Si A 6= a0 B, entonces A B; cuando A = (a0 A).3. en otro caso, entonces A B #f;

EJERCICIO

1. Describe formalmente la frase en otro caso.

-AbC

TAREA

Escribe una definicion en DrRacket para el concepto subconjunto? de acuerdo con los trescasos de la implementacion; con el formato subconjunto?: --> ,para probar tu definicion puedes seguir los siguientes ejemplos.

> (subconjunto? () (a b c d e f))

#t

> (subconjunto? (a b) (a b c d e f))

#t

> (subconjunto? (a b c e f g) (a b c d e f))

#f ; g 6 {a, b, c, d, e, f}>


-AbC

Subconjunto propio

Definicion (Subconjunto propio)Si A y B son conjuntos, decimos que B es un subconjunto propio de A, y lo denotamoscomo B A, cuando A B y A 6= B.

-AbC

TAREA

Escribe una definicion en DrRacket que implemente el concepto de subconjunto-propio? dedos conjuntos pasados como listas, siguiendo el formato:

subconjunto-propio?: -->

Es importante que cada definicion tenga los comentarios adecuados (de otro modo la tareaesta incompleta).

Las siguientes interacciones te deben servir de gua para determinar si tu programa escorrecto.

> (subconjunto-propio? () (a b c d e f))

#t

> (subconjunto-propio? (a b) (a b c d e f))

#t

> (subconjunto-propio? (a b c e f g) (e f b c g a))

#f ; son iguales

> (subconjunto-propio? (a b c e f g) (a b c d e f))

#f ; no es subconjunto


-AbC

Cuantificadores

-AbC

Cuantificadores

Un tema importante sobre logica matematica son los cuantificadores. Los cuantificadoresrepresentan predicados que permiten establecer un valor de verdad de una sentencia sobreun conjunto de valores. En esta seccion estudiaremos dos cuantificadores, el llamadocuantificador universal y el cuantificador existencial.

En la practica cotidiana del desarrollo de sofware, cuando se hacen los requerimientos delsistema es posible encontrar frases como las siguientes:

I Si todos los miembros del equipo estan de acuerdo, podemos empezar el proyectoinmediatamente.

I Si hay algun miembro del equipo que no este de acuerdo, el proyecto se pospone.

Estas frases son solamente ejemplos y se puede hacer un modelo computacional quepermita incluir condiciones sin confusiones. Cuando un predicado se debe aplicar a unconjunto de valores, se deben utilizar cuantificadores, el primer caso muestra un tpicoejemplo de un cuantificador universal, mientras que el segundo es un ejemplo tpico deun cuantificador existencial.

-AbC

Cuantificador universal

Para estudiar el cuantificador universal, recuperamos el primer ejemplo mostrado en laseccion anterior:

Si todos los miembros del equipo estan de acuerdo, podemos empezar elproyecto inmediatamente

A primera vista se puede ver como una forma de implicacion, donde se puede separar estafrase en dos:

p: todos los miembros del equipo estan de acuerdo

q: podemos empezar el proyecto inmediatamente

Pero una lectura mas detallada indica que una doble implicacion se acerca mas a laintencion de la expresion, ya que el proyecto no debe empezar si hay alguien que no este deacuerdo. En una implicacion no importara que el predicado p fuera falso, siempre que qfuera verdadero.

De modo que se debe hacer ( p q), para determinar la veracidad o falsedad del predicado.

-AbC

Claro que para saber si todos los miembros del equipo estan de acuerdo, habra quepreguntarle a cada integrante del equipo, y una vez que se le haya preguntado acada uno yque ninguno haya respondido que no esta de acuerdo, entonces el predicado p, tendra unvalor verdadero, de otro modo el predicado sera falso.

Para modelar esta situacion es util considerar un predicado que sea verdadero si unaproposicion es verdadera para todos los elementos de un conjunto, y sea el predicado seafalso si al menos un elemento del conjunto ocasiona que la proposicion sea falsa.

Definicion (Cuantificador universal)Si P es un predicado y A es un conjunto, el cuantificador universal se denota por

x A : P (x)

es un predicado que es verdadero si P aplicado a todos y cada uno de los elementos de Aes verdadero, y es falso si el predicado P no es verdadero en alguno de los elementos delconjunto A.

En la notacion del cuantificador universal x A : P (x), el conjunto A recibe el nombre dedominio, que es el conjunto de elementos sobre los cuales de debe verificar el predicado P .

El predicado P es una expresion que adquiere un valor falso o verdadero en dependencia delvalor de la variable o variables que fungen como argumentos de la expresion.

-AbC

EJEMPLO

Cual esel valor del siguiente predicado?

x {0, 1, 2, 3, 4} : (x 3)

El valor del predicado resulta al aplica y verificar el valor de la aplicacion del predicado acada miembro del dominio. Esto es equivalente a calcular:

(0 3) (1 3) (2 3) (3 3) (4 3)#t #t #t #t #f#f

-AbC

El predicado puede tener nombre o ser anonimo, esto es, un predicado anonimo requiere eluso de un smbolo para determinar su calidad de predicado anonimo, mientras que parahacer referencia a un predicado con nombre, simplemente se escribe su identificador,veamos el segmento de codigo siguiente:

(define P ((p q) (if p q #t))

Una definicion tpica en DrRacket, como la anterior, se compone de tres elementos,formando una expresion encerrada entre parentesis:

1. la palabra reservada define, sirve para indicar que se va a efectuar una asociacion entreun identificador y una expresion. Internamente se reserva memoria y se relaciona elcontenido de esa memoria con el identificador5

2. Un identificador, es una secuencia de smbolos sin el espacio en blanco; en esteejemplo se ha utilizado el smbolo P. Es equivalente a definir un nuevo concepto, elnombre del concepto es el identificador.

3. Una expresion. Es el significado del concepto que se esta definiendo. EN el ejemplo laexpresion es ((p q) (if p q #t)). El significado es la evaluacion de la expresion,as el nuevo concepto P, significa o #t, o #f.

5Aunque internamente la computadora hace mas cosas, lo interesante es que se hace unaasociacion entre el contenido de la memoria y in identificador.

-AbC

As, cuando se requiera el uso del concepto ya definido, puede utilizarse bien su nombre, osu significado:

Una implementacion del cuantificador universal se puede hacer verificando el valor deverdad de un predicado sobre cada elemento de un conjunto dominio, considerando que si eldominio s vaco, entonces el valor de verdad del cuantificador es verdadero.

1 (define paraTodo

2 ( (P A)3 (cond ((empty? A) #t)

4 ((P (car A)) (paraTodo P (cdr A)))

5 (else #f))))

> (para-todo ( (x) (> x 0)) (2 4 6 8 10))#t

>

-AbC

Cuantificador existencial

El cuantificador existencial es un predicado similar al cuantificador universal, en el sentidoque se debe verificar el valor de verdad de un predicado sobre un conjunto de elementos, eldominio del cuantificador.

Definition (Cuantificador existencial)Si P es un predicado y A es un conjunto, el cuantificador existencial se denota por

x A : P (x)

es un predicado que es verdadero existe al menos un elemento x en el dominio A de talmodo que P (x) es verdadero, y es falso en otro caso.

Otro modo de entender el cuantificador existencial, es que solamente se requiere que unelemento del dominio ocasione que el predicado probado sea verdadero, para que todo elpredicado sea verdadero, aunque haya mas elementos que tambien hagan verdadero elpredicado.

-AbC

En esta ocasion, es necesario verificar la vercidad del predicado para el primer elemento delconjunto, o para el segundo elemento, y as sucesivamente hasta encontrar el primerelemento que ocasione el valor #t del predicado probado, veamos el siguiente ejemplo.

EJEMPLO

Determina el valor de la expresion x {0, 1, 2, 3, 4} : (x > 2)

(0 > 2) (1 > 2) (2 > 2) (3 > 2) (4 > 2)#f #f #f #t #f#t

-AbC

En cuanto a la implementacion, podemos observar que una vez que se ha determinado laveracidad del predicado el algun miembro del dominio, es innecesaria la verificacion para elresto, pues sin importar el valor del resto de las verificaciones, el resultado final seraverdadero.

1 (define existeUn

2 ( (P A)3 (cond ((empty? A) #f)

4 ((P (car A)) #t)

5 (else (existeUn P (cdr A))))))

> (existeUn ( (x) (> x 3)) (0 1 2 3 4 5))#t

> (existeUn ( (x) (> x 5)) (0 1 2 3 4 5))#f

> (existeUn ( (x) (> x -1)) (0 1 2 3 4 5))#t

> (existeUn ( (x) (> x 3)) ())#f

>

> (existeUn ( (x) (> x 3)) (0 1 2 3 4 5))(( (x) (> x 3)) 0) (existeUn ( (x) (> x 3)) (1 2 3 4 5))(( (x) (> x 3)) 1) (existeUn ( (x) (> x 3)) (2 3 4 5))(( (x) (> x 3)) 2) (existeUn ( (x) (> x 3)) (3 4 5))(( (x) (> x 3)) 3) (existeUn ( (x) (> x 3)) (4 5))(( (x) (> x 3)) 4) (> 4 3) #t#t

>

-- Y ya no es necesario verificar el ultimo elemento (5).

-AbC

La negacion universal

La negacion del cuantificador universal es una nueva proposicion que toma valor verdaderocuando el cuantificador universal resulta falso, y falso cuando su valorresultante esverdadero. La negacion del cuantificador existencial se escribe

x A : P (x)

En palabras se puede establecer lo siguiente: No es verdad que para todo elemento x en sudominio A, se cumple P .No muchas ocasiones tendremos oportunidad de decir algo as. En el lenguaje natural lasexpresiones pueden ser mas sutiles, de modo que una manera de expresar la frase anterior, yque se parece mas a una expresion natural es: En el conjunto A, existe al menos unelemento x que no cumple P .Esto es, que hace falta unicamente que uno de los elementos del dominio no cumpla elpredicado P , para que todo el cuantificador no se cumpla. De modo que la negacion delcuantificador existencial se puede escribir equivalentemente como cualquiera de lasexpresiones:

1. x A : P (x)2. x A : P (x)

-AbC

La implementacion del cuantificador universal se puede hacer en cualquiera de las dosmaneras equivalentes, sin embargo la segunda, puede ser mas eficiente que la primera, puesse en el momento que un elemento x no cumpla el predicado P , se termina la evaluacion,sin tener que revisar todos los elemetos, como sucedera en la primera forma equivalente.Aqu ponemos las dos versiones:

Negacion universal - 11 (define noParaTodo1

2 ( (P A)3 (neg (paraTodo P A))))

Negacion universal - 21 (define noParaTodo2

2 ( (P A)3 (existeUn ( (x) (neg (P x))) A)))

-AbC

La negacion existencial

De manera simiar, la negacion del cuantificador existencial tiene una interpretacion en ellenguaje natural. De manera formal la negacion del cuantificador existencial se escribecomo:

x A : P (x)Que ledo literalmente puede expresar algo como:

No es verdad que exista al menos un elemento x en su dominio A, se cumple P .

La frase anterior significa que todos los elementos en el dominio del cuantificadorexistencial no cumplen el predicado. Esto nos da una pista sobre una manera equivalente deexpresar la negacion del cuantificador existencial.

Todos los elementos x en el dominio A, No cumplen el predicado P .

O tambien de manera mas coloquial: Ningun elemento x en el dominio A cumple P .Observemos que la anterior construccion gramatical sugiere el uso de un cuantificadoruniversal:

x A : P (x)

-AbC

Podemos implementar las dos versiones

Negacion universal - 11 (define noExisteUn1

2 ( (P A)3 (neg (existeUn P A))))

Negacion universal - 21 (define noExisteUn2

2 ( (P A)3 (paraTodo ( (x) (neg (P x))) A)))

En terminos de eficiencia podemos decir que la implementacion que utiliza un cuantificadorexistencial es una mejos solucion, aunque ambas soluciones tienen el mismo grado decomplejidad; y la razon es porque el cuantificador universal requiere recorrer toda la lista demiembros del conjunto dominio antes de emitir una evaluacion, mientras que uncuantificador existencial detiene las evaluaciones apenas se encuentre el primer miembro delconjunto dominio que cumple con el predicado.

-AbC

Cuantificadores multivariable

Hasta ahora, los ejemplos que se han tratado con los cuantificadores han involucradosolamente una variable, pero en muchos casos debemos tratar con mas de una.Supongamos la siguiente frase coloquial: Todos los empleados estan certificados en todoslos programas de software. Esta frase involucra dos dominios, los empleados y losprogramas de software. Para cada dominio debe existir una variable que se instancie concada miembro del conjunto dominio.Si A es el dominio de los empleados, y B es el dominio de los programas de software,formalmente podemos establecer:

x A : (y B : P (x, y))Esta expresion significa que para cada valor instanciado de x, la variable y debera tomartodos sus posible valores; una vez que y ha tomado todos los posibles valores, x puedecambiar de valor. Esto continua hasta que y haya agotado sus posibilidades y x tambien.

-AbC

EJEMPLO

calcula el valor de predicado Todos los empleados estan certificados en todos losprogramas de software, cuando los empleados son {ana, fer, cam}, mientras que lasoficinas son {sw1, sw2}.

x {ana, fer, cam} : (y {of1, of2} : P (x, y))Esta-certificado(ana, sw1)Esta-certificado(ana, sw2)Esta-certificado(fer, sw1)Esta-certificado(fer, sw2)Esta-certificado(cam, sw1)Esta-certificado(cam, sw2)

El valor de verdad resultante depende del valor de verdad de cada predicado instanciado.

-AbC

Mapeos

Computacionalmente hay una gran ventaja en el uso de los cuantificadores, en particular delos elementos en los dominios de los cuantificadores, que aunque son conjuntos, pueden servistos como listas.

La extension que describiremos se llama mapeo y va en el sentido de que el resultado de laevaluacion no es una proposicion, sino que se evalua una expresion. Esto en realidad no esnuevo en computacion, pues la implementacion de expresiones como if ejecuta/evalua unaexpresion si el predicado es verdadero, en lugar de simplemente resolver #t y ejecuta/evaluaotra expresion si el predicado es falso, en lugar de simplemente reolver #f.

Cuando se desea modelar computacionalmente frases como: Todos los asistentes debenregistrarse, el resultado esperado es la evaluacion del procedimiento aplicado a cadaelemento del dominio, y eso reside en una nueva lista.

Es claro que cada uno de los miembros del dominio Asistentes debe realizar unprocedimiento. Aqu el cuantificador no es propiamente un predicado, sino que sirve comocontrol de un procedimiento iterativo que se lleva a cabo sobre todos los elementos delconjunto dominio. Veamos el siguiente ejemplo:

-AbC

EJEMPLO

Si A es el conjunto de asistentes definido como A , {ana, sue, cam}, modele el mapeoTodos los asistentes deben registrarse.

x A : (se-registra x)(se-registra ana)

(se-registra sue)

(se-registra cam)

(ok err1 ok)

El resultado (ok err1 ok) esta estrechamente relacionado con el dominio (ana sue cam),significa que el procedimiento (se-registra ana) genero el valor ok; (se-registra sue) genero elvalor err1 y (se-registra cam) genero el valor ok.

-AbC

Implementacion de los mapeos

En el lenguaje DrRacket, existe una expresion primitiva llamada map, que realiza losmapeos. La manera de escribir un mapeo es como sigue:

(map ...)

donde:

1. map: es una palabra reservada, que indica que se debe realizar un mapeo utilizando elprocedimiento definido en cada elemento del dominio.

2. : Es una expresion que debe ser evaluada, este procedimiento debe serexpresado yasea mediante un identificador o descrito de manera anonima. Esimportante que la aridad6 del procedimiento concuerde con la cantidad de dominios.

3. ...: Signfica uno o mas dominios. Todos los dominios debe tener la mismacardinalidad, y el numero de dominios debe coincidir con la aridad del procedimiento.

6La aridad de un procedimiento es la cantidad de argumentos que requiere, aspor ejemplo, elpredicado (neg p), requiere solamente 1 argumento, de modo que tiene aridad 1. La conjuncion (y p q)requiere dos argumentos, de modo que tiene aridad 2.

-AbC

EJEMPLO

Supongamos que la siguiente es una lista de personas, especificando para cada persona elporcentaje de satisfaccion sobre cierto producto: ((sue 70) (cam 50) (ana 90)), y el siguienteprocedimiento anonimo: ( (par) (porcentaje-en par)), que indica que para cada par, se debeobtener el porcentaje. As, hacemos:

> (map

( (par) (porcentaje-en par))((sue 70) (cam 50) (ana 90)))

>> (porcentaje-en (sue 70)) 70>> (porcentaje-en (cam 50)) 50>> (porcentaje-en (ana 90)) 90(70 50 90)

>

-AbC

Mapeos uno a uno multivariable

La extension de utilizar procedimientos en los cuantificadores, en lugar de devolver un valorde verdad, tambien se puede utilizar con mas de una variable anonima, en el siguienteejemplo se utilizan dos variables, y se desea generar una lista con la aplicacion de unprocedimiento a cada par de instancias.

-AbC

EJEMPLO

Cada elemento x del conjunto A, {1, 2, 3, 4}, debe estar asociado con un elemento delconjunto B, {a, b, c, d}, de manera ordenada de acuerdo a la posicion en la que aparecen,el 1 con a, el 2 con b, y as en adelante.

Mapeo uno a uno1 (define mapeo1-1

2 ( (P A B)3 (map ( (x y) (P x y)) A B)))

> (mapeo1-1 list (1 2 3 4) (a b c d))

((1 a) (2 b) (3 c) (4 d))

>

En los mapeos uno a uno multivariable, se debe aplicar un procedimiento a una lista devariables, el numero de variables indica el numero de dominios, todos los dominios debenser del mismo numero de elementos.

-AbC

Mapeos anidados multivariable

La version de mapeos multivariable anidados, como en la version uno a uno, se aplica unprocedimiento a una lista de variables, pero a diferencia de la version uno a uno, en laversion anidada no se requiere que cada dominio sea de la misma longitud. La aplicaciondel procedimiento se hace para todos los elementos de primer dominio, con todos loselementos del segundo dominio, y as para cada dominio.

-AbC

EJEMPLO

Mapeo multivariable anidado1 (define mapeo-anidado

2 ( (P A B)3 (map ( (x) (map ( (y) (P x y)) A)) B)))

> (mapeo-anidado list (1 2) (a b c))

(((a 1) (a 2)) ((b 1) (b 2)) ((c 1) (c 2)))

>

Figure: Mapeo multivariable anidado donde se aplica el procedimiento P a cada par de elementos,el primero del primer dominio, con cada uno del segundo, y as hasta terminar con todos losdominios; luego el segundo del primer dominio con cada uno del segundo y as hasta terminar losdominios; y as hasta terminar.

-AbC

La cantidad de mapeos que se hacen en un mapeo multivariable anidado, esta en funciondel numero de elementos de cada dominio.

Si A1, A2, . . . , Am son m dominios en un mapeo multivariable de m variables, y |A1| = n1es la cardinalidad del dominio A1, |A2| = n2, y as en adelante hasta |Am| = nm, entoncesresultan n1 n2 nm aplicaciones del procedimiento.

El siguiente captulo se trata sobe hacer operaciones con conjuntos, crear procedimientosque modifiquen conjuntos, o bien que generen conjuntos a partir de otros.

-AbC

Operaciones con conjuntos

-AbC

Agregar elementos a un conjunto

El primer modificador de conjuntos que necesitamos es una manera de agregar un elementoa un conjunto.

Si A es un conjunto y e un elemento cualquiera, agregar el elemento e al conjunto A,significa que e:

1. cumplira con las condiciones que hacen que un elemento pertenezca a un conjunto, siel conjunto esta definido de manera implcita,

2. debera estar enlistado entre los elementos del conjunto, si el conjunto esta definido demanera explcita.

EJEMPLO

Elemento Antes de agregar Despues de agregar5 {1, 2, 3, 4} {5, 1, 2, 3, 4}

-AbC

Agregar

Formalmente podemos definir la operacion de agregar como

Definicion (Agregar)La operacion de agregar un elemento a un conjunto es un procedimiento que requiere unelemento e y un conjunto C, y el resultado es un nuevo conjunto denotado por 1 (e, C),que es el conjunto que reune a todos los elementos de A junto con el nuevo elemento e.

Se observa que | 1 (e, C)| = 1 + |C|; y que | 1 (e, C)| = 1 cuando C = .

Agregar un elemento a un conjunto1 ;; Formato:: agregar: -->

2 ;; Objetivo:: crear un conjunto con los elementos del conjunto dado junto con el nuevo elemento

3 ;; Ejemplos:

4 ;; > (agregar 3 (2 4 6 8 10))

5 ;; (3 2 4 6 8 10)

6 ;; > (agregar 3 ())

7 ;; (3)

8 ;; > (agregar () ())

9 ;; (())

10 (define agregar

11 ( (e C)12 (if (pertenece? e C)

13 C

14 (cons e C))))

-AbC

Union de conjuntos

Definicion (Union de conjuntos)Sean A y B dos conjuntos. La union de los conjuntos A y B es un nuevo conjuntodenotado por A B, cuyos miembros los conforman todos los miembros que pertenecen alconjunto A o al conjunto B.

-AbC

Union (efectiva)

Definicion (Union de conjuntos)Sean A y B dos conjuntos. La union de los conjuntos A y B es un nuevo conjuntodenotado por A B definido recursivamente como:

A B ,{B si A = A 1 (a0, B) si A = (a0 A) a0 B

Union de conjuntos1 ;; Formato: agregar : conjunto x conjunto -> conjunto

2 ;; Proposito: construir un conjunto, haciendo la union de ellos

3 ;; Ejemplos y casos de prueba:

4 ;; > (union () (2 4 6 8 10))

5 ;; (2 4 6 8 10)

6 ;; > (union (5) (2 4 6 8 10))

7 ;; (5 2 4 6 8 10)

8 ;; > (union 3 ())

9 ;; (3)

10 ;; > (union () ())

11 ;; ()

12 (define union

13 ( (A B)14 (if (empty? A)

15 B

16 (union (cdr A) (agregar (car A) B)))))

-AbC

EJEMPLO

Determina la union del conjunto A , {2, 4, 6, 8, 10} con el conjunto B , {1, 2, 3, 4, 5, 6, 7}

-AbC

"YRMSR

"

"YRMSR

"

Interseccion

Definicion (Interseccion)Si A y B son conjuntos, la interseccion de A con B es el conjunto denotado por A Bdefinido por los elementos que pertenecen al conjunto A y al conjunto B simultaneamente.

Efectivamente, la interseccion de los conjuntos A y B se logra definiendo una funcionauxiliar que podemos llamar intrseccion auxiliar, que considera ademas, un conjunto auxiliarC inicialmente vaco; esta interseccion auxiliar esta definida por

(A,B,C) ,

si B = C si A = (A, B,1 (a0, C)) si a0 B(A, B, C) si a0 6 B

Hay varias cosas interesantes que comentar con esta definicion

-AbC

Hay varias cosas interesantes que comentar con esta definicion

(A,B,C) ,

1: si B = 2: C si A = 3: (A, B,1 (a0, C)) si a0 B4: (A, B, C) si a0 6 B

i La notacion normal infija se ha modificado a una notacion tpica en las funciones,dejando los argumentos encerrados entre parentesis.

ii Se trata de una definicion recursiva que contiene dos casos de salida y dos casos derecursion.

iii A diferencia de las definiciones matematicas de multiples casos, las definiciones efectivasde multiples casos se evaluan una por una de arriba hacia abajo.

iv Dado que la definicion formal de la interseccion no incluye un conjunto auxiliar C, serequiere una definicion mas apropiada.

(A,B) , (A,B, )

-AbC

TAREA

Escribe las definiciones en DrRacket de la interseccion auxiliar.

1. La funcion de interseccion auxiliar tiene un formato:

1 ;; 2 ;;

3 ;; Proposito: Construir un conjunto, haciendo la intersccion

4 ;; de los primeros dos conjuntos

5 ;;


7 ;; > (interseccion-auxiliar () (2 4 6 8 10) ())

8 ;; ()

9 ;; > (interseccion-auxiliar (2 4 6 8 10) (11 12 13 14 15) ())

10 ;; ()

11 ;; > (interseccion-auxiliar (2 4 6 8 10) (2 3 4 5) ())

12 ;; (4 2)

13 (define interseccion-auxiliar

14 ( (A B C)....)15 ;; > (interseccion (2 4 6 8 10) (2 3 4 5))

16 ;; (4 2)

17 (define interseccion

18 ( (A B)19 (interseccion-auxiliar A B vacio)))


-AbC

HIRIMRXIVWIGGMSREY\MPMEVS %&'GSRH &SSPIER" )\TVIWMSR" &SSPIER" )\TVIWMSR" &SSPIER" )\TVIWMSR" &SSPIER" )\TVIWMSR"

HIRIMRXIVWIGGMSRS %&MRXIVWIGGMSREY\MPMEV%&GSRNYRXSZEGMS

HIRIMRXIVWIGGMSREY\MPMEVS %&'GSRH &SSPIER" )\TVIWMSR" &SSPIER" )\TVIWMSR" &SSPIER" )\TVIWMSR" &SSPIER" )\TVIWMSR"

HIRIMRXIVWIGGMSRS %&MRXIVWIGGMSREY\MPMEV%&GSRNYRXSZEGMS

Diferencia

Definicion (Diferencia)Si A y B son conjuntos, la diferencia del conjunto A respecto del conjunto B es elconjunto denotado por A \B, que se compone de los elementos que pertenecen a A peroque no pertenecen a B.

-AbC

Diferencia-efectiva

La diferencia del conjunto A respecto del conjunto B se puede definir efectivamente alconsiderar un conjunto auxiliar C originalmente vaco, como

\(A,B,C) ,

C si A = \(A, B, C) si a0 B\(A, B,1 (a0, C)) si a0 6 B

Y al igual que la interseccion, esta definicion efectiva se complementa con

\(A,B) , \(A,B, )

-AbC

TAREA

Escribe las definiciones en DrRacket de la diferencia de dos conjuntos.

1. La funcion de diferencia-auxiliar tiene un formato:

1 ;; 2 ;;

3 ;; Proposito: Construir un conjunto, haciendo la diferencia entre

4 ;; los primeros dos conjuntos

5 ;;


7 ;; > (diferencia-auxiliar (1 2 3 4) (a b c) ())

8 ;; (4 3 2 1)

9 ;; > (diferencia-auxiliar () (a b c) ())

10 ;; ()

11 ;; > (diferencia-auxiliar (1 2 3 4) () ())

12 ;; (4 3 2 1)

13 ;; > (diferencia-auxiliar (1 2 3 4) (a b c 2 4) ())

14 ;; (3 1)

15 ;; >

16 (define diferencia-auxiliar

17 ( (A B C)....)18 ;; > (diferencia (1 2 3 4) (a b c 2 4) ())

19 ;; (3 1)

20 (define diferencia

21 ( (A B)22 (diferencia-auxiliar A B vacio)))


-AbC

Diferencia simetrica

Definicion (Diferencia simetrica)La diferencia simetrica de dos conjuntos A y B, es un conjunto denotado por A4B, demanera equivalente se puede denotar en forma de aplicacion de una funcion como 4(A,B)y representa al conjunto de todos los elementos que pertenecen a A pero nno pertenecen aB, junto con los elementos de B que no pertenecen al conjunto A.

diferencia-simetrica1 ;; 2 ;;

3 ;; Proposito: Construir un conjunto, haciendo la diferencia simetrica entre

4 ;; dos conjuntos

5 ;;


7 ;; > (diferenciaSimetrica (1 2 3 4) (a b c 2 4))

8 ;; (1 3 c b a)

9 ;; > (diferenciaSimetrica (a b c 2 4) (1 2 3 4))

10 ;; (a b c 3 1)

11 ;; > (diferenciaSimetrica (a b c 2 4) ())

12 ;; (a b c 2 4)

13 ;; > (diferenciaSimetrica (1 2 3 4) ())

14 ;; (1 2 3 4)

15 ;; > (diferenciaSimetrica () ())

16 ;; ()

17 ;; >

18 (define diferencia-simetrica

19 ( (A B)20 (union (diferencia A B)

21 (diferencia B A))))

-AbC

EJERCICIO

Utiliza DrRacket para resolver los siguientes ejercicios. Escribe una R-expresion y escribeel resultado.

I Si A , {a, b, c, d, e, f}, B , {a, d, f, y, u} y C , {x, y, z, q, a}, define:i A (define A (a b c d e f))ii B

iii C

II Con A, B y C anteriores, calcula:

i A B (union A B)(a b c d e f y u)ii A Biii A B Civ (A4 C) B

III Marca las expresiones verdaderas

i A B (subconjunto? A B)#fii f Biii x 6 Biv (A4 C) (B 4A)v (A \ C) (B 4A) C (A C)

-AbC

TAREA

Considera el conjunto A como el conjunto de alumnos que cursan el cuarto ciclo en launiversidad, y B el conjunto de alumnos que toman el curso de Matematicas Discretas.Considera que ya existen definiciones en DrRacket de estos conjuntos:

1 (define A (20 16 1 31 5 7 25 22 38 11 22 27 21 10 24 19 23 3 22 25))

2 (define B (15 32 21 10 16 14 29 30 9 18 7 8 20 24 27 17 18 22 5 36))

Una respuesta correcta tiene la forma:

1 (define X (diferencia (union A B) (interseccion B A)))

i Escribe la definicion en DrRacket de un conjunto C compuesto por los alumnos decuarto ciclo que se han matriculado en Matematicas Discretas.

ii Escribe la definicion en DrRacket de un conjunto D compuesto por los alumnos decuarto ciclo que no cursan Matematicas Discretas.

iii Escribe la definicion en DrRacket de un conjunto E compuesto por los alumnos que obien cursan el cuarto ciclo o que se han matriculado en Matematicas Discretas.

iv Escribe la definicion en DrRacket de un conjunto F compuesto por los alumnos que ono cursan el cuarto ciclo o no se han matriculado en Matematicas Discretas.

Es importante que cada definic

Documents

Matematicas Discretas (in progress)