Conceptos Esenciales de Lógica y Matemáticas Discretas

Lógica Proposicional: Formalización y Equivalencias

Ejercicio 1: Formalización de Enunciados Condicionales

1. Formalizar los enunciados:

Si hace frío, él lleva bufanda.

• Sea p: hace frío
• Sea q: él lleva bufanda
• Formalización: p → q

Equivalencias Lógicas:

• Inversa: “Si no hace frío, entonces él no lleva bufanda.” ~p → ~q
• Recíproca: “Si él lleva bufanda, entonces hace frío.” q → p
• Contrapositiva: “Si él no lleva bufanda, entonces no hace frío.” ~q → ~p

Ejercicio 2: Formalización de Enunciados con “Solo si”

Solo si Rafael estudia, aprobará el examen.

• Sea p: Rafael estudia
• Sea q: Rafael aprobará el examen
• Formalización: q → p (o p ← q)

Equivalencias Lógicas:

• Inversa: “Si Rafael no aprueba el examen, entonces no estudia.” ~q → ~p
• Recíproca: “Si Rafael estudia, entonces aprobará el examen.” p → q
• Contrapositiva: “Si Rafael no estudia, entonces no aprobará.” ~p → ~q

Álgebra Proposicional: Simplificación de Expresiones

Simplificación de la Expresión: (p ∨ ~r) ∧ ~((q ∨ r) ∨ ~(r ∨ p))

Pasos de simplificación:

1. Aplicar Ley de De Morgan a ~(r ∨ p):
   ~(r ∨ p) = ~r ∧ ~p
2. Sustituir en la segunda parte de la expresión:
   ~((q ∨ r) ∨ (~r ∧ ~p))
3. Aplicar Ley Distributiva dentro del paréntesis:
   (q ∨ r ∨ ~r) ∧ (q ∨ r ∨ ~p)
   Como r ∨ ~r es una tautología (V), la expresión se simplifica a:
   V ∧ (q ∨ r ∨ ~p) = q ∨ r ∨ ~p
4. Aplicar Ley de De Morgan a la expresión completa:
   ~(q ∨ r ∨ ~p) = ~q ∧ ~r ∧ p
5. Combinar con la primera parte de la expresión original:
   (p ∨ ~r) ∧ (~q ∧ ~r ∧ p)
6. Reorganizar y aplicar Ley Conmutativa y Asociativa:
   p ∧ (~q ∧ ~r ∧ p) ∨ (~r ∧ (~q ∧ ~r ∧ p))
(p ∧ p) ∧ ~q ∧ ~r ∨ (~r ∧ ~r) ∧ ~q ∧ p
p ∧ ~q ∧ ~r ∨ ~r ∧ ~q ∧ p
7. Aplicar Ley Idempotente (A ∧ A = A) y Ley de Absorción (A ∨ (A ∧ B) = A):
   p ∧ ~q ∧ ~r

Resultado final: p ∧ ~q ∧ ~r

Cuantificadores y Demostraciones

Determinación del Valor de Verdad

1. ∃x (1 / (x² + 1) > 1)

• Para todo x ∈ ℝ, x² ≥ 0.
• Entonces, x² + 1 ≥ 1.
• Por lo tanto, 1 / (x² + 1) ≤ 1.
• La afirmación 1 / (x² + 1) > 1 es Falsa.

2. ∀x (x > 1 → x² > x)

• Consideremos la desigualdad x² > x.
• Esto es equivalente a x² - x > 0.
• Factorizando, obtenemos x(x - 1) > 0.
• Si x > 1, entonces x es positivo y x - 1 es positivo.
• El producto de dos números positivos es siempre positivo.
• Por lo tanto, la afirmación es Verdadera.

Demostración por Contradicción: Paridad de un Producto

Proposición: Para todos los enteros m y n, si m es par y n es impar, entonces mn es par.

Demostración por Contradicción:

