Posgrado
  1. Introducción al análisis real  1.1. Teoría de conjuntos y lógica en el análisis real  1.1.1. Conjuntos y operaciones en teoría de conjuntos y lógica en análisis real  1.1.2. Relaciones y funciones  1.1.3. Lógica y cuantificadores  1.1.4. Cardinalidad de conjuntos  1.2. Espacio métrico  1.2.1. Introducción a conjuntos abiertos y cerrados en espacios métricos  1.2.2. Convergencia de secuencias en un espacio métrico  1.2.3. Función continua en un espacio métrico  1.2.4. Compacidad y completitud en espacios métricos en análisis real  1.3. Secuencias y series  1.3.1. Convergencia de secuencias  1.3.2. Series infinitas  1.3.3. Convergencia uniforme  1.3.4. Serie de potencias  1.4. Discriminación  1.4.1. Teorema del valor medio  1.4.2. Serie de Taylor  1.4.3. Funciones de varias variables  1.4.4. Derivada parcial  1.5. Integración  1.5.1. Integración de Riemann y Lebesgue  1.5.2. Integrales impropias  1.5.3. Teoría de la medida: una herramienta fundamental en la integración  1.5.4. Teorema de Fubini  1.6. Análisis funcional  1.6.1. Comprendiendo los espacios de Banach  1.6.2. Espacios de Hilbert  1.6.3. Operadores en espacios  1.6.4. Teoría espectral
  2. Álgebra abstracta  2.1. Entendiendo los grupos en el álgebra abstracta  2.1.1. Definiciones y ejemplos de grupos en álgebra abstracta  2.1.2. Homomorfismos de grupos  2.1.3. Introducción a los subgrupos normales  2.1.4. Teorema de Sylow  2.2. Anillos y campos  2.2.1. Ideales y anillos cociente  2.2.2. Extensiones de campos  2.2.3. Teoría de Galois  2.2.4. Anillos de polinomios  2.3. Introducción a los módulos en álgebra abstracta  2.3.1. Homomorfismo de módulos  2.3.2. Módulos libres  2.3.3. Introducción a los productos tensoriales  2.3.4. Secuencia exacta en módulos  2.4. Álgebra lineal  2.4.1. Espacio vectorial  2.4.2. Autovalores y autovectores  2.4.3. Espacio de producto interior  2.4.4. Diagonalización
  3. Topología  3.1. Topología general  3.1.1. Conjuntos abiertos y cerrados  3.1.2. Compacidad y conexión  3.1.3. Mapas continuos  3.1.4. Axioma de separación  3.2. Topología algebraica  3.2.1. Comprensión de los grupos fundamentales en la topología algebraica  3.2.2. Homotopía y homología  3.2.3. Complejo simplicial  3.2.4. Secuencias exactas en homología  3.3. Topología diferencial  3.3.1. Comprendiendo las variedades en topología diferencial  3.3.2. Funcionamiento suave  3.3.3. Espacio tangente y cotangente  3.3.4. Fibrados vectoriales
  4. Ecuaciones diferenciales  4.1. Ecuación diferencial ordinaria  4.1.1. Ecuaciones de primer orden  4.1.2. Ecuaciones lineales de segundo orden  4.1.3. Sistemas de ecuaciones diferenciales  4.1.4. Análisis de estabilidad en ecuaciones diferenciales ordinarias  4.2. Ecuaciones en derivadas parciales  4.2.1. Clasificación de EDP  4.2.2. Entendiendo las series de Fourier en ecuaciones diferenciales parciales  4.2.3. Introducción a las funciones de Green  4.2.4. Método de caracterización  4.3. Sistemas dinámicos en ecuaciones diferenciales  4.3.1. Teoría de la sostenibilidad  4.3.2. Ciclos límite en sistemas dinámicos  4.3.3. Teoría del caos  4.3.4. Teoría de bifurcación
  5. Probabilidad y estadística  5.1. Teoría de la probabilidad  5.1.1. Variables aleatorias  5.1.2. Distribuciones de probabilidad  5.1.3. Ley de los grandes números  5.1.4. Teorema del límite central  5.2. Inferencia estadística  5.2.1. Pruebas de hipótesis  5.2.2. Intervalo de confianza  5.2.3. Métodos bayesianos  5.2.4. Estimación de máxima verosimilitud  5.3. Procesos estocásticos  5.3.1. Cadenas de Markov  5.3.2. Movimiento browniano  5.3.3. Comprendiendo los procesos de Poisson  5.3.4. Martingalas: Un estudio integral en probabilidad y estadística
  6. Análisis numérico  6.1. Soluciones numéricas de ecuaciones  6.1.1. Descubrimiento original  6.1.2. Métodos iterativos  6.1.3. Análisis de convergencia  6.1.4. Cotas de error en soluciones numéricas de ecuaciones  6.2. Álgebra lineal numérica  6.2.1. Factorización de matrices  6.2.2. Cálculo de valores propios  6.2.3. Matrices dispersas  6.2.4. Técnicas de preacondicionamiento  6.3. Integración y diferenciación numérica  6.3.1. Métodos de cuadratura  6.3.2. Introducción a las diferencias finitas  6.3.3. Análisis de errores en la integración y diferenciación numérica  6.3.4. Métodos adaptativos en integración y diferenciación numérica
  7. Análisis complejo  7.1. Números complejos  7.1.1. Forma polar  7.1.2. Conjugados complejos  7.1.3. Forma exponencial de los números complejos  7.1.4. Raíces de la unidad  7.2. Funciones analíticas  7.2.1. Ecuaciones de Cauchy–Riemann  7.2.2. Series de potencias  7.2.3. Mapeo conforme  7.2.4. Funciones armónicas  7.3. Integración en el plano complejo  7.3.1. Teorema de Cauchy  7.3.2. Teorema del residuo  7.3.3. Integración de contornos  7.3.4. Transformaciones integrales
  8. Lógica matemática y fundamentos  8.1. Lógica proposicional  8.1.1. Tablas de verdad  8.1.2. Equivalencia lógica en la lógica proposicional  8.1.3. Técnicas de demostración en lógica proposicional  8.1.4. Solución en lógica proposicional  8.2. Lógica de predicados  8.2.1. Cuantificadores en lógica de predicados  8.2.2. Sistemas formales en lógica de predicados  8.2.3. Integridad y solidez  8.2.4. Teoría de modelos  8.3. Teoría de conjuntos  8.3.1. Cardinalidad y ordinalidad  8.3.2. Sistemas axiomáticos  8.3.3. Comprender la teoría de conjuntos de Zermelo-Fraenkel  8.3.4. Fuerzas en la teoría de conjuntos
  9. Personalización  9.1. Programación lineal  9.1.1. Método simplex  9.1.2. Dualidad en la programación lineal  9.1.3. Análisis de sensibilidad en programación lineal  9.1.4. Métodos de punto interior  9.2. Programación no lineal  9.2.1. Descenso de gradiente  9.2.2. Multiplicadores de Lagrange  9.2.3. Optimización convexa  9.2.4. Programación cuadrática  9.3. Optimización Combinatoria  9.3.1. Algoritmos de grafos  9.3.2. Programación entera  9.3.3. Flujo de red  9.3.4. Algoritmos de aproximación
  10. Matemáticas discretas  10.1. Teoría de grafos  10.1.1. Representación de grafos  10.1.2. Llanura y color  10.1.3. Algoritmo de camino más corto  10.1.4. Flujo de red  10.2. Compañerismo  10.2.1. Permutación y combinación  10.2.2. Función generadora  10.2.3. Relación de recurrencia  10.2.4. Comprendiendo el Principio de Inclusión-Exclusión  10.3. Criptografía  10.3.1. Aplicaciones de la teoría de números en criptografía  10.3.2. Criptografía Simétrica y Asimétrica  10.3.3. RSA y criptografía de curvas elípticas  10.3.4. Criptografía post-cuántica

