VALORES Y VECTORES CARACTERÍSTICOS

Sea T: V --> W una transformación lineal. En diversas aplicaciones, resulta útil encontrar un vector v en V tal que Tv y v son paralelos. Es decir, se busca un vector v y una escalar λ tal que

Tv = λv (1)Si v ≠ 0 y λ satisface a (1), entonces λ se denomina un valor característico de T y v un vector característico de T correspondiente al valor característico λ. El propósito de este trabajo es investigar las propiedades de los valores característicos y vectores característicos. Si V tiene dimensión finita, entonces T se puede representar por una matriz A. Por esta razón se estudiaran los valores y los vectores característicos de las matrices de n x n.

DEFINICION DE VALOR CARACTERÍSTICO Y VECTOR CARACTERÍSTICO

Sea A una matriz de n x n con componentes reales. El número λ(real o complejo) se denomina valor característico de A si existe un vector diferente de cero v en Cn tal que

Av = λv (2)El vector v ≠ 0 se denomina vector característico de A correspondiente al valor característico λ.Nota: Los valores y vectores característicos también se denominan valores y vectores impropios o eigenvalores y eigenvectores; la palabra “eigen” es la palabra alemana para “propio”.Ejemplo:Valores característicos y vectores característicos de una matriz de 2 x 2.

Sea A = [10 −186 −11]. Entonces A[21] = [10 −18

6 −11] [21] = [21]. Así, λ1 = 1 es un valor

característico de A con el correspondiente vector característico v1 = [21]. De manera similar, A[32] = [10 −18

6 −11] [32] = [−6−4 ] = -2[32] de modo que λ2 = -2 es un valor

característico de A con el correspondiente vector característico v2 = [32]. Teorema 1Sea a una matriz de n x n. Entonces λ es un valor característico de A si y solo si