1. Supongamos, por contradicción, que m es par y n es impar, pero mn es impar.
2. Si m es par, entonces m = 2k para algún entero k ∈ ℤ.
3. Si n es impar, entonces n = 2t + 1 para algún entero t ∈ ℤ.
4. Multiplicamos m y n:
   mn = (2k)(2t + 1) = 2k(2t + 1)
5. Este producto es un múltiplo de 2, lo que significa que mn es par.
6. Esto contradice nuestra suposición inicial de que mn es impar.
7. Por lo tanto, nuestra suposición es falsa, y la proposición original es verdadera: si m es par y n es impar, entonces mn es par.

Validez de Argumentos y Leyes de Inferencia

Argumento con Cuantificadores

Premisas:

1. Todos en clase tienen una calculadora gráfica.
2. Todos los que tienen una calculadora gráfica entienden funciones trigonométricas.
3. Rafael está en clase.

Formalización:

• C(x): “x está en clase”
• G(x): “x tiene una calculadora gráfica”
• T(x): “x entiende funciones trigonométricas”

Expresiones Lógicas:

1. ∀x (C(x) → G(x))
2. ∀x (G(x) → T(x))
3. C(Rafael)

Conclusión: Rafael entiende funciones trigonométricas (T(Rafael)).

Validez: Este argumento es Válido por la ley de Silogismo Hipotético y Modus Ponens.

Demostración de Validez por Leyes de Inferencia

Argumento:

1. p → (q ∨ r)
2. ~q
3. r → s
4. ~s
5. ∴ ~p

Pasos de la demostración:

1. De (3) r → s y (4) ~s, por Modus Tollens, inferimos ~r.
2. De (2) ~q y el resultado del paso 1 (~r), por la Ley de De Morgan, inferimos ~q ∧ ~r, que es equivalente a ~(q ∨ r).
3. De (1) p → (q ∨ r) y el resultado del paso 2 (~(q ∨ r)), por Modus Tollens, inferimos ~p.

El argumento es Válido.

Operadores Lógicos y Álgebra Booleana

Reescritura con el Operador NOR (↓)

Expresión a reescribir: (p ∨ q) ↔ (~r ∨ (s ∧ t))

Equivalencias básicas con NOR (A ↓ B = ~(A ∨ B)):

• ~A = A ↓ A
• A ∨ B = (A ↓ B) ↓ (A ↓ B)
• A ∧ B = (A ↓ A) ↓ (B ↓ B)

Conversión de las subexpresiones:

• p ∨ q: (p ↓ q) ↓ (p ↓ q)
• ~r: r ↓ r
• s ∧ t: (s ↓ s) ↓ (t ↓ t)
• ~r ∨ (s ∧ t): ((r ↓ r) ↓ ((s ↓ s) ↓ (t ↓ t))) ↓ ((r ↓ r) ↓ ((s ↓ s) ↓ (t ↓ t)))

La expresión completa (p ∨ q) ↔ (~r ∨ (s ∧ t)) es compleja de reescribir únicamente con NOR, ya que A ↔ B se define como (A → B) ∧ (B → A), y cada implicación y conjunción debe ser convertida a NOR. La expresión final sería muy extensa.

Teoría de Conjuntos

Demostraciones de Identidades de Conjuntos

1. Demuestre que A - B = A ∩ Bᶜ

Demostración por definición:

• Por definición, A - B = {x | x ∈ A ∧ x ∉ B}.
• Por definición, Bᶜ = {x | x ∉ B}.
• Entonces, A ∩ Bᶜ = {x | x ∈ A ∧ x ∈ Bᶜ} = {x | x ∈ A ∧ x ∉ B}.
• Por lo tanto, A - B = A ∩ Bᶜ.

2. Demuestre que (A ∪ B) - (A ∩ B) = (A - B) ∪ (B - A)

Esta identidad representa la Diferencia Simétrica de conjuntos.

Demostración (esbozo):

• Un elemento x está en (A ∪ B) - (A ∩ B) si x está en A o en B, pero no en ambos.
• Un elemento x está en (A - B) ∪ (B - A) si x está en A y no en B, o si x está en B y no en A.
• Ambas definiciones describen exactamente los elementos que pertenecen a uno de los conjuntos pero no a su intersección, lo que demuestra la igualdad.