Posgrado → Lógica matemática y fundamentos → Lógica proposicional ↓


Solución en lógica proposicional


La resolución es una regla fundamental de inferencia utilizada en la lógica proposicional y la demostración automática de teoremas. Juega un papel importante en la programación lógica y forma la base del lenguaje de programación Prolog. La técnica se basa en el principio de refutación, donde se prueba la imposibilidad de una proposición asumiendo su negación y obteniendo una contradicción. En lógica proposicional, la resolución se usa para derivar una conclusión resolviendo un conjunto de cláusulas.

Conceptos básicos de lógica proposicional

En la lógica proposicional, tratamos con proposiciones, que son afirmaciones que pueden ser verdaderas o falsas. Estas proposiciones se representan mediante variables proposicionales como p, q, r, etc. Las proposiciones combinadas se forman utilizando conectivos lógicos como Y (∧), O (∨), NO (¬), IMPLICA (→) y EQUIVALENTE (↔).

Un literal es una variable proposicional o la negación de una variable proposicional. Una cláusula es una disyunción de un literal. Por ejemplo, la cláusula (p ∨ ¬q ∨ r) contiene los literales p, ¬q y r.

El concepto central en la solución es la regla de solución, que nos permite deducir una nueva cláusula a partir de dos cláusulas existentes que contienen literales complementarios. Los literales complementarios son pares, como p y ¬p, que son negaciones entre sí.

