[manooooh]

Hola!

Supongamos que \( (D,+,\cdot,',0,1) \) es un Álgebra de Boole. Entonces \( a'b+(abc)'+c(b'+a)=b'+c' \).


Creo que es falso.

Como contraejemplo, tomemos \( D=D_{15} \), o sea todos los divisores de \( 15 \). Por una conocida propiedad, \( (D,+,\cdot,',0,1) \) es Álgebra de Boole puesto que \( 15 \) puede descomponerse como producto de primos únicos. El diagrama de Hasse es:

Sea por ejemplo \( a=1 \), \( b=3 \) y \( c=15 \). Entonces \( a'=15 \), \( b'=5 \) y \( c'=1 \), entonces \begin{align*}a'b+(abc)'+c(b'+a)&=15\cdot3+(1\cdot3\cdot15)'+15\cdot(5+1)\\&=3+15+5\\&=15,\end{align*} pero \begin{align*}b'+c'&=5+1\\&=5,\end{align*} por tanto la proposición es falsa.


¿Otra manera de probalo podría ser a través de la comparación de sus tablas de verdad asociadas? Donde \( \cdot \) representa el \( \mathrm{AND} \) lógico y \( + \) es el \( \mathrm{OR} \) lógico:

\(
\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline a&b&c&a'&b'&c'&a'b&abc&(abc)'&b'+a&c(b'+a)&a'b+(abc)'+c(b'+a)\\\hline
\mathrm V&\mathrm V&\mathrm V&\mathrm F&\mathrm F&\mathrm F&\mathrm F&\mathrm V&\mathrm F&\mathrm V&\mathrm V&\mathrm V\\\hline
\mathrm V&\mathrm V&\mathrm F&\mathrm F&\mathrm F&\mathrm V&\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm F&\mathrm V\\\hline
\mathrm V&\mathrm F&\mathrm V&\mathrm F&\mathrm V&\mathrm F&\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm V&\mathrm V\\\hline
\mathrm V&\mathrm F&\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm F&\mathrm V\\\hline
\mathrm F&\mathrm V&\mathrm V&\mathrm V&\mathrm F&\mathrm F&\mathrm V&\mathrm F&\mathrm V&\mathrm F&\mathrm F&\mathrm V\\\hline
\mathrm F&\mathrm V&\mathrm F&\mathrm V&\mathrm F&\mathrm V&\mathrm V&\mathrm F&\mathrm V&\mathrm F&\mathrm F&\mathrm V \\\hline
\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm V&\mathrm F&\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm V&\mathrm V \\\hline
\mathrm F&\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm V&\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm F&\mathrm V \\\hline
\end{array}
 \)

y

\(
\begin{array}{|c|c|c|c|c|}
\hline b&c&b'&c'&b'+c' \\\hline
\mathrm V&\mathrm V&\mathrm F&\mathrm F&\mathrm F \\\hline
\mathrm V&\mathrm F&\mathrm F&\mathrm V&\mathrm V \\\hline
\mathrm F&\mathrm V&\mathrm V&\mathrm F&\mathrm V \\\hline
\mathrm F&\mathrm F&\mathrm V&\mathrm V&\mathrm V \\\hline
\end{array}
 \)

Como ambas tablas de verdad arrojan distintos resultados, concluimos que la proposición dada es falsa.

¿Ambas formas son correctas?

Gracias!
Saludos

EDIT. Título cambiado de "Probar o no: En un Álgebra de Boole, se verifica que \(a'b+(abc)'+c(b'+a)=b'\)" a "Probar o no: En un Álgebra de Boole se verifica que \(a'b+(abc)'+c(b'+a)=b'+c'\)" ya que faltaba una parte. Disculpas.

[Luis Fuentes]

Hola

 Bien el planteamiento de ambas formas; no he comprobado al detalle las cuentas.

Saludos.

[manooooh]

Hola

Bien el planteamiento de ambas formas; no he comprobado al detalle las cuentas.

¡Gracias!

Con respecto a la última forma, ¿qué hubiera pasado si la tabla de las \( 8 \) filas habrían, por decir algo, \( 3 \) verdaderos y \( 5 \) falsos (o lo que sea), mientras que la segunda tabla tiene \( 3 \) y \( 1 \) falso?

Digamos, ¿aquí este método ya dejaría de funcionar porque ahora los valores de verdad resultan "no comparables"?

¿No es que para que este segundo método sea realmente eficaz hay que agregar un tercer elemento a la 2da tabla, a fin de comparar \( 8 \) filas con \( 8 \) filas? No hablo de modificar \( a'b+(abc)'+c(b'+a)=b'+c' \) sino de utilizar una forma normal (disyuntiva o conjuntiva) en el segundo término del igual a fin de "hacer aparecer" la variable faltante.

Saludos

[Luis Fuentes]

Hola

Con respecto a la última forma, ¿qué hubiera pasado si la tabla de las \( 8 \) filas habrían, por decir algo, \( 3 \) verdaderos y \( 5 \) falsos (o lo que sea), mientras que la segunda tabla tiene \( 3 \) y \( 1 \) falso?

Digamos, ¿aquí este método ya dejaría de funcionar porque ahora los valores de verdad resultan "no comparables"?

¿No es que para que este segundo método sea realmente eficaz hay que agregar un tercer elemento a la 2da tabla, a fin de comparar \( 8 \) filas con \( 8 \) filas? No hablo de modificar \( a'b+(abc)'+c(b'+a)=b'+c' \) sino de utilizar una forma normal (disyuntiva o conjuntiva) en el segundo término del igual a fin de "hacer aparecer" la variable faltante.

Di por sobrentendido que cuando comparas las dos tablas, en la segunda cada resultado lo estás considerando dos veces por cada valor de \( a \), una para \( a=V \) y otra para \( a=F \).

Saludos.

[Carlos Ivorra]

No sé si está sobreentendido en toda la discusión que las tablas de verdad sirven porque salen tablas distintas en ambos miembros. Si las tablas resultantes hubieran sido iguales, eso no probaría nada. Más concretamente, probaría que la identidad es cierta en el álgebra de Boole trivial de dos elementos, pero no probaría que la igualdad es cierta en cualquier álgebra de Boole, que es lo que pide el problema.

[manooooh]

Buenos días Carlos, primera vez en mucho tiempo que debatimos fuera del ámbito privado

No sé si está sobreentendido en toda la discusión que las tablas de verdad sirven porque salen tablas distintas en ambos miembros. Si las tablas resultantes hubieran sido iguales, eso no probaría nada. Más concretamente, probaría que la identidad es cierta en el álgebra de Boole trivial de dos elementos, pero no probaría que la igualdad es cierta en cualquier álgebra de Boole, que es lo que pide el problema.

Creo que te entiendo. Es totalmente cierto, por eso la pregunta de los "elementos comparables".

En este caso justo dio la casualidad de que la proposición es falsa (pues son tablas distintas), y si hubiera sido verdadero temía que este método NO iba ser válido.

Ahora bien, me gustaría entender por qué no sería válido, ya que de tu comentario me gustaría saber si lo entendí: si por ejemplo la primer fila de la primer tabla hubiera arrojado falso, ¿esto NO prueba la veracidad del problema puesto que en la segunda tabla "está implícita la variable \( a \)"?  Me refiero a que no tenemos forma de saber a qué fila de la segunda tabla corresponde a la primera de la primera tabla (¿ocurre cuando \( a \) es falsa o verdadera?), ¿verdad?

Pero en el caso de que las dos primeras filas de la primer tabla hubieran arrojado falso (sabiendo que la primer fila de la 2da tabla también es falsa), ¿ahora sí se puede concluir que la proposición es verdadera, puesto que no depende de \( a \)?

Desde ya que no existe un caso general sino muchos particulares, pero me gustaría ahondar en estas cuestiones.


Otra, relacionada, que no me deja dormir desde hace tiempo. ¿Se dice que dos proposiciones son iguales si sus tablas de verdad asociadas arrojan los mismos valores de verdad (¿en el mismo orden?) ¿Debe ir obligatoriamente lo que está marcado en negrita?

Me refiero a que si tenemos dos tablas ordenadas (o sea las variables puestas en un orden personalizado, como alfabético) entonces es condición de que el valor de verdad de la fila \( n \) de la tabla uno coincida con el \( n \) de la segunda tabla.

Ya sé que el orden no importa, pero para decidir si algo es equivalente a otra cosa me parece que el orden sí debería importar. Bah, no sé.

Saludos y gracias

P.D. Estoy asumiendo que las dos primeras filas de la primer tabla tienen por un lado a \( a \) como verdadero y en la segunda es \( a \) falsa.

[Carlos Ivorra]

En este caso justo dio la casualidad de que la proposición es falsa (pues son tablas distintas), y si hubiera sido verdadero temía que este método NO iba ser válido.

Ahora bien, me gustaría entender por qué no sería válido, ya que de tu comentario me gustaría saber si lo entendí: si por ejemplo la primer fila de la primer tabla hubiera arrojado falso, ¿esto NO prueba la veracidad del problema puesto que en la segunda tabla "está implícita la variable \( a \)"?  Me refiero a que no tenemos forma de saber a qué fila de la segunda tabla corresponde a la primera de la primera tabla (¿ocurre cuando \( a \) es falsa o verdadera?), ¿verdad?

Pero en el caso de que las dos primeras filas de la primer tabla hubieran arrojado falso (sabiendo que la primer fila de la 2da tabla también es falsa), ¿ahora sí se puede concluir que la proposición es verdadera, puesto que no depende de \( a \)?

No. Lo que te digo no tiene nada que ver con esto. El hecho de que en el miembro derecho no esté la \( a \) es anecdótico para lo que te estoy diciendo. Lo que te digo es que si tienes una igualdad como la del enunciado (y supón, por simplificar, que en ambos miembros aparecen las mismas variables) y calculas las tablas de verdad de ambos miembros y son iguales, de ahí no puedes deducir que la igualdad sea cierta en cualquier álgebra de Boole. Sólo has probado que es cierta en el álgebra de Boole trivial formada por dos elementos (V y F).

Otra, relacionada, que no me deja dormir desde hace tiempo. ¿Se dice que dos proposiciones son iguales si sus tablas de verdad asociadas arrojan los mismos valores de verdad (¿en el mismo orden?) ¿Debe ir obligatoriamente lo que está marcado en negrita?

Me refiero a que si tenemos dos tablas ordenadas (o sea las variables puestas en un orden personalizado, como alfabético) entonces es condición de que el valor de verdad de la fila \( n \) de la tabla uno coincida con el \( n \) de la segunda tabla.

No entiendo. No hay ningún orden que tener en cuenta. Se trata de que si das unos valores de verdad a las variables (VVV), (VVF), etc., ambas proposiciones toman siempre el mismo valor de verdad. Da igual en qué orden recorras la sucesión de todas las ternas, o cuádruplas o lo que sea de valores posibles.

[Carlos Ivorra]

Rectifico: me acabo de dar cuenta de que lo que he dicho no es cierto.

En realidad, si al dar valores de verdad a las variables se obtiene lo mismo en los dos miembros, entonces la igualdad es cierta en cualquier álgebra de Boole, aunque no es inmediato que sea asi. Incluyo la prueba, pero requiere saber algunas cosas sobre álgebras de Boole.

Spoiler

Supongamos que tenemos dos expresiones Booleanas \( \alpha \) y \( \beta \) (del estilo de las que aparecen en el enunciado, pero arbitrarias) y que no son iguales en una cierta álgebra de Boole \( B \). La igualdad \( \alpha=\beta \) equivale a que \( \alpha\beta'+\alpha'\beta=0 \), luego, si no son iguales, esta expresión no da \( 0 \), luego existe un ideal primo \( I \) en \( B \) que no contiene a este elemento, luego \( [\alpha][\beta]'+[\alpha]'[\beta]\neq 0 \) en el cociente \( B/I \) (que es el álgebra trivial de dos elementos). Pero esto significa que \( [\alpha]\neq [\beta] \) en dicho cociente, lo que a su vez significa que si damos a cada variable \( x \) de \( \alpha \) y \( \beta \) el valor V o F según si \( [{}x]=1 \) o \( [{}x]=0 \), obtenemos un valor de verdad distinto en cada miembro.

Recíprocamente, si al evaluar las variables de cualquier modo obtenemos siempre el mismo valor de verdad, las expresiones tienen que ser iguales en cualquier álgebra de Boole.

También se puede razonar usando el teorema de completitud de la lógica proposicional.

[cerrar]

[manooooh]

Hola

Rectifico: me acabo de dar cuenta de que lo que he dicho no es cierto.

No hay problema. De todas formas:

(...) Sólo has probado que es cierta en el álgebra de Boole trivial formada por dos elementos (V y F).

¿A qué te referís con "los elementos V y F"? ¿No es que toda proposición es verdadera o excluyentemente falsa? ¿Qué ejemplos hay en los que en una tabla de verdad aparezcan otros elementos?

En realidad, si al dar valores de verdad a las variables se obtiene lo mismo en los dos miembros, entonces la igualdad es cierta en cualquier álgebra de Boole, aunque no es inmediato que sea asi. Incluyo la prueba, pero requiere saber algunas cosas sobre álgebras de Boole.

Spoiler

Supongamos que tenemos dos expresiones Booleanas \( \alpha \) y \( \beta \) (del estilo de las que aparecen en el enunciado, pero arbitrarias) y que no son iguales en una cierta álgebra de Boole \( B \). La igualdad \( \alpha=\beta \) equivale a que \( \alpha\beta'+\alpha'\beta=0 \), luego, si no son iguales, esta expresión no da \( 0 \), luego existe un ideal primo \( I \) en \( B \) que no contiene a este elemento, luego \( [\alpha][\beta]'+[\alpha]'[\beta]\neq 0 \) en el cociente \( B/I \) (que es el álgebra trivial de dos elementos). Pero esto significa que \( [\alpha]\neq [\beta] \) en dicho cociente, lo que a su vez significa que si damos a cada variable \( x \) de \( \alpha \) y \( \beta \) el valor V o F según si \( [{}x]=1 \) o \( [{}x]=0 \), obtenemos un valor de verdad distinto en cada miembro.

Recíprocamente, si al evaluar las variables de cualquier modo obtenemos siempre el mismo valor de verdad, las expresiones tienen que ser iguales en cualquier álgebra de Boole.

También se puede razonar usando el teorema de completitud de la lógica proposicional.

[cerrar]

Pero entonces también deberías demostrar que dos proposiciones \( p \) y \( q \) dentro de la lógica de primer orden son equivalentes si sus tablas de verdad coinciden, ¿verdad?

Lo mismo para cualquier estructura algebraica finita; sin embargo nunca he visto que particularmente lo debamos demostrar para el Álgebra de Boole. ¿Por qué esto es así y no para, por ejemplo, dos proposiciones \( p \) y \( q \)? ¿Tiene algo de especial el Álgebra de Boole?

Yo creo que en un curso de Matemática Discreta esto ya se da por entendido; es obvio que dos Álgebras de Boole finitas son equivalentes si sus fórmulas arrojan los mismos valores de verdad.

Saludos

[Carlos Ivorra]

(...) Sólo has probado que es cierta en el álgebra de Boole trivial formada por dos elementos (V y F).

¿A qué te referís con "los elementos V y F"? ¿No es que toda proposición es verdadera o excluyentemente falsa? ¿Qué ejemplos hay en los que en una tabla de verdad aparezcan otros elementos?

¿Qué relación hay para ti entre lo que preguntan en el enunciado y las tablas de verdad? Un álgebra de Boole es un conjunto en el que hay definidas dos operaciones (que tú llamas \( + \) y \( \cdot \)) que cumplen ciertas propiedades. Lo que te están preguntando es si al operar tres objetos arbitrarios \( a, b, c \) de dos formas distintas te va a salir el mismo objeto del álgebra o si te pueden salir dos cosas distintas.

¿Qué relación ves tú entre eso y una tabla de verdad? En principio, cuando sustituyes las variables por los valores V y F estás evaluando ambas expresiones en un álgebra de Boole muy concreta, la que tiene dos elementos, que puedes llamar V y F o 1 y 0. Por lo tanto, si al evaluarla en esa álgebra salen cosas distintas, es que ambas expresiones no dan el mismo resultado en todas las álgebras. Lo que no es trivial es el recíproco, que si dan el mismo resultado en el álgebra de Boole trivial (si las tablas de verdad son iguales) entonces ambas expresiones tienen que dar el mismo resultado en cualquier álgebra de Boole.

Pero entonces también deberías demostrar que dos proposiciones \( p \) y \( q \) dentro de la lógica de primer orden son equivalentes si sus tablas de verdad coinciden, ¿verdad?

Eso es cierto, pero la demostración que he puesto no depende de eso.

Lo mismo para cualquier estructura algebraica finita; sin embargo nunca he visto que particularmente lo debamos demostrar para el Álgebra de Boole. ¿Por qué esto es así y no para, por ejemplo, dos proposiciones \( p \) y \( q \)? ¿Tiene algo de especial el Álgebra de Boole?

¿Por qué es así el qué? No te sigo.

Yo creo que en un curso de Matemática Discreta esto ya se da por entendido; es obvio que dos Álgebras de Boole finitas son equivalentes si sus fórmulas arrojan los mismos valores de verdad.

¿A qué llamas álgebras de Boole equivalentes? ¿A qué llamas fórmulas de un álgebra de Boole?