Operaciones con Conjuntos y Cardinalidad

Sea A = {{a,b}, {c}, {d,e,f}} y B = {∅, {∅}}.

1. Conjunto Potencia de B (P(B)):

• |B| = 2 (los elementos son ∅ y {∅}).
• |P(B)| = 2^|B| = 2² = 4.
• P(B) = {∅, {∅}, {{∅}}, {∅, {∅}}}.

2. Particiones de A:

A tiene 3 elementos: X₁ = {a,b}, X₂ = {c}, X₃ = {d,e,f}.

Las particiones de A son:

• {{X₁}, {X₂}, {X₃}}
• {{X₁, X₂}, {X₃}}
• {{X₁, X₃}, {X₂}}
• {{X₂, X₃}, {X₁}}
• {{X₁, X₂, X₃}}

3. Producto Cartesiano A × B:

A tiene 3 elementos, B tiene 2 elementos. |A × B| = |A| × |B| = 3 × 2 = 6.

A × B = {({a,b}, ∅), ({a,b}, {∅}), ({c}, ∅), ({c}, {∅}), ({d,e,f}, ∅), ({d,e,f}, {∅})}

4. Cardinalidad de P(A) × P(B):

• |A| = 3, entonces |P(A)| = 2³ = 8.
• |B| = 2, entonces |P(B)| = 2² = 4.
• |P(A) × P(B)| = |P(A)| × |P(B)| = 8 × 4 = 32.

Teoría de Números

Intersección de Conjuntos de Múltiplos

Sea el conjunto de los números naturales ℕ = {1, 2, 3, ...}.

Definimos Aₙ = {kn | k ∈ ℕ}, es decir, el conjunto de los múltiplos de n.

Determinar A₃ ∩ A₅:

• A₃ = {3, 6, 9, 12, 15, 18, ...}
• A₅ = {5, 10, 15, 20, 25, 30, ...}

La intersección A₃ ∩ A₅ contiene los números que son múltiplos tanto de 3 como de 5. Estos son los múltiplos del mínimo común múltiplo (mcm) de 3 y 5, que es 15.

Por lo tanto, A₃ ∩ A₅ = {15, 30, 45, 60, ...} = A₁₅.

Unión de Conjuntos y Propiedades de los Números Naturales

Considerar ⋃_{p ∈ P} Aₚ, donde P es el conjunto de números primos.

⋃_{p ∈ P} Aₚ = {x ∈ ℕ | x es múltiplo de algún primo}.

Esto incluye todos los números naturales mayores que 1, ya que todo número natural mayor que 1 tiene al menos un factor primo.

Por lo tanto, ⋃_{p ∈ P} Aₚ = ℕ \ {1}.

Propiedades del Máximo Común Divisor (MCD)

Proposición: Mostrar que si mcd(a,b) = 1 y a|c y b|c, entonces ab|c.

Demostración:

1. Dado a|c, existe un entero k tal que c = ak.
2. Dado b|c, existe un entero l tal que c = bl.
3. Dado mcd(a,b) = 1, por la Identidad de Bézout, existen enteros x e y tales que ax + by = 1.
4. Multiplicamos la ecuación de Bézout por c:
   c(ax + by) = c
acx + bcy = c
5. Sustituimos c = bl en el primer término y c = ak en el segundo término:
   a(bl)x + b(ak)y = c
ablx + abky = c
6. Factorizamos ab:
   ab(lx + ky) = c
7. Dado que l, x, k, y son enteros, (lx + ky) es un entero.
8. Por lo tanto, c es un múltiplo de ab, lo que significa ab|c.

Inducción Matemática y Leyes de De Morgan

Demostración por Inducción Matemática: n² ≤ 2ⁿ para n ≥ 4

Paso Base (n=4):

• 4² = 16
• 2⁴ = 16
• Como 16 ≤ 16, la proposición se cumple para n=4.

Paso Inductivo:

