jueves, 7 de noviembre de 2013

~p → r →. p → r → r


1.  ~p → ~~p →. ~p → ~p →. ~~p
     Sustitución,
p → ~q →. p → q →. ~p

2.  ~p → p → p
     tertium non datur


3.  ~p → p → p →. [q → p →. ~p → p] →. q → p → p
     Transitividad de →


4.  [q → p →. ~p → p] →. q → p → p
     Modus ponens (3 y 2)


5.  ~p → q →. q → p → p
     Regla de transitividad, (1 y 4
)

miércoles, 30 de octubre de 2013

p → q →. p → ~q → ~p

(a)  [p →. q → ~.p → p] →. p → q →. p → ~.p → p
     Regla 2, Axioma 2

(b)  [~q →. q → ~.p → p] →. p → ~q →. p →. q → ~.p → p
     Regla 2, transitividad de →

(c)  ~q →. q → ~.p → p
     Regla 2, ex falso sequitur quodlibet
(d)  p → ~q →. p →. q → ~.p → p
     Regla 1, b y c

(e)  p → ~q →. p → q →. p → ~.p → p
     Lema 3, d y a

(f)  p → ~[p → p] → ~p →. [p → q →. p → ~[p → p]] →. p → q →. ~p
     Regla 2, transitividad de →


g  [~p →. p → p] →. ~[p → p] → ~~p
    Modus tollens


h  ~[p → p] → ~~p
     Regla 1, g y ex falso sequitud quodlibet

i   ~~p → p →. ~[p → p] → ~~p →. ~[p → p] → p
    transitividad de →

j   ~[p → p] → p
    Regla 1, i y Doble negación, y Regla 1, h.

k   p → ~[p → p] → p
     Lema 1, j


l  [p → q →. p → ~[p → p]] →. p → q → ~p
     Regla 1,  f y k

m  p → ~q →. p → q →. ~p
     Lema 3, e y l

miércoles, 23 de octubre de 2013

p →. ~q → ~[p → q]

Una prueba de  p →. ~q → ~[p → q]
 


(a) p → q → q →. ~q → ~[p → q]
    Sust., Modus tollens

(c) p → q →. p → q
    Sust., reflexividad de →

(d) p → q → p →. p → q → q
    Lema 2, (c)

(f) p →. p → q → p →. p → q → q
    Modus ponens, (d)

(g) [p →. p → q → p] →. p →. p → q → q
    Lema 2, (f)

(h) p →. p → q → p
    Sust., Axioma 1

(i) p →. p → q → q
    Modus ponens, (g y h)

(j) p →. q → ~[p → q]
    Lema 3, (a e i)

miércoles, 28 de agosto de 2013

Una numeración para fórmulas

En este blog, al escribir fórmulas de la lógica proposicional, usamos la convención que resulta en lo siguiente:

En una fórmula, a falta de corchetes, se agrupa primero el que se encuentra a la izquierda, es decir que prevalece el de la derecha. Así, de estas dos últimas fórmulas, p → q → p es la segunda. Por otra parte, puede figurar un punto junto a una flecha, así: "→.", lo cual significa que desde el lugar donde se coloca el punto habrá un corchete izquierdo que se cerrará con uno derecho ubicado al final de la fórmula, salvo que dicho punto se encuentre encerrado entre corchetes, en cuyo caso el derecho correspondiente al que se ubica en el lugar del punto estará inmediatamente antes que el derecho que cierra la subfórmula entre corchetes donde se encuentra el punto.

Numeramos los símblos de esta manera:

1 [
2 →
3 ]
4 ~

Para ordenar las fórmulas haremos así: se genera el código asociado de cada fórmula y se ordena alfabéticamente colocando primero las letras y luego los números (que representan los símbolos impropios). Recuérdese que a nunguna fórmula bien formada pueden faltar los corchetes extremos. Así, p no es bien formada mienbtras que [p] sí lo es. Para evitar la excesiva sobreabundancia de corchetes, para la negación usaremos la cantidad mínima para que no haya equivocidad. Se agrupará antes una ~ que un →.

domingo, 18 de agosto de 2013

p → q → p → p


1.   p → q → p →. ~p → ~.p → q
     Sustitución en modus tollens

2.   [~p →. p → q] →. ~p → ~[p → q] →. ~~p
     Sustitución en reductio ad absurdum
 

3.  [~p → ~.p → q] → ~~p
     Modus ponens (2 y Ex falso sequitur quodlibet)
 

4.   p → q → p → ~~p
     Regla de Transitividad (1 y 3)

5.   p → q → p → p
     Regla de Transitividad (4 y Doble negación)



Esta la fórmula ha de escribirse, en su forma desplegada : [[[p → q] → p] → p]. Según las convenciones adoptadas por Church se escribe también como figura en el título y en (5).

viernes, 16 de agosto de 2013

p →. p → q → q

1.  p → q →. p → q
     Por reflexividad de →

2.  p → q → p →. p → q → q
     Lema 2, 1

3.  p →. p → q → p →. p → q. → q
     Lema 1, 2

4.  p → [p → q → p] →. p → .p → q. → q
     Lema 2, 3

5.  p → .p → q → q
     Modus Ponens 1 y 4

 Esta fórmulas, una vez restaurados los paréntesis, se escribe: [p → [[p → q] → q]].

viernes, 7 de junio de 2013

Equivalencia entre cuantificaciones

Hemos visto aquí que podía, una vez introducido el cuantificador universal, intruducirse 'por definición' el existencial con la siguiente fórmula: (∃a)A ≡df ~(a)~A.

