Elementos de Lógica y Matemática Discreta

Flashcards para repasar términos y conceptos clave de Lógica y Matemática Discreta.

Cuantificadores Anidados

Cuantificadores que analizan proposiciones con múltiples variables, como $orall x orall y P(x, y)$. Importante el orden.

Negación de Cuantificadores

Aplicación de las equivalencias de De Morgan para cuantificadores, como $
eg orall x P(x) ext{ es equivalente a } orall x
eg P(x)$.

Demostración por el Absurdo

Método que asume la falsedad de la tesis para llegar a una contradicción.

Inducción Matemática Fuerte

Técnica que asume que $P(j)$ es verdadera para todos los $1 ext{ a } k$ para demostrar $P(k+1)$.

Conjunto Potencia

Conjunto de todos los subconjuntos de un conjunto $A$, denotado como $ ext{P}(A)$.

Producto Cartesiano

Conjunto de pares ordenados de elementos de dos conjuntos, definido como $A imes B = ext{((a, b) : a in A and b in B)}$.

Identidades de Conjuntos

Igualdades demostradas mediante la inclusión doble de conjuntos.

Algoritmo de Euclides

Método iterativo para calcular el máximo común divisor (mcd) de dos números.

Identidad de Bézout

Existencia de enteros $s$ y $t$ tales que $mcd(a, b) = as + bt$.

Relación de Congruencia

$a ext{ es congruente a } b ext{ módulo } n$ significa que $n | (a - b)$.

Teorema del Resto Chino

Método para resolver sistemas de congruencias con módulos coprimos.

Relaciones de Equivalencia

Relaciones que son reflexivas, simétricas y transitivas.

Cierre Transitivo

Relación que representa la conectividad en grafos, introduciendo la transitividad.

Minimales y Maximales en Posets

Elementos que no tienen otros elementos por debajo (mínimos) o por encima (máximos).

Álgebra de Boole

Estructura algebraica que trata con valores de verdad y operaciones lógicas.

Notación Asintótica

Método para describir el comportamiento asintótico de funciones, como $O(n), heta(n)$.

Complejidad del Peor Caso

Análisis que considera el escenario más desfavorable para evaluar el rendimiento de un algoritmo.