Álgebra de Boole

El álgebra de Boole, también llamada álgebra booleana, en electrónica digital, informática y matemática es una estructura algebraica que esquematiza las operaciones lógicas.

Historia

 

Se denomina así en honor a George Boole (02 de noviembre de 1815 a 8 de diciembre de 1864), matemático inglés autodidacta, que fue el primero en definirla como parte de un sistema lógico, inicialmente en un pequeño folleto, The Mathematical Analysis of Logic,^[1]​ publicado en 1847, en respuesta a una controversia en curso entre Augustus De Morgan y sir William Rowan Hamilton. El álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. Más tarde fue extendido como un libro más importante: An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities (también conocido como An Investigation of the Laws of Thought ^[2]​ o simplemente The Laws of Thought^[3]​), publicado en 1854.

Las interpretaciones respectivas de los símbolos 0 y 1 en el sistema de lógica son Nada y Universo.

George Boole^[4]​

En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1948. Esta lógica se puede aplicar a dos campos:

• Al análisis, porque es una forma concreta de describir cómo funcionan los circuitos.
• Al diseño, ya que teniendo una función se aplica dicha álgebra para poder desarrollar una implementación de la función.

Definición

Dado un conjunto ${\displaystyle {\mathfrak {B}}}$  en el que se han definido dos leyes de composición interna ${\displaystyle \oplus ,\odot }$ . La estructura ${\displaystyle ({\mathfrak {B}},\oplus ,\odot )}$ es un álgebra de Boole si y solo si ${\displaystyle ({\mathfrak {B}},\oplus ,\odot )}$ es un Retículo distributivo,^[5]​ esto es:

• ${\displaystyle \odot }$  es distributiva respecto a ${\displaystyle \oplus }$ :

${\displaystyle a\odot (b\oplus c)=(a\odot b)\oplus (a\odot c)}$ 

• ${\displaystyle \oplus }$  es distributiva respecto a ${\displaystyle \odot }$ 

${\displaystyle a\oplus (b\odot c)=(a\oplus b)\odot (a\oplus c)}$ 

Basándose en esta definición se determina el siguiente...

Principio

Dado un conjunto: ${\displaystyle {\mathfrak {B}}}$  formado cuando menos por los elementos: ${\displaystyle \varnothing ,\;U}$  en el que se ha definido:

• Una operación unaria interna, que llamaremos complemento:

${\displaystyle {\begin{array}{rrcl}\sim :&{\mathfrak {B}}&\to &{\mathfrak {B}}\\&a&\to &b=\sim a\end{array}}}$ 

En esta operación definimos una aplicación que, a cada elemento a de B, le asigna un b de B.

${\displaystyle \forall a\in {\mathfrak {B}}\,:\quad \exists !b\in {\mathfrak {B}}\;/\quad b=\sim a}$ 

Para todo elemento a en B, se cumple que existe un único b en B, tal que b es el complemento de a.

• La operación binaria interna, que llamaremos suma:

${\displaystyle {\begin{array}{rrcl}\oplus :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\oplus b\end{array}}}$ 

por la que definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

${\displaystyle \forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\oplus b}$ 

Para todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de sumar a con b.

• La operación binaria interna, que llamaremos producto:

${\displaystyle {\begin{array}{rrcl}\odot :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\odot b\end{array}}}$ 

Con lo que definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

${\displaystyle \forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\odot b}$ 

Para todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal que c es el resultado del producto a y b.

Dada la definición del álgebra de Boole como una estructura algebraica genérica, según el caso concreto de que se trate, la simbología y los nombres de las operaciones pueden variar.

Axiomas necesarios

Diremos que este conjunto y las operaciones así definidas: ${\displaystyle ({\mathfrak {B}},\sim ,\oplus ,\odot )}$  son un álgebra de boole, si cumple las siguientes axiomas:

1a: La ley asociativa de la suma: ${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;(a\oplus b)\oplus c=a\oplus (b\oplus c)}$  2a: Existencia del elemento neutro para la suma: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\oplus \varnothing =a}$  3a: La ley conmutativa de la suma: ${\displaystyle \forall a,b\in {\mathfrak {B}}:\;a\oplus b=b\oplus a}$  4a: Ley distributiva de la suma respecto al producto: ${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;a\oplus (b\odot c)=(a\oplus b)\odot (a\oplus c)}$  5a: Existe elemento complementario para la suma: ${\displaystyle \forall a\in {\mathfrak {B}};\;\exists \sim a\in {\mathfrak {B}}:\;a\oplus \sim a=U}$

1b: La ley asociativa del producto: ${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;(a\odot b)\odot c=a\odot (b\odot c)}$  2b: Existencia del elemento neutro para el producto: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\odot U=a}$  3b: La ley conmutativa del producto: ${\displaystyle \forall a,b\in {\mathfrak {B}}:\;a\odot b=b\odot a}$  4b: Ley distributiva del producto respecto a la suma: ${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;a\odot (b\oplus c)=(a\odot b)\oplus (a\odot c)}$  5b: Existe elemento complementario para el producto: ${\displaystyle \forall a\in {\mathfrak {B}};\;\exists \sim a\in {\mathfrak {B}}:\;a\odot \sim a=\varnothing }$

Teoremas fundamentales

Partiendo de los cinco axiomas anteriores, se pueden deducir y demostrar los siguientes teoremas fundamentales:

6a: Ley de idempotencia para la suma: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\oplus a=a}$  7a: Ley de absorción para la suma: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\oplus U=U}$  8a: Ley de identidad para la suma: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\oplus \varnothing =a}$

6b: Ley de idempotencia para el producto: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\odot a=a}$  7b: Ley de absorción para el producto: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\odot \varnothing =\varnothing }$  8b: Ley de identidad para el producto: ${\displaystyle \forall a\in {\mathfrak {B}}:\;a\odot U=a}$

9: Ley de involución: ${\displaystyle \forall a\in {\mathfrak {B}}:\;\sim (\sim a)=a}$  10: Ley del complemento: ${\displaystyle \sim U=\varnothing \;,\quad \sim \varnothing =U}$  11: Leyes de De Morgan: ${\displaystyle \forall a,b\in {\mathfrak {B}}:\;\sim (a\oplus b)=\sim a\odot \sim b}$  ${\displaystyle \forall a,b\in {\mathfrak {B}}:\;\sim (a\odot b)=\sim a\oplus \sim b}$

Orden en el álgebra de Boole

Sea: ${\displaystyle ({\mathfrak {B}},\sim ,\oplus ,\odot )}$  un álgebra de Boole, sean a, b dos elementos del conjunto, podremos decir entonces que a antecede a b y lo denotamos:

${\displaystyle a\preceq b}$ 

si se cumple alguna de las siguientes condiciones:

1. ${\displaystyle a\oplus b=b}$ 
2. ${\displaystyle a\odot b=a}$ 
3. ${\displaystyle \sim a\oplus b=U}$ 
4. ${\displaystyle a\odot \sim b=\varnothing }$ 

Estas cuatro condiciones se consideran equivalentes y el cumplimiento de una de ellas implica necesariamente el cumplimiento de las demás. Definiendo un conjunto parcialmente ordenado.

Si se cumple que:

${\displaystyle a,b\in {\mathfrak {B}}\;:\quad a\preceq b\;\lor \;b\preceq a\quad \longrightarrow \quad a,b\rightarrow {\mathit {comparables}}}$ 

Para los valores a, b de ${\displaystyle {\mathfrak {B}}}$ , que cumplen que a antecede a b, o que b antecede a a, se dice que a y b son comparables.

Si se cumple que:

${\displaystyle a,b\in {\mathfrak {B}}\;:\quad a\npreceq b\;\land \;b\npreceq a\quad \longrightarrow \quad a,b\rightarrow {\mathit {no\;comparables}}}$ 

Para los valores a, b de ${\displaystyle {\mathfrak {B}}}$ , que cumplen que a no antecede a b, y que b no antecede a a, se dice que a y b son no comparables.

Principio de dualidad

El concepto de dualidad permite formalizar este hecho: a toda relación o ley lógica le corresponderá su dual, formada mediante el intercambio de los operadores suma con los de producto, y de los ${\displaystyle U\;}$  con los ${\displaystyle \varnothing }$ .

	Adición	Producto
1	${\displaystyle a\oplus \sim {a}=U\,}$	${\displaystyle a\odot \sim {a}=\varnothing }$
2	${\displaystyle a\oplus \varnothing =a\,}$	${\displaystyle a\odot U=a\,}$
3	${\displaystyle a\oplus U=U\,}$	${\displaystyle a\odot \varnothing =\varnothing \,}$
4	${\displaystyle a\oplus a=a\,}$	${\displaystyle a\odot a=a\,}$
5	${\displaystyle a\oplus b=b\oplus a\,}$	${\displaystyle a\odot b=b\odot a\,}$
6	${\displaystyle a\oplus (b\oplus c)=(a\oplus b)\oplus c\,}$	${\displaystyle a\odot (b\odot c)=(a\odot b)\odot c\,}$
7	${\displaystyle a\oplus (b\odot c)=(a\oplus b)\odot (a\oplus c)\,}$	${\displaystyle a\odot (b\oplus c)=(a\odot b)\oplus (a\odot c\,)}$
8	${\displaystyle a\oplus a\odot b=a\,}$	${\displaystyle a\odot (a\oplus b)=a\,}$
9	${\displaystyle \sim {(a\oplus b)}=\sim {a}\odot \sim {b}}$	${\displaystyle \sim {(a\odot b)}=\sim {a}\oplus \sim {b}\,}$

Otras formas de notación del álgebra de Boole

En Lógica binaria se suele emplear la notación ${\displaystyle (\{0,1\},{\bar {}},+,\cdot )}$ , común en la tecnología digital, siendo la forma más usual y la más cómoda de representar.

Por ejemplo las leyes de De Morgan se representan así:

${\displaystyle {\overline {a+b}}={\bar {a}}\cdot {\bar {b}}\,}$ 

${\displaystyle {\overline {a\cdot b}}={\bar {a}}+{\bar {b}}\,}$ 

Cuando el álgebra de Boole se emplea en electrónica, suele emplearse la misma denominación que para las puerta lógica AND (Y), OR (O) y NOT (NO), ampliándose en ocasiones con X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y X-NOR (equivalencia). las variables pueden representarse con letras mayúsculas o minúsculas, y pueden tomar los valores {0, 1}.

Empleando esta notación las leyes de De Morgan se representan:

${\displaystyle {\mbox{NOT }}(a{\mbox{ OR }}b)={\mbox{NOT }}a{\mbox{ AND }}{\mbox{NOT }}b\,}$ 

${\displaystyle {\mbox{NOT }}(a{\mbox{ AND }}b)={\mbox{NOT }}a{\mbox{ OR }}{\mbox{NOT }}b\,}$ 

En su aplicación a la lógica se emplea la notación ${\displaystyle \land \lor \lnot }$  y las variables pueden tomar los valores {F, V}, falso o verdadero, equivalentes a {0, 1}

Con la notación lógica las leyes de De Morgan serían así:

${\displaystyle \lnot {(a\lor b)}=\lnot {a}\land \lnot {b}\,}$ 

${\displaystyle \lnot {(a\land b)}=\lnot {a}\lor \lnot {b}\,}$ 

En el formato de Teoría de conjuntos el Álgebra de Boole toma el aspecto: ${\displaystyle ({\mathcal {P}}(U),\sim ,\cup ,\cap )}$ 

En esta notación las leyes de De Morgan serían así:

${\displaystyle \sim {(a\cup b)}=\;\sim {a}\;\cap \sim {b}\,}$ 

${\displaystyle \sim {(a\cap b)}=\;\sim {a}\;\cup \sim {b}\,}$ 

Otra forma en la álgebra de conjuntos del Álgebra de Boole, las leyes de De Morgan serían así:

