Problema del viajante

El problema del vendedor viajero, problema del vendedor ambulante, problema del agente viajero o problema del viajante (TSP por sus siglas en inglés (Travelling Salesman Problem)), responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en la investigación de operaciones y en la ciencia de la computación.

El problema fue formulado por primera vez en 1930 y es uno de los problemas de optimización más estudiados. Es usado como prueba para muchos métodos de optimización. Aunque el problema es computacionalmente complejo, una gran cantidad de heurísticas y métodos exactos son conocidos, de manera que, algunas instancias desde cien hasta miles de ciudades pueden ser resueltas.

El TSP tiene diversas aplicaciones aún en su formulación más simple, tales como: la planificación, la logística y en la fabricación de circuitos electrónicos. Un poco modificado, aparece como: un sub-problema en muchas áreas, como en la secuencia de ADN. En esta aplicación, el concepto de “ciudad” representa, por ejemplo: clientes, puntos de soldadura o fragmentos de ADN y el concepto de “distancia” representa el tiempo de viaje o costo, o una medida de similitud entre los fragmentos de ADN. En muchas aplicaciones, restricciones adicionales como el límite de recurso o las ventanas de tiempo hacen el problema considerablemente difícil. El TSP es un caso especial de los Problemas del Comprador Viajante (travelling purchaser problem).

En la teoría de la complejidad computacional, la versión de decisión del TSP (donde, dado un largo “L”, la tarea es decidir cuál grafo tiene un camino menor que L) pertenece a la clase de los problemas NP-completos. Por tanto, es probable que en el caso peor el tiempo de ejecución para cualquier algoritmo que resuelva el TSP aumente de forma exponencial con respecto al número de ciudades.

Denotamos por “Problema del Mensajero” (dado que en la práctica esta pregunta puede resolverse por cada cartero, aunque puede ser resuelta por varios viajeros) la pregunta es encontrar, para un conjunto finito de puntos de los cuales se conocen las distancias entre cada par, el camino más corto entre estos puntos. Por supuesto, el problema es resuelto por un conjunto finito de intentos. La regla que se debe seguir es que desde el punto inicial se va al punto más cercano a este, de ahí a su más cercano y así sucesivamente, en general este algoritmo no retorna la ruta más corta

Caso práctico

En el problema se presentan N! rutas posibles, aunque se puede simplificar ya que dada una ruta nos da igual el punto de partida y esto reduce el número de rutas a examinar en un factor N quedando (N-1)!. Como no importa la dirección en que se desplace el viajante, el número de rutas a examinar se reduce nuevamente en un factor 2. Por lo tanto, hay que considerar (N-1)!/2 rutas posibles.

En la práctica, para un problema del viajante con 5 ciudades hay (5-1)!/2=12 rutas diferentes y no necesitamos un ordenador para encontrar la mejor ruta, pero apenas aumentamos el número de ciudades las posibilidades crece factorialmente:

• Para 10 ciudades hay (10-1)!/2=181.440 rutas diferentes
• Para 30 ciudades hay más de 4·10^30 rutas posibles. Un ordenador que calcule un millón de rutas por segundo necesitaría 10^17 años para resolverlo. Dicho de otra forma, si se hubiera comenzado a calcular al comienzo de la creación del universo (hace unos 13.400 millones de años) todavía no se habría terminado.

Puede comprobarse que por cada ciudad nueva que incorporemos, el número de rutas se multiplica por el factor N y crece factorialmente. Por ello el problema pertenece a la clase de problemas NP-completos.

Como un problema de grafos

TSP simétrico con 4 ciudades

El TSP puede ser modelado como un grafo ponderado no dirigido, de manera que las ciudades sean los vértices del grafo, los caminos son las aristas y las distancias de los caminos son los pesos de las aristas. Esto es un problema de minimización que comienza y termina en un vértice específico y se visita el resto de los vértices exactamente una vez. Con frecuencia, el modelo es un grafo completo (cada par de vértices es conectado por una arista). Si no existe camino entre un par de ciudades, se añade arbitrariamente una arista larga para completar el grafo sin afectar el recorrido óptimo.

