Download DIESIA TEMA II.- ÁLGEBRA DE BOOLE
Document related concepts
Transcript
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’.