${\displaystyle {(A\cup B)}^{C}=\;{A}^{C}\cap {B}^{C}}$ 

${\displaystyle {(A\cap B)}^{C}=\;{A}^{C}\cup {B}^{C}}$ 

Desde el punto de vista práctico existe una forma simplificada de representar expresiones booleanas. Se emplean apóstrofos (') para indicar la negación, la operación suma (+) se representa de la forma normal en álgebra, y para el producto no se emplea ningún signo, las variables se representan, normalmente con una letra mayúscula, la sucesión de dos variables indica el producto entre ellas, no una variable nombrada con dos letras.

La representación de las leyes de De Morgan con este sistema quedaría así, con letra minúsculas para las variables:

${\displaystyle (a+b)'=a'b'\,}$ 

${\displaystyle (ab)'=a'+b'\,}$ 

y así, empleando letras mayúsculas para representar las variables:

${\displaystyle (A+B)'=A'B'\,}$ 

${\displaystyle (AB)'=A'+B'\,}$ 

Todas estas formas de representación son correctas, se utilizan de hecho, y pueden verse al consultar bibliografía. La utilización de una u otra notación no modifica el álgebra de Boole, solo su aspecto, y depende de la rama de las matemáticas o la tecnología en la que se esté utilizando para emplear una u otra notación.

Estructuras algebraicas que son álgebra de Boole

Hay numerosos casos de distintos análisis de estructuras algebraicas que corresponden al álgebra de Boole, aunque en apariencia son muy diferentes, su estructura es la misma. Vamos a ver algunos de ellos, con el propósito de hacer palpable las similitudes en la estructura y los distintos ámbitos de aplicación y distinta terminología para referirse a las operaciones o a las variables.

Lógica binaria

Artículo principal: Lógica binaria

Artículo principal: Sistema digital

Artículo principal: Sistema binario

Artículo principal: Tabla de verdad

Artículo principal: Sistema combinacional

Artículo principal: Formas canónicas (álgebra de Boole)

Artículo principal: Circuito de conmutación

Una serie de temas, aparentemente tan distintos, tiene dos cosas en común, la lógica binaria basada en los ceros y los unos y el álgebra de Boole, posiblemente la forma más conocida de esta álgebra, que en ocasiones da lugar a la interpretación que el álgebra de Boole es la lógica binaria exclusivamente, así el conjunto ${\displaystyle {\mathfrak {B}}}$  en este caso está formado por dos elementos {0,1}, o {F, V}, o {no, sí}, dos valores contrapuestos, que son las dos posibles alternativas entre dos situaciones posibles, aquí, sin pérdida de la generalidad, tomaremos el conjunto: {0,1} como ya hemos dicho:

${\displaystyle {\mathfrak {B}}=\{0,1\}}$ 

Donde:

${\displaystyle \varnothing =0}$ 

${\displaystyle U=1\;}$ 

• La operación unaria interna, que llamaremos negación:

${\displaystyle {\begin{array}{c|c}a&{\bar {a}}\\\hline 0&1\\1&0\end{array}}}$

${\displaystyle {\begin{array}{rrcl}{\bar {}}:&{\mathfrak {B}}&\to &{\mathfrak {B}}\\&a&\to &b={\bar {a}}\end{array}}}$ 

La operación unaria interna negación, definimos una aplicación que a cada elemento a de {0,1}, le asigna un b de {0,1}.

${\displaystyle \forall a\in {\mathfrak {B}}\,:\quad \exists !b\in {\mathfrak {B}}\;/\quad b={\bar {a}}}$ 

Para todo elemento a en {0,1}, se cumple que existe un único b en {0,1}, tal que b es la negación de a. Como se ve en la tabla.

• La operación binaria interna, que llamaremos suma:

${\displaystyle {\begin{array}{cc|c}a&b&a+b\\\hline 1&1&1\\1&0&1\\0&1&1\\0&0&0\\\end{array}}\quad \longleftrightarrow \quad {\begin{array}{c|cc}0&1&0\\1&1&1\\\hline +&1&0\\\end{array}}}$

${\displaystyle {\begin{array}{rrcl}+:&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a+b\end{array}}}$ 

Con la operación suma definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

${\displaystyle \forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a+b}$ 

Para todo par ordenado (a,b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de sumar a con b.

• la operación binaria interna, que llamaremos producto:

${\displaystyle {\begin{array}{cc|c}a&b&a\cdot b\\\hline 1&1&1\\1&0&0\\0&1&0\\0&0&0\\\end{array}}\quad \longleftrightarrow \quad {\begin{array}{c|cc}0&0&0\\1&1&0\\\hline \cdot &1&0\\\end{array}}}$

${\displaystyle {\begin{array}{rrcl}\cdot :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\cdot b\end{array}}}$ 

Con la operación producto definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

${\displaystyle \forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\cdot b}$ 

Para todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal que c es el resultado del producto a y b. Como se puede ver en la tabla.

Axiomas

Así ${\displaystyle (\{0,1\},{\bar {}},+,\cdot )}$  es un álgebra de Boole al cumplir los siguientes axiomas:

• 1a: La ley asociativa de la suma:

${\displaystyle \forall a,b,c\in \{0,1\}:\;(a+b)+c=a+(b+c)}$ 

• 1b: La ley asociativa del producto:

${\displaystyle \forall a,b,c\in \{0,1\}:\;(a\cdot b)\cdot c=a\cdot (b\cdot c)}$ 

• 2a: Existencia del elemento neutro para la suma:

${\displaystyle \forall a\in \{0,1\}:\;a+0=a}$ 

• 2b: Existencia del elemento neutro para el producto:

${\displaystyle \forall a\in \{0,1\}:\;a\cdot 1=a}$ 

• 3a: La ley conmutativa de la suma:

${\displaystyle \forall a,b\in \{0,1\}:\;a+b=b+a}$ 

• 3b: La ley conmutativa del producto:

${\displaystyle \forall a,b\in \{0,1\}:\;a\cdot b=b\cdot a}$ 

• 4a: Ley distributiva de la suma respecto al producto:

${\displaystyle \forall a,b,c\in \{0,1\}:\;a+(b\cdot c)=(a+b)\cdot (a+c)}$ 

• 4b: Ley distributiva del producto respecto a la suma:

${\displaystyle \forall a,b,c\in \{0,1\}:\;a\cdot (b+c)=(a\cdot b)+(a\cdot c)}$ 

• 5a: Existe elemento complementario para la suma:

${\displaystyle \forall a\in \{0,1\};\;\exists {\bar {a}}\in \{0,1\}:\;a+{\bar {a}}=1}$ 

• 5b: Existe elemento complementario para el producto:

${\displaystyle \forall a\in \{0,1\};\;\exists {\bar {a}}\in \{0,1\}:\;a\cdot {\bar {a}}=0}$ 

Luego ${\displaystyle (\{0,1\},{\bar {}},+,\cdot )}$  es álgebra de Boole.

Teoremas fundamentales

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

• 6a: Ley de idempotencia para la suma:

${\displaystyle \forall a\in \{0,1\}:\;a+a=a}$ 

• 6b: Ley de idempotencia para el producto:

${\displaystyle \forall a\in \{0,1\}:\;a\cdot a=a}$ 

• 7a: Ley de absorción para la suma:

${\displaystyle \forall a\in \{0,1\}:\;a+1=1}$ 

• 7b: Ley de absorción para el producto:

${\displaystyle \forall a\in \{0,1\}:\;a\cdot 0=0}$ 

• 8a: Ley de identidad para la suma:

${\displaystyle \forall a\in \{0,1\}:\;a+0=a}$ 

• 8b: Ley de identidad para el producto:

${\displaystyle \forall a\in \{0,1\}:\;a\cdot 1=a}$ 

• 9: Ley de involución:

${\displaystyle \forall a\in \{0,1\}:\;{\bar {\bar {a}}}=a}$ 

• 10: Ley del complemento:

${\displaystyle {\bar {1}}=0}$ 

${\displaystyle {\bar {0}}=1}$ 

• 11: Leyes de De Morgan:

${\displaystyle \forall a,b\in \{0,1\}:\;{\overline {a+b}}={\bar {a}}\cdot {\bar {b}}}$ 

${\displaystyle \forall a,b\in \{0,1\}:\;{\overline {a\cdot b}}={\bar {a}}+{\bar {b}}}$ 

Orden en el álgebra de Boole

Partiendo de ${\displaystyle (\{0,1\},{\bar {}},+,\cdot )}$  álgebra de Boole, dadas dos variables binarias: a, b, que cumplen alguna de estas condiciones:

${\displaystyle \left.{\begin{array}{l}a+b=b\\a\cdot b=a\\{\bar {a}}+b=1\\a\cdot {\bar {b}}=0\end{array}}\right\}\longrightarrow \quad a\leq b}$ 

entonces a es menor o igual que b. Dados los valores binarios 0 y 1, podemos ver:

1. ${\displaystyle 0+1=1}$ 
2. ${\displaystyle 0\cdot 1=0}$ 
3. ${\displaystyle {\bar {0}}+1=1}$ 
4. ${\displaystyle 0\cdot {\bar {1}}=0}$ 

Estas cuatro condiciones son equivalentes y el cumplimiento de una de ellas supone el cumplimiento de las otras, en este caso es sencillo comprobarlas todas. Luego podemos decir que 0 antecede a 1 y lo denotamos:

${\displaystyle 0\leq 1}$ 

Si además sabemos que 0 y 1 son valores distintos:

${\displaystyle \left.{\begin{array}{l}0\leq 1\\0\neq 1\end{array}}\right\}\longrightarrow \quad 0<1}$ 

El valor binario 0 es menor que el valor binario 1.

Álgebra de conjuntos

Artículo principal: Álgebra de conjuntos

Artículo principal: Teoría de conjuntos

Artículo principal: Conjunto potencia

Artículo principal: Diagrama de Venn

 

Dado cualquier conjunto U, se llama conjunto potencia de U, al conjunto de todos los subconjuntos posibles de U y lo denotamos ${\displaystyle {\mathcal {P}}(U)}$ .

A título de ejemplo podemos considerar:

${\displaystyle U=\{a,b,c,d,e,f\}\,}$ 

Que tiene como conjunto potencia:

${\displaystyle {\mathcal {P}}(U)={\Big \{}\{\},\{a\},\{b\},\dots ,\{a,b\},\{a,c\},\dots ,\{a,b,c,d,e\},\dots ,U{\Big \}}}$ 

El conjunto vacio es el que no tiene elementos y se representa:

${\displaystyle \{\}\quad \equiv \quad \emptyset \quad \equiv \quad \varnothing }$ 

Podemos definir:

${\displaystyle {\mathfrak {B}}={\mathcal {P}}(U)}$ 

Y como es obvio:

${\displaystyle \varnothing =\varnothing }$ 

${\displaystyle U=U\;}$ 

• La operación unaria interna, que llamaremos complemento:

 

${\displaystyle {\begin{array}{rrcl}{}^{C}:&{\mathcal {P}}(U)&\to &{\mathcal {P}}(U)\\&A&\to &B=A^{C}\end{array}}}$ 

En esta operación definimos una aplicación que, a cada elemento A de P(U), le asigna un B de P(U).

${\displaystyle \forall A\in {\mathcal {P}}(U)\,:\quad \exists !B\in {\mathcal {P}}(U)\;/\quad B=A^{C}}$ 

Para todo elemento A en P(U), se cumple que existe un único B en P(U), tal que B es el complemento A.

Definiendo el complemento de un conjunto así:

${\displaystyle B=A^{C}\longrightarrow \quad \forall x\in B:\quad x\in U\;\land \;x\notin A}$ 

B es el complemento de A, si se cumple que para todo x que pertenezca a B, x pertenece a U y x no pertenece a A.

• La primera operación binaria la llamaremos unión:

 

${\displaystyle {\begin{array}{rrcl}\cup :&{\mathcal {P}}(U)\times {\mathcal {P}}(U)&\to &{\mathcal {P}}(U)\\&(A,B)&\to &C=A\cup B\end{array}}}$ 

Con esta operación binaria interna definimos una aplicación que, a cada par ordenado (A, B) de P(U) por P(U), le asigna un C de P(U).

${\displaystyle \forall (A,B)\in {\mathcal {P}}(U)\times {\mathcal {P}}(U)\,:\quad \exists !C\in {\mathcal {P}}(U)\;/\quad C=A\cup B}$ 

Para todo par ordenado (A,B) en P(U) por P(U), se cumple que existe un único C en P(U), tal que C es la unión A y B.

Definiendo la unión de dos conjuntos como:

${\displaystyle C=A\cup B\longrightarrow \quad \forall x\in C:\quad x\in A\;\lor \;x\in B}$ 

El conjunto C es la unión de A y B, si para todo elemento x de C, se cumple que x es elemento de A o de B

• La segunda operación binaria la llamaremos intersección:

 

${\displaystyle {\begin{array}{rrcl}\cap :&{\mathcal {P}}(U)\times {\mathcal {P}}(U)&\to &{\mathcal {P}}(U)\\&(A,B)&\to &C=A\cap B\end{array}}}$ 

Con lo que definimos una aplicación que, a cada par ordenado (A, B) de P(U) por P(U), le asigna un C de P(U).

${\displaystyle \forall (A,B)\in {\mathcal {P}}(U)\times {\mathcal {P}}(U)\,:\quad \exists !C\in {\mathcal {P}}(U)\;/\quad C=A\cap B}$ 

Para todo par ordenado (A,B) en P(U) por P(U), se cumple que existe un único C en P(U), tal que C es la intersección A y B.

Definiendo la intersección de dos conjuntos como:

${\displaystyle C=A\cap B\longrightarrow \quad \forall x\in C:\quad x\in A\;\land \;x\in B}$ 

El conjunto C es la intersección de A y B, si para todo elemento x de C, se cumple que x es elemento de A y de B.

Axiomas

Con lo que podemos plantear: ${\displaystyle ({\mathcal {P}}(U),{}^{C},\cup ,\cap )}$ , para un U conocido, como álgebra de Boole si cumple las siguientes axiomas:

• 1a: La ley asociativa de la unión:

${\displaystyle \forall A,B,C\in {\mathcal {P}}(U):\;(A\cup B)\cup C=A\cup (B\cup C)}$ 

• 1b: La ley asociativa de la intersección:

${\displaystyle \forall A,B,C\in {\mathcal {P}}(U):\;(A\cap B)\cap C=A\cap (B\cap C)}$ 

• 2a: Existencia del elemento neutro para la unión:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cup \varnothing =A}$ 

• 2b: Existencia del elemento neutro para la intersección:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cap U=A}$ 

• 3a: La ley conmutativa de la unión:

${\displaystyle \forall A,B\in {\mathcal {P}}(U):\;A\cup B=B\cup A}$ 

• 3b: La ley conmutativa de la intersección:

${\displaystyle \forall A,B\in {\mathcal {P}}(U):\;A\cap B=B\cap A}$ 

• 4a: Ley distributiva de la unión respecto de la intersección:

${\displaystyle \forall A,B,C\in {\mathcal {P}}(U):\;A\cup (B\cap C)=(A\cup B)\cap (A\cup C)}$ 

• 4b: Ley distributiva de la intersección respecto a la unión:

${\displaystyle \forall A,B,C\in {\mathcal {P}}(U):\;A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$ 

• 5a: Existe elemento complementario para la unión:

${\displaystyle \forall A\in {\mathcal {P}}(U);\;\exists A^{C}\in {\mathcal {P}}(U):\;A\cup A^{C}=U}$ 

• 5b: Existe elemento complementario para la intersección:

${\displaystyle \forall A\in {\mathcal {P}}(U);\;\exists A^{C}\in {\mathcal {P}}(U):\;A\cap A^{C}=\varnothing }$ 

Concluyendo que ${\displaystyle ({\mathcal {P}}(U),{}^{C},\cup ,\cap )}$  es un álgebra de boole.

Teoremas fundamentales

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

• 6a: Ley de idempotencia para la unión:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cup A=A}$ 

• 6b: Ley de idempotencia para la intersección:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cap A=A}$ 

• 7a: Ley de absorción para la unión:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cup U=U}$ 