p(λ¿ = det (A – λ I ) = 0 (4)

ECUACION Y POLINOMIOS CARACTERISTICOS

La ecuación (4) se denomina la ecuación característica de A; p(λ¿ se denomina el polinomio característico de A.Como será evidente en los ejemplos, p(λ¿ es un polinomio de grado n en λ. Por ejemplo, si

A = [a bc d ], entonces A – λ I = [a b

c d ] - [ λ 00 λ] = [a−λ 0

0 d−λ ] y p(λ¿ = det (A – λ I ) =

(a – λ)(d - λ) – bc = λ2 – (a + d)λ + (ad – bc).De acuardo con el teorema fundamental del algebra, cualquier polinomio de grado n con coeficientes reales o complejos tienen exactamente n raíces. Esto significa, por ejemplo, que el polinomio (λ – 1)5 tiene cinco raíces, todas iguales al numero 1. Como cualquier valor característico de A es una raíz de la ecuación característica de A, se concluye que

Contando multiplicidades, toda matriz de n x nTiene exactamente n valores característicos.

CALCULO DE VALORES Y VECTORES CARACTERISTICOS

Ejemplo

Sea A = [4 23 3] . Entonces det (A – λ I ) = [4−λ 2

3 3−λ] = (a – λ)(3 – λ) – 6 = λ2 - 7λ + 6 =

(λ – 1)(λ – 6). Entonces los valores característicos de A son λ1 = 1 y λ2 = 6.

Para λ1 = 1 se resuelve (A – I)v = 0 o [3 23 2] [x 1

x 2] = [00]. Es claro que cualquier vector

característico correspondiente a λ1 = 1 satisface 3x1 + 2x2 = 0. Un vector característico de

este tipo es v1 = [ 2−3].

Así E1 = gen[ 2−3].

De manera similar, la ecuación (A – 6 I)v =0 significa que [−2 23 −3 ][ x1

x2] = [00] o x1 = x2.

Entonces v2 = [11] es un vector característico correspondiente a λ2 = 6 y E6 = gen [11].Observe que v1 y v2 son linealmente independientes ya que uno no es múltiplo del otro.

MATRICES SEMEJANTES Y DIAGONALIZACION

Definición de matrices semejantesSe dice que dos matrices A y B de n x n son semejantes si existe una matriz invertible C de n x n tal que

B = C-1 AC (1)

La función definida pro (1) que lleva la matriz A en la matriz B se denomina transformación de semejanza. Se puede escribir esta transformación lineal como

T(A) = C-1 ACDefinición alternativa de semejanzaA y B son semejantes si y solo si existe una matriz invertible c tal que

CB = ACEjemplo

Sean A = [2 10 −1], B = [4 −2

5 −3] y C = [ 2 −1−1 1 ].

Entonces CB = [ 2 −1−1 1 ] [4 −2

5 −3] = [3 −11 −1] y AC = [2 1

0 −1][ 2 −1−1 1 ] = [3 −1

1 −1]Así. CB =AC. Como det C = 1 ≠ 0, C es invertible. Esto muestra, por la ecuación (2), que A y son semejantes. Definición de matriz diagonalizableUna matriz A de n x n es diagonalizable si existe una matriz diagonal d tal que a es semejante a D.Ejemplo Diagonalizacion de una matriz de 2 x 2

Sea A = [4 23 3]. Se encuentran dos vectores característicos linealmente independientes v1 =

[ 2−3] y v2 = [11]. Después, haciendo C = [ 2 1

−3 1] se encontró que

C-1 AC = 15 [1 −1

3 2 ][ 4 23 3][ 2 1

−3 1] = 15 [5 0

0 30] = [1 00 6]

Que es la matriz cuyas componentes en la diagonal son los valores característicos de A.

MATRIZ DIAGONALIZABLE ORTOGONALMENTE

Se dice que una matriz A de n x n es diagonalizable ortogonalmente si existe una matriz ortogonal Q tal que

Q’AQ = D (9)Donde D = diag(λ 1 , λ 2 , …, λn¿y λ 1 , λ 2 , … λn son valores caracteristicos de A. Recuerde que Q es ortogonal si Q’ =Q-1; por lo tanto (9) se puede escribir como Q-1 AQ = D.Diagonalizacion de una matriz simétrica de 2 x 2 usando una matriz ortogonal

Sea A = [ 1 −2−2 3 ]. Entonces la ecuación característica de A es det (A - λI ) = [1−λ −2

−2 3−λ] =λ2 - 4λ – 1 = 0, que tiene dos raíces λ = (4 ±√20)/2 = (4 ± 2√5)/2 = 2 ±√5. Para λ1 = 2 -√5

se obtiene (A - λI )v = [−1+√5 −2−2 31+√5][ x1

x2] = [00]. Un vector característico es v1 =

[ 2−1+√5 ]

Y v1 = √22+ (−1+√5 )2 = √10−2√5. Por lo tanto

U1 = 1

√10−2√5 [ 2−1+√5]

Después para λ2 = 2 + √5 se calcula (A - λI )v = [−1−√5 −2−2 1−√5][ x1

x2] = [00] y v2 =

[1−√52 ]

Observe que v1 * v2 = 0. Entonces |v2| = √10−2√5 de manera que u2 = 1

√10−2√5 [1−√52 ]

Por ultimo,

Q = 1

√10−2√5 [ 2 1−√5−1+√5 2 ]

Y

Q’ AQ = Q = 1

10−2√5 [ 2 −1+√51−√5 2 ][ 2 1−√5

−1+√5 2 ]=

110−2√5 [ 2 −1+√5

1−√5 2 ][ 4−2√5 −3−√5−7+3√5 4+2√5 ]

= 1

10−2√5 [30−14√5 00 10+6√5] [2−√5 0

0 2+√5]FORMAS CUADRATICAS

Definición de ecuación cuadrática y forma cuadrática1) Una ecuación cuadrática en dos variables sin términos lineales es una ecuación de

la forma

Ax2 + bxy + cy2 =d (1) Donde|a| +|b| + |c| ≠ 0. Esto es, al menos uno de los números a, b y c es diferente de cero.

2) Una forma cuadrática de dos variables es una expresión de la forma

F(x,y) = ax2 + bxy +cy2 (2)Donde |a| +|b| + |c| ≠ 0Es evidente que las ecuaciones y las formas cuadráticas tienen una fuerte relación. Se comenzara el análisis de las formas cuadráticas con un ejemplo sencillo.

Considere la forma cuadrática F(x, y) = x2 -4xy + 3y2. Sean v = [ xy ] y A = [ 1 −2

−2 3 ].Entonces

Av*v = [ 1 −2−2 3 ] [ x

y ]*[ xy ] = [ x−2 y

−2 x+3 y ] [ xy ]

=(x2 -2xy) +(-2xy +3y2) = x2 -4xy + 3y2 = F(x,y)De forma inversa, si A es una matriz simétrica, entonces la ecuación (3) define una forma cuadrática F(x,y) = Av*v.Se puede representar F(x,y) por muchas matrices pero solo por una matriz simétrica. Para

ver esto, sea A = [1 ab 3], donde a + b = -4. Entonces Av*v = F(x,y). Si, por ejemplo, A =

[ 1 3−7 3], entonces Av = [ x+3 y

−7 x+3 y ] y Av*v = x2 -4xy + 3y2. Sin embargo, si insistimos en

que A sea simétrica, entonces debe tenerse a + b = -4 y a = b. Este par de ecuaciones tiene una solución única a = b -2.Si F(x,y) =ax2 + bxy + cy2 es una forma cuadrática, sea

A = [ a b/2b/2 c ] (4)

Entonces

Av*v = [ a b/2b/2 c ] [ x

y ]*[ xy ] = [ax+( b

2 ) y

( b2 )x+cy ]*[ x

y ] = ax2 + bxy +cy2 =F(x,y)

Se regresa ahora a la ecuación cuadrática (1). Usando (3), se puede escribir (1) comoAv*v = d (5)

Donde A es simétrica.

TEOREMA DE CAYLEY –HAMILTON

Toda matriz cuadrada satisface su propia ecuación característica. Es decir, si p (λ) = 0 es la ecuación característica de A, entonces P(A) = 0. Se tiene

P (λ) = det(A-λI ) =

Es claro que cualquier cofactor de (A - λI ) es un polinomio en λ. Así, la adjunta de A - λI es una matriz de n x n en la que cada componente es un polinomio en λ. Es decir

adj(A - λI ) =

Esto significa que se puede pensar en adj (A - λI ) como en un polinomio, Q (λ¿, en λ cuyos coeficientes son matrices de n x n. Para entender esto, se ve lo siguiente:

[−λ2−2λ+1 2 λ2−7 λ−44 λ2+5 λ−2 −3 λ2−λ+3 ] = [−1 2

4 −3] λ2 +[−2 −7

5 −1 ] λ + [ 1 −4−2 3 ]

det (A - λI )I = [adj (A -λI )][A - λI ] = Q (λ¿(A - λI )(5)

pero det (A -λI )I = p(λ¿ I . Sip(λ¿ = λn + an-1 λn-1 + … + a1λ + a0

Entonces se define

a11 - λ a12 … a1n

a21 a22 -λ … a2n

: : :an1 an2 … anm - λ

p11 (λ¿ p12 (λ¿ … p1n (λ¿p21 (λ¿ p22 (λ¿ … p2n (λ¿: : :pn1 (λ¿ pn2 (λ¿ … pnm (λ¿

p(λ¿ = p(λ¿ I = λnI + an-1 λn-1I + … + a1λI + a0IPor lo tanto, de (5) se tiene p(λ¿ = Q(λ)(A - λI ). Por ultimo, P(A) = 0.Esto completa la prueba.Aplicación del teorema para calcular A-1

Sea A = [1 −1 43 2 −12 1 −1]. Entonces p(λ) = λ3 - 2λ2 +5λ + 6. Aquí n = 3, a2 = -2, a1 = -5, a0 = 6

y

A-1 = 16

(-A2 + 2A + 5I)

= 16 {[−6 −1 −1

−7 0 −11−3 1 −8 ]+[2 −2 8

6 4 −24 2 −2]+[5 0 0

0 5 00 0 5]} =

16 [ 1 −3 7

−1 9 −131 3 −5 ]

Observe que se calculo A-1 haciendo solo una división y calculando solo un determinante (al encontrar p(λ¿ = det(A - λI )). Este método en ocasiones es muy eficiente al implementarlo en una computadora.

APLICACIONES MÁS USADAS DE LOS VALORES Y VECTORES CARACTERÍSTICOS:

Las matrices pueden aplicarse para elaborar modelos que describan el crecimiento de alguna población en clases de edad de la misma duración.Si el tiempo que vive un miembro de la población es L años entonces las clases de edad se representan por los n siguientes intervalos:

Numero en la clase de primera edad.

Numero en la clase de segunda edad.Numero en la clase de la n-esima edad.Durante un periodo de L/n años, la probabilidad de que un elemento de la clase de la i-esima edad sobreviva para convertirse en elemento de laclase de la (i + 1) –esima edad está dada por pi, donde

Al multiplicar esta matriz de transición de edades por el vector de distribución de edades durante un periodo especifico seobtiene el vector de distribución de edades para el siguiente periodo. Es decir:Axi = xi+1

Ejemplo:Una población de conejos criados en un laboratorio tiene las siguientes características:

a) La mitad de conejos sobrevive el primer año. De estos, la mitad sobrevive el segundo año. La duración máxima de vida es de tres años.

b) Durante el primer año los conejos no producen descendencia. El número medio de descendencia es 6 durante el segundo año y 8 durante el tercer año.Actualmente la población de laboratorio consta de 24 conejos en la clase de la primera edad 24 en la segunda y 20 en la tercera. ¿Cuántos habrá en cada clase de edad en un año?Solución:El vector actual de distribución de edades es

Si el patrón de crecimiento continúa durante otro año, entonces la población de conejos será:

A partir de los vectores de distribución de edades x1, x2, x3 se observa que el porcentaje de conejos en las tres clases de edad cambia cada año.

EJERCICIOS:

1.- Use la matriz A de transición de edades y el vector x de distribución de edades para encontrar los vectores de distribución de edades x2 y x3. Luego encuentre una distribución de edades estable para la matriz dada.

Ahora encontramos una distribución de edades estables. Para ello encontramos los valores propios.

2.- Use la matriz A de transición de edades y el vector x1, de distribución de edades para encontrar los vectores de distribución de edades x2, x3.3.- Encuentre una distribución de edades estable para la matriz de transición de edades del ejercicio anterior.

Solo trabajamos con el valor propio positivo, y encontramos el vector propio:

4.- Una población presenta las siguientes características: a. Un total del 75% de la poblacion sobrevive el primer año. De este 75%, el 25%

sobrevive el segundo año. La duración máxima de vida es de 3 años. b. El numero medio de de descendencia de cada miembro de la población es 2 el primer

año, 4 el segundo y 2 el tercero.Actualmente la población consta de 120 elementos en cada una de las tres clases de edad. ¿Cuántos habrá en cada clase de edad en un año? ¿Y en dos años?Solución:Primero formamos la matriz de transición de edades y el vector de distribución de edades a partir de los datos:

Habrá 960 individuos en la primera clase de edad, 90 en la segunda y 30 en la tercera.Si el patrón de crecimiento no se altera, entonces el vector de distribución de edades será:

Habrá 2340 individuos en la primera clase de edad, 720 en la segunda y 22 en la tercera.5.- Una población de conejos criados en un laboratorio tiene las siguientes características:

a) La mitad de conejos sobrevive el primer año. De estos, la mitad sobrevive el segundo año. La duración máxima de vida es de tres años.

b) Durante el primer año los conejos no producen descendencia. El número medio de descendencia es 6 durante el segundo año y 8 durante el tercer año.Actualmente la población de laboratorio consta de 24 conejos en la clase de la primera edad 24 en la segunda y 20 en la tercera. ¿Cuántos habrá en cada clase de edad en un año?Solución:Primero tomamos la matriz de transición de edades y el vector de distribución de edades con los datos del problema.

Al cabo de un año en la primera clase de edad habrá 304 conejos, en la segunda clase de edad habrán 12 conejos, y de igual manera en la tercera clase.

NOCIONE S SOBRE

A ́ LGEBRA DE BOOLE

DEFINICI ́ ON Y PROPIEDADES GENERALES

El ´algebra de Boole es una estructura matem´atica que, como tal, abarca un abanico de situaciones cuya componente comu´n es la que se formula en su definici´on.

En particular, el ´algebra de Boole tiene aplicaci´on en la s´ıntesis de redes de conmutacion, en el estudio de circuitos digitales y en el an´alisis y progra- maci´on mediante ordenador.

Definici´on de ´algebra de BooleUn conjunto B dotado de dos leyes de composici´on interna (suma y producto)tiene estructura de ´algebra de Boole si se verifican las propiedades siguientes.

(1) Las dos leyes son asociativas.

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

(a b) c = a (b c) ∀ a, b, c ∈ B

(2) Las dos leyes son conmutativas.

a + b = b + a

a b = b a ∀ a, b ∈ B

(3) Cada ley tiene elemento neutro.

∃ 0 ∈ B / a + 0 = a ∀ a ∈ B

∃ 1 ∈ B / a 1 = a ∀ a ∈ B

(4) Para cada elemento a ∈ B existe un u´nico elemento a ∈ B, llamado complementario de a, tal que

a + a = 1

a a = 0

(5) Cada ley es distributiva respecto a la otra.

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

a + (b c) = (a + b) (a + c) ∀ a, b, c ∈

B

Estos cinco pares de propiedades se consideran propiedades primitivas que caracterizan la estructura de ´algebra de Boole. Tambi´en reciben el nombre de axiomas del ´algebra de Boole. El resto de propiedades se deduce a partir de ´estas.

Ejemplos de ´algebras de Boole

(1) Consideremos un conjunto U al que nos referiremos como universo.Llamamos conjunto de las partes del conjunto U al conjunto formado por todos los subconjuntos del conjunto U ; lo denotamos por P(U ).Si el nu´mero de elementos de U es card U = n entonces card P(U ) = 2n. Todo conjunto P(U ) con las operaciones uni´on de conjuntos, ∪, e in- tersecci´on de conjuntos, ∩, tiene estructura de ´algebra de Boole.

El elemento neutro de la uni´on de conjuntos es el conjunto vac´ıo,

∅,mientras que el neutro de la intersecci´on es el conjunto universo U . El elemento complementario de cualquier subconjunto A ∈ P(U ) es elcomplementario en el sentido de conjuntos:

A = { x ∈ U / x 6∈ A }

(2) Una proposici´on l´ogica es un enunciado declarativo que puede ser ver- dadero o falso, pero no ambas cosas a la vez. El conjunto de las proposi-ciones l´ogicas con las operaciones disyunci´on (o, ∨) y conjunci´on (y, ∧)tiene estructura de ´algebra de Boole.

(3) El ´algebra de Boole binaria, formada u´nicamente por dos elementos:

B = { 0, 1 }

Principio de dualidad del ´algebra de Boole

Toda propiedad que pueda deducirse de las propiedades primitivas o de cualquier otra propiedad derivada de ´estas da lugar a otra propiedad que se obtiene intercambiando:

- las operaciones suma y producto,

- los s´ımbolos 0 y 1.

La propiedad as´ı obtenida recibe el nombre de propiedad dual de la inicial.

El principio de dualidad es consecuencia de la propia estructura de ´algbra

deBoole, ya que cada par de propiedades en su definici´on est´a formada por unay por su dual.

Propiedades en un ´algebra de Boole

Las siguientes propiedades son consecuencia de las propiedades primitivas.

(1) Involuci´on. x = x, ∀ x ∈ B.(2) Idempotencia. x + x = x, x x = x, ∀ x ∈ B. (3) x 0 = 0, x + 1 = 1, ∀ x ∈ B.

x + x y = x(4) Absorci´on. x (x + y) = x

∀ x, y ∈ B.

(5) Los neutros son rec´ıprocamente complemetarios. 0 = 1, 1 =

0. (6) x + x y = x + y, x (x + y) = x y, ∀ x, y ∈ B.

(1a Ley) x + y = x y(7) Leyes de De Morgan. ∀ x, y ∈ B.

(2a Ley) x y = x + y

Demostraci´on

(1) Basta comprobar que x hace el papel de complemetario de x.

x + x = x + x = 1 ∧ x x = x x = 0

Las dos primeras igualdades se deducen de las respectivas conmutativas y las dos segundas de la propiedad del complemetario. En consecuencia, x = x. (2) Para demostrar la propiedad x + x = x, ∀ x ∈ B, escribimos:

x + x = (x + x) 1 = (x + x) (x + x) = x + (x x) = x + 0 = x

La primera igualdad se deduce de la propiedad del neutro, la segunda del complemetario, la tercera de la distributiva de la suma respecto al producto, la cuarta del complemetario y la quinta del neutro.

La propiedad x x = x es la dual de la anterior y queda demostrada por el principio de dualidad. Podemos efectuar su desarrollo observando que en cada paso se emplea la propiedad dual, con lo que el resultado es precisamente la propiedad dual de la demostrada.

x x = x x + 0 = x x + x x = x (x + x) = x 1 = x

(3) Las propiedades x 0 = 0, x + 1 = 1, ∀ x ∈ B, son una la dual de la otra.Para demostrarlas podemos escribir:

x 0 = x 0 + 0 = x 0 + x x = x (0 + x) = x x = 0

x + 1 = (x + 1) 1 = (x + 1) (x + x) = x + (1 x) = x + x = 1

Las dos primeras igualdades son consecuencia de la propiedad del neutro, las dos segundas del complementario, las dos terceras derivan de la distributiva, las dos cuartas del neutro y las dos u´ltimas nuevamente del complemetario.

(4) Actuamos an´alogamente para las leyes de absorci´on.

x + x y = x 1 + x y = x (1 + y) = x 1 = x

x (x + y) = (x + 0) (x + y) = x + (0 y) = x + 0 = x

Las dos primeras igualdades se derivan de la propiedad del neutro, las dos segundas de la distributiva, las dos terceras de la propiedad (3) y las dos cuartas otra vez del neutro.

(5) Las propiedades 0 = 1 y 1 = 0 se deducen de la propiedad (3) segu´n la cual 0 + 1 = 1 y 0 1 = 0 y ´esta es la condici´on para que un elemento sea el complementario del otro.

(6) Se cumplen las siguientes cadenas de igualdades:

x + x y = (x + x) (x + y) = 1 (x + y) = x +

y x (x + y) = x x + x y = 0 + x y = x y

Otra vez una propiedad es la dual de la otra. Las dos primeras igualdades provienen de la propiedad distributiva, las dos segundas del complementario y las dos terceras del elemento neutro.

(7) Demostramos la 1a ley de De Morgan, x + y = x y, lo cual equivale a probar que se cumplen las dos igualdades siguientes:

(i) x + y + x y = 1 (ii) (x + y) (x y) = 0

Probamos (i):

x + y + x y = [(x + y) + x] [(x + y) + y] = [(x + x) + y] [x + (y + y)] =

= [1 + y] [x + 1] = 1 1 = 1

+ 0 101

0 11 1

0 101

0 00 1

Probamos (ii):

(x + y) (x y) = [x (x y)] + [y (x y)] = (x x) y + (y y) x =

= 0 y + 0 x = 0 + 0 = 0

En ambos casos, las primeras igualdades son consecuencia de la propiedad distributiva, las segundas de las propiedades asociativa y conmutativa, las terceras del complementario y las cuartas de la propiedad (3).

La 2a ley de De Morgan, x y = x + y, es la dual de la 1a ley y queda demostrada en virtud del principio de dualidad.

Tabla de las operaciones en el ´algebra de Boole binaria

Empleando las propiedades del neutro en cualquier ´algebra de Boole y la propiedad de idempotencia, podemos completar las tablas de las operaciones

en B = { 0, 1 }.

Operaciones derivadas en un ´algebra de Boole

• Diferencia si m ́ etrica XOR

x ⊕ y = x y + x y = (x + y) (x + y)

Propiedades(1) x ⊕ y = y ⊕ x(2) x ⊕ (y ⊕ z) = (x ⊕ y) ⊕ z(3) x ⊕ 0 = x(4) x ⊕ x = 0(5) x (y ⊕ z) = (x y) ⊕ (x z)

• O p eraci ́ on de Sheffer NAND

x | y = x y = x + y

Propiedades (1) x | x = x (2) x | y = x y

(3) x | y = x + y

• Op eraci´on de Pierce NOR

x ↓ y = x + y = x y

Propiedades(1) x ↓ x = x(2) x ↓ y = x + y(3) x ↓ y = x y

F unciones bo oleanas en el ́ algebra de B o ole binaria

Consideramos a partir de ahora el ´algebra de Boole binaria B = { 0, 1 } y denotamos mediante Bn el producto cartesiano de B por s´ı mismo n veces.

Bn = B × B × · · · × B = {(x1, x2 , . . . , xn) / xi ∈ {0, 1}, i = 1, . . . , n, }

Los elementos de Bn son n−plas de elementos de B, es decir, sucesiones de0’s y 1’s cuyo nu´mero total es n.Funci´on booleana en B = { 0, 1 }Llamamos funci´on booleana definida en B = { 0, 1 } o funci´on de conmutacion l´ogica a toda aplicaci´on

f : Bn → B

de manera que f (x1, x2, . . . , xn) pueda expresarse a partir de las operaciones definidas en B efectuadas sobre las variables x1, x2, . . . , xn.

Ejemplos

f : B2 → B definida por f (x1, x2) = x1 + x2

g : B2 → B definida por g(x1, x2) = x1 x2

Tablas de valores o tablas de verdad

Toda funci´on booleana en B = { 0, 1 } puede representarse mediante tablas de valores o tablas de verdad. Las n primeras columnas permiten representarlos 2n elementos de Bn y la columna final indica el valor asignado por la funci´on f a cada n−pla (x1, x2, . . . , xn).

Ejemplo

Tablas de verdad de algunas funciones binarias (de dos variables) definidas en B = { 0, 1 }.

x1 x2

ORx1 + x2

ANDx1 x2

XORx1 ⊕ x2

NANDx1 | x2

NORx1 ↓ x2

0 00 11 01 1

0111

0001

0110

1110

1000

El ´algebra de Boole binaria de los interruptores

Un interruptor instalado en un circuito el´ectrico es un mecanismo que pro- duce dos respuestas: permite o impide el paso de la corriente el´ectrica.

Se puede pensar en el conjunto de respuestas de un interruptor como en los elementos de un ´algebra de Boole binaria B = { 0, 1 }, asociando valor 1 a lavariable que denota el interruptor en caso de permitir el paso de la corriente y valor 0 en caso de impedir el paso de la misma.

x toma valor 0 x toma valor 1

La suma de dos variables x, y asociadas a interruptores corresponde a la instalaci´on de ambos interruptores en paralelo. El interruptor asociado a

lasuma x + y ofrece respuesta 0 respuesta 0.

u´nicamente en el caso en que x, y ofrecen

x

x + y y

x y x + y0 00 11 01 1

0111

n

Por su lado, el producto de dos variables x, y asociadas a interruptores corresponde a la instalaci´on en serie. El interruptor asociado al producto x y u´nicamente ofrece respuesta 1 si x, y ofrecen respuesta 1.

x y x y

x y x y0 00 11 01 1

0001

Nu´mero de funciones booleanas en el ´algebra de Boole binaria

Para el ´algebra de Boole binaria B = { 0, 1 }, el nu´mero de funciones de nvariables f : Bn → B resulta ser igual al nu´mero de variaciones con repetici´onde 2 elementos tomados de 2n en 2n.

El nu´mero de elementos en el conjunto Bn es 2n y para cada uno de estos elementos una funci´on f definida sobre B = { 0, 1 } puede tomar valor 0 ovalor 1. Entonces,

card{ f / f : Bn → B} = RV2,2n = 2(2 )

Para n = 2, el nu´mero de funciones de conmutaci´on l´ogica de dos variables es 24 = 16; para n = 3, el nu´mero de funciones de tres variables es 28 = 256; para n = 4, el nu´mero de funciones de cuatro variables es 216

= 65536.

Tablas de las funciones booleanas de dos variables

A continuaci´on se ofrecen las tablas de las 16 funciones de conmutacion l´ogica de dos variables. Junto a cada tabla se encuentra una expresi´on simplificada de la f´ormula en t´erminos de las operaciones suma, producto y complemen- tario.

x1 x2 f0

0 00 11 01 1

0000

x1 x2 f1

0 00 11 01 1

0001

x1 x2 f2

0 00 11 01 1

0010

x1 x2 f3

0 00 11 01 1

0011

x1 x2 f4

0 00 11 01 1

0100

x1 x2 f5

0 00 11 01 1

0101

x1 x2 f6

0 00 11 01 1

0110

x1 x2 f7

0 00 11 01 1

0111

x1 x2 f8

0 00 11 01 1

1000

x1 x2 f9

0 00 11 01 1

1001

x1 x2 f10

0 00 11 01 1

1010

x1 x2 f11

0 00 11 01 1

1011

f0 = 0f1 = x1 x2

AND

f2 = x1 x2 f3 = x1

f4 = x1 x2 f5 = x2

f6 = x1 x2 + x1x2

f6 = x1 ⊕ x2

XOR

f7 = x1 + x2

OR

f8 = x1 x2 = x1 ↓ x2

NORf9 = x1 x2+x1 x2

f10 = x2 f11 = x1 +x2

x1 x2 f12

0 00 11 01 1

1100

x1 x2 f13

0 00 11 01 1

1101

x1 x2 f14

0 00 11 01 1

1110

x1 x2 f15

0 00 11 01 1

1111

1 2 n · · ·

f12 = x1 f13 = x1 +x2

f14 = x1 + x2 = x1|x2

NANDf15 = 1

Definici´on de maxterm y de mintermB = { 0, 1 } denota el ´algebra de Boole binaria.En Bn el producto de n variables diferentes, complementadas o no, recibe el nombre de minterm o t´ermino m´ınimo.

En Bn la suma de n variables diferentes, complementadas o no, recibe el nombre de maxterm o t´ermino m´aximo.

Ejemplo

En B4 son minterms x1 x2 x3 x4 x1 x2 x3 x4

En B3 son maxterms x1 + x2 + x3 x1 + x2 + x3

Propiedad(1) Toda funci´on booleana f : Bn → B puede ser expresada como

suma de minterms (suma de productos). Esta expresi´on es la que se conoce como forma canonica disyuntiva de la funci´on f .

f (x1, x2, . . . , xn) =

X

xδ1

xδ2

· · ·

xδn

xδi

=

½ xi

1 2 n i xi

(2) Toda funci´on booleana f : Bn → B puede ser expresada como productode maxterms (producto de sumas). Esta expresi´on es la que se conocecomo forma canonica conjuntiva de la funci´on f .

f (x , x , . . . , x ) =

Y

(xδ1

+ xδ2

+ + xδn

) xδi

=

½ xi

1 2 n i xi

De las dos formas can´onicas la m´as empleada es la forma disyuntiva.

Propiedad

(1) Las formas can´onicas de una funci´on booleana f : Bn → B son u

´nicas. (2) Dos funciones booleanas son equivalentes (son la misma funci

´on) si ys´olo si tienen las mismas formas can´onicas.

Obtenci´on de las formas can´onicas

1. Obtenci ́ on a partir de la tabla de v alores de la funci ́ on

La forma can´onica disyuntiva de una funci´on f : Bn → B se obtiene a partir de cada uno de los valores 1 que toma la funci´on. La u´nica forma en la que un producto de todas las variables (o sus complementarios) toma valor 1 es con todos sus factores tomando valor 1. As´ı el nu´mero de minterms en laforma disyuntiva es igual al nu´mero de 1’s en la tabla de valores de f .

Por su lado, la forma can´onica conjuntiva de una funci´on f : Bn → B se obtiene a partir de cada uno de los valores 0 que toma la funci´on. La u´nica posibilidad para que una suma de todas las variables (o sus complementarios) tome valor 0 es con todos sus t´erminos tomando valor 0. El nu´mero demaxterms en la forma conjuntiva es igual al nu´mero de 0’s en la tabla de valores de f .

Para una funci´on f : Bn → B, la suma del nu´mero de minterms en la forma can´onica disyuntiva y el nu´mero de maxterms en la forma can´onica conjuntivaes igual a 2n, que es el cardinal de Bn.

Ejemplo

Obtenci´on de las formas can´onicas disyuntiva y conjuntiva de la funci´onf : B3 → B cuya tabla de valores es

x1 x2 x3 f

0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1

10110011

f (x1, x2, x3) = x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3

Forma can´onica conjuntiva:

f (x1, x2, x3) = (x1 + x2 + x3) (x1 + x2 + x3) (x1 + x2 + x3 )

Nu´mero de minterms: 5. Nu´mero de maxterms: 3. Total: 5 + 3 = 8 = 23.

2. Obtenci ́ on a partir de una expresi ́ on en f ́ or m ula

Para obtener la forma can´onica disyuntiva a partir de una expresi´on cual- quiera conviene, en una primera aproximaci´on, obtener una suma de produc- tos, aunque estos productos no sean minterms. La propiedad que en mayor medida permite esta aproximaci´on es la distributiva del producto respecto a la suma.

Una vez obtenida la suma de productos, cada variable xj que no figure en un producto se puede an˜adir al mismo multiplicando por 1 en la forma

1 = xj + xj

A continuaci´on se vuelve a aplicar la propiedad distributiva.

Para la forma can´onica conjuntiva se requiere transformar la expresi´on inicial en producto de sumas. En este proceso juega un papel esencial la propiedad distributiva de la suma respecto al producto.

Una vez obtenido el producto de sumas, cada variable xj que no figure en una suma se puede an˜adir a la misma sumando 0 en la forma

0 = xj xj

A continuaci´on se vuelve a aplicar la propiedad distributiva.

En ambos procedimientos, despu´es de multiplicar por 1 o sumar 0 y aplicar la distributiva, se debe eliminar los minterms o maxterms repetidos empleando la popiedad de idempotencia.

Ejemplo

Obtenci´on de las formas can´onicas disyuntiva y conjuntiva de la funci´onf : B3 → B definida por f (x, y, z) = x + y z.

f (x, y, z) = x (y + y) (z + z) + (x + x) y z

= x y z + x y z + x y z + x y z + x y z + x y z

= x y z + x y z + x y z + x y z + x y z

En este caso, la f´ormula inicial ya era suma de productos. En el primer sumando se ha hecho aparecer las variables y, z, mientras que en el segundo se ha an˜adido x. Despu´es de aplicar la propiedad distributiva se ha comprobado que el primer y el u´ltimo minterm estaban repetidos y se ha eliminado uno de ellos.

Forma can´onica conjuntiva:

f (x, y, z) = (x + y) (x + z)

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

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

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

En primer lugar se ha aplicado la distributiva de la suma respecto al producto para obtener un producto de sumas. En el primer sumando se ha an˜adido la variable z y en el segundo la variable y. Es importante an˜adir las variables en el orden que figuran en la funci´on, x y z. De esta manera la simplificaci´on de maxterms es m´as sencilla, tal y como ha sucedido con el primer y el tercer maxterm que estaban repetidos.

Ejemplo

Obtenci´on de las formas can´onicas disyuntiva y conjuntiva de la funci´onf : B4 → B definida por f (x, y, z, w) = (x + y) (z + w) (x +

z).

Forma can´onica disyuntiva:

f (x, y, z, w) = x z x + x z z + x w x + x w z + y z x + y z z + y w x + y w z

Despu´es de aplicar la propiedad distributiva del producto respecto a la suma ha aparecido una suma de ocho productos. De entre ´estos, el primero, el segundo, el tercero y el sexto son nulos, pues en ellos aparece una expresi´on del tipo x x ´o z z que es igual a 0 por la propiedad del

complementario. Los cuatro productos restantes se escriben con sus variables en el orden dado por la funci´on, x y z w.

f (x, y, z, w) = x z w + x y z + x y w + y z w

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

= x y z w + x y z w + x y z w + x y z w + x y z w + x y z w +

+ x y z w + x y z w

Los minterms segundo y s´eptimo, cuarto y quinto as´ı como sexto y octavo est´an repetidos. Por la idempotencia, eliminamos uno de cada pareja y obte- nemos la forma can´onica disyuntiva de f con 5 minterms:

f (x, y, z, w) = x y z w + x y z w + x y z w + x y z w + x y z w

Forma can´onica conjuntiva:

f (x, y, z, w) = (x + y + z z + w w) (x x + y y + z + w) (x + y y + z + w w)

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

w) (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z

+ w) (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y

+ z + w)

La expresi´on inicial de la funci´on ya es un producto de sumas. En cada sumando hemos an˜adido en la posici´on correspondiente las variables que faltan en la forma x x, y y, z z ´o w w. Despu´es de aplicar la propiedad dis- tributiva aparecen los maxterms, observando que el segundo y el sexto est´an repetidos. Una vez eliminado uno de ellos se obtiene la forma can´onica con-juntiva de f con los esperados 11 maxterms, ya que card B4 = 24 = 16 y enla forma can´onica disyuntiva obtuvimos 5 minterms.

f (x, y, z, w) = (x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z +

w) (x + y + z + w) (x + y + z + w) (x + y + z + w)

(x + y + z + w) (x + y + z + w) (x + y + z + w) (x + y + z + w)

BIBLIOGRAFÍA

http://www.dcb.unam.mx/users/normapla/ValoresVectoresCaracteristicos.pdf

http://www.monografias.com/trabajos14/algebra-booleana/algebra-booleana.shtml

http://galia.fc.uaslp.mx/~uragani/algebra1/Textos/Algebra_Boole.pdf

http://cursos.aiu.edu/Algebra%20Lineal/PDF/Tema%206.pdf

http://es.slideshare.net/encinamarisel/notas-de-algebra-lineal

http://es.slideshare.net/encinamarisel/notas-de-algebra-lineal

http://www.monografias.com/trabajos14/algebra-booleana/algebra-booleana.shtml#teo