Lógica proposicional

Estudia las relaciones que se dan entre los enunciados sin analizar su estructura interna, es decir, tomadas como un todo.

Características: - limitación: solo uso declarativo - precisión: no tiene ambiguedad - conectores: funciones veritativas, es decir, que a unos valores de verdad y unos conectores dados responden con un valor de verdad total. - atomicidad: enunciados simples - falsedad: no distingue los tipos de falsedad, solo si es falso o no - bivalencia: o es falso o verdadero

Principios

• contradicción: un enunciado no puede ser verdadero y falso a la vez
• tercio excluso: no se puede ser algo que no sea verdadero o falso.

Símbolos

Símbolos proposicionales

p, q, r, s

Símbolos lógicos

• constantes: V o T y F o ⊥.
• conectivas
  • ¬ que significa: «no» (símbolo de negación).
  • ∧ que significa: «y» (símbolo de conjunción).
  • ∨ que significa: «o» (símbolo de disyunción).
  • → que significa: «si… entonces» (símbolo de condicional o implicación).
  • ↔ que significifica "si y solo si"
• auxiliares:
  • (
  • )
  • ,

El alfabeto total es Σ = Σ ∪ {⊤, ⊥, ¬, ∧, ∨, →, ↔}, ∪ {(,)}

Siguen estas reglas:

• Todo símbolo proposicional es una fórmula: es decir, p, q, r, s, t,…
• Si p y q son fórmulas, también lo son: ¬p, p ∧ q, p ∨ q, p → q, p ↔ q.
• Solo es posible construir fórmulas usando las dos reglas anteriores..

Una proposición es simple si no tiene conectivas, por ejemplo:

Peter Pan es el amor.
    P

Y proposición compuesta si tiene conectivas.

Peter Pan es el amor y campanilla su princesa.
    P  ∧ Q

Conectores

Las conectivas ∧ y ∨ son diádicas (afectan a dos proposiciones) y la conectiva NO monádica, pues afecta solo a uno.

Una proposición compuesta es la idea expresada y llamamos fórmula a la expresión escrita de esa propósición en lenguaje lógico.

Todas las expresiones que contienen identificadores que representan expresiones se denominan esquemas.

Por ejemplo, si A = (p ∧ q) y si B = (p ∨ q), entonces el esquema (A → B) representa ((p → → q) → (p ∨ q)).

FBF Fórmulas bien formadas

Todas las FBF pueden construirse de acuerdo con las siguientes reglas de formación: 1. Toda expresión atómica es una FBF. 2. Si A es una FBF, (¬A) también lo es. 3. Si A y B son FBF, entonces lo son (A ∧ B), (A ∨ B), (A → B), y (A ↔ B). 4. Ninguna otra expresión es una FBF

Prioridades de conectivas y parentesis

• Negación (¬): La negación tiene la mayor prioridad y se evalúa antes que cualquier otra operación en una expresión lógica.
• Conjunción (∧): La conjunción tiene una prioridad menor que la negación y se evalúa después de esta.
• Disyunción (∨): La disyunción tiene una prioridad menor que la conjunción y se evalúa después de esta.

• Implicación (→): La implicación tiene una prioridad menor que la disyunción y se evalúa después de esta. • Bicondicional (↔): El bicondicional tiene la menor prioridad y se evalúa después de todas las otras operaciones.

  p ∧ q → r ∨ s

Se omiten siempre los paréntesis más externos. Las conectivas ∧, ∨ y → asocian por la derecha. De esta manera:

p → r → s  significa   p → (r → s)   y no  (p → r) → s

• Video de udima

Semántica

Es la interpretación de cada proposición. ¿Es verdadera? ¿O es falsa?

Las tablas de verdad

Se expresan los 2 valores posibles de cada proposición simple y vemos las combinaciones para averiguar el valor final de verdad.

Tabla de Verdad para $(P \land Q) \to R$

Tabla de verdad de las conectivas lógicas

Si tienes $n$ proposiciones, las combinaciones posibles son $2^n$. Para construir las columnas de cada proposición ($p$, $q$, $r$, etc.), sigue estas reglas:

