algebra de boole

El Algebra de Boole
Es un sistema matemático que utiliza variables y operadores lógicos. Las variables pueden valer 0 o 1. Y las operaciones b ́asicas son
OR (+) y AND (·)
.
Luego se definen las expresiones de conmutación como un número finito de variables y constantes, relacionadas mediante los operadores (AND y OR).

En la ausencia de paréntesis, se utilizan las mismas reglas deprecedencia, que tienen los operadores suma (OR) y multiplicación (AND) en el ́algebra normal.

Algebra de Boole
Leyes
En el ́algebra de Boole se cumplen las siguientes Leyes:
1) Conmutatividad:
X+Y=Y+X
X·Y=Y·X

2) Asociatividad:
X+ (Y+Z) = (X+Y) +Z
X· (Y·Z) = (X·Y) · Z

3) Distributividad:
X+ (Y·Z) = (X+Y) · (X+Z)
X · (Y+Z) = (X·Y) + (X·Z)


Identidades

4) Elementos Neutros(Identidad):
X+ 0 =X
X · 1 =X

5) Complemento:
X+X= 1
X · X= 0

6) Dominación:
X+ 1 = 1
X · 0 = 0

Demostración:
X + 1 = (X + 1) · 1 = (X+ 1) · (X+X)
(X+ 1) · (X+X) =X + (1 · X) = 1

7) Idempotencia:
X+X=X
X·X=X

8) Doble complemento:
X=X.

9) Absorción:
X+X·Y=X
X · (Y+X) =X

Demostración:
X+X · Y= (X · 1) + (X·Y) =X·(1 +Y) =X

10) DeMorgan:
A·B=A+B
A+B=A·B

Relacionesbinarias entre los elementos de un conjunto

Llamaremos relación binaria entre los elementos de A, a cualquier subconjunto de
A×A

Al conjunto de todas las relaciones binarias entre los elementos de A, lo representaremos con el símbolo Rel (A).

Es claro que se verifica que
Rel(A)= {B:B⊆A×A}=P(A×A).

En toda esta sección, cuando no digamos lo contrario, las relaciones consideradas seránentre los elementos de un conjunto.

Relaciones con ciertas propiedades particulares

Sea R ∈ Rel(A)
Diremos que R es
(i) reflexiva si: (a, a) ∈ R, para todo a ∈ A, [aRa]
(ii) simétrica si: (x, y) ∈R⇒(y, x)∈R, [xRy⇒yRx]
(iii) antisimetrica si: (x, y)∈R,(y, x)∈ R⇒x=y [xRy, yRx⇒x=y]
(iv) transitiva si: (x, y), (y, z)∈R⇒(x, z)∈R.[xRy, yRz⇒xRz ]
Nota.
Otra forma de definir la propiedad antisimetrica es: si (x, y) ∈ R y x W= y, entonces (y, x) / ∈ R

Ejemplos
Consideremos el conjunto
A={a, b, c, d, e} y las relaciones binarias
R1= {(a, b), (b, c), (a, c)},
R2= {(a, a), (b, b), (c, c),(d, d), (e, e)},
R3= R2∪{(a, b), (b, a)}

Entonces
R1: no es reflexiva, [(a, a) / ∈ R1]
No es simétrica[(a, b) ∈ R1 y (b, a) / ∈ R1]
Es transitiva y antisimetrica.
R2: es reflexiva, simétrica, transitiva y antisimetrica.
R3: es reflexiva, simetrica y transitiva,
No es antisimetrica. [(a , b), (b, a) ∈R3 y a W=b]

Nota.
La relación R2 del ejemplo muestra que una relación puede ser simetrica y antisimetrica a la vez.


RELACIONES BINARIAS
DEFINICIÓN(FORMAL, GRÁFICA,...)
Dado un conjunto A, una relación binaria en A es cualquier subconjunto R del producto cartesiano A A
RAA= {(a, b) / a, bA}.

Diremos que un elemento aA está relacionado con un elemento bA por la relación binaria R si se verifica que (a, b)  R. Se denotará
A R b

a R b
.
Para representar una relación binaria definida en un conjunto finito se puedeutilizar un diagrama sagital, de modo que si a R b entonces se dibuja una flecha desde a hasta b.
La flecha será un bucle cuando un elemento esté relacionado consigo mismo.
Por ejemplo, dado el conjunto
A= {a, b, c, d}, se verifica que el diagrama sagital de la relación binaria
R = {(a, a), (a, c), (b, b), (b, c), (c, d), (d, c)} es:

Observación:
Una relación puede definirse en términosde una propiedad P, ya que R es un conjunto:
R = {(a, b) AB/ P(a, b) es cierta}.
y, en este caso, R puede expresarse como sigue:
A R bP(a, b) es cierta

Ejemplos:
a) En el conjunto de las palabras de la lengua castellana se define R de forma que
palabra1 R palabra2 si palabra1 está antes en el diccionario que palabra2

b) En N se define la relación binaria: a R bb aN.
¿3 R...