Autor Tema: Probar o refutar proposición sobre Álgebra de Boole

0 Usuarios y 1 Visitante están viendo este tema.

28 Noviembre, 2017, 02:24 am
Leído 1365 veces

manooooh

  • Matemático
  • Mensajes: 2,989
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola a todos! El profesor resolvió un ejercicio y no sé qué hizo:

En un Álgebra de Boole \( (B, \wedge, \vee) \) con primer elemento \( 0_B \) y último elemento \( 1_B \) se verifica \( \overline{a \wedge b} = \overline{a} \vee \overline{b} \).



Resolución:

VERDADERO.

\( \overline{a \wedge b} = \overline{a} \vee \overline{b} \Leftrightarrow{} \begin{cases}(1) & \color{red}(a \wedge b) \vee (\overline{a} \vee \overline{b}) & = & 1_B \\ (2) & \color{red}(a \wedge b) \wedge (\overline{a} \vee \overline{b}) & = & 0_B \end{cases} \)

Dem.:
\( (1) \; (a \wedge b) \vee (\overline{a} \vee \overline{b}) = (a \vee b \vee \overline{a}) \wedge (a \vee b \vee \overline{b}) = (a \vee \overline{a} \vee b) \wedge 1_B = 1_B \wedge 1_B = 1_B \).

\( (2) \;  (a \wedge b) \wedge (\overline{a} \vee \overline{b}) = (a \wedge \overline{a} \wedge \overline{b}) \vee (b \wedge \overline{a} \wedge \overline{b}) = \ldots = 0_B \vee 0_B = 0_B \).



Entiendo las operaciones que hizo para obtener el primer y último elemento pero no entiendo el por qué de lo rojo. Yo tengo la definición de

Sea \( (B, ≼) \) Álgebra de Boole: \( \forall{}x \in{} B, \exists{}\overline{x} \in{} B: \begin{cases}x \wedge \overline{x} & = & 0_B \\ x \vee \overline{x} & = & 1_B \end{cases} \). ¿No es esto diferente a lo que puse en rojo? Entiendo que tomó \( x = (\overline{a} \vee \overline{b}) \), pero \( \overline{x} \) debería ser \( \overline{x} = \overline{(\overline{a} \vee \overline{b})} \). O sea ¿\( \overline{x} = \overline{(\overline{a} \vee \overline{b})} = (a \wedge b) \) por De Morgan?

Gracias!!

28 Noviembre, 2017, 05:34 am
Respuesta #1

serpa

  • Experto
  • Mensajes: 541
  • País: co
  • Karma: +0/-0
Hola a todos! El profesor resolvió un ejercicio y no sé qué hizo:

En un Álgebra de Boole \( (B, \wedge, \vee) \) con primer elemento \( 0_B \) y último elemento \( 1_B \) se verifica \( \overline{a \wedge b} = \overline{a} \vee \overline{b} \).



Resolución:

VERDADERO.

\( \overline{a \wedge b} = \overline{a} \vee \overline{b} \Leftrightarrow{} \begin{cases}(1) & \color{red}(a \wedge b) \vee (\overline{a} \vee \overline{b}) & = & 1_B \\ (2) & \color{red}(a \wedge b) \wedge (\overline{a} \vee \overline{b}) & = & 0_B \end{cases} \)

Dem.:
\( (1) \; (a \wedge b) \vee (\overline{a} \vee \overline{b}) = (a \vee b \vee \overline{a}) \wedge (a \vee b \vee \overline{b}) = (a \vee \overline{a} \vee b) \wedge 1_B = 1_B \wedge 1_B = 1_B \).

\( (2) \;  (a \wedge b) \wedge (\overline{a} \vee \overline{b}) = (a \wedge \overline{a} \wedge \overline{b}) \vee (b \wedge \overline{a} \wedge \overline{b}) = \ldots = 0_B \vee 0_B = 0_B \).



Entiendo las operaciones que hizo para obtener el primer y último elemento pero no entiendo el por qué de lo rojo. Yo tengo la definición de

Sea \( (B, ≼) \) Álgebra de Boole: \( \forall{}x \in{} B, \exists{}\overline{x} \in{} B: \begin{cases}x \wedge \overline{x} & = & 0_B \\ x \vee \overline{x} & = & 1_B \end{cases} \). ¿No es esto diferente a lo que puse en rojo? Entiendo que tomó \( x = (\overline{a} \vee \overline{b}) \), pero \( \overline{x} \) debería ser \( \overline{x} = \overline{(\overline{a} \vee \overline{b})} \). O sea ¿\( \overline{x} = \overline{(\overline{a} \vee \overline{b})} = (a \wedge b) \) por De Morgan?

