Autor Tema: Probar: Toda álgebra de Boole finita es isomorfa al conjunto de partes de átomos

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

05 Julio, 2020, 12:35 am
Respuesta #40

manooooh

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

Me parece que te estás liando un poco. Vamos a ver la demostración de \( h(u) \subseteq V \) con más calma (si no entiendes algún paso dilo). Pasaré de las \( q \) y hablaré directamente de \( v_i \), así simplificamos la notación.

1. Sea \( p \in h(u) \). Por definición tenemos que \( p \) es un átomo (en particular \( p \neq 0 \)) y \( p \leq u \).

2. Lema: Existe \( v_i \in V \) tal que \( p \wedge v_i \neq 0 \).
Demostración del lema:
Por reducción al absurdo, supón que es falso, es decir, para todo \( v_i\in V \)  se tiene que \( p \wedge v_i = 0 \). Entonces:
\( p \wedge u = p\wedge (v_1 \vee \dots \vee v_n) = (p \wedge v_1) \vee \dots \vee (p \wedge v_n)=0 \).
Como \( p \leq u \), \( p = p \wedge u = 0 \). Pero como \( p \) es un átomo, \( p \neq 0 \), contradicción.

3. Por el lema anterior sabemos que existe \( v_i \in V \) con \( p \wedge v_i \neq 0 \). Como \( 0 < p\wedge v_i \leq p \) y \( p \) es átomo, \( p= p\wedge v_i \). Similarmente, como \( 0<p\wedge v_i \leq v_i \) y \( v_i \) es átomo, \( v_i = p \wedge v_i \). Juntando las dos igualdades obtenemos \( p = p\wedge v_i = v_i \). Luego \( p = v_i \in V \) y hemos acabado.

En definitiva, creo que lo que te confunde es el lema, o mejor dicho, la estructura de la demostración. No es que tomemos un \( q \) como algún elemento de \( V \) sin más. Es que primero demostramos que hay un \( q \in V \) con \( p \wedge q \neq 0 \) (para ello usamos reducción al absurdo y el argumento de la demostración del lema) y una vez sabemos que un tal \( q \) existe tomamos ese \( q \).

 :aplauso: :aplauso:. Lo veo más claro. Desde el punto 2 ya veo que necesariamente ha de ocurrir que \( v_i=p\in V \), ¡qué fácil lo has hecho!

Saludos

05 Julio, 2020, 12:47 am
Respuesta #41

manooooh

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

Me gusta más usar esta forma:

  • \( h \) es sobreyectiva: Para todo \( V\in P(A) \) existe \( u\in B \) tal que \( V=h(u) \).
    • Probar: Dado \( V=\{v_1,\dots,v_n\} \) un conjunto formado por átomos de \( B \), si tomamos \( u=v_1\lor\dots\lor v_n\in B \), entonces \( V=h(u) \).
      • \( \vdots \)
      • \( p\in h(u) \), o sea \( p \) es un átomo y \( p\leq u \).
      • Por otro lado, existe \( v_i\in V \) tal que \( p\land v_i\neq0_B \).
        • Por reducción al absurdo.
        • \( p \wedge u = p\wedge (v_1 \vee \dots \vee v_n) = (p \wedge v_1) \vee \dots \vee (p \wedge v_n)=0 \).
        • Como \( p\leq u \) y \( p\land u=0_B \), \( p=0_B \). Contradicción.
      • Como \( 0<p\land v_i\leq p \) y \( p \) es átomo, \( p=p\land v_i \).
      • Similarmente, como \( 0<p\land v_i\leq v_i \) y \( v_i \) es átomo, \( v_i=p\land v_i \).
      • \( v_i=p\in V \).

¿Está bien?

Saludos

05 Julio, 2020, 12:58 am
Respuesta #42

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sí, en principio lo veo bien. Aunque habría que ver como lo explicas en el vídeo, claro.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

10 Julio, 2020, 09:00 am
Respuesta #43

manooooh

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

Revisando un poco el tema me ha entrado duda en la demostración de que \( h(\overline u)=\overline{h(u)} \):

(...) Es decir, que \( p\in h(\overline{u}) \) significa que \( p\leq\overline{u} \), o sea \( \neg(p\leq u) \), o sea \( \neg(p\in h(u)) \), o sea \( p\in\overline{h(u)} \). (...)

Sabemos que \( p \) es un átomo y \( p\leq u \) si y sólo si \( p\in h(u) \). ¿De aquí se desprende que \( p\notin h(u) \) si y sólo si... opción 1): \( \neg(\text{\(p\) es un átomo y \(p\leq u\)}) \), o la opción 2: \( \text{\(p\) es un átomo y }\neg(p\leq u) \)? ¿Cuál de las dos?