Esto significa que el universar está implicitamente definido en los axiomas mientras que el otro a partir de él. Facil resulta probar, dada la definición, que ~(∃a)A ≡ (a)~A, que (∃a)~A ≡ ~(a)A y que y ~(∃a)~A ≡ (a)A; y en todo caso lo dejaremos para el lector.

Por otra parte, en la deducciónnatural, no se introduce un por defición y otro en los axiomas. De hecho, no hay axiomas sino reglas en los cuales está implícita su definición sintáctica. Por su puesto que no se debe ni al azar ni a ninguna armonía prestablecida que las equivalencias se cumplan en este sistema, pues al elaborárselo eran condición suya. Pero veamos cómo probarlas en él.

Primero: (x)A ≡ ~(∃x)~A

1 (x)A                     sup
2 (∃x)~A                 sup
3 ~A                       sup
4 A                         E∀, 1
5 ⊥                        3 y 4
6 ~A → ⊥                T.D. (3 a 5)
7 ⊥                         E∃ (2 y 6)
8 ~(∃x)~A                 RAA (2 - 7)
9 (x)A → ~(∃x)~A      T.D. (1 a 8)

1 ~(∃x)~A             sup
2 ~A                     sup
3 (∃x)~A               I∃ 2
4 ⊥                      1 y 3
5 ~~A                    RAA (2-4)
6 A                       Dneg
7 (x)A                    I ∀
8 ~(∃x)~A → (x) A   T.D. (1 a 7)


Ahora: ~(a)~A ≡ (∃a)A

1 ~(x)~A                     sup
2 ~(∃x) A                    sup
3 A                             sup
4 (∃x) A                     I∃, 3
5 ⊥                            2 y 4
6 ~A                           RAA (3-5)
7 (x)~A                        I∀, 6
8 ⊥                            1 y 7
9 ~~(∃x) A                   RAA(2-8)
10 (∃x) A                    D.Neg
11 ~(x)~A → (∃x) A      T.D. (1 a 10)


Y los restantes pueden ser tarea del lector.

sábado, 13 de abril de 2013

Sustitutividad de la equivalencia, segunda parte.

Ahora consideremos, siguiendo con el post anterior sobre la sustitutividad de la equivalencia, que se realiza la sustitución y hay alguna ocurrencia en A de algún →, ~ o ∀. 

Existen tres casos: 

1) A es A₁ → A₂, 

2)A es ~A₁ y 

3) A es ∀xA₁. 


Primer caso: A es A₁ → A₂

Aquí (salvo en el caso a, ver post anterior) B es B₁ → B₂ donde B₁ y B₂ resultan por sustitución de M por N en A₁ y A₂. Por hipótesis de inducción:


*1) ∀x₁x₂...nₙ[M ≡ N] →. A₁ ≡ B₁ y
*2) ∀x₁x₂...nₙ[M ≡ N] →. A₂ ≡ B₂


Necesitamos probar, entonces, que de (*1) y (*2) se sigue el teorema.

Primero probemos T₁:

p → q →. r → s →. q → r →. s → t

Cuando figuren dos letras proposicionales una al lado de la otra así: pq, significará [p → q].

a) pq →. qr →. ps
transitividad de →

b) ps →. st →. pt
transitividad de →

c) [ps →. st → pt] →. qr → ps →. qr →. st → pt
transitividad de →

d) qr → ps →. qr →. st → pt
modus ponens (c y b)

e) pq →. qs →. st → pt
Regla de transitividad, (a y d)

f) p → qr →. q → pr
ley de conmutación

g) [qs →. st → pt] →. st →. qs → pt
R2, (f)

h) pq →. st →. qs → pt
Regla de transitividad (e y g)

Ahora probemos T₂: 

[p →. q → rs] →. pq →. pr → ps

a) [p →. r → s] →. pr → ps
Axioma 2

b) [p →. q → rs] →. pq →. p → rs
Axioma 2

c) [p → rs →. pr → ps] →. [pq →. p → rs] →. pq →. pr → ps
ley de transitividad de → 2

d) [pq →. p → rs] →. pq →. pr → ps
modus ponens (c y a)

e) [p →. q → rs] →. pq →. pr → rs
Regla de transitividd, (b y d)


Ahora escojamos cinco fórmulas cuales quiera A₁, A₂, B₁, B₂ y C tales que sea

*11) ⊢ C →. A₁ → B₁, ⊢ C →. A₂ → B₂
*12) ⊢ C →. A₂ → B₂ y ⊢ C →. A₂ → B₂

(es decir ⊢ C →. A₁ ≡ B₁ y ⊢ C →. A₂ ≡ B₂)

Tenemos:

a) B₁ → A₁ →. A₂ → B₂ →. A₁ → A₂ →. B₁ → B₂ y
b) A₁ → B₁ →. B₂ → A₂ →. B₁ → B₂ →. A₁ → A₂
ambos por regla 2, T₁.

Sustituyendo en T₂, obtenemos (c) y (d):

c) [C →. B₁A₁ →. A₂B₂ →. A₁A₂ → B₁B₂] →. C → B₁A₁ →. C → A₂B₂ →. C →. A₁A₂ → B₁B₂
d) [C →. A₁B₁ →. B₂A₂ →. B₁B₂ → A₁A₂] →. C → A₁B₁ →. C → B₂A₂ →. C →. B₁B₂ → A₁A₂

Luego:

e) C →. B₁A₁ →. A₂B₂ →. A₁A₂ → B₁B₂
Lema 1, (a)
f) C →. A₁B₁ →. B₂A₂ →. B₁B₂ → A₁A₂
Lema 1, (b)

