Categories
General

RESUMEN DE LÓGICA

1. Lógica Formal de Primer Orden:

1.1. Razonar: Resolver problemas conectando unas ideas con otras.

  • Lógica: Ciencia formal que estudia la validez de los razonamientos.
  • Lógica Formal: Ejerce la lógica sirviéndose de lenguajes formales abstractos que desprecian el contenido del razonamiento y se centran en la estructura.

1.2. Componentes de los razonamientos:

  • Proposición: Sentencia declarativa bivalente, que puede ser verdadera o falsa.
    • Atómica: Carece de conexiones con otras proposiciones, V o F.
    • Literal: Proposición atómica afirmada o negada.
    • Molecular: Conjunto de proposiciones atómicas unidas por una conectiva:

–  Conjuntiva: Equivale al “Y”, es conmutativa, expresa adicción.

–  Disyuntiva: Equivale al “O”, es conmutativa, expresa alternativas.

–  Condicional: Equivale al “SI… ENTONCES…”, no es conmutativa.

°       Antecedente: Después del “SI” condición suficiente del consecuente.

°       Consecuente: Después del “ENTONCES” condición necesaria del antecedente.

–  Bi-condicional: Equivale al “SI Y SOLO SI… ENTONCES…” es conmutativa.

  • Premisas: Proposiciones de las que se parte para llevar a cabo un razonamiento.
  • Inferencia: Operación lógica que obtiene nuevas proposiciones aplicando reglas.
  • Conclusión: Resultado que se quiere demostrar. Se obtiene a partir de las premisas.

1.3. Razonamientos correctos y falacias

  • Razonamiento correcto: Si no es posible que sus premisas sean verdaderas y su conclusión falsa. Si se aceptan las premisas se acepta la conclusión.
  • Falacia: Razonamiento aparentemente lógico pero que incorrecto.
    • Falacia formal: Afecta a la estructura del razonamiento.

–  Afirmar el consecuente: En un condicional, si se afirma el consecuente, no tiene porque afirmarse el antecedente.

–  Negar el antecedente: En las condicionales, al negar el antecedente no se debe negar el consecuente.

  • Falacia informal: Afecta al contenido del razonamiento.

1.4. Sistemas Formales Lógicos: Herramienta de la lógica formal compuesta por:

  • Lenguaje formal Tema 2: Símbolos (alfabeto) y reglas (gramática), formalmente especificados, que combinados dan  lugar a una fbf (formula bien formada).
  • Semántica Temas 3 y 4: Estudia la interpretación de las fórmulas en el mundo real.
  • Proceso Deductivo: Demostración de que desde las premisas se extrae la conclusión, mediante la aplicación de reglas
  • Lógica Proposicional: Supone que existen hechos simples que pueden ser verdaderos o falsos (proposiciones), y los relaciona mediante conectivas lógicas.
  • Lógica de predicados: Describe, además de los hechos y sus relaciones, a los sujetos, sus propiedades y sus  semejanzas con otros sujetos.

2. Lenguaje de la Lógica de Primer Orden. Teoría de Conjuntos.

2.1. El Lenguaje de la Lógica de Primer Orden:

  • Lenguaje Natural: Ambiguo, polisemántico, muy expresivo. Ejemplo: el español.
  • Lenguaje Formal: Conciso, preciso, universal, estático, basado en la estructura y no en el contenido. Ejemplo: Lenguaje Formal de la Lógica de Primer Orden:
    • Lógica Proposicional: Busca hechos y conexiones entre ellos
    • Lógica de Predicados: Además destaca sujetos y sus propiedades y relaciones.

2.2. El Lenguaje Proposicional: Propio de la lógica proposicional.

  • Alfabeto: Conjunto de símbolos que se utilizan en el lenguaje.
    • Variables Proposicionales: Letras que representan proposiciones atómicas.
    • Conectivas Lógicas: Representan conexiones entre proposiciones atómicas.

– Negación: Se expresa mediante ¬ y, ¬A es cierta cuando A es falsa.

– Conjunción: Se expresa como ∧, y A∧B es cierto cuando ambas son ciertas.

– Disyunción: Se expresa como ∨, y A∨B es cierto si alguna de las dos lo es.

– Condicional: Se expresa como →, A→B se cumple si para A cierto, lo es B.