Porque no entiendo cuál de las 2 opciones es que uso en la prueba:

Como \( p\in h(\overline u) \) entonces \( p \) es un átomo y \( p\leq\overline {u} \). O sea \( p \) es un átomo y \( \neg(p\leq u) \). O sea \( \neg(\text{\(p\) NO es un átomo } \underline{\text{o}}\;p\leq u) \) (por De Morgan). Y a partir de aquí no sé qué opción aplicar, porque en el paso anterior sería la opción 2 pero para mí si uno quiere negar \( p\iff q \) debería ser \( \neg p\iff\neg q \) o cómo ???.

Ya sé que no debería preguntar por cuestiones simbólicas, pero es que de verdad la parte de "\( p \) es un átomo" no sé cómo ponerla, porque aunque en la prueba quede bonito no reiterarlo todo el tiempo, aquí me confundo y no puedo darme completamente por satisfecho con todo el trabajo si no entiendo bien lo que hicimos.

Gracias y saludos

10 Julio, 2020, 09:29 am
Respuesta #44

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
\( p \in h(u) \) si y solo si \( p \) es un átomo y \( p \leq u \).
Luego \( p \notin h(u) \) si y solo si \( p \) no es un átomo o \( p \not\leq u \).
Es decir, la opción 1. La opción 2 no puede ser porque implicaría que \( h(u) \) contiene a todos los elementos que no son átomos.

Fíjate pues que para comprobar \( p \notin h(u) \) te basta con comprobar que \( p \) no es átomo, o bien que \( p \not\leq u \). En la parte que nos interesa demostramos que \( p \not\leq u \), así que ya podemos afirmar que \( p \notin h(u) \), independientemente de si \( p \) es átomo o no.

De manera muy formal, esto es porque si tienes que \( p \not\leq u \) también tienes \( \neg(p \leq u) \vee (p \text{ no es un átomo}) \) (ya que para que una disyunción sea verdadera basta con que lo sea una de sus componentes) que es equivalente a \( \neg(p \leq u \wedge (p \text{ es un átomo})) \) que a su vez es equivalente a \( p \notin h(u) \).

Aunque insisto en que me parece que le das más vueltas a la formalización de estas cosas de las necesarias. Si yo te digo que \( h(u) \) es el conjunto de elementos \( p \) que a la vez son átomos y cumplen \( p \leq u \), debería estar claro que si \( p \not\leq u \), \( p \) no puede estar en \( h(u) \), sea átomo o no. Igual que si te digo que \( A \) es el conjunto de futbolistas argentinos y te presento a un tipo que no es futbolista ya puedes saber que no está en \( A \), sea o no argentino.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

10 Julio, 2020, 09:46 am
Respuesta #45

manooooh

  • Matemático
  • Mensajes: 2,989
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Entendido. Caí como un novato: pensando en que para demostrar que una disyunción es verdadera era necesario probar ambas partes, pero no, con una alcanza.

Son errores de novato que no puedo permitirme. Me falta más "práctica".

Muchas gracias geométracat.

Saludos

12 Agosto, 2020, 08:50 am
Respuesta #46

manooooh

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

Leyendo esta cita:

He vuelto a mirar el hilo y con la lista que diste al final creo que deberías ser capaz de probar cualquier tautología, pues son los axiomas de un álgebra de Boole (y más cosas).


Me has recordado a cuando había que demostrar el homomorfismo, específicamente que \( h(u\lor v)=h(u)\cup h(v) \) y \( h(\overline{u})=\overline{h(u)} \) se deducen las otras 3 propiedades (se preserva el ínfimo y los primer y último elementos).

¿Eso es así porque el conjunto \( \{\lor,\overline{\vphantom{a}}\} \) es funcionalmente completo? Llamamos a un conjunto de tipos de compuertas lógicas (AND, NOT etc.) funcionalmente completo si con dicho conjunto se pueden representar cualquier función booleana.

Esto es así pues para definir a \( \land \) basta con decir \( a\land b=\overline{\overline{a}\lor\overline{b}} \), para \( 1 \) se escribe \( 1=\overline{a}\lor a \) y \( 0=\overline{a}\land a=\overline{a\lor\overline{a}} \), ¿está bien?

Pero también es cierto que el conjunto \( \{\mathrm{NAND}\} \) (Not-AND) es funcionalmente completo. ¿Por qué Carlos entonces usa un conjunto funcionalmente completo de 2 elementos y no de 1 solo? ¿Y por qué no eligió un conjunto de 3 elementos?



