Conceptos Fundamentales de Álgebra, Teoría de Números y Lógica Matemática

Conceptos Fundamentales en Álgebra y Teoría de Números

Álgebra de Boole y Retículos

Teorema de Estructura de las Álgebras de Boole Finitas

Sea (L, ∨, ∧) un álgebra de Boole finita y M el conjunto de todos los átomos de L. Entonces L es isomorfo al álgebra de Boole (P(M), ∪, ∩).

Retículo

Un retículo es una terna (L, ∨, ∧) donde L ≠ ∅ es un conjunto y ∨, ∧ son dos operaciones internas en L verificando las propiedades:

• Asociativas
• Conmutativas
• De Idempotencia
• De Absorción

Teoría de Números y Notación Asintótica

Teorema Chino del Resto

Sean a₁, a₂, ..., aₙ ∈ ℤ y p₁, p₂, ..., pₙ ∈ ℤ tales que (pᵢ, pⱼ) = 1 si i ≠ j. Entonces:

1. Existe a ∈ ℤ tal que a ≡ aᵢ mod pᵢ, para todo i = 1, 2, ..., n.
2. Si existe a' ∈ ℤ tal que a' ≡ aᵢ mod pᵢ, para todo i = 1, 2, ..., n, entonces a ≡ a' mod (p₁ ⋅ p₂ ⋅ ... ⋅ pₙ).

Notación O Grande (Big O)

Decimos que f(x) es O(g(x)) si y solo si existen constantes c y k tales que |f(x)| ≤ c|g(x)| para todo x > k.

Ecuaciones Diofánticas

Una ecuación diofántica es una ecuación de la forma: ax + by = c donde a, b, c ∈ ℤ \ {0} y las soluciones son enteras.

Teorema de Caracterización (Ecuaciones Diofánticas)

Sean a, b, c en ℤ \ {0} y d = m.c.d.(a, b). Entonces la ecuación ax + by = c admite solución en ℤ si y solo si d | c; es decir, si existe k ∈ ℤ tal que c = d ⋅ k.

Conceptos de Teoría de Conjuntos y Relaciones

Elementos en Conjuntos Ordenados

Maximal

Sea X un conjunto ordenado. Un elemento x ∈ X se dice maximal de X si la relación x ≤ a, para algún a ∈ X, implica que x = a.

Minimal

Sea X un conjunto ordenado. Un elemento y ∈ X se dice minimal en X si la relación b ≤ y, para algún b ∈ X, implica que y = b.

Cotas Inferiores

Sea A ⊆ X. Un elemento b ∈ X es una cota inferior de A si, para todo a ∈ A, se cumple que a ≥ b.

Cotas Superiores

Sea A ⊆ X. Un elemento b ∈ X es una cota superior de A si, para todo a ∈ A, se cumple que a ≤ b.

Supremo

Sea A ⊆ X. Llamaremos supremo de A, denotado como sup(A), al mínimo (si existe) del conjunto de cotas superiores de A.

Ínfimo

Sea A ⊆ X. Llamaremos ínfimo de A, denotado como inf(A), al máximo (si existe) del conjunto de cotas inferiores de A.

Relaciones y Aplicaciones

Correspondencia

Sean X e Y conjuntos. Una correspondencia entre X e Y es una terna (X, Y, G) donde G ⊆ X × Y. Al conjunto X se le llama conjunto inicial, al conjunto Y se le llama conjunto final y a G se le llama grafo o gráfica de la correspondencia.

Conjunto Cociente

Sea R una relación de equivalencia en X. Llamaremos conjunto cociente de X por la relación R, y lo denotaremos por X/R, al conjunto de todas las clases de equivalencia en X determinadas por R: X/R = {ā | a ∈ X }.

Clase de Equivalencia

Dada R una relación de equivalencia sobre un conjunto X y a ∈ X, definimos la clase de equivalencia de a como el subconjunto de X formado por todos los elementos b ∈ X tales que a R b.

Aplicación (Función)

Una correspondencia f: X → Y se dice que es una aplicación (o función) cuando todo elemento de X tiene UNA Y SOLO UNA imagen en Y: para todo a ∈ X, existe un único b ∈ Y tal que f(a) = b.

Aplicación Inyectiva (Inyección)

Una aplicación f: X → Y es inyectiva si cada elemento de Y es imagen a lo más de un elemento de X; es decir, si x ≠ x' implica f(x) ≠ f(x'), o equivalentemente, si f(x) = f(x') implica x = x'.

Aplicación Sobreyectiva (Sobreyeción)

Una aplicación f: X → Y es sobreyectiva si todo elemento de Y es imagen de al menos un elemento de X; es decir, para todo b ∈ Y, existe un a ∈ X tal que f(a) = b.

Identidades Lógicas Fundamentales

1. A ∨ B ⇔ (¬A) → B
2. A ∧ B ⇔ ¬(A → (¬B))
3. A → B ⇔ (¬A) ∨ B
4. A → B ⇔ ¬(A ∧ (¬B))
5. A ↔ B ⇔ (A → B) ∧ (B → A)
6. A ↔ B ⇔ ¬(A ⊕ B)
7. A ⊕ B ⇔ ¬(A ↔ B)
8. A ⊕ B ⇔ (A ∨ B) ∧ (¬(A ∧ B))
9. A ∧ B ⇔ ¬((¬A) ∨ (¬B))
10. A ∨ B ⇔ ¬((¬A) ∧ (¬B))
11. A ↑ B ⇔ ¬(A ∧ B)
12. A ↓ B ⇔ ¬(A ∨ B)
13. (¬A) ⇔ (A ↑ A) ⇔ (A ↓ A)
14. ¬(¬A) ⇔ A
15. ¬A ⇔ 1 ⊕ A