Gracias!!

De seguro ya habían demostrado: \( \overline{a\vee b}=\bar{a} \wedge \bar{b} \). Es lo que está usando en la prueba.

Saludos

02 Febrero, 2020, 07:23 am
Respuesta #2

manooooh

  • Matemático
  • Mensajes: 2,989
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

No consigo darme cuenta cómo debería probarse. En mi libro dice que para probar esta y otras propiedades se puede tomar como HIPÓTESIS a la definición de Álgebra de Boole y demostrar lo que se pida.

Tengo 2 definiciones que son equivalentes entre sí:

Definición 1: Un Álgebra de Boole es una red distributiva y complementada.

Definición 2: Sea \( (B,\vee,\wedge) \). Diremos que \( B \) es Álgebra de Boole si:

a) \( \vee \) y \( \wedge \) son operaciones binarias cerradas en \( B \).

b) \( \vee \) y \( \wedge \) son conmutativas.

c) \( \vee \) y \( \wedge \) son distributivas entre sí.

d) \( \vee \) y \( \wedge \) tienen elementos neutros \( 0_B \) y \( 1_B \) respectivamente.

e) Todos los elementos de \( B \) tienen complementos.



Bajo cualquiera de estas 2 definiciones uno debería ser capaz de probar que \( \overline{a \wedge b} = \overline{a} \vee \overline{b} \), pero no logro dar con la prueba.

Ejemplo
A modo de ejemplo pondré una demostración sobre redes:

Propiedad. En toda red distributiva, el complemento, si existe, es único.

Demostración. Supongamos que un elemento \( a \) posee dos complementos \( b \) y \( c \). Entonces: \( a\vee b=1 \), \( a\wedge b=0 \), \( a\vee c=1 \) y \( a\wedge c=0 \). Luego sabemos que:

\( b=b\wedge 1=b\wedge(a\vee c)=(b\wedge a)\vee(b\wedge c)=0\vee(b\wedge c)=(a\wedge c)\vee(b\wedge c)=(a\vee b)\wedge c=1\wedge c=c. \)
[cerrar]

Saludos

02 Febrero, 2020, 07:32 am
Respuesta #3

manooooh

  • Matemático
  • Mensajes: 2,989
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Se me ocurre algo así...:

Sea \( x=\overline{a\wedge b} \). Entonces \( x=x\wedge(x\vee\overline{x})=\overline{a\wedge b}\wedge(\overline{a\wedge b}\vee(a\wedge b)) \).

Pero ahí me quedo.

Saludos

02 Febrero, 2020, 09:40 am
Respuesta #4

feriva

  • Matemático
  • Mensajes: 9,067
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Hola, manooooh, buenos días.

¿Qué quieren decir las líneas sobre la “x”?

Imagino que significa algo así como “complementario”, porque esto \( \overline{a\wedge b}=\overline{a}\vee\overline{b}
  \) lo veo “isomorfo” a la primera ley de Morgan, es decir, si cambiamos la raya por “c” y los signos de “Y”, “O” por unión y la intersección, tenemos la expresión que se usa en teoría de conjuntos \( (A\cup B)^{c}=A^{c}\cap B^{c}
  \) (donde también se utiliza la raya a veces en vez de la “c”; o también la “prima”).

Si es así, la demostración de la leyes de Morgan supongo que te pueden servir para orientarte, aunque aquí se trate de una salida para el “bit” 1 ó para el cero.

Saludos.

02 Febrero, 2020, 09:53 am
Respuesta #5

manooooh

  • Matemático
  • Mensajes: 2,989
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola feriva, buenos días

Efectivamente! Se trata de la ley de DeMorgan pero aplicada a un Álgebra de Boole.

Si bien no había visto su demostración en la Wikipedia hasta hace 2 segundos, me interesa tratar de probar DeMorgan usando las herramientas del Álgebra de Boole.

¿Se podrá?

Saludos y gracias

02 Febrero, 2020, 10:13 am
Respuesta #6

feriva

  • Matemático
  • Mensajes: 9,067
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
  • No soy matemático, eso es una etiqueta.
Hola feriva, buenos días

Efectivamente! Se trata de la ley de DeMorgan pero aplicada a un Álgebra de Boole.

