u2 algebra boole (1)

26
DISEÑO DIGITAL UNIDAD 2: ALGEBRA DE BOOLE M.C. RAFAEL ARTEAGA VELASCO

Upload: julio-cesar-ortiz-gonzalez

Post on 10-Sep-2015

240 views

Category:

Documents


11 download

DESCRIPTION

Algebra Boole

TRANSCRIPT

  • DISEO DIGITAL

    UNIDAD 2: ALGEBRA DE BOOLE

    M.C. RAFAEL ARTEAGA VELASCO

  • Unidad 2. Algebra de Boole. El lgebra de Boole permite manipular relaciones proposicionales y cantidades binarias. Aplicada a las tcnicas digitales se utiliza para la descripcin y diseo de circuitos ms econmicos. Las expresiones booleanas sern una representacin de la funcin que realiza un circuito digital. En esta unidad se trabaja con las teoras del creador de los circuitos lgicos, posteriormente se explicar cmo realizar la suma de minitrminos y el producto de un maxitrmino. Subtemas: 2.1 Teoremas y postulados del Algebra de Boole. 2.1.1 Postulados de D'Morgan. 2.2 Funciones lgicas. 2.2.1 Formas cannicas. 2.3 Simplificacin de funciones. 2.3.1 Suma de minitrminos. 2.3.2 Producto de maxitrminos.

  • El lgebra de Boole desarrollada por George Boole a mediados del siglo XIX constituye la base matemtica en la que se ha fundamentado el desarrollo de la lgica digital y que, an en la actualidad, contina siendo el soporte matemtico indispensable en la construccin de sistemas digitales.

    2.1 Teoremas y postulados del Algebra de Boole.

    El algebra de Boole opera con variables que admiten slo dos valores discretos y con que se pueden designar como verdadero-falso, si-no, bajo-alto y 0-1 .

    Hay que tener presente que estos smbolos no representan nmeros, sino dos estados diferentes de un dispositivo.

    Cuando el 0 y el 1 booleanos representan el estado de una variable de tensin se hablan de niveles lgicos.

    Slo existen tres tipos de operaciones bsicas: negacin (NOT), suma (OR) y producto (AND) . Estas operaciones bsicas se llaman operaciones lgicas.

  • Los circuitos digitales llamados puertas lgicas se pueden construir mediante componentes electrnicos como diodos, transistores y resistencias conectados de tal forma que la salida del circuito es el resultado de una operacin lgica bsica realizada con las entradas.

    La lgica aritmtica se parece a la aritmtica binaria y las operaciones AND y OR tienen su similitud con la multiplicacin y la suma respectivamente.

  • Principales compuertas lgicas y Algebra de Boole

  • Teoremas y postulados del Algebra de Boole

  • Teoremas y postulados del Algebra de Boole

  • 2.2. Simplificacin de funciones

    En lgebra booleana, se conoce como trmino cannico de una funcin lgica a todo producto o suma en la cual aparecen todas las variables en su forma directa o inversa.

    Una Funcin lgica que est compuesta por operador lgico puede ser expresada en forma cannica usando los conceptos de miniterminos y maxiterminos. Todas las funciones lgicas son expresables en forma cannica, tanto como una "suma de miniterms" como "producto de maxiterms". Esto permite un mejor anlisis para la simplificacin de dichas funciones, lo que es de gran importancia para la minimizacin de circuitos digitales.

    Una funcin booleana expresada como una disyuncin lgica (OR) de miniterms es usualmente conocida como "suma de productos", y su Dual de Morgan es el "producto de sumas", la cual es una funcin expresada como una conjuncin lgica (AND) de maxiterms

  • TERMINO MINIMOS Y TERMINOS MAXIMOS

    Una variable binaria puede aparecer en su forma normal (x) o en

    la forma de complemento (x).

    Considrese ahora dos variable binarias x y y combinadas con la

    operacin AND; como cada variable puede aparecer de cualquier

    forma, habr cuatro combinaciones posibles: xy, xy, xy y xy.

    Cada uno de estos cuatro trminos AND representan una de las

    diferentes reas de producto normalizado. De igual manera, se

    pueden cambiar n variable para formar 2n trminos mnimos.

    Los 2n diferentes trminos mnimos pueden determinarse por

    un mtodo similar al mostrado en la siguiente tabla para tres

    variables.

  • Trminos Mnimos y Mximos para tres variables

    Trminos Mnimos Trminos Mximos

    x y z Trmino Designacin Trmino Designacin

    0 0 0

    0 0 1

    0 1 0

    0 1 1

    1 0 0

    1 0 1

    1 1 0

    1 1 1

    xyz

    xyz

    xyz

    xyz

    xyz

    xyz

    xyz

    xyz

    m0

    m1

    m2

    m3

    m4

    m5

    m6

    m7

    x+y+z

    x+y+z

    x+y+z

    x+y+z

    x+y+z

    x+y+z

    x+y+z

    x+y+z

    M0

    M1

    M2

    M3

    M4

    M5

    M6

    M7

  • PROCESO PARA UNA SUMA DE TERMINOS MINIMOS (forma normal disyuntiva)

    Se haba dicho antes que para n variables binarias, se pueden obtener

    2n trminos mnimos diferentes y que cualquier funcin de Boole

    puede expresarse como una suma de trminos mnimos.

    Los trminos mnimos cuya suma define la funcin de Boole son

    aquellos que dan el 1 de la funcin en una tabla de verdad.

    Como la funcin puede ser 1 0 para cada termino mnimo y ya que

    hay 2n trminos mnimos, se pueden calcular las funciones posibles

    que pueden formarse con n variables como 22n

    Algunas veces es conveniente expresar la funcin de Boole en la

    forma de ella expandiendo primero la expresin a una suma de

    trminos AND. Luego se inspecciona cada termino para ver si contiene

    todas las variables. Si le hace falta una o mas variables, se aplica la

    funcin AND con una expresin tal como x + x, donde x sea una

    variable faltante. El siguiente ejemplo aclara este procedimiento.

  • Ejemplo: Expresar la funcin de Boole F = A + BC como suma de trminos mnimos.

    La funcin tiene tres variables: A, B y C. como el primer trmino A no tiene las otras dos variables por tanto:

    A = A (B + B) = AB + AB

    Como la expresin carece de una variable:

    A = AB (C + C) + AB (C + C)

    = ABC + ABC + ABC + ABC

    El segundo trmino BC carece tambin de una variable:

    BC = BC (A + A) = ABC + ABC

  • Combinando todos los trminos se obtendr: F = A + BC

    = ABC + ABC + ABC + ABC + ABC + ABC

    Pero como ABC aparece dos veces, y de acuerdo al teorema 1 (x + x = x), es posible quitar uno de ellos. Rearreglando los trminos en orden ascendente se obtendr finalmente:

    F = ABC + ABC + ABC + ABC + ABC

    = m1 + m4 + m5 + m6 + m7

    Es conveniente algunas veces, expresar la funcin de Boole cuando est compuesta de una suma de trminos mnimos por medio de la siguiente forma simplificada:

    F (A, B, C) = (1, 4, 5, 6, 7)

  • )7,3,1(),,(

    ______

    731

    zyxf

    xyzzyxzyxmmmf

    Ejemplo miniterms

  • Cada una de las 2n funciones de n variables binarias pueden

    expresarse como un producto de trminos mximos. Para expresar

    las funciones de Boole como un producto de trminos mximos se

    debe primero llevar a una forma de trminos OR. Esto puede

    lograse usando la ley distributiva x + yz = (x + y)(x + z) y si hay una

    variable x faltante en cada trmino OR se le aplicar la funcin OR

    conjuntamente con xx.

    Este procedimiento se clarifica por medio del siguiente ejemplo:

    Proceso para un producto de Trminos Mximos

    (forma normal conjuntiva)

  • Ejemplo: Expresar la funcin de Boole F = xy + xz como un producto en la forma de trminos mximos.

    Primero convirtase la funcin a trminos OR usando la ley distributiva:

    F = xy + xz = (xy + x)(xy + z)

    = (x + x)(y + x)(x + z)(y + z)

    = (x + y)(x + z)(y + z)

    La funcin se tiene tres variables: x, y y z. a cada termino OR le hace falta

    una variable, por tanto:

    x + y = x + y + zz = (x + y + z)(x + y + z)

    x + z = x + z + yy = (x + y + z)(x + y + z)

    y + z = y + z + xx = (x + y + z)(x + y + z)

  • Combinando todos los trminos y quitando aquellos que aparezcan

    ms de una vez se obtendr finalmente:

    F = (x + y + z)(x + y + z)(x + y + z)(x + y + z)

    = M0M2M4M5

    Una forma conveniente de expresar esta funcin es de la siguiente

    manera:

    F (x, y, z) = (0, 2, 4, 5)