– Bicondicional: Se expresa como ↔, A↔B se cumple si v(A)=v(B).

  • Símbolos auxiliares: Paréntesis que se utilizan para estructurar las fórmulas.
  • Gramática: Equivale al “Y”, es conmutativa, expresa adicción.
    • Formación de una fbf: Una variable proposicional A siempre es una fbf, además también lo serán ¬A, A∧B, A∨B, A→B y A↔B.
    • Jerarquía: Negación (¬), conjunción (∧) y disyunción (∨), y condicionales (→,↔)
    • Asociatividad: Todas las conectivas lógica binarias son asociativas por la izquierda menos los condicionales y bicondicionales que lo son por la derecha.

2.3. El Lenguaje de Predicados: Formaliza las proposiciones con  sus conexiones y los sujetos que las realizan con sus propiedades y relaciones dentro de un marco conceptual.

  • Alfabeto: Conjunto de símbolos formado por:
  • Símbolos del lenguaje proposicional: Las variables proposicionales, conectivas lógicas y los símbolos auxiliares también se usan en este lenguaje.
  • Términos: Expresión que se refiere a un objeto, no es ni verdadera ni falsa.

– Variables: Se refieren a objetos indeterminados Ej: x.

– Constantes: Hacen referencia a algún objeto concreto Ej: maría.

– Funciones: Denotan objetos en función de sus argumentos Ej: padre (luís).

  • Predicados: Denotan una propiedad de su argumento o describen una relación entre sus argumentos, pueden ser verdaderos o falsos Ej: Padre(pepe, luís).
  • Cuantificadores: Establecen el alcance de las variables de una fórmula lógica

– Universal: Se escribe como “, y engloba a todos los elementos del dominio. Ej. “x(Ho(x) → Mor(x)), todo hombre es mortal.

– Existencial: Se escribe como $, y declara que algún elemento del dominio cumple la condición. Ej. $x(Ho(x) ∧ Feo(x)), existe algún hombre feo.

  • Gramática: Similar a la del lenguaje proposicional
  • Dominio: Conjunto de cosas de las cuales se habla, universo del discurso.

2.4. Construcción de Formulas:

  • Formalizar en lenguaje proposicional: Ver si la formula es atómica  o molecular.
    • Atómica: En este caso nombrarla con una variable proposicional.
    • Molecular: En este caso detectar los elementos que la forman y unirlos con las conectivas correspondientes. Realizar el smismo análisis con los elementos.
    • Formalizar en lenguaje de predicados: Analizar la estructura de la fórmula lógica:
      • Atómica: Elegir nombre para predicados y constantes.
      • Molecular: Conectar los componentes con las conectivas correspondientes.
      • No constantes: Elegir cuantificador y el nombre de predicados.

– Un cuantificador universal se formaliza con el Implicador.

– Un cuantificador existencial se formaliza con la conjunción.

  • Equivalencias:
    • Implicador-Disyuntor: A→B » ¬A∨B
    • Implicador-Conjuntor: A→B » ¬(A ∧ ¬B)
    • Leyes de Morgan: ¬A ∧ ¬B » ¬(A ∨ B) ; ¬A ∨ ¬B » ¬(A ∧ B)
    • Ley del Bicondicional: A↔B » (A→B) ∧ (B→A)
    • Cuantificadores: ¬ [“/$] x P(x) » [$/”]x ¬P(x) ; ¬[“/$] ¬P(x) » [$/”]x P(x).

2.5. Formalización de Razonamientos: Para formalizar un razonamiento deductivo en el lenguaje lógico hay que identificar las premisas y la conclusión, y formalizarlas tras definir un marco conceptual sobre el que trabajarán.

2.6. Conjunto: Colección de objetos definidos y diferenciados llamados elementos. Se denotan con letras mayúsculas, Ej. El conjunto de vocales: V= {a,e,i,o,u}.

  • Pertenencia: Si “a” es un elemento del conjunto “A” se dice que aÎA, y si no aÏA.
  • Declaración: Encerrando entre llaves todos sus elementos, o enunciando una característica que lo defina. Æ es el conjunto vacio, y U el universo del discurso.
  • Subconjuntos: A es un subconjunto de B si todo elemento de A pertenece también a B: AÍB. Para que el subconjunto sea propio A no debe ser igual que B.

