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)

lunes, 7 de octubre de 2013

La probabilidad del envido

Retomando la entrada anterior, tenemos acá la siguiente tabla del envido:




Puntaje
Frecuencia

0 puntos
112
1 puntos
148
2 puntos
244
3 puntos
364
4 puntos
504
5 puntos
676
6 puntos
868
7 puntos
1084
20 puntos
364
21 puntos
372
22 puntos
372
23 puntos
504
24 puntos
504
25 puntos
640
26 puntos
640
27 puntos
780
28 puntos
408
29 puntos
420
30 puntos
284
31 puntos
292
32 puntos
148
33 puntos
152

En la columna izquierda tenemos los puntos que una mano tiene en el envido, en la derecha la cantidad de manos. La probabilidad acumulada se ve en esta otra tabla:


33 o más
2%
32 o más
3%
31 o más
6%
30 o más
9%
29 o más
13%
28 o más
17%
27 o más
25%
26 o más
32%
25 o más
38%
24 o más
43%
23 o más
48%
22 o más
52%
21 o más
56%
20 o más
60%
7 o más
70%
6 o más
79%
5 o más
86%
4 o más
91%
3 o más
95%
2 o más
97%
1 o más
99%
0 o más
100%


Así, la probabilidad de obtener 33 de envido equivale a 2 de cada 100. Esto nos da una media de 17,35951417 puntos, con un desvío estándar de 10,6024356.

_______________
Nota: si bien el lector muy probablemente lo sepa, como no hemos dicho aquí qué significan la media y el desvío estándar, haremos una mención de ello.
Sea W el conjunto de todas las manos posibles, cada una con un puntaje (existe una función de W a puntajes). La media es la suma de env(wi) para cada mano wi dividido por m, el número de manos. En el presente caso, m = 9880 y la sumatoria en cuestión da 171.512.
En general, si tenemos los valores para cada mano xi, siendo en total n las manos, la calculamos:




El desvío estándar es la raíz cuadrada de la varianza, la cual por su parte se calcula así: se toma primero la sumatoria del cuadrado de las diferencias entre cada uno de los valores env(wi) y la media. Luego se divide este número por m, el número de manos posibles en el ejemplo.

martes, 10 de septiembre de 2013

Sumando el envido

Jugando al truco, un jugador no a a cantar o dejar de cantar envido fijándose meramente en 'lo que tiene'. Sin embargo, muy probablemente mire primero sus cartas. Así, uno podría preguntarse ¿qué probabilidad existe de obtener envido, quiero decir, sumar 20 o más? Bueno, tal vez 20 sea demasiado poco, pero esto permite hacer algunas cuentas.

El número total de manos (con mano me refiero a las cartas que tiene un jugados luego de repartidas éstas) con exactamente dos cartas del mismo palo se obtiene así. Primero, C(10,2), es decir, 45. Esto lo graficamos así:

    1    2    3    4    5    6    7    8    9    10
1    -                                   
2    3    -                               
3    4    5    -                           
4    5    6    7    -                       
5    6    7    8    9    -                   
6    7    8    9    10    11    -               
7    8    9    10    11    12    13    -           
8    1    2    3    4    5    6    7    -       
9    1    2    3    4    5    6    7    0    -   
10    1    2    3    4    5    6    7    0    0    -

Los números del 1 al 10 en la primera columna y la primera fila representan las cartas de una palo, las cifras en el interior suman el valor que tienen ambas para el envido, menos 20. Esto nos da la siguiente distribucion de frecuencias:

20    3    3
21    3    6
22    3    9
23    4    13
24    4    17
25    5    22
26    5    27
27    6    33
28    3    36
29    3    39
30    2    41
31    2    43
32    1    44
33    1    45


En este cuadro vemos el envido a la izquierda, en el centro cuantas manos posibles conexactamente dos cartas de un mismo palo dan ese valor, y a la derecha la frecuencia acumulada.

Ahora bien, existen por cada uno de esos 45 pares, 30 cartas de otros palos. Luego, hay por cada palo 45 ⨯ 30 = 1350 manos con exactamente dos cartas de un mismo palo. De modo que en total son 1350 ⨯ 4 = 5400.

Pero es importante tener en cuenta lo siguiente: faltan sumar las manos con flor, es decir aquellas que tienen dos del mismo palo, pero también una tercera de ese mismo palo. El número total por palo es C(10,3) = 120. Esto nos da el número:

Manos al menos dos cartas de un mismo palo = 5880, o sea un 59,5% (ver post anterior).

Manos con flor: C(10,3) ⨯ 4 = 480, un 4,85%

A esto último también podíamos llegar así. Sea un palo cualquiera e. La probabilidad de obtener como carta 1 una e es 10/40, como sengunda 9/39 y como tercera 8/38. Y esto vale para cualquier palo. Pero (10÷40)×(9÷39)×(8÷38)×4 = 0,048582996.

