Blog informativo
de
Matematicas Discretas
por
Angel Emmanuel Ruiz Alcaraz
6° V
Ingenieria en sistemas
lunes, 8 de diciembre de 2014
1. SISTEMAS NUMÉRICOS
1. SISTEMAS NUMÉRICOS
Los sistemas numéricos son muy importantes en computación, aquí veremos los sistemas en base
2, 8 y 16 que son las que más se utilizan en computación; por supuesto con la relación entre la
base 10 que es la que utilizamos los seres humanos.
SISTEMAS DE NUMERACIÓN Un sistema de numeración es un conjunto de símbolos y reglas
que se utilizan para representar los números.
Dependiendo del sistema en particular el manejo y las operaciones pueden resultar muy simples o
muy complicadas, por tal razón en computación se manejan sistemas posicionales de bases que
sean potencias de 2, ya que los algoritmos para las operaciones son los más simples.
Los sistemas de numeración usados en la actualidad son posicionales. El valor de una cifra
depende tanto de qué dígito es como de la posición que ocupa en el número.
Base. Es el número de símbolos distintos que se utiliza para representar un número en un sistema
de numeración. Entonces decimos que el sistema de numeración es de esa base. Los símbolos de
una determinada base van desde el 0 hasta la base −1.
Coeficiente. El coeficiente determina el valor de cada símbolo dependiendo de la posición que
ocupe con respecto al punto decimal. Por lo tanto a estos sistemas de numeración los llamaremos
sistemas de numeración posiciónales, porque el valor de cada cifra dependerá del valor absoluto
del símbolo y de la posición relativa que ocupa con respecto al punto decimal.
Empezamos por representar números enteros en una base b. Los símbolos utilizados son
{0,1,2,3,…,b-1} si b es menor o igual a 10, en caso de ser mayor podemos utilizar las letras A, B,
C, … después del 9 o algún otro símbolo que se defina previamente. Como los sistemas que se
utilizan por lo general no pasan de base 16, con las letra A, B, C, D, E y F es suficiente.
En un sistema de numeración de base n existen n símbolos. Al escribir un número en base n, el
dígito d en la posición i, de derecha a izquierda, tiene un valor
En general, un número escrito en base n como dmdm − 1…d2d1 tiene un valor
Número: Idea que representa la cantidad de elementos de un conjunto. Sentido Semántico.
Numeral: Símbolo que se usa para representar un número. Sentido Sintáctico.
Así en el caso anterior se tienen varios numerales para un sólo número.
El numeral es a nivel sintáctico, esto es, símbolos utilizados para representar el número que es al
nivel semántico: idea ó significado que representa dicho símbolo.
Por ahora utilizaremos el sistema indo-arábigo para representar los enteros, o sea
= {1, 2, 3,…}
= {0, 1, 2, 3…}
Pero también se utilizará el español. Así, por ejemplo: 7 y siete representan la misma idea.
La fundamentación de los números enteros se puede hacer de acuerdo a Peano y tiene dos
ventajas, primero se formaliza matemáticamente y segundo se consideran como entes sintácticos,
que pueden ser manejados en computación.
Así definimos 0 como la cardinalidad del conjunto vacío, 1 como la cardinalidad de un conjunto
que contenga un elemento. 2 como la cardinalidad de un conjunto que contenga dos elementos.
Obviamente los números naturales no son suficientes para realizar los problemas que se presentan
y es necesario otro conjunto mayor. El de los números enteros, este conjunto aparece cuando se
presenta el siguiente problema:
X + 5 = 3
Que aparece en casos como el siguiente: “Oye sobrino, cómo es que en la bodega hay 3 toneladas
si envié 5, deberían de tener 5 más lo que había “, el problema es que se debían 2, contesta el
sobrino.
De cualquier manera matemáticamente el problema planteado está dado por:
X+5 = 3
Cuya solución requiere de un tipo de número llamado: los enteros negativos. Así llegamos a los
enteros
Z = {…,−3, −2, −1, 0, 1, 2, 3,…}
1.1 Sistemas numéricos
1.1 Sistemas numéricos (binario, octal, decimal, hexadecimal).
El sistema decimal. El sistema de numeración decimal es un sistema posicional. La base del
sistema de numeración decimal es 10 y está formado por los dígitos del 0 al 1. Un número en el
sistema de numeración decimal lo podemos definir según el teorema fundamental de la
numeración de la siguiente forma. Numero b= x0b0+ x1b1 + x2b2 + …. + xn-1bn-1 xi = cifras b
= datos n = número de cifras
El sistema binario. El sistema binario o sistema de numeración en base 2 es también un sistema
de numeración posicional igual que el decimal, pero sólo utiliza dos símbolos, el “0” y el “1”. Por
lo tanto para poder representar mayor número de información al tener menos símbolos tendremos
que utilizar más cifras § Cuarteto: Número formado por 4 cifras en base 2 § Bit: Bynary digit §
Byte: 8 bits § Kilobyte: 1024 bytes § Megabyte: 1024 kilobytes § Gigabyte: 1025 megabytes
Binario puro
El método de representación de enteros del binario puro consiste en pasar el número entero
sin signo a binario, con la particularidad de respetar siempre el tamaño de la representación.
El paso de decimal a binario consiste en dividir por 2 sucesivamente hasta que el cociente sea
menor que la base:
Con lo que queda 1110 = 10112
Sistema Octal. Es un sistema de base 8, es decir, con tan solo ocho dígitos posibles, „0‟ a „7‟.
El paso de octal a decimal se realiza multiplicando cada dígito por su peso: 278 = 2 ·81 + 7 · 80 =
2310 El paso inverso consiste en dividir por la base (8):
Con lo que queda 678 = 10310
Sistema Hexadecimal. Sin embargo el sistema de numeración más utilizado es el hexadecimal, el
cual consta de 16 dígitos diferentes (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E y F). El paso de
hexadecimal a decimal es análogo a los anteriores: 12316 = 1 · 162 + 2 · 161
+ 3 · 160
= 29110 Al
igual que el paso de decimal a hexadecimal:
Con lo que queda 29110 = 12316 Los 16 valores posibles de una variable hexadecimal son:
1.2 Conversiones entre Sistemas
1.2 Conversiones entre Sistemas
1.2.1 Decimal a Binario Octal y Hexadecimal
Para poder manejar los números en la computadora es necesario entender cómo seconvierta de una base a otra.
Para convertir de base 10 a binario el algoritmo resulta muy sencillo, se divide entre 2 y se
anota el cociente bajo el número y el residuo a la derecha, se aplica iterativamente este
procedimiento hasta llegar a 0 y al final el resultado es la cadena de bits de abajo hacia arriba.
Ejemplo 1: Convertir a binario 49
Por lo tanto 49= 110001 base 2
Ejemplo 2. Convertir 123 a binario:
Por lo tanto 123= 1111011 base 2
Convertir de decimal a octal
Ejemplo: Convertir 381 a base 8.
Por lo tanto 381= 575 base 8
Similarmente para convertir un número en base 10, a base 16 dividimos entre 16
aplicando el algoritmo que se utilizó en base 2 y en base 8, en este caso si el residuo es mayor de
9 se utilizan las letras A, B, C, D, E y F.
Por lo tanto 4325= 10E5 base 16
1.3 Operaciones básicas.
1.3 Operaciones básicas.
Recordemos los algoritmos para efectuar las operaciones básicas:
Adición
76.512
+
149.83
----------------
226.342
Sustracción
628.420
-
555.405
----------------
73.015
Multiplicación
42.5
x 6.7
-------------
2975
2550
-----------
284.75
Recuerde una prueba para verificar si la operación está bien hecha.
42.5 Sumando los dígitos obtenemos: 11 módulo 9 queda: 2
× 6.7 Sumando los dígitos obtenemos: 13 módulo 9 queda: 4
---------------
2975
2550 Multiplicando los dígitos anteriores da 4 x 2 = 8
-----------
284.75 Sumando los dígitos obtenemos: 26 módulo 9 queda 8
y por ser igual al producto anterior la multiplicación es correcta.
Sistema binario.
Recordemos que la representación de un número en el sistema posicional es una cadena
de símbolos básicos los cuales se forman de acuerdo a la base.
Para no confundir los números a la representación en otra base distinta de diez se le
escribirá dicha base al terminar el numeral que representa el número.
Ejemplo: 2468 significa que está en base 8.
43025 significa que está en base 5.
10100112 significa que está en base 2.
La base que se va a utilizar, por ahora, es la base 2, tiene la ventaja de que utiliza sólo dos
símbolos, llamados bits. Conjunto de bits {0,1}.
A la representación en base 2 se le llama también representación binaria.
Ejemplo: 100112 = 1 x 2^4
+ 0 x 2^3
+ 0 x 2^2
+ 1 x 2^1
+ 1 x 2^0
= 16 + 2 + 1 = 19
( al no aparecer base la base indicada, significa base 10)
110.10112 = 1 x 2^2
+ 1 x 2^1
+ 0 x 2^0
+ 1 x 2^–1
+ 0 x 2^–2
+ 1 x 2^–3
+ 1 x 2–^4
= 4 + 2 + 0 + .5 + .125 + .0625 = 6.6825
Para representar un número que está en base 10 en sistema binario, deberá agruparse de
dos en dos (en lugar de diez en diez que fue lo que se hizo en el sistema decimal).
Por ejemplo, analicemos el número 7
Si agrupa en pares se tienen tres pares y una unidad, si se agrupan en pares de duplos se
obtiene un par y un duplo \ 7 = 1112
Para entender mejor el sistema binario considere unas celdas donde se pueden escribir los
símbolos 0 ó 1 (bits) y piense que cada celda tiene un valor dado por la siguiente figura:
Así el número 100112 lo analizamos
y su representación en base 10 es 16 + 2 + 1 = 19.
Para convertir de base 10 a binario el algoritmo resulta muy sencillo, se divide entre 2 y se
anota el cociente bajo el número y el residuo a la derecha, se aplica iterativamente este
procedimiento hasta llegar a 0 y al final el resultado es la cadena de bits de abajo hacia arriba.
Ejemplo 1: convertir a binario 49
Ejemplo 2. Convertir 123 a binario:
Como en el sistema binario sólo hay 2 dígitos la adición y la multiplicación resultan muy
simples:
Apliquemos el procedimiento de la suma que usamos en el sistema decimal ya que
también los algoritmos son similares:
Algoritmos de División
Igual que en el producto, la división es muy fácil de realizar, porque no son posibles en el
cociente otras cifras que UNOS y CEROS.
Consideremos el siguiente ejemplo, 42 : 6 = 7, en binario:
Se intenta dividir el dividendo por el divisor, empezando por tomar en ambos el mismo número
de cifras (100 entre 110, en el ejemplo). Si no puede dividirse, se intenta la división tomando un
dígito más (1001 entre 100).
Si la división es posible, entonces, el divisor sólo podrá estar contenido una vez en el dividendo,
es decir, la primera cifra del cociente es un UNO. En ese caso, el resultado de multiplicar el
divisor por 1 es el propio divisor. Restamos las cifras del dividendo del divisor y bajamos la cifra
siguiente.
El procedimiento de división continúa del mismo modo que en el sistema decimal.
2. CONJUNTOS
2. CONJUNTOS
Características de los conjuntos.
DEFINICIÓN: La palabra conjunto generalmente la asociamos con la idea de agrupar
objetos, por ejemplo un conjunto de discos, de libros, de plantas de cultivo y en otras ocasio nes
en palabras como hato, rebaño, piara, parcelas, campesinado, familia, etc., es decir la palabra
conjunto denota una colección de elementos claramente entre sí, que guardan alguna
característica en común. Ya sean números, personas, figuras, ideas y conceptos.
En matemáticas el concepto de conjunto es considerado primitivo y ni se da una
definición de este, sino que se trabaja con la notación de colección y agrupamiento de objetos, lo
mismo puede decirse que se consideren primitivas las ideas de elemento y pertenencia.
La característica esencial de un conjunto es la de estar bien definido, es decir que dado un
objeto particular, determinar si este pertenece o no al conjunto. Por ejemplo si se considera el
conjunto de los números dígitos, sabemos que el 3 pertenece al conjunto, pero el 19 no. Por otro
lado el conjunto de las bellas obras musicales no es un conjunto bien definido, puesto que
diferentes personas puedan incluir distintas obras en el conjunto.
Los objetos que forman un conjunto son llamados miembros o elementos. Por ejemplo el
conjunto de las letras de alfabeto; a, b, c, ..., x, y, z. que se puede escribir así:
{ a, b, c, ..., x, y, z}
Como se muestra el conjunto se escribe entre llaves ({}) , o separados por comas (,).
El detallar a todos los elementos de un conjunto entre las llaves, se denomina forma
tabular, extensión o enumeración de los elementos.
Dos conjuntos son iguales si tienen los mismos elementos, por ejemplo:
El conjunto { a, b, c } también puede escribirse:
{ a, c, b }, { b, a, c }, { b, c, a }, { c, a, b }, { c, b, a }
En teoría de conjuntos se acostumbra no repetir a los elementos por ejemplo:
El conjunto { b, b, b, d, d } simplemente será { b, d }.
NOTACIÓN: Los conjuntos se denotan por letras mayúsculas : A, B, C,... por ejemplo:
A={ a, c, b } B={ primavera, verano, otoño, invierno }
El símbolo indicará que un elemento pertenece o es miembro de un conjunto. Por el
contrario para indicar que un elemento no pertenece al conjunto de referencia, bastará cancelarlo con una raya inclinada / quedando el simbolo como
Ejemplo: Sea B={ a, e, i, o, u }, a
B y c B
B y c B 2.1 Conjunto universo, vacío
2.1 Conjunto universo, vacío
UNIVERSO O CONJUNTO UNIVERSAL: El conjunto que contiene a todos los elementosa los que se hace referencia recibe el nombre de conjunto Universal, este conjunto depende del
problema que se estudia, se denota con la letra U y algunas veces con la letra S (espacio
muestral).
Por ejemplo si solo queremos referirnos a los 5 primeros números naturales el conjunto
queda:
U={ 1, 2, 3, 4, 5 }
Forma alternativa para indicar conjuntos de gran importancia:
Conjunto de números naturales (enteros mayores que cero) representados por la letra N
donde
N={ 1, 2, 3, .... }
Conjunto de números enteros positivos y negativos representados por la letra Z donde
Z={..., -2, -1, 0, 1, 2, ... }
Conjunto de números racionales (números que se representan como el cociente de dos
números enteros {fracciones }). Estos números se representan por una Q
Conjunto de números irracionales (números que no puedan representarse como el cociente
de dos números enteros) representados por la letra I.
Conjunto de los números reales que son los números racionales e irracionales es decir
todos, representados por R.
Todos estos conjuntos tienen un número infinito de elementos, la forma de simbolizarlos
por extensión o por enumeración es de gran utilidad cuando los conjuntos a los que se hace referencia tienen pocos elementos para poder trabajar con ellos se emplean la notación llamada
comprensión.
Por ejemplo, la denotar el conjunto de los números naturales menores que 60. Aquí U es
el conjunto N y se tiene una propiedad que caracteriza a los elementos del conjunto: ser menores
que 60.
Para indicar esta situación empleamos la simbología del álgebra de conjuntos:
{ x/x E N ; x<60 }
En esta expresión se maneja un conjunto de x que pertenece a los números naturales (N) y
además que los valores de x son menores que 60.
Ahora si se desea trabajar con conjuntos que manejen intervalos estos pueden ser
representados por medio de una expresión algebraica; supongamos que se desea expresar los
números enteros (Z) entre -20 y 30 el conjunto quedaría de la manera siguiente:
{ x/x E Z ; -20 E x E 30 }
También se puede expresar el valor de un conjunto indicando la pertenencia o no
pertenencia a uno diferente, por ejemplo
L={ 1, 3, 4, 6, 9 }
P={ x/x E N ; X E L }
En el conjunto P se indica que los elementos x de un conjunto pertenecen a los números
naturales y además x no pertenece al conjunto L.
CONJUNTO VACÍO: Es un conjunto que carece de elementos. Se suele llamarle
conjunto nulo, y se le denota por el símbolo ø o { }.
Ejemplos:
A = { Los perros que vuelan }
A
= { }
A
= Ø
B = { x / x
es un mes que tiene 53 días}
B
= { }
B
= Ø
C = { x / x3
= 8 y x es impar }
C
= { }
C
= Ø
D = { x / x
es un día de 90 horas }
D
= { }
D
= Ø
2.2 Operaciones con conjuntos
2.2 Operaciones con conjuntos (Unión, Intersección, Complemento, Diferencia
y diferencia simétrica)
UNIÓN:
La unión de dos conjuntos A y B la denotaremos por A v B y es el conjunto formado
por los elementos que pertenecen al menos a uno de ellos ó a los dos. Lo que se denota por:
AvB = { x/xE A ó xE B }
Ejemplo: Sean los conjuntos A={ 1, 3, 5, 7, 9 } y B={ 10, 11, 12 }
A v B ={ 1, 3, 5, 7, 9, 10, 11, 12 }
INTERSECCIÓN
Sean A={ 1, 2, 3, 4, 5, 6, 8, 9 } y B={ 2, 4, 8, 12 }
Los elementos comunes a los dos conjuntos son: { 2, 4, 8 }. A este conjunto se le llama
intersección de A y B; y se denota por A ^ B, algebraicamente se escribe así:
A ^ B = { x/x E A y xE B }
Y se lee el conjunto de elementos x que están en A y están en B.
Ejemplo:
Sean Q={ a, n, p, y, q, s, r, o, b, k } y P={ l, u, a, o, s, r, b, v, y, z }
Q ^ P={ a, b, o, r, s, y }
CONJUNTO VACÍO
Un conjunto que no tiene elementos es llamado conjunto vacío ó conjunto nulo lo que denotamos
por el símbolo 0 .
por ejemplo:
Sean A={ 2, 4, 6 } y B={ 1, 3, 5, 7 } encontrar A ^ B.
A ^B= { }= 0
El resultado de A ^ B= { } muestra que no hay elementos entre las llaves, si este es el caso se le
llamará conjunto vacío ó nulo y se puede representar como: A ^ B=0
CONJUNTOS AJENOS
Sí la intersección de dos conjuntos es igual al conjunto vacío, entonces a estos conjuntos les
llamaremos conjuntos ajenos, es decir:
Si A ^ B = 0 entonces A y B son ajenos.
COMPLEMENTO
El complemento de un conjunto respecto al universo U es el conjunto de elementos de U que no
pertenecen a A y se denota como A' y que se representa por comprensión como:
A'={ x E U/x y x E A }
Ejemplo:
Sea U = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }
A= { 1, 3, 5, 7, 9 } donde A c U
El complemento de A estará dado por:
A'= { 2, 4, 6, 8 }
DIFERENCIA
Sean A y B dos conjuntos. La diferencia de A y B se denota por A-B y es el conjunto de los
elementos de A que no están en B y se representa por comprensión como:
A - B={ x/xE A ; X E B }
Ejemplo:
Sea A= { a, b, c, d } y
B= { a, b, c, g, h, i }
A - B= { d }
En el ejemplo anterior se observa que solo interesan los elementos del conjunto A que no estén en
B. Si la operación fuera B - A el resultado es
B – A = { g, h, i }
E indica los elementos que están en B y no en A.
2.3 Diagrama de Venn
2.3 Diagramas de Venn:
Es una representación de las clases o conjuntos mediante círculos que seintersectan.
Por ejemplo: Sean las clases:
C1: los profesores
C2: los humanos
C3: los buenos docentes
Para poder representar un diagrama de Venn se necesita de un razonamiento de la siguiente forma
(tomando como base las clases):
Los diagramas sirven, en ocasiones, para visualizar las operaciones que se pueden realizar con
conjuntos a si el universo se representa mediante rectángulos y los conjuntos que se extraen
mediante curvas cerradas.
Los diagramas de Venn son útiles para determinar la validez de razonamientos relacionados con
proposiciones categóricas.
Sean los siguientes argumentos
Todos los profesores son humanos
Todos los buenos docentes son humanos
Por lo tanto, Todos los profesores son buenos docentes
Podemos presentar el razonamiento en la forma:
Todo C1 es C2
Todo C3 es C2
Por lo tanto Todo C1 es C3
El diagrama de Venn Que representa la hipótesis se representa:
Considere la región que tiene la marca palomeada, como esta región no está sombreada, no es
vacía necesariamente, es decir pueden haber elementos de C1 que no estén en C3. Por lo tanto la
conclusión no es correcta por lo que El razonamiento es falso.
3 ALGEBRA BOOLEANA
3 ALGEBRA BOOLEANA
El álgebra booleana es un sistema matemático deductivo centrado en los valores cero yuno (falso y verdadero). Un operador binario “ º “ definido en éste juego de valores acepta un par
de entradas y produce un solo valor booleano, por ejemplo, el operador booleano AND acepta
dos entradas booleanas y produce una sola salida booleana. Para cualquier sistema algebraico
existen una serie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y
otras propiedades del sistema,
Teoremas y postulados.
Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si
para cada par de valores booleanos se produce un solo resultado booleano.
Conmutativo. Se dice que un operador binario “ º “ es conmutativo si A º B = B º A para
todos los posibles valores de A y B.
Asociativo. Se dice qu un operador binario “ º “ es asociativo si (A º B) º C = A º (B º C)
para todos los valores booleanos A, B, y C.
Distributivo. Dos operadores binarios “ º “ y “ % “ son distributivos si A º (B % C) = (A º
B) % (A º C) para todos los valores booleanos A, B, y C.
Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un
operador binario “ º “ si A º I = A.
Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano
“ º “ si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A.
Para nuestros propósitos basaremos el álgebra booleana en el siguiente juego de
operadores y valores: - Los dos posibles valores en el sistema booleano son cero y uno, a menudo
llamaremos a éstos valores respectivamente como falso y verdadero. El símbolo · representa la
operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminará el
símbolo ·, por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el producto entre A y B. - El símbolo “+” representa la operación lógica
OR, decimos que A + B es la operación lógica OR entre A y B, también llamada la suma de A y
B. El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el
símbolo “ ¬ “ para denotar la negación lógica, por ejemplo, ¬ A denota la operación lógica NOT
de A.
Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la
expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis,
operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico
AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia
están adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es
asociativo por la derecha. Utilizaremos además los siguientes postulados:
P1 El álgebra booleana es cerrada bajo las operaciones AND, OR y NOT
P2 El elemento de identidad con respecto a · es uno y con respecto a + es cero. No existe
elemento de identidad para el operador NOT
P3 Los operadores * y + son conmutativos.
P4 * y + son distributivos uno con respecto al otro, esto es, A*(B+C) = (A*B)+(A*C) y A+(B*C)
= (A+B)*(A+C).
P5 Para cada valor A existe un valor ¬A tal que A*¬A = 0 y A+¬A = 1. Éste valor es el
complemento lógico de A.
P6 * y + son ambos asociativos, esto es, (AB)C = A(BC) y (A+B)+C = A+(B+C).
Es posible probar todos los teoremas del álgebra booleana utilizando éstos postulados, además es
buena idea familiarizarse con algunos de los teoremas más importantes
Hemos dicho que los circuitos digitales trabajan con números, y que estos números se
expresan en binario. Veremos más adelante cómo con un conjunto de ecuaciones podemos
describir lo que hace un circuito, que transforma los números de la entrada y por otros que obtenemos en la salida. Sin embargo, puesto que estos números vienen expresados en binario, las
variables y números utilizados NO SON REALES.
Para describir un circuito digital utilizaremos ecuaciones
Para describir un circuito digital utilizaremos ecuaciones matemáticas. Sin embargo,
estas ecuaciones tienen variables y números que NO SON REALES, por lo que NO podemos
aplicar las mismas propiedades y operaciones que conocemos. Hay que utilizar nuevas
operaciones y nuevas propiedades, definidas en el ALGEBRA DE BOOLE.
Por tanto, vamos a trabajar con unas ecuaciones a las que NO estamos acostumbrados.
Son muy sencillas, pero al principio pueden resultar poco intuitivas. En este capítulo
aprenderemos a trabajar con ellas.
Las operaciones del Álgebra de Boole
En el Álgebra de Boole hay dos operaciones, denotadas con los símbolos + y * pero que
¡¡no tienen nada que ver con las operaciones que todos conocemos de suma y producto!!.
¡¡¡No hay que confundirlas!!!!. El + y el * del Algebra de Boole se aplican a bits, es decir, a
números que sólo pueden ser el ’0’ ó el ’1’.
La operación +
Esta operación se define de la siguiente manera:
0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Las tres primeras operaciones nos resultan obvias, son iguales que la suma que
conocemos, sin embargo la expresión 1 + 1 = 1 nos puede resultar chocante. ¿¿Pero no me
habían dicho toda la vida que 1+1=2??, nos podemos estar preguntando. Sí, pero hay que
recordar que aquí estamos utilizando otra operación que NO ES LA SUMA, la denotamos con el
mismo símbolo ‟+‟, ¡¡pero no es una suma normal!! ¡¡Hay que cambiar el “chip”!! ¡¡Ahora
estamos con Algebra de Boole!!
Pasado el pánico inicial, si nos fijamos en esta nueva operación, notamos lo siguiente: El
resultado siempre es igual a ’1’ cuando alguno de los bits sumandos es igual a ’1’. O lo que
es lo mismo, El resultado de esta suma sólo da ’0’ si los dos bits que estamos sumando son
iguales a cero. En caso contrario valdrá ‟1‟.
¿Y para qué nos sirve esta operación tan extraña? Veamos un ejemplo. Imaginemos que
hay una sala grande a la que se puede acceder a través de dos puertas. En el techo hay una única
lámpara y existen dos interruptores de luz, uno al lado de cada puerta de entrada. Como es lógico,
la luz se enciende cuando algunos de los dos interruptores (o los dos) se activan. Esto lo
podemos expresar mediante una ecuación booleana. Para denotar el estado de uno de los
interruptores utilizaremos la variable booleana A, que puede valor ‟0‟ (Interruptor apagado) ó
‟1‟ (interruptor activado). Para el otro interruptor usaremos la variable B. Y para el estado de la
luz, ‟0‟ (apagada) y ‟1‟ encendida, usaremos la variable F.
El estado en el que se encuentra la luz, en función de cómo estén los interruptores viene
dado por la ecuación booleana:
F = A +B que indica que F=1 (Luz encendida) si alguno de los interruptores está a ‟1‟
(activado).
Ya lo veremos más adelante, pero podemos ir adelantando unas propiedades muy
interesantes.
Si A es una variable boolena, se cumple:
A + A = A
1 + A = 1
0 + A = A
La operación * Esta operación se define así:
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1
En este caso, la operación es más intuitiva, puesto que es igual que el producto de
números Reales. Si nos fijamos, vemos que el resultado sólo vale ’1’ cuando los dos bits están
a ’1’, o visto de otra manera, el resultado es ’0’ cuando alguno de los dos bits es ’0’.
Vamos a ver un ejemplo. Imaginemos una caja de seguridad de un banco que sólo se abre
cuando se han introducido dos llaves diferentes, una la tiene el director y la otra el jefe de
seguridad. Si sólo se introduce una de ellas, la caja no se abrirá. Modelaremos el problema así.
Utilizaremos la variable A para referirnos a una de las llaves (‟0‟ no introducida, ‟1‟
introducida) y la variable B para la otra llave. Con la variable F expresamos el estado de la caja
de seguridad (‟0‟ cerrada y ‟1‟ abierta). El estado de la caja lo podemos expresar con la ecuación:
F = A*B que indica que la caja se abrirá (F=1) sólo si A=1 (una llave introducida) y B=1 (la otra
llave introducida). En cualquier otro caso, F=0, y por tanto la caja no se abrirá.
Podemos ir adelantando algunas propiedades de esta operación:
A*A=A
A*0=0
A*1=A
La negación
La operación de negación nos permite obtener el estado complementario del bit o variable
booleana al que se lo aplicamos. Se define de la siguiente manera:
Es decir, que si se lo aplicamos a ‟0‟ obtenemos ‟1‟ y si se lo aplicamos al ‟1‟ obtenemos
‟0‟. Esta operación nos permite cambiar el estado de una variable booleana. Si A es una variable
boolena, Ā tiene el estado contrario.
3.4 Mapas de Karnaugh
3.4 Mapas de Karnaugh
Un mapa de Karnaugh (también conocido como tabla de Karnaugh o diagrama de Veitch, abreviado como Mapa-K o Mapa-KV) es un diagrama utilizado para la simplificación de funciones algebraicas Booleanas. El mapa de Karnaugh fue inventado en 1950 por Maurice Karnaugh, un físico y matemático de los laboratorios Bell, famosos por sus patentes.
Los mapas de Karnaugh reducen la necesidad de hacer cálculos extensos para la simplificación de expresiones booleanas, aprovechando la capacidad del cerebro humano para el reconocimiento de patrones y otras formas de expresión analítica, permitiendo así identificar y eliminar condiciones redundantes.
El mapa de Karnaugh consiste en una representación bidimensional de la tabla de verdad de la función a simplificar. Puesto que la tabla de verdad de una función de "n" variables posee 2 elevado a "n" filas, el mapa K correspondiente debe poseer también 2 elevado a "n" cuadrados. Las variables de la expresión son ordenadas en función de su peso y siguiendo el código Gray, de manera que sólo una de las variables varía entre celdas adyacentes. La transferencia de los términos de la tabla de verdad al mapa de Karnaugh se realiza de forma directa, albergando un 0 ó un 1, dependiendo del valor que toma la función en cada fila. Las tablas de Karnaugh se pueden utilizar para funciones de hasta 6 variables.
Existe software de caracter gratuito que te ayudará a comprobar los resultados de tus simplificaciones. Para descargarlo basta con que sigas el siguiente enlace.
Los mapas de Karnaugh reducen la necesidad de hacer cálculos extensos para la simplificación de expresiones booleanas, aprovechando la capacidad del cerebro humano para el reconocimiento de patrones y otras formas de expresión analítica, permitiendo así identificar y eliminar condiciones redundantes.
El mapa de Karnaugh consiste en una representación bidimensional de la tabla de verdad de la función a simplificar. Puesto que la tabla de verdad de una función de "n" variables posee 2 elevado a "n" filas, el mapa K correspondiente debe poseer también 2 elevado a "n" cuadrados. Las variables de la expresión son ordenadas en función de su peso y siguiendo el código Gray, de manera que sólo una de las variables varía entre celdas adyacentes. La transferencia de los términos de la tabla de verdad al mapa de Karnaugh se realiza de forma directa, albergando un 0 ó un 1, dependiendo del valor que toma la función en cada fila. Las tablas de Karnaugh se pueden utilizar para funciones de hasta 6 variables.
Existe software de caracter gratuito que te ayudará a comprobar los resultados de tus simplificaciones. Para descargarlo basta con que sigas el siguiente enlace.
Aquí tienes un vídeo donde puedes seguir el proceso de simplificación, paso a paso:
4. RELACIONES
Conceptos básicos.
Las relaciones son muy importantes en matemáticas y sobretodo en computación, pues
vienen a ser una herramienta fundamental en Bases de Datos, Programación, etc.; casi en
cualquier tópico de una u otra forma se utiliza el concepto de relación. El término relación es
muy amplio y se puede conceptualizar en términos muy generales, pero la idea central es muy
simple y entendiendo el concepto se puede aplicar en cualquier situación por diversa que sea.
Una relación es una asociación entre elementos u objetos, generalmente de dos conjuntos
arbitrarios. Una manera de formalizar el concepto y al mismo tiempo hacerlo práctico para usarse
en computación es considerar una relación como un conjunto de pares ordenados. Esto se puede
extender posteriormente a tuplos para definir relaciones de varios elementos.
Primeramente empezaremos por el concepto de producto cartesiano entre Conjuntos
.
A diferencia de un conjunto en un par ordenado (a,b), importa el orden de los elementos. Si se
consideran los conjuntos A y B y formamos parejas o pares ordenados con los elementos de A
como primeros elementos y los de B como segundos, se obtiene un conjunto llamado producto
cartesiano. Esto es:
Definición. A x B = {(a,b) : a ε A, b ε B }
Ejemplo: A= {1,2,5}, B = {2,3}
A x B = {(1,2),(1,3),(2,2),(2,3),(5,2),(5,3)}
Con el producto cartesiano podemos establecer la definición formal de relación.
Definición. Una relación R de A a B es un subconjunto de A x B. Los elementos de A que
aparecen en la relación forman el dominio y los de B forman el rango.
Notación: R ε A X B
DOM(R) = {x : (x,y) ε R }
RAN(R) = {y : (x,y) ε R }
O sea que una relación de A a B es un conjunto de pares ordenado, donde los primeros elementos
pertenecen al conjunto A y los segundos a B.
Definición. La relación inversa de una relación R^-1 de A a B es la que se obtiene si invertimos
el orden en las parejas.
R^-1= { (y,x) : (x,y) ε R }
Observamos que la relación inversa es una relación de B a A.
Ejemplos.
Si A = {a,b,c,x,y,z}, B = {1,2,3,4,5}
R1= {(a,2),(c,2),(x,1),(y,5),(z,5)}
R2= {(a,1),(a,5),(c,3),(x,2),(x,4)}
R3= {(a,4),(b,2),(c,5),(x,1)}
R4= {(a,3),((b,1),(b,5),(c,3),((c,5),(x,1),(y,4)}
4.1 Propiedades de las Relaciones
Propiedades de las Relaciones
Las relaciones se pueden clasificar de acuerdo al tipo de asociación que hay en sus
elementos como: uno-a-uno 1–1, uno-a-mucho 1-M, muchos-a-uno M-1 o muchos-a-muchos M-M
Recordemos que una relación es un conjunto de pares ordenados.
Definición: Una relación R de A a B es: Muchos-a-uno, M-1 si existen dos pares con el mismo
segundo elemento, esto es existen (x,y), (z,y) distintas en la relación.
Uno-a-muchos 1-M si existen dos pares con el mismo primer elemento, esto es existen (x,y),
(x,z) distintas en la relación.
Muchos-a-muchos M-M si es muchos-a-uno y uno-a-muchos. O sea que hay al menos dos
pares con el mismo primer elemento y también hay dos pares con el mismo segundo elemento. O
sea que cumple las dos definiciones anteriores.
Uno-a-uno 1–1 si no es muchos-a-uno ni uno-a-muchos, o sea que no hay dos pares con el
mismo primer elemento y no hay dos pares con el mismo segundo elemento. Esto significa que
cumple las dos condiciones siguientes
Representación matricial: Una relación entre dos conjuntos A y B puede ser
representada por una matriz binaria, que consiste en 0′s y 1′s. Asociamos cada elemento del
primer conjunto A con un renglón de la matriz y cada elemento del segundo conjunto B con una
columna de la matriz. Los elementos deben estar ordenados. En el correspondiente lugar del
renglón y columna asociada a un par de elementos el valor es 1 si el par ordenado está en la
relación y 0 si el par no está.
Ejemplo: Si A = {a,b,c,d}, B = {1,2,3} y la relación
R = {(a,2), (a,3), (b,1), (d,2)} entonces la matriz es
La representación matricial nos da otra forma de poder manejar una relación y es muy útil
sobretodo cuando la cantidad de elementos en los conjuntos es pequeña, también nos sirven para
reconocer fácilmente que propiedades tiene una relación sobre un conjunto como se ve en la
siguiente sección.
Relaciones Sobre un Conjunto
Cuando la relación es entre elementos del mismo conjunto, o sea que el conjunto B es igual a A,
entonces decimos que es una relación en A.
Definición Una relación R en A puede ser
Reflexiva: Si todo elemento en A está relacionado consigo mismo.
Irreflexiva: Si ningún elemento en A está relacionado consigo mismo.
Simétrica: Si cuando un elemento está relacionado con un segundo elemento, el segundo
también se relaciona con el primero.
Antisimétrica: Si cuando un elemento está relacionado con un segundo elemento diferente, el
segundo no se relaciona con el primero.
Transitiva: Si cuando un elemento está relacionado con un segundo elemento y el segundo está
relacionado con un tercero, entonces el primero está relacionado con el tercero: Observamos que
las relaciones en un conjunto tienen una matriz cuadrada asociada y esta juega un papel muy
importante para determinar las propiedades anteriores.
Suscribirse a:
Entradas (Atom)