~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)

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

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)

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 →.

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).

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]].

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.

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.

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.

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.

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á).

Un prueba en la teoría Nicod-Lukasiewicz

Veamos la prueba de «p → p» en el sistema Nicod-Lukasiewicz.

Recordemos el axioma: p/qr | (s/ss) / (sq → ps)

Sustituyendo en él: 'p' por 'p/qr', 'q' por 's/ss', 'r' por 'sq → ps' y 's' por 't', obtememos:

[p/qr|(s/ss)/(sq → ps)] | t/tt / (t|s/ss → p/qr|t)

Nótese que la parte entre corchetes es el axioma mismo, por tanto podemos aplicar la regla, lo cual nos permite afirmar:

(I)  t|s/ss → p/qr|t


Sustituyendo, nuevamente en el axioma, 'p' por 't|s/ss', 'q' y 'r' por 'p/qr|t', 's' por 'w', obtenemos:


(t|(s/ss) → p/qr|t) | (w → w) / (w|(p/qr|t) → t/(s/ss)|w)

Y aplicando la regla (teniendo en cuenta I), obtenemos:

(II)   w|(p/qr|t) → t/(s/ss)|w


Ahora, realizamos en (II) la siguiente sustitución:

'w' por 'p/qr'; 'p', 'q' y 'r' por 's'; 't' por 'sq → ps', 's' por 't' y 't' por 'sq → ps'. Obtenemos el condicional:

p/qr|(s/ss)/(sq → ps) → (sq → ps)/(t/tt)|p/qr

Cuyo antecedente no es sino al axioma, y por ende:

(III)    (sq → ps)/(t/tt)|p/qr

Sustityendo en (I) 't' por '((st → ts)|t/tt)' y 's' por 't':

(st → ts)/(t/tt)| t/tt → p/qr | (st → ts)/(t/tt)

Y como reemplazando en (III) 'p', 'q' y 'r' por 't' nos da:

 (st → ts)/(t/tt)|t/tt

Luego:

(IV)     p/qr | (st → ts)/(t/tt)


Reemplazando en (IV) 'p' por 't|s/ss' y 'q' y 'r' por 'p/qr|t', obtenemos:

(t|s/ss → p/qr|t) | (st → ts) / (t/tt)

Aplicando la regla (teniendo en cuenta (I)), deducimos:

⊢ t/tt

Que es lo que se quería probar.

Más del axioma de Nicod

En el post anterior se hace rerefencia a un axioma que permite, usando la regla de sustitución y una regla de inferencia deducir toda fórmula proposicional. Lukasiwiecz menciona que Leśniewski fue quien notó que la prueba dada por Nicod de «p → p» incluía un error y que, por tanto, no era tal prueba. Esa deducción es publicada por Lukasiewicz en 1931¹. Asimismo, introduce también una modificación en el  axioma de Nicod por otro que es deductible a partir de él en un paso con una sustitución, y que es el presentado en el post citado. El de Nicod es:

p/qr | Ctt / (sq → ps)²

A partir del cual con la sustitución de t por s obtenemos el de Lukasiewicz. Otra prueba que da este autor es la que parte de esta segunda versión del axioma y concluye en la primera, permitiendo afirmar su equivalencia. Se menciona a su vez otro axioma, respecto del cual Wajsberg mostró que servía en lugar del de Nicod. Éste es:

p/qr | [(sr → ps) | p/pq]

Ejercicios:

Usando el axioma y las reglas del post citado, probar:

a. p → p
b. p/qr | Ctt / (sq → ps)



Nota:
1. Luakasiewicz, J. «Uwagi o aksjomacie Nicoda i 'dedukcji uogólniajacej'»
2. Para leer lafórmula téngase en cuenta que: dos letras minuculas una después de la otra, por ejemplo 'pq' representa «p|q»; la barra «/» tiene el mismo significado que «|», pero al momento de cerrar entre paréntesis prepondera la seguda, o sea que 'p|q/p' significa 'p|(q|p)'; 'Css' representa 's → s'.

Demostraciones lógicas

Obtuvimos de la página rinconmatematico.com (del foro de lógica y teoría de conjuntos), el siguiente ejercicio:


