Probabilidades [Parte 3: Ejercicios - Conceptos Elementales]



En las entradas anteriores se introdujeron las nociones fundamentales de la teoría de probabilidades, por lo que ahora toca resolver algunos problemas para practicar un poco los conceptos vistos. Los ejercicios de esta entrada estarán centrados en lo visto en la entrada Probabilidades [Parte 1 - Introducción y Definiciones Elementales]. Estas son esencialmente demostraciones sobre hechos básicos, pero que vale la pena ver por lo menos una vez en la vida.


Problema 1: Probar que $P(A^c)=1-P(A)$ y deducir que $P(\varnothing) = 0$

Solución: De la definición de medida de probabilidad se tiene que, si $A$ y $B$ son dos eventos medibles, entonces se cumple que

  1. $0\leq P(A) \leq 1$ y $0\leq P(B) \leq 1$
  2. $\left(A\cup B = \varnothing \right) \longrightarrow P(A\cup B) = P(A) + P(B) $
  3. $P(\Omega) = 1$

Ahora, remplazando $B=A^c$ en la expresión 2., se tiene que

$A\cup A^c = \varnothing \longrightarrow P(A\cup A^c) = P(A)+P(A^c)$

y como es claro que $A\cap A^c = \varnothing$, $A \cup A^c = \Omega$ y $P(\Omega) = 1$, se deduce que

$1 = P(\Omega) = P(A \cup A^c) = P(A) + P(A^c) \\ \\

\equiv P(A) + P(A^c) = 1 \\ \\

\equiv \boxed{P(A^c) = 1 - P(A)}$

que es lo que se quería demostrar.


Para deducir que $P(\varnothing) = 0$, basta tomar justo esta expresión que acabamos de deducir. Remplazando ahí $A=\Omega$ nos queda que

$P(\Omega^c) = 1 - P(\Omega)$

Como es claro que $\Omega^c = \varnothing$ y $P(\Omega) = 1$, entonces se tiene que

$\boxed{P(\varnothing) = 1 - 1 = 0}$

que es lo que queríamos demostrar.


Problema 2:
  1. Probar que $(A\subseteq B) \longrightarrow P(B-A)= P(B) - P(A)$
  2. ¿Es esta igualdad válida en general?
  3. Deducir que $(A\subseteq B) \longrightarrow P(A)\leq P(B)$

Solución:
  1. Esta parte la podemos resolver mediante la siguiente deducción

    $\begin{array}{rll}
    (1) & A\subseteq B & ;Hipótesis \\
    &\equiv A\cap B = A & \\
    (2) & B - A = B\cap A^c & ;Def.\;Conjuntos \\
    (3) & B = (B\cap A)\cup (B\cap A^c) & ;Prop.\;Conjuntos \\
    (4) & (B\cap A)\cap (B\cap A^c) = \varnothing & ;Prop.\;Conjuntos \\
    (5) & P(B) = P\left( (B\cap A)\cup (B\cap A^c) \right)& ;de\;(3) \\
    & \;\;\;\;\;\;\;\;\;\; = P\left( B\cap A\right) + P\left(B\cap A^c \right)& ; de\;(4)\;y\;(5) \\
    & \;\;\;\;\;\;\;\;\;\; = P\left( A \right) + P\left( B-A \right)& ; de\;(1)\;y\;(2)\\
    &\equiv P(B-A) = P(B) - P(A) \\
    & \therefore \boxed{A\subseteq B \vdash P(B-A) = P(B) - P(A)}
    \end{array}$

    Finalmente se cumple que:

    $\vdash \left( A\subseteq B \right) \longrightarrow \biggl( P(B-A) = P(B) - P(A) \biggl)$

    Lo cual es lo que se quería demostrar.

    ¿La igualdad se cumple en general? O en otras palabras, ¿Es cierto que

    $P(B-A) = P(B) - P(A)$

    sin importar si se cumple que $A\subseteq B$?


    Si revisamos el razonamiento anterior y eliminamos la hipótesis $A \subseteq B$, notaremos que la igualdad ya no se cumplirá en general. En su lugar se cumplirá que

    $\boxed{P(B-A) = P(B) - P(B\cup A)}$


  2. A partir de lo razonado en la parte anterior, tenemos la siguiente sucesión de teoremas:

    $\begin{array}{ll}
    &\vdash \left( A\subseteq B \right) \longrightarrow \biggl( P(B-A) = P(B) - P(A) \biggl) \\
    \equiv &\vdash \left( A\subseteq B \right) \longrightarrow \biggl( P(A) + P(B-A) = P(B) \biggl)
    \end{array}$

    Como $ 0\leq P(X) \leq 1 $, donde $X=A, B, B-A$, finalmente se tiene que

    $\begin{array}{ll}
    &\boxed{\vdash \left( A\subseteq B \right) \longrightarrow P(A) \leq P(B) }
    \end{array}$



Problema 4:

  1. Probar que $P(A\cup B) = P(A) + P(B) - P(A\cap B)$
  2. Deducir que $P(A\cup B) \leq P(A) + P(B)$

Solución:

  1. Para demostrar esta primera parte tenemos el siguiente razonamiento:

    $\small \begin{array}{lll}
    (1) & A\cup B = (A\triangle B) \cup (A \cap B) & ; Prop.\;de\;Conjuntos \\
    (2) & A\triangle B := (A - B) \cup (B - A) & ; Def.\;de\;Conjuntos \\
    (3) & (A\triangle B)\cap (A \cap B) = \varnothing & ; Prop.\;de\;Conjuntos \\
    (4) & (A - B)\cap (B - A) = \varnothing & ; Prop.\;de\;Conjuntos \\
    (5) & P(A\cup B) = P\biggl((A\triangle B) \cup (A \cap B)\biggl) & ; de\;(1) \\
    & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\, = P(A\triangle B) + P(A \cap B) & ; de\;(3) \\
    & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\, = P(A-B) + P(B-A) + P(A \cap B) & ; de\;(2) \\
    (6) & P(B-A) = P(B) - P(A\cap B ) & ;\;Parte\;2\;del\;ejercicio\;anterior \\
    (7) & P(A-B) = P(A) - P(A\cap B ) & ;\;Parte\;2\;del\;ejercicio\;anterior\\
    (8) & P(A\cup B) = P(A) - P(A\cap B ) + P(B) - P(A\cap B ) + P(A \cap B) & \;de\;(5),\;(6)\;y\;(7) \\
    & \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\, = P(A) + P(B) - P(A\cap B ) \\
    & \therefore \boxed{\vdash P(A\cup B) = P(A) + P(B) - P(A\cap B)}
    \end{array}$


  2. De la parte anterior se tienen la siguiente sucesión de teoremas

    $\vdash P(A\cup B) = P(A) + P(B) - P(A\cap B) \\
    \equiv \; \vdash P(A\cup B) + P(A\cap B) = P(A) + P(B) \\
    \equiv \boxed{\vdash P(A\cup B) \leq P(A) + P(B)}$

Problema 3: Sea $\{E_n\}$ una familia infinita de eventos tales que

$E_1 \supseteq E_2\supseteq E_3\supseteq \cdots \supseteq E_n \supseteq E_{n+1}\supseteq \cdots$.

Probar que

$\displaystyle P\left( \bigcap_{n=1}^\infty E_n \right) = \lim_{n \to \infty} P(E_n)$


Solución:

La demostración se sigue del siguiente razonamiento:

$\begin{array}{lll}
(1) & \left( \forall n \in \mathbb{N}\right) \left(E_n \supseteq E_{n+1} \right) &;\;Hipótesis \\
(2) & \left( \forall n \in \mathbb{N}\right) \left(E_n^c \subseteq E^c_{n+1} \right) &;\;de\;(1) \\
(3) & \displaystyle \left( \forall n \in \mathbb{N}\right) \left(E_n^c \subseteq E^c_{n+1} \right) \longrightarrow P\left(\bigcup_{n=1}^\infty E_n^c \right) = \lim_{n\to\infty} P(E_n^c) &;\;Prop.\;de\;continuidad \\
(4) & \displaystyle P\left(\bigcup_{n=1}^\infty E_n^c \right) = \lim_{n\to\infty} P(E_n^c) &;\;MP(2,3) \\
(5) & \displaystyle \bigcup_{n=1}^\infty E_n^c = \left( \bigcap_{n=1}^\infty E_n \right)^c &;\;Leyes\;de\;De\;Morgan \\
(6) & \displaystyle P \left( \bigcap_{n=1}^\infty E_n \right)^c = \lim_{n\to\infty} P(E_n^c) &;\;de\;(4)\;y\;(5) \\
& \equiv \displaystyle 1 - P \left( \bigcap_{n=1}^\infty E_n \right) = 1 - \lim_{n\to\infty} P(E_n) &;\;PROBLEMA\;1 \\
& \equiv \displaystyle { P \left( \bigcap_{n=1}^\infty E_n \right) = \lim_{n\to\infty} P(E_n)}& \\
\end{array}$

$\therefore \boxed{ \left( \forall n \in \mathbb{N}\right) \left(E_n \supseteq E_{n+1} \right) \vdash \displaystyle P \left( \bigcap_{n=1}^\infty E_n \right) = \lim_{n\to\infty} P(E_n)} $


Problema 5: Un sistema de control está formado por 10 componentes. La falla de cualquiera de ellos provoca la falla del sistema completo. Se sabe que la probabilidad de falla de cada componente es $\leq 0,0002$. Probar que la probabilidad de que el sistema funcione correctamente es $\geq 0,998$

Solución: Si cada componente tiene una probabilidad $\leq 0,0002$ de fallar, entonces tienen una probabilidad $\geq 1 - 0,0002 = 0,9998$ de funcionar correctamente. Por lo tanto, la probabilidad de que el sistema funcione correctamente estará dada por

$\boxed{P(funciona\;correctamente) \geq (0,9998)^{10} = 0,998001799}$


Problema 6: Sobre una mesa hay tres naipes boca abajo: Son un AS y dos Jokers, y hay que adivinar cual de ellas es un AS para ganar. Cuando usted elige un naipe, justo en ese instante el croupier le muestra una de las dos cartas, que resulta no ser el AS, y le da la oportunidad de cambiar su de elección. ¿Qué conviene más: mantener la elección o elegir la otra carta desconocida?