2.7. Operaciones entre Conjuntos:

  • Intersección: Se representa por AÇB, y lo forman los elementos que pertenecen a A y a B al mismo tiempo.
  • Unión: Escrito AÈB,  lo forman todos los elementos de A y todos los de B.
  • Diferencia: A-B, es el conjunto formado por todos los elementos de A menos los que también pertenecen a B.
  • Complementario: A’ lo forman los elementos que no pertenecen a A.
  • Propiedades: Conmutativa, asociativa, distributiva y leyes de Morgan.

2.8. Relación entre Tª de Conjuntos y L. de 1er Orden

  • El subconjunto equivale al Implicador: AÍB » A→B.
  • La unión equivale a la disyunción: AÈB » A∨B .
  • La intersección equivale a la conjunción: AÇB » A∨B.
  • El complementario equivale al negado: A’ » ¬A.

3. Semántica de la Lógica de Primer Orden. Demostración.

3.1. Fundamentos teóricos:

  • Preparación del problema: Con Tablas de Verdad, el Contraejemplo, o Resolución.
  • Concepto de verdad: Se define como satisfacción de una condición. Según el principio de bivalencia, una proposición atómica solo puede ser verdadera o falsa.
  • Interpretación: Función que asigna un valor de verdad a una función a partir de los significados de sus componentes básicas.
    • Fórmulas atómicas: Tienen dos interpretaciones, verdadero y falso.
    • Fórmulas moleculares: Según sus variables n, tiene 2n interpretaciones.

– Conectivas: Mirar el apartado 2.2. (“Conectivas Lógicas”).

– Términos: Es necesario definir un dominio de referencia.

– Predicados: También se define según el dominio, con Dn interpretaciones.

– Cuantificadores: Se definen según el dominio de referencia:

°   Universales: Son V si todos los elementos del dominio de la variable son V.

°   Existenciales: Son V si algún elemento del dominio de la variable es V.

  • Tipos de interpretaciones: Según los valores de la interpretación:

– Interpretación Modelo: Bajo la cual, la fbf se interpreta como verdadera.

– Interpretación Contraejemplo: Cuando la fbf se interpreta como falsa.

  • Clasificación Semántica: De fórm. atómicas hay 2: V y F. De las moleculares:

– Tautología: Cuando para toda interpretación la fbf es verdadera.

– Contradicción: Cuando para cualquier interpretación la fbf es falsa.

– Contingencia: Existe algunas interpretaciones que la hagan V y otras F.

  • Tipos de fórmulas: Según sus interpretaciones posibles:

– Satisfacible: Si alguna interpretación la hace verdadera.

– Insatisfacible: Si ninguna interpretación la hace verdadera.

  • Consecuencia Lógica: Q es consecuencia lógica de P si siempre que se cumple P se cumple Q también, sin excepción
  • Razonamiento correcto: Un razonamiento Pi Þ Q es correcto solo si la conclusión Q es consecuencia lógica de las premisas.

3.2. Métodos de las tablas de verdad y del contraejemplo

  • Tablas de Verdad: Muestran el valor semántico de una fbf molecular para cada combinación de valores de verdad que se pueden asignar a sus componentes.

–  Filas: Una por cada interpretación de la fórmula. 2n siendo n las variables.

–  Columnas: Una por cada variable que aparezca en la fbf.

  • Resultado: Con el desglose de valores de verdad podemos comprobar que siempre que se cumplen las premisas se cumple la conclusión.
  • Método del Contraejemplo: Prueba la falsedad de un enunciado, suponiendo que lo es. Si con esta suposición se llega a contradicción el enunciado es correcto.
    • Procedimientos: Dar valores verdaderos a todas las premisas y valor falso a la conclusión, y desarrollar hasta encontrar una contradicción. Si no encontramos contradicción es que existe una interpretación con esos valores, que hacen al razonamiento contingente o contradictorio.

3.3. Regla de Resolución: Comprueba que el conjunto C = {P1, P2,…Pi, ¬Q} es insatisfacible.

  • Forma Clausal: Expresión de una formula como disyunción de literales.
    • Obtención: Usando las equivalencias que resultan en disyunciones (2.4.) y las propiedades (2.7.), renombrando variables, usando el criterio de Skolem y situando los universales al principio de la fórmula.