• 7b: Ley de absorción para la intersección:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cap \varnothing =\varnothing }$ 

• 8a: Ley de identidad para la unión:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cup \varnothing =A}$ 

• 8b: Ley de identidad para la intersección:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;A\cap U=A}$ 

• 9: Ley de involución:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;{{A}^{C}}^{C}=A}$ 

• 10: Ley del complemento:

${\displaystyle {U}^{C}=\varnothing }$ 

${\displaystyle {\varnothing }^{C}=U}$ 

• 11: Leyes de De Morgan:

${\displaystyle \forall A,B\in {\mathcal {P}}(U):\;{(A\cup B)}^{C}={A}^{C}\cap {B}^{C}}$ 

${\displaystyle \forall a,b\in {\mathcal {P}}(U):\;{(A\cap B)}^{C}={A}^{C}\cup {B}^{C}}$ 

Orden en el álgebra de Boole

Dado ${\displaystyle ({\mathcal {P}}(U),{}^{C},\cup ,\cap )}$  álgebra de Boole, podemos comprobar:

1. ${\displaystyle A\cup B=B}$ 
2. ${\displaystyle A\cap B=A}$ 
3. ${\displaystyle {A}^{C}\cup B=U}$ 
4. ${\displaystyle A\cap {B}^{C}=\varnothing }$ 

Para los conjuntos A y B que cumplen estas propiedades, podemos decir que A antecede a B, que en el caso de conjuntos se diría A es igual o un subconjunto de B y lo denotamos:

${\displaystyle A\subseteq B}$ 

Entendiéndose que A es igual o un subconjunto de B cuando:

 

${\displaystyle A\subseteq B\longrightarrow \quad \forall x\in A:\;x\in B}$ 

El conjunto A es igual o un subconjunto de B, si para todo elemento x que pertenezca a A, x pertenece a B.

También se puede comprobar:

${\displaystyle \forall B\in {\mathcal {P}}(U):\;{\begin{array}{|l}B\cup U=U\\B\cap U=B\\{B}^{C}\cup U=U\\B\cap {U}^{C}=\varnothing \end{array}}\longrightarrow \quad B\subseteq U}$ 

Para todo B de las partes de U, si se cumple que: la unión de B y U es U, la intersección de B y U es B, la unión del complemento de B y U es U, la intersección de B y el complemento de U es el conjunto vacío, entonces B es igual o un subconjunto de U.

Esta conclusión forma parte de la definición de las partes de U, pero se puede llegar a ella por el cumplimiento de una de las cuatro condiciones expuestas, como ya se mencionó, las cuatro condiciones son equivalentes y el cumplimiento de una de ellas implica el cumplimiento de las demás.

Aplicando el mismo razonamiento podemos ver:

${\displaystyle \forall A\in {\mathcal {P}}(U):\;{\begin{array}{|l}\varnothing \cup A=A\\\varnothing \cap A=\varnothing \\{\varnothing }^{C}\cup A=U\\\varnothing \cap {A}^{C}=\varnothing \end{array}}\longrightarrow \quad \varnothing \subseteq A}$ 

Siendo A un conjunto de las partes de U, llegando a la conclusión de que el conjunto vacío es igual o un subconjunto de A.

Lógica proposicional

Artículo principal: Lógica proposicional

Artículo principal: Proposición

Artículo principal: Cálculo lógico

Artículo principal: Lógica matemática

Una proposición, o un predicado, es un valor de verdad que puede expresarse de forma verbal o con expresiones o relaciones matemática o lógica, por ejemplo:

• 'Hoy es miércoles.'
• 'El edificio es alto.'
• 'El perro está ladrando.'

Son proposiciones expresadas verbalmente, y también lo son:

• 'x = 3'
• 'mcd(a, b) = 2n + 1'

Dado que cada una de ellas puede ser verdadera o falsa, las proposiciones suelen designarse con letra:

• p= 'Llueve'
• q= 'Llueve mucho'
• r= 'Llevo paraguas'
• s= 'La calle está mojada'

Las afirmaciones verdadero y falso también son proposiciones, designaremos con: ${\displaystyle {\mathfrak {B}}}$  al conjunto de proposiciones, a fin de ver que la lógica de proposiciones es un álgebra de Boole, además consideraremos:

${\displaystyle \varnothing \longrightarrow \quad \bot =F=falso}$ 

${\displaystyle U\longrightarrow \quad \top =V=verdadero}$ 

• La operación unaria interna, que llamaremos negación:

${\displaystyle {\begin{array}{rrcl}\lnot :&{\mathfrak {B}}&\to &{\mathfrak {B}}\\&a&\to &b=\lnot a\end{array}}}$ 

La operación unaria interna negación, definimos una aplicación que a cada proposición a, le asigna otra poposición b.

${\displaystyle \forall a\in {\mathfrak {B}}\,:\quad \exists !b\in {\mathfrak {B}}\;/\quad b=\lnot {a}}$ 

Para toda proposición a, se cumple que existe una única proposición b, tal que b es la negación de a.

• La primera operación binaria interna, que llamaremos disyunción:

${\displaystyle {\begin{array}{rrcl}\lor :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\lor b\end{array}}}$ 

Con la operación disyunción, definimos una aplicación que a cada par ordenado (a, b) de B por B, le asigna un c de B.

${\displaystyle \forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\lor b}$ 

Para todo par ordenado (a,b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de la disyunción de a y b.

• La segunda operación binaria interna, que llamaremos conjunción:

${\displaystyle {\begin{array}{rrcl}\land :&{\mathfrak {B}}\times {\mathfrak {B}}&\to &{\mathfrak {B}}\\&(a,b)&\to &c=a\land b\end{array}}}$ 

Con la operación conjunción definimos una aplicación que, a cada par ordenado (a, b) de B por B, le asigna un c de B.

${\displaystyle \forall (a,b)\in {\mathfrak {B}}\times {\mathfrak {B}}\,:\quad \exists !c\in {\mathfrak {B}}\;/\quad c=a\land b}$ 

Para todo par ordenado (a, b) en B por B, se cumple que existe un único c en B, tal que c es el resultado de la conjunción de a y b.

Axiomas

Así ${\displaystyle ({\mathfrak {B}},\lnot {},\lor ,\land )}$  es un álgebra de Boole al cumple los siguientes axiomas:

• 1a: La ley asociativa de la disyunción:

${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;(a\lor b)\lor c=a\lor (b\lor c)}$ 

• 1b: La ley asociativa de la conjunción:

${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;(a\land b)\land c=a\land (b\land c)}$ 

• 2a: Existencia del elemento neutro para la disyunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\lor F=a}$ 

• 2b: Existencia del elemento neutro para la conjunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\land V=a}$ 

• 3a: La ley conmutativa de la disyunción:

${\displaystyle \forall a,b\in {\mathfrak {B}}:\;a\lor b=b\lor a}$ 

• 3b: La ley conmutativa de la conjunción:

${\displaystyle \forall a,b\in {\mathfrak {B}}:\;a\land b=b\land a}$ 

• 4a: Ley distributiva de la disyunción respecto a la conjunción:

${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;a\lor (b\land c)=(a\lor b)\land (a\lor c)}$ 

• 4b: Ley distributiva de la conjunción respecto al disyunción:

${\displaystyle \forall a,b,c\in {\mathfrak {B}}:\;a\land (b\lor c)=(a\land b)\lor (a\land c)}$ 

• 5a: Existe elemento complementario para la disyunción:

${\displaystyle \forall a\in {\mathfrak {B}};\;\exists \lnot {a}\in {\mathfrak {B}}:\;a\lor \lnot {a}=V}$ 