Y entonces

h) C → B₁A₁ →. C → A₂B₂ →. C →. A₁A₂ → B₁B₂
i) C → A₁B₁ →. C → B₂A₂ →. C →. B₁B₂ → A₁A₂

ambos por modus ponens (c y e) y (d y f). Esto se cumple para cualesquiera fórmulas (bf) C, A₁, A₂, B₁ y B₂.

Ahora sustituímos C por ∀x₁x₂...nₙ[M ≡ N] (regla de sust.), con lo cual obtenemos:

h') [∀x₁x₂...nₙ[M ≡ N] →. B₁ → A₁] →. [∀x₁x₂...nₙ[M ≡ N] →. A₂ → B₂] →. ∀x₁x₂...nₙ[M ≡ N] →. A₁ → A₂ →. B₁ → B₂

i') [∀x₁x₂...nₙ[M ≡ N] →. A₁ → B₁] →. [∀x₁x₂...nₙ[M ≡ N] →. B₂ → A₂] →. ∀x₁x₂...nₙ[M ≡ N] →. B₁ → B₂ → A₁ → A₂


Entonces (recuérdense las hipótesis de la inducción *1 y *2):

j) [∀x₁x₂...nₙ[M ≡ N] →. A₂ → B₂] →. ∀x₁x₂...nₙ[M ≡ N] →. A₁ → A₂ →. B₁ → B₂
modus ponens, (h' y *1)

k) ∀x₁x₂...nₙ[M ≡ N] →. A₁ → A₂ →. B₁ → B₂
modus ponens, (j y *2)

l) [∀x₁x₂...nₙ[M ≡ N] →. B₂ → A₂] →. ∀x₁x₂...nₙ[M ≡ N] →. B₁ → B₂ → A₁ → A₂
modus ponens, (i' y *1)

m) ∀x₁x₂...nₙ[M ≡ N] →. B₁ → B₂ → A₁ → A₂
modus ponens (l y *2)

Y como A es A₁ → A₂ y B es B₁ → B₂, luego hemos probado:

n) ∀x₁x₂...nₙ[M ≡ N] →. A ≡. B

Ahora el segundo caso: A es ~A₁

Así, B es ~B₁ y nuestra hipótesis de inducción establece que

*) ∀x₁x₂...nₙ[M ≡ N] →. A₁ ≡ B₁

Debemos probar

[C →. q ≡ r] →. C → ~q ≡ ~r

y sustutuir C por la hipótesis, q por A₁ y r por B₁ para obtener por modus ponens lo que queremos, de modo similar al primer caso.

Sabemos por el axioma 3 y por modus tolens que:

a) q ≡ r →. ~q ≡ ~r

Por otra parte:

b) p → q →. C →. p → q
Axioma 1

c) [C →. p → q] →. C → p →. C → q
Axioma 2

d) [C →. q ≡ r →. ~q ≡ ~r] →. C → q ≡ r →. C →. ~q ≡ ~r
Sustituyendo en (b)

e) C →. q ≡ r →. ~q ≡ ~r
lema 1, (a)

f) C → q ≡ r →. C →. ~q ≡ ~r
modus ponens (d y e)

Finalmente, nos queda el tercer caso: A es ∀xA₁

Aquí, B es ∀xB₁. hay que probar:

A ≡ₓ B →. (x)A ≡ (x)B

Y con eso obtenemos la prueba utilizando la transitivida de →.

Sabemos, desde luego, que:

a) A ≡ B →. A → B y

b) A ≡ B →. B → A , por la definición de ≡.

c) ∀x[A ≡ B] →. A → B
regla 5 y reflexividad de →

d) ∀x[A ≡ B] →. ∀x[A → B]
Lema 4

e) (x)A → A
regla 5

f) [p →. q → r] →. s → q →. p → s → r
ver prueba

g) [A ≡ₓ B →. A → B] →. (x)A → A →. [A ≡ₓ B →. (x)A → B]
sust, (f)

h) (x)A → A →. [A ≡ₓ B →. (x)A → B]
modus ponens, (g y c)

i) A ≡ₓ B →. (x)A → B
modus ponens, (h y e)

j) A ≡ₓ B →. (x)A →ₓ B
lema 4, i

k) (x)A →ₓ B →. (x)A → (x)B
Axioma 4

l) A ≡ₓ B →.(x)A → (x)B
Regla de transitividad

viernes, 12 de abril de 2013

Sustitutividad de la equivalencia

El sistema axiomático de Nicod-Lukasievicz se caracteriza por bastar para abarcar a la lógica proposicional en su conjunto, quiero decir, para probar cada uno de sus teoremas, y no contar más que con un solo teorema y dos reglas de inferencia. Su nombre tiene el de dos personas pues la primera de ellas no dió su versión definitiva sino que su versión del axioma difería en el número de variables proposicionales del de la segunda según quien, por otra parte, había omitido explicitar que el sistema incluía la regla de sustitución −además de faltarle un paso en la demostración de la reflexividad de → al publicarlo−, (ver).

Tal regla de sustitución, que puede encontrarse como conformando este sistema axiomático de lógica de primer orden, afirma que una variable proposicional puede ser sustituída por una fórmula cualquiera constituyendo un paso válido de prueba.

Algunos sistemas axiomáticos prescinden de ella. Por ejemplo, si el citado es reemplazado por uno en que en lugar de los axiomas presentara "esquemas de axiomas" de la misma forma pero que en lugra de p → [q → p], etc., sea A → [B → A], etc., donde A y B no son variables proposicionales sino lugares a ser ocupados por fórmulas cualesquiera; entonces la regla de sustitución podría ser una regla derivada (omitimos la prueba en este post).

