3.1 Matemáticas discretas

3.1 Álgebra booleana

Esto es un párrafo listo para contener creatividad, experiencias e historiasLa lógica simbólica y el álgebra de conjuntos han sido pilares fundamentales en el desarrollo de la teoría matemática y la informática moderna. Estos campos, al principio independientes, convergieron para formar una estructura más general conocida como álgebra booleana. Esta disciplina, nombrada en honor al matemático británico George Boole, proporciona un marco formal para el estudio de las operaciones lógicas sobre conjuntos de datos, lo que resulta crucial en campos como la computación, la electrónica digital y la inteligencia artificial. En este contexto, exploraremos cómo el Álgebra Booleana ha revolucionado nuestra comprensión de la lógica y ha sentado las bases para numerosos avances tecnológicos que transforman nuestras vidas cotidianas (Espinoza, 2010). Además, cabe destacar que en 1854. Boole escribió un libro titulado "The laws of thought" (Las leyes del pensamiento), una obra seminal que profundiza en los principios fundamentales de la lógica y sienta las bases para la formalización de este campo y su aplicación en diversas áreas científicas y tecnológicas (Johnsonbaugh, 2005). geniales.

Leer más

3.1.2 Definición de retícula distributiva.

Como recordatorio de lo estudiado previamente en la unidad sobre relaciones y funciones, observa el siguiente diagrama:

Info

Recuerda: A×B={(a,b) ┤| a∈A∧b∈B}. Si el par ordenado (𝑎, 𝑏)∈𝑅 se escribe 𝑎𝑅𝑏 y significa que 𝑎 está relacionado con 𝑏. Si el par ordenado (𝑎, 𝑏)∉𝑅 se escribe ¬(𝑎𝑅𝑏), para indicar que 𝑎 no está relacionado con 𝑏.

Reflexiona lo siguiente: Una relación binaria R puede estar definida en un conjunto A. En ese caso, se tiene que: Sea A={1,2,3,4}, y definimos a R={(a,b) ┤| a≤b}. Se tiene que R es una relación binaria en A:

R⊆A×A.

R={(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)}

(Villalpando, 2015)

Una relación binaria 𝑅 sobre un conjunto 𝐴 se dice que es reflexiva si para todo 𝑎∈𝐴, se tiene que 𝑎𝑅𝑎.

Una relación binaria 𝑅 sobre un conjunto 𝐴 se dice que es irreflexiva si para todo 𝑎∈𝐴, se tiene que ¬(𝑎𝑅𝑎).

Una relación binaria 𝑅 sobre un conjunto 𝐴 se dice que es asimétrica si para todo 𝑎𝑅𝑏, se tiene que ¬(𝑏𝑅𝑎).

Una relación binaria 𝑅 sobre un conjunto 𝐴 se dice que es simétrica si para todo 𝑎𝑅𝑏, se tiene que 𝑏𝑅𝑎.

Una relación binaria 𝑅 sobre un conjunto 𝐴 se dice que es antisimétrica si para todo 𝑎𝑅𝑏 y 𝑏𝑅𝑎, se tiene que 𝑎=𝑏.

Leer más

• Si 𝑅 es una relación de orden parcial sobre 𝐴, entonces se utiliza la notación 𝑎≤𝑏 para indicar que 𝑎𝑅𝑏.
• Si 𝑅 es una relación de orden parcial sobre 𝐴, entonces se utiliza la notación 𝑎≰𝑏 para indicar que ¬(𝑎𝑅𝑏).
• Sea 𝐴={1, 2, 3, 4}, y definimos a 𝑅={(𝑎,𝑏) ┤| 𝑎≤𝑏}. Entonces 𝑅 es una relación de orden parcial sobre 𝐴.
• Si ≤ es una relación de orden parcial sobre 𝐴, entonces a la pareja (𝐴, ≤) se le conoce como conjunto parcialmente ordenado o COPO o POSET.

• Sean (𝐴, ≤) un COPO y 𝑎, 𝑏∈(𝐴,≤). Diremos que 𝑎 y 𝑏 son comparables si 𝑎≰𝑏 o 𝑏≰𝑎.
• Sean (𝐴, ≤) un COPO y 𝑎, 𝑏∈(𝐴,≤). Diremos que 𝑎 y 𝑏 son incomparables si 𝑎≰𝑏 y 𝑏≰𝑎.
• Sean (𝐴, ≤) un COPO y para todo 𝑎, 𝑏∈(𝐴,≤) si 𝑎 y 𝑏 son comparables, entonces se dice que ≤ es un orden total sobre 𝐴.
• Sean (𝐴, ≤) un COPO y 𝑎∈𝐴. Diremos que 𝑎 es un elemento maximal en 𝐴 si para todo 𝑏∈𝐴 se tiene que 𝑏≤𝑎 o 𝑎 y 𝑏 son incomparables.