Reglas de resolución

La regla de solución se puede expresar formalmente de la siguiente manera:

C1: (A ∨ X)
C2: (¬x ∨ b)
,
Respuesta: (A ∨ B)

Aquí, C1 y C2 son cláusulas que contienen letras x y ¬x, respectivamente. La cláusula (A ∨ B) es el resultado de resolver estas dos cláusulas sobre la letra x.

Considere el siguiente ejemplo:

C1: (p ∨ q)
C2: (¬q ∨ r)
,
Res: (P ∨ R)

En este caso, el literal q en C1 y ¬q en C2 están complementados. El resultado de la solución es (p ∨ r).

Forma normal conjuntiva (CNF)

Para utilizar la solución de manera efectiva, las proposiciones deben convertirse en una forma específica conocida como forma normal conjuntiva (CNF). Una fórmula está en CNF si es una conjunción de una o más cláusulas, donde cada cláusula es una disyunción de literales.

Convertir una fórmula lógica a CNF implica una serie de transformaciones de equivalencia:

  • Eliminar implicaciones y equivalencias utilizando equivalencias lógicas tales como: 
            p → q ≡ ¬p ∨ q
        p ↔ q ≡ (p → q) ∧ (q → p)
  • Mover los NOTs hacia adentro usando las leyes de De Morgan y la doble negación: 
            ¬(p ∧ q) ≡ ¬p ∨ ¬q
        ¬(p ∨ q) ≡ ¬p ∧ ¬q
        ¬¬P ≡ P
  • Distribuir el OR sobre el AND, asegurándose de que todas las cláusulas se conviertan en disyunciones de términos literales.

Ejemplo de conversión a CNF

Considere la fórmula: 

 (P → Q) → (Q → R)

Paso 1: Eliminar las implicaciones: 

 ¬(¬p∨q) ∨ (¬q∨r)

Paso 2: Aplicar las leyes de De Morgan: 

 (p ∧ ¬q) ∨ (¬q ∨ r)

Paso 3: Distribuir: 

 (p ∨¬q) ∧ (p ∨r)

Ahora, la fórmula está en CNF.

Ejemplo de solución en lógica proposicional

Consideremos un ejemplo de cómo la resolución puede utilizarse para resolver un problema lógico:

Se dan las siguientes afirmaciones:

  1. Si está lloviendo, entonces el suelo está húmedo. (R → W)
  2. Si el suelo está húmedo, el cielo está nublado. (W → C)
  3. No hay nubes en el cielo. (¬C)

Demuestre que no está lloviendo. (¬R)

Represente cada afirmación en CNF:

  • ¬R ∨ W (derivado de R → W)
  • ¬W ∨ C (derivado de W → C)
  • ¬C

Para probar ¬R, agregue la negación de la conclusión como una suposición y resuelva la contradicción:

Agregue R al conjunto.

Solución:

1. R
2.¬R ∨ W
3. ¬W ∨ C
4. ¬C

Resolve (1) R y (2) ¬R ∨ W: 

 5. W