Solución: Una buena alternativa para responder a esta pregunta es colocándonos en dos escenarios distintos: Uno donde nunca cambiamos de elección y el otro donde siempre lo hacemos.

Si nunca cambiamos de elección, claramente nuestra probabilidad de ganar el juego será de 1/3.

En el caso en que siempre cambiamos de elección ocurre el siguiente fenómeno: Si por casualidad hemos elegido el AS en nuestra primera elección (con probabilidad 1/3), entonces siempre perderemos al cambiar de carta porque estaríamos eligiendo el único Joker que queda. Por otro lado, si por casualidad hemos elegido alguno de los Jokers (con probabilidad 2/3), el crupier se verá en la obligación de mostrar el Joker restante, por lo que al cambiar de opción siempre ganaremos. De aquí vemos que tomando siempre la opción de cambiar de elección tenemos una probabilidad de 2/3 de ganar, el doble con respecto a mantener la decisión, por lo tanto es mucho más conveniente siempre cambiar de elección.

Compartir:

Probabilidades [Parte 2: Experimentos con resultados equiprobables y técnicas de conteo]



En la entrada anterior concluimos con el ejemplo del lanzamiento de un dado de 6 caras (1d6). Este, junto con el lanzamiento de una moneda, son ejemplos de lo que llamamos experimentos de resultados equiprobable. A lo largo de esta entrada veremos algunos resultados adicionales que agregarán detalles a lo que ya sabemos sobre este tipo de experimentos.

Casos favorables v/s casos posibles

Las primeras aplicaciones de la teoría de las probabilidades emergen de los juegos de azar, los cuales generalmente consisten de experimentos no deterministas donde el espacio muestral está dado por un conjunto finito $\Omega = \{\omega_1, \cdots , \omega_N\}$, donde cada evento $\{\omega_i\}$, con $1 \leq i \leq N $, tiene la misma probabilidad de ocurrir.


De la noción de medida de probabilidad inducida por el límite de las frecuencias relativas, mostrada en la entrada anterior, podemos establecer que la probabilidad de que ocurra un evento $A$ está dada por

