UTNianos

Lo que escribí demuestra que para un Álgebra concreta, sea

\[B_n=\left\{\left(a_1,a_2,a_3,\ldots,a_n\right)\right\},\]

donde a_k es un entero 0 o 1 para cada k (1 ≤ k ≤ n), y sus operaciones + y ·

A partir de acá hay que demostrar que cualquier Álgebra de Boole es isomorfa a un Álgebra de Boole de partes de un conjunto, y de ahí es inmediato que el cardinal es 2^n.

---

Para el primer caso demostraremos que cualquier Álgebra de Boole finita es isomorfa a un Álgebra de Boole B_n, para algún n > 0.

Prueba: Sea B un Álgebra de Boole y sean \[e_1,e_2,e_3,\ldots,e_n\] sus mínimos elementos de B. Tenemos que para todo x ∈ B, x tiene una única expresión lineal \[x=c_1\cdot e_1+c_2\cdot e_2+c_3\cdot e_3+\ldots c_n\cdot e_n,\] donde c_k = 0 o c_k = 1 para cada k (1 ≤ k ≤ n) (Se puede demostrar pero no lo haremos).
Luego definamos una correspondencia \[\phi:B\to B_n\] como sigue: \[\phi(x)=\left(a_1,a_2,a_3,\ldots,a_n\right),\] donde a_k = 0 si c_k = 0 y a_k = 1 si c_k = 1, para cada k (1 ≤ k ≤ n).
Si aceptamos los elementos 1 y 0 dentro de B como enteros de B_n, sencillamente podemos definir \[\phi(x)=\left(c_1,c_2,c_3,\ldots,c_n\right).\]
Es obvio que la correspondencia φ es 1-1.
Además, porque para cada k (1 ≤ k ≤ n)
\[e_k+0=e_k,\quad e_k+e_k=e_k,\quad e_k\cdot 0=e_k,\quad e_k\cdot e_k=e_k,\]
podemos verificar que para todo x, y ∈ B
\[\phi(x+y)=\phi(x)+\phi(y)\quad\textrm{y}\quad\phi(x\cdot y)=\phi(x)\cdot \phi(y).\]
Esto es porque los elementos de ambos lados de las ecuaciones tiene las mismas expresiones de coordenadas.
También es fácil verificar que
\[\phi\left(x'\right)={[\phi(x)]}'.\]
Omitimos la prueba.

Por lo tanto B es isomorfo a B_n para algún entero entero n > 0.

---

Para el segundo caso, es decir el cardinal de cualquier Álgebra de Boole finita es 2^n para algún entero positivo n, es la misma que la que se encuentra en el PDF.

La gramática es de tipo 3 pues los términos de la izquierda (A y B) son los únicos símbolos no terminales, mientras que los términos de la derecha cumplen la concatenación de 2 símbolos con uno de ellos terminal (x A, y B y x B) o un único símbolo terminal (el término x).

Es falso que genere un lenguaje finito pues al menos una de sus producciones se llama a sí misma, de forma recursiva, y por tanto genera un lenguaje infinito, aunque el hecho de que esa recursión infinita pueda finalizar y producir una palabra terminal en cualquiera de el/los punto/s (o incluso infinitos), y que infinitamente muchos de ellos son diferentes por pares.

Queremos probar que \[a_n = 2^n-1\] es solución de la RRLH \[a_n = 3a_{n-1} - 2a_{n-2}\] con \[a_1 = 1\] y \[a_2 = 3\] como condiciones iniciales.

Demostración:
n = 1
\[a_1 = 2^1 -1 = 2-1=1\] (coincide con la condición inicial)

n = 2
\[a_2 = 2^2 -1 = 4-1=3\] (coincide con la condición inicial)

n => n+1
\[\forall n \epsilon N, a_n = 2^n-1 soluci\acute{o}n \Rightarrow a_n = 2^{n+1} - 1 soluci\acute{o}n\]
\[a_n = 3a_{n-1} - 2a_{n-2}\]
\[ = 3(2^n-1) - 2(2^{n-1}-1)\]
\[= 3.2^n-3-2.2^{n-1}+2 \]
\[=3.2^n-3-2^n+2 \]
\[=(3-1).2^n - 3 +2\]
\[=2.2^n-1 \]
\[ =2^{n+1}-1\]
Que es lo queríamos demostrar.