Asimétrico y simétrico

En el ‘’’TSP simétrico’’’, la distancia entre un par de ciudades es la misma en cada dirección opuesta, formando un grafo no dirigido. Este problema reduce a la mitad el número de soluciones posibles. En el ‘’’TSP asimétrico’’’, pueden no existir caminos en ambas direcciones o las distancias pueden ser diferentes, formando un grafo dirigido. Los accidentes de tráfico, las calles de un solo sentido y las tarifas aéreas para ciudades con diferentes costos de partida y arribo, son ejemplos de cómo esta simetría puede ser quebrada.

Problemas relacionados

• Una formulación equivalente en términos de Teoría de grafos es: dado una grafo ponderado completo (donde los vértices representan las ciudades, las aristas representan los caminos y los pesos son el costo o las distancias de estos caminos), encontrar un ciclo de Hamilton con menor peso.

• Las restricciones de retorno a la ciudad de comienzo no cambia la complejidad computacional del problema, vea Problema del camino Hamiltoniano.

• Otro problema relacionado es el Problema del agente viajero con cuello de botella (bottleneck TSP): Encontrar un ciclo de Hamilton en un grafo ponderado con el mínimo peso de las aristas más pesadas. El problema es de una considerable importancia en la práctica, en las áreas de la transportación y la logística. Un ejemplo clásico es en la fabricación de circuitos impresos: planificando una ruta de la máquina perforadora para perforar los huecos en un PCB. Otras son, las aplicaciones de perforado o maquinado en la robótica: las “ciudades” son los huecos de diferentes tamaños a perforar y el “costo de viaje” incluye el tiempo para reequipar el robot (problema del secuenciado del trabajo de una máquina simple).⁶​

• La generalización del TSP trata con “estados” que tienen (una o más) “ciudades” y el viajante tiene que visitar exactamente una ciudad de cada “estado”. También se conoce como el Problema del Político Viajero. Como una aplicación se considera, el perforado en la fabricación de semiconductores, vea e.g., Patente USPTO nº 7054798. Sorprendentemente, Behzad y Modarres demostraron que el problema generalizado del viajante puede ser transformado en el problema del viajante estándar con el mismo número de ciudades, pero modificando la Matriz de distancias

• El problema de ordenamiento secuencial trata con el problema de visitar un conjunto de ciudades donde se tiene en cuenta las relaciones de precedencias entre las ciudades.

• El problema del viajante comprador trata con un comprador que está cargado con un conjunto de productos. Él puede comprar estos productos en varias ciudades, pero tienen diferentes precios y no todas las ciudades ofrecen los mismos productos. El objetivo es encontrar una ruta entre un subconjunto de ciudades, los cuales minimicen el costo total (costo de viaje + costo de la compra) y habilite la compra de todos los productos requeridos.

Formulación de la programación lineal en enteros

El TSP puede ser formulado por la programación lineal en enteros.​ Sea ${\displaystyle x_{ij}}$ igual 1, si existe el camino de ir de la i a la ciudad j, y 0 en otro caso, para el conjunto de ciudades 0,..., n. Sean ${\displaystyle u_{i}}$ para i = 1,..., n variables artificiales y sea ${\displaystyle c_{ij}}$ la distancia desde la ciudad i a la ciudad j. Entonces el modelo de programación lineal en enteros puede ser escrito como:

${\displaystyle {\begin{aligned}\min &\sum _{i=0}^{n}\sum _{j\neq i,j=0}^{n}c_{ij}x_{ij}&\\0\leq &x_{ij}\leq 1&i,j=0,\dots n\\&x_{ij}{\text{ integer}}&i,j=0,\dots n\\&\sum _{i=0,i\neq j}^{n}x_{ij}=1&j=0,\ldots ,n\\&\sum _{j=0,j\neq i}^{n}x_{ij}=1&i=0,\ldots ,n\\u_{i}-u_{j}&+nx_{ij}\leq n-1&1\leq i\neq j\leq n.\end{aligned}}}$