$\Large \displaystyle P(A) = \lim_{N\to \infty} g_N(A) = \lim_{N\to \infty} \dfrac{f_N(A)}{N} = \dfrac{\#A}{\#\Omega}$

Donde el símbolo «$\#$» hace referencia a la cardinalidad (cantidad de elementos) del conjunto que aparece a su derecha . Esto es la fórmula conocida como "casos favorables sobre casos posibles".

Como podemos ver, para este tipo de situaciones el cálculo de probabilidades se reduce a calcular el cardinal de los conjuntos, por lo que es útil revisar algunos resultados que permitan hacer esto sin la necesidad de contarlos uno a uno.


Técnicas de Conteo

El objetivo de esta sección es la de introducir formalmente las nociones de combinatoria, variación y permutación, para ello diseñaremos algunos experimentos pensados.

Supongamos que existe un objeto que denominaremos "la máquina más aleatoria del mundo", la cual consiste de una caja negra, una pantalla, un botón de acción y otro de reset. Esta máquina tiene las siguientes propiedades:
  • Sólo tiene una configuración personalizable, la cardinalidad del espacio muestral $\Omega= \{\omega_1,\omega_2, \cdots\}$.
  • Cuando se presiona el botón de acción, mostrará aleatoriamente un elemento de $\Omega$ en la pantalla.
  • Cuando muestra un resultado, lo guarda en la memoria para no volverlo a mostrar.
  • Nunca favorece ningún resultado posible por sobre otro
  • Cuando la máquina ya ha mostrado todos los resultados posibles, al presionar el botón de acción se congela y no muestra nada.
  • El botón de reset hace que la máquina olvide los resultados que ha mostrado.
Lo que haremos ahora será diseñar algunos experimentos pensados con esta máquina teórica y analizar sus respectivos espacios muestrales.

Experimento 1 (AORm):
Accionar - anotar en orden - resetear, repetir $m$ veces

Se configura la máquina con $\#\Omega = N$ y se repiten $m$ veces la siguiente serie de pasos:

  1. Presionar el botón de acción.
  2. Anotar el resultado en una lista ordenada.
  3. Resetear.
Cuando terminamos, obtendremos una lista ordenada de $m$ elementos de $\Omega = \{\omega_1, \cdots, \omega_N\}$, por lo que el espacio muestral de este experimento puede ser representado como

$\Large \Omega_{AORm} = \underbrace{\Omega \times \cdots \times \Omega}_{m\;veces} = \Omega^m $,

por lo tanto, la cardinalidad del espacio muestral será

$\Large \#\Omega_{AORm} = \#\left(\Omega^m \right)= \left(\#\Omega \right)^m = N^m$

En otras palabras, al finalizar el experimento, lo que obtendremos será una de los $N^m$ posibles listados de los elementos de $\Omega$. Por lo tanto, la probabilidad de obtener una lista en particular será justo $1/N^m$

Experimento 2 (AOk):
Accionar - anotar en orden, repetir $k$ veces

Se configura la máquina con $\#\Omega = N$ y se repiten $k$ veces (con $k\leq N)$ la siguiente serie de pasos
  1. Presionar el botón de acción.
  2. Anotar el resultado en una lista ordenada.
Cuando terminemos, lo que obtendremos será una lista con $k$ elementos de $\Omega = \{\omega_1, \cdots, \omega_N\}$, pero donde cada elemento nunca es igual a algún elemento que le preceda.

Como la máquina no favorece ningún resultado por sobre otro (es completamente aleatoria), es posible asumir sin perdida de generalidad que al accionar la máquina por primera vez ocurrió el evento $\{\omega_1\}$, por lo que el espacio muestral de la siguiente acción será $\Omega - \{\omega_1\}$. Análogamente podemos asumir que al accionarla por segunda vez ocurrie el evento $\{\omega_2\}$, por lo que el espacio muestral de la siguiente acción será $\left(\Omega-\{\omega_1\}\right)-\{\omega_2\}$, y así sucesivamente, de modo tal que la $k$-ésima acción tendrá espacio muestral $( \cdots ((\Omega-\{\omega_1\})-\{\omega_2\})- \cdots)-\{\omega_{k-1}\}$. De este modo, el espacio muestral del experimento estará dado por

$\Large \Omega_{AOk} = \underbrace{\Omega \times \left( \Omega - \{\omega_1\} \right) \times \left(\left(\Omega-\{\omega_1\}\right)-\{\omega_2\}\right) \times \cdots \\ \\
\cdots \times \left(( \cdots ((\Omega-\{\omega_1\})-\{\omega_2\})- \cdots)-\{\omega_{k-1}\}\right)}_{producto\;cartesiano\;de\;k\;conjuntos} $

Por lo tanto, la cardinalidad del espacio muestral es

$\Large \#\Omega_{AOk} = N (N-1)(N-2) \cdots (N-(k-1)) = \dfrac{N!}{(N-k)!}$

Definición: Se define la variación de $N$ sobre $k$ (con $k\leq N$) como el número dado por

$\Large (N)_k = \dfrac{N!}{(N-k)!}$

Este viene representado el número de $k$-tuplas sin elementos repetidos que se pueden formar a partir de un conjunto de $N$ elementos.

Para el caso en que $N=k$, se asume que $0! = 1$, y se dice que $(N)_N = N!$ es el número de formas en que se puede ordenar un conjunto de $N$ elementos. Esto es lo que conocemos como permutación.


Similar al caso anterior, tenemos que la probabilidad de obtener una lista (ordenada) en particular viene dada por $1/(N)_k$

Experimento 3 (ADk):
Accionar - anotar en desorden, repetir $k$ veces

Este experimento es exactamente el mismo que el anterior, sólo que ahora no importa el orden en que aparece cada elemento de $\Omega$; en otras palabras, dos $k$-tuplas con los mismos elementos, pero en distinto orden, corresponden ahora al mismo evento. En este caso, denotaremos al espacio muestral de este experimento por $\Omega_{ADk}$. Como los elementos de cada $k$-tupla (sin elementos repetidos) se pueden ordenar de $(k)_k = k!$ formas diferentes, tendremos que

$\Large \#\Omega_{ADk} = \dfrac{\#\Omega_{AOk}}{(k)_k} = \dfrac{(N)_k}{k!} = \dfrac{N!}{k!(N-k)!}$


Definición: Se define la combinación de $N$ sobre $k$ (con $k\leq N$) como el número de dado por

$\Large \displaystyle \binom{N}{k} = \dfrac{N!}{k!(N-k)!}$

Este representa el número de subconjuntos posibles que se pueden formar con $k$ elementos de un conjunto con $N$ elementos.


De aquí tenemos que, por lo tanto cada lista (desordenada) tiene una probabilidad de ser obtenida igual a $1/\binom{N}{k}$


Compartir:

Probabilidades [Parte 1: Introducción y Definiciones Elementales]



Introducción

Cada proceso que ocurre en la naturaleza puede ser clasificado como determinista o indeterminista. Un proceso determinista es aquel que, una vez fijadas las condiciones iniciales, proporciona siempre los mismos resultados. Un proceso indeterminista, por otro lado, es aquel que admite un espectro de resultados posibles aún cuando se han fijado sus condiciones iniciales. Estos resultados posibles son denominados estados. Es en este contexto en que emerge La Teoría de las Probabilidades como una ciencia formal mediante la cual podemos adquirir información razonable sobre la frecuencia con que un proceso indeterminista tiende a llegar a un determinado de estado, o conjuntos de estados

Del determinismo al indeterminismo

Consideremos el proceso del lanzamiento de un proyectil dentro de un entorno controlado. Es un hecho experimental que, para cada posición y velocidad iniciales, existe una única posición final como destino; en otras palabras, las condiciones iniciales determinan la posición final del proyectil (o estado final). Dado que para cada conjunto de condiciones iniciales existe un único resultado posible, decimos que existe un modelo determinista del sistema. En este caso, el modelo viene dado por la Dinámica de Newton. Pero qué pasaría si el lanzamiento del proyectil ya no se realiza en un entorno tan controlado y sucede que ahora hay, por ejemplo, corrientes de aire capaces de alterar la trayectoria del proyectil de un modo que desconocemos, entonces ocurrirá que sucesivas observaciones nos mostrarán que para cada conjunto de condiciones iniciales existen más de un punto de caída posible

El punto en donde caerá cada hoja seca de un árbol depende factores como la temperatura, dirección del viento, peso, etc. y cada una de esos factores dependen a su vez del tiempo. Para cada hoja existe un conjunto de lugares posibles donde caer, y el punto en que tocará finalmente el suelo puede variar mucho aún cuando las condiciones iniciales varíen tan solo un poco.


Mientras más complejo es un proceso, más información necesitamos para establecer las condiciones iniciales que nos permitirán determinar su estado final, y además la precisión de tales datos también debe ser cada vez mayor, ya que pequeñas variaciones en las condiciones iniciales dentro de un proceso de alta complejidad pueden alterar de forma notoria el estado final del proceso.


¿Que es el azar?

El azar es una propiedad intrínseca de los procesos no-determinista; de hecho, decimos que un proceso es azaroso (o completamente aleatorio) cuando ninguno de sus estados posibles parece ocurrir con mayor frecuencia que el resto. El ejemplo más sencillo es el lanzamiento de una moneda. A medida que aumenta el número de lanzamientos, se observa que la frecuencia relativa con que aparecen caras y sellos son cada vez más parecidos. Es decir:

$\huge \lim_{N\to \infty} \dfrac{C}{N} = \lim_{N\to \infty} \dfrac{S}{N} = \dfrac{1}{2}$,

donde: $N:=$ número de lanzamientos, $C:=$ número de caras, $S:=$ número de sellos.

Es decir, a medida que el número de lanzamiento aumenta, la proporción de caras y sellos tiende a coincidir justo con la mitad de los lanzamientos totales. El sistema no favorece a ningún estado posible (Cara o Sello), ambos tienen la misma probabilidad de ocurrir. Si existiese algún agente externo que favorezca un resultado por sobre otro, entonces el proceso es menos aleatorio.

El espacio de Probabilidades

La noción fundamental de la teoría de las probabilidades es una estructura matemática que conoceremos por el nombre de Espacio de Probabilidades. Un Espacio de Probabilidades $(\Omega, \Sigma, P)$ es una colección de tres componentes:

  1. La reunión de todos los Estados Posibles $\omega$ forman un conjunto no-vacío $\Omega$ que denominamos Espacio Muestral

    Ejemplos: 
    • Si realizamos el experimento aleatorio de lanzar una moneda al aire, entonces tenemos dos resultados posibles: Cara (C) o Sello (S). El espacio muestral es, por lo tanto:
      $$\Omega_{1m} = \{C, S\}.$$
    • Si el experimento ahora consistiese en lanzar dos monedas, una a continuación de la otra, entonces el espacio muestral contendrá todas las combinaciones posibles:
      $$\Omega_{2m}=\{ (C,C), (C,S), (S,C), (S,S)\}.$$
    • El lanzamiento de un dado de 6 caras (1d6) tiene un espacio muestral dado por:
      $$\Omega_{1d6} = \{1,2,3,4,5,6\}.$$
    • El tiempo de vida de un aparato electrónico (medido en horas) que podría estropearse en cualquier momento está dado por:
      $$\Omega_{e}=[0,+\infty[.$$
  2. Una $\sigma$-álgebra (o espacio medible) representa el conjunto de todos los subconjuntos observables del espacio muestral $\Omega$. Se dice que el par $\Sigma =(\Omega, \mathcal{A})$ es una $\sigma$-álgebra sobre el espacio muestral $\Omega$ si se cumple que:

    • $\Large\varnothing,\Omega \in \mathcal{A}$
    • $\Large\left(E \in \mathcal{A}\right) \longrightarrow \left(E^c:=\Omega - E \in \mathcal{A}\right)$
    • $\Large\left(E_1,E_2, \cdots \in \mathcal{A}\right) \longrightarrow \left(\bigcup_{i=1}^\infty E_i \in \mathcal{A}\right)$

    Los objetos $X\in\mathcal{A}$ son denominados Eventos de $\Omega$ y pueden involucrar uno, mas o ninguno de sus estados posibles.

    Ejemplos:
    • Para el lanzamiento de una moneda, la $\sigma$-álgebra está dada por $\Sigma_{1m}=\{\Omega_{1m},\mathcal{A}_{1m}\}$, donde

      $\Omega_{1m}= \{C,S\}\\
      \mathcal{A}_{1m}= \{\varnothing, \{C\},\{S\}, \{C,S\}\} = \{\varnothing, \{C\},\{S\}, \Omega_{1m} \} $

      Cada elemento de $\mathcal{A}_{1m}$ es un evento, a saber:

      $\varnothing$ -> No cae ni cara ni sello (evento imposible).
      $\{C\}$ -> Cae cara.
      $\{S\}$ -> Cae sello.
      $\Omega_{1m}$ -> Cae cualquiera de los dos, cara o sello (evento seguro).


    • Para el lanzamiento de dos monedas, una detrás de la otra, la $\sigma$-álgebra está dada por $\Sigma_{2m}=\{\Omega_{2m},\mathcal{A}_{2m}\}$, donde

      $\Omega_{2m}= \{(C,C),(C,S),(S,C),(S,S)\}\\
      \mathcal{A}_{1m}= \{\varnothing, \{(C,C)\}, \{(C,S)\}, \{(S,C)\}, \{(S,S)\}, \cdots \\
      \cdots, \{(C,C),(C,S)\}, \{(C,C),(S,C)\}, \{(C,C),(S,S)\}, \cdots \\
      \cdots, \{(C,C),(C,S),(S,C)\}, \{(C,C),(C,S),(S,S)\}, \cdots \\
      \cdots, \{(C,C),(S,C),(S,S)\}, \{(C,C),(C,S),(S,C),(S,S)\}\} $

      Cada elemento de $\mathcal{A}_{2m}$ es un evento, a continuación se muestran algunos ejemplos:

      $\varnothing$ -> No cae ni cara ni sello (evento imposible).
      $\{(C,C)\}$ -> Caen dos caras seguidas.
      $\{(C,S)\}$ -> Cae primero cara, y luego sello.
      .
      .
      .
      $\{(C,C),(C,S)\}$ -> Siempre sale cara en el primer lanzamiento
      $\{(C,C),(S,C)\}$ -> Siempre sale cara en el segundo lanzamiento.
      $\{(C,C),(S,S)\}$ -> Los dos lanzamientos son iguales.
      .
      .
      .
      $\{(C,C),(C,S),(S,S)\}$ -> Nunca sale cara después de obtener un sello.
      $\{(C,C),(S,C),(S,S)\}$ -> Nunca sale sello después de obtener una cara.
      $\{(C,C),(C,S),(S,C),(S,S)\}$ -> Sale cualquiera de los resultados posibles (evento seguro)


    • Para el tiempo de vida de un aparato electrónico (medido en horas) que podría estropearse en cualquier momento se tiene que la $\sigma$-álgebra $\Sigma_e =(\Omega_e, \mathcal{A}_e)$ esta dada por:

      $\Omega_{e}=[0,+\infty[.$
      $\mathcal{A}_e = \{ \{I\} \;|\; I \subset \Omega_{e} \}$

      Así, si $I_t = [0,t]$, entonces se tienen los eventos de la forma

      $\{I_t\}$ -> El aparato electrónico no sobrevive más allá del tiempo $t$.

  3. Una medida de probabilidad $P$ es una función que, dada una $\sigma$-álgebra $\Sigma = (\Omega, \mathcal{A})$, asigna una probabilidad a cada evento $E\in \mathcal{A}$.

    Si $E_1, E_2, \cdots \in \mathcal{A}$, entonces se cumple que:

    • $\Large 0 \leq P(E_1) \leq 1 $

    • $\Large P(\Omega) = 1 $

    • $\large \displaystyle \left(E_i \cap E_j =\varnothing \right) \longrightarrow P\left(\bigcup_{i=1}^n E_i\right) = \sum_{i=1}^n P(E_i)$

    • $\large \displaystyle \left( E_n \subseteq E_{n+1} \right) \longrightarrow P \left( \bigcup_{n=1}^\infty E_n \right) = \lim_{n\to\infty}P(A_n) $

    Esta noción de medida de probabilidad se puede comprender a través de la idea intuitiva de la probabilidad como "límite de frecuencias relativas". Tomemos, por ejemplo, el experimento en donde se lanza $N$ veces un dado de 6 caras. El espacio muestral de cada lanzamiento es $\Omega_{1d6}=\{1,2,3,4,5,6\}$. Si $A$ es un evento de $\Omega_{1d6}$, entonces podemos medir una frecuencia $f_N(A)$ que resulta de contar las veces que ocurre $A$ entre el número de lanzamientos $N$. Se verifica fácilmente que

    $\Large 0\leq f_N(A) \leq f_N(\Omega_{1d6}) = N$
    $\Large A\cap B = \varnothing \longrightarrow f_N(A\cup B) =f_N(A) + f_N(B)$

    Ahora, si llamamos $g_N(A)=f_N(A)/N$ (el número de veces que ocurre $A$ entre los $N$ lanzamientos, o frecuencia relativa de $A$), entonces veremos que la función $g_N$ cumple las tres primeras propiedades de una medida de probabilidad y es razonable definir

    $\huge \displaystyle P(A) = \lim_{N\to \infty}g_N(A).$

    Sólo la cuarta propiedad (de continuidad) no se puede deducir de este modo, pero es introducida por "motivos técnicos": Muchos resultados importantes no se podrían demostrar sin esta propiedad

    Ejemplo: Continuando el análisis del lanzamiento de un dado de 6 caras $N$ veces, entonces tendremos que los eventos $\{1\}$, $\{2\}$, ..., $\{6\}$ tendrán una frecuencia relativa de la forma


     $\Large g_N(\{x\}) = f_N(\{x\})/N$
    (Número de veces que salió el número "$x$", entre los $N$ lanzamientos)

    Y si el experimento se repite un cantidad de veces lo suficientemente grande (y el dado no favorece ningún estado por sobre el resto), entonces veremos que

    $\large \displaystyle \lim_{N\to \infty} g_N(\Omega_{1d6}) = 1 $
    $\large \displaystyle \lim_{N\to \infty} g_N(\{x\}) = \dfrac{1}{6}$, donde $x=1,2,3,4,5,6$

    Ahora, si definimos

    $\Large \displaystyle P(\{x\}) = \lim_{N\to \infty} g_N(\{x\}),$

    podremos ver que se cumple que, por ejemplo

    $\displaystyle P( x=\{1,3,5\} ) = P(\{1\}\cup\{3\}\cup\{5\}) \\
    \hspace{1cm}= P(\{1\})+ P(\{3\}) + P(\{5\}) \\
    \hspace{1cm}= \dfrac{1}{6}+\dfrac{1}{6}+\dfrac{1}{6} =\dfrac{3}{6} = \dfrac{1}{2}$

    que es justo la probabilidad de obtener un número impar al lanzar 1d6.

Compartir:

Aprendiendo C++ [Parte 3: Variables de Punto Flotante y Moldeamiento Numérico - El método de Euler para Resolver Ecuaciones Diferenciales Ordinarias ]



En esta entrada vamos a introducir las variables de punto flotante y escribiremos un programa que realizará un modelamiento numérico del proceso de decaimiento radiactivo.

Como sabemos, el proceso de decaimiento radiactivo se modela a través de la ecuación diferencial ordinaria con valor inicial

(1)$\hspace{1cm}$$\dfrac{d}{dt}m(t) = -km(t),$

(2)$\hspace{1cm}$$m(0) = m_0,$

donde $m(t)$ es la cantidad de materia en cada instante de tiempo $t$, $k>0$ es la constante de decaimiento y $m_0$ es la masa inicial del sistema.

Para resolver este problema utilizaremos el enfoque numérico entregado por el método de Euler.

También veremos el uso de un nuevo archivo de cabecera, fstream, el cual nos permitirá abrir, crear, escribir y leer ficheros con datos.

Finalmente, presentaremos los datos que entrega el programa a través de un gráfico con gnuplot.


El método de Euler

En general, el método de Euler está pensado para resolver una ecuación diferencial ordinaria de primer orden de la forma

(3)$\hspace{1cm}$ $\dfrac{dy(t)}{dt} = f(x,t),$

(4)$\hspace{1cm}$ $y(0) = y_0,$

Ahora, por la definición de derivada tenemos que

(5)$\hspace{1cm}$ $\displaystyle \dfrac{dy(t)}{dt} = \lim_{h\to 0} \dfrac{y(t+h) - y(t)}{h}$

por lo que, para valores pequeños de $h$, a partir de las expresiones (3) y (5) podemos escribir


(6)$\hspace{1cm}$ $\displaystyle \dfrac{y(t+h) - y(t)}{h} \approx f(x,t)$

de modo que ahora el sistema (3)-(4) ahora puede ser escrito como

(7)$\hspace{1cm}$ $y(0)=f(x,0)=y_0$

(8)$\hspace{1cm}$ $y(t+h) \approx y(t) + h f(x,t)$

De aquí tenemos que, si tomamos $t=0$, de las ecuaciones (7) y (8) llegaremos a que

(9)$\hspace{1cm}$ $y(h) \approx y(0) + h f(x,0)$

Luego, de (8) y (9)

(10)$\hspace{1cm}$ $y(2h) = y(h+h) \approx y(h) + h f(x,h)$

De (8) y (10)

(11)$\hspace{1cm}$ $y(3h) \approx y(2h) + h f(x,2h)$

y así sucesivamente.


De aqui tenemos que las expresiones entre (9) y (11) (ambas incluidas) muestran un proceso inductivo que puede ser generalizado mediante la fórmula

(12)$\hspace{1cm}$ $y( (i+1) h) \approx y(ih) + h f(x,ih)$

donde $i=1,2,3,\cdots$


Implementación


Si regresamos a la expresión (5), podemos ver que se puede escribir

(13)$\hspace{1cm}$ $h=t_f - t_0$
(14)$\hspace{1cm}$ $t_f =t_0 + h$

donde ahora es más claro cómo $h$ representa la longitud de tiempo del intervalo $[t_i, t_f]$ (tiempo inicial y tiempo final). Ahora, supongamos que dividimos ese intervalo en $n$ trozos tal y como se muestra en el siguiente esquema



y ahora aplicamos el método de Euler para cada trozo de tiempo $dt$ obtenido.

(15)$\hspace{1cm}$ $t_i = 0$ (instante inicial)
(16)$\hspace{1cm}$ $t_f =$ Tiempo de observación
(17)$\hspace{1cm}$ $n=$ Número de particiones
(18)$\hspace{1cm}$ $dt=t_f/n$ (tamaño de las particiones)
(19)$\hspace{1cm}$ $\underbrace{y( (i+1)dt )}_{y[i+1]} = \underbrace{y(idt)}_{y[i]} + f(x,idt)dt$ (método de Euler)

Esto es lo que finalmente escribiremos en la forma de código.

Escribiendo el código


Partiremos creando el fichero decaimiento.c

$ pico decaimiento.c

Como siempre, la escritura de nuestro código parte con la estructura básica
#include<iostream>
#include<fstream>

using namespace std;

main(){

}
La novedad con respecto a nuestro código anterior aquí es la linea #include<fstream>. Esto nos permitirá utiliza comandos ofstream que necesitaremos en esta ocasión. Como se mencionó anteriormente, fstream es un archivo de cabecera que agrega las funcionalidades de abrir/crear y escribir/leer ficheros con datos. Finalmente, la linea using namespace std; nos permitirá ahorrarnos muchos "std::" en el código.

Lo siguiente será la declaración de las variables que serán utilizadas
#include<iostream>
#include<fstream>

using namespace std;

main(){
unsigned short int n, i=-1;
float ti=0, tf, dt, k=1;

}

Como se vió en la entrada anterior, la linea unsigned short int n, i=-1; reserva memoria para las variables n e i para guardar valores positivos. La linea float ti=0, tf, dt, k=1; introduce las variables que pueden asumir valores de punto flotante o decimales (como 0.5, etc...).

Las variables de punto flotante de C++ son:

float: 4 bytes de memoria. Permite valores entre $- 3,4\cdot 10^{38}$ y $3,4\cdot 10^{38}$, con hasta 6 decimales. También admite enteros

double: 8 bytes de memoria. Permite valores entre $- 1,79\cdot 10^{308}$ y $1,79\cdot 10^{308}$, con hasta 14 decimales. También admite enteros

Esto puede variar según la máquina.

El resto del código toma la siguiente forma:
#include<iostream>
#include<fstream>

using namespace std;

main(){
unsigned short int n, i=-1;
float ti=0, tf, dt, k=1;

 cout<<"ingresa el numero de iteraciones"<<endl;
 cin>>n;
 cout<<"ingrese el tiempo de observación"<<endl;
 cin>>tf;

 dt=tf/n;

float m[n]; 

 cout<<"ingrese la masa inicial"<<endl;
 cin>>m[0];

ofstream datnuout("datnu");

do{i=i+1; 
   datnuout<<ti<< "          ";
   datnuout<<m[i]<<endl;

   m[i+1]=m[i] - k*m[i]*dt;
   m[i]=m[i+1]; 

   ti=ti+dt;

   }while(i<=n-1);
datnuout.close();
}

Descargas: Código Limpio - Código con comentarios

Aquí hay algunas cosas nuevas (con respecto a las entradas anteriores) que merecen ser explicadas.

La linea float m[n]; introduce a la variable m como un arreglo de números de punto flotante que puede guardar $n$ valores (el $n$ es entregado por el usuario durante la ejecución del programa)

$m[n] = [\underbrace{m(1), m(2), \cdots, m(n)}_{n\;valores}]$

La linea ofstream datnuout("datnu"); crea/abre un fichero de nombre "datnu", en el que podemos escribir datos usando la sentencia "datnuout".

La parte del código
datnuout<<ti<< "          ";
datnuout<<m[i]<<endl;
escribe en el fichero "datnu" el dato ti, seguido de un espacio, luego escribe el dato m[i] y finalmente hace un salto de linea. Esto es un par "(tiempo, masa)".

El método de Euler propiamente tal, está dado por

   m[i+1]=m[i] - k*m[i]*dt;
   m[i]=m[i+1]; 

   ti=ti+dt;

La linea datnuout.close(); cierra el fichero "datnu"

Finalmente, guardamos (Crtl+O) y compilamos
$ c++ decaimiento.c -o decaimiento

Si todo ha salido bien, al ejecutar el programa se nos debería generar el fichero "datnu" con los datos que reflejan el resultado del problema.


Si ahora escribimos en la terminal
$ pico datnu
veremos lo siguiente:


Representación gráfica de los resultados


En caso de no tener gnuplot instalado en el sistema, en ubuntu la solución es simple. Lo puedes instalar escribiendo
$ sudo apt-get install gnuplot 
Para iniciar gnplot basta con escribir
$ gnuplot 

Ahora le pediremos que nos grafique los datos del fichero "datnu" y la solución analítica del problema para comparar, escribimos
gnuplot> plot "datnu", 90*exp(-x)
y obtendremos el siguiente gráfico


Mientras más iteraciones, mejor será el ajuste entregado por el programa.
Compartir:

El Cálculo Deductivo [Parte 3: El lenguaje del cálculo proposicional]



En esta entrada se hará una descripción detallada de los elementos que componen el lenguaje del cálculo proposicional, estos conceptos son necesarios para introducir el razonamiento lógico elemental desde un enfoque formal.

Alfabeto y Sintaxis

Consideremos el alfabeto $A_0=\mathbb{N}$ y el siguiente convenio de notaciones:
  • $0:= \; \downarrow $
  • $1:= \; ( $
  • $2:= \; ) $
  • $3+i:= p_i \;$
Donde $i$ es cualquier número natural, se define la sintaxis del cálculo proposicional como la generada por las siguientes reglas recursivas:
  • Para cualquier $i\in\mathbb{N}$, $p_i$ es una expresión.
  • Si $e_i$ y $e_j$ son expresiones, entonces $(e_i \downarrow e_j)$ es una expresión.
Se dice que $A_0$ provisto de éstas reglas de sintaxis es un lenguaje para el cálculo proposicional y lo representamos por $\mathcal{P}_0$. Las cadenas de $A_0$ que cumplen con la sintaxis que hemos introducido se dice que son expresiones del cálculo proposicional o, en forma resumida, expresiones de $\mathcal{P}_0$.

*Notas:

  • El símbolo "$\downarrow$" representa al conector binario llamado negación conjunta, la expresión $e_i \downarrow e_j$ se lee en castellano como "ni $e_i$ ni $e_j$". Semánticamente hablando, la expresión $e_i \downarrow e_j$ es verdadera cuando $e_i$ y $e_j$ son ambas afirmaciones falsas, y es falsa en cualquier otro caso.
  • Al momento de introducir la sintaxis de $\mathcal{P}_0$ hemos hecho uso de algunos metasímbolos. Sabemos que "$e_i$" y "$e_j$" no son expresiones del cálculo proposicional, ni siquiera son símbolos de $A_0$, pero nos permiten describir y definir lo que ocurre cuando «$e_i$» y «$e_j$» son sustituidos por expresiones cualesquiera de $\mathcal{P}_0$. Los metasímbolos que cumplen ese propósito reciben el nombre de metavariables del cálculo proposicional. La mayoría de los resultados que obtendremos sobre este tema son, de heho, escritos en términos de metasímbolos.
  • Debe prestarse especial atención al uso de comillas en estas cosas: Las comillas «.» se utiliza para introducir un nombre o para indicar que el énfasis va sobre la cadena de símbolos más que sobre el concepto que tal escritura representa, las comillas "." se centra en señalar una palabra en un sentido que puede ser distinto del usual, para dar énfasis al significado pretendido de una expresión o para destacar algo y, finalmente, las comillas simples '' cumplen la misma función que las dobles, solo que van dentro de las comillas dobles por un asunto de jerarquía.

Debido a su uso frecuente y a modo de simplificación, se introducen los siguientes conectores derivados de $\mathcal{P}_0$

Definición:
Sean $e_i$ y $e_j$ expresiones cualesquiera de $\mathcal{P}_0$, se definen:

  1. El negador: $(\neg e_i) := (e_i \downarrow e_i) $.
    Se lee: No $e_i$.
  2. El disyuntor: $(e_i \vee e_j) := (\neg (e_i \downarrow e_j))$.
    Se lee: $e_i$ o $e_j$.
  3. El implicador: $(e_i \rightarrow e_j):= ((\neg e_i) \vee e_j)$.
    Se lee: $e_i$ implica $e_j$.
  4. El conjuntor: $(e_i \wedge e_j) := (\neg((\neg e_i) \vee (\neg e_j)))$.
    Se lee: $e_i$ y $e_j$.
  5. El bicondicional: $(e_i \leftrightarrow e_j):= ((e_i\rightarrow e_j)\wedge (e_j \rightarrow e_i))$.
    Se lee: $e_i$ si, y sólo si $e_j$.
  6. La disyunción exclusiva: $(e_i \underline{\vee} e_j) := (\neg(e_i \leftrightarrow e_j))$.
    Se lee: O bien $e_i$, o bien $e_j$.

Llegados a este punto es evidente notar la sobreabundancia de paréntesis en la definición anterior. Para solucionar esto establecemos el siguiente convenio de notación:

Notación - Eliminación de Paréntesis 1: En adelante se tendrá que, si $(C)$ es una expresión de $\mathcal{P}_0$, entonces $C:= (C)$ siempre que «$(C)$» no esté escrita de modo tal que forme parte de otra expresión. Este convenio de notación nos permite eliminar los paréntesis mas externos de cualquier expresión con el objetivo de no sobrecargar tanto la notación.

Ejemplo: Tomando las expresiones de la definición anterior, podemos escribir:

  1. $\neg e_i = e_i \downarrow e_j$
  2. $e_i \vee e_j = \neg(e_i\downarrow e_j)$

Notación - Eliminación de Paréntesis 2: El negador ($\neg$) liga más fuerte que los demás conectores. Es decir, si tenemos, por ejemplo, $\neg e_i \rightarrow e_j$, entonces la interpretación correcta es $(\neg e_i) \rightarrow e_j$, nunca $\neg(e_i \rightarrow e_j)$.

Ejemplo: Tomando, de nuevo, las expresiones de la definición anterior, se tiene que

  1. $e_i \rightarrow e_j = \neg e_i \vee e_j$
  2. $e_i \wedge e_j = \neg(\neg e_i \vee \neg e_j)$
  3. $e_i \leftrightarrow e_j = (e_i\rightarrow e_j) \wedge (e_j \rightarrow e_i)$
  4. $e_i \underline{\vee} e_j = \neg(e_i \leftrightarrow e_j)$


En esencia, el cálculo proposicional que estamos construyendo sólo tiene un conector, la negación conjunta. Todos los demás conectores fueron construidos a partir de esta.

Los símbolos de paréntesis sólo sirven para agrupar expresiones en caso de que la jerarquía de los conectores sea confusa. Por ejemplo, no es lo mismo escribir «$(e_i\rightarrow e_j) \downarrow e_k$» que «$e_i\rightarrow (e_j \downarrow e_k)$», el no usar paréntesis genera confusión en este caso. Hay que estar atentos a los convenios de eliminación de paréntesis anteriormente mostrados.

Si bien es cierto, los símbolos del cálculo proposicional tienen cierta carga semántica sobre ellos, como que $p_i$ representa una proposición, $\neg p_i$ es la negación de una proposición, $p_i\rightarrow p_j$ se lee "$p_i$ implica $p_j$", etc., se debe hacer énfasis en que el método que hemos utilizado para introducirlos es completamente independiente de dichos significados. Por supuesto, nos referiremos a "$\neg$" como "el negador" y a "$\rightarrow$" como "el implicador" porque en el estudio de la lógica se asocian rápidamente con la noción intuitiva que cargan dichos nombres, pero nada más que por eso. Si se quiere revisar su correcto uso, se debe recurrir a la definición que acabamos de dar porque es lo único rigurosamente planteado que tenemos sobre su uso, y además no es complicado hacerlo de este modo.

Hasta este punto ya tenemos completamente definida la escritura en $\mathcal{P}_0$, ahora solo nos falta establecer el sistema deductivo formal que, en esencia, construye la maquinaria que nos permite ``calcular'' expresiones de $\mathcal{P}_0$

Sistema deductivo

Definición - Axiomas de Łukasiewicz: Sean $e_i$, $e_j$ y $e_k$ expresiones cualesquiera de $\mathcal{P}_0$. Se define el Esquema axiomático Łukasiewicz como el conjunto de todas las expresiones de $\mathcal{P}_0$ que tienen alguna de las siguientes formas:

$\begin{array}{ll}
(a1) & e_i \rightarrow (e_j \rightarrow e_i)\\
(a2) & (e_i \rightarrow (e_j \rightarrow e_k)) \rightarrow ((e_i \rightarrow e_j) \rightarrow (e_i \rightarrow e_k))\\
(a3) & (\neg e_i \rightarrow \neg e_j) \rightarrow (e_j \rightarrow e_i)
\end{array}$



Definición - Modus Ponens: Se define el esquema deductivo del modus ponens (MP) como todos los lazos inferenciales de la forma

$\{e_i, e_i\rightarrow e_j\}\vdash e_j$

donde $e_i$ y $e_j$ son expresiones de $\mathcal{P}_0$.


Definición - El Cálculo Proposicional: Se define el cálculo proposicional como el sistema deductivo conformado por el lenguaje $\mathcal{P}_0$ provisto del esquema axiomático de Łukasiewicz y el esquema deductivo dado por el modus ponens. Lo representaremos simbólicamente por $\mathcal{K}_{\mathcal{P}_0}$.

Este cálculo que acabamos de construir introduce formalmente la noción intuitiva de razonamiento lógico elemental; para probarlo, una vez que introduzcamos el teorema de deducción, mostraremos cómo en el cálculo proposicional se pueden probar rigurosamente todas las reglas básicas del razonamiento usual. Por ahora, nos conformemonos con el siguiente ejemplo.

Ejemplo: En $\mathcal{K}_{\mathcal{P}_0}$ vale el teorema:

$\vdash_{\mathcal{K}_{\mathcal{P}_0}} e_i \rightarrow e_i$

Demostración:

$\begin{array}{cll}
&Afirmacion & Argumento\\ \hline \\
\begin{array}{c}
(1)\\(2)\\(3)\\(4)\\(5)
\end{array} & \begin{array}{l}
e_i \rightarrow (e_i \rightarrow e_i)\\
e_i \rightarrow ( (e_i \rightarrow e_i) \rightarrow e_i)\\
(e_i \rightarrow ( (e_i \rightarrow e_i) \rightarrow e_i))\rightarrow (e_i \rightarrow (e_i \rightarrow e_i) ) \rightarrow (e_i \rightarrow e_i ) ) \\
(e_i \rightarrow(e_i \rightarrow e_i)) \rightarrow (e_i \rightarrow e_i) \\
e_i \rightarrow e_i
\end{array} & \begin{array}{l}
(a1)\\ (a1) \\ (a2) \\ MP(2,3) \\ MP(1,4)
\end{array}\\
& {\therefore\; \vdash_{\mathcal{K}_{\mathcal{P}_0}} (e_i \rightarrow e_i)} &
\end{array}$

En esta demostración, la indicación $(a1)$ muestra que la expresión correspondiente es de la forma del primer esquema axiomático de $\mathcal{K}_{\mathcal{P}_0}$. La indicación $MP(2,3)$ muestra que se ha realizado \textit{modus ponens} sobre las líneas $2$ y $3$.

Todos los teoremas de $\mathcal{K}_{\mathcal{P}_0}$ se pueden agregar como una línea dentro de cualquier razonamiento de $\mathcal{K}_{\mathcal{P}_0}$ porque son expresiones que se obtienen exclusivamente desde los axiomas.

Si agregamos $e_i$ como premisa en el ejemplo anterior podemos obtener la deducción de $e_i\vdash_{\mathcal{K}_{\mathcal{P}_0}} e_i$, lo que en el fondo nos dice que dentro de cualquier razonamiento es válido escribir líneas repetidas. En efecto

$\begin{array}{lll}
(1) & e_i &(premisa)\\
(2) & e_i \rightarrow e_i & (teorema\;que\;acabamos\;de\;demostrar)\\
(3) & e_i & MP(1,2) \\
& \therefore e_i \vdash_{\mathcal{K}_{\mathcal{P}_0}} e_i &
\end{array} $

El resultado $e_i \vdash_{\mathcal{K}_{\mathcal{P}_0}} e_i$ se conoce por el nombre de regla de repetición.
Compartir:

El Cálculo Deductivo [Parte 2: Metateoría - La construcción de un cálculo deductivo]



Una metateoría es una teoría que se enfoca en el estudio de otra teoría. En esta entrada haremos un poco sobre la metateoría del cálculo deductivo con el objetivo de establecer algunos conceptos elementales.

Nuestro primer contacto con la construcción de un cálculo deductivo lo tendremos con la noción de lenguaje formal. Un lenguaje formal consiste de un alfabeto provisto de una sintaxis, es decir, un conjunto de símbolos con reglas rigurosamente definidas que indican la manera correcta de escribirlos de modo tal que se obtengan expresiones válidas.

Ejemplo:
El lenguaje del cálculo proposicional está conformado por los conectores ($\rightarrow,\wedge,\vee, \neg$, etc...) y las variables proposicionales ($p,q,r$, etc...) con los cuales se pueden escribir escribir cadenas de símbolos como
  • $p$
  • $p\rightarrow \neg q$
  • $\rightarrow\rightarrow \wedge p q$
De estas, sólo la primera y la segunda son expresiones del cálculo proposicional, mientras que la tercera no es una expresión válida.

Los lenguajes formales, al contrario de los lenguajes naturales como el español, el chino o el inglés, no están diseñados para comunicar hechos de la realidad; cosas como "hoy hace frío" o "estoy triste", en realidad están diseñados para representar la estructura de las afirmaciones que pueden ser usadas como argumento dentro de una demostración.

Ejemplos:
  1. La expresión del cálculo proposicional

    $p \rightarrow q$

    es una representación para afirmaciones como "Si llueve hoy, entonces mañana hará frío", "si bebo ácido, entonces puedo morir", "si hace calor, entonces voy a la playa", etc. En general, una afirmación $p$ implica otra afirmación $q$.


  2. La expresión del cálculo de predicados de primer orden

    $\forall x \left(P_1 (x) \rightarrow P_2(x) \right)$

    es una representación para afirmaciones como "todos los sabios son prudentes" o "todos los ciudadanos pueden votar", etc. En general, todos los $x$ que cumplen la propiedad $P_1$ cumplen cumplen la propiedad $P_2$.


La segunda parte de la construcción de un cálculo deductivo viene con la noción de sistema deductivo formal.

Construcción de un lenguaje formal

Alfabetos y cadenas de símbolos

Cualquier conjunto distinto de vacío puede ser un alfabeto para un lenguaje formal.

Sea $\mathcal{A}$ un alfabeto. Una cadena de símbolos de ${\mathcal{A}}$ es cualquier elemento del conjunto

$\displaystyle Cad(\mathcal{A}) := \left\{ x\; \left|\; x\in \bigcup_{n\in \mathbb{N}} \mathcal{A}^n \right. \right\}$

donde $\mathcal{A}^n$ es el producto cartesiano del conjunto $\mathcal{A}$ por si mismo $n$ veces.

$\mathcal{A}^n = \underbrace{\mathcal{A} \times \mathcal{A} \times \cdots \times \mathcal{A}}_{n\;veces}$

Generalmente, en la consideración de las cadenas de símbolos, es usual remplazar la notación de n-úplas ordenadas por el simple arreglo ordenado de los símbolos, es decir, por ejemplo, si tenemos la cadena $a:=(a_1,a_2,\cdots,a_n)$, entonces se escribirá $a:= a_1a_2\cdots a_n$. Lo que hacemos en el fondo es optar por la economía de omitir los paréntesis y las comas.

Una sintaxis sobre un alfabeto $\mathcal{A}$ es cualquier subconjunto

$Sint(\mathcal{A}) \subseteq Cad(\mathcal{A})$

Los elementos de $Sint(\mathcal{A})$ se llaman expresiones válidas de $\mathcal{A}$.

Así, un lenguaje formal queda definido como un alfabeto provisto de una sintaxis. En el caso del lenguaje que corresponde al alfabeto $\mathcal{A}$ provisto de la sintaxis $Sint(\mathcal{A})$, se denotará por $L_{\mathcal{A}}:=(\mathcal{A} , Sint(\mathcal{A}))$.

En términos intuitivos, el lenguaje formal viene constituido por un conjunto del cual podemos sacar símbolos y un conjunto que nos indica cuales son las cadenas que son denominadas expresiones del lenguaje. En analogía a nuestro lenguaje cotidiano, las expresiones de un lenguaje formal, tal y como las hemos definido, son como las palabras correctamente escritas en castellano; de hecho, mediante el abecedario podemos escribir un sinnúmero de cosas, pero no todas esas cosas clasifican como expresiones en castellano «caballo» una cadena de símbolos que representa una palabra en castellano que hace referencia al animal "caballo", mientras que «alsjdlñasj» no lo es.

Sistemas Deductivos Formales

A continuación se definen los elementos que permiten conectar las expresiones de un lenguaje formal.

Un esquema axiomático sobre un lenguaje formal $L_{\mathcal{A}}$ es un subconjunto $Ax(L_{\mathcal{A}})\subseteq Sint(\mathcal{A})$.

El conjunto de todos los lazos inferenciales posibles de ${L_{\mathcal{A}}}$ es el conjunto $Li(L_{\mathcal{A}}) := \{ A\vdash B\; | \; A,B \subseteq Sint(\mathcal{A}) \}$. El objeto «$A\vdash B$» lo leemos en términos intuitivos como "la ley de inferencia que nos permite ir del conjunto de expresiones $A$ al conjunto de expresiones $B$".

Un esquema deductivo sobre un lenguaje formal ${L_{\mathcal{A}}}$ es un subconjunto $Ed(L_{\mathcal{A}})\subseteq Li(L_{\mathcal{A}})$.

Un sistema deductivo formal ${\mathcal{F}}$ es un lenguaje formal provisto de un esquema deductivo y un esquema axiomático definido sobre él y se denota por el trio

$\mathcal{F}:=(L_{\mathcal{A}},Ax(L_{\mathcal{A}}),Ed(L_{\mathcal{A}}))$.

Los elementos de $Ax(L_{\mathcal{A}})$ y de $Ed(L_{\mathcal{A}})$ se denominan, respectivamente, axiomas e inferencias válidas en $\mathcal{F}$.

*Nota:
Si $A$ y $B$ son conjuntos con un solo elemento, entonces se puede omitir la notación conjuntista. Por ejemplo, si $A=\{p\}$ y $B=\{q\}$, en vez de escribir «$A\vdash B$» o «$\{p\}\vdash\{q\}$» se preferirá escribir «$p\vdash q$». Bajo este mismo tipo de criterio, escrituras como «$A\vdash q$» y «$p\vdash B$» también son admitidas.

El acto de enunciar estas definiciones debe verse como si hubiéramos abierto una enorme caja repleta de engranajes, manivelas, cadenas, correas, cuerdas, poleas, pesos y soportes. Tenemos un lenguaje que nos entrega sus expresiones y podemos escoger los axiomas y reglas de inferencias para crear nuestro sistema deductivo; sin embargo, debemos destacar la diferencia entre regar las piezas en el suelo y armar algo que haga algo con ellas. Del mismo modo en que las máquinas que sirven para algo se pueden interpretar como expresiones del lenguaje cuyos elementos son engranajes y otras piezas mecánicas, el sistema deductivo representa la reunión de los criterios fundamentales para construir máquinas útiles a partir de las piezas sencillas que hemos definido.

Un sistema deductivo formal $\mathcal{F}$ se caracteriza por obtener expresiones del lenguaje a partir de su esquema deductivo y su esquema axiomático; sin embargo, dependiendo de la construcción del sistema deductivo, pueden existir expresiones que no se puedan deducir a partir del esquema axiomático a menos que agreguemos un determinado conjunto de expresiones $\Gamma$ adicionales a la deducción. De este modo, decimos que el sistema deductivo provisto de este conjunto de expresiones $\Gamma$ es una ampliación para el sistema deductivo original. A éste conjunto de expresiones $\Gamma$ las llamamos:

  • Postulados o principios cuando no sabemos si dicha expresión se puede o no inferir en el sistema deductivo.
  • Hipótesis cuando no interesa cómo se deduce la expresión en si, si no qué se puede inferir a partir de ella.
  • Axiomas complementarios cuando son postulados o principios que se han probado imposibles de inferir en el sistema deductivo y pretendemos formar uno nuevo y más general que el anterior haciendo uso de ellos.

El razonamiento y la notación de secuentes

Cuando razonamos en algún sistema deductivo formal $\mathcal{F}$, lo hacemos paso a paso, como se muestra en el siguiente esquema

$\begin{array}{r l l l}
& Afirmacion & Argumento & \\ \hline \\
\begin{array}{r}
(1) \\ \vdots \\ (n)
\end{array} & \begin{array}{l}
p_1 \\ \vdots \\ p_n
\end{array} & \left.\begin{array}{l}
{Premisa\;1} \\ \vdots \\ {Premisa\;n}
\end{array}\right\} & {Elementos\;de\;\Gamma} \\
\begin{array}{r}
(n+1) \\ \vdots \\ (n+j)
\end{array} & \begin{array}{l}
a_1 \\ \vdots \\ a_j
\end{array} & \left.\begin{array}{l}
{Axioma\;1} \\ \vdots \\ {Axioma\;j}
\end{array}\hspace{2.5px}\right\} & {Elementos\;de\; Ax(L) } \\
\begin{array}{r}
(n+j+1) \\ \vdots \\ (n+k)
\end{array} & \begin{array}{l}
e_i \\ \vdots \\ e_k
\end{array} & \left.\begin{array}{l}
R_l \\ \vdots \\ R_m
\end{array}\hspace{32px}\right\} & \begin{array}{l}
{Expresiones\;deducidas\;a\;partir\;de\;\Gamma},\\ {Ax(L)\;y\;las\;reglas\;de\;inferencia\;de\;\mathcal{F}.}\\ {Este\;conjunto\;de\;expresiones\;es\;la}\\ {Tesis,\;lo\;denotamos\;por\;T.}
\end{array}
\end{array}$

Por la izquierda tenemos la numeración de las lineas del razonamiento, por el centro las expresiones que entran en juego y por la derecha una descripción breve o el argumento que explica el medio por el cual se obtuvo la expresión correspondiente. En este esquema de razonamiento, $R_i$ representa la $i$-ésima regla de inferencia que, por el hecho de aparecer en $n+j+1$-ésima fila, significa que la expresión correspondiente se ha obtenido de aplicar dicha regla sobre alguna (o todas) las expresiones anteriores en la deducción. Este esquema completo es lo que finalmente resumimos escribiendo $\Gamma\vdash_{\mathcal{F}} T$

Con todo esto ahora podemos definir la equivalencia lógica:

Sean $p$ y $q$ dos expresiones de $L$. Si se tiene que $p\vdash_{\mathcal{F}}q$ y $q \vdash_{\mathcal{F}}p$, entonces se dice que $p$ y $q$ son expresiones equivalentes en el sistema deductivo formal ${\mathcal{F}}$ y lo representamos por $p \equiv_{\mathcal{F}} q$. Resumiendo esto en símbolos se tiene que:

$(p \equiv_{\mathcal{F}} q) := ( p \vdash_{\mathcal{F}} q ) \wedge ( q \vdash_{\mathcal{F}} p ).$


Si dos expresiones son equivalentes, entonces se puede sustituir en cualquier momento la una por la otra a lo largo de cualquier razonamiento.

Convenios sobre la notación de secuentes

  1. Si $\Gamma$ y $T$ son conjuntos de expresiones de $L$ tales que de $\Gamma$ se deduzca $T$ en base a los axiomas y reglas de inferencia de $\mathcal{F}$, entonces se escribe $\Gamma \vdash_{\mathcal{F}} T$. Se dice que $\Gamma$ es la hipótesis, premisa o antecedente y $T$ la tesis, resultado o consecuente. A esto se le llama notación de secuentes.
  2. Si $\Gamma \neq \varnothing$, entonces $\Gamma \vdash_{\mathcal{F}} T$ es una deducción.
  3. Si $\Gamma = \varnothing$, entonces $\Gamma \vdash_{\mathcal{F}} T$ es una demostración y $T$ es una colección de teoremas o axiomas de $\mathcal{F}$.
  4. Si $T$ es una colección de teoremas o axiomas de $\mathcal{F}$, entonces escribimos $\vdash_{\mathcal{F}} T$.
  5. En la práctica es común que los axiomas, las hipótesis y la tesis aparezcan mezclados en el razonamiento.
  6. En la práctica no es usual listar todos los axiomas, solo se nombran aquellos que se van a ocupar en el momento que se considere oportuno.
  7. Es común, en el uso de la notación de secuentes, que en vez de anotar la tesis como un conjunto $T$, sólo se escriba la expresión perteneciente a la tesis que es de interés obtener. Por ejemplo, {si en el razonamiento anterior sólo estuviéramos interesados en obtener $e_k$, entonces, en el momento de obtener dicha expresión simplemente dejamos de razonar y en la siguiente linea escribimos $\therefore \Gamma\vdash_{\mathcal{F}} e_k$.
  8. El símbolo «$\therefore$» se lee "por lo tanto".

Conclusión sobre la metateoría

Para concluir esta sección, demos un vistazo general a lo hecho hasta ahora. Tenemos que la construcción realizada hasta este punto abarca todo lo que es el cálculo deductivo, sin embargo, es claro que no nos entrega muchos detalles. Lo que acabamos de hacer es similar a mirar un cúmulo de galaxias completo, cuando lo que nos interesa es conocer un sistema solar que contenga planetas capaces de sostener vida —¿Se entiende la analogía?—. Para comenzar a encontrar detalles en el cálculo deductivo, y por lo tanto, comenzar a estudiarlo, es necesario proponer detalles sobre la constitución de sus componentes.

El objetivo de hacer esto es el de acotar nuestro estudio, que en principio engloba una infinidad de familias de lenguajes formales; aquellos que son especialmente útiles para nuestros propósitos son sólo un caso particular de aquellos. Los que nos interesan pretenden, en principio, conformar un análogo formal al razonamiento humano. Las alternativas más estudiadas que parecen cumplir con este objetivo son el cálculo proposicional y los cálculo de predicados de primer y segundo orden.

El cálculo proposicional es un sistema formal cuyo alfabeto se encuentra definido por proposiciones y conectores. Las proposiciones son análogas a las sentencias declarativas (afirmaciones) del lenguaje humano (Ej: Sócrates es mortal, es una proposición), los conectores enlazan una o mas proposiciones para formar otras proposiciones mas complejas. Por otro lado, el cálculo de predicados funciona como una extensión que agrega un mayor nivel de detalles sobre el cálculo proposicional definiendo la estructura interna sus proposiciones (Ej: La sentencia declarativa "Todos individuo es libre" es una proposición cuya estructura interna se encuentra conformada por un cuantificador (Todo), una variable (individuo) y un predicado (es libre) que nos dice algo sobre esa variable).
Compartir:

El Cálculo Deductivo [Parte 1: Introducción - ¿Qué es una demostración?]



Introducción

Es parte del conocimiento general, aún en ausencia de una formación académica, ciertos conceptos elementales de matemática, por lo que es buena idea partir desde ahí para introducir las ideas básicas de razonamiento y el cálculo deductivo.

Es difícil que tengas problemas sumando todos los números del $1$ al $10$. Si te lo pidieran, no tardarías en llegar a la respuesta correcta, la cual es $55$. Sin embargo ¿qué ocurriría si te pidieran sumar los primeros $100$ números naturales, o los primeros $1000$? Obviamente no intentarías hacer la suma a mano porque tardarías mucho y el esfuerzo no vale la pena. Un enfoque alternativo de abordar el problema se hace necesario. Lo primero que uno haría es comenzar a razonar sobre qué significa ``sumar todos los números del $1$ hasta el $n$, donde $n$ es un número natural cualquiera'' porque, de ese modo, podrías encontrar algún indicio que te permita resolver el problema de una forma más sencilla y abarcadora; forma que, en efecto, existe. La respuesta se encuentra en la conocida fórmula de la progresión aritmética:

Suma de los primeros $n$ números naturales $= \dfrac{n(n+1)}{2}.$

Con esto llegamos rápidamente a la conclusión de que:

  • La suma de los primeros $100$ naturales es $100\cdot 101/2 =5050$
  • La suma de los primeros 1000 naturales es $1000\cdot 1001/2 =500500$

Es probable que ya conozcas la validez de estos resultados, porque la fórmula de la progresión aritmética es algo que se sabe que funciona para todos los números naturales. Pero supongamos que no estamos convencidos, o mejor, que intentamos convencer a alguien que no no sabe nada de esto, a alguien que solo conoce las operaciones básicas de la aritmética. Para mostrar que esto es, en efecto, un resultado verdadero para cualquier número natural, lo que hacemos es proporcionar una demostración.

Decimos, por ejemplo:
Sea $S(n)$ la suma de los primeros $n$ números naturales. Como la suma es conmutativa, podemos escribir las siguientes expresiones
$$\begin{array}{lllllll}
S(n)= &1 &+2 &+3 &\cdots &+(n-1) &+n, \\
S(n)= &n &+(n-1) &+(n-2) &\cdots &+2 &+1,
\end{array}$$
ahora, sumándolas termino a término llegamos a que

$2S(n) = \underbrace{(n+1)+ \cdots + (n+1)}_{n\; veces} = n(n+1),$

lo cual es equivalente a decir

$S(n) = \dfrac{n(n+1)}{2},$

que es lo que queríamos demostrar.


Esto que acabamos de hacer es una demostración, y luego de verla ya no debería haber duda de que la fórmula de la progresión aritmética es una expresión verdadera. Sin embargo, aunque puede que no sea muy evidente a simple vista, el razonamiento tal y como lo tenemos hasta ahora sólo nos habla de un resultado para un $n$ en particular, que puede ser, por ejemplo, $15$, $50$ o un millón, pero algo que no hace es el asegurar que esto se cumple para todos los números naturales $n$. No basta con mostrar que funciona para $n=1,2,3,4$, etc... para decir que vale para todos los $n\in \mathbb{N}$, hace falta un paso adicional, esto que nos falta es lo que denominamos paso inductivo y lo explicaremos a continuación.

Supongamos que la formula se cumple para un $n=k$, lo que haremos a continuación será probar que a partir de eso se puede concluir que entonces se cumplirá para $n=k+1$, es decir, para su sucesor. Si para $n=k$ tenemos

$S(k)=1+2+3+\cdots + k = \dfrac{k(k+1)}{2}$

entonces, para $n=k+1$ tendremos

$\begin{align*}
S(k+1) &=1+2+3+\cdots + k + (k+1) \\ \\
&=S(k) + (k+1) \\ \\
&= \dfrac{k(k+1)}{2} + (k+1) \\ \\
&= \dfrac{k(k+1) + 2(k+1)}{2} \\ \\
S(k+1) &= \dfrac{(k+1)(k+2)}{2}
\end{align*}$

En otras palabras, hemos demostrado que si la fórmula se cumple para un $n=k$, entonces de igual forma se cumplirá cuando tomemos el siguiente $n=k+1$.


El paso inductivo que acabamos de realizar tiene agrega algo importante al razonamiento. Con esto ahora tenemos que, si éste es valido para $n=1$, entonces lo será para $n=2$, y si se cumple para $n=2$, entonces lo hará para $n=3$, y así sucesivamente; es decir, funcionará para todos los naturales, por lo que sólo nos falta agregar el caso inicial en que $n=1$ y la demostración quedará concluida.

Para $n=1$ tenemos que

$S(1) = \dfrac{1(1+1)}{2} = 1$

Esto es un resultado razonable porque la suma del único numero natural $1$ da justo $1$. De forma similar, si queremos, podemos ver cómo se cumple la fórmula para $n=2,3,4,\cdots$

$\begin{align*}
S(2)&=\dfrac{2(2+1)}{2} =3=1+2 \\
S(3)&=\dfrac{3(3+1)}{2} =6=1+2+3 \\
S(4)&=\dfrac{4(4+1)}{2} =10=1+2+3+4 \\
\vdots &
\end{align*}$

Cualquiera sera el caso, el paso inductivo nos asegura de que siempre se cumplirá para el paso siguiente.

Este razonamiento que acabo de mostrar es el que demuestra efectivamente que la fórmula $S(n)=n(n+1)/2$ vale para todos los números naturales; esto, escrito en fórmula, nos queda como:

$\left( \forall n \in \mathbb{N} \right) \left( S(n)=\dfrac{n(n+1)}{2} \right)$

Entonces, recapitulando, teníamos la afirmación de que la suma de los primeros $n$ números naturales esta dada por $S(n) =n(n+1)/2$ y luego, mediante una sucesión ordenada y finita de argumentos, probamos que eso es verdad para cualquier número natural $n$, es decir, que vale la fórmula $\left( \forall n \in \mathbb{N} \right) \left( S(n)=n(n+1)/2 \right)$. Esta sucesión de argumentos es lo que denominamos demostración, y esto es lo que nos permitió usar lo que sabíamos sobre la suma de números naturales para adquirir un nuevo conocimiento, que sería la formula que acabamos de probar.

¿Qué es una demostración y cuál es su relevancia?

Una demostración, o razonamiento, es un conjunto de argumentos que permiten obtener conclusiones a partir de un conjunto de premisas. Ambos, premisas y conclusiones, son afirmaciones, y si la demostración que los relaciona está bien construida, entonces tenemos una relación de implicancia entre la premisas y la conclusiones; es decir, si se cumplen las premisas entonces se cumplen las conclusiones. En el caso de la demostración que se mostró anteriormente tenemos que de las operaciones de la aritmética elemental se puede deducir que la suma de los primeros $n$ números naturales está dada por $S(n) = n(n+1)/2$. La relevancia de una demostración es que nos permite partir de un conjunto de premisas (hechos conocidos) y, a partir de ellas, obtener conclusiones que no necesariamente conocemos de antemano o, de forma similar, corroborar si un resultado conocido es, en efecto, un resultado verdadero.


Regularidad y consistencia

Las demostraciones, para que valga la pena consideradas como tales, deben ser regulares y consistentes. Con regulares nos referimos a que los mismos razonamientos con las mismas premisas proporcionan siempre las mismas conclusiones. Por consistente nos referimos a que un esquema de razonamiento provisto de premisas que no se contradicen entre si, entonces nunca proporcionarán conclusiones que se contradicen entre si ni a las premisas.

La teoría de la demostración

Como vimos anteriormente, una demostración está conformada por argumentos que permiten obtener conclusiones a partir de premisas. La teoría de la demostración, por lo tanto, es la teoría que estudia los objetos con que los argumentos son construidos, y estos a su vez son construidos con las herramientas que proporcionan los cálculos deductivos o lógicas. Algunos ejemplos de cálculos deductivos son el calculo proposicional y los cálculos de predicados de primer y segundo orden. Se espera que en esta serie de entradas se estudien cada uno de esos cálculos deductivos.

Compartir:

Aprendiendo C++ [Parte 2: Variables Enteras y Ciclos do-while - La Sucesión de Fribonacci ]

Una de las razones por las que es bueno aprender a programar es porque con eso ganas el control sobre un esclavo que hará exactamente lo que tu le digas, tantas veces como se lo pidas. El computador puede realizar una tarea millones de veces sin cansarse, y cada repetición será igual a la primera. Sin embargo, el mundo no es tan perfecto, este esclavo carece de la capacidad de pensar y hará literalmente lo que tu le digas (lo cual no es necesariamente lo que tu quieres decir), similar a la leyenda del Golem de Praga.

A continuación ahondaremos un poco más en el lenguaje de C++ para realizar ciertos trabajo matemático muchas veces, por lo que introduciremos los conceptos de variable entera y los ciclos do-while de C++.

La Sucesión de Fribonacci

La sucesión de Fribonacci es la sucesión dada por los números 1, 1, 2, 3, 5, 8, 13..., donde cada número es la suma de los dos anteriores. Lo que queremos hacer es escribir un programa que nos proporcione los n primeros números de esta serie, donde n es cualquier numero natural positivo que nosotros le entreguemos al programa.

Lo que debemos hacer, antes de tirarnos de cabeza a escribir el código, es razonar un poco sobre cómo se construye la sucesión de Fribonacci. Notamos que tenemos dos valores iniciales, los dos primeros 1's, luego tenemos que el tercero es 1+1=2 y los siguientes son 1+2=3, 2+3=5, etc... Si colocamos esto en una recta y les asignamos variables, podemos armar el siguiente esquema



Con este esquema ya tenemos una idea de lo que queremos que el programa haga, ahora toca escribir el código. Creamos un programa llamado fribonacci.c

$ pico fribonacci.c

y dentro de él comenzamos escribiendo la estructura básica de todo programa escrito en C++

#include
main(){
}

Tenemos un proceso que queremos que se repita n veces, que es el de sumar tal y como se muestra en el esquema anterior. Para indicarle al programa que queremos repetir algo n veces usamos un ciclo do-while. Esto se hace agregando el siguiente código dentro del main

#include<iostream>
main(){
  int i=0,n;
  std:: cin>>n;
  do{i=i+1;
  }while(i<=n);
}

Aquí aparecieron cosas nuevas que explicaré ahora mismo:

La linea int i=0,n; le dice al programa que las letras n e i serán variables que asumen valores enteros. Nótese que es posible dar un valor a las variables justo cuando son declaradas, en este caso, se hizo i=0 y n se declaró como variable entera sin asignarle ningún valor. Cuando declaramos variables, lo que en el fondo hacemos es reservar algo de memoria para guardar información en ella.

La linea std::cin>>n indica al programa que solicite al usuario que le asigne un valor a n. Como éste es declarado como un entero en el programa, si el usuario proporciona algo que no sea un número entero hará que el programa no entregue resultados coherentes.

El ciclo do-while viene dado por do{i=i+1; }while(i<=n);. Lo que hace esto es tomar el valor inicial de i (i=0 en nuestro caso) e incrementarlo en 1, si nuevo valor de i es menor que el n entregado por el usuario, entonces se repite la operación. Esto lo hará siempre que se cumpla la relación i≤n,, cuando esto ya no ocurra, el ciclo do-while finalizará. Notemos que cualquier procedimiento que coloquemos dentro del ciclo do-while se repetirá n veces.

Ahora, dentro del ciclo do-while introducimos las instrucciones para generar la sucesión de Fribonacci sugerido por el esquema de más arriba

#include<iostream>
main(){
int i=0,n, a=1, b=0, c;
std:: cin>>n;
do{i=i+1;
   c=a+b;
   a=b;
   b=c;
   std::cout << c << std::endl;
   }while(i<=n);
}

Para concluir la redacción del programa, podemos agregar algunos "adornos" al código para hacerlo más fácil de entender durante la ejecución:

#include<iostream>
main(){
int i=0,n, a=1, b=0, c;
std::cout << "ingresa el número de iteraciones" << std::endl;
std:: cin>>n;

std::cout << "los primeros "<< n <<" términos de la sucesión de fribonaci son" << std::endl;
do{i=i+1;    
   c=a+b;
   a=b;
   b=c;
   std::cout << c << std::endl;
   }while(i<=n);
}

Ahora guardamos (Ctrl+O), salimos del editor de texto (Ctrl+X), compilamos y ejecutamos

$ c++ fribonacci.c -o fribonacci
$ ./fribonacci

El resultado debería ser el siguiente:
 

En los siguientes enlaces puedes encontrar el código fuente con comentarios y el código fuente limpio.

Tipos de variables enteras y sus propiedades

Si comenzamos a hacer pruebas el programa que hemos escrito no tardaremos en toparnos con algo extraño. Si le proporcionamos, por ejemplo, un n=50, entonces veremos algunos resultados algo extraños:



Lo que ha pasado aquí es que el tamaño de los números de la serie de Fribonacci se han hecho tan grandes que han superado el espacio de memoria disponible para una variable de tipo entero (int), es por eso que, a partir de cierto punto, los resultados entregador por el programa comienzan a perder todo sentido; vale la pena, por lo tanto, detenernos un momento a revisar los tipos de variables enteras y sus propiedades.

En C++ podemos encontrar los siguientes tipos de variables de tipo entero, donde cada una destina una cantidad de memoria determinada, estas son:

unsigned short int
Normalmente usa 2 bytes de memoria, permite valores entre 0 y 65.535

short int
Normalmente usa 2 bytes de memoria, permite valores entre -32.768 y 32.767

unsigned long int
Normalmente usa 4 bytes de memoria, permite valores entre 0 y 4.294.967.295

long int
Normalmente usa 4 bytes de memoria, permite valores entre -2.147.483.648 y 2.147.483.647

int (16 bits)
Normalmente usa 2 bytes de memoria, permite valores entre -32.768 y 32.767

int (32 bits)
Normalmente usa 4 bytes de memoria, permite valores entre -2.147.483.648 y 2.147.483.647

unsigned int (16 bits)
Normalmente usa 2 bytes de memoria, permite valores entre 0 y 65.535

unsigned int (32 bits)
Normalmente usa 2 bytes de memoria, permite valores entre 0 y 4.294.967.295

El tamaño de las variables en memoria puede variara de un PC a otro.

Formas adecuadas de definir las variables permite un mejor uso de la memoria, por ejemplo, como el programa fribonacci sólo utiliza enteros positivos, es buena idea declarar las variables como unsigned int, de este modo, la memoria reservada para los enteros negativos que implementa int puede ser aprovechada para obtener algunos cuantos términos adicionales de la sucesión de Fribonacci. Sin embargo, y como ha ocurrido aquí, el hecho de haber usado int nos ha permitido detectar fácilmente que un error estaba ocurriendo, ya que para el programador es más fácil notar cuando aparecen números negativos en la serie que cuando un grupo de enteros positivos dejan de pertenecer a la serie (sobre todo cuando estos son muy grandes). Aquí cada quien es libre de decidir qué priorizar. Es importante ser consciente de los límites de cada aspecto del programa para evitar esta clase de problemas.

Dejaremos esto hasta aquí por ahora.
Compartir:

Copyright © GireBz.cl
Template diseñado por SimpleWpThemes & NewBloggerThemes.com