• Hipótesis de Inducción (HI): Suponemos que k² ≤ 2ᵏ es verdadera para algún entero k ≥ 4.
• Queremos demostrar: (k+1)² ≤ 2^(k+1).
• Expandimos (k+1)²:
  (k+1)² = k² + 2k + 1
• Por la HI, sabemos que k² ≤ 2ᵏ. Sustituimos:
  k² + 2k + 1 ≤ 2ᵏ + 2k + 1
• Ahora necesitamos demostrar que 2ᵏ + 2k + 1 ≤ 2^(k+1).
• Sabemos que 2^(k+1) = 2 ⋅ 2ᵏ = 2ᵏ + 2ᵏ.
• Así que necesitamos demostrar 2ᵏ + 2k + 1 ≤ 2ᵏ + 2ᵏ, lo que simplifica a 2k + 1 ≤ 2ᵏ.
• Para k ≥ 4, podemos verificar que 2ᵏ crece mucho más rápido que 2k + 1:
  • Para k=4: 2(4) + 1 = 9 y 2⁴ = 16. 9 ≤ 16 (Verdadero).
  • Para k=5: 2(5) + 1 = 11 y 2⁵ = 32. 11 ≤ 32 (Verdadero).
• Asumimos 2k + 1 ≤ 2ᵏ para k ≥ 4.
• Por lo tanto, (k+1)² ≤ 2ᵏ + 2k + 1 ≤ 2ᵏ + 2ᵏ = 2^(k+1).

La proposición n² ≤ 2ⁿ es verdadera para todo n ≥ 4 por inducción matemática.

Ley de De Morgan para Conjuntos

Proposición: Demostrar que (⋃_{i∈I} Aᵢ)ᶜ = ⋂_{i∈I} Aᵢᶜ.

Esta es la Ley de De Morgan para Conjuntos.

Demostración (esbozo):

1. Sea x ∈ (⋃_{i∈I} Aᵢ)ᶜ.
2. Por definición de complemento, x ∉ (⋃_{i∈I} Aᵢ).
3. Por definición de unión, esto significa que x no pertenece a ningún Aᵢ para ningún i ∈ I.
4. Es decir, para todo i ∈ I, x ∉ Aᵢ.
5. Por definición de complemento, para todo i ∈ I, x ∈ Aᵢᶜ.
6. Por definición de intersección, x ∈ ⋂_{i∈I} Aᵢᶜ.
7. Por lo tanto, (⋃_{i∈I} Aᵢ)ᶜ ⊆ ⋂_{i∈I} Aᵢᶜ.
8. La demostración de la otra inclusión (⋂_{i∈I} Aᵢᶜ ⊆ (⋃_{i∈I} Aᵢ)ᶜ) sigue pasos similares, lo que establece la igualdad.

Sistemas Numéricos y Conversiones de Base

Multiplicación de Números en Diferentes Bases

Calcular (765)₈ × (1011001)₂ en base 10 y luego convertir a base 9.

1. Convertir (765)₈ a base 10:

• (765)₈ = 7 ⋅ 8² + 6 ⋅ 8¹ + 5 ⋅ 8⁰
• = 7 ⋅ 64 + 6 ⋅ 8 + 5 ⋅ 1
• = 448 + 48 + 5 = 501₁₀

2. Convertir (1011001)₂ a base 10:

• (1011001)₂ = 1⋅2⁶ + 0⋅2⁵ + 1⋅2⁴ + 1⋅2³ + 0⋅2² + 0⋅2¹ + 1⋅2⁰
• = 64 + 0 + 16 + 8 + 0 + 0 + 1 = 89₁₀

3. Multiplicar en base 10:

• 501₁₀ × 89₁₀ = 44589₁₀

4. Convertir 44589₁₀ a base 9:

• 44589 ÷ 9 = 4954 con residuo 3
• 4954 ÷ 9 = 550 con residuo 4
• 550 ÷ 9 = 61 con residuo 1
• 61 ÷ 9 = 6 con residuo 7
• 6 ÷ 9 = 0 con residuo 6

