Un sistema intuicionista de cálculo proposicional

Según Hilbert y Ackermann, el intuicionismo "rechaza por principio la noción de que a todas las aserciones matemáticas haya de corresponder uno de los valores, «verdadero» o «falso»", y eso debido a que "en su opinión [del intuicionismo] se oculte aquí el supuesto infundado de que sería posible resolver alguna vez todos los problemas matemáticos¹.

Por ende, para representar conexiones lógicas entre proposiciones en un sistema donde rija tal principio, el significado de los signos conectivos no será,, como lo son habitualmente, funciones veritativas.

En lugar de los valores verdad puede usarse el concepto de construcción de una proposición, es decir de demostración mediante razonamientos correctos desde este punto de vista. Así, a partir de «φ ∧ ψ» pueden construirse tanto «φ» como «ψ»; y de cualquiera de éstos últimos se puede construir «φ ∨ ψ», etc. (ver más adelante).

Hay ejemplos de fórmulas que en la lógica clásica son válidas universalmente, mas no para la intuicionista. Por ejemplo «A ∨ ¬A». Tampoco lo son, intuicionísticamente, las fórmulas «¬¬A → A», «(¬B → ¬A) → (A → B)», «A ∨ (A → B)», «(A → B) ∨ (B → A)» ni «(A → B) → ¬A ∨ B»; todas ellas válidas en el cálculo proposicional de, por ejemplo, este otro post.

_____________________

En lugar de fórmulas elementales o axiomas, partiremos de ciertas relaciones fundamentales de deductibilidad. A saber:

1. Φ_n es deducible de las hipótesis Φ₁, ..., Φn (n ≥ 1)

2. Φ ∧ Ψ es deducible de las hipótesis Φ, Ψ

3. Φ es deducible de Φ ∧ Ψ

4. Φ ∨ Ψ es deducible de Φ

5. Φ ∨ Ψ es deducible de Ψ

6. Ψ es deducible de Φ, Φ → Ψ

7. La fórmula arbitraria Ψ es deducible de Φ, ¬Φ



También existen las siguientes reglas:

I. Si «Ψ» es deducible de «Φ₁, ..., Φ_n», también lo es de toda permutación de «Φ₁, ..., Φ_n»

II. Si la fórmula «Γ» es deducible de «Ψ₁, ..., Ψ_k», y cada una de estas últimas fórmulas es deductible de «Φ₁, ..., Φ_n», «Γ» es asimismo deductible de «Φ₁, ..., Φ_n».

III. Si la fórmula «Δ» es deducible de «Φ₁, ..., Φ_n», «Ψ» y es deducible de «Φ₁, ..., Φ_n», «Γ», también es deducible, «Δ», de «Φ₁, ..., Φ_n», «Φ ∨ Ψ» (n ≥ 0).

IV. Si la fórmula «Γ» es deductible de «Φ₁, ..., Φ_n», «Ψ», también es la fórmula «Ψ → Γ» deductible de «Φ₁, ..., Φ_n» (n ≥ 0)

V. Si la fórmula «Γ» es deductible de «Φ₁, ..., Φ_n», «Ψ» y también «¬Γ» es deductible de las mismas hipótesis, la fórmula «¬Ψ» es deductible de «Φ₁, ..., Φ_n» (n ≥ 0)

(Seguir leyendo)
________
Notas.
1. Hilbert y Ackermann, Elementos de lógica teórica. Cap. 1, §10.

La paradoja del mentiroso

La antinomia del mentiroso puede parecer una mera curiosidad histórica, pero también parece que fue el punto de partida contingente de diversas especulaciones en la historia.

Una formulación de la misma*, publicada por Tarski, es como sigue:

_______________
Sea S un enunciado cualquiera que comience con las palabras «Todo enunciado».

Llamamos S' a un enunciado obtenido a partir de S así:
 - Reemplazamos en S la primera palabra «Todo» por «El»
 - Insertamos, después de la sgunda palabra («enunciado») toda la frase S entre comillas.

Llamamos autoaplicable al enunciado S, si S' es verdadero y no autoaplicable si no lo es.

Sea pues el siguiente enunciado:

(1)     Todo enunciado es no autoaplicable.

El enunciado correlativo sería:

(2)     El enunciado "Todo enunciado es no autoaplicable" es no autoaplicable.

______________

En este enlace puede leerse un diálogo, o a lo sumo un hilo de un foro, que al lector puede interesar, que toma su punto de partida en ella.

He aquí otro post donde también se aborda el tema, pero de otra manera, de mayor interés, creo.
____________
*Nota: Esta formulación se extrajo de Tarski, A., La concepción semántica de la verdad y los fundamentos de la semántica, Ed. Nueva Visión, Bs. As., 1972.

Forma normal conyuntiva