• 5b: Existe elemento complementario para la conjunción:

${\displaystyle \forall a\in {\mathfrak {B}};\;\exists \lnot {a}\in {\mathfrak {B}}:\;a\land \lnot {a}=F}$ 

Luego ${\displaystyle ({\mathfrak {B}},\lnot {},\lor ,\land )}$  es álgebra de boole.

Teoremas fundamentales

Partiendo de estos axiomas se puede demostrar los siguientes teoremas:

• 6a: Ley de idempotencia para la disyunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\lor a=a}$ 

• 6b: Ley de idempotencia para la conjunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\land a=a}$ 

• 7a: Ley de absorción para la disyunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\lor V=V}$ 

• 7b: Ley de absorción para la conjunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\land F=F}$ 

• 8a: Ley de identidad para la disyunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\lor F=a}$ 

• 8b: Ley de identidad para la conjunción:

${\displaystyle \forall a\in {\mathfrak {B}}:\;a\land V=a}$ 

• 9: Ley de involución:

${\displaystyle \forall a\in {\mathfrak {B}}:\;\lnot \lnot a=a}$ 

• 10: Ley de complemento:

${\displaystyle \lnot V=F}$ 

${\displaystyle \lnot F=V}$ 

• 11: Leyes de De Morgan:

${\displaystyle \forall a,b\in {\mathfrak {B}}:\;\lnot ({a\lor b})=\lnot {a}\land \lnot {b}}$ 

${\displaystyle \forall a,b\in {\mathfrak {B}}:\;\lnot ({a\land b})=\lnot {a}\lor \lnot {b}}$ 

Orden en el álgebra de Boole

Sabiendo que ${\displaystyle ({\mathfrak {B}},\lnot {},\lor ,\land )}$  es álgebra de Boole, se puede comprobar que:

1. ${\displaystyle a\lor b=b}$ 
2. ${\displaystyle a\land b=a}$ 
3. ${\displaystyle \lnot a\lor b=V}$ 
4. ${\displaystyle a\land \lnot b=F}$ 

Para las proposiciones: a, b que cumplen alguna de estas condiciones se puede afirmar que a antecede a b. Que en el caso de proposiciones o predicados se dice que a es tanto o más fuerte que b, o que b es más débil que a, y lo representamos:

${\displaystyle a\preccurlyeq b}$ 

Así por ejemplo dadas las proposiciones:

• a= Llueve mucho
• b= Llueve

podemos ver:

• ${\displaystyle a\lor b=b}$ 

Si: llueve mucho o llueve entonces llueve.

Si se da la circunstancia de cualesquiera de dos, que llueve mucho o llueve, claramente llueve en cualquier caso.

• ${\displaystyle a\land b=a}$ 

Si: llueve mucho y llueve entonces llueve mucho.

Si afirmamos que llueve mucho y que llueve, y se cumplen las dos circunstancias entonces es que llueve mucho.

• ${\displaystyle \lnot a\lor b=V}$ 

Si: no llueve mucho o llueve es verdadero.

No llueve mucho indica que puede que llueva poco o que no llueva, si no llueve mucho o llueve abarca todas las posibilidades, desde tiempo seco a muy lluvioso, luego la afirmación es verdadera en todo caso.

• ${\displaystyle a\land \lnot b=F}$ 

Si: llueve mucho y no llueve es falso.

Si afirmamos que llueve mucho y simultáneamente que no llueve, la afirmación es claramente falsa.

La afirmación más restrictiva es la más fuerte y la menos restrictiva la más débil, en este caso:

${\displaystyle llueve\;mucho\preccurlyeq llueve}$ 

La proposición llueve mucho es tanto o más fuerte que llueve, la afirmación llueve mucho es un caso particular o el mismo caso de llueve.

Operaciones en álgebra de Boole

Artículo principal: Conectiva lógica

Artículo principal: Operación matemática

El álgebra de Boole se basa en un conjunto en el que se han definidos tres operaciones internas: una unaria y dos binarias, como ya hemos visto, siendo cómoda esta definición. Estrictamente hablando solo son necesarias dos, la unaria y una de las binarias, así, por ejemplo, en la lógica binaria con la negación y el producto podemos definir la suma.

Con la ley de De Morgan:

${\displaystyle \forall a,b\in \{0,1\}:\;{\overline {a+b}}={\bar {a}}\cdot {\bar {b}}\longrightarrow \quad a+b={\overline {{\bar {a}}\cdot {\bar {b}}}}}$ 

Esta expresión resulta más compleja, pero partiendo de la negación y el producto binarios define la suma binaria.

En la imagen de la derecha podemos ver un circuito en paralelo de dos pulsadores a y b, que corresponde a la suma binaria de a y b, y su equivalente en un circuito en serie de a y b, los dos dan como resultado la misma tabla de verdad, y por tanto son equivalentes, lo artificioso el circuito serie para obtener el mismo resultado que en un circuito paralelo deja ver lo conveniente de considerar esa función, la posibilidad de obtener la suma de dos variables binarias mediante la negación y el producto señalan que, de forma primaria, el álgebra de Boole se basa solo en dos operaciones, y que cualquier expresión en la que intervenga la suma puede transformarse en otra equivalente en la que solo intervienen la negación y el producto.

En el caso de la teoría de conjuntos con el complemento y la intersección podemos definir la unión:

${\displaystyle {(A\cup B)}^{C}={A}^{C}\cap {B}^{C}\longrightarrow \quad A\cup B={({A}^{C}\cap {B}^{C})}^{C}}$ 

De una forma similar al álgebra binaria, o cualquier otra álgebra de Boole, La definición del álgebra con solo dos operaciones complica las expresiones, pero permite determinar ciertas relaciones muy útiles, así como otras operaciones distintas.

En el álgebra de Boole definido en un conjunto ${\displaystyle {\mathfrak {B}}}$  las operaciones son internas, dado que parte de elemento de ${\displaystyle {\mathfrak {B}}}$ , para obtener un resultado en ${\displaystyle {\mathfrak {B}}}$ .

Sin perdida de la generalidad, y dado los distintos formas que puede adoptar el álgebra de Boole consideraremos la lógica proposicional con las proposiciones: a, c, b, etc. Que pueden tomar los valores verdadero: V o falso: F. Y las conectivas lógicas sobre esas proposiciones que dan como resultado otras proposiciones lógicas, cada proposición: a, b, c, etc. Define un conjunto A, B, C, etc. Que podemos representar de forma gráfica en un diagrama de Venn.

Podemos ver estas conectivas lógicas para: 0, 1 y 2 variables en un diagrama de Hasse:

Operaciones por el número de argumentos

Si vemos las distintas operaciones por su número de argumentos podemos distinguir:

 

Sin argumentos

Artículo principal: Operación nularia

Las operaciones lógicas sin argumentos son:

Operación nularia
Positiva		Negativa
${\displaystyle \top }$	Tautología	${\displaystyle \bot }$	Contradicción

Con un argumento

Artículo principal: Operación unaria

Las operaciones con solo un argumento son:

Operación unaria
Positiva		Negativa
${\displaystyle a\,}$	Afirmación lógica	${\displaystyle \neg a}$	Negación lógica

Con dos argumentos

Artículo principal: Operación binaria

Las operaciones que necesitan dos argumentos son:

Operación binaria
Positiva		Negativa
${\displaystyle a\lor b}$	Disyunción lógica	${\displaystyle a\downarrow b}$	Disyunción opuesta
${\displaystyle a\land b}$	Conjunción lógica	${\displaystyle a\uparrow b}$	Conjunción opuesta
${\displaystyle a\to b}$	Consecuencia lógica	${\displaystyle a\not \rightarrow b}$	Adjunción lógica
${\displaystyle a\leftarrow b}$	Implicación opuesta	${\displaystyle a\not \leftarrow b}$	Adjunción opuesta
${\displaystyle a\leftrightarrow b}$	Bicondicional	${\displaystyle a\not \leftrightarrow b}$	Disyunción exclusiva

Operaciones nularias

Una operación nularia es la que devuelve un valor sin necesidad de argumentos, podemos ver tautología y contradicción.

${\displaystyle {\begin{array}{|c||c|}\hline &\top \\\hline \hline &V\\\hline \end{array}}}$

La tautología presenta el valor verdadero sin necesidad de argumentos o independientemente de las variables sobre la que se calcule. En teoría de conjuntos corresponde al conjunto universal.

En lógica proposicional corresponde al valor: verdadero:

${\displaystyle {\begin{array}{ccll}\top :&\varnothing &\longrightarrow &\mathbb {U} \\&()&\longrightarrow &a=\top ()\equiv a=V\end{array}}}$ 

En un circuito de conmutación corresponde a una conexión fija o puente cerrado.

${\displaystyle {\begin{array}{|c||c|}\hline &\bot \\\hline \hline &F\\\hline \end{array}}}$

La contradicción, por el contrario, presenta siempre el valor falso, sin necesitar argumentos o independientemente de los argumentos presentados. En teoría de conjuntos corresponde al conjunto vacío.

En lógica proposicional corresponde al valor: falso:

${\displaystyle {\begin{array}{ccll}\bot :&\varnothing &\longrightarrow &\mathbb {U} \\&()&\longrightarrow &a=\bot ()\equiv a=F\end{array}}}$ 

En un circuito de conmutación, corresponde a la no conexión o puente abierto.

Operaciones unarias

Una operación unaria es la que solo necesita un argumento para presentar un resultado, podemos ver dos operaciones unarias: identidad y negación.

${\displaystyle {\begin{array}{|c||c|}\hline a&a\\\hline \hline V&V\\F&F\\\hline \end{array}}}$

La operación identidad de una afirmación presenta el valor de la variación.

${\displaystyle {\begin{array}{ccll}id:&\mathbb {U} &\longrightarrow &\mathbb {U} \\&a&\longrightarrow &b=id(a)\equiv b=a\end{array}}}$ 

Esta operación se puede hacer con el dispositivo electrónico amplificador buffer.

En un circuito de conmutación corresponde a un interruptor normalmente abierto: Interruptor NA.

${\displaystyle {\begin{array}{|c||c|}\hline a&\lnot a\\\hline \hline V&F\\F&V\\\hline \end{array}}}$

La operación negación lógica de una variable presenta el valor contrario del argumento, o los casos contrarios de los recogidos en el argumento.

${\displaystyle {\begin{array}{ccll}\lnot :&\mathbb {U} &\longrightarrow &\mathbb {U} \\&a&\longrightarrow &b=\lnot (a)\equiv b=\lnot a\end{array}}}$ 

Esta operación se hace con la Puerta NOT.

En un circuito de conmutación corresponde a un interruptor normalmente cerrado: Interruptor NC.

Operaciones binarias

La operación binaria es la que necesita dos argumentos, de hecho es la forma más generalizada de operación, normalmente cuando nos referimos a operaciones, nos referimos a operaciones binarias, en el álgebra de Boole podemos ver las siguientes operaciones binarias:

---

${\displaystyle {\begin{array}{|c|c||c|}\hline a&b&a\land b\\\hline \hline V&V&V\\V&F&F\\F&V&F\\F&F&F\\\hline \end{array}}}$

• La Conjunción lógica presenta resultado verdadero solo cuando sus dos argumentos son verdaderos.

${\displaystyle {\begin{array}{ccll}\land :&\mathbb {U} \times \mathbb {U} &\longrightarrow &\mathbb {U} \\&(a,b)&\longrightarrow &c=\land (a,b)\equiv c=a\land b\end{array}}}$ 

Normalmente representado:

${\displaystyle a\land b}$ 

La conjunción lógica de proposiciones es equivalente a la intersección de conjuntos en teoría de conjuntos, o a la puerta lógica AND:

en circuitos de conmutación sería un circuito en serie de interruptores.

---