Ahora veamos en un cuadro todas las manos-flor posibles de un palo:




En las dos columnas de la izquierda están las dos primeras cartas de la mano y en la primera fila la tecera. El valor correspondiente está representado como un número igual el puntaje de envido menos 20. Obtenemos así la siguiente distribución de frecuencias:

20    1    1
21    3    4
22    3    7
23    6    13
24    6    19
25    10    29
26    10    39
27    15    54
28    12    66
29    15    81
30    11    92
31    13    105
32    7    112
33    8    120
    120   

Recordemos que esto ocurre con cada palo. Podemos ahora completar el cuadro siguiente:

20    364    364
21    372    736
22    372    1108
23    504    1612
24    504    2116
25    640    2756
26    640    3396
27    780    4176
28    408    4584
29    420    5004
30    284    5288
31    292    5580
32    148    5728
33    152    5880
    5880   


Donde la columna izquierda nos da el envido de una mano y la izquierda el número total de manos que suman ese número. A la derecha la frecuencia acumulada.

viernes, 30 de agosto de 2013

Elementos del truco y las probabilidades



Supongo que el conjunto de lectores que hayan llegado a este post sabrán jugar y habrán jugado al truco, de modo que lo asumo. Ahora me interesaba anotar algunas cuestiones que el juego plantea. Pero antes una aclaración. El uso de la probabilidad no siempre es viable y muchas veces puede conducir a error. Por ejemplo, J puede estar jugando y ver que el otro jugador K, tras haber cantado 30 de envido dejó en la mesa, sucesivamente un 7 de espadas y un 12 de copas. La lógica indicaría que tiene el 3 de espadas, entonces no acepta el truco que le canta y se va al mazo. Pero supongamos que K mintió el envido y tenía, en lugar de 30 no más que 7, y en lugar del 3 de espadas le quedaba el cuatro de copas. En este caso, la conclusión sacada lógicamente ¿fue beneficiosa o perjudicial? Como suele ocurrir, las presunciones no fueron las mejores. Cuestiones similares pueden plantearse al uso de la probabilidad en algunos casos.


Pero veamos, un maso de cartas de truco M tiene en total 40 cartas. ¿Cuál es el número total de manos que podrían tocarle a un jugador? Una mano es un conjunto de tres cartas (todo conjunto con las mismas tres cartas es idéntico, todo aquel donde alguna está en uno pero no en otro difieren). El número total en cuestión es el tamaño del conjunto de todos los subconjuntos de tres elementos de M. Definamos:

W =  {U : U ⊆ M & |U| = 3}

¿Cuántos elementos hay en W? Pues bien para responder eso hacemos C(40,3) o sea todas las combinaciones de 3 elementos tomados de M: 40 ⨯ 39 ⨯ 38 : 6. O sea:

|W| = 9880

Con esto podemos responder preguntas simples como cuál es la probabilidad de obtener el ancho de espadas en una mano.

Si sacamos esta carta del mazo nos quedan 39. El número total de pares que podemos formar con esas cartas es:

C(39,2) = 741

Y como por cada par hay una mano compuesta por él y el ancho, ese es el número de de manos posibles con esta carta. Llamemos A al conjunto de todos los conjuntos U de W tales que la carta determinada a ∊ U. Si llamamos a al ancho de espada, |A| = 741.

De esta forma, 741/9880 nos da la probabilidad de obtener dicha carta en una mano, esto es 

p(A) = 0,075.

 
Es evidente que esto mismo ocurre con cualquiera de las cartas, la misma probabilidad hay en que toque el cuatro de copas. ¿Y la de obtener un ancho de espadas o una cuatro de copas? Sin duda las probabilidades aumentan. Esto, llamando a y b a tales cartas, se representa así A ∪ B.

En este caso, no podemos sumar |A| + |B|, puesto que en tal caso duplicaríamos todas aquellas manos que tuvieran tanto a a como a b, ya que se encuentran tanto en A como en B. Para restarlas simplemente pensamos ¿cuantas manos hay que tengan tanto a como b? Pues bien, es obvio que no hay sino exactamente 38, una por cada carta que queda en el mazo luego de haberle separado a y b. Entonces:

|A ∪ B| = |A| + |B| - |A ∩  B|

Sabemos que |A| = |B| = 741 y que |A ∩  B| 38, luego:

|A ∪ B| = 1444

O sea que:

 
p(A ∪ B) = 0,14615...

 

¿Y p(A ∪ B ∪ C)? Bueno, hacemos de modo similar:

|A ∪ B| + |C| - |(A ∪ B) ∩ C|

Tenemos entonces que calcular (A ∪ B) ∩ C. Son las manos que tienen a la vez c y también ya sea a o b. O sea el conjunto X ⊆ W tal que ∀U∊X (c ∊ U ∧ (a ∊ U ∨ b ∊ U)).