El primer conjunto de igualdades asegura que cada ciudad 0,..., n de salida llegue exactamente a una ciudad, y el segundo conjunto de igualdades aseguran que desde cada ciudad 1,..., n se salga exactamente hacia una ciudad (ambas restricciones también implican que exista exactamente una salida desde la ciudad 0.) La última restricción obliga a que un solo camino cubra todas las ciudades y no dos o más caminos disjuntos cubran conjuntamente todas las ciudades. Para probar esto se muestra en (1) que toda solución factible contiene solamente una secuencia cerrada de ciudades, y en (2) que para cada uno de los recorridos que cubren todas las ciudades, hay valores para todas las variables ${\displaystyle u_{i}}$ que satisfacen las restricciones.

Para probar que cada solución factible contiene solamente una secuencia cerrada de ciudades, es suficiente mostrar que cada sub-ruta en una solución factible pasa a través de la ciudad 0 (note que las igualdades aseguran que solamente pude haber un recorrido de ese tipo). Por tanto, si sumamos todas las desigualdades correspondiente a ${\displaystyle x_{ij}=1}$ para cada sub-ruta de k pasos que no pasan a través de la ciudad 0, obtenemos ${\displaystyle nk\leq (n-1)k,}$ lo cual es una contradicción.

Ahora, mostramos que para cada recorrido que cubre todas las ciudades, hay valores de las variables ${\displaystyle u_{i}}$ que satisfacen las restricciones.

Sin pérdida de generalidad, se define el recorrido con origen y fin en la ciudad 0. Escoger  si la ciudad i es visitada en el paso t (i, t = 1, 2,..., n). Entonces dado  no puede ser mayor que n y  no puede ser menor que 1; por lo tanto las restricciones se satisfacen siempre que  Para  se satisfacen las restricciones.

Mapas de Karnaugh

Metodología

Vamos a indicar cada uno de los pasos para obtener la expresión MSP (mínima suma de productos). Para ello vamos a ilustrarlo con el ejemplo:

F(x, y, z) = x’ y’ z’ + x’ y’ z + x’ y z’+ x y’ z’+ x y z’

Los pasos a seguir para conseguir reducir esta expresión  son:

1.  Convertir la expresión a una suma de productos si es necesario. Esto se puede realizar de varias maneras:

§ Algebraicamente.

§ Construyendo una tabla de verdad, trasladando los valores al mapa de Karnaugh. Esta es la forma que vamos a utilizar.

X	Y	Z	Resultado
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

                 

        

2.  Cubrir todos los unos del mapa mediante rectángulos de 2^N elementos, donde N = 0 ... número de variables. Ninguno de esos rectángulos debe contener ningún cero (tal y como indicábamos en el apartado anterior).

§ Para minimizar el número de términos resultantes se hará el mínimo número posible de rectángulos que cubran todos los unos.

§ Para minimizar el número de variables se hará cada rectángulo tan grande como sea posible.

Véase que en este caso se ha unido la columna izquierda con la derecha para formar un único rectángulo.

3. Encontrar la MSP (suma de productos minimal). Ojo porque podemos encontrarnos con que puede haber más de una MSP.

§ Cada rectángulo pertenece a un término producto.

§ Cada término se define encontrando las variables que hay en común en tal rectángulo.

En nuestro ejemplo tenemos F(X, Y, Z) = Z’ + X’Y’ nótese que las variables resultado son las que tienen un valor común en cada rectángulo.

          

Rectángulos y productos.

Cada rectángulo representa un término. El tamaño del rectángulo y el del término resultante son inversamente, es decir que, cuanto más largo sea el rectángulo menor será el tamaño del término final.

En general, si tenemos una función con n variables :

§ Un rectángulo que ocupa una celda equivale a un término con  n variables.