1. Primera proposición ($p$):
2. Alterna $V$ y $F$ cada $2^{n-1}$ filas.

3. Ejemplo: Si $n = 3$, alterna $V, F$ cada $2^{3-1} = 4$ filas.

4. Segunda proposición ($q$):

5. Alterna $V$ y $F$ cada $2^{n-2}$ filas.

6. Ejemplo: Para $n = 3$, alterna $V, V, F, F$ cada $2^{3-2} = 2$ filas.

7. Tercera proposición ($r$):

8. Alterna $V$ y $F$ cada $2^{n-3}$ filas.
9. Ejemplo: Para $n = 3$, alterna $V, F$ cada $2^{3-3} = 1$ fila.

$$ \text{Período de alternancia para una proposición} = 2^{n-i}, \quad \text{donde } i \text{ es el índice de la proposición (1 para } p, 2 \text{ para } q, \text{ etc.)}. $$

Una expresión lógica es una tautología si es verdadera para todas las asignaciones posibles. Una expresión lógica es una contradicción si es falsa para todas las asignaciones posibles. Una expresión lógica, que no sea ni una tautología ni una contradicción es una contingencia.

Debido a la importancia de las tautologías, se ha creado un símbolo especial para indicar que una expresión lógica es una tautología: ⊤ o ⊨. Así como ¬(p ∧ q) ∨ q, es, según su tabla de verdad, una tautología puede escribirse ⊤ ¬ (p ∧ q) ∨ q.

Para toda tautología su negación es una contradicción. Como las tautologías, las contradic- ciones pueden convertirse en esquemas. Esto significa, verbigracia, que (p → q) ∧ ¬(p → q) es una contradicción porque sigue el esquema A ∧ ¬A, del que, a su vez, puede derivarse p ∧ ¬p.

De todas las tautologías una célebre es el tercio excluso y que es p ∨ ¬ p

Implicación lógica ($\Rightarrow$): - Dos proposiciones $p$ y $q$ están en relación de implicación si $p \to q$ es una tautología. - Notación: $p \Rightarrow q$, leído como "p implica lógicamente a q". - Distinción: - $\to$: Operación lógica entre proposiciones, que puede ser verdadera o falsa. - $\Rightarrow$: Relación lógica basada en que $p \to q$ sea siempre verdadero. - $p$: Hipótesis.
$q$: Tesis.

Equivalencia lógica ($\Leftrightarrow$): - $p$ y $q$ son equivalentes lógicamente si $p \leftrightarrow q$ es una tautología. - Notación: $p \Leftrightarrow q$ o $p \equiv q$, leído como "p si y solo si q".

Pragmática: Razonamiento Deductivo y Reglas de Inferencia

Inferencia y razonamiento
Proceso para obtener conclusiones a partir de premisas. Si la inferencia es confiable, se denomina deducción o inferencia lógica.

Validez
Un enunciado es válido si es verdadero en todas las interpretaciones posibles.
Ejemplo: "Llueve o no llueve" es válido porque siempre es verdadero, independientemente de las circunstancias.
También se llaman analíticos o tautológicos.

Satisfacibilidad
Un enunciado es satisfacible si existe al menos una interpretación donde es verdadero.
Ejemplo: "Hay un muro frente a mí y no hay muro frente a mí" es insatisfacible porque es contradictorio.

Reglas de inferencia
Métodos para derivar conclusiones a partir de premisas. Utilizan conectores como "luego", "por tanto", o el símbolo ⊢ (deductor).

Ejemplo de Inferencia

Premisas
- $p \to q$: "Si suben los salarios, entonces suben los precios." - $q \to r$: "Si suben los precios, baja el poder adquisitivo." - $p$: "Suben los salarios."

Conclusión
- $r$: "Baja el poder adquisitivo."

Razonamiento
- Aplicar modus ponens: - De $p \to q$ y $p$, se deduce $q$. - De $q \to r$ y $q$, se deduce $r$.

Deductor
$\vdash$ representa que una conclusión se deduce lógicamente de las premisas.

Modus Ponens
Si $p \to q$ es verdadero y $p$ es verdadero, entonces $q$ es verdadero.