Pero cuando hablamos de "sustitutividad de la equivalencia" nos referimos a una cosa completamente distinta. Con ello mentamos que si dos fórmulas son equivalentes y una de ella es una parte de una tercera, entonces la resultante de sustituir en esta última tal fórmula por la otra (su equivalente), es equivalente con ella. Por si resulta más claro, en símbolos:

Si M ≡ N, y si B resulta de sustituir N por M en A en cero o más lugares, entonces A ≡ B.

Es decir que B es S[N/M]A|, y que si ⊢ M ≡ N, luego ⊢ A ≡ B.

Una muy útil regla de inferencia que se sigue de ella es que si B es S[N/M]A|, si ⊢ M ≡ N y si ⊢ A, luego ⊢ B. Una muestra suficiente de su utilidad está en que con ella, en conjunto con algunos teoremas del cálculo restringido de predicados, puede probarse que cualquier fórmula tiene una equivalente en forma normal prenexa. Lo cual es un paso para una de las demostraciones de la completitud semántica de dicho cálculo. Probemosla, pues por inducción, según el número de ocurrencias de los signos →, ~ y ∀. Formulemos el teorema para la lógica de primer orden:

Si B resulta de A por sustitución de N por M en cero o más lugares de A (no necesariamente todas las ocurrencias de M en A), y si x₁, x₂, ..., xₙ es una lista de variables individuales que incluye al menos todas aquellas variables libres en M y en N que ocurren también como variables ligadas en A, entonces: ⊢ ∀x₁x₂...nₙ[M ≡ N] →. A ≡ B

Primero veamos los casos a) la sustitución de N por M tiene lugar en cero lugares en A, y b) M coincide con A y se sustituye una ocurrencia de M en A.

a) En este caso B es lo mismo que A por que se obtiene de A sin cambiar nada en ella. Luego,

∀x₁x₂...xₙ[M ≡ N] →. A ≡ B
es lo mismo que
∀x₁x₂...xₙ[M ≡ N] →. A ≡ A

Sustituyendo en el axioma 1 (ver post citado):

A ≡ A →. ∀x₁x₂...xₙ[M ≡ N] →. A ≡ A
Como A ≡ A (por reflexividad de la implicación material), luego, por modus ponens:

∀x₁x₂...xₙ[M ≡ N] →. A ≡ A

b) En este caso A es lo mismo que M y B lo mismo que N. De modo que:

∀x₁x₂...xₙ[M ≡ N] →. A ≡ B
en nada difiere de
∀x₁x₂...xₙ[A ≡ B] →. A ≡ B

Pero dicha fórmula se obtiene por medio del axioma 5 aplicado n veces y la regla de transitividad.


Debemos considerar ahora que se realiza la sustitución y hay alguna ocurrencia en A de algún →, ~ o ∀. 

Existen tres casos: 
1) A es A₁ → A₂,

2)A es ~A₁ y 

3) A es ∀xA₁. 

Lo que resta puede leerse en el siguiente post.

martes, 12 de marzo de 2013

Ley de reductio ad absurdum

La reductio ad absurdum es una manera muy habitual de proceder, no sólo dentro de la actividad deductiva. Básicamente, ella consiste en el rechazo del absurdo, que nuestra razón parece realizar espontáneamente. No es mi intención sin embargo dejar sentado este último aserto. Existen quienes (yo hablé con uno hace poco) niegan que, el otrora llamado animal racional, proceda ni aún las más de las veces de tal modo. Una posición en cierto modo sintética (y en sentido estricto, no) es la que considera la actividad humana como no rigiéndose todas las veces según ese principio, pero pudiendo hacerlo, aunque no particularmente inclinado a ello. En apoyo de tal idea del hombre se aboga, en numerosas oportunidades, el testimonio de la experiencia según la cual el mantenimiento estricto de las leyes de la lógica en el acto de pensar supone cierto esfuerzo a falta de cual no está garantizado. Así, el hombre sería libre de ser racional, pero pudiendo dar otros usos a su arbitrio. Aunque esto a riesgo de descaminarse, pues la verdad sólo puede ser racional, y cualquier afirmación que no lo sea será banal, no será, en rigor, más que nada.

Un inconveniente con dicha concepción fue señalado por el mismo Descartes en su cuarta meditación¹, pues no es lo mismo el error que la ignorancia. No es lo mismo, por ejemplo, pretender haber probado una contradicción, que no poseer la prueba de su negación. Tal y como lo apunta el filósofo, se trata de dos órdenes ditintos, los que Kant llama práctico y especulativo. Creer que uno ha probado una contradicción es un acto, así como lo es la restitución de un depósito por ejemplo. Hay actos encomiables y también los hay reprochables. Pero también hay otros que no son ni tanto ni tan poco. Las afirmaciones, se pueda o no decidir esto, son verdaderas o no lo son, tertium non datur.

Claro que esto último puede considerarse una posición un poco extrema. ¿No hay sistemas lógicos que no son binarios acaso? ¿Y eso no prueba su posibilidad? ¿Pero entonces son racionales o no?

En la modernidad se solía dividir las aguas de manera tajante: el conocimiento y el voluntad. Para Descartes es una confusión entre ambos la fuente del error:

"¿De dónde nacen, pues, mis errores? Nacen de que la voluntad, siendo mucho más amplia y extensa que el entendimiento, no se contiene dentro de los mismos límites, sino que se extiende, además, a las cosas que no comprendo, y, como de suyo es indiferente, se extravía con mucha facilidad y elige lo falso en lugar de lo verdadero, el mal en vez del bien; y esta es la causa por la cual me engaño y peco" (op. cit).

Se ve con claridad que la división no es completa. Uno podría deducirla de la misma exhortación que se hace para mantener la línea divisoria, pues si hay que advertir al respecto es porque, cuando menos, la confusión es una posobilidad. Esta misma conclusión puede obtenerse también sin apelar si quiera al modus tollens. El entendimiento es la facultad humana de concebir la verdad, expresada en sentencias, cuyo uso se consuma en la aseveración de las mismas. Toda aseveración es una acción humana. Por ende, el entendimeinto está subsumido (como bien afirmó Kant) a la praxis. De este modo, las discusiones sobre si el hombre es o no racional en el sentido en que sólo ha de sobordinarse al imperio de la razón es cuestión de razón práctica, no especulativa.

Podemos entonces proseguir describiendo en qué consiste esta ley de reducción al absurdo. Desde un punto de vista retórico, uno diría: se reduce el argumento que se quiere criticar a algún absurdo, es decir, se deduce de él una contradicción por todos conocida, y así se lo descarta. De modo formal diríamos: si una proposición permite inferir una contradición, entonces es falsa. Y la contradicción puede definirse con contar con dos proposiciones, una de las cuales es la negación de la otra, p y ~p. Así, en símbolos:

p → q, p → ~q ⊢ ~p

Usanto el teorema de la deducción podemos probar, en tres pasos:

p → q →. p → ~q → ~p (ley de reductio ad absurdum)

Pero procedamos ahora a demostrarla para esta formulación de la lógica proposicional de otra manera.

Primero probemos el converso del tercer axioma, a saber: p → q →. ~q → ~p.

1   q → ~~q →. p → q →. p → ~~q
    Ley de Transitividad-I.

2  p → q →. p → ~~q
     modus ponens, 1 y converso de doble negación.

3  ~~p → p →. p → ~~q →.~~p → ~~q
     Transitividad-I


4  p → ~~q →.~~p → ~~q
    modus ponens, 3 y doble negación

5  p → q →. ~~p → ~~q
    Regla de transitividad , 2, 4.

6   ~~p → ~~q →. ~q → ~p
     Axioma III

7   p → q →. ~q → ~p
     Regla de transitividad, 5 y 6.

Ahora consideremos que ~p es equivalente a p → ~[r → r] dado que el consecuente de eta fórmula es necesariamente falso y por lo tanto el condicional lo será también si (y sólo si) el antecedente es verdadero. Para probar esto escribimos:

1 ~p →. p → ~[r → r]
    EFSQ


2   p → ~[r → r] →. ~~[r → r] → ~p
     modus tollens

3   [p → ~[r → r] →. ~~[r → r]] →. p → ~[r → r] → ~p
     Lema 2,  2

4  ~~[r → r]
     R1: Doble negación y ref→

5  ~~[r → r] →. p → ~[r → r] →. ~~[r → r]
     R2: Ax1

6   p → ~[r → r] →. ~~[r → r]
     R1: 4 y 5

7   p → ~[r → r] → ~p
     R1: 3 y 6

Así:

* ~p ≡ p → ~[r → r]

Seguimos de este modo:

**  [p →. q → ~[r → r]] →. p → q →. p → ~[r → r]
     Axioma II

La equivalencia cuya prueba está dada arriba permitiría probar, en caso de contar con el teorema de sustitución de la equivalencia, con ** el teorema: p → ~q →. p → q → ~p, que no es otra cosa que una versión de la reducción al absurdo con las premisas permutadas. Como no usaremos ese teorma de sustitución recurriremos, primero, a la regla de la transitividad:

1  [~q →. q → ~[r → r]] →. p → ~q →. p →. q → ~[r → r]
    (ley de transitividad)

2  p → ~q →. p →. q → ~[r → r]
    modus ponens, 1 y *

3  p → ~q →. p → q →. p → ~[r → r]
    Regla de transitividad, 2 y **

4  p → ~[r → r] → ~p →. [p → q →. p → ~[r → r]] →. p → q →. ~p
    (segunda ley de transitividad)

5  [p → q →. p → ~[r → r]] →. p → q → ~p
    modus ponens 4 y *

6 *** p → ~q →. p → q →. ~p
   Regla de transitividad, 3 y 5.

Con esto hemos probado la reducción al absurdo, si bien con las premisas en el orden inverso al habitual. Para obtener esta última nos servimos de la ley de conmutación:

1  [p → ~q →. p → q →. ~p] →. p → q →. p → ~q →. ~p
    ley de conmutación
2  p → q →. p → ~q →. ~p
    modus ponens, 1 y ***


______________
1. Descartes, Meditaciones Metafísicas
2. Se trata de la segunda de las leyes de la transitivida de →, cuyas premisas conmutan las de la primera.

viernes, 1 de marzo de 2013

Ex falso sequitur quodlibet

La solución al primero de los ejercicios de este post, el cual consistía en demostrar que p ⊃ p, o sea la reflexividad de la implicación material, puede hallarse en este lugar (otra prueba pero basada en otros fundamentos, acá). Así que veamos en esta ocasión el que le sigue, que requería de la prueba del ex falso sequitur quodlibet (EFSQ), es decir de:

~p ⊃. p ⊃ q

Con esta ley ocurre que en caso de tener demostrada alguna fórmula y también su negación podría demostrarse cualquiera, de modo que ofrece importantes motivos para excluír toda contradicción del sistema, a fin de no volverlo superfluo. Dado que la demostración de una fórmula y su negación es en sí una contradicción, y que la contradicción es una fórmula necesariamente falsa, se entiende su nombre, que de lo falso se sigue cualquier cosa Veamos una prueba:

1 [~q → ~p →.p → q] → [~p → [~q → ~p →.p → q]]
 Axioma I, Sust.

2 ~p → [~q → ~p →.p → q] → [[~p →. ~q → ~p] → [~p →.p → q]]
  Axioma II, Sust.

3 ~q → ~p →.p → q
   Axioma III, Sust.

4 ~p → [~q → ~p →.p → q]
   modus ponens, 1 y 3.

5 [~p →. ~q → ~p] → [~p →.p → q]
  modus ponens, 2 y 4.

6 ~p →. ~q → ~p
  Axioma I, Sust.

7 ~p →.p → q
  modus ponens, 5 y 6.

Así como esta última fórmula, se puede probar desde luego otra versión del mismo principio en el cual se permutan las hipótesis, es decir de p →. ~p → q. Veamos.

1 p → ~~p
    doble negación¹

2 ~~p →. ~p → q
    EFSQ (infra)

3 [p → ~~p] → [~~p →. ~p → q → [p →. ~p → q]]
    ley de transitividad de →

4 ~~p →. ~p → q → [p →. ~p → q]
   modus ponens, 1 y 3.

5 p →. ~p → q
    modus ponens, 2 y 4.

 ______
1. El lector habrá notado que no figura en este post una prueba de esta ley de doble negación, ni se linkea una en él. Sin embargo, tal prueba puede ofrecerse, puede quedar para el interesado.

lunes, 25 de febrero de 2013

La transitividad como regla

El teorema p → q → [q → r →. p → r] una de cuyas pruebas figura acá, permite deducir una implicación en base a otros dos teoremas siempre que el antecedente de uno sea el consecuente del otro. Si esto último ocurre entonces podrá demostrarse la implicación del antecedente del segundo al consecuente del primero. Es decir, si ⊢ p → q y ⊢ q → r, entonces ⊢ p → r (si pueden demostrarse p → q y q → r, también puede demostrarse, entonces, p → r). Y la razón por la que esto ocurre así hay que buscarla, lógicamente, en la reflexividad de la implicación material¹.


En la lógica proposicional puede probarse una regla de transitividad. Sean A, B y C proposiciones bien formadas arbitrariamente escogidas, que incluyan cualquier número de variables, de conectivas y paréntesis; con la condición de que existan pruebas tanto para A → B como para B → C. Es decir, A implica B y B implica C. Ahora sustituímos en la ley de transitividad p/A, q/B y r/C, nos queda:

A → B → [B → C →. A → C]

Pero como convenimos en escoger A y B de modo tal que sabemos que A → B, luego, por modus ponens, tenemos:

B → C →. A → C

Nuevamente, como habíamos convenido en que B → C era una proposición necesariamente verdadera, luego:

A → C

Así, de ⊢ A → B y ⊢ B → C se sigue ⊢ A → C


____________
1. Ocurre de una manera similar a cuando decimos que un silogismo categórico compuesto de tres proposiciones universales afirmativas es válido. Este "modo" de silogismo, es decir, uno compuesto con tres proposiciones universales afirmativas, se ha dado en llamar BARBARA. ¿Por qué? Sencillamente, porque la proposición universal afirmativa, es decir una que predique algo de la totalidad de lo que pone como sujeto del asreto, se llama A. Como las tres llevan esa forma, tienen esa letra por nombre. En BARBARA encontramos esa letra tres veces. Digamos que no se ha encontrado una razón lógica para que sea así, es decir, por qué se han agregado las dos B y las dos R. Suele decirse que el listado de los modos (que incluye otros como CELARENT, DARII, etc.) se ha hecho de esa manera para memorizarlas facilmente.

En fin, en este modo del silogismo categórico, el término medio es el predicado de la premisa mayor y el sujeto de la premia menor, mientras que el término menor es sujeto de la mayor. Un ejempl sería:

Todas las disonancias acústicas son también disonancias artmónicas. Los acordes con quinta dismonuída son disonantes desde el punto de vista acústico. Luego, los acordes con quinta disminuída son disonantes desde el punto de vista armónico.


Hay una relación que se establece entre los términos en las proposiciones universales afirmativas (A). Y esa relación es transitiva. Pero en ambos casos no es la misma relación (son dos relaciones con una misma propiedad). Una cosa es el modo de inferir un enunciado en base a la relación que en su interior mismo se establece, dado que existen otros dos enunciados que lo permiten hacer, a afirmar que entre dos enunciados existe una determinada relación, basándose en que un tercer enunciado se relaciona con uno de un modo, con le otro del recíproco, teniendo en cuenta esa misma relación. La diferencia, que es la base de la separación de la lógica en proposicional y de de predicados, estriba en que en un caso el enunciado es la unidad mínima de análisis, mientras que en el otro éste es analizado en predicados y aquello de lo que se predica, argumento y función diría Frege.

martes, 19 de febrero de 2013

De una peculiaridad observable del uso teórico de la Razón Pura

El relativamente ínfimo (con respecto a su totalidad) número de matemáticos con los que he intercambiado opiniones y puntos de vista, me ha transmitido la opinión de que afinca una considerable distancia entre la sintaxis de la lógica meramente proposicional y los cursos por donde su razonamiento frecuenta. No pocas veces, tratándose de ello, sus razonamientos tiene la forma: "las tablas de verdad siempre bastan para decidir si una fórmula proposicional debe aceptarse ¿para qué entonces andar dedicando tiempo a rodeos por el lenguaje objeto si con las tablas se responden todas las preguntas allí posibles?".

En efecto, la semántica es suficiente, por sí misma, porque el sistema del cálculo de enunciados es completo y consistente. Una fórmula pasa la prueba de las tablas de verdad si (y sólo si) es válida. Y cómo se trata de una semántica basada sólo en dos funciones, la función unaria de la negación y la función binaria de la implicación material, cuyos dominios y rangos se construyen con sólo dos elementos, se estima, por añadidura, en poco el sistema en cuestión¹.

No obstante, cuando se trata de hacer demostraciones en dicho ámbito proposicional, se recurre en ocasiones a consabidos metateoremas como el de la deducción que han llevado la tarea a un grado tal de parsimonia, que incluso resulta más conveniente aún eso que el trazado sobre el papel de las tablas de veradad.

Es que la ciencia, se dirá, debe seguir su curso incesante de progreso, sin detenerse en problemas harto sabidos, resueltos ya por las generaciones de nuestros antepasados, sino afrontar los desafíos siempre nuevos, aquellos cuya solución nos aguarde aún.

Pero ¿pueden ser esgrimidos motivos formalistas en sentido estricto para ello, o sólo lógicos en sentido metafórico, con lo insuficiente de esto último al punto de vista que debe seguir la ciencia? El mismo Kant, en su Crítica de la Razón Práctica fue de esta opinión. Pero pese a que, si bien usualmente sustituyendo por autores más actuales el nombre del filósofo de Königsberg, argumentos así no son infrecuentes, no nos sería lícito conformarnos con eso.

¿Y si nos fuera lícito dudar de todo hasta el punto de preguntarnos si todo el progreso de la saber científico no es más que una serie de vueltas en círculo eludiendo siempre los mismos e irresueltos problemas? Muy probablemente parezca al lector semejante duda demasiado extrema como para justificar aun el ocuparse en examinar sus derechos, los indicios en su favor y en su contra. Además, la progresividad del sendero de la ciencia parece una verdad tan natural que ponerla en entredicho sólo puede dar la impresión de una broma.

Se trata, evidentemente, de un falso problema. El movimiento deductivo, por llamarlo así, va sumando nuevos teoremas y metateoremas, sin contramarcha alguna, a veces más rápidamente, otras menos, nadie habrá que dude de eso. Y a la vez, aquello cuya forma no sea la que nuestra facultad cognoscitiva requiere que su objeto posea para entenderlo, —y que por tanto será inocuo a ese movimiento— no dará noticias pues quien transita ese camino hace tiempo ha aprendido a no comlicarse en su trayecto en formas tales. Pero nada de eso prueba, de ningún modo, que al franquear los límites de la razón pura especulativa no pueda la presencia de aquello volverse presente.

______
NOTA:
1. Y ni hablar de los puentes que puedan trazarse entre la lógica formal, ciencia necesariamente pura, y aquellas situaciones necesariamente informales en que se hace uso de la lógica, como cuando alguien quiere explicar la absoluta imposibilidad de un hecho, por ejemplo (para lo cual de nada serviría esgrimir motivos empíricos), etc.

viernes, 15 de febrero de 2013

La transitividad de la implicación material

La implicación material es una relación entre dos enunciados. Siempre que tengamos dos de ellos cualesquiera, entonces la relación se mantiene entre ambos en alguna de las dos formas en que esto puede ocurrir, es decir implicando uno al otro o vice versa. Esto es bastante curioso, e incluso bastante extraño. Los lógicos han terminado por ponerse de acuerdo en dar este significado a la implicación y no otras, como el de la «implicación estricta» por ejemplo.

De todas formas, no era a eso a lo que me iba a referir, sino una propiedad que puede demostrarse de la relación en cuestión, a saber, la transitividad. Esto quiere decir que dadas tres proposiciones, si alguna es implicada por una de las otras e implica la restante, entonces esta última es implicada también por la otra. Más fácil de ver: si p → q y si q → r, entonces p → r. Puede formularse así:

p → q → [q → r →. p → r] (ley de transitividad de la implicación material)

Lo cual puede ser de utilidad en caso de que alguien quiera probar una implicación y ya haya probado las dos premisas. Es como si tuviéramos una regla que dijera: p → q, q → r ⊢ p → r, de lo cual se deduce lo anterior mediante el teorema de la deducción. También se podría probar, apelando a dicho teorema, del modo siguiente.

Esto p → q, q → r, p ⊢ r se prueba ya que de p → q y p se obtiene q (por modus ponens), y de q y q → r, por el mismo motivo se obtiene r, que es lo que se quería probar. Por otro lado, si llegamos a tener probado p → q y q → r, entonces con la fórmula p → q → [q → r →. p → r] nos basta, pues inferimos primero q → r →. p → r (por modus ponens) y luego p → r. Esto puede hacerse incluso incluso con las premisas en otro orden, es decir en base a:

q → r → [p → q →. p → r] (segunda ley de transitividad de la implicación material)

Lo cual se prueba mediante el teorema de la deducción del mismo modo, pero también del siguiente (véase este post para los axiomas y las reglas):

Probaremos primero dos lemas que harán más legible, creo, la demostración.

Lema I: si ⊢ A, luego ⊢ B → A

Prueba:

1 Sea ⊢ A
2 A →. B → A Axioma I
3 B → A modus ponens, 1 y 2.

Lema II: si ⊢ A →. B → C, luego ⊢ A → B →. A → C

Prueba:

1 Sea ⊢ A →. B → C
2 [A →. B → C] → [A → B →. A → C] Axioma II
3 A → B →. A → C modus ponens, 1 y 2.

Entonces tenemos:

1 [p →. q → r] → [p → q →. p → r]
    Axioma II

2 q → r →. [p →. q → r] → [p → q →. p → r]
   Lema I, 1.

3 q → r → [p →. q → r] →. q → r → [p → q →. p → r]
   Lema II, 2.

4 q → r → [p →. q → r]
   Axioma I.

5 q → r → [p → q →. p → r]  
   modus ponens, 3 y 4.


Y si queremos probar el teorema con las premisas en el orden habitual (lo cual puede ser de mayor utilidad en ciertos casos), procedemos así:

1 p → r → [p → q →. p → r]
   Axioma I, Sust.

2 [q → r →.p → q] → [q → r →. p → r]
   Lema II, teorema anterior

3 p → q → [q → r →. p → q]
   Axioma I, Sust.

4 [q → r →.p → q] → [q → r →. p → r] → [p → q → [q → r →. p → q] →. p → q → [q → r →. p → r]]

Para el caso en que no resulte del todo legible este último teorema (4), lo escribiremos con la siguiente convención: pq siginificará p → q, pq → r será p → q → r, y p → qr será p →. q → r, etc.

4' [qr → pq →. qr → pr] → [[pq →. qr → pq] → [pq →. qr → pr]]
     ley de transitividad infra.
      
5 p → q → [q → r →. p → q] →. p → q → [q → r →. p → r]]  
   modus ponens, 2 y 4.

5' [pq →. qr → pq] → [pq →. qr → pq]

6 p → q → [q → r →. p → r]  
    modus ponens, 3 y 5.

jueves, 10 de enero de 2013

Teorema de la deducción y permutación de las hipótesis

El teorema de la deducción es el que afirma, por ejemplo, que de una demostración de p suponiendo q se puede concluir que q → p. Dicho teorema sirve para demostrar p → q →. p → q así: p → q, p ⊢ q luego p → q ⊢ p → q luego p → q →. p → q. Pero tal vez sea una forma más correcta de expresarse decir que lo que esto prueba es que existe la demostración de esta última fórmula, antes que ser la prueba de ella. De un modo bastante similar tenemos: p, p → q ⊢ q luego p ⊢ p → q → q luego p →. p → q → q. De nuevo, con esto probamos (en virtud de la prueba del teorema de la deducción) que tal prueba existe, pero no dijimos cual es en concreto (usando sólo el lenguaje objeto).

La prueba de Church proporciona en cierto sentido un modo de dar con una prueba. Veamos por ejemplo el primero de los dos ejemplos del post. El lector dirá probablemente que resulta más lógico probar primero p → p y luego sustituir p por p → q en dicho teorema. Eso se obtendría así:

ley de la reflexividad de la implicación material

1 [p →. p → p → p] →. [p →. p → p] →. p → p ; por sustitución en axioma 2.

2 p →. p → p → p ; sustitución en axioma 1

3 [p →. p → p] →. p → p ; modus ponens 1, 2

4 p →. p → p ;  sustitución en axioma 1

*5 p → p ; por modus ponens, 3, 4.
    

Luego, por sustitución en *5: p → q →. p → q

Pero a diferencia de p → q →. p → q, con p →. p  → q → q no podemos proceder así, apelando sencillamente a la reflexividad de →.

Primero tenemos que pasar de p, p → q ⊢ q a p  ⊢ p → q →. q. Aquí tenemos p → q en lugar de Aₙ y q de Bₘ (Cf. este post). Para cada B hay que probar Aₙ → B.


Como p es supuesto, sabemos como probar p ⊢ p → q → p. También sabemos probar p → q →. p → q. Tenemos que probar entonces p ⊢ p → q →. q. Y la parte derecha de dicha fórmula es nuestro Aₙ → Bₘ, con lo que usamos:

[Aₙ →. Bₖ → Bₘ] →. Aₙ → Bₖ →. Aₙ → Bₘ

 y sustiyendo:
[p → q →. Bₖ → q] →. [p → q] → Bₖ →. p → q. → q

y Bₖ es una las las líneas de la prueba de p, p → q ⊢ q. En este caso es una de las premisas: p. Así, nos queda

[p → q →. p → q] →. p → q → p →. p → q. → q

p → q →. p → q ya sabemos probarlo, obtenemos:

p → q → p →. p → q. → q 

Y como p es premisa, probamos también p ⊢ p → q → p. Una vez más modus ponens  y nos queda : 

p ⊢ p → q. → q

Ahora hacemos el paso que sigue. Sustituyendo en
[Aₙ →. Bₖ → Bₘ] →. Aₙ → Bₖ →. Aₙ → Bₘ

¿Cuál es Bₖ → Bₘ? Pues como vimos: 

** p → q → p →. p → q. → q

obtenemos pues:

[p →. [p → q → p] → [p → q. → q] ] →. p → [p → q → p] →. p → [p → q. → q] 

El antecedente se prueba por ** y lema 1. Obtenemos:

[p →. p → q → p] →. p →. p → q. → q

Y p →. p → q → p se obtiene en un paso del primer axioma, entonces:

p →. p → q. → q

Que es lo que queríamos probar.

Sin duda, ahora el lector querrá la prueba de algo un poco más general, a saber: [p →. q → r] → [q →. p → r], lo cual establece la posibilidad de permutación en general de las hipótesis en una deducción de modo que si de cualesquiera p y q se concluye r, se las puede suponer en cualquier orden, queda como ejercicio (o se lo encuentra acá).