${\displaystyle {\begin{array}{|c|c||c|}\hline a&b&a\uparrow b\\\hline \hline V&V&F\\V&F&V\\F&V&V\\F&F&V\\\hline \end{array}}}$

• La Conjunción opuesta presenta resultado verdadero en todos los casos excepto cuando sus dos argumentos son verdaderos. Esta operación es la negación de la conjunción.

${\displaystyle a\uparrow b\;=\;\lnot (a\land b)\;=\;\lnot a\lor \lnot b}$ 

La conjunción lógica de proposiciones es equivalente a la puerta lógica NAND.

---

${\displaystyle {\begin{array}{|c|c||c|}\hline a&b&a\lor b\\\hline \hline V&V&V\\V&F&V\\F&V&V\\F&F&F\\\hline \end{array}}}$

• La Disyunción lógica acepta dos argumentos presentando como resultado verdadero si uno u otro de los argumentos es verdadero.

La disyunción puede expresarse:

${\displaystyle a\lor b\;=\;\lnot (\lnot a\land \lnot b)}$ 

La operación disyunción lógica de proposiciones, es equivalente a la unión de conjuntos en teoría de conjuntos, a la puerta lógica OR:

y al circuito en paralelo en circuitos de conmutación

---

${\displaystyle {\begin{array}{|c|c||c|}\hline a&b&a\downarrow b\\\hline \hline V&V&F\\V&F&F\\F&V&F\\F&F&V\\\hline \end{array}}}$

• La Disyunción opuesta presenta resultado verdadero solo cuando sus dos argumentos son falsos. Esta operación es la negación de la disyunción.

${\displaystyle a\downarrow b\;=\;\lnot (a\lor b)\;=\;\lnot a\land \lnot b}$ 

La negación conjunta de proposiciones es equivalente a la puerta lógica NOR.

---

${\displaystyle {\begin{array}{|c|c||c|}\hline a&b&a\to b\\\hline \hline V&V&V\\V&F&F\\F&V&V\\F&F&V\\\hline \end{array}}}$

