Cálculo Proposicional y Lógica Matemática

Resumen de Temas Fundamentales

• El libro explora la aplicación de matemática discreta y lógica en el diseño y razonamiento de aplicaciones informáticas.
• Se centra en lógica proposicional, programación lógica y funcional, y sistemas de información.
• Incluye capítulos dedicados a lenguajes de especificación como Z, gramáticas, lenguajes, bases de datos relacionales, Prolog y Miranda.
• Recomendado para estudiantes universitarios, docentes de matemáticas y profesionales informáticos que necesitan fundamentos matemáticos sólidos.
• Destaca por su enfoque didáctico, ejemplos resueltos y propuesta de problemas con soluciones.

Introducción al Cálculo Proposicional

• La lógica es esencial en matemáticas y en la construcción de programas de computadora.
• El razonamiento lógico puede ser erróneo, por lo que es importante conocer las leyes fundamentales de la derivación lógica.
• Las proposiciones (afirmaciones verdaderas o falsas) son básicas para la derivación lógica.
• El cálculo proposicional se enfoca en combinar y manipular proposiciones de diversas maneras.
• El capítulo introduce argumentos lógicos y examina proposiciones atómicas y compuestas en detalle.
• Se analizan tautologías, implicaciones lógicas y equivalencias lógicas, necesarias para un razonamiento sólido.

Argumentos y Proposiciones Lógicas

• Es crucial distinguir entre argumentos lógicamente válidos e inválidos.
• Un argumento tiene premisas que llevan a una conclusión.
• Un argumento es válido si la conclusión se sigue lógicamente de las premisas sin importar la veracidad de las premisas.
• Silogismo hipotético: Si P → Q y Q → R, entonces P → R, donde P, Q y R representan cualquier afirmación.
• Silogismo disyuntivo: Si P o Q es cierto, y Q es falso, entonces P debe ser cierto.
• Modus ponens: Si P → Q es cierto y P es cierto, entonces Q debe ser cierto.
• En lógica, las afirmaciones involucradas en argumentos deben ser únicamente verdaderas o falsas, no tener otro estado.
• Proposición: Cualquier afirmación que es verdadera o falsa.
• No se consideran proposiciones a órdenes y preguntas.
• Variables proposicionales: Variables como P, Q, R, con valores verdadero o falso.
• Constantes proposicionales: V (verdadero) y F (falso).
• Proposiciones atómicas: Variables o constantes proposicionales que no pueden subdividirse.
• Proposiciones compuestas: Combinación de proposiciones atómicas mediante conexiones lógicas.
• Una tabla de verdad muestra los valores verdaderos de una proposición para todas las asignaciones posibles.

Conexiones Lógicas

• Las conexiones lógicas combinan proposiciones para formar nuevas proposiciones.
• Lenguajes naturales pueden ser ambiguos, por lo que se usan símbolos matemáticos para evitar la ambigüedad.
• En lógica, una proposición formulada implica que es verdadera.
• Negación: ¬P (no P), es verdadera si P es falsa y viceversa; se representa con una tabla de verdad.
• Conjunción: P ∧ Q (P y Q), es verdadera solo si ambas P y Q son verdaderas.
• En el lenguaje español coloquial se utilizan abreviaturas que no permiten expresar la lógica formal.
• Disyunción: P ∨ Q (P o Q), es falsa solo si ambas P y Q son falsas; se puede entender como "P, Q o ambas".
• Condicional: P ⇒ Q (Si P, entonces Q), es falsa solo si P es verdadera y Q es falsa; si P es falsa, la condicional es trivialmente verdadera.
• P ⇒ Q significa que siempre que P sea correcta, Q lo es. P se llama antecedente y Q el consecuente.
• P ⇒ Q se puede traducir como "P sólo si Q". Q es condición necesaria para P; P es condición suficiente para Q.
• Indicaciones para expresar la condicional: Si P, entonces Q; Siempre que P, entonces Q; P es suficiente para Q; P sólo si Q; P implica Q
• Se puede invertir el orden del antecedente y del consecuente
• Una frase "solo si X es valida" corresponde a <=, sin embargo "si" corresponde a =>.
• Bicondicional: P ⇔ Q es verdadera solo si P y Q tienen los mismos valores de verdad. También llamada equivalencia (P si y sólo si Q).
• La conexión ¬ es unaria, mientras que ∧, ∨, ⇒, ⇔ son binarias.
• Las binarias ∧, vy ⇔ son simétricas, el orden no afecta el valor de verdad, mientras que ⇒ no lo es.

Proposiciones Compuestas

• Se pueden combinar proposiciones atómicas o compuestas utilizando conexiones lógicas.
• Si no se toman precauciones, las expresiones pueden ser ambiguas interpretarse de diversas maneras.
• Para evitar esto, introducimos primero las expresiones completamente en paréntesis y las reglas de precedencia.
• Cualquier proposición debe expresarse de algún modo, bien sea verbalmente, gráficamente o mediante una cadena de caracteres, donde una proposición expresada mediante una cadena de caracteres se denomina una expresión lógica o una fórmula.
• A menos que se tomen precauciones las expresiones lógicas pueden ser ambiguas, para evitar ambigüedades deben pro-porcionarse reglas que muestren la forma de agrupar las diferentes subexpresiones.

Análisis de proposiciones compuestas

• Todo depende el tipo de expresión que sea, estas deben de ser o atómicas o deben de ser negaciones, conjunciones, disyunciones, condicionales o equivalencias.
• Las expresiones completamente entre paréntesis son un método para representar las preposiciones compuestas
• También se pueden representar gráficamente las proposiciones compuestas y analizarlas.
• Analizar una expresión equivale a hallar todas sus subexpresiones.
• El análisis está representado mediante el árbol de análisis en el sentido de que todas las subexpresiones de la expresión están presentes en el árbol.

Prioridad en los operadores y tipos de literales

• Gracias a que muy poca gente trabaja con expresiones completamente entre paréntesis son expresiones largas y con frecuencia difíciles de leer, se puede escribir en cambio (PЛО) → (Pv Q).
• Generalmente, cada conexión tiene dada una prioridad, y las conexiones con una prioridad más alta introducen una unión más fuerte que las conexiones con una prioridad más baja.
• Si P y Q son variables proposicionales, entonces P, Q y-Q son todas literales, pero (P v Q) no es literal. Py-P son dos literales complementarios, pero Py Q no lo son.
• Siempre tener en cuenta si el operador es asociativo por la izquierda o por la derecha
• Operador prefijo, infijo y postfijo

Evaluación de expresiones

• Si usted recibe una clase de computadoras, y no entiende la recursividad, usted no aprobará. (PA-Q)→R
• Se deben usar tablas de verdad para saber las relaciones entre las conexiones
• Enumerar todas las posibles combinaciónes entre las variables

Tautologías

• Para establecer si una expresión es una tautología debes usar tablas de verdad
• A es una expresión tautológica A
• Es menester la ley del medio excluido. Esta establece que PvP es una tautología.

Razonamiento válido

• Un argumento lógico es válido si la conclusión se deduce lógicamente e las premisas

Contradicciones

• Si produce falso para todas las asignaciones es una contradicción
• Una contradicción y las tautologías están relacionados. De hecho si A es tautologia entonces la negación de A es una contradicción

Equivalencias lógicas

• Es una tautología. Esto demuestra que las dos expresiones son lógicamente equivalentes
• Las afirmaciones que son lógicamente equivalentes pueden sustituirse una por la otra sin afectar sus valores de verdad
• Existen tablas de verdad para diferentes compuertas y los distintos dispositivos electrónicos.

Teoría de conjuntos

• Un Conjunto: es una colección de objetos que pueden ser números, letras, personas.
• Objetos del conjunto reciben el nombre de elemento.
• Cardinalidada del conjunto: numero de elementos que tiene un conjuntos n(A)
• Los conjuntos deben ser expresador por extension o comprension

Operaciones entre conjunctos

• Conjunstos A y B
• Interseccion = A ∩ B
• Union = A U B