Lógica y Conjuntos: Proposiciones

Capítulo 1: Preliminares - Lógica y Conjuntos

• Una proposición es un enunciado declarativo que es verdadero o falso, pero no ambos.
• El valor de verdad de una proposición verdadera se denota por $V$, mientras que para una proposición falsa se denota por $F$.
• La negación de una proposición $p$ se denota por $\neg p$ ("no $p$").
  • Si $p$ es verdadera, $\neg p$ es falsa, y viceversa.
• La conjunción de proposiciones $p$ y $q$ se denota por $p \land q$ ("$p$ y $q$").
  • $p \land q$ es verdadera solo si ambas $p$ y $q$ son verdaderas.
• La disyunción de proposiciones $p$ y $q$ se denota por $p \lor q$ ("$p$ o $q$").
  • $p \lor q$ es falsa solo si ambas $p$ y $q$ son falsas.
• La implicación de proposiciones $p$ y $q$ se denota por $p \implies q$ ("si $p$, entonces $q$").
  • En $p \implies q$, $p$ es la hipótesis (antecedente) y $q$ es la conclusión (consecuente).
  • $p \implies q$ es falsa solo si $p$ es verdadera y $q$ es falsa.

Capítulo 2: Espacios Vectoriales - Definiciones

• Un espacio vectorial es un conjunto no vacío $V$ de vectores con operaciones de suma y multiplicación escalar, cumpliendo diez axiomas.
• Axioma 1: Si $\mathbf{u}$ y $\mathbf{v}$ están en $V$, entonces $\mathbf{u} + \mathbf{v}$ está en $V$ (cerradura bajo la suma).
• Axioma 2: $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$ (conmutatividad).
• Axioma 3: $\mathbf{u} + (\mathbf{v} + \mathbf{w}) = (\mathbf{u} + \mathbf{v}) + \mathbf{w}$ (asociatividad).
• Axioma 4: Existe un vector $\mathbf{0}$ en $V$ tal que $\mathbf{u} + \mathbf{0} = \mathbf{u}$ para todo $\mathbf{u}$ en $V$ (existencia del vector cero).
• Axioma 5: Para cada $\mathbf{u}$ en $V$, existe $-\mathbf{u}$ en $V$ tal que $\mathbf{u} + (-\mathbf{u}) = \mathbf{0}$ (existencia del inverso aditivo).
• Axioma 6: Si $k$ es un escalar y $\mathbf{u}$ está en $V$, entonces $k\mathbf{u}$ está en $V$ (cerradura bajo la multiplicación escalar).
• Axioma 7: $k(\mathbf{u} + \mathbf{v}) = k\mathbf{u} + k\mathbf{v}$ (distributividad con respecto a la suma de vectores).
• Axioma 8: $(k + l)\mathbf{u} = k\mathbf{u} + l\mathbf{u}$ (distributividad con respecto a la suma de escalares).
• Axioma 9: $k(l\mathbf{u}) = (kl)\mathbf{u}$ (asociatividad con respecto a la multiplicación escalar).
• Axioma 10: $1\mathbf{u} = \mathbf{u}$ (elemento neutro multiplicativo).
• Una combinación lineal de vectores $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n$ es cualquier vector de la forma $k_1\mathbf{v}_1 + k_2\mathbf{v}_2 + \dots + k_n\mathbf{v}_n$, donde los $k_i$ son escalares.
• El espacio generado por $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n$ es el conjunto de todas las combinaciones lineales de estos vectores.
• Un subespacio $H$ de un espacio vectorial $V$ es un subconjunto de $V$ que cumple tres condiciones:
  • El vector cero de $V$ está en $H$.
  • $H$ es cerrado bajo la suma de vectores.
  • $H$ es cerrado bajo la multiplicación por escalares.
• El espacio generado por $\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n$ es un subespacio de $V$.
• Un conjunto de vectores $S = {\mathbf{v}_1, \mathbf{v}_2, \dots, \mathbf{v}_n}$ es linealmente independiente si la ecuación $k_1\mathbf{v}_1 + k_2\mathbf{v}_2 + \dots + k_n\mathbf{v}_n = \mathbf{0}$ tiene únicamente la solución trivial ($k_1 = k_2 = \dots = k_n = 0$).
• Si existen escalares $k_1, k_2, \dots, k_n$ no todos cero tales que $k_1\mathbf{v}_1 + k_2\mathbf{v}_2 + \dots + k_n\mathbf{v}_n = \mathbf{0}$, entonces $S$ es un conjunto linealmente dependiente.

Teoría Algorítmica de Juegos

• La Teoría Clásica de Juegos está orientada a la economía, asume jugadores racionales e ignora cuestiones computacionales.
• El Diseño de Algoritmos está orientado a la eficiencia, con objetivos bien definidos y control centralizado.
• Teoría Algorítmica de Juegos = Teoría de Juegos + Diseño de Algoritmos.

Metas principales

• Diseñar algoritmos para juegos que calculen conceptos de solución teórica de juegos (como los equilibrios de Nash).
• Diseñar juegos para implementar un buen comportamiento social.

Ejemplo 1: La Paradoja de Braess

• En una red de carreteras, los conductores buscan minimizar su tiempo de viaje de S a T.
• Un equilibrio del usuario (User Equilibrium) es un flujo donde ningún conductor tiene incentivos para desviarse unilateralmente a otra ruta.
• Añadir una nueva carretera puede empeorar el tiempo de viaje de todos los conductores en el equilibrio del usuario.
• Si hay 100 conductores, inicialmente el tiempo de viaje es 1, pero después de añadir la nueva carretera, el tiempo de viaje aumenta a 1.5.

Ejemplo 2: El problema de la secretaria

• $n$ solicitantes aparecen en un orden aleatorio, se entrevista a cada uno en orden.
• Se debe aceptar o rechazar a un solicitante inmediatamente.
• Solo se conoce el rango relativo de los solicitantes.
• El éxito es aceptar al mejor solicitante.
• Estrategia: Rechazar los primeros $n/e$ solicitantes, luego aceptar al siguiente solicitante que sea mejor que todos los anteriores.
• Esta estrategia selecciona al mejor solicitante con una probabilidad de al menos $1/e \approx 37%$.