§ Un rectángulo que ocupa dos celdas equivale a un término con  n-1 variables.

§ Un rectángulo que ocupa 2ⁿ  celdas equivale al término de valor 1.

Por lo tanto,  para encontrar el MSP se debe:

§ Minimizar el número de rectángulos que se hacen en el mapa de Karnaugh, para minimizar el número de términos resultantes.

§ Maximizar el tamaño de cada rectángulo, para minimizar el número de variables de cada término resultante.

Agrupación de rectángulos.

Cuando tenemos distintas posibilidades de agrupar rectángulos hay que seguir ciertos criterios:

1. Localiza todos los rectángulos más grandes posibles, agrupando todos los unos. Estos se llamarán  implicantes primos.
2. Si alguno de los rectángulos anteriores contiene algún uno que no aparece en ningún otro rectángulo entonces es un implicante primo esencial.Éstos han de aparecer en el resultado final de manera obligatoria.

El resto de implicantes primos se podrán combinar para obtener distintas soluciones.

Véase este ejemplo que ilustra lo que les planteamos. Aquí los implicantes primos son cada uno de los diferentes rectángulos obtenidos. Los primos implicantes esenciales son el rectángulo rojo y el verde, por contener unos que no son cubiertos por otros rectángulos. Así todas las posibles soluciones han de contener estos dos implicantes.

Solución: F( X, Y, Z, T ) = X’Y’ + XYT’ + XZT

Técnicas de conteo

Principios fundamentales del conteo

La enumeración o conteo puede parecer un proceso obvio que un estudiante aprende al estudiar aritmética por primera vez. Pero luego según parece se presta poca atención en lo que se refiere a un desarrollo mas amplio del conteo conforme al estudiante pasa a áreas mas difíciles de las matemáticas, como el álgebra, la geometría, la trigonométrica y el calculo. En consecuencia deberá servir como advertencia acerca del conteo.

La enumeración no termina con la aritmética, También tiene aplicaciones en áreas como la teoría de códigos, la probabilidad y estadísticas.

Reglas de la suma y el producto.

1-. Si una primera tarea puede realizarse de  n formas y de una segunda tarea puede realizarse de n formas y no es posible realizar ambas tareas de manera simultanea, entonces para llevar a acabo cualquieras de ellas de n

2-. Si un procedimiento se puede descomponer en las etapas primera y segunda y si existen m resultados posibles y la segunda y si existen m resultados posibles de la primera etapa, para cada uno de los resutlados existen n resultados posibles para la segunda etapa, entonces el procedimento total que puede realizar en el orden dado.

 EJERICICIOS:

1.¿Cuantos número de tres cifras digernetes se puden formar con los siguientes dígitos " 1,2,3"

                  Pn=n!= P3  =3!   3x2x1=6                                      123

                                                                                                  132

                                                                                                  231

                                                                                                  213

                                                                                                  312

                                                                                                  321

2. ¿Cuantos grupos diferentes de 3 cifras se pueden formar sin que se repitan los elementos usado las siguientes vocales ?

          "A,E,O"

                 Pn=n!= p3=3!    3x2x1=6                          AEO

                                                                                    OAE

                                                                                    EAO

                                                                                    OAE

                                                                                    AOE

                                                                                    EOA

3.¿Cuantos grupos de 4 elementos se pueden formar con los siguientes dígitos"3,5,7,9"

               

       

                 p4=4!= 4x3x2x1=24

4. Antiguamente los barcos se comunicaban entre si utilizando banderas de diferentes colores colocando de manera ordenadas en diferentes posiciones ,¿Cuantos mensajes distintos se podrán enviar con las banderas en los colores azul,rojo,verde,negro?

indique cuantos mensajes serian si se añade otra bandera con color cafe en este caso n se muestran las agrupaciones :

   Pn=n!= P4!   4x3x2x1= 24 mensajes.

 Pn=n!=  P5!  5x4x3x2x1=120 mensajes.

                                        PERMUTACIONES CON REPETICIÓN.                                                 

  

