Conceptos Fundamentales de Lógica, Conjuntos y Álgebra

Conceptos Fundamentales de Lógica, Conjuntos y Álgebra

Lógica Proposicional

• Una argumentación es inválida si y solo si existen asignaciones de valores de verdad a las variables de enunciado de forma que las premisas sean "V" y la conclusión sea "F".
• Una forma enunciativa es contradicción si siempre alcanza el valor falso para cualquier asignación de valores de verdad que damos a las variables de enunciado que intervienen.
• Una forma enunciativa es una expresión formada por una variable de enunciado, una variable de enunciado negada o varias variables de enunciado.
• Conjunción básica: es una forma enunciativa que tiene un único caso verdadero en su tabla de verdad, cuya expresión es de la forma: p1 ∧ p2 ∧ … ∧ pn.
• Forma Normal Conjuntiva: dada una forma enunciativa que no sea tautología, llamaremos forma normal conjuntiva a la forma enunciativa lógicamente equivalente que nos sale al hacer la conjunción de todas las disyunciones básicas asociadas a los falsos en la tabla de verdad.
• Forma Normal Disyuntiva: dada una forma enunciativa que no sea contradicción, llamaremos forma normal disyuntiva a la forma enunciativa lógicamente equivalente que nos sale al hacer la disyunción de todas las conjunciones básicas asociadas a los verdaderos en la tabla de verdad.
• Equivalencia lógica: dos formas enunciativas son lógicamente equivalentes si tienen la misma tabla de verdad o A ↔ B es tautológico. Si A y B son idénticos, A ↔ B es tautológico, entonces A es lógicamente equivalente a B.
• Refutación: comprobar si existe una combinación de valores de verdad que haga verdaderas las premisas y falsa la conclusión a la vez. Si es posible, será inválida; si no es posible, será válida.
• Implicación lógica: A implica lógicamente a B si A → B es tautológico, por lo que A implica lógicamente a B, es decir, B es consecuencia lógica de A.

Teoría de Conjuntos y Relaciones

• Llamaremos conjunto cociente de X por la relación R, y lo notaremos por X/R, al conjunto de todas las clases de equivalencia en X determinadas por R: X/R = {ā / a ∈ X}.
• Una relación binaria R en X se dice que es una relación de equivalencia si verifica simultáneamente las propiedades reflexiva, simétrica y transitiva.
• 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.
• Una correspondencia f: X → Y se dice que es una aplicación cuando todo elemento de X tiene una y solo una imagen en Y: ∀a ∈ X, ∃!b ∈ Y tal que f(a) = b.
• Dada una aplicación f: X → Y, diremos que es:
  • A) Inyectiva si cada elemento de Y es imagen a lo más de un elemento de X, es decir, x ≠ x’ ⇒ f(x) ≠ f(x’), (equiv. f(x) = f(x’) ⇒ x = x’).
  • B) Sobreyectiva si todo elemento de Y es imagen al menos de un elemento de X, ∀b ∈ Y, ∃a ∈ X tal que f(a) = b.
  • C) Biyectiva si es inyectiva y sobreyectiva a la vez, ∀b ∈ Y, ∃!a ∈ X tal que f(a) = b.
• Dada una aplicación f: X → Y (es decir, f = (X, Y, G)) existe una correspondencia de Y en X, f^-1 = (Y, X, G_inv), de manera que (b, a) ∈ G_inv si y solo si (a, b) ∈ G. Además, si f es biyectiva, entonces f^-1 es una aplicación, también biyectiva, que se llama inversa de f.
• Sea X un conjunto. Llamamos relación binaria en X a todo subconjunto R del producto cartesiano X × X, es decir, R ⊆ X × X.
• Sea X un conjunto ordenado por una relación de orden R y A ⊆ X:
  • Diremos que A está acotado inferiormente si existe un y ∈ X tal que y ≤ a para todo a ∈ A. A tal elemento y se le llama cota inferior de A.
  • Diremos que A está acotado superiormente si existe un x ∈ X tal que a ≤ x para todo a ∈ A. A tal elemento x se le llama cota superior de A.
• Sea A ⊆ X. Llamaremos supremo de A, sup(A), al mínimo (si existe) del conjunto de cotas superiores de A. Llamaremos ínfimo de A, inf(A), al máximo (si existe) del conjunto de cotas inferiores de A.
• 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. Un elemento y ∈ X se dice minimal en X si la relación b ≤ y para algún b ∈ X, implica que y = b.
• Se dice que un elemento m ∈ A es el máximo de A si es una cota superior de A. De igual forma, un elemento n ∈ A es el mínimo de A si es una cota inferior de A.

Estructuras Algebraicas

• Un retículo es una terna (L, ∨, ∧) donde L ≠ ∅ es un conjunto y ∨, ∧ son dos operaciones internas en L verificando las propiedades:
  • 1. Asociativas, (a ∨ b) ∨ c = a ∨ (b ∨ c), (a ∧ b) ∧ c = a ∧ (b ∧ c), ∀a, b, c ∈ L.
  • 2. Conmutativas, a ∨ b = b ∨ a, a ∧ b = b ∧ a, ∀a, b ∈ L.
  • 3. Idempotencia, a ∨ a = a, a ∧ a = a, ∀a ∈ L.
  • 4. Absorción, a ∨ (a ∧ b) = a, a ∧ (a ∨ b) = a, ∀a, b ∈ L.