Puedes corregirme lo anterior, creo que la siguiente nota simplifica los cálculos:

NOTA Para poder representar cualquier función booleana es necesario y suficiente que se puedan representar las dos operaciones binarias (supremo e ínfimo) y la unaria (complemento).

Con esto nos quitamos de encima las pruebas de \( h(1)=1 \) y \( h(0)=0 \), ¿verdad? ¿Y cómo se demostraría esa nota/propiedad? Dice que es condición necesaria y suficiente, o sea una doble implicación...

Saludos

12 Agosto, 2020, 10:55 am
Respuesta #47

geómetracat

  • Moderador Global
  • Mensajes: 1,699
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Me has recordado a cuando había que demostrar el homomorfismo, específicamente que \( h(u\lor v)=h(u)\cup h(v) \) y \( h(\overline{u})=\overline{h(u)} \) se deducen las otras 3 propiedades (se preserva el ínfimo y los primer y último elementos).

¿Eso es así porque el conjunto \( \{\lor,\overline{\vphantom{a}}\} \) es funcionalmente completo? Llamamos a un conjunto de tipos de compuertas lógicas (AND, NOT etc.) funcionalmente completo si con dicho conjunto se pueden representar cualquier función booleana.

Sí, exacto.

Citar
Esto es así pues para definir a \( \land \) basta con decir \( a\land b=\overline{\overline{a}\lor\overline{b}} \), para \( 1 \) se escribe \( 1=\overline{a}\lor a \) y \( 0=\overline{a}\land a=\overline{a\lor\overline{a}} \), ¿está bien?

Sí, está perfecto.

Citar
Pero también es cierto que el conjunto \( \{\mathrm{NAND}\} \) (Not-AND) es funcionalmente completo. ¿Por qué Carlos entonces usa un conjunto funcionalmente completo de 2 elementos y no de 1 solo? ¿Y por qué no eligió un conjunto de 3 elementos?
Sí, lo podrías hacer con una sola operación usando el NAND. Si no se suele hacer así es por varios motivos.

Uno es que el NAND tiene una interpretación bastante menos natural que las tres habituales, lo que hace más difícil pensar en términos de NAND que en términos de \( \vee,\wedge \) y complementos. Por ejemplo, si \( A,B \) son conjuntos de un álgebra, la unión, intersección y complementos son operaciones muy naturales, que se usan continuamente. En cambio el NAND corresponde a \( \overline{A \cap B} \), que es menos natural y no se usa tanto.

Otro motivo es que a la hora de definir álgebra de Boole es conveniente usar la definición con \( \wedge,\vee \) y complementos, porque así puedes ver directamente un álgebra de Boole como un caso particular de retículo, y usar toda la teoría que sabes sobre retículos directamente.

Sobre por qué Carlos usa dos operaciones en lugar de una o tres habría que preguntárselo a él. Pero mi conjetura es que usa dos porque en las definición usual de álgebra de conjuntos, la que se suele encontrar en prácticamente cualquier libro de teoría de la medida, se define álgebra de conjuntos en \( X \) como un subconjunto de \( P(X) \) que cumple que \( X \) está en el algebra y que es cerrada bajo complementos y uniones. Es una cuestión de convenio, pero así te ahorras tratar explícitamente una operación (la intersección en este caso) y por otro lado trabajas con dos operaciones "naturales" (complemento y unión) en vez de con una operación menos natural (NAND).

Pero vamos, que es cuestión de gustos. Lo puedes hacer como quieras, tanto con tres, como con dos, como con una operación y nadie te podrá decir que esté mal.

Citar
Puedes corregirme lo anterior, creo que la siguiente nota simplifica los cálculos:

NOTA Para poder representar cualquier función booleana es necesario y suficiente que se puedan representar las dos operaciones binarias (supremo e ínfimo) y la unaria (complemento).

Con esto nos quitamos de encima las pruebas de \( h(1)=1 \) y \( h(0)=0 \), ¿verdad? ¿Y cómo se demostraría esa nota/propiedad? Dice que es condición necesaria y suficiente, o sea una doble implicación...

Sí. Es lo mismo de antes. Si partes de un conjunto primitivo de operaciones y eres capaz de representar \( \vee, \wedge \) y complementos eres capaz de representar cualquier función Booleana (porque éstas son por definición las que puedes obtener usando esas tres operaciones). Y al revés, si puedes representar cualquier función Booleana a partir de un conjunto de operaciones, puedes representar \( \vee,\wedge \) y complementos (porque \( (p,q) \mapsto p \vee q \) es una función Booleana y lo mismo con las otras).
La ecuación más bonita de las matemáticas: \( d^2=0 \)