Tema 1: Lógica proposicional (L0)

Diapositivas: 1. LógicaProposiciones_2026-2027

Para qué sirve la lógica

La lógica estudia la corrección de los razonamientos. Un razonamiento son varias premisas seguidas de una conclusión, y es correcto si preserva la verdad: siempre que las premisas son verdaderas, la conclusión también lo es.

Lo que importa es la estructura, no el contenido:

• "Si hace frío voy al cine. Hace frío. Por tanto, voy al cine" es correcto, como todos los que tienen esa forma.
• "La luna es amarilla. Por tanto, la luna es de queso" no lo es.

En informática aparece en la inteligencia artificial, la programación lógica (Prolog), las bases de datos relacionales, la verificación de software, la electrónica digital…

Hay varias lógicas: las clásicas (proposicional y de predicados) y las no clásicas (modal, multivaluada, difusa…). La proposicional (L0) es la más sencilla y la menos expresiva: su elemento básico es la proposición.

Del lenguaje natural a L0

Una proposición (enunciado simple) es la unidad mínima de información sobre la que se puede decir si es verdadera o falsa: "llueve", "Juan es médico", "Juan es amigo de Pedro".

No son proposiciones: "¿Qué hora es?", "¡Genial!", "2+2", "Pedro". Tampoco lo es "$X$ es mayor que 3", porque su verdad depende de $X$ (para eso está la lógica de predicados).

Las proposiciones se combinan con conectivas:

Método para formalizar:

1. Identificar las proposiciones simples y darles nombre.
2. Identificar las conectivas.

El lenguaje natural puede ser ambiguo. "Cuando no hay electricidad el robot se detiene y el sensor se activa" puede leerse como $(\lnot p \to q) \land r$ o como $\lnot p \to (q \land r)$.

Sintaxis

La sintaxis dice qué cadenas de símbolos están bien formadas.

Alfabeto:

• Símbolos proposicionales: $p, q, r, p_1, \dots$
• Conectivas: $\lnot, \land, \lor, \to, \leftrightarrow$
• Constantes lógicas: $V$ (verdadero) y $F$ (falso)
• Paréntesis

Fórmulas bien formadas (fbf), que se construyen aplicando estas reglas un número finito de veces:

• Caso básico: los símbolos proposicionales y $V$, $F$ son fórmulas (atómicas).
• Paso inductivo: si $F$ y $G$ son fórmulas, también lo son $\lnot F$, $(F \land G)$, $(F \lor G)$, $(F \to G)$ y $(F \leftrightarrow G)$ (compuestas).

La estructura de una fórmula se ve en su árbol de formación: la raíz es la conectiva principal y las hojas son las proposiciones. Cada subárbol es una subfórmula.

Prioridad de las conectivas, de más a menos, para ahorrar paréntesis:

Entre conectivas del mismo nivel manda la de más a la izquierda: $p \to q \to r$ es $(p \to q) \to r$. Ejemplo: $\lnot p \land q \to r$ es $((\lnot p \land q) \to r)$.

Semántica

La semántica da significado a las fórmulas. En lógica clásica solo hay dos valores, V y F, y el valor de una fórmula depende solo de los valores de sus proposiciones y de cómo se combinan.

• Una interpretación $I$ asigna un valor a cada símbolo proposicional: $I: P \to \{V, F\}$.
• Una fórmula con $n$ símbolos distintos tiene $2^n$ interpretaciones posibles.
• Si $F^I = V$, $I$ es un modelo de $F$. Si $F^I = F$, es un contramodelo.

Reglas semánticas (tablas de verdad de las conectivas):

Ejemplo: $\lnot p \land q \to r$ con $I = \{p{=}V, q{=}F, r{=}F\}$ da $F \to F = V$. Con $J = \{p{=}F, q{=}V, r{=}F\}$ da $V \to F = F$, así que $J$ es un contramodelo.

Clasificación de fórmulas

Toda fórmula válida es satisfacible. Las satisfacibles no válidas son las "normales": verdaderas en unas interpretaciones y falsas en otras.

Ejemplos de las diapositivas:

• $p \to q \lor r$: satisfacible, no válida.
• $\lnot p \lor q \land \lnot q \to \lnot p$: válida.

Conjuntos de fórmulas

• Consistente: existe una misma interpretación que hace verdaderas a todas. Ejemplo: $\{p,\ p \to p\}$.
• Inconsistente: no existe ninguna. Ejemplo: $\{p,\ \lnot p\}$.

Ojo: un conjunto de fórmulas satisfacibles puede ser inconsistente. $p$ y $\lnot p$ son satisfacibles cada una por separado, pero no a la vez.

Equivalencia lógica