Pero esto significa que buscamos (A ∩ C) ∪ (B ∩ C), pues
c ∊ U ∧ (a ∊ U ∨ b ∊ U) ≡ c ∊ U ∧ a ∊ U ∨ c ∊ U ∧ b ∊ U)

Sabemos ya que |A ∩ C| = |B ∩ C| = 38, pero no podemos sumar simplemente porque se duplicaría A ∩ C ∩ B ∩ C, que es el conjunto con la única mano {abc}. De este modo,

|(A ∪ B) ∩ C| = 38 + 38 - 1 = 75

Sabemos entonces que
|A ∪ B| + |C| - |(A ∪ B) ∩ C| = 1444 + 741 - 75 = 2110

Así,

 
p(A ∪ B ∪ C) = 0,213562753
 


Repasemos:

p(A ∪ B) = p(A) + p(B) - p(A ∩  B)

p(A ∪ B ∪ C) = p(A ∪ B) + p(C) - [p(A ∩ C) + p(B ∩ C) - p(A ∩ B ∩ C)]

Sustituyendo tenemos también:

p(A∪B∪C) = p(A) + p(B) - p(A∩B) + p(C) - [p(A∩C) + p(B∩C) - p(A∩B∩C)]

Que es lo mismo que:

p(A ∪ B ∪ C) =
p(A) + p(B) + p(C) - p(A ∩ C) - p(A ∩  B) - p(B ∩ C) + p(A ∩ B ∩ C)


Veamos ahora el siguiente problema: p(A ∪ B ∪ C ∪ D) = ?

Necesitamos averiguar |(A ∪ B ∪ C) ∩ D|. El tema está en conocer (A ∪ B ∪ C) ∩ D. Las condiciones a cumplir para cada elemento U de dicho conjunto son: d ∊ U y a ∊ U ∨ b ∊ U ∨ c ∊ U. Esto significa (con AB para A∩B):

DA ∪ DB ∪ DC

En cuanto a |DA ∪ DB| ya sabemos, es 38 + 38 - 1, o sea 75

Pero ¿cuáles son los elementos comunes de DA ∪ DB y DC? Evidentemente, las conjunciones DAC y DBC. Entonces:

|DA ∪ DB ∪ DC| = |DA ∪ DB|+|DC|-|ACD|-|BCD|
75 + 38 - 1 - 1 = 114

Entonces:

|A∪B∪C|+|D|-|(A ∪ B ∪ C) ∩ D| = 2110 + 741 - 114 = 2737

Así,
 


p(A ∪ B ∪ C ∪ D) = 0,277...

 


Esta es, por ejemplo, la probabilidad de ligar algún cuatro.

La fórmula desplegada es así:

p(A∪B∪C∪D) = p(A∪B∪C) + p(D) - p((A∪B∪C)∩D)
O sea:
=[p(A) + p(B) + p(C) - p(A∩C) - p(A∩B) - p(B∩C) + p(A∩B∩C)] + p(D) - [p(DA∪DB)+p(DC)-p(ACD)-p(BCD)]

Pero p(DA ∪ DB) =  p(DA) + p(DB) - p(ADB), luego:


=[p(A) + p(B) + p(C) - p(A∩C) - p(A∩B) - p(B∩C) + p(A∩B∩C)] + p(D) - [p(DA) + p(DB) - p(ADB) + p(DC) - p(ACD) - p(BCD)]

Esto es:

p(A∪B∪C∪D) =
p(A) + p(B) + p(C) + p(D) - p(AB) - p(AC) - p(BC) - p(DA) - p(DB) - p(DC) + p(ADB) + p(ACD) + p(BCD) + p(ABC)

Dado que para cualesquiera A, B, C, D, etc., p(A) = P(B), etc., y p(AB) = p(CD), etc.; etc., Si llamamos:

p(A) = α₁
P(AB) = α₂
P(ABC) = α₃

Recordemos que
 
α₁ = 741/9880
α₂ = 38/9880
α₃ = 1/9880

Simplificamos:

4·α₁ - 6·α₂ + 4·α₃ = 0,277327935

Los números 4, 6 y 4 vienen, respectivamente, de C(4,1), C(4,2) y C(4,3).

¿Qué pasa entonces si queremos saber p(⋃A₁...A₃₀)?

Procedemos así (tengamos en cuenta que para todo n mayor que 3
p(⋂A₁...Aₙ) = 0):


C(30,1)·α₁ - C(30,2)·α₂ + C(30,3)·α₃ = 0,987854251, de modo que


p(⋃A₁...A₃₀)  =  0,987854251

 

Evidentemente va a llegar un momento en que la unión sea tal que su probabilidad sea 1. ¿Cuál?

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.