Leyes Esenciales del Álgebra de Enunciados

[!note] Tabla 6: Leyes Esenciales del Álgebra de Enunciados

Doble negación
$\neg(\neg p) \Leftrightarrow p$

Tercio excluso
$p \lor \neg p \Leftrightarrow V$

Contradicción
$p \land \neg p \Leftrightarrow F$

Identidad
$p \lor F \Leftrightarrow p$
$p \land V \Leftrightarrow p$

Denominación
$p \lor V \Leftrightarrow V$
$p \land F \Leftrightarrow F$

Idempotencia
$p \lor p \Leftrightarrow p$
$p \land p \Leftrightarrow p$

Conmutativas
$p \lor q \Leftrightarrow q \lor p$
$p \land q \Leftrightarrow q \land p$

Asociativas
$(p \lor q) \lor r \Leftrightarrow p \lor (q \lor r)$
$(p \land q) \land r \Leftrightarrow p \land (q \land r)$

Distributivas
$(p \lor q) \land (p \lor r) \Leftrightarrow p \lor (q \land r)$
$(p \land q) \lor (p \land r) \Leftrightarrow p \land (q \lor r)$

De Morgan
$\neg(p \land q) \Leftrightarrow \neg p \lor \neg q$
$\neg(p \lor q) \Leftrightarrow \neg p \land \neg q$

Transitividad
$[(p \to q) \land (q \to r)] \to (p \to r)$

Métodos para manipular expresiones

Generalmente para poder trabajar con lógica de proposiciones lo primero que se hace es transformar las condicionales y bicondicionales en Y O.

p → q ⇔ ¬p ∨ q

En lo concerniente a la bicondicional p ↔ q, existen dos modos de expresarla:
p ↔ q ⇔ (p ∧ q) ∨ (¬p ∧ ¬q)
p ↔ q ⇔ (p → q) ∧ (q → p)

Y

En expresiones como $c ∧ b ∧ ¬a$

ordenamos por nombre $a ∧ b ∧ c$

Si la expresión tiene literales complementarios es false $a ∧ ¬a ↔ F$

O

Si tiene un F, es False

• Tautología en disyunciones:

  • Una disyunción es una tautología si contiene literales complementarios (por ejemplo, $A \lor \neg A$) o si contiene la constante lógica V (verdadero). Esto ocurre porque:
    • $A \lor \neg A$ Siempre es verdadero (ley del tercero excluido).
    • $A \lor V$: Siempre es verdadero

  • Simplificación de disyunciones:

  • La constante lógica F (falso) no afecta el resultado de una disyunción y puede eliminarse:

    • $A∨F=A$
  • Los literales duplicados también pueden eliminarse porque no cambian el valor de la disyunción:
    • $A∨A=A$

  Formas normales

Es útil, generalmente, estandarizar las expresiones para facilitar su identificación y comparación entre ellas. Las formas estándar de las expresiones lógicas se denominan formas normales y son de dos tipos: disyuntivas y conjuntivas, que se definen como sigue: Se dice que una expresión lógica está en forma normal disyuntiva si está escrita como disyunción, en la cual todos los términos son conjunciones literales. Similarmente, está en forma normal conjuntiva si está escrita como conjunción de disyunciones de literales.

Cómo se hace una fórma normal: - 1. Elimnar condicionales - 2. Si la expresión continee cualquier subexpresión compuesta negada, eliminar la negación usando la ley de doble negación o usar las leyes de De Morgan para reducir el alcancer de la negación. - 3. Una vez encontrada una expresión sin ninguna subexpresión compuesta negada, usar las leyes; De esta manera reducimos la disyunción.

Reglas de inferencia

Lógica Proposicional y Problemas NP

¿Qué son los problemas NP?

• Son problemas que pueden resolverse con una computadora de manera eficiente si se cuenta con una "pista" o solución posible para verificar.
• Ejemplo: Resolver un sudoku. Es difícil encontrar la solución desde cero, pero si alguien te da una solución, es fácil verificar si es correcta.

Stephen Cook y su trabajo