1. El lenguaje a utilizar consta del alfabeto de símbolos: ¬, →, (, ), p, q, etc.

2. Un conjunto de fórmulas bien formadas (fbf), que son aquellas que cumplen:

i. p, q, r, etc. son cada una fbf.

ii. Si A y B son fbf, así lo son ¬A y  ¬B.

iii. El conjunto de todas las fbf. es generado por (i) y (ii)

3. Axiomas. Para cada A, B, fbf  se cumple:

L1  (A → (B → A))
L2  ((A → (B → C) → ((A → B) → (A → C))
L3  (¬A → ¬B) → (B → A)

4. Regla de inferencia.
De A, A → B  es consecuencia inmediata B.

5. También pueden usarse las siguientes formas adicionales de deducción:
1. Si γ, A ⊢ B entonces γ ⊢ (A → B)
2. A → B, B → C ⊢ A → C

A) Demuéstrese:

A.1) (p → q) → ((¬p → ¬q) → (q → q)
A.2) ((p → (q → r)) → (p → q)) → ((p → (q → r)) → (p → r))
A.3) (p → (p → q)) → (p → q)
A.4)  p → (q → (p → q))

B) Como ejercicio adicional puede intentarse demostrar estas formas adicionales a partir de L1, L2, L3 y la regla de inferencia. 

Demostraciones formales Implicación estricta

Hace unos días, en este post, citamos un sistema lógico que figura en el libro de Hilbert y Ackermann de la bibliografía, que se caracteriza por un concepto de implicación que no es el mas frecuente. Mostraré ahora cómo puede procederse con él para demostrar algunas de las fórmulas que figuran en este post. Desde ya, de aquellas proposiciones que se demuestran en una línea figura a la derecha el esquema axiomático del que son instancias.


i) A → ¬¬A                              Esquema Axiomático 14


iii) A ∧ (A → B) → B

a) (A → B) → ((A ∧ (A → B) → A) → (A ∧ (A → B ) → B))   EA 3
b) A ∧ (A → B) → A                                                         EA 5
c) (A → B) → (A ∧ (A → B ) → B)                                 Regla IV a,b
d) ((A → B) → (A ∧ (A → B) → B)) → ((A ∧ (A → B) → (A → B)) →
     → ((A ∧ (A → B) → (A ∧ (A → B) → B)))                    
                                                                                           EA3
e) ((A ∧ (A → B) → (A → B)) → ((A ∧ (A → B) → (A ∧ (A → B) → B))
                                                                                   Rega I, c,d
f) A ∧ (A → B) → (A → B)                                                 EA 6
g) A ∧ (A → B) → (A ∧ (A → B) → B)                             Regla I, e,f
h) A ∧ (A → B) → (A ∧ (A → B) → B)) → (A ∧ (A → B) → B)    EA 4
i) A ∧ (A → B) → B                                                       Regla I g,h




iv) (A → B) → (¬B → ¬A)                     E.A. 12



v) (A → B) → ((B → C) → (A → C))        E.A. 3



vi) ¬¬¬A → ¬A                                   E.A. 15



vii) ¬A → ¬¬¬A                                      E.A. 14


viii) ¬A → ¬(A ∧ B)

a)  A ∧ B → A                                          E.A.5
b)  (A ∧ B → A) → (¬A → ¬(A ∧ B))          E.A.12
c)  ¬A → ¬(A ∧ B)                                   R.I, a, b.




xi) ¬(A ∨ B) → ¬A ∧ ¬B

a)  A → A ∨ B                                             E.A.5
b)  B → A ∨ B                                             E.A.6
c)  (A → A ∨ B) → (¬(A ∨ B) → ¬A)            E.A.12
d)  ¬(A ∨ B) → ¬A                                     Regla I, a, c
e)  (B → A ∨ B) → (¬(A ∨ B) → ¬B)              E.A.12
f)  ¬(A ∨ B) → ¬B                                       Regla I, b, e
g)  (¬(A ∨ B) → ¬A) ∧ (¬(A ∨ B) → ¬B) →
    → (¬(A ∨ B) → ¬A ∧ ¬B)                        E.A.7