$F \equiv G$ si $F$ y $G$ tienen el mismo valor en toda interpretación. $\equiv$ es un metasímbolo: habla de las fórmulas, no forma parte de L0.

• Teorema de sustitución: si $F \equiv G$, se puede cambiar $F$ por $G$ dentro de cualquier fórmula y el resultado es equivalente.
• Relación con la validez: $F \equiv G \iff F \leftrightarrow G$ es válida.

Consecuencia lógica y razonamiento correcto

$Q$ es consecuencia lógica de $\Gamma = \{F_1, \dots, F_n\}$, y se escribe $\Gamma \models Q$, si todo modelo común de $F_1, \dots, F_n$ es también modelo de $Q$.

Un razonamiento $\{P_1, \dots, P_n\} \models Q$ es correcto si la conclusión es consecuencia lógica de las premisas.

Ejemplo que se usa en todos los métodos: "Si llueve y no hace viento, llevo abierto el paraguas. No llevo abierto el paraguas, pero llueve. Por tanto, hace viento."

Con $p$: llueve, $q$: hace viento, $r$: llevo el paraguas abierto:

Métodos semánticos de prueba

Tablas de verdad

Se aplica el Teorema I: se construye la tabla de $P_1 \land \dots \land P_n \to Q$ y se comprueba si sale V en todas las filas. Funciona siempre, pero con $n$ variables hay $2^n$ filas.

Pruebas por contradicción (reducción al absurdo)

Para ver si $G$ es válida, se supone que es falsa y se propagan los valores desde fuera hacia dentro:

• Si se llega a una contradicción (una variable tendría que valer V y F a la vez), $G$ es válida.
• Si no, los valores obtenidos son una interpretación que la hace falsa: $G$ no es válida y esa interpretación es un contraejemplo.

Métodos sintácticos de prueba

Una regla de inferencia obtiene una fórmula a partir de otras manipulando solo símbolos. $\Gamma \vdash H$ ("$H$ se deriva de $\Gamma$") significa que hay una cadena finita de fórmulas, cada una obtenida por una regla, que termina en $H$.

Formas normales y forma clausal

• Literal: proposición atómica o su negación. $L^c$ es su complementario ($p$ y $\lnot p$).
• Forma normal conjuntiva (FNC): conjunción de disyunciones de literales. Ejemplo: $(p \lor \lnot q) \land (\lnot p \lor r \lor s) \land p$.
• Forma normal disyuntiva (FND): disyunción de conjunciones de literales. Ejemplo: $(\lnot p \land q \land r) \lor p \lor (r \land s)$.
• Forma clausal (FC): el conjunto de cláusulas (disyunciones) de la FNC. Ejemplo: $\{p \lor \lnot q,\ \lnot p \lor r \lor s,\ p\}$.
• Cláusula vacía $\square$: la que no tiene literales. Es insatisfacible (equivale a $F$).
• Cláusula de Horn: tiene como mucho un literal positivo. Es la base de Prolog.

Toda fórmula se puede pasar a FNC:

1. Eliminar $\leftrightarrow$: $F \leftrightarrow G \equiv (F \to G) \land (G \to F)$.
2. Eliminar $\to$: $F \to G \equiv \lnot F \lor G$.
3. Meter las negaciones hacia dentro (De Morgan) y quitar las dobles.
4. Distribuir $\lor$ sobre $\land$: $F \lor (G \land H) \equiv (F \lor G) \land (F \lor H)$.
5. Simplificar: quitar las cláusulas con un literal y su complementario (son tautologías), los literales repetidos y las absorciones.

Resolución (Robinson, 1965)

Usa una sola regla de inferencia. Es poco intuitiva para una persona, pero muy fácil de automatizar.

Se prueba por refutación (Teorema II): para demostrar $\Gamma \models Q$, se demuestra que $\Gamma \cup \{\lnot Q\}$ es inconsistente derivando la cláusula vacía:

Algoritmo:

1. Pasar a FC las premisas y la negación de la conclusión.
2. Elegir dos cláusulas resolubles respecto a un literal (un par que no se haya usado antes) y añadir su resolvente.
3. Si sale $\square$: conjunto inconsistente, el razonamiento es correcto.
4. Si ya se han resuelto todos los pares posibles sin llegar a $\square$: consistente, el razonamiento no es correcto.

Deducción natural (Gentzen, 1935)

Imita la forma de razonar de las personas. Tiene dos reglas por conectiva: una para introducirla (I) y otra para eliminarla (E).

Las reglas que empiezan "suponiendo…" abren una caja (un supuesto provisional). Lo deducido dentro de la caja solo vale dentro de ella, hasta que se cierra con la regla.

Resumen: cómo comprobar si un razonamiento es correcto