• Sean (𝐴, ≤) un COPO y 𝑏∈𝐴. Diremos que 𝑏 es un elemento minimal en 𝐴 si para todo 𝑎∈𝐴 se tiene que 𝑏≤𝑎 o 𝑎 y 𝑏 son incomparables.
• Si (𝐴, ≤) es COPO y 𝐴 es finito y no vacío, entonces 𝐴 tiene un elemento maximal y tiene un elemento minimal.
• Sean (𝐴, ≤) un COPO y 𝑎∈𝐴. Diremos que 𝑎 es un elemento máximo en 𝐴 si 𝑏≤𝑎 para todo 𝑏∈𝐴.
• Sean (𝐴, ≤) un COPO y 𝑏∈𝐴. Diremos que 𝑎 es un elemento mínimo en 𝐴 si 𝑏≤𝑎 para todo 𝑎∈𝐴.
• Sean (𝐴, ≤) un COPO. Nota que un elemento máximo es maximal, y un elemento mínimo es minimal, pero el recíproco no necesariamente es cierto, por ejemplo:

Sea 𝐴={𝑎,𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔, ℎ} y sea ≤ ={(𝑎, 𝑐), (𝑎, 𝑑),(𝑏, 𝑑),(𝑏, 𝑒),(𝑐, 𝑓),(𝑑, ℎ),(𝑒, 𝑔),(𝑓, ℎ),(𝑔, ℎ)}. Nota que (𝐴, ≤) un COPO y no tiene elementos máximos, pero si maximales.

• Sean (𝐴, ≤) un COPO, 𝐵⊆𝐴 y 𝑎∈𝐴. Diremos que 𝑎 es una cota superior de 𝐵 si 𝑏≤𝑎 para todo 𝑏∈𝐵.
• Sean (𝐴, ≤) un COPO, 𝐵⊆𝐴 y 𝑏∈𝐴. Diremos que 𝑏 es una cota inferior de 𝐵 si 𝑏≤𝑎 para todo 𝑎∈𝐵.
• Sean (𝐴, ≤) un COPO, 𝐵⊆𝐴 y 𝑎∈𝐴. Diremos que 𝑎 es el supremo de 𝐵 si 𝑎 es cota superior de 𝐵 y 𝑎≤𝑐 para todo 𝑐 cota superior de 𝐵. Es decir, el supremo es la menor de las cotas superiores.
• Sean (𝐴, ≤) un COPO, 𝐵⊆𝐴 y 𝑏∈𝐴. Diremos que 𝑏 es el ínfimo de 𝐵 si 𝑏 es cota inferior de 𝐵 y 𝑐≤𝑏 para todo 𝑐 cota inferior de 𝐵. Es decir, el ínfimo es la mayor de las cotas inferiores.
• Si el supremo existe, entonces es único.
• Si el ínfimo existe, entonces es único.

Después de haber reflexionado sobre todos los puntos anteriores, es momento de definir lo que entendemos por una retícula. Consideremos que (𝐴, ≤) es un conjunto parcialmente ordenado (COPO). Diremos que (𝐴, ≤) constituye una retícula si, para cualquier subconjunto {𝑎,𝑏} de A que contenga exactamente dos elementos, existen tanto el supremo (el menor elemento mayor o igual que a y b) como el ínfimo (el mayor elemento menor o igual que a y b) de a y b.

3.1.3 Definición de álgebra booleana.

Hemos explorado las condiciones que definen una retícula distributiva, destacando su importancia en el estudio de las estructuras algebraicas. Ahora nos adentraremos en el concepto de álgebra booleana, un área fundamental que encuentra sus raíces en las propiedades de las retículas distributivas. Continuaremos examinando cómo estas estructuras algebraicas influyen en diversos campos, desde la lógica hasta la computación, demostrando su relevancia y versatilidad en la resolución de problemas y en el avance del conocimiento matemático y científico. El álgebra booleana es una quinteta (𝐵, ∨, ∧, ′,0,1), donde 𝐵 es un conjunto, ∨ y ∧ son relaciones binarias sobre 𝐵, ′ es una relación unaria en 𝐵 y dos elementos distintos 0 y 1, que satisfacen las siguientes propiedades (Espinosa, 2010):

Para cualesquiera a,b,c∈B se tiene que:

Ley asociativa

Ley conmutativa

a∨(b\∨c)=(a∨b)∨c. a∧(b∧c)=(a∧b)∧c.

a∨b=b∨a. a∧b=b∧a.

Ley distributiva

Ley identidad

a∨0=a. a∧1=a.

a∨(b∧c)=(a∨b)∧(a∨c). a∧(b∨c)=(a∧b)∨(a∧c).

Ley complemento

a∨a^'=1. a∧a^'=0.

Usualmente, a las relaciones binarias ∨, ∧ y ' se les llama “la unión, intersección y complemento”, respectivamente. También, a 0 se le llama “el cero” y al 1 se le llama “el uno”.

Reflexiona los siguientes ejemplos de álgebras booleanas:

3.1 Álgebra booleana

Sea 𝐴 el conjunto de todas las proposiciones lógicas. Observa que en 𝐴, se puede definir una relación de equivalencia como sigue:

𝑅={(𝑝,𝑞) | 𝑝⇔𝑞}.

Sea 𝐵 el conjunto de las clases de equivalencia que se forman a través de 𝑅, es decir:

𝐵={[𝑝] ┤| 𝑝∈𝐴}.