– Criterio de Skolem: Si un cuantificador existencial esta dentro del ámbito de un universal, la variable del primero depende de la del segundo según una función: Ej. “y$x P(x, y) » ” P(f(y), y).

  • Resolución Proposicional: A partir de un conjunto de clausulas C = {P1, P2,…Pi, ¬Q} se desarrollan clausulas resolubles y se obtienen resolventes (a partir de literales complementarios) Ej. desde Cl1: P∨Q , Cl2: ¬P∨R, se obtiene Cl3: Q∨R. Hasta encontrar una contradicción que demuestre que el conjunto C es insatisfacible.
  • Resolución Predicativa: Es necesaria la sustitución de las variables por términos, con el fin de conseguir los literales complementarios (si tenemos Q(x) y ¬Q(a) deberemos sustituir x por a), la sustitución se debe hacer en todas las sub-fórmulas: Ej. Cl1: P(x, y) ∨ Q(x), Cl2: ¬Q(a) ∨ R(z), Cl3: P(a, y) ∨ R(z).

4. Demostración por Deducción Natural

4.1. Fundamentos Teóricos: El objetivo es, a partir de las premisas y con el único apoyo de unas reglas básicas obtener la conclusión pedida, tras pequeños pasos justificados.

  • Subdeducciones: Deducciones tras un supuesto provisional. Este supuesto debe cancelarse antes de finalizar la demostración y las formulas interiores de la subdeducción son inaccesibles. Podemos suponer cualquier cosa.
  • Componentes: Un número finito de fórmulas que pueden diferenciarse en:
    • Premisas: Hipotéticamente dadas desde el principio de la deducción.
    • Supuestos provisionales: Subdeducciones.
    • Líneas deducidas: Consecuencias lógicas inmediatas de líneas anteriores.
    • Líneas de deducción:
      • Número de líneas: Se numeran las líneas en la parte izquierda, desde el 1.
      • Señalas premisas: Se señalan con una raya antes de la numeración.
      • Comentarios de consecuencias inmediatas: Se señala, en cada deducción inmediata la regla utilizada para llevarla a cabo, y las líneas afectadas.
      • Subdeducciones: En la línea que empieza marcamos con el inicio de una escuadra (ì), y en las sucesivas prolongamos la escuadra (ï). Para cancelas la subdeducción cerramos la escuadra (î), siempre antes de la numeración.

4.2. Reglas de Inferencia Básicas: Dos para cada conectiva (introducción y eliminación):

  • Reglas básicas de Implicación
    • Introducción: Si de una hipótesis A se sigue B, se puede añadir que A→B.
    • Eliminación: Supuesta una implicación y la fórmula que hace en ella de  antecedente, se puede afirmar  consecuente.
    • Reglas básicas de Conjunción
      • Introducción: Si se afirma una proposición y luego se afirma otra también, se puede afirmar la conjunción de ambas
      • Eliminación: De la conjunción de varias proposiciones se afirman todas ellas.
    • Reglas básicas de Disyunción
      • Introducción: Si una fórmula es verdadera, también es verdadera su disyunción con otra fórmula cualquiera.
      • Eliminación: Si de cada uno de los componentes se deduce la misma fórmula se puede afirmar esa fórmula.
    • Reglas básicas de Negación
      • Introducción: Toda proposición que deduce una contradicción debe negarse.
      • Eliminación: Negar doblemente una fórmula es tanto como afirmarla.
    • Reglas básicas del Cuantificador Universal
      • Introducción: Si un individuo cualquiera (no uno en particular) verifica una propiedad, todos los individuos del universo la verifican.
      • Eliminación: De la verdad de todos los individuos se puede afirmar la verdad de un individuo en particular.
    • Reglas básicas del Cuantificador Existencial
      • Introducción: Si un individuo verifica una propiedad P, existe algún individuo que la verifica.

4.3. Demostración por el Método Directo: Si se quiere deducir una formula condicional hay que suponer el consecuente (subdeducción) y se realiza la argumentación hasta llegar a inferir el consecuente.

4.4. Demostración por el Método de Reducción al Absurdo: Para demostrar una formula por este método debemos de suponer su complementaria, y desarrollarla en una subdeducción hasta llegar a una contradicción. Si aparece la contradicción es que la negada, la complementaria, no existe, con lo que la formula queda demostrada.