Si bien no había visto su demostración en la Wikipedia hasta hace 2 segundos, me interesa tratar de probar DeMorgan usando las herramientas del Álgebra de Boole.

¿Se podrá?

Saludos y gracias

No me puedo arriesgar a decirte que sí sin conocer esto, pero imagino que todo es cuestión de adaptar los conceptos; una nube es como una bola de algodón, haciendo un símil, pero no es una bola de algodón. Del igual modo, no es lo mismo un “x” que pertenece a un conjunto unido a otros, que una respuesta “uno” o una respuesta “cero”; que intuyo que es de lo que se trata aquí, o algo parecido, por analogía con la programación y los circuitos y esas cosas. Pero sí que creo que en esencia tiene un punto de contacto; la cuestión estará en encontrar una similitud, depende de cómo cada uno (un poco subjetivamente) relaciona los conceptos.

Saludos.


02 Febrero, 2020, 10:33 am
Respuesta #7

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,035
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Sea \( (B, ≼) \) Álgebra de Boole: \( \forall{}x \in{} B, \exists{}\overline{x} \in{} B: \begin{cases}x \wedge \overline{x} & = & 0_B \\ x \vee \overline{x} & = & 1_B \end{cases} \).

Esa definición significa que dado \( x \) se define \( \bar{x} \) como el único elemento cumpliendo:

\(  \begin{cases}x \wedge \overline{x} & = & 0_B \\ x \vee \overline{x} & = & 1_B \end{cases} \)

Citar
¿No es esto diferente a lo que puse en rojo? Entiendo que tomó \( x = (\overline{a} \vee \overline{b}) \), pero \( \overline{x} \) debería ser \( \overline{x} = \overline{(\overline{a} \vee \overline{b})} \).


No, lo ha aplicado a \( x=a\wedge b \). Ve que \( \overline{a}\vee \overline{b} \) cumple lo que se le exige en la definición de \( \bar x \) y así prueba que \( \bar x=\overline{a}\vee \overline{b} \), es decir, que \( \overline{a\wedge b}=\overline{a}\vee \overline{b} \).

Saludos.

02 Febrero, 2020, 10:43 am
Respuesta #8

manooooh

  • Matemático
  • Mensajes: 2,989
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola Luis, muchas gracias

No entiendo tu último párrafo y es la clave para comprender la prueba.

¿Cómo que "ve"? Si no hay otra cosa que ver, es obvio que no iba a tomar \( x=a\wedge a\wedge\overline{b}\vee a \) o cualquier otra cosa que no sea algún miembro de la igualdad, a mi criterio. ¿Podrías detallar ese párrafo?

Saludos

02 Febrero, 2020, 11:12 am
Respuesta #9

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 47,035
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Hola

No entiendo tu último párrafo y es la clave para comprender la prueba.

¿Cómo que "ve"? Si no hay otra cosa que ver, es obvio que no iba a tomar \( x=a\wedge a\wedge\overline{b}\vee a \) o cualquier otra cosa que no sea algún miembro de la igualdad, a mi criterio. ¿Podrías detallar ese párrafo?

Ese "ve" quiere decir comprueba, verfica, demuestra, chequea. ¿Dónde lo hace?. Esa comprobación está aquí:

Dem.:
\( (1) \; (a \wedge b) \vee (\overline{a} \vee \overline{b}) = (a \vee b \vee \overline{a}) \wedge (a \vee b \vee \overline{b}) = (a \vee \overline{a} \vee b) \wedge 1_B = 1_B \wedge 1_B = 1_B \).

\( (2) \;  (a \wedge b) \wedge (\overline{a} \vee \overline{b}) = (a \wedge \overline{a} \wedge \overline{b}) \vee (b \wedge \overline{a} \wedge \overline{b}) = \ldots = 0_B \vee 0_B = 0_B \).

Y volviendo al principio por si no quedó claro. Por definición para probar que \( \bar x=y \) se tiene que comprobar que \( x \) e \( y \) cumplen:

\( \begin{cases}x \wedge y & = & 0_B \\ x \vee y & = & 1_B \end{cases} \)

En nuestro caso si queremos comprobar que \( \overline{a\wedge b}=\bar a\vee \bar b \) tenemos que comprobar que:

\( \begin{cases}(a\wedge b) \wedge (\bar a\vee \bar b) & = & 0_B \\ (a\wedge b) \vee (\bar a\vee \bar b) & = & 1_B \end{cases} \)

Saludos.