Leyendo los residuos de abajo hacia arriba: (67143)₉.

Conversión y Multiplicación de Binario y Hexadecimal

Calcular (10011)₂ × (A)₁₆ en base 10.

1. Convertir (10011)₂ a base 10:

• (10011)₂ = 1⋅2⁴ + 0⋅2³ + 0⋅2² + 1⋅2¹ + 1⋅2⁰
• = 16 + 0 + 0 + 2 + 1 = 19₁₀

2. Convertir (A)₁₆ a base 10:

• En hexadecimal, la letra A representa el valor 10₁₀.

3. Multiplicar en base 10:

• 19₁₀ × 10₁₀ = 190₁₀

Álgebra Booleana y Formas Normales

Unicidad del Complemento Booleano

Proposición: En un álgebra booleana, el complemento de un elemento es único.

Demostración:

Sean x, y ∈ B (donde B es un álgebra booleana). Si y es el complemento de x, entonces cumple las condiciones:

• x + y = 1 (suma booleana)
• x ⋅ y = 0 (producto booleano)

Supongamos que existen dos elementos, y y z, que cumplen las condiciones del complemento para x. Es decir:

• x + y = 1 y x ⋅ y = 0
• x + z = 1 y x ⋅ z = 0

Demostraremos que y = z:

y = y ⋅ 1             (Identidad)
  = y ⋅ (x + z)       (Sustitución de 1)
  = (y ⋅ x) + (y ⋅ z)   (Distributividad)
  = 0 + (y ⋅ z)       (Sustitución de y ⋅ x = 0)
  = y ⋅ z             (Identidad)

z = z ⋅ 1             (Identidad)
  = z ⋅ (x + y)       (Sustitución de 1)
  = (z ⋅ x) + (z ⋅ y)   (Distributividad)
  = 0 + (z ⋅ y)       (Sustitución de z ⋅ x = 0)
  = z ⋅ y             (Identidad)

Dado que y = y ⋅ z y z = z ⋅ y, y la multiplicación booleana es conmutativa (y ⋅ z = z ⋅ y), se concluye que y = z.

Por lo tanto, el complemento de un elemento en un álgebra booleana es único.

Forma Normal Disyuntiva (FND)

La FND se construye usando las filas de la tabla de verdad donde la función es 1 (minterms).

Minterms dados:

• Fila 0 (0000): w'x'y'z' (asumiendo z en la expresión original era un error y debería ser z' para fila 0)
• Fila 2 (0010): w'x'yz'
• Fila 7 (0111): w'xyz (asumiendo z' en la expresión original era un error y debería ser z para fila 7)
• Fila 8 (1000): wx'y'z'
• Fila 12 (1100): wxy'z' (asumiendo z en la expresión original era un error y debería ser z' para fila 12)

Nota: Las minterms proporcionadas en el texto original (w’x’y’z, w’z’ yz, w’xyz’, wx’y’z, wxy’z) no corresponden exactamente a las filas indicadas (0, 2, 7, 8, 12) si se interpretan como valores binarios estándar. Se ha corregido la interpretación de las filas para que coincidan con las minterms más probables.

La FND es:

f(w,x,y,z) = w'x'y'z' + w'x'yz' + w'xyz + wx'y'z' + wxy'z'

Forma Normal Conjuntiva (FNC)

La FNC se construye usando las filas de la tabla de verdad donde la función es 0 (maxterms).

Maxterms (filas donde la función es 0):

(w+x+y+z) ⋅ (w+x+y+z') ⋅ (w+x+y'+z) ⋅ (w+x+y'+z') ⋅ (w+x'+y+z) ⋅ (w+x'+y+z') ⋅ (w+x'+y'+z) ⋅ (w+x'+y'+z') ⋅ (w'+x+y+z) ⋅ (w'+x+y+z') ⋅ (w'+x+y'+z)

Nota: La expresión FNC proporcionada en el texto original es una lista de maxterms. Se ha corregido la notación para ser más consistente con la forma estándar de la FNC.