Si definimos

[𝑝]∨[𝑞]=[𝑝∨𝑞] [𝑝]∧[𝑞]=[𝑝∧𝑞] [𝑝]′=[¬𝑝] 0=[𝑐𝑜𝑛𝑡𝑟𝑎𝑑𝑖𝑐𝑐𝑖𝑜𝑛𝑒𝑠] 1=[𝑡𝑎𝑢𝑡𝑜𝑙𝑖𝑔í𝑎𝑠]

¡Es un álgebra booleana!

Hemos explorado las condiciones bajo las cuales un conjunto, junto con ciertas operaciones, puede constituir un álgebra booleana, comprendiendo así cómo estas estructuras algebraicas se aplican en diversos contextos, desde la lógica digital hasta la teoría de conjuntos.Al entender las propiedades y aplicaciones de las álgebras booleanas, se sientan las bases para abordar problemas complejos y desarrollar soluciones innovadoras en campos como la informática, la inteligencia artificial y la criptografía, entre otros.

Lo questás observando es una correspondencia entre los elementos de dos conjuntos, es decir, una relación, la que usualmente está denotada por:

La pareja (x_1, y_1 ) da a entender que la x_1 está relacionada con y_1, mediante R. Algunos autores lo escriben: "x_1 Rx_2 “, y así sucesivamente con las demás parejas. En la forma intuitiva, una relación es una comparación entre dos elementos de dos conjuntos. Esta se expresa usando pares ordenados. Por lo tanto, en la forma abstracta, una relación R, se define como un conjunto de pares ordenados (Villalpando, 2015). De manera formal, una relación binaria R de un conjunto A en un conjunto B es un subconjunto del producto cartesiano A×B, es decir:

R={(x_1,y_1 ),(x_1,y_2 ),(x_2,y_1 ),(x_2,y_2 ),(x_3,y_3 ),(x_4,y_4 ),…}

R⊆A×B.

Sean B={0, 1}, y definamos a ∨ y ∧ mediante las tablas:

También sea 0'=1 y 1'=0. Esta es un álgebra booleana. Sea X un conjunto no vacío. Tomemos B=A A⊆X}, para todo A, C∈B definimos:

A∨C=A∪C A∧C=A∩C A'=Ac 0=∅ 1=X

¡Es un álgebra booleana!

En la sección 3.1 y 3.2 veremos cómo definir un orden parcial. Luego, veremos qué es un álgebra booleana y algunos ejemplos, para posteriormente ver que hay un orden parcial en un álgebra booleana. También, te mostraremos las propiedades más importantes de las álgebras booleanas. Finalmente, en las secciones 3.3 y 3.4, veremos la relación entre expresiones y funciones booleanas y cómo utilizar los conceptos y resultados del álgebra booleana en el diseño y análisis de circuitos lógicos.

Todo COPO es una retícula. Sea (𝐴, ≤) es una retícula, escribiremos: 𝑎∨𝑏= supremo del conjunto {𝑎, 𝑏}. 𝑎∧𝑏= ínfimo del conjunto {𝑎, 𝑏}. Sea (𝐴, ≤) es una retícula, entonces para cualesquiera 𝑎, 𝑏, 𝑐∈𝐴 se cumple que:

Ley asociativa:

𝑎∨(𝑏∨𝑐)=(𝑎∨𝑏)∨𝑐. 𝑎∧(𝑏∧𝑐)=(𝑎∧𝑏)∧𝑐.

Ley conmutativa:

𝑎∨𝑏=𝑏∨𝑎. 𝑎∧𝑏=𝑏∧𝑎.

Ley absorción:

Ley idempotencia:

𝑎∨(𝑎∧𝑏)=𝑎. 𝑎∧(𝑎∨𝑏)=𝑎.

𝑎∨𝑎=𝑎. 𝑎∧𝑎=𝑎.

Sea (A,≤) es una retícula. Diremos que es una retícula distributiva si satisface que para cualesquiera a,b,c∈A se cumple que:

a∨(b∧c)=(a∨b)∧(a∨c). a∧(b∨c)=(a∧b)∨(a∧c).

Una relación binaria 𝑅 sobre un conjunto 𝐴 se dice que es transitiva si para todo 𝑎𝑅𝑏 y 𝑏𝑅𝑐, se tiene que 𝑎𝑅𝑐.

Cuando una relación binaria 𝑅 sobre un conjunto 𝐴 es reflexiva, simétrica y transitiva, se dice que 𝑅 es una relación de equivalencia sobre 𝐴 o 𝑅 es una relación de equivalencia en 𝐴.

Sea 𝑅 es una relación de equivalencia en 𝐴 y sea 𝑎∈𝐴. Definimos la clase de equivalencia de 𝑎 como: [𝑎]={𝑥∈𝐴 ┤| 𝑥𝑅𝑎}, Es decir, la clase de equivalencia de un elemento son todos los elementos que están relacionados con él.

Cuando una relación binaria 𝑅 sobre un conjunto 𝐴 es reflexiva, antisimétrica y transitiva, se dice que 𝑅 es una relación de orden parcial sobre 𝐴.