Se llama permutación con repetición a los grupos de elementos que se forman usado N elementos donde el primer elemento se repite n veces, el segundo tambien se repite n veces y así se repite hasta llegar al fin de la lista. estas agrupaciones deben seguir las siguientes reglas:

• entran todos los elementos
• si importa el orden
• si se repiten los elementos

La formula para realizar calculo de la permutación con repetición es la siguiente:

                     

Con las cifras 2,2,2,3,3,3,3,4,4¿Cunatos números de 9 cifras se pueden formar su los datos son  n=9, a=3,b=4,c=2

        3,4,2

  Prn=                     P9                         9x8x7x6x5x4x3x2x1     =    9x8x7x6x5      = 1260

                       3!4!2!                        3x2x1.4x3x2x1                    6;2

                                          PERMUTACIONES CIRCULARES                                                

Las permutaciones circulares   se utilizan cunado los elecentos se van a ordenar en circulo.

EJEMPLO:

  

Los comensales en un mesa de modo que el prier elemento que se situe en la mesa determina el principio y el fin de la lista

La fomrula para la permutacón circular es PC=  n!

                                                                              n-1

Teoría de conjuntos

1 -. A la entrada de la escuela, se les aplicó a 156 niños una encuesta respecto a sus juguetes favoritos. 
La encuesta arrojó los siguientes resultados:
▪ A 52 niños les gustaba el balón; a 63 les gustaban los carritos; a 87 les gustaban los videojuegos.
▪ Además algunos de ellos coinciden en que les gustaba mas de un juguete: 26 juegan con el balón y  carritos; 37 juegan con carritos y videojuegos; 23 juegan con el balón y los videojuegos; por ultimo 7  expresaron su gusto por los tres.
a) ¿A cuántos niños les gusta otro juguete no mencionado en la encuesta?
b) ¿A cuántos niños les gusta solamente jugar con los videojuegos?
c) ¿A cuántos niños les gusta solamente jugar con el balón?

2-.La secretaría de educación municipal requiere la provisión de 29 cargos docentes en las siguientes áreas:  13 profesores en matemáticas, 13 profesores en física y 15 en sistemas. Para el cubrimiento de los cargos  se requiere que: 6 dicten matemáticas y física, 4 dicten física y sistemas y 5 profesores dicten  matemáticas y sistemas.
Determinar:
a) ¿Cuántos profesores se requiere que dicten las 3 áreas?
b) ¿Cuántos profesores se requiere para dictar matemáticas únicamente?
c) ¿Cuántos profesores se requiere para dictar matemáticas y sistemas pero no física?

3-.Se encuesta a 150 familias consultando por el nivel educacional actual de sus hijos. 

Los resultados obtenidos son:
    ▪ 10 familias tienen hijos en Enseñanza Básica, Enseñanza Media y Universitaria.
    ▪ 16 familias tienen hijos en Enseñanza Básica y Universitaria.
    ▪ 30 familias tienen hijos en Enseñanza Media y Enseñanza Básica.
    ▪ 22 familias tienen hijos en Enseñanza Media y Universitaria.
    ▪ 72 familias tienen hijos en Enseñanza Media.
    ▪ 71 familias tienen hijos en Enseñanza Básica.
    ▪ 38 familias tienen hijos en Enseñanza Universitaria.
Con la información anterior, deducir:
- El número de familias que solo tienen hijos universitarios.
- El número de familias que tienen hijos solo en dos niveles.
- El número de familias que tienen hijos que no estudian.

Diagramas de Venn

1 -Un Diagrama de Venn es una representación gráfica, normalmente óvalos o círculos, que nos muestra las relaciones existentes entre los conjuntos. Cada óvalo o círculo es un conjunto diferente. La forma en que esos círculos se sobreponen entre sí muestra todas las posibles relaciones lógicas entre los conjuntos que representan. Por ejemplo, cuando los círculos se superponen, indican la existencia de subconjuntos con algunas características comunes.