Resuelva (5) W y (3) ¬W ∨ C: 
 6. C
(6) C contradice (4) ¬C. Por lo tanto, la suposición R debe ser falsa, por lo que ¬R es verdadera.

Propiedades de la resolución

La resolución tiene varias propiedades importantes que la hacen una herramienta poderosa en la demostración automática de teoremas:

  • Corrección: Si una cláusula surge de la regla de solución, entonces esa cláusula está lógicamente implicada por el conjunto inicial de cláusulas.
  • Completitud: Si un conjunto de cláusulas es insatisfacible (es decir, no pueden ser todas verdaderas al mismo tiempo), entonces la solución puede reflejar esa insatisfacción.
  • Refutación completa: Si se puede derivar una contradicción de un conjunto de cláusulas, entonces la solución eventualmente la encontrará.

Complejidad y limitaciones

Aunque la resolución es una técnica poderosa, es importante notar sus limitaciones:

  • Crecimiento exponencial: El espacio de posibles segmentos puede crecer exponencialmente en tamaño, volviendo las soluciones computacionalmente costosas para problemas grandes.
  • Restringido a CNF: Dado que la solución funciona en CNF, cualquier problema debe transformarse en esta forma, lo cual a veces puede implicar un gran número de cláusulas.

Representación visual de la resolución

Para aclarar más la solución, veamos una representación diagramática simple. Considere estas oraciones:

A (A ∨ B) ¬B
(A ∨ B) ¬B A

El paso de solución A combina (A ∨ B) y (¬B) para hacer una conjetura.

Estrategias de solución

En la práctica, se emplea una serie de estrategias y optimizaciones para utilizar la solución de manera eficiente. Estas estrategias buscan controlar el orden y método en el que se resuelven las cláusulas, a menudo basados en heurísticas o algoritmos específicos.

  • Solución unitaria: Esto implica priorizar bloques de letras individuales, conocidos como bloques unitarios, para simplificar y reducir rápidamente el tamaño del problema.
  • Resolución de entrada: asegura que la resolución se realice entre un segmento del conjunto original y un segmento derivado nuevo, reduciendo así la complejidad.
  • Estrategia de conjunto de apoyo: se enfoca en reducir el espacio de búsqueda resolviendo cláusulas solo dentro de un subconjunto específico, a menudo utilizados en la demostración interactiva de teoremas.

Aplicaciones en informática

La resolución es ampliamente utilizada en disciplinas de la informática, particularmente en áreas como inteligencia artificial y programación lógica. Sus principales aplicaciones incluyen:

  • Demostración automática de teoremas: Como técnica principal en sistemas de prueba y herramientas de razonamiento automático, la solución de pruebas ayuda a verificar la validez de afirmaciones lógicas.
  • Programación lógica: La teoría de la solución es la base de lenguajes como Prolog, donde se resuelven relaciones lógicas para formar preguntas computacionales.
  • Solucionadores de satisfacibilidad: Los solucionadores SAT modernos aplican estrategias basadas en la solución para determinar si se puede satisfacer una fórmula proposicional.

Conclusión

La resolución en lógica proposicional es un método robusto y atractivo para el razonamiento lógico. Al aprovechar el poder de la inferencia a través de la regla de resolución, provee un enfoque sistemático para probar la validez o contradicción de afirmaciones expresadas en lógica proposicional. Mientras su aplicación en escenarios del mundo real puede ser computacionalmente intensiva, su base teórica tiene un valor inmenso para entender sistemas lógicos y desarrollar herramientas automatizadas prácticas en la informática.

La inferencia por resolución brinda una gran visión sobre la estructura lógica de los problemas, lo que permite construir algoritmos eficientes para abordar tareas complejas de razonamiento lógico, y sigue siendo un área importante de estudio en matemáticas e informática.


Posgrado → 8.1.4


U
username
0%
completado en Posgrado

← Anterior (8.1.3)
Técnicas de demostración en lógica proposicional
Siguiente (8.2) →
Lógica de predicados

Comentarios 



Solución en lógica proposicional

https://www.buddymath.com/g/8.1.4?bmal=es