• Una terna (L, ∨, ∧) es un álgebra de Boole si satisface las propiedades asociativas, conmutativas, existencia de elemento neutro y complementarios, y distributivas.
• 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), ∪, ∩).
• Sea (L, ∨, ∧) un álgebra de Boole. Un elemento a ≠ 0 en L se llama átomo si verifica: ∀x ∈ L, x ∧ a = a (a ≤ x) o bien x ∧ a = 0, es decir, si es un elemento minimal de L – {0}.
• Un elemento a ≠ 0 en X es una unidad en X si tiene inverso (elemento simétrico para el producto), es decir, si existe otro elemento b ≠ 0 en X tal que a ⋅ b = b ⋅ a = 1. Diremos que X es un cuerpo si todo elemento no nulo de X es una unidad.

Teoría de Números y Complejidad

• Teorema Fundamental de la Numeración: Sea b ≥ 2, un número entero. Cualquier entero positivo n se puede escribir de forma única en base b como: n = d_kb^k + ... + d₂b² + d₁b¹ + d₀b⁰ con d_i ∈ ℕ y 0 ≤ d_i < b, ∀i = 0,1,...,k. Para abreviar escribiremos n = (d_k d_k-1 ... d₁ d₀)_b.
• Teorema Chino del Resto: Sean a₁, a₂,..., a_n ∈ ℤ y p₁, p₂,..., p_n ∈ ℤ tales que (p_i, p_j) = 1 si i ≠ j. Entonces:
  • i) Existe a ∈ ℤ tal que a ≡ a_i mod p_i, ∀i = 1,2,...,n.
  • ii) Si ∃a’ ∈ ℤ tal que a’ ≡ a_i mod p_i, ∀i = 1,2,...,n, ⇒ a ≡ a’ mod (p₁⋅p₂...p_n).
• Algoritmo Chino del Resto: Consideremos el sistema de congruencias: x ≡ a₁ mod p₁, x ≡ a₂ mod p₂, ..., x ≡ a_r mod p_r, tal que (p_i, p_j) = 1 si i ≠ j, entonces el teorema anterior nos asegura que dicho sistema tiene solución.
  • Paso 1: Llamamos M₁ = 1, M₂ = p₁, M₃ = p₁⋅p₂, ..., M_r = p₁⋅p₂...p_r-1.
  • Paso 2: Hallamos u_k ∈ ℤ tal que u_k⋅M_k ≡ 1 mod p_k, ∀k = 1,2,...,r.
  • Paso 3: Hallamos b₁ ∈ ℤ tal que b₁ ≡ a₁ mod p₁.
  • Paso 4: Hallamos w₂ ∈ ℤ tal que w₂ ≡ (a₂ – b₁)⋅u₂ mod p₂.
  • Paso 5: Hallamos b₂ = b₁ + w₂⋅M₂.
  • Paso 4bis: ∀k ≥ 3 calculamos w_k ∈ ℤ tal que w_k ≡ (a_k – b_k-1)⋅u_k mod p_k.
  • Paso 5bis: ∀k ≥ 3 calculamos b_k = b_k-1 + w_k⋅M_k.
  • Paso 6: La solución del sistema es x = b_r.
• Teorema de caracterización de ecuaciones diofánticas solubles: Sean a, b, c ∈ ℤ - {0} y d = (a, b). Entonces la ecuación ax + by = c admite solución en ℤ si y solo si d | c.
• La complejidad en tiempo se describe en términos del número de operaciones requeridas, en lugar del tiempo de cálculo real, ya que distintos ordenadores necesitan tiempos diferentes para realizar la misma operación básica.
• Un problema que se puede resolver utilizando un algoritmo con complejidad polinómica en el peor caso se dice tratable, pues se espera que el algoritmo nos dé la solución para una entrada de tamaño razonable en un tiempo relativamente corto.

Funciones Booleanas y Circuitos Lógicos

• A cualquier aplicación f: (B²)ⁿ → B² la llamaremos función booleana elemental de n variables o puerta lógica de n entradas.
• El conjunto {1, ⊕ = XOR, AND} es funcionalmente completo y la síntesis de cualquier función booleana elemental a partir de estas puertas lógicas se le llama polinomio de Gegalkine de la función.
• Un conjunto adecuado de conectivas es un conjunto tal que toda función de verdad puede representarse por medio de una forma enunciativa en la que sólo aparezcan conectivas de dicho conjunto.
• Llamamos circuito lógico a una aplicación f: (B²)ⁿ → (B²)^m que asocia cada nupla (x₁, x₂,..., x_n) en (B²)ⁿ a una mupla (z₁, z₂,..., z_m) en (B²)^m, es decir, f(x₁, x₂,..., x_n) = (z₁, z₂,..., z_m).