2- Los diagramas de Venn son esquemas usados en la teoría de conjuntos, tema de interés en matemáticas, lógica de clases y razonamiento diagramático. Estos diagramas muestran colecciones (conjuntos) de cosas (elementos) por medio de líneas cerradas. La línea cerrada exterior abarca a todos los elementos bajo consideración, el conjunto universal U.

Los diagramas de Venn fueron ideados hacia 1880 por John Venn.

Operaciones con conjuntos:

En las matemáticas, no podemos definir a un conjunto, por ser un concepto primitivo, pero hacemos abstracción y lo pensamos como una colección desordenada de objetos, los objetos de un conjunto pueden ser cualquier cosa siempre que tengan una relación entre ellos, a los objetos de un conjunto se les llama elementos o miembros de dicho conjunto, por lo tanto un conjunto contiene a sus elementos. Se representan con una letra mayúscula y a los elementos o miembros de ese conjunto se les mete entre llaves corchetes o parentesis. ({,}).

Dos conjuntos se pueden combinar de muchas maneras distintas, por ejemplo, teniendo un conjunto de la gente que juega al fútbol y otro de la gente que juega a baloncesto podemos hacer muchas combinaciones como el conjunto de personas que juegan a fútbol o baloncesto, las que juegan a fútbol y baloncesto, las que no juegan a baloncesto, etc.

Unión: En las matemáticas, no podemos definir a un conjunto, por ser un concepto primitivo, pero hacemos abstracción y lo pensamos como una colección desordenada de objetos, los objetos de un conjunto pueden ser cualquier cosa siempre que tengan una relación entre ellos, a los objetos de un conjunto se les llama elementos o miembros de dicho conjunto, por lo tanto un conjunto contiene a sus elementos. Se representan con una letra mayúscula y a los elementos o miembros de ese conjunto se les mete entre llaves corchetes o parentesis. ({,}).

Dos conjuntos se pueden combinar de muchas maneras distintas, por ejemplo, teniendo un conjunto de la gente que juega al fútbol y otro de la gente que juega a baloncesto podemos hacer muchas combinaciones como el conjunto de personas que juegan a fútbol o baloncesto, las que juegan a fútbol y baloncesto, las que no juegan a baloncesto, etc.

Intersección: El símbolo del operador de esta operación es: ∩, y es llamado capa.

:Sean A y B dos conjuntos, la coincidencia de ambos (A ∩ B) es el conjunto C el cual contiene los elementos que están en A y que están en B.

Un elemento x pertenece a la coincidencia de los conjuntos A y B si, y sólo si, x pertenece al conjunto A y x pertenece al conjunto B, por lo tanto 

Disjuntividad: Se dice que dos conjuntos A y B son disjuntos cuando la coincidencia de ambos es el conjunto vacío. A ∩ B= {}

Ejemplos

1. Ejemplo: La coincidencia del conjunto de números pares y el conjunto de números impares sería el conjunto C={${\displaystyle \emptyset }$} o sea serían disjuntos.
2. Ejemplo: La coincidencia del conjunto de personas que juegan a baloncesto y el conjunto de personas que juegan a fútbol es el conjunto vacío, osea serían disjuntos.
3. Ejemplo: La coincidencia de A={3,7,8} y B={1,2,9} sería C={${\displaystyle \emptyset }$}, ya que {3,7,8}∩{1,2,9}={${\displaystyle \emptyset }$} por lo tanto A y B son disjuntos.

Ley de morgan: Teniendo presentes estas definiciones quizás sea entonces mucho más sencillo comprender el sentido de cada una de estas relaciones de Unión e Intersección de conjuntos, que se dan en base al Conjunto complementario, y que pueden ser descritas a su vez de la siguiente forma:

Ley de Morgan con respecto a la Unión

