Estructuras de objetos discretos para la computación

1.       Teoría de conjuntos y subconjuntos

2.       Métodos para la representación de objetos

3.       Funciones empleadas en la aplicación de las ciencias de la computación

4.      

Teoría básica de los semigrupos y grupos 

5.       Razonamiento lógico en las ciencias de la computación

6.       Introducción a los autómatas finitos

Teoría de la codificación

Teoría de conjuntos y subconjuntos

            Se entiende por conjunto a la agrupación en un todo de objetos bien diferenciados de nuestra intuición o nuestra mente.

El concepto de conjunto es intuitivo y podríamos definirlo simplemente como una colección de objetos, así podemos hablar de un conjunto de personas, ciudades, lapiceros o del conjunto de objetos que hay en un momento dado encima de una mesa. Un conjunto esta bien definido si se sabe si un determinado elemento pertenece o no al conjunto, así el conjunto de los bolígrafos azules, esta bien definido, porque a la vista de un bolígrafo podemos saber si es azul o no. El conjunto de las personas altas no esta bien definido, porque a la vista de una persona, no siempre podrá decir si es alta o no, o puede haber distintas personas, que opinen si esa persona es alta o no lo es.      

Se le llama subconjuntos al conjunto aquel que pertenece a otro, o sus elementos son tomados de un conjunto superior o de mayor tamaño.

Es decir, conjunto  se dice que es subconjunto de otro , si cada elemento de  es también elemento de , es decir, cuando se verifique:

,

Sea cual sea el elemento . En tal caso, se escribe .

Cabe señalar que, por definición, no se excluye la posibilidad de que si , se cumpla . Si tiene por lo menos un elemento que no pertenezca al conjunto , pero si todo elemento de es elemento de , entonces decimos que es un subconjunto propio de , lo que se representa por . Llamamos subconjuntos impropios de a los conjuntos y

Si es un subconjunto de , decimos también que es un superconjunto de , lo que se escribe . Así pues

.

   1.2 Operaciones con conjuntos

Unión

Para cada par de conjuntos A y B existe un conjunto que se denota como el cual contiene todos los elementos de A y de B. De manera más general, para cada conjunto S existe otro conjunto denotado como de manera que sus elementos son todos los  tales que . De esta manera es el caso especial donde .

Es claro que el hecho de que un elemento x pertenezca a es condición necesaria y suficiente para afirmar que x es un elemento de A o al menos de B. Es decir

Intersección

Diagrama de Venn que ilustra

Los elementos comunes a y forman un conjunto denominado intersección de y , representado por . Es decir, es el conjunto que contiene a todos los elementos de A que al mismo tiempo están en B:

.

Si dos conjuntos y son tales que , entonces y se dice que son conjuntos disjuntos.

Es claro que el hecho de que es condición necesaria y suficiente para afirmar que y . Es decir

Diferencia