h)  (¬(A ∨ B) → ¬A) ∧ (¬(A ∨ B) → ¬B)      R.II, d, f.
i)  ¬(A ∨ B) → ¬A ∧ ¬B                              R.I, g, h.

Otro sistema de «implicación estricta»

Hemos hablado ya del sistema de Lewis donde tiene cabida un concepto de implicación que no es el de la implicación material. En esta oportunidad, mencionaremos otro, distinto, que figura en hilbert-Ackermann (1928). Según los autores, no existe necesidad alguna que inexorablemente nos fuerce a introducir este tipo de implicación, pero le dedican un parágrafo por revestir la cuestión, dicen, “cierto interés filosófico”.

En este sistema, enunciados como los allí citados «si la nieve es blanca, 7 es un número primo», «si la nieve es negra, 7 es un número primo» y «si la nieve es negra 9 es número primo» no serán válidos como lo serían si la implicación fuera verdadera toda vez que su antecedente sea “la nieve es negra” o su consecuente “7 es número primo”, es decir, aquél falso y ésta verdadera.

Los caminos seguidos por los autores citados y por Lewis difieren. Por ejemplo, éste acepta la validez de fórmulas como «A → B ∨ ¬B», «A ∧ ¬A → B», «¬(B ∨ ¬B)→A» y «¬B → ¬(A ∧ ¬A)», mientras que ellos no lo hacen. Veamos sus axiomas y reglas:

________________

Fórmulas elementales:

(1)    φ → φ

(2)    (φ → ψ) → ((ψ → χ) → (φ → χ))

(3)    (φ → ψ) → ((χ → φ) → (χ → ψ ))

(4)    (φ →(φ → ψ)) → (φ → ψ)

(5)    φ ∧ ψ → φ

(6)    φ ∧ ψ → ψ

(7)    (φ → ψ) ∧ (φ → χ) → (φ → ψ ∧ χ )

(8)     φ → φ ∨ ψ

(9)     ψ → φ ∨ ψ

(10)   (φ → χ) ∧ (ψ → χ) → (φ ∨ ψ → χ)

(11)   φ ∧ (ψ ∨ χ) → ψ ∨ (φ ∧ χ)

(12)   (φ → ψ) → (¬ψ → ¬φ)

(13)   φ ∧ ¬ψ → ¬(φ → ψ)

(14)   φ → ¬¬φ

(15)   ¬¬φ → φ

Las reglas de deducción son:

I. de φ y φ → ψ se deduce ψ

II. de φ y ψ se sigue φ ∧ ψ

III. de φ y ¬φ ∨ ψ se deduce ψ

IV. de ψ y φ→(ψ→χ) se deduce ψ→χ

El lector querrá quizá ahora verificar si alguna de las fórmulas de éste post son demostrables con esto, y por qué.

(Seguir leyendo)

La implicación y la validez del condicional

He aquí un par de ejercicios más de lógica proposicional, que pueden ser oportunos para continuar poniendo en práctica el método de Hilbret y Ackerman (1928). Ellos son:


((¬q ∨ p) → (t ∧ ¬m)) ∧ ¬ q

∴   ¬m ∧ ¬q

y


r ∧ ¬s → q ∨ m,

t ∧ ¬p ¬ ¬(q ∨ m),

r ∧ ¬s ∨ t ∧ ¬p,

∴   (q ∨ m) ∨ ¬(q ∨ m)

Considerando aquello de que "la implicación es la validez del condicional" veremos cómo se prueban los condicionales cuyos antecedentes estén formados por las conjunciones de las premisas (en caso de que haya más de una) y el consecuente por la conclusión.

Adoptaré, por comodidad, la siguiente notación. Para representar las variables proposicionales usaré letras como p, q, r, s, etc. Del modo habitual serán usados los signos →, ∨ y los paréntesis. Para la conjunción usaré ∧, pero en el caso en que dos letras proposionales, ej. p y q, formen una conjunción, podrán escribirse, en lugar de «p ∧ q», directamente así: «pq». En cuanto a la negación, usaré el signo ¬. Pero para indicar la negación de una proposición sola en lugar de servirme de ese símbolo colocaré sobre ella una barra horizontal. Así, en lugar de ¬p escribiré p̄. Tendré en cuenta las equivalencias «¬p̄ ≡ p», «¬¬p̄ ≡ p̄», la conmutatividad de ∨ y ∧, etc.