Esta Ley o propiedad matemática, según lo que indican las diferentes fuentes de Álgebra de Conjuntos, señala que siempre y en todo caso, el conjunto complementario de la Unión de dos conjuntos resulta ser equivalente a la intersección que puede ocurrir entre cada uno de los conjuntos complementarios de estos. Igualmente, esta propiedad o Ley de Morgan puede ser expresada matemáticamente de la siguiente forma:

(A ∪ B)∁ =  A∁ ∩ B∁

Diferencia: El símbolo de esta operación es: \.

La diferencia consiste en eliminar de A todo elemento que esté en B, también se puede denotar con el símbolo de la resta A-B, por lo tanto, la diferencia de los conjuntos A y B es el conjunto C que tiene a todos los elementos que están en A, pero no en B.

También se le puede llamar a la diferencia de A y B: complementario de B con respecto a A.

Por lo tanto, un elemento pertenece a la diferencia de A y B si, y sólo si ${\displaystyle \{x/x\in A\land x\not \in B\}}$

Ejemplos

1. Ejemplo: La diferencia de los conjuntos {1,2,3,4} y {1,3,5,7} es el conjunto {2,4}, sin embargo la diferencia de los conjuntos {1,3,5,7} y {1,2,3,4} es el conjunto {5,7}.
2. Ejemplo: La diferencia del conjunto de las personas que juegan al fútbol y el conjunto de las personas que juegan a baloncesto es el conjunto de las personas que solo y exclusivamente juegan al fútbol.

Diferencia simétrica: El símbolo de esta operación es: Δ.

La diferencia simétrica de dos conjuntos A y B es otro conjunto el cual posee los elementos que o bien se encuentran en A, o bien se encuentran en B, pero no en los dos a la vez. A Δ B = C, donde C no tiene

1. Ejemplo: La diferencia simétrica del conjunto de personas que juegan a fútbol y el conjunto de personas que juegan a baloncesto es el conjunto de personas que juegan sólo a fútbol y sólo a baloncesto, pero no que jueguen a ambos a la vez.

                                  Teoría de conjuntos

La teoría de conjuntos es una rama de la lógica matemática que estudia las propiedades y relaciones de los conjuntos: colecciones abstractas de objetos, consideradas como objetos en sí mismas. Los conjuntos y sus operaciones más elementales son una herramienta básica en la formulación de cualquier teoría matemática.¹​

La teoría de los conjuntos es lo suficientemente rica como para construir el resto de objetos y estructuras de interés en matemáticas: números, funciones, figuras geométricas,...; gracias a las herramientas de la lógica, permite estudiar los fundamentos de aquella. En la actualidad se acepta que el conjunto de axiomas de la teoría de Zermelo-Fraenkel es suficiente para desarrollar toda la matemática.

Además, la propia teoría de conjuntos es objeto de estudio per se, no sólo como herramienta auxiliar, en particular las propiedades y relaciones de los conjuntos infinitos. En esta disciplina es habitual que se presenten casos de propiedades indemostrables o contradictorias, como la hipótesis del continuo o la existencia de un cardinal inaccesible. Por esta razón, sus razonamientos y técnicas se apoyan en gran medida en la lógica.

El desarrollo histórico de la teoría de conjuntos se atribuye a Georg Cantor, que comenzó a investigar cuestiones conjuntistas «puras» del infinito en la segunda mitad del siglo XIX, precedido por algunas ideas de Bernhard Bolzano e influido por Richard Dedekind. El descubrimiento de las paradojas de la teoría cantoriana de conjuntos, formalizada por Gottlob Frege, propició los trabajos de Bertrand Russell, Ernst Zermelo, Abraham Fraenkel y otros a principios del siglo XX.

                                                        Lógica matemática

La lógica matemática, también llamada lógica simbólica, lógica teorética, lógica formal o logística,¹​ es el estudio matemático de la lógica y su aplicación a otras áreas de la matemática y la ciencia. Comprende la aplicación de las técnicas de la lógica formal a las matemáticas y el razonamiento matemático, y conversamente la aplicación de técnicas matemáticas a la representación y el análisis de la lógica formal. La investigación en lógica matemática ha jugado un papel crucial en el estudio de los fundamentos de las matemáticas.