Septiembre 02, 2021 Últimos artículos Enero 01, 1970 Menufia Enero 01, 1970 Menzoberranzan Enero 01, 1970 Menájem Beguin Enero 01, 1970 Menétru-le-Vignoble Enero 01, 1970 Menú (programa de televisión) Enero 01, 1970 Menú Inicio Enero 01, 1970 Meowth Enero 01, 1970 Mephisto (cómic) Enero 01, 1970 Mequinez Enero 01, 1970 Mercator (obra) Más leído Enero 01, 1970 Imperio mongol Enero 01, 1970 Imperio purépecha Enero 01, 1970 Imperio safávida Enero 01, 1970 Imperios Centrales Enero 01, 1970 Impero Álgebra, boole, álgebra, boole, también, llamada, álgebra, booleana, electrónica, digital, informática, matemática, estructura, algebraica, esquematiza, operaciones, lógicas, Índice, historia, definición, principio, axiomas, necesarios, teoremas, fundamentales. El algebra de Boole tambien llamada algebra booleana en electronica digital informatica y matematica es una estructura algebraica que esquematiza las operaciones logicas Indice 1 Historia 2 Definicion 3 Principio 3 1 Axiomas necesarios 3 2 Teoremas fundamentales 3 3 Orden en el algebra de Boole 3 4 Principio de dualidad 4 Otras formas de notacion del algebra de Boole 5 Estructuras algebraicas que son algebra de Boole 5 1 Logica binaria 5 1 1 Axiomas 5 1 2 Teoremas fundamentales 5 1 3 Orden en el algebra de Boole 5 2 Algebra de conjuntos 5 2 1 Axiomas 5 2 2 Teoremas fundamentales 5 2 3 Orden en el algebra de Boole 5 3 Logica proposicional 5 3 1 Axiomas 5 3 2 Teoremas fundamentales 5 3 3 Orden en el algebra de Boole 6 Operaciones en algebra de Boole 6 1 Operaciones por el numero de argumentos 6 1 1 Sin argumentos 6 1 2 Con un argumento 6 1 3 Con dos argumentos 6 2 Operaciones nularias 6 3 Operaciones unarias 6 4 Operaciones binarias 7 Formula de Boole bien formada 7 1 Jerarquia de los operadores 8 Vease tambien 9 Referencias 9 1 Bibliografia 9 2 Enlaces externosHistoria Editar Se denomina asi en honor a George Boole 02 de noviembre de 1815 a 8 de diciembre de 1864 matematico ingles autodidacta que fue el primero en definirla como parte de un sistema logico inicialmente en un pequeno folleto The Mathematical Analysis of Logic 1 publicado en 1847 en respuesta a una controversia en curso entre Augustus De Morgan y sir William Rowan Hamilton El algebra de Boole fue un intento de utilizar las tecnicas algebraicas para tratar expresiones de la logica proposicional Mas tarde fue extendido como un libro mas importante An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities tambien conocido como An Investigation of the Laws of Thought 2 o simplemente The Laws of Thought 3 publicado en 1854 Las interpretaciones respectivas de los simbolos 0 y 1 en el sistema de logica son Nada y Universo George Boole 4 En la actualidad el algebra de Boole se aplica de forma generalizada en el ambito del diseno electronico Claude Shannon fue el primero en aplicarla en el diseno de circuitos de conmutacion electrica biestables en 1948 Esta logica se puede aplicar a dos campos Al analisis porque es una forma concreta de describir como funcionan los circuitos Al diseno ya que teniendo una funcion se aplica dicha algebra para poder desarrollar una implementacion de la funcion Definicion EditarDado un conjunto B displaystyle mathfrak B en el que se han definido dos leyes de composicion interna displaystyle oplus odot La estructura B displaystyle mathfrak B oplus odot es un algebra de Boole si y solo si B displaystyle mathfrak B oplus odot es un Reticulo distributivo 5 esto es displaystyle odot es distributiva respecto a displaystyle oplus a b c a b a c displaystyle a odot b oplus c a odot b oplus a odot c dd displaystyle oplus es distributiva respecto a displaystyle odot a b c a b a c displaystyle a oplus b odot c a oplus b odot a oplus c dd Basandose en esta definicion se determina el siguiente Principio EditarDado un conjunto B displaystyle mathfrak B formado cuando menos por los elementos U displaystyle varnothing U en el que se ha definido Una operacion unaria interna que llamaremos complemento B B a b a displaystyle begin array rrcl sim amp mathfrak B amp to amp mathfrak B amp a amp to amp b sim a end array En esta operacion definimos una aplicacion que a cada elemento a de B le asigna un b de B a B b B b a displaystyle forall a in mathfrak B quad exists b in mathfrak B quad b sim a Para todo elemento a en B se cumple que existe un unico b en B tal que b es el complemento de a La operacion binaria interna que llamaremos suma B B B a b c a b displaystyle begin array rrcl oplus amp mathfrak B times mathfrak B amp to amp mathfrak B amp a b amp to amp c a oplus b end array por la que definimos una aplicacion que a cada par ordenado a b de B por B le asigna un c de B a b B B c B c a b displaystyle forall a b in mathfrak B times mathfrak B quad exists c in mathfrak B quad c a oplus b Para todo par ordenado a b en B por B se cumple que existe un unico c en B tal que c es el resultado de sumar a con b La operacion binaria interna que llamaremos producto B B B a b c a b displaystyle begin array rrcl odot amp mathfrak B times mathfrak B amp to amp mathfrak B amp a b amp to amp c a odot b end array Con lo que definimos una aplicacion que a cada par ordenado a b de B por B le asigna un c de B a b B B c B c a b displaystyle forall a b in mathfrak B times mathfrak B quad exists c in mathfrak B quad c a odot b Para todo par ordenado a b en B por B se cumple que existe un unico c en B tal que c es el resultado del producto a y b Dada la definicion del algebra de Boole como una estructura algebraica generica segun el caso concreto de que se trate la simbologia y los nombres de las operaciones pueden variar Axiomas necesarios Editar Diremos que este conjunto y las operaciones asi definidas B displaystyle mathfrak B sim oplus odot son un algebra de boole si cumple las siguientes axiomas 1a La ley asociativa de la suma a b c B a b c a b c displaystyle forall a b c in mathfrak B a oplus b oplus c a oplus b oplus c dd 2a Existencia del elemento neutro para la suma a B a a displaystyle forall a in mathfrak B a oplus varnothing a dd 3a La ley conmutativa de la suma a b B a b b a displaystyle forall a b in mathfrak B a oplus b b oplus a dd 4a Ley distributiva de la suma respecto al producto a b c B a b c a b a c displaystyle forall a b c in mathfrak B a oplus b odot c a oplus b odot a oplus c dd 5a Existe elemento complementario para la suma a B a B a a U displaystyle forall a in mathfrak B exists sim a in mathfrak B a oplus sim a U dd 1b La ley asociativa del producto a b c B a b c a b c displaystyle forall a b c in mathfrak B a odot b odot c a odot b odot c dd 2b Existencia del elemento neutro para el producto a B a U a displaystyle forall a in mathfrak B a odot U a dd 3b La ley conmutativa del producto a b B a b b a displaystyle forall a b in mathfrak B a odot b b odot a dd 4b Ley distributiva del producto respecto a la suma a b c B a b c a b a c displaystyle forall a b c in mathfrak B a odot b oplus c a odot b oplus a odot c dd 5b Existe elemento complementario para el producto a B a B a a displaystyle forall a in mathfrak B exists sim a in mathfrak B a odot sim a varnothing dd Teoremas fundamentales Editar Partiendo de los cinco axiomas anteriores se pueden deducir y demostrar los siguientes teoremas fundamentales 6a Ley de idempotencia para la suma a B a a a displaystyle forall a in mathfrak B a oplus a a dd 7a Ley de absorcion para la suma a B a U U displaystyle forall a in mathfrak B a oplus U U dd 8a Ley de identidad para la suma a B a a displaystyle forall a in mathfrak B a oplus varnothing a dd 6b Ley de idempotencia para el producto a B a a a displaystyle forall a in mathfrak B a odot a a dd 7b Ley de absorcion para el producto a B a displaystyle forall a in mathfrak B a odot varnothing varnothing dd 8b Ley de identidad para el producto a B a U a displaystyle forall a in mathfrak B a odot U a dd 9 Ley de involucion a B a a displaystyle forall a in mathfrak B sim sim a a dd 10 Ley del complemento U U displaystyle sim U varnothing quad sim varnothing U dd 11 Leyes de De Morgan a b B a b a b displaystyle forall a b in mathfrak B sim a oplus b sim a odot sim b dd a b B a b a b displaystyle forall a b in mathfrak B sim a odot b sim a oplus sim b dd Orden en el algebra de Boole Editar Sea B displaystyle mathfrak B sim oplus odot un algebra de Boole sean a b dos elementos del conjunto podremos decir entonces que a antecede a b y lo denotamos a b displaystyle a preceq b si se cumple alguna de las siguientes condiciones a b b displaystyle a oplus b b a b a displaystyle a odot b a a b U displaystyle sim a oplus b U a b displaystyle a odot sim b varnothing Estas cuatro condiciones se consideran equivalentes y el cumplimiento de una de ellas implica necesariamente el cumplimiento de las demas Definiendo un conjunto parcialmente ordenado Si se cumple que a b B a b b a a b c o m p a r a b l e s displaystyle a b in mathfrak B quad a preceq b lor b preceq a quad longrightarrow quad a b rightarrow mathit comparables Para los valores a b de B displaystyle mathfrak B que cumplen que a antecede a b o que b antecede a a se dice que a y b son comparables Si se cumple que a b B a b b a a b n o c o m p a r a b l e s displaystyle a b in mathfrak B quad a npreceq b land b npreceq a quad longrightarrow quad a b rightarrow mathit no comparables Para los valores a b de B displaystyle mathfrak B que cumplen que a no antecede a b y que b no antecede a a se dice que a y b son no comparables Principio de dualidad Editar El concepto de dualidad permite formalizar este hecho a toda relacion o ley logica le correspondera su dual formada mediante el intercambio de los operadores suma con los de producto y de los U displaystyle U con los displaystyle varnothing Adicion Producto1 a a U displaystyle a oplus sim a U a a displaystyle a odot sim a varnothing 2 a a displaystyle a oplus varnothing a a U a displaystyle a odot U a 3 a U U displaystyle a oplus U U a displaystyle a odot varnothing varnothing 4 a a a displaystyle a oplus a a a a a displaystyle a odot a a 5 a b b a displaystyle a oplus b b oplus a a b b a displaystyle a odot b b odot a 6 a b c a b c displaystyle a oplus b oplus c a oplus b oplus c a b c a b c displaystyle a odot b odot c a odot b odot c 7 a b c a b a c displaystyle a oplus b odot c a oplus b odot a oplus c a b c a b a c displaystyle a odot b oplus c a odot b oplus a odot c 8 a a b a displaystyle a oplus a odot b a a a b a displaystyle a odot a oplus b a 9 a b a b displaystyle sim a oplus b sim a odot sim b a b a b displaystyle sim a odot b sim a oplus sim b Otras formas de notacion del algebra de Boole EditarEn Logica binaria se suele emplear la notacion 0 1 displaystyle 0 1 bar cdot comun en la tecnologia digital siendo la forma mas usual y la mas comoda de representar Por ejemplo las leyes de De Morgan se representan asi a b a b displaystyle overline a b bar a cdot bar b a b a b displaystyle overline a cdot b bar a bar b Cuando el algebra de Boole se emplea en electronica suele emplearse la misma denominacion que para las puerta logica AND Y OR O y NOT NO ampliandose en ocasiones con X OR O exclusiva y su negadas NAND NO Y NOR NO O y X NOR equivalencia las variables pueden representarse con letras mayusculas o minusculas y pueden tomar los valores 0 1 Empleando esta notacion las leyes de De Morgan se representan NOT a OR b NOT a AND NOT b displaystyle mbox NOT a mbox OR b mbox NOT a mbox AND mbox NOT b NOT a AND b NOT a OR NOT b displaystyle mbox NOT a mbox AND b mbox NOT a mbox OR mbox NOT b En su aplicacion a la logica se emplea la notacion displaystyle land lor lnot y las variables pueden tomar los valores F V falso o verdadero equivalentes a 0 1 Con la notacion logica las leyes de De Morgan serian asi a b a b displaystyle lnot a lor b lnot a land lnot b a b a b displaystyle lnot a land b lnot a lor lnot b En el formato de Teoria de conjuntos el Algebra de Boole toma el aspecto P U displaystyle mathcal P U sim cup cap En esta notacion las leyes de De Morgan serian asi a b a b displaystyle sim a cup b sim a cap sim b a b a b displaystyle sim a cap b sim a cup sim b Otra forma en la algebra de conjuntos del Algebra de Boole las leyes de De Morgan serian asi A B C A C B C displaystyle A cup B C A C cap B C A B C A C B C displaystyle A cap B C A C cup B C Desde el punto de vista practico existe una forma simplificada de representar expresiones booleanas Se emplean apostrofos para indicar la negacion la operacion suma se representa de la forma normal en algebra y para el producto no se emplea ningun signo las variables se representan normalmente con una letra mayuscula la sucesion de dos variables indica el producto entre ellas no una variable nombrada con dos letras La representacion de las leyes de De Morgan con este sistema quedaria asi con letra minusculas para las variables a b a b displaystyle a b a b a b a b displaystyle ab a b y asi empleando letras mayusculas para representar las variables A B A B displaystyle A B A B A B A B displaystyle AB A B Todas estas formas de representacion son correctas se utilizan de hecho y pueden verse al consultar bibliografia La utilizacion de una u otra notacion no modifica el algebra de Boole solo su aspecto y depende de la rama de las matematicas o la tecnologia en la que se este utilizando para emplear una u otra notacion Estructuras algebraicas que son algebra de Boole EditarHay numerosos casos de distintos analisis de estructuras algebraicas que corresponden al algebra de Boole aunque en apariencia son muy diferentes su estructura es la misma Vamos a ver algunos de ellos con el proposito de hacer palpable las similitudes en la estructura y los distintos ambitos de aplicacion y distinta terminologia para referirse a las operaciones o a las variables Logica binaria Editar Articulo principal Logica binaria Articulo principal Sistema digital Articulo principal Sistema binario Articulo principal Tabla de verdad Articulo principal Sistema combinacional Articulo principal Formas canonicas algebra de Boole Articulo principal Circuito de conmutacion Una serie de temas aparentemente tan distintos tiene dos cosas en comun la logica binaria basada en los ceros y los unos y el algebra de Boole posiblemente la forma mas conocida de esta algebra que en ocasiones da lugar a la interpretacion que el algebra de Boole es la logica binaria exclusivamente asi el conjunto B displaystyle mathfrak B en este caso esta formado por dos elementos 0 1 o F V o no si dos valores contrapuestos que son las dos posibles alternativas entre dos situaciones posibles aqui sin perdida de la generalidad tomaremos el conjunto 0 1 como ya hemos dicho B 0 1 displaystyle mathfrak B 0 1 Donde 0 displaystyle varnothing 0 U 1 displaystyle U 1 La operacion unaria interna que llamaremos negacion a a 0 1 1 0 displaystyle begin array c c a amp bar a hline 0 amp 1 1 amp 0 end array B B a b a displaystyle begin array rrcl bar amp mathfrak B amp to amp mathfrak B amp a amp to amp b bar a end array La operacion unaria interna negacion definimos una aplicacion que a cada elemento a de 0 1 le asigna un b de 0 1 a B b B b a displaystyle forall a in mathfrak B quad exists b in mathfrak B quad b bar a Para todo elemento a en 0 1 se cumple que existe un unico b en 0 1 tal que b es la negacion de a Como se ve en la tabla La operacion binaria interna que llamaremos suma a b a b 1 1 1 1 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 displaystyle begin array cc c a amp b amp a b hline 1 amp 1 amp 1 1 amp 0 amp 1 0 amp 1 amp 1 0 amp 0 amp 0 end array quad longleftrightarrow quad begin array c cc 0 amp 1 amp 0 1 amp 1 amp 1 hline amp 1 amp 0 end array B B B a b c a b displaystyle begin array rrcl amp mathfrak B times mathfrak B amp to amp mathfrak B amp a b amp to amp c a b end array Con la operacion suma definimos una aplicacion que a cada par ordenado a b de B por B le asigna un c de B a b B B c B c a b displaystyle forall a b in mathfrak B times mathfrak B quad exists c in mathfrak B quad c a b Para todo par ordenado a b en B por B se cumple que existe un unico c en B tal que c es el resultado de sumar a con b la operacion binaria interna que llamaremos producto a b a b 1 1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 0 1 0 displaystyle begin array cc c a amp b amp a cdot b hline 1 amp 1 amp 1 1 amp 0 amp 0 0 amp 1 amp 0 0 amp 0 amp 0 end array quad longleftrightarrow quad begin array c cc 0 amp 0 amp 0 1 amp 1 amp 0 hline cdot amp 1 amp 0 end array B B B a b c a b displaystyle begin array rrcl cdot amp mathfrak B times mathfrak B amp to amp mathfrak B amp a b amp to amp c a cdot b end array Con la operacion producto definimos una aplicacion que a cada par ordenado a b de B por B le asigna un c de B a b B B c B c a b displaystyle forall a b in mathfrak B times mathfrak B quad exists c in mathfrak B quad c a cdot b Para todo par ordenado a b en B por B se cumple que existe un unico c en B tal que c es el resultado del producto a y b Como se puede ver en la tabla Axiomas Editar Asi 0 1 displaystyle 0 1 bar cdot es un algebra de Boole al cumplir los siguientes axiomas 1a La ley asociativa de la suma a b c 0 1 a b c a b c displaystyle forall a b c in 0 1 a b c a b c dd 1b La ley asociativa del producto a b c 0 1 a b c a b c displaystyle forall a b c in 0 1 a cdot b cdot c a cdot b cdot c dd 2a Existencia del elemento neutro para la suma a 0 1 a 0 a displaystyle forall a in 0 1 a 0 a dd 2b Existencia del elemento neutro para el producto a 0 1 a 1 a displaystyle forall a in 0 1 a cdot 1 a dd 3a La ley conmutativa de la suma a b 0 1 a b b a displaystyle forall a b in 0 1 a b b a dd 3b La ley conmutativa del producto a b 0 1 a b b a displaystyle forall a b in 0 1 a cdot b b cdot a dd 4a Ley distributiva de la suma respecto al producto a b c 0 1 a b c a b a c displaystyle forall a b c in 0 1 a b cdot c a b cdot a c dd 4b Ley distributiva del producto respecto a la suma a b c 0 1 a b c a b a c displaystyle forall a b c in 0 1 a cdot b c a cdot b a cdot c dd 5a Existe elemento complementario para la suma a 0 1 a 0 1 a a 1 displaystyle forall a in 0 1 exists bar a in 0 1 a bar a 1 dd 5b Existe elemento complementario para el producto a 0 1 a 0 1 a a 0 displaystyle forall a in 0 1 exists bar a in 0 1 a cdot bar a 0 dd Luego 0 1 displaystyle 0 1 bar cdot es algebra de Boole Teoremas fundamentales Editar Partiendo de estos axiomas se puede demostrar los siguientes teoremas 6a Ley de idempotencia para la suma a 0 1 a a a displaystyle forall a in 0 1 a a a dd 6b Ley de idempotencia para el producto a 0 1 a a a displaystyle forall a in 0 1 a cdot a a dd 7a Ley de absorcion para la suma a 0 1 a 1 1 displaystyle forall a in 0 1 a 1 1 dd 7b Ley de absorcion para el producto a 0 1 a 0 0 displaystyle forall a in 0 1 a cdot 0 0 dd 8a Ley de identidad para la suma a 0 1 a 0 a displaystyle forall a in 0 1 a 0 a dd 8b Ley de identidad para el producto a 0 1 a 1 a displaystyle forall a in 0 1 a cdot 1 a dd 9 Ley de involucion a 0 1 a a displaystyle forall a in 0 1 bar bar a a dd 10 Ley del complemento 1 0 displaystyle bar 1 0 dd 0 1 displaystyle bar 0 1 dd 11 Leyes de De Morgan a b 0 1 a b a b displaystyle forall a b in 0 1 overline a b bar a cdot bar b dd a b 0 1 a b a b displaystyle forall a b in 0 1 overline a cdot b bar a bar b dd Orden en el algebra de Boole Editar Partiendo de 0 1 displaystyle 0 1 bar cdot algebra de Boole dadas dos variables binarias a b que cumplen alguna de estas condiciones a b b a b a a b 1 a b 0 a b displaystyle left begin array l a b b a cdot b a bar a b 1 a cdot bar b 0 end array right longrightarrow quad a leq b entonces a es menor o igual que b Dados los valores binarios 0 y 1 podemos ver 0 1 1 displaystyle 0 1 1 0 1 0 displaystyle 0 cdot 1 0 0 1 1 displaystyle bar 0 1 1 0 1 0 displaystyle 0 cdot bar 1 0 Estas cuatro condiciones son equivalentes y el cumplimiento de una de ellas supone el cumplimiento de las otras en este caso es sencillo comprobarlas todas Luego podemos decir que 0 antecede a 1 y lo denotamos 0 1 displaystyle 0 leq 1 Si ademas sabemos que 0 y 1 son valores distintos 0 1 0 1 0 lt 1 displaystyle left begin array l 0 leq 1 0 neq 1 end array right longrightarrow quad 0 lt 1 El valor binario 0 es menor que el valor binario 1 Algebra de conjuntos Editar Articulo principal Algebra de conjuntos Articulo principal Teoria de conjuntos Articulo principal Conjunto potencia Articulo principal Diagrama de Venn Dado cualquier conjunto U se llama conjunto potencia de U al conjunto de todos los subconjuntos posibles de U y lo denotamos P U displaystyle mathcal P U A titulo de ejemplo podemos considerar U a b c d e f displaystyle U a b c d e f Que tiene como conjunto potencia P U a b a b a c a b c d e U displaystyle mathcal P U Big a b dots a b a c dots a b c d e dots U Big El conjunto vacio es el que no tiene elementos y se representa displaystyle quad equiv quad emptyset quad equiv quad varnothing Podemos definir B P U displaystyle mathfrak B mathcal P U Y como es obvio displaystyle varnothing varnothing U U displaystyle U U La operacion unaria interna que llamaremos complemento C P U P U A B A C displaystyle begin array rrcl C amp mathcal P U amp to amp mathcal P U amp A amp to amp B A C end array En esta operacion definimos una aplicacion que a cada elemento A de P U le asigna un B de P U A P U B P U B A C displaystyle forall A in mathcal P U quad exists B in mathcal P U quad B A C Para todo elemento A en P U se cumple que existe un unico B en P U tal que B es el complemento A Definiendo el complemento de un conjunto asi B A C x B x U x A displaystyle B A C longrightarrow quad forall x in B quad x in U land x notin A B es el complemento de A si se cumple que para todo x que pertenezca a B x pertenece a U y x no pertenece a A La primera operacion binaria la llamaremos union P U P U P U A B C A B displaystyle begin array rrcl cup amp mathcal P U times mathcal P U amp to amp mathcal P U amp A B amp to amp C A cup B end array Con esta operacion binaria interna definimos una aplicacion que a cada par ordenado A B de P U por P U le asigna un C de P U A B P U P U C P U C A B displaystyle forall A B in mathcal P U times mathcal P U quad exists C in mathcal P U quad C A cup B Para todo par ordenado A B en P U por P U se cumple que existe un unico C en P U tal que C es la union A y B Definiendo la union de dos conjuntos como C A B x C x A x B displaystyle C A cup B longrightarrow quad forall x in C quad x in A lor x in B El conjunto C es la union de A y B si para todo elemento x de C se cumple que x es elemento de A o de B La segunda operacion binaria la llamaremos interseccion P U P U P U A B C A B displaystyle begin array rrcl cap amp mathcal P U times mathcal P U amp to amp mathcal P U amp A B amp to amp C A cap B end array Con lo que definimos una aplicacion que a cada par ordenado A B de P U por P U le asigna un C de P U A B P U P U C P U C A B displaystyle forall A B in mathcal P U times mathcal P U quad exists C in mathcal P U quad C A cap B Para todo par ordenado A B en P U por P U se cumple que existe un unico C en P U tal que C es la interseccion A y B Definiendo la interseccion de dos conjuntos como C A B x C x A x B displaystyle C A cap B longrightarrow quad forall x in C quad x in A land x in B El conjunto C es la interseccion de A y B si para todo elemento x de C se cumple que x es elemento de A y de B Axiomas Editar Con lo que podemos plantear P U C displaystyle mathcal P U C cup cap para un U conocido como algebra de Boole si cumple las siguientes axiomas 1a La ley asociativa de la union A B C P U A B C A B C displaystyle forall A B C in mathcal P U A cup B cup C A cup B cup C dd 1b La ley asociativa de la interseccion A B C P U A B C A B C displaystyle forall A B C in mathcal P U A cap B cap C A cap B cap C dd 2a Existencia del elemento neutro para la union A P U A A displaystyle forall A in mathcal P U A cup varnothing A dd 2b Existencia del elemento neutro para la interseccion A P U A U A displaystyle forall A in mathcal P U A cap U A dd 3a La ley conmutativa de la union A B P U A B B A displaystyle forall A B in mathcal P U A cup B B cup A dd 3b La ley conmutativa de la interseccion A B P U A B B A displaystyle forall A B in mathcal P U A cap B B cap A dd 4a Ley distributiva de la union respecto de la interseccion A B C P U A B C A B A C displaystyle forall A B C in mathcal P U A cup B cap C A cup B cap A cup C dd 4b Ley distributiva de la interseccion respecto a la union A B C P U A B C A B A C displaystyle forall A B C in mathcal P U A cap B cup C A cap B cup A cap C dd 5a Existe elemento complementario para la union A P U A C P U A A C U displaystyle forall A in mathcal P U exists A C in mathcal P U A cup A C U dd 5b Existe elemento complementario para la interseccion A P U A C P U A A C displaystyle forall A in mathcal P U exists A C in mathcal P U A cap A C varnothing dd Concluyendo que P U C displaystyle mathcal P U C cup cap es un algebra de boole Teoremas fundamentales Editar Partiendo de estos axiomas se puede demostrar los siguientes teoremas 6a Ley de idempotencia para la union A P U A A A displaystyle forall A in mathcal P U A cup A A dd 6b Ley de idempotencia para la interseccion A P U A A A displaystyle forall A in mathcal P U A cap A A dd 7a Ley de absorcion para la union A P U A U U displaystyle forall A in mathcal P U A cup U U dd 7b Ley de absorcion para la interseccion A P U A displaystyle forall A in mathcal P U A cap varnothing varnothing dd 8a Ley de identidad para la union A P U A A displaystyle forall A in mathcal P U A cup varnothing A dd 8b Ley de identidad para la interseccion A P U A U A displaystyle forall A in mathcal P U A cap U A dd 9 Ley de involucion A P U A C C A displaystyle forall A in mathcal P U A C C A dd 10 Ley del complemento U C displaystyle U C varnothing dd C U displaystyle varnothing C U dd 11 Leyes de De Morgan A B P U A B C A C B C displaystyle forall A B in mathcal P U A cup B C A C cap B C dd a b P U A B C A C B C displaystyle forall a b in mathcal P U A cap B C A C cup B C dd Orden en el algebra de Boole Editar Dado P U C displaystyle mathcal P U C cup cap algebra de Boole podemos comprobar A B B displaystyle A cup B B A B A displaystyle A cap B A A C B U displaystyle A C cup B U A B C displaystyle A cap B C varnothing Para los conjuntos A y B que cumplen estas propiedades podemos decir que A antecede a B que en el caso de conjuntos se diria A es igual o un subconjunto de B y lo denotamos A B displaystyle A subseteq B Entendiendose que A es igual o un subconjunto de B cuando A B x A x B displaystyle A subseteq B longrightarrow quad forall x in A x in B El conjunto A es igual o un subconjunto de B si para todo elemento x que pertenezca a A x pertenece a B Tambien se puede comprobar B P U B U U B U B B C U U B U C B U displaystyle forall B in mathcal P U begin array l B cup U U B cap U B B C cup U U B cap U C varnothing end array longrightarrow quad B subseteq U Para todo B de las partes de U si se cumple que la union de B y U es U la interseccion de B y U es B la union del complemento de B y U es U la interseccion de B y el complemento de U es el conjunto vacio entonces B es igual o un subconjunto de U Esta conclusion forma parte de la definicion de las partes de U pero se puede llegar a ella por el cumplimiento de una de las cuatro condiciones expuestas como ya se menciono las cuatro condiciones son equivalentes y el cumplimiento de una de ellas implica el cumplimiento de las demas Aplicando el mismo razonamiento podemos ver A P U A A A C A U A C A displaystyle forall A in mathcal P U begin array l varnothing cup A A varnothing cap A varnothing varnothing C cup A U varnothing cap A C varnothing end array longrightarrow quad varnothing subseteq A Siendo A un conjunto de las partes de U llegando a la conclusion de que el conjunto vacio es igual o un subconjunto de A Logica proposicional Editar Articulo principal Logica proposicional Articulo principal Proposicion Articulo principal Calculo logico Articulo principal Logica matematica Una proposicion o un predicado es un valor de verdad que puede expresarse de forma verbal o con expresiones o relaciones matematica o logica por ejemplo Hoy es miercoles El edificio es alto El perro esta ladrando Son proposiciones expresadas verbalmente y tambien lo son x 3 mcd a b 2n 1 Dado que cada una de ellas puede ser verdadera o falsa las proposiciones suelen designarse con letra p Llueve q Llueve mucho r Llevo paraguas s La calle esta mojada Las afirmaciones verdadero y falso tambien son proposiciones designaremos con B displaystyle mathfrak B al conjunto de proposiciones a fin de ver que la logica de proposiciones es un algebra de Boole ademas consideraremos F f a l s o displaystyle varnothing longrightarrow quad bot F falso U V v e r d a d e r o displaystyle U longrightarrow quad top V verdadero La operacion unaria interna que llamaremos negacion B B a b a displaystyle begin array rrcl lnot amp mathfrak B amp to amp mathfrak B amp a amp to amp b lnot a end array La operacion unaria interna negacion definimos una aplicacion que a cada proposicion a le asigna otra poposicion b a B b B b a displaystyle forall a in mathfrak B quad exists b in mathfrak B quad b lnot a Para toda proposicion a se cumple que existe una unica proposicion b tal que b es la negacion de a La primera operacion binaria interna que llamaremos disyuncion B B B a b c a b displaystyle begin array rrcl lor amp mathfrak B times mathfrak B amp to amp mathfrak B amp a b amp to amp c a lor b end array Con la operacion disyuncion definimos una aplicacion que a cada par ordenado a b de B por B le asigna un c de B a b B B c B c a b displaystyle forall a b in mathfrak B times mathfrak B quad exists c in mathfrak B quad c a lor b Para todo par ordenado a b en B por B se cumple que existe un unico c en B tal que c es el resultado de la disyuncion de a y b La segunda operacion binaria interna que llamaremos conjuncion B B B a b c a b displaystyle begin array rrcl land amp mathfrak B times mathfrak B amp to amp mathfrak B amp a b amp to amp c a land b end array Con la operacion conjuncion definimos una aplicacion que a cada par ordenado a b de B por B le asigna un c de B a b B B c B c a b displaystyle forall a b in mathfrak B times mathfrak B quad exists c in mathfrak B quad c a land b Para todo par ordenado a b en B por B se cumple que existe un unico c en B tal que c es el resultado de la conjuncion de a y b Axiomas Editar Asi B displaystyle mathfrak B lnot lor land es un algebra de Boole al cumple los siguientes axiomas 1a La ley asociativa de la disyuncion a b c B a b c a b c displaystyle forall a b c in mathfrak B a lor b lor c a lor b lor c dd 1b La ley asociativa de la conjuncion a b c B a b c a b c displaystyle forall a b c in mathfrak B a land b land c a land b land c dd 2a Existencia del elemento neutro para la disyuncion a B a F a displaystyle forall a in mathfrak B a lor F a dd 2b Existencia del elemento neutro para la conjuncion a B a V a displaystyle forall a in mathfrak B a land V a dd 3a La ley conmutativa de la disyuncion a b B a b b a displaystyle forall a b in mathfrak B a lor b b lor a dd 3b La ley conmutativa de la conjuncion a b B a b b a displaystyle forall a b in mathfrak B a land b b land a dd 4a Ley distributiva de la disyuncion respecto a la conjuncion a b c B a b c a b a c displaystyle forall a b c in mathfrak B a lor b land c a lor b land a lor c dd 4b Ley distributiva de la conjuncion respecto al disyuncion a b c B a b c a b a c displaystyle forall a b c in mathfrak B a land b lor c a land b lor a land c dd 5a Existe elemento complementario para la disyuncion a B a B a a V displaystyle forall a in mathfrak B exists lnot a in mathfrak B a lor lnot a V dd 5b Existe elemento complementario para la conjuncion a B a B a a F displaystyle forall a in mathfrak B exists lnot a in mathfrak B a land lnot a F dd Luego B displaystyle mathfrak B lnot lor land es algebra de boole Teoremas fundamentales Editar Partiendo de estos axiomas se puede demostrar los siguientes teoremas 6a Ley de idempotencia para la disyuncion a B a a a displaystyle forall a in mathfrak B a lor a a dd 6b Ley de idempotencia para la conjuncion a B a a a displaystyle forall a in mathfrak B a land a a dd 7a Ley de absorcion para la disyuncion a B a V V displaystyle forall a in mathfrak B a lor V V dd 7b Ley de absorcion para la conjuncion a B a F F displaystyle forall a in mathfrak B a land F F dd 8a Ley de identidad para la disyuncion a B a F a displaystyle forall a in mathfrak B a lor F a dd 8b Ley de identidad para la conjuncion a B a V a displaystyle forall a in mathfrak B a land V a dd 9 Ley de involucion a B a a displaystyle forall a in mathfrak B lnot lnot a a dd 10 Ley de complemento V F displaystyle lnot V F dd F V displaystyle lnot F V dd 11 Leyes de De Morgan a b B a b a b displaystyle forall a b in mathfrak B lnot a lor b lnot a land lnot b dd a b B a b a b displaystyle forall a b in mathfrak B lnot a land b lnot a lor lnot b dd Orden en el algebra de Boole Editar Sabiendo que B displaystyle mathfrak B lnot lor land es algebra de Boole se puede comprobar que a b b displaystyle a lor b b a b a displaystyle a land b a a b V displaystyle lnot a lor b V a b F displaystyle a land lnot b F Para las proposiciones a b que cumplen alguna de estas condiciones se puede afirmar que a antecede a b Que en el caso de proposiciones o predicados se dice que a es tanto o mas fuerte que b o que b es mas debil que a y lo representamos a b displaystyle a preccurlyeq b Asi por ejemplo dadas las proposiciones a Llueve mucho b Lluevepodemos ver a b b displaystyle a lor b b Si llueve mucho o llueve entonces llueve Si se da la circunstancia de cualesquiera de dos que llueve mucho o llueve claramente llueve en cualquier caso a b a displaystyle a land b a Si llueve mucho y llueve entonces llueve mucho Si afirmamos que llueve mucho y que llueve y se cumplen las dos circunstancias entonces es que llueve mucho a b V displaystyle lnot a lor b V Si no llueve mucho o llueve es verdadero No llueve mucho indica que puede que llueva poco o que no llueva si no llueve mucho o llueve abarca todas las posibilidades desde tiempo seco a muy lluvioso luego la afirmacion es verdadera en todo caso a b F displaystyle a land lnot b F Si llueve mucho y no llueve es falso Si afirmamos que llueve mucho y simultaneamente que no llueve la afirmacion es claramente falsa La afirmacion mas restrictiva es la mas fuerte y la menos restrictiva la mas debil en este caso l l u e v e m u c h o l l u e v e displaystyle llueve mucho preccurlyeq llueve La proposicion llueve mucho es tanto o mas fuerte que llueve la afirmacion llueve mucho es un caso particular o el mismo caso de llueve Operaciones en algebra de Boole EditarArticulo principal Conectiva logica Articulo principal Operacion matematica El algebra de Boole se basa en un conjunto en el que se han definidos tres operaciones internas una unaria y dos binarias como ya hemos visto siendo comoda esta definicion Estrictamente hablando solo son necesarias dos la unaria y una de las binarias asi por ejemplo en la logica binaria con la negacion y el producto podemos definir la suma Con la ley de De Morgan a b 0 1 a b a b a b a b displaystyle forall a b in 0 1 overline a b bar a cdot bar b longrightarrow quad a b overline bar a cdot bar b Esta expresion resulta mas compleja pero partiendo de la negacion y el producto binarios define la suma binaria En la imagen de la derecha podemos ver un circuito en paralelo de dos pulsadores a y b que corresponde a la suma binaria de a y b y su equivalente en un circuito en serie de a y b los dos dan como resultado la misma tabla de verdad y por tanto son equivalentes lo artificioso el circuito serie para obtener el mismo resultado que en un circuito paralelo deja ver lo conveniente de considerar esa funcion la posibilidad de obtener la suma de dos variables binarias mediante la negacion y el producto senalan que de forma primaria el algebra de Boole se basa solo en dos operaciones y que cualquier expresion en la que intervenga la suma puede transformarse en otra equivalente en la que solo intervienen la negacion y el producto En el caso de la teoria de conjuntos con el complemento y la interseccion podemos definir la union A B C A C B C A B A C B C C displaystyle A cup B C A C cap B C longrightarrow quad A cup B A C cap B C C De una forma similar al algebra binaria o cualquier otra algebra de Boole La definicion del algebra con solo dos operaciones complica las expresiones pero permite determinar ciertas relaciones muy utiles asi como otras operaciones distintas En el algebra de Boole definido en un conjunto B displaystyle mathfrak B las operaciones son internas dado que parte de elemento de B displaystyle mathfrak B para obtener un resultado en B displaystyle mathfrak B Sin perdida de la generalidad y dado los distintos formas que puede adoptar el algebra de Boole consideraremos la logica proposicional con las proposiciones a c b etc Que pueden tomar los valores verdadero V o falso F Y las conectivas logicas sobre esas proposiciones que dan como resultado otras proposiciones logicas cada proposicion a b c etc Define un conjunto A B C etc Que podemos representar de forma grafica en un diagrama de Venn Podemos ver estas conectivas logicas para 0 1 y 2 variables en un diagrama de Hasse Operaciones por el numero de argumentos Editar Si vemos las distintas operaciones por su numero de argumentos podemos distinguir Sin argumentos Editar Articulo principal Operacion nularia Las operaciones logicas sin argumentos son Operacion nulariaPositiva Negativa displaystyle top Tautologia displaystyle bot ContradiccionCon un argumento Editar Articulo principal Operacion unaria Las operaciones con solo un argumento son Operacion unariaPositiva Negativaa displaystyle a Afirmacion logica a displaystyle neg a Negacion logicaCon dos argumentos Editar Articulo principal Operacion binaria Las operaciones que necesitan dos argumentos son Operacion binariaPositiva Negativaa b displaystyle a lor b Disyuncion logica a b displaystyle a downarrow b Disyuncion opuestaa b displaystyle a land b Conjuncion logica a b displaystyle a uparrow b Conjuncion opuestaa b displaystyle a to b Consecuencia logica a b displaystyle a not rightarrow b Adjuncion logicaa b displaystyle a leftarrow b Implicacion opuesta a b displaystyle a not leftarrow b Adjuncion opuestaa b displaystyle a leftrightarrow b Bicondicional a b displaystyle a not leftrightarrow b Disyuncion exclusivaOperaciones nularias Editar Una operacion nularia es la que devuelve un valor sin necesidad de argumentos podemos ver tautologia y contradiccion V displaystyle begin array c c hline amp top hline hline amp V hline end array La tautologia presenta el valor verdadero sin necesidad de argumentos o independientemente de las variables sobre la que se calcule En teoria de conjuntos corresponde al conjunto universal En logica proposicional corresponde al valor verdadero U a a V displaystyle begin array ccll top amp varnothing amp longrightarrow amp mathbb U amp amp longrightarrow amp a top equiv a V end array En un circuito de conmutacion corresponde a una conexion fija o puente cerrado F displaystyle begin array c c hline amp bot hline hline amp F hline end array La contradiccion por el contrario presenta siempre el valor falso sin necesitar argumentos o independientemente de los argumentos presentados En teoria de conjuntos corresponde al conjunto vacio En logica proposicional corresponde al valor falso U a a F displaystyle begin array ccll bot amp varnothing amp longrightarrow amp mathbb U amp amp longrightarrow amp a bot equiv a F end array En un circuito de conmutacion corresponde a la no conexion o puente abierto Operaciones unarias Editar Una operacion unaria es la que solo necesita un argumento para presentar un resultado podemos ver dos operaciones unarias identidad y negacion a a V V F F displaystyle begin array c c hline a amp a hline hline V amp V F amp F hline end array La operacion identidad de una afirmacion presenta el valor de la variacion i d U U a b i d a b a displaystyle begin array ccll id amp mathbb U amp longrightarrow amp mathbb U amp a amp longrightarrow amp b id a equiv b a end array Esta operacion se puede hacer con el dispositivo electronico amplificador buffer En un circuito de conmutacion corresponde a un interruptor normalmente abierto Interruptor NA a a V F F V displaystyle begin array c c hline a amp lnot a hline hline V amp F F amp V hline end array La operacion negacion logica de una variable presenta el valor contrario del argumento o los casos contrarios de los recogidos en el argumento U U a b a b a displaystyle begin array ccll lnot amp mathbb U amp longrightarrow amp mathbb U amp a amp longrightarrow amp b lnot a equiv b lnot a end array Esta operacion se hace con la Puerta NOT En un circuito de conmutacion corresponde a un interruptor normalmente cerrado Interruptor NC Operaciones binarias Editar La operacion binaria es la que necesita dos argumentos de hecho es la forma mas generalizada de operacion normalmente cuando nos referimos a operaciones nos referimos a operaciones binarias en el algebra de Boole podemos ver las siguientes operaciones binarias a b a b V V V V F F F V F F F F displaystyle begin array c c c hline a amp b amp a land b hline hline V amp V amp V V amp F amp F F amp V amp F F amp F amp F hline end array La Conjuncion logica presenta resultado verdadero solo cuando sus dos argumentos son verdaderos U U U a b c a b c a b displaystyle begin array ccll land amp mathbb U times mathbb U amp longrightarrow amp mathbb U amp a b amp longrightarrow amp c land a b equiv c a land b end array Normalmente representado a b displaystyle a land b La conjuncion logica de proposiciones es equivalente a la interseccion de conjuntos en teoria de conjuntos o a la puerta logica AND en circuitos de conmutacion seria un circuito en serie de interruptores a b a b V V F V F V F V V F F V displaystyle begin array c c c hline a amp b amp a uparrow b hline hline V amp V amp F V amp F amp V F amp V amp V F amp F amp V hline end array La Conjuncion opuesta presenta resultado verdadero en todos los casos excepto cuando sus dos argumentos son verdaderos Esta operacion es la negacion de la conjuncion a b a b a b displaystyle a uparrow b lnot a land b lnot a lor lnot b La conjuncion logica de proposiciones es equivalente a la puerta logica NAND a b a b V V V V F V F V V F F F displaystyle begin array c c c hline a amp b amp a lor b hline hline V amp V amp V V amp F amp V F amp V amp V F amp F amp F hline end array La Disyuncion logica acepta dos argumentos presentando como resultado verdadero si uno u otro de los argumentos es verdadero La disyuncion puede expresarse a b a b displaystyle a lor b lnot lnot a land lnot b La operacion disyuncion logica de proposiciones es equivalente a la union de conjuntos en teoria de conjuntos a la puerta logica OR y al circuito en paralelo en circuitos de conmutacion a b a b V V F V F F F V F F F V displaystyle begin array c c c hline a amp b amp a downarrow b hline hline V amp V amp F V amp F amp F F amp V amp F F amp F amp V hline end array La Disyuncion opuesta presenta resultado verdadero solo cuando sus dos argumentos son falsos Esta operacion es la negacion de la disyuncion a b a b a b displaystyle a downarrow b lnot a lor b lnot a land lnot b La negacion conjunta de proposiciones es equivalente a la puerta logica NOR a b a b V V V V F F F V V F F V displaystyle begin array c c c hline a amp b amp a to b hline hline V amp V amp V V amp F amp F F amp V amp V F amp F amp V hline end array span, wikipedia, wiki, leyendo, leer, libro, biblioteca, español , española, descargar, gratis, descargar gratis, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, imagen, música, canción, película, libro, juego, juegos © Derechos de autor 2021, Todos los derechos reservados  |   www.wiki3.es-es.nina.az Rss Feed SiteMap Ping DMCA Contacta con nosotros Página principal Cerrado Llama: