Lógica

Metateoremas

Los capítulos anteriores presentaron teoremas dentro del sistema formal: equivalencias y propiedades de los operadores proposicionales. Este capítulo se mueve un nivel hacia arriba: los metateoremas son enunciados acerca del sistema formal mismo. No hablan de expresiones booleanas particulares, sino de qué se puede hacer con los teoremas como objetos.

Definición 1 — Metateorema

Un metateorema es un enunciado sobre el sistema formal que describe una propiedad general de los teoremas o de los métodos de demostración. Mientras que un teorema es una expresión del lenguaje formal que se demuestra igual a ⊤\top, un metateorema dice algo sobre esas expresiones: por ejemplo, que cierta operación aplicada a teoremas produce otro teorema.

La distinción es sutil pero importante. El teorema p⇒p∨qp \Rightarrow p \lor q es una expresión del lenguaje formal. En cambio, el enunciado "si P⇒QP \Rightarrow Q es un teorema, entonces P∧R⇒Q∧RP \land R \Rightarrow Q \land R es un teorema" es un metateorema: habla sobre qué ocurre cuando manipulamos teoremas.

Metateorema de la deducción

El metateorema más utilizado en la práctica justifica el método de demostración directa.

Teorema 1 — Metateorema de la deducción

Si al agregar P1,…,PnP_1, \ldots, P_n como axiomas al sistema formal (tratando sus variables como constantes) podemos derivar QQ, entonces:

P1∧⋯∧Pn⇒QP_1 \land \cdots \land P_n \Rightarrow Q

es un teorema del sistema original.

▶Demostración

La idea central es que toda demostración que usa PiP_i como axioma puede transformarse mecánicamente en una demostración de P1∧⋯∧Pn⇒QP_1 \land \cdots \land P_n \Rightarrow Q. Cada paso que invocaba PiP_i se reemplaza por una aplicación de la identidad de ∧\land (Pi∧⊤≡PiP_i \land \top \equiv P_i) y debilitamiento. La transformación es larga pero sistemática.

QED

Este metateorema es la base formal del método de "suponer el antecedente y demostrar el consecuente". Cuando escribimos "supongamos PP" y derivamos QQ, estamos aplicando exactamente este principio.

Metateorema de análisis por casos

Teorema 2 — Metateorema de análisis por casos

Si E[z:=⊤]E[z := \top] y E[z:=⊥]E[z := \bot] son ambos teoremas, entonces E[z:=p]E[z := p] es un teorema para toda variable pp.

▶Demostración

Por Shannon:

E[z:=p]≡(p∧E[z:=⊤])∨(¬p∧E[z:=⊥])E[z := p] \equiv (p \land E[z := \top]) \lor (\neg p \land E[z := \bot])

Si E[z:=⊤]E[z := \top] es un teorema, por identidad de ∧\land el primer conjuntor se reduce a pp. Si E[z:=⊥]E[z := \bot] es un teorema, el segundo se reduce a ¬p\neg p. Luego:

E[z:=p]≡p∨¬p≡⊤E[z := p] \equiv p \lor \neg p \equiv \top

y por tanto E[z:=p]E[z := p] es un teorema.

QED

En la práctica, esto significa que para demostrar un teorema podemos considerar por separado los casos p=⊤p = \top y p=⊥p = \bot para alguna variable pp que aparezca en la expresión.

Metateorema de equivalencia

Teorema 3 — Dos teoremas cualesquiera son equivalentes

Si PP y QQ son ambos teoremas, entonces P≡QP \equiv Q es un teorema.

▶Demostración

Si PP es un teorema, existe una demostración que transforma PP en ⊤\top. Análogamente, si QQ es un teorema, existe una que transforma QQ en ⊤\top. Por transitividad de ≡\equiv, se puede encadenar P≡⊤≡QP \equiv \top \equiv Q.

QED

Este metateorema nos dice que en el universo de los teoremas, la equivalencia es trivial: todos son equivalentes entre sí (pues todos equivalen a ⊤\top). Su utilidad real aparece como contrarrecíproco: si P≡QP \equiv Q no es un teorema, entonces PP y QQ no pueden ser ambos teoremas.

Metateorema de monotonía de ∨\lor

Teorema 4 — Monotonía de ∨\lor

Si P⇒QP \Rightarrow Q es un teorema, entonces P∨R⇒Q∨RP \lor R \Rightarrow Q \lor R es un teorema.

▶Demostración

Partimos del consecuente, que tiene más estructura:

Q∨RQ \lor R

Por la definición de implicación, P⇒Q≡P∨Q≡QP \Rightarrow Q \equiv P \lor Q \equiv Q. Sustituyendo QQ por P∨QP \lor Q:

P∨Q∨RP \lor Q \lor R

Y por debilitamiento, P∨R⇒P∨Q∨RP \lor R \Rightarrow P \lor Q \lor R. Combinando con P∨Q∨R≡Q∨RP \lor Q \lor R \equiv Q \lor R, obtenemos P∨R⇒Q∨RP \lor R \Rightarrow Q \lor R.

QED

La monotonía nos permite "agregar un disjunto" a ambos lados de una implicación sin perder validez.

Metateorema de monotonía de ∧\land

Teorema 5 — Monotonía de ∧\land

Si P⇒QP \Rightarrow Q es un teorema, entonces P∧R⇒Q∧RP \land R \Rightarrow Q \land R es un teorema.

▶Demostración

Por la definición de implicación, P⇒Q≡P∧Q≡PP \Rightarrow Q \equiv P \land Q \equiv P. Reemplazamos PP por P∧QP \land Q en la expresión P∧RP \land R, obteniendo P∧Q∧RP \land Q \land R. Por debilitamiento, P∧Q∧R⇒Q∧RP \land Q \land R \Rightarrow Q \land R.

QED

La monotonía de ∧\land es el dual: permite "mantener una conjunción" a ambos lados de una implicación.

Metateorema de dualidad

Teorema 6 — Dualidad

Si EE es un teorema del cálculo proposicional, entonces la expresión EDE^D obtenida al intercambiar simultáneamente ∨\lor con ∧\land, ⊤\top con ⊥\bot y ⊥\bot con ⊤\top en EE también es un teorema.

▶Demostración

La dualidad se sigue de la negación y la doble negación. Negar una expresión intercambia ∨\lor y ∧\land (por De Morgan) y ⊤\top y ⊥\bot (por ¬⊤≡⊥\neg\top \equiv \bot y ¬⊥≡⊤\neg\bot \equiv \top). Si EE es un teorema, entonces E≡⊤E \equiv \top, y por tanto ¬E≡⊥\neg E \equiv \bot. Pero ¬E\neg E tiene la estructura dual de EE. Aplicando doble negación se recupera una expresión equivalente a EDE^D.

Más concretamente: si E≡⊤E \equiv \top, entonces ¬E≡⊥\neg E \equiv \bot. La expresión ¬E\neg E es equivalente a ED[p:=¬p,q:=¬q,…]E^D[p := \neg p, q := \neg q, \ldots] (por De Morgan aplicado recursivamente). Sustituyendo de vuelta, se obtiene que EDE^D es un teorema.

QED

La dualidad explica por qué los teoremas del cálculo vienen en pares. Por ejemplo, la dominación p∨⊤≡⊤p \lor \top \equiv \top tiene como dual p∧⊥≡⊥p \land \bot \equiv \bot. La absorción p∧(p∨q)≡pp \land (p \lor q) \equiv p tiene como dual p∨(p∧q)≡pp \lor (p \land q) \equiv p. Las leyes de De Morgan son duales entre sí. En la práctica, cada vez que demostramos un teorema, obtenemos su dual gratis.

Metateorema del testigo

Teorema 7 — Metateorema del testigo

Para cualquier expresión EE del tipo apropiado:

P[x:=E]⇒(∃x:P(x))P[x := E] \Rightarrow (\exists x : P(x))

Este metateorema se trató en detalle en el capítulo de existencia y unicidad. El teorema del testigo opera al nivel de cómo demostramos enunciados existenciales: exhibir un testigo y verificar la propiedad es suficiente para concluir la existencia.

Resumen

MetateoremaForma
DeducciónSi asumiendo PP se puede derivar QQ, entonces P⇒QP \Rightarrow Q es un teorema
Análisis por casosSi E[⊤]E[\top] y E[⊥]E[\bot] son teoremas, E[p]E[p] es un teorema
EquivalenciaSi PP y QQ son teoremas, P≡QP \equiv Q es un teorema
Monotonía de ∨\lorSi P⇒QP \Rightarrow Q es un teorema, P∨R⇒Q∨RP \lor R \Rightarrow Q \lor R es un teorema
Monotonía de ∧\landSi P⇒QP \Rightarrow Q es un teorema, P∧R⇒Q∧RP \land R \Rightarrow Q \land R es un teorema
DualidadSi EE es un teorema, su dual EDE^D (intercambiando ∨↔∧\lor \leftrightarrow \land, ⊤↔⊥\top \leftrightarrow \bot) también lo es
TestigoP[x:=E]⇒(∃x:P(x))P[x := E] \Rightarrow (\exists x : P(x))