La lógica matemática estudia la inferencia mediante la construcción de sistemas formales como la lógica proposicional, la lógica de primer orden o la lógica modal. Estos sistemas capturan las características esenciales de las inferencias válidas en los lenguajes naturales, pero al ser estructuras formales susceptibles de análisis matemático, permiten realizar demostraciones rigurosas sobre ellas.

La lógica matemática se suele dividir en cuatro áreas: teoría de modelos, teoría de la demostración, teoría de conjuntos y teoría de la computabilidad. La teoría de la demostración y la teoría de modelos fueron el fundamento de la lógica matemática. La teoría de conjuntos se originó en el estudio del infinito por Georg Cantor y ha sido la fuente de muchos de los temas más desafiantes e importantes de la lógica matemática, a partir del teorema de Cantor, el axioma de elección y la cuestión de la independencia de la hipótesis del continuo, al debate moderno sobre grandes axiomas cardinales. La lógica matemática tiene estrechas conexiones con las ciencias de la computación. La teoría de la computabilidad captura la idea de la computación en términos lógicos y aritméticos. Sus logros más clásicos son la indecidibilidad del Entscheidungsproblem de Alan Turing y su presentación de la tesis de Church-Turing. Hoy en día, la teoría de la computabilidad se ocupa principalmente del problema más refinado de las clases de complejidad (¿cuándo es un problema eficientemente solucionable?) y de la clasificación de los grados de insolubilidad.

                                                           Álgebra booleana

Es una rama especial del álgebra que se usa principalmente en electrónica digital. El álgebra booleana fue inventada en el año 1854 por el matemático inglés George Boole.

El álgebra de Boole es un método para simplificar los circuitos lógicos (o a veces llamados circuitos de conmutación lógica) en electrónica digital.

Por lo tanto, también se llama como "Cambio de álgebra". Podemos representar el funcionamiento de los circuitos lógicos utilizando números, siguiendo algunas reglas, que son bien conocidas como "Leyes del álgebra de Boole".

También podemos hacer los cálculos y las operaciones lógicas de los circuitos aún más rápido siguiendo algunos teoremas, que se conocen como "Teoremas del álgebra de Boole". Una función booleana es una función que representa la relación entre la entrada y la salida de un circuito lógico.

La lógica booleana solo permite dos estados del circuito, como True y False. Estos dos estados están representados por 1 y 0, donde 1 representa el estado "Verdadero" y 0 representa el estado "Falso".

Lo más importante para recordar en el álgebra de Boole es que es muy diferente al álgebra matemática regular y sus métodos. Antes de aprender sobre el álgebra de Boole, vamos a contar  un poco sobre la historia del álgebra de Boole y su invención y desarrollo.

---

Historia del álgebra de Boole

Como se mencionó anteriormente, el álgebra de Boole se inventó en el año de 1854, por el matemático inglés George Boole. Primero declaró la idea del álgebra de Boole en su libro "Una investigación de las leyes del pensamiento".

Después de esto, el álgebra de Boole es bien conocida como la forma perfecta para representar los circuitos lógicos digitales.

A fines del siglo XIX, los científicos Jevons, Schroder y Huntington utilizaron este concepto para términos modernizados. Y en el año de 1936, MHStone demostró que el álgebra de Boole es 'isomorfo' para los conjuntos (un área funcional en matemáticas).

En la década de 1930, un científico llamado Claude Shannon desarrolló un nuevo método de álgebra tipo "Cambio de álgebra" utilizando los conceptos de álgebra de Boole, para estudiar los circuitos de conmutación.

La síntesis lógica de las herramientas modernas de automatización electrónica se representa de manera eficiente mediante el uso de funciones booleanas conocidas como "Diagramas de decisión binarios".

El álgebra de Boole permite solo dos estados en un circuito lógico, como True y False, High and Low, Yes y No, Open and Close o 0 y 1.