Funciones Boleanas

2-Funciones y representaciones booleanas

2.1 Lógica y álgebra de Boole

2.2 Funciones booleanas

2.3 Representaciones de funciones booleanas 2.4 Funciones de varias variables

2: Funciones booleanas

2

Lógica Booleana

❒ Definiciones básicas

❍ Una variable booleana (e.g. x, y) es un símbolo que puede ser substituido por un elemento del conjunto B={0,1}

❍ Una constante booleana es un valor perteneciente al conjunto {0,1}

❍ Una expresión (e.g. x+y, x·y, x’) esta compuesta de variables, constantes y operadores (e.g. +, ·, ’)

❍ Una función booleana de n variables f(x1, x2, ..., xn) es un expresión o formula que mapea f a un valor del conjunto booleano B (0 o 1)

❍ Un literal es una variable o su complemento

2: Funciones booleanas

3

Álgebra de Boole

❒ Definición: el álgebra de Boole es un sistema algebraico cerrado que contiene:

❍ un conjunto de dos elementos {0, 1}, ❍ dos operadores binarios {+, ·},

❍ un operador unitario { ‘ }.

2: Funciones booleanas

4

Lógica y álgebra de Boole

❒ El álgebra de Boole es la fundación matemática de los sistemas digitales.

❒ Las operaciones del álgebra de Boole deben regirse por propiedades y reglas lógicas llamados leyes o postulados.

❒ Estos postulados se pueden usar para demostrar leyes mas generales sobre expresiones booleanas.

❒ Estos postulados también se usan para simplificar y optimizar expresiones booleanas y sistemas digitales.

❍ Ejemplo: X AND (Y OR Y’) = X (¿porque?)

2: Funciones booleanas

5

Álgebra de Boole

❒ Una expresión algebraica de Boole consiste de ❍ unconjuntodeB

❍ operacionesbinarias{+,•}

❍ unaoperacionesunitaria{’}

❒ B tiene dos elementos : a, b y los siguientes postulados se cumplen:

Clausura: Conmutatividad: Asociatividad:

a+b estaenB,a•b estaenB a + b = b + a, a • b = b • a

a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c

Identidad: Distributividad:

a + 0 = a, a • 1 = a

a + (b • c) = (a + b) • (a + c) a • (b + c) = (a • b) + (a • c)

Complementariedad:

a + a’ = 1, a • a’ = 0

2: Funciones booleanas

6

Álgebra de Boole: Resumen

❒ Álgebra de Boole ❍ B={0,1}

❍ variables

❍ +eselORlógico,•eselANDlógico ❍ ’ es el NOT lógico

❒ Todos los postulados (axiomas) algebraicos se cumplen

❒ La prioridad de los operadores es ‘, seguido por AND y despues OR.

❒ El ‘ tiene la mayor prioridad.

❒ Los ( ) pueden cambiar el orden de evaluación.

2: Funciones booleanas

7

Álgebra de Boole: Teoremas

❒ Con la formulación de los postulados del álgebra de Boole se pueden demostrar varias proposiciones o teoremas de álgebra booleana

❒ Para las demostraciones de teoremas se pueden usar:

❍ tablas de verdad,

❍ postulados,

❍ y teoremas ya demostrados

2: Funciones booleanas

8

Álgebra de Boole: Teoremas

❒ Definición: El álgebra de boole es un sistema algebraico cerrado que contiene un conjunto B de dos elementos {0,1} y tres operadores {·, +, ‘}.

❒ igualdad: Dos expresiones son iguales si una puede ser substituida por otra.

❒ identidad:

1. X+0=X

1D. X•1=X 2D. X•0=0 3D. X•X=X

❒ nulo (elementos

...