Stephen Cook demostró que ciertos problemas en lógica y Matemáticas son especialmente difíciles. A esto se le llama "NP-completo". Esto significa que: - Resolver estos problemas es complicado. - Pero si encontramos una solución para uno de ellos, podríamos resolver muchos otros problemas difíciles de manera más fácil. - Cook usó lógica proposicional para demostrar su idea. En lógica proposicional: - Las máquinas de Turing son como modelos de computadoras que Cook usó para analizar estos problemas difíciles. - Explicó que estas máquinas no pueden resolver problemas NP-completos en tiempo razonable sin ayuda.

Problema SAT (Satisfacibilidad Booleana)

Definición

El problema de Satisfacibilidad Booleana (SAT) consiste en determinar si existe una asignación de valores verdaderos (True) o falsos (False) para un conjunto de variables booleanas que haga que una fórmula lógica sea verdadera.

Fórmula: $(A \lor \neg B) \land (B \lor C)$ Pregunta: ¿Es posible asignar valores a (A), (B), y (C) de modo que la fórmula sea verdadera? Solución: - Una asignación válida sería: - $(A = \text{True})$ - $(B = \text{False})$ - $(C = \text{True})$ Importancia Problemas NP-completos: - SAT fue el primer problema demostrado como NP-completo por Stephen Cook en 1971 (Teorema de Cook). - Resolver SAT implica resolver otros problemas complejos de la clase NP. - Para (n) variables, probar todas las posibles combinaciones tiene un tiempo de cálculo exponencial ((2^n)). - Aunque existen herramientas llamadas SAT solvers (como MiniSAT o Z3) que optimizan la búsqueda, no garantizan resolver el problema eficientemente en todos los casos.

El problema de Hamilton acerca de los puentes de Königsberg o del viajante de comercio, el problema de acoplar grupos de tres compañeros de habitación, todos muy conocidos en teoría de grafos, también son NP-completos

Reglas de inferencia

Reglas de Inferencia en Lógica Proposicional

Modus Ponens (MP)

Esta regla establece que si tenemos una implicación y su antecedente, podemos inferir su consecuente:

$$\frac{P \rightarrow Q, \space P}{Q}$$

Ejemplo: - $llueve \rightarrow uso_paraguas$ - $llueve$ - $\therefore \space uso_paraguas$

Y-Eliminación (∧E)

Permite extraer cualquier componente de una conjunción:

$$\frac{P \land Q}{P}$$ o $$\frac{P \land Q}{Q}$$

Ejemplo: - $alto(juan) \land delgado(juan)$ - $\therefore alto(juan)$

Y-Introducción (∧I)

Si tenemos dos premisas, podemos formar su conjunción:

$$\frac{P, \space Q}{P \land Q}$$

Ejemplo: - $nublado$ - $frio$ - $\therefore nublado \land frio$

O-Introducción (∨I)

Permite añadir cualquier proposición mediante disyunción:

$$\frac{P}{P \lor Q}$$

Ejemplo: - $llueve$ - $\therefore llueve \lor sol$

Resolución (Res)

Resuelve dos cláusulas con literales complementarios:

$$\frac{P \lor Q, \space \lnot P \lor R}{Q \lor R}$$

Ejemplo: - $llueve \lor paraguas$ - $\lnot llueve \lor mojado$ - $\therefore paraguas \lor mojado$

Nota sobre la Notación

• $\therefore$ significa "por lo tanto"
• La línea horizontal separa premisas de conclusión
• Las letras mayúsculas ($P$, $Q$, $R$) representan proposiciones
• $\lor$ representa disyunción (O)
• $\land$ representa conjunción (Y)
• $\rightarrow$ representa implicación (SI...ENTONCES)
• $\lnot$ representa negación (NO)

Tableaux o árboles semánticos

Es un procedimiento semántico de despliegue de todas las condiciones de verdad de la fórmula en estudio. Sus ramas se cierran el encontrar una contradicción. Un árbol de ramas cerradas es insatisfacible. Es un procedimiento sistemático de búsquedas de contraejemplos o una refutación.

Lo que se busca en un tableux es un modelo que satisface la fórmula. Para validar una fórmula demostramos que el conjunto de hipótesis más negación de la conclusión es insatisfacible.