A todo esquema de argumento (o "forma proposicional") de la lógica proposicional puede dársele una forma que se llama "normal conyuntiva" (o conjuntiva) FNC.

Esta forma se define así (téngase presente que nos estamos refiriendo a una lógica de proposiciones):

1. Sólo están presentes, de entre los signos conectivos lógicos, los siguientes: ¬, ∧ y ∨.

2. Los signos de negación sólo afectan a expresiones simples, quiero decir, sólo a variables. Dicho de otra manera: no afecta a ningún ¬, ∧ ni ∨; de modo que ni ¬¬p ni ¬(p ∧ q) ni ¬(p ∨ p) están en FNC.

3. Ningún signo «∧» puede estar encerrado en alguna disyunción. Así, la fórmula  p ∨ ( p ∧ q) no está en FNC, pero sí lo está (p ∨ p) ∧ (p ∨ q).

De este modo, una "forma normal conyuntiva" es una conjunción (como: P₁ ∧ P₂ ∧ ... ∧ P_n ) en la que cada miembro P_i consiste en alguna disyunción de variables proposicionales (negadas o no) o en una variable (negada o no).

Mostraremos ahora eso de que todo esquema proposicional puede ser llevado a uno equivalente pero de esta forma. Para ello, podemos recurrir a las transformaciones siguientes:

I. Puede ocurrir que querramos dar forma normal conjuntiva a una "forma proposicional" como «p → q» o a una como «p ↔ q».

En el primero de estos dos casos procedemos teniendo en cuenta lo siguiente: 

p → q  ≡ ¬p ∨ q

En el segundo tendremos en cuenta:

p ↔ q  ≡  (p → q) ∧ (p → q)

de donde llemagmos a:

p ↔ q  ≡  (¬p ∨ q) ∧ (¬q ∨ p)

Otra equivalencia útil en este punto es:

p ↔ q  ≡  (p ∧ q) ∨ (¬p ∧ ¬q)

II. Cuando la negación no cumple con 2., entonces tenemos en cuenta las leyes de De Morgan.

III. Si tenemos alguna sucesión de negaciones, consideramos la equivalencia: ¬¬p ≡ p

IV. Puede ocurrir, lo hace de hecho lo hace, que tengamos algo como:

p ∨ (q ∧ r)

Pero esto es manifiestamente contrario a 3. Aplicamos la "ley distributiva" siguiente:

p ∨ (q ∧ r)  ≡  (p ∨ q) ∧ (p ∨ r)

que nos recuerda la matemática que veíamos en el colegio [por ejemplo: a(b + c) = ab + ac].

Veamos ahora el siguiente ejemplo¹:

(1)   (p → q) ↔ (¬q → ¬p)

Transformamos los condicionales:

(¬p ∨ q) ↔ (¬¬q ∨ ¬p)

Ahora la equivalencia:

[¬(¬p ∨ q) ∨ (¬¬q ∨ ¬p)]  ∧  [¬(¬¬q ∨ ¬p) ∨ (¬p ∨ q)]

De Morgan:

[(¬¬p ∧ ¬q) ∨ (¬¬q ∨ ¬p)]  ∧  [(¬¬¬q ∧ ¬¬p) ∨ (¬p ∨ q)]

Simplificamos las doble-negaciones:

[(p ∧ ¬q) ∨ (q ∨ ¬p)]  ∧  [(¬q ∧ p) ∨ (¬p ∨ q)]

Ahora distribuimos y obtenemos el siguiente esquema de forma conyuntiva normal:

(2) (p ∨ q ∨ ¬p) ∧ (¬q ∨ q ∨ ¬p)  ∧  (¬q ∨ ¬p ∨ q) ∧ (p ∨ ¬p ∨ q)

En la forma que nos ocupa durante este post es posible comprobar si se trata de un esquema válido de un modo breve. Para corroborar que así sea, basta ver que en cada una de las conyunciones (cada una de las partes de la «forma conjuntiva normal» de que se trate) haya alguna variable y a la vez su negación.

Por ejemplo en (2) tenemos cuatro disyunciones agrupadas en una conjunción. La primera de ellas tiene 'p' y '¬p', la segunda 'q' y '¬q', la tercera también 'q' y '¬q' y la última 'p' y '¬p'. Así, podemos concluir que (1) es válida universalmente o, en otros términos, que es una tautología.

De un modo completamente análogo, en un esquema presentado en la forma normal disyuntiva (no veremos qué es esto en el presente post) puede verse si es una contradicción.

Al lector podrá serle de utilidad el ejecicio siguiente:

Dar forma conyuntiva normal al esquema «(p ∧ ¬p) ∨ (q ∧ ¬q)»

________

1. El ejemplo así como el resto del contenido en el post está presente en Grundzüge det theoretischen logik de Hilbert y Ackermann, traducido como Elementos de lógica teórica.