Download DIESIA TEMA II.- ÁLGEBRA DE BOOLE

A + A’ = 1
A · A’ = 0
✏ SIEMPRE EXISTE EL COMPLEMENTO DE A, DENOMINADO A’ O A
A + 0 = A
A · 1 = A
✏ ELEMENTOS NEUTROS DIFERENTES:
A + (B · C) = (A + B)·(A + C)
A · (B + C) = A · B + A · C
✏ PROPIEDAD DISTRIBUTIVA:
A + B = B + A
A · B = B · A
✏ PROPIEDAD CONMUTATIVA:
DIESIA
☞ UN SISTEMA DE ELEMENTOS B Y DOS OPERACIONES BINARIAS CERRADAS (·) Y (+) SE DENOMINA ALGEBRA DE BOOLE SIEMPRE Y CUANDO
SE CUMPLAN LAS SIGUIENTES PROPIEDADES:
TEMA II.- ÁLGEBRA DE BOOLE
☞ PRINCIPIO DE DUALIDAD: CUALQUIER
TEOREMA O IDENTIDAD ALGEBRAICA DEDUCIBLE DE LOS POSTULADOS ANTERIORES
PUEDE TRANSFORMARSE EN UN SEGUNDO
TEOREMA O IDENTIDAD VÁLIDA SUSTITUYENDO 1’S POR 0’S Y (+) POR (·)
☞ CONSTANTE: CUALQUIER ELEMENTO DEL
CONJUNTO B
☞ VARIABLE: SÍMBOLO QUE REPRESENTA UN
ELEMENTO ARBITRARIO DEL ÁLGEBRA, YA
SEA CONSTANTE O UNA FÓRMULA
☞ TEOREMA 1: EL ELEMENTO COMPLEMENTO,
A’, ES ÚNICO
☞ TEOREMA DE LOS ELEMENTOS NULOS: PARA
CADA ELEMENTO DE B, SE VERIFICA:
A + 1 = 1
A · 0 = 0
☞ TEOREMA 3: CADA ELEMENTO IDENTIDAD
ES EL COMPLEMENTO DEL OTRO
☞ TEOREMA DE IDEMPOTENCIA: PARA CADA
ELEMETO DE B, SE VERIFICA:
A + A = A
A · A = A
DIESIA
☞ TEOREMA DE INVOLUCIÓN: PARA CADA
ELEMENTO DE B, SE VERIFICA:
(A’)’ = A
☞ TEOREMA DE ABSORCIÓN: PARA CADA
PAREJA DE ELEMENTOS DE B, SE VERIFICA:
A + A · B = A
A · (A + B) = A
☞ TEOREMA 7: PARA CADA PAREJA DE ELEMENTOS DE B, SE VERIFICA:
A + A’ · B = A + B
A · (A’ + B) = A · B
☞ LEYES DE DEMORGAN:
DE ELEMENTOS DE B,
(A + B)’
(A · B)’
PARA CADA PAREJA
SE VERIFICA:
= A’ · B’
= A’ + B’
☞ LEYES DE DEMORGAN GENERALIZADAS:
PARA CADA CONJUNTO DE B, SE VERIFICA
(A+B+...+Q)’ = A’·B’·...·Q’
(A·B·...·Q)’ = A’+B’+...+Q’
☞ TEOREMA DE ASOCIATIVIDAD: CADA UNO
DE LOS OPERADORES BINARIOS (+) Y (·)
CUMPLEN LA PROPIEDAD ASOCIATIVA
A+(B+C) = (A+B)+C
A·(B·C) = (A·B)·C
DIESIA
☞ ÁLGEBRA DE CONMUTACIÓN: UN SISTEMA
DE ELEMENTOS B={0,1} Y LOS OPERADORES DEFINIDOS DE LA SIGUIENTE FORMA
AB
A+B
A·B
A’
00
0
0
1
01
1
0
10
1
0
11
1
1
0
ES UN ÁLGEBRA DE BOOLE
OPERADOR + --> OPERADOR OR
OPERADOR · --> OPERADOR AND
OPERADOR ‘ --> OPERADOR NOT
☞ FUNCIÓN COMPLETA: UNA FUNCIÓN QUE SE
ENCUENTRA DEFINIDA PARA TODAS LAS
COMBINACIONES DE LAS VARIABLES DE
ENTRADA
☞ TABLA DE COMBINACIONES: FORMA DE
REPRESENTAR FUNCIONES
X1 X0
F(X1,X0)
0 0
F(0,0)
0 1
F(0,1)
1 0
F(1,0)
1 1
F(1,1)
DIESIA
LO SON
DIESIA
☞ FÓRMULA NORMAL DISYUNTIVA: SUMA DE TÉRMINOS PRODUCTOS
☞ TÉRMINO PRODUCTO: OPERACIÓN AND DE UN NÚMERO DE LITERALES
☞ DOS FÓRMULAS, A Y B, SON EQUIVALENTES (A=B) SI DESCRIBEN LA
MISMA FUNCIÓN DE CONMUTACIÓN
☞ TEOREMA 11: CADA FÓRMULA DESCRIBE UNA ÚNICA FUNCIÓN
NÚMERO FINITO DE PASOS.
✏ NADA MÁS ES UNA FÓRMULA A MENOS QUE SIGAN LOS PUNTOS ANTERIORES EN UN
✏ SI A Y B SON FÓRMULAS, A+B Y A·B
✏ SI A ES UNA FÓRMULA, A’ TAMBIÉN LO ES
✏ XI ES UNA FÓRMULA SI PERTENECE A {0,1}
✏ 1 Y 0 SON FÓRMULAS DE CONMUTACIÓN
☞ FÓRMULAS DE CONMUTACIÓN: EXPRESIÓN DE UNA FUNCIÓN DE CONMUTACIÓN.
DIESIA
☞ TEOREMA 13: LA FÓRMULA COMPUESTA POR TODOS LOS MINTÉRMINOS
SERÁ IDÉNTICAMENTE 1.
☞ TEOREMA 12: DADA LA LISTA COMPLETA DE MINTÉRMINOS Y ASIGNANDO 1’S Y 0’S ARBITRARIAMENTE A LAS VARIABLES, SIEMPRE HAY
UN Y SÓLO UN MINTÉRMINO QUE TOMA EL VALOR 1.
☞ FÓRMULA CANÓNICA DISYUNTIVA O DE MINTÉRMINOS: SUMA DE MINTÉRMINOS
☞ MINTÉRMINO (mi): TÉRMINO PRODUCTO EN EL QUE APARECEN TODAS
LAS VARIABLES, YA SEAN COMPLEMENTADAS O SIN COMPLEMENTAR
☞ FÓRMULA NORMAL CONJUNTIVA: PRODUCTO DE TÉRMINOS SUMA
☞ TÉRMINO SUMA: OPERACIÓN OR DE UN NÚMERO DE LITERALES
DIESIA
☞ FÓRMULA CANÓNICA CONJUNTIVA O DE MAXTÉRMINOS: PRODUCTO DE
MAXTÉRMINOS
☞ MAXTÉRMINO (MI): TÉRMINO SUMA EN EL QUE APARECEN TODAS LAS
VARIABLES, YA SEAN COMPLEMENTADAS O SIN COMPLEMENTAR
F(X,Y,Z) = X·Y·Z+X’·Y·Z’+X’·Y’·Z’ = m7 + m2 + m0
☞ TEOREMA 17: CADA FUNCIÓN COMPLETA PUEDE EXPRESARSE COMO:
F(X1,...,XN) = ΣiF(i)·mi(X1,...,XN)
☞ PRIMER TEOREMA DE EXPANSIÓN: SIEMPRE SE VERIFICA:
F(X1,...,XN) = X1·F(1,...,XN) + X1’·F(0,...,XN)
☞ TEOREMA 15: LA FÓRMULA DE MINTÉRMINOS ES ÚNICA
☞ TEOREMA 14: CADA FUNCIÓN PUEDE EXPREASRSE COMO SUMA DE MINTÉRMINOS
DIESIA
☞ TEOREMA 23: CADA FUNCIÓN COMPLETA PUEDE ESCRIBIRSE COMO:
F(X1,...,XN) = Πi [F(i)+M(X1,...,XN)]
F(X,Y,Z) = (X’+Y’+Z’)·(X+Y’+Z)·(X+Y+Z) = M7 · M2 · M0
☞ SEGUNDO TEOREMA DE EXPANSIÓN: SIEMPRE SE VERFICA:
F(X1,...,XN)=[X1+F(0,...,XN)]·[X1’+F(1,...,XN)]
☞ TEOREMA 21: LA FÓRMULA DE MAXTÉRMINOS ES ÚNICA
☞ TEOREMA 20: CADA FUNCIÓN PUEDE EXPRESARSE COMO PRODUCTO DE
MAXTÉRMINOS
☞ TEOREMA 19: LA FÓRMULA COMPUESTA POR TODOS LOS MAXTÉRMINOS
SERÁ IDÉNTICAMENTE 0.
☞ TEOREMA 18: DADA LA LISTA COMPLETA DE MAXTÉRMINOS Y ASIGNANDO 0’S Y 1’S ARBITRARIAMENTE A LAS VARIABLES, SIEMPRE HAY
UN Y SÓLO UN MAXTÉRMINO QUE TOMA EL VALOR 0.
DIESIA
Nº TÉRMINOS + Nº VARIABLES - Nº TÉRMINOS CON UN SOLO LITERAL -1
✏ MENOR VALOR ASOCIADO:
✏ MENOR NÚMERO DE TÉRMINOS
✏ MENOR NÚMERO DE VARIABLES
☞ CRITERIOS DE MINIMALIDAD:
☞ LA TRANSFORMACIÓN DE UNA FÓRMULA DE MINTÉRMINOS (EN GENERAL
DISYUNTIVA) EN OTRA DE MAXTÉRMINOS (EN GENERAL CONJUNTVA) SE
BASA EN LA DOBLE COMPLEMENTACIÓN, (F’)’ = F
☞ TEOREMA 26: mi’ = Mi Y Mi’ = mi
☞ TEOREMA 25: EL COMPLEMENTO DE UNA FÓRMULA DE MÁXTERMINOS
ESTÁ FORMADO POR EL PRODUCTO DE LOS MAXTÉRMINOS QUE NO APARECEN
☞ TEOREMA 24: EL COMPLEMENTO DE UNA FÓRMULA DE MINTÉRMINOS
ESTÁ FORMADO POR LA SUMA DE LOS MINTÉRMINOS QUE NO APARECEN
DIESIA
☞ LAS FÓRMULAS DE MINTÉRMINOS Y MAXTÉRMINOS DE LAS FUNCIONES
INCOMPLETAS NO SON ÚNICAS
☞ COMPLEMENTO DE UNA FUNCIÓN INCOMPLETA: OTRA FUNCIÓN INCOMPLETA CON LA MISMA FUNCIÓN INESPECIFIFCACIÓN Y EL COMPLEMENTO DE LA FUNCIÓN COMPLETA
✏ FUNCIÓN INESPECIFICACIÓN
✏ FUNCIÓN COMPLETA CON TODAS LAS INESPECIFICACIONES A 0
☞ FUNCIONES INCOMPLETAS: FUNCIONES QUE NO ESTÁN DEFINIDAS PARA
TODAS LAS COMBINACIONES DE LAS VARIABLES DE ENTRADA
☞ ARITMÉTICA BINARIA
✏ SUMA BINARIA:
A
B
SUMA
ACARREO
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
11111 100
10110.011
+11011.110
110010.001
<-- ACARREO
--> 22.375
--> +27.750
--> 50.125
✏ RESTA BINARIA:
A
B
RESTA
DESBORDAMIENTO
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
0
10100.11
10110.00
-01011.01
01001.10
---> 20.75
<-- DESBORDAMIENTO
---> -11.25
9.50
DIESIA
✏ COMPLEMENTO A DOS: NÚMERO BINARIO NEGATIVO
✓ INVERSIÓN DEL NÚMERO Y SUMAR 1
2(1011)
--> 0100+1 = 0101
✓ DESDE LA DERECHA, BUSCAR EL PRIMER 1, Y
A PARTIR DEL SIGUIENTE INVERTIR EL
RESTO DE BITS.
2(1011) --> 0101
✏ OPERACIONES DE DESPLAZAMIENTO
✓ DESPLAZAMIENTO DE N DÍGITOS A LA
✓
IZQUIERDA (AÑADIENDO CEROS EN CASO
NECESARIO) ES IGUAL QUE MULTIPLICAR
POR 2N
DESPLAZAMIENTO DE N DÍGITOS A LA DERECHA (AÑADIENDO CEROS EN CASO NECESARIO) ES IGUAL QUE MULTIPLICAR POR 2-N
O DIVIDIR POR 2N
✏ MULTIPLICACIÓN BINARIA:
A
B
A·B
0
0
0
0
1
0
1
0
0
1
1
1
SE MULTIPLICA DÍGITO A DÍGITO Y SE REALIZAN LAS SUMAS SUCESIVAS:
101.11
101
101 11
0000 00
+10111 00
11100.11
DIESIA
BAJA EL SIGUIENTE
DÍGITO DEL DIVIDENDO
AL RESULTADO DE LA
RESTA
AL COCIENTE SE LE
AÑADE UN ‘1’.
RESTA
101101 : 101
101
1001
000101
101
000
0<
<0
ALINEAR EL DIVISOR CON
LA PARTE MÁS IZQUIERDA
DEL DIVIDENDO (QUE SEA
MAYOR QUE EL DIVISOR)
✏ DIVISIÓN BINARIA: MEDIANTE ALGORITMO
DIESIA
BAJA EL SIGUIENTE
DÍGITO DEL DIVIDENDO
AL RESULTADO DE LA
RESTA ANTERIOR
AL COCIENTE SE LE
AÑADE UN ‘0’.