Veamos el primero:

((q̄∨p) → (tm̄)) ∧ q̄ 
∴   m̄q̄

Como se dijo, debemos verificar:

(a)     ((q̄∨p) → (tm̄)) ∧ q̄  →  m̄q̄

Para emplear el método mencionado debemos expresar el esquema en una forma equivalnte con sólo las letras proposicionales, la negación y la disyunción. Vamos por pasos comenzando por las conectivas de menor alcance. Apliquemos primero las leyes de De Morgan:

((q̄∨p) → ¬(t̄∨m)) ∧ q̄  →  ¬(m∨q)

Covertimos un condicional:

(¬(q̄∨p) ∨ ¬(t̄∨m)) ∧ q̄  →  ¬(m∨q)



Ahora nuevamente De Morgan:

¬(¬(¬(q̄∨p) ∨ ¬(t̄∨m)) ∨ q)  →  ¬(m∨q)

Ahora el otro condicional:

¬(¬(q̄∨p) ∨ ¬(t̄∨m)) ∨ q  ∨ ¬(m∨q)

Dado que:

¬(¬(q̄∨p) ∨ ¬(t̄∨m)) ∨ q ∨ q̄

es válido, nos queda examinar:

*   ¬(¬(q̄∨p) ∨ ¬(t̄∨m)) ∨ q  ∨ m̄

Primero: "¬(¬(q̄∨p)) ∨ q ∨ m̄"

q̄ ∨ p ∨ q  ∨ m̄

Es fórmula elemental (y por tanto válido). Ahora:
"¬(¬(t̄∨m)) ∨ q  ∨ m̄"

O sea:

t̄ ∨ m ∨ q  ∨ m̄

Que también lo es. Por lo tanto (a) es válido.


El otro:

rs̄ → q ∨ m
tp̄ → ¬(q ∨ m)
rs̄ ∨ tp̄
∴   (q ∨ m) ∨ ¬(q ∨ m)


(b) (rs̄ → q∨m) ∧ (tp̄ → ¬(q∨m)) ∧ (rs̄ ∨ tp̄) → (q ∨ m ∨¬(q∨m))


(¬(r̄∨s) → q∨m) ∧ (¬(t̄∨p) → ¬(q∨m)) ∧ (¬(r̄s) ∨ ¬(t̄p))) → (q ∨ m ∨ ¬(q∨m))

((r̄∨s ∨ q∨m) ∧ (t̄∨p ∨ ¬(q∨m)) ∧ (¬(r̄s) ∨ ¬(t̄p))) → (q ∨ m ∨ ¬(q∨m))

¬(¬(r̄∨s ∨ q∨m) ∨ ¬(t̄∨p ∨ ¬(q∨m)) ∨ ¬(¬(r̄s) ∨ ¬(t̄p))) → (q ∨ m ∨ ¬(q∨m))

¬(r̄∨s ∨ q∨m) ∨ ¬(t̄∨p ∨ ¬(q∨m)) ∨ ¬(¬(r̄s) ∨ ¬(t̄p)) ∨ q ∨ m ∨ ¬(q∨m)


Este esquema es válido ya que «q ∨ m ∨ ¬(q ∨ m)» lo es.
De todas formas, podríamos haber especulado de este modo: dado que cualquier condicional suyo consecuente es válido, lo es también él mismo; y como el consecuente de (b) es verdadero bajo toda interpretación de sus variables, luego (b) es una tautología, con lo que resolvíamos el ejercicio de un modo más breve.

Demostración en una lógica de 'ecuaciones'

Anteriormente se mostró una manera representar las fórmulas veritativas de la lógica proposicional. Vimos entonces que podíamos escribir:

    f_(x) = 1 − x

para la negación,

    f.(x,y) = x·y

para la conjunción,

    f→(x,y) = 1 − x + xy

para el condicional y

    f↔(x,y) = 1 − x − y + 2xy

para el bicondicional.

Para representar una disyunción escribiremos:

    fₒ(x,y) = 1 − ((1 − x)(1 − y))

Esto se justifica así: tendremos en cuanta la ley de De Morgan, a saber, «p ∨ q ≡ ¬(p̄ ∧ q̄)». Luego, si 'p' y 'q' son 'x' e 'y' respectivamente obtenemos la fórmula mencionada.




Podemos ahora hacer uso de un método 'algebraico'. Demostremos primero que "A si y sólo si A":

Como p ↔ p se representa como "1 − x − y + 2xy" (ver prueba), luego tenemos que demostrar:

 1 − x − y + 2xy = 1

ya que 1 es el único valor de verdad de toda fórmula válida, y queremos saber si tal fórmula lo es. Como p y p son la misma variable, luego x = y. Así:

1 − x − x + 2xx =
1 − 2x + 2x² =

Aplicando ∀x x²= x (ver post anterior):

1 − 2x + 2x = 1

Así, la fórmula inicial es válida.

(seguir leyendo)

Lógica, funciones de verdad, adición, producto y sustracción

Cabría preguntarse cuál es el lugar de la lógica. En una primera consideración la respuesta parece simple: su lugar es el lenguaje. La lógica es siempre inherente a algún lenguaje, tanto sea artificial o no, se dirá. ¿Pero dónde? podría insistirse. Se ha dicho¹ que su lugar es entre los juicios, entre los conceptos, etc. Así dados el juicio p: "el gato está en la alfombra" y otro: "yo no sé que p"; yo puedo decir ambos dando lugar a una conjunción. En tal caso, la única constante lógica -a cierto nivel de análisis- sería y. Pero también puedo preguntarme por otros aspectos de una afirmación en la cual se asevera algo y luego que no sé respecto de eso. Y también puede preguntarse si ello cae dentro de lo que solemos llamar lógica.

Dado que omni deteminatio est negatio, debe escogerse el modo de proceder. Es usual usar p, q, etc. para referir a proposiciones cualesquiera y ciertos signos conectivos como por ejemplo la herradura: ⊃. Se llama esto lógica proposicional (o cálculo proposicional), dado que se representan lo que se considera son vínculos lógicos entre las proposiciones. Hay otros. La lógica de predicados de primer orden (o cálculo restringido de predicados), por ejemplo, se erige sobre la base de la lógica proposicional e introduce en las proposiciones la noción de predicado relativa a individuos determinados, indeterminados o cuantificados.

Centrémosnos, una vez más, en el cálculo proposicional, (ya he escrito en el blog, sobre el mismo tema, las mismas cuestiones). Las letras que representan variables proposicionales no representan proposiciones cualesquiera. O mejor dicho, sí lo hacen. Pero el aparato de la lógica sólo se ve concernido con cierto par de cualidades inherente a -según se cree- toda proposición, que son mutuamente excluyentes.

Consideremos las dos frases: "En cambio tú, como eres erudito², nunca dices lo mismo sobre los mismos temas" y "Sí, Hipias, y, lo que es más sorprendente todavía, no sólo digo las mismas cosas siempre, sino que sigo hablando de los mismos tópicos"³.

Facilmente se ve que no son la misma frase. Se diferencian, por ejemplo, en que una habla de la segunda persona, mientras que la otra de la primera. Claro que no es la única diferencia. Pero tienen cosas en común: ambas forman parte de un diálogo -el mismo- ambas remiten a otro fragmento de ese mismo diálogo, ambas son atribuidas a Sócrates, ambas son una (y la misma) respuesta a una pregunta, ambas son afirmaciones, etc.

Podríamos, si quisiéramos, representarlas con las letras A y B. Ahora bien, si escribimos, como los lógicos: A ∧ B, entonces estamos abstrayéndonos respecto de todo lo que diferencia o no a estas frases con la sola excepción de las mentadas dos cualidades: la vedad o la falsedad, que suelen ser representada mediante los números, naturales o no, 0 y 1.

Está claro que que simbolizando la respuesta socrática a Hipias citada "A ∧ B" no podremos saber si la misma es verdadera o falsa, e incluso se diría que hemos abstraído todo lo que en ella tenía valor como para que sea evocada. Este hecho a veces hace que se otorgue a la lógica un lugar marginal. Incluso para quienes un lenguaje abstracto y artificial es de suma importancia en sus actividades cotidianas, e intentan sirviéndose de él conocer algo acerca de la estructura de su referente, esto sigue siendo problemático. ¿Cómo estar seguros de si lo que se abstrayó incluye o no eso que nos permitiría tener la capacidad de discernir lo que, precisamente, era nuestra pretensión discernir? Tal asunto puede inducir a error tanto como lo hace el equivocar un signo al transcribir.

Sea como fuera, lo cierto es que la lógica abstrae las mencionadas cualidades y representa el conjunto de sus posibles combinaciones. Así, si consideramos todas las fórmulas lógicas de dos variables proposicionales (ya lo hicimos antes) tenemos 16 combinaciones. Ese número es el resultado de elevar el 2 a la 2 a la n. Es decir 2^(2^n), donde n es el número de variables proposicionales.

Es decir, se trata de 16 funciones binarias cuyo dominio es el producto cartesiano de ({0,1}⨯{0,1}) o {0,1}², a saber:

{0,1}² = {(1,1), (1,0), (0,1), (0,0)}

EL codominio de cada una de estas funciones es el conjunto {0,1}.

Las funciones de una sola variable proposicional tienen por dominio al conjunto {0,1} y por imagen a ese mismo conjunto. Dada la fórmula de dos a la dos a la ene, tenemos que en total son 4.

Podemos designarlas así:

f₁ = {(1,1), (0,1)}
f₂ = {(1,0), (0,0)}
f₃ = {(1,1), (0,0)}
f_ = {(1,0), (0,1)}

Una de estas cuatro funciones, la última, ha sido objeto de particular atención⁴. Es habitual que se la represente mediante los signos ¬ y ~, optaremos por ⨍_ (en lugar de ⨍₄). Con esta función y una más (pero ésta de entre las 16 binarias) se pueden representar las 16. No es una única, podemos elegir entre algunas de ellas. Por ejemplo la conjunción, a saber:

f. = {((1,1),1), ((1,0),0), ((0,1),0), ((0,0),0)}

Esta función asigna el elemento 0 a todo elemento del dominio, con la sola excepción del par (1,1).

Para obtener la función conocida como condicional o implicación material tenemos que escribir, para las proposiciones x e y (x ⊃ y):

f_(f.(x,f_(y)))

Pero ¿Cómo expresar estas dos funciones con dos de las operaciones habituales de la aritmética, la adición y el producto?

Algún tiempo atrás, había escrito sobre un post del blog eltopologico que para intentar dar cabida en un lenguaje simbólico a la paradoja de Epiménides había sentado las bases de un sistema lógico donde intervenía la resta. El caso presente difiere, pues no se pretende ahora formalizar así una proposición (paradójica o no) sino lo que ocurre entre ellas, las conectivas lógicas.

La conjunción suele llamarse, también, producto lógico, y su nombre conduce a una expresión algebraica que permite operar con ella:

f.(x,y) = x·y

Así:

f.(1,1) = 1·1 = 1
f.(1,0) = 1·0 = 0
f.(0,1) = 0·1 = 0
f.(0,0) = 0·0 = 0

También podemos representar la negación, del siguiente modo:

f_(x) = 1 − x

De modo tal que:

f_(1) = 1 − 1 = 0
f_(0) = 1 − 0 = 1

Tal era la forma que en el post citado en primer término se usaba para la negación, justamente.

Con esto, ya podemos expresar todas las fórmulas binarias de la lógica proposicional. Por ejemplo, el bicondicional (o equivalencia material), a saber: «p ↔ q».

Tenemos en cuenta a su vez esta equivalencia:

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

Pero es preciso también encontrar una expresión para la flechita, el condicional. Una de las formas (pues no la única) de dar con ella es sirviéndonos de la siguiente fórmula:

f→(x,y) = 1 − x + xy

Lo cual surge de la equivalencia entre «p → q» y «¬(p ∧ ¬q)», tal como vimos arriba. El bicondicional será entonces:

(1 − x + xy)·(1 − y + xy)

O sea:

(1 − x + xy) − y(1 − x + xy) + xy(1 − x + xy)

Es decir:

(1 − x + xy) − (y − xy + xy²) + (xy − x²y + x²y²)

Por ende:

1 − x − y + 3xy − xy² − x²y + x²y²

Pero como es fácil demostrar, en general, que:

    ∀x : x ∊ {0,1}   ⇒   x² = x

Y los argumentos posibles para la función son el 0 y el 1 y ninguno otro (cierta practicidad inherente a una lógica que excluye al tercero), podemos simplificar la fórmula de la equivalencia material:

1 − x − y + 3xy − xy − xy + xy

y así obtener:

f↔(x,y) = 1 − x − y + 2xy


(seguir leyendo)
_________
Notas:
1. Hilbert-Ackerman(1928)
2. πολυμαθής
3. Jenofonte, Recuerdos de Sócrates, Libro IV.
4. Las funciones ⨍₁ y ⨍₂ también. Se las suele llamar, respectivamente, tautología y contradicción.

Pruebas de validez de esquemas disyuntivos

Vamos a poner en práctica el método que figura en este lugar y que es allí citado de Hilbert y Ackerman (1928). Hablar de tal forma, haciendo referencia a un praxis, no es en realidad más que una manera de decir, pues no se trata aquí de práctica ya que según las distinciones de la teoría del conocimiento kantiana, no es otra cosa que un uso especulativo de la razón, y ni si quiera técnico. Uso puro y especulativo de la facultad de conocer pues (y sin siquiera referir a objetos¹). ¿Pero uso analítico o sintético? Dejaré este último interrogante para otra oportunidad. Vayamos ahora a las fórmulas proposicionales que figuran al final del ya citado post y que son:


(i)     A → (S → A ∧ S)
(ii)    ¬¬¬A ∨ ¬¬(¬A ∨ ¬S ∨ ¬C)


Empecemos por (i), Lo primero que tenemos que hacer de llegar a una fórmula equivalente pero sin ∧ ni →. Entonces:

A → (S → ¬(¬A ∨ ¬S))
A → (¬S ∨ ¬(¬A ∨ ¬S))
¬A ∨ ¬S ∨ ¬(¬A ∨ ¬S))

Esta fórmula equivale a la aserción conjunta de

¬A ∨ ¬S ∨ ¬(¬A))

por un lado y de

¬A ∨ ¬S ∨ ¬(¬S))

Es decir de

¬A ∨ ¬S ∨ A

que es manifiestamente válida tanto como

¬A ∨ ¬S ∨ S

Luego (i) es válida.

Veamos ahora la otra

¬A ∨ ¬A ∨ ¬S ∨ ¬C

Esta fórmula no es deductible en el método en cuestión, por tanto no es válida.

Ahora el primer ejercicio:

(1)     ¬(¬A ∨ B) ∨ ¬(C ∨ A) ∨ C ∨ B

Esta fórmula es deductible a partir de

*   ¬(¬A) ∨ ¬(C ∨ A) ∨ C ∨ B

y de

**  ¬(B) ∨ ¬(C ∨ A) ∨ C ∨ B

de * obtenemos:

A ∨ ¬(C ∨ A) ∨ C ∨ B

que a su vez es deductible a partir de

***     A ∨ ¬(C) ∨ C ∨ B

y de

****    A ∨ ¬(A) ∨ C ∨ B

de acuerdo a la regla (b). Ambas, *** y **** son fórmulas elementales. Ahora resta por probar **, a partir de la cual obtenemos las dos a partir de las cuales es deductible:

#   ¬B ∨ ¬(C) ∨ C ∨ B

y

#  ¬(B) ∨ ¬(A) ∨ C ∨ B

Ambas son evidentemente válidas, luego (1) lo era, quod erad demonstrandum.

_____________________
1. Nota: Muy bien, Frege quizá expresaría su protesta ante esto. Lo que no parece, de todas formas, es que se trate de una mera cuestión de palabras (Cf. Frege Los fundamentos de la aritmética, § 89).