ESTRUCTURAS DISCRETAS : marzo 2021

martes, 9 de marzo de 2021

CONJUNTO ESTRUCTURA

La noción de conjunto es aceptada como sinónimo de las nociones usual de colección,agrupación de objetos, etc. Los objetos de un conjunto se llaman: miembros o elementos, sinembargo, de éstos dos términos el más usado es “elemento”. Cuando nos referimos a los objetos que componen un conjunto A, entonces usamos lapalabra elementos del conjunto A, se escribe: x ∈ A. Que se puede leer también "x pertenece a A" o "x está en A". Si por el contrario, un objetox no es elemento de un conjunto A, se escribe: x ∉ A. Un conjunto se puede definir haciendo la presentación efectiva de cada uno de suselementos, así el conjunto A cuyos elementos son 2, 3, 5, se escribe: A = { 2, 3, 5} Los conjuntos se denotan por letras mayúsculas: A, B, C,... por ejemplo: A= {a, c, b} B= {primavera, verano, otoño, invierno}
3. 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 símbolo como ∉. Ejemplo: Sea B= {a, e, i, o, u}, a є B y c ∉ Bo CARACTERITICAS DE LOS CONJUNTOS1. Conjunto unitario: conjunto compuesto de un solo elemento.2. Conjunto vació o nulo: cuando no consta de elementos.3. Conjunto universal: conjunto de elementos por los que se tiene interés4. Si un conjunto tiene elementos y se relaciona con otro se dice que este es subconjunto del otro.5. Por definición el conjunto nulo es subconjunto de cualquier otro conjunto.6. Dos conjuntos son iguales si y solo si contienen los mismo elementos
4. CONJUNTO UNIVERSAL Conjunto que contiene todos los elementos posibles para un problema particular en consideración y contiene a todos los elementos a 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:o Conjunto de números naturales (enteros mayores que cero) representados por la letra N donde N={ 1, 2, 3, .... }o Conjunto de números enteros positivos y negativos representados por la letra Z donde Z={..., -2, -1, 0, 1, 2, ... }o 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 Qo Conjunto de números irracionales (números que no puedan representarse como el cociente de dos números enteros) representados por la letra I.o Conjunto de los números reales que son los números racionales e irracionales es decir todos, representados por R.
5. Todos estos conjuntos tienen un número infinito de elementos, la forma desimbolizarlos por extensión o por enumeración es de gran utilidad cuando losconjuntos a los que se hace referencia tienen pocos elementos para poder trabajarcon 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 elementosdel conjunto: ser menores que 60. Para indicar esta situación empleamos la simbología del álgebra de conjuntos: { x/x Î N ; x<60 } En esta expresión se maneja un conjunto de x que pertenece a losnú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 estospueden ser representados por medio de una expresión algebraica;supongamos que se desea expresar los números enteros (Z) entre -20 y 30el conjunto quedaría de la manera siguiente: { x/x Î Z ; -20 £ x £ 30 }
6. Un conjunto está definido por extensión, si se enumeran sus elementos. Por ejemplo: A = {x / x es un número obtenido al lanzar un dado corriente} es un conjunto definido por comprensión ya que sus elementos “x” se describen a través de una propiedad “es un número obtenido al lanzar un dado corriente”. DIAGRAMA DE VENN Esencialmente, se conoce como una forma de mostrar de manera gráfica, una agrupación de elementos según los conjuntos, siendo representado cada conjunto con una circunferencia. Esta clase de gráficos se emplean en la Teoría de Conjuntos, dentro de las matemáticas modernas y nos explica el funcionamiento de un conjunto de elementos al realizar alguna operación con ellos. La posición en que estén dispuestas las circunferencias, nos mostrará el vínculo queexiste entre los conjuntos
7. En la imagen de abajo, el círculo del grupo A se haya dentro del círculo B, de manera que todos los componentes de B también se encuentran contenidos en A. SUBCONJUNTOSean los conjuntos A={ 0, 1, 2, 3, 5, 8 } y B={ 1, 2, 5 }En este caso decimos que B esta contenido en A, o que B es subconjunto de A. En general si A y B son dosconjuntos cualesquiera, decimos que B es un subconjunto de A si todo elemento de B lo es de A también.Por lo tanto si B es un subconjunto de A se escribe B ∈ A. Si B no es subconjunto de A se indicará con unadiagonal ∉ . Note que ∈se utiliza solo para elementos de un conjunto y ⊂ solo para conjuntos.
8. FÓRMULA:B С A: x €B = x C AС = no está incluido. Э = no contiene a.no es subconjuntoEJEMPLO:- Conjunto de los números reales mayores que -2 y menores o iguales que 3- Conjunto de los números reales mayores o iguales que -1 y menores o iguales que 1.B = -1, 0, 1, 2, 3A = -1, 0, 1A es Subconjunto de B AЭB=BСA
9. PROPIEDADES DE LA INCLUSIÓN1) Reflexiva.- para todo conjunto A se cumple que todo conjunto está incluido a sí mismo. AСA2) Asimétrica.- para todo conjunto A y B se cumple que si A está incluido en B. AСB^BСA=A=B3) Transitiva.- AСB^BСAAСCSi se cumple las 3 propiedades se dice que existe una relación de orden.Si al comparar dos conjuntos y estos no se incluyen entre A y B en este caso se dice que los dosconjuntos no son comparables. El conjunto vacío es el conjunto matemático que no tiene ningún elemento. Se representa con el símbolo ∅ o simplemente como {}. Algunas de sus propiedades son: •Para cualquier conjunto A, el conjunto vacío es un subconjunto de A: {} ⊆ A. •Para cualquier conjunto A, la unión de A y el conjunto vacío es A: A ∪ {} = A. •Para cualquier conjunto A, la intersección de A y el conjunto vacío es el conjunto vacío: A ∩ {} = {}. •El único subconjunto del conjunto vacío es el conjunto vacío.
10. CONJUNTO POTENCIA El conjunto potencia de un conjunto cualquiera A, P(A) es el conjunto formado por todos los subconjuntos de A. Si A tiene n elementos, el conjunto potencia de A tendrá 2n elementos. Otro símbolo para usar ⊆ IGUALDAD DE CONJUNTO Dos conjuntos son iguales el uno al otro scontienen exactamente a los mismos miembros.Indicado matemáticamente A= B si y solamente si A ⊆ By B ⊆ A. Esto significa que si conjunto A contiene todoen el conjunto B y el conjunto B contiene todo adentroconjunto A, después los dos conjuntos tienenexactamente el mismo contenido.
11. OPERACIONES FUNDAMENTALES CON CONJUNTOS.UNIÓN Una interpretación gráfica de la unión de A y B es la La unión de los conjuntos A y siguiente:B, es el conjunto de todos loselementos que pertenecen a A o a Bo a ambos. Se denota la unión de Ay B por A U B y se llama unión de Ay B.Entonces se puede expresar porcomprensión este conjunto así: En la gráfica la región rayada corresponde a la unión de A y B. Se presentan los conjuntos dentro de un rectángulo que representa el conjunto referencial del cual se seleccionan los conjuntos A y B. Podemos decir que la unión de conjuntos es una operación binaria (aquella operación matemática, que precisa del operador y de dos argumentos para que se pueda calcular un valor) en el conjunto de todos los subconjuntos de un U, Conjunto universal (Se denomina así al conjunto formado por todos los elementos del tema de referencia) dado. Mediante la cual a cada par de conjuntos A y B de U le es asociado otro conjunto (A U B) de U.
12. PROPIEDADESSean A, B y C tres conjuntos cualesquierao A ∪ A = A (propiedad idempotente) En álgebra de conjuntos, las operaciones de unión y tambiénde intersección de conjuntos cumplen con esta propiedad. Esto quiere decir que la unión ointersección de un conjunto con el mismo, resultará en el mismo conjunto.o A ∪ B = B ∪ A (propiedad conmutativa). Si se cambia el orden de los conjuntos, el conjuntounión no se altera.o (A ∪ B) ∪ C = A ∪ (B ∪ C) (propiedad asociativa).o (B ∩ C) ∪ A = (B ∪ A) ∩ (C ∪ A) (propiedad distributiva respecto de la intersección).o A ∪ (A ∩ B) = A = A ∩ (A ∪ B) (ley de absorción). INTERSECCIÓN Gráficamente, una representación de A ∩ B es: Una intersección de dos o másconjuntos es un conjunto que contiene alos miembros que están en todos losconjuntos. Se habla esto, “conjunto C esla intersección de los conjuntos A y B.”Escriba esto como, C = A ∩ B. La región rayada corresponde a AB. Cuando A y B no tienen elementos comunes, se dice que son disjuntos.
13. PROPIEDADES DE LA INTERSECCIÓN DE CONJUNTOSo Comutativo A∩B=B∩A La intersección de conjuntos es comutativa.o Asociativo (D ∩ E) ∩ F = D ∩ (E ∩ F) La intersección de conjuntos esasociativao Distributivo (D ∩ E) ∪ F = (D ∪ F) ∩ (E ∪ F)А ∩ (B ∩ C) = (А ∩ B) ∩ C La intersección y la unión de conjuntos son distributivas o Propiedad Conmutativa. А∩B=B∩Аo Propiedad IdempotenteА∩А=А Intersección con el Vacío А∩Ø=Ø
14. Diferencia La diferencia entre los conjuntos A y B, denotada por A - B, es el conjunto formado por loselementos que pertenecen al conjunto de A y no pertenecen al conjunto B.Ejemplo: Sean los conjuntos A = {a, b, c, d, e, f} y B = {a, h, j}. La diferencia A - B es {b, c, d, e,f}. La diferencia B - A es {h, j}Dados dos conjuntos A y B su diferencia simétrica es la unión de la diferencia A - B y B - A.En el ejemplo anterior la diferencia simétrica es {b, c, d, e, f, h, j}PROPIEDADES DE LA DIFERENCIA DE CONJUNTOSo Unicidad: Dados dos conjuntos A y B, el resultado de la diferencia entre los conjuntos A yB es un único conjunto C y no puede ser otro distinto. o Propiedad conmutativa o Propiedad conmutativa:o Elemento neutro: El elemento neutro de la operación diferenciaes el conjunto vacío.
15. COMPLEMENTO Sean los conjuntos A y universal U. El complemento del conjunto A es la parte el conjunto universal U que no pertenece al conjunto A. Sean:PROPIEDADESPuesto que el conjunto universal contiene todos los elementos en consideración, y el conjunto vacíono contiene a ninguno, se tiene lo siguiente:Puesto que la noción de complementariedad está relacionada con la negación en lógica, la primeraposee propiedades similares a la segunda: o Propiedad involutiva. El complementario del complementario de A es el propio A: (A ∁ )∁ = A
16. o La unión de un conjunto y su complementario es el conjunto universal: A ∪ A∁ = Uo Propiedad involutiva. El complementario del complementario de A es el propio A: (A ∁ )∁ = Ao La unión de un conjunto y su complementario es el conjunto universal: A ∪ A∁ = Uo Un conjunto y su complementario son disjuntos: A ∩ A∁ = ∅o El complementario de A está contenido en el complementario de cualquier subconjunto de A: B ⊆ A implica que A∁ ⊆ B∁ ALGEBRA DE CONJUNTOS PROPIEDADES UNION INTERSECCION 1.- Idempotencia A A=A A A=A 2.- Conmutativa A B=B A A B=B A 3.- Asociativa A (B C)=(A B) C A (B C)=(A B) C 4.- Absorción A (A B)=A A (A B)=A 5.- Distributiva A (B C)=(A B) (A C) A (B C)=(A B) (A C) 6.- Complementariedad A A = U A A =
17. (A ∪ B) = A ∩ B Propiedades de identidad o A∪ φ = A o A∪U = U o A∩U = A o A∩φ = φ LEYES DE D’MORGAN Estas leyes establecen los complementos de la unión e intersección entre conjuntos: Primera ley. El complemento de la unión de dos conjuntos es la intersección de sus complementos. En el diagrama de la izquierda, A∪ B viene dada por la región en blanco y (A ∪ B) está representado, por el área sombreada verticalmente. Por su parte en el diagrama de la derecha, A es la región sombreada horizontalmente, B es el área sombreada verticalmente, por lo que A ∩ B está representado por la superficie cuadriculada. Las regiones resultantes son iguales.
18. PRODUCTO CARTESIANO DE DOS CONJUNTOS Uno de los principios básicos para hacer primera componente a un elemento queun análisis matemático es el concepto de pertenezca a A , y como segunda componenteparejas ordenadas: dos objetos, personas, a un elemento que pertenezca a B .símbolos o cosas mencionados en un ordendefinido por su posición, es decir, primero uno El producto cartesiano se denota de lay luego el otro. Si este orden cambiara, es siguiente forma: A× B y se lee “ A cruz B ”.decir, primero el otro y luego el uno, se tendrá A× B = { ( y,x ) x∈ A y y ∈ B }como resultado una nueva pareja ordenada ydiferente a la inicialmente considerada. La definición anterior expresa que el producto cartesiano de los conjuntos A y B , son laLa simbología matemática que se utiliza para parejas ordenadas ( y,x ) tal que x pertenece alrepresentar una pareja ordenada es escribir conjunto A y y pertenece al conjunto B .dentro de un paréntesis, la primeracomponente separada por una coma de lasegunda componente, por ejemplo: ( y,x ) es lapareja ordenada, en donde x es la primeracomponente y y es la segunda componente. Elproducto cartesiano de dos conjuntos A y B esel conjunto de todos los posibles paresordenados que se forman eligiendo como
19. Ejemplo. Obtener el producto cartesiano A× B de los siguientes conjuntos: A = {1,2,3} B = {2,4,6,7 } Solución. A× B = {(1,2),(1,4),(1,6),(1,7),(2,2),(2,4),(2,6),(2,7),(3,2),(3,4),(3,6),(3,7)} El número de parejas ordenadas que resultan de un producto cartesiano se obtienemultiplicando sus cardinalidades. En el ejemplo anterior, η(A) = 3 y η(B) = 4 , el número de parejasordenadas es: (3)(4) = 12. El producto cartesiano no es conmutativo. Esto significa que A × B ≠ B× A , a menos que A = B Ejemplo. . Obtener el producto cartesiano B × A dados los mismos conjuntos anteriores: A = {1,2,3} B = {2,4,6,7 } Solución. B × A = {(2,1),(2,2),(2,3),(4,1),(4,2),(4,3),(6,1),(6,2),(6,3),(7,1),(7,2),(7,3)} A× B ≠ B × A
20. OPERACIONES GENERALIZADAS El concepto de familia indexada de conjunto, permite generalizar las operaciones conconjuntos (unión, intersección, producto cartesiano) que se habían definido para dos conjuntos, alcaso de un número arbitrario de conjuntos. Dada una familia de conjuntos F y un conjunto I, se denomina familia indexada de conjuntoscon conjuntos Índices I a toda función f: I -> F Si I es cualquier conjunto, una familia de conjuntos indizada por I es una colecciónde conjuntos, denotada por {Xi}, donde, para cada i € I, se tiene que Xi es un conjunto miembro dela familia. Entonces la unión de la familia {Xi} es el conjuntos de elementos x tales x pertenece aalguno de los conjuntos Xi. De igual forma, la intersección de la familia es el conjunto de todos los ytales y € Xi, para todos los i € I. De manera simbólica se tiene
21. PARTICIÓN Una partición de un conjunto A es una clase de subconjuntos Sі de A que son colectivamente exhaustivos y mutuamente excluyentes. En otras palabras, los subconjuntos son disjuntos (excluyentes) y su unión es A (exhaustivos). Dado un conjunto A, diremos que los subconjuntos de A, A1,A2, . . . ,An, constituyen una partición del mismo si se cumplen las siguientes condiciones: 1. Ai ≠ Ø; i = 1,2,3,…,n 2 Ai  Aj = Ø; i ≠j,i, j=1,2,3,…,n 3. A1  A2  A3 … = A An Las particiones de conjuntos ya han demostrado ser muy útiles en las cuestiones de Combinatoria: la regla de la suma nos permitirá evaluar el tamaño de un conjunto si lo“partíamos” en subconjuntos (disjuntos dos a dos) cuyo tamaño fuera más fácil de calcular. Sea X un conjunto con n elementos, que supondremos, como hacemos habitualmente, que son los números {1, . . . , n}. Una partición en k bloques no vacios de X será una colecciónde subconjuntos {A1, A2, . . . Ak} , tales que 1. los bloques, efectivamente, conforman una partición de X: X = A1 ∪ · · · ∪ Ak y Ai ∩ Aj = Ø para cada i = j. 2. Y los bloques son no vacíos , esto es, Ai = Ø para cada i = 1, . . . , k. Es importante señalar que el orden de los elementos dentro de cada bloque es irrelevante y elde presentación de los bloques, también. Observemos que, pese a que los nombremos como A1, . . . , Ak, no estamos dando un orden entre ellos.
22. LA CARDINALIDADEs simplemente la forma en que se relacionan las Entidades, o expresa cuantas entidades serelacionan con otras entidades.Hay varias maneras de mostrar las cardinalidades:-Poner etiquetas en las líneas que unen las relaciones con las entidades, consiste en un mínimo ymáximo que contiene un cero (varios a varios) y lo usual es poner una “M” en unExisten 4 tipos de relaciones que pueden establecerse entre entidades, las cuales establecen concuantas ocurrencias de entidad de tipo b se puede relacionar una ocurrencia de entidad de tipo a:Relación uno a uno.Relación uno a varios (n).Relación varios (n) a uno.Relación varios a varios (n)- (n). UNO A UNO Cada registro de la tabla A se relaciona sólo con un registro de una tabla B y cada registro de la tabla B se relaciona sólo con un registro de la tabla A.
23. UNO A VARIOSCada registro de la tabla A está relacionado con varios registros de la tabla B y cada registro de latabla B está relacionado con un sólo un registro de la tabla A. VARIOS A VARIOS Cada registro de la tabla A puede estar relacionado con más de un registro de la tabla B y cada registro de la tabla B puede estar relacionado con más de un registro de la tabla A.
24.

sta asignatura proporciona estructuras matemáticas sobre las que modelizar problemas (preguntas, restricciones, sobre un determinado conjunto de datos). Además facilita los mecanismos deductivos necesarios para construir la solución de tales problemas o para comprobar que una solución dada es cor

Proyección de la asignatura en el plan de estudios

Ésta es una de las tres asignaturas en que se divide la materia "Fundamentos Matemáticos".

Lógica y Estructuras Discretas (1er cuatrimestre, 1er curso, 6 créditos)
Fundamentos Matemáticos (1er cuatrimestre, 1er curso, 6 créditos)
Estadística (2º cuatrimestre, 1er curso, 6 créditos)

Las asignaturas de esta materia son comunes tanto al Grado de Ingeniería Informática como al Grado de Ingeniería de las Tecnologías de la Información. Forman parte del bloque de formación básica de ambas titulaciones.

Esta asignatura facilita los siguientes fundamentos formales comunes:

Facilita estructuras matemáticas sobre las que modelizar datos (conjuntos, relaciones, funciones, árboles, grafos, etc.)
Facilita un lenguaje preciso y universal para especificar restricciones y problemas (preguntas, especificaciones) sobre estos modelos.
Facilita técnicas de construcción y comprobación de soluciones (mecanismos deductivos, inducción y recursión, verificaciones)

Sólo en el primer curso, el estudiante debe poder apreciar el valor instrumental de esta asignatura tanto para la compresión de las otras dos de la misma materia como para la comprensión de otras asignaturas, especialmente:

Fundamentos de Programación
Estrategias de Programación
Estructuras de Datos y Autómatas, Gramáticas y Lenguajes

lunes, 8 de marzo de 2021

PRACTICOS REALIZADOS

ALGEBRA BOOLEANA

ALGEBRA DE BOOLE 1 Introducción. El álgebra de Boole es una herramienta de fundamental importancia en el mundo de la computación. Las propiedades que se verifican en ella sirven de base al diseño y la construcción de las computadoras que trabajan con objetos cuyos valores son discretos, es decir las computadoras digitales, en particular las binarias (en las cuales los objetos básicos tienen solo 2 valores posibles) las que son, en definitiva, la totalidad de las computadoras de uso corriente. Desde ya adelantemos que no se verán aquí detalles formales de la construcción algebraica, ni todas las propiedades que se verifican, así como tampoco todos los métodos de síntesis de funciones booleanas que habitualmente se incluyen en este tema en cursos de lógica y/o diseño lógico. Como toda álgebra, la de Boole parte de un cuerpo axiomático, el cual puede adquirir diversas formas, variando la cantidad y calidad de los axiomas. Aquí en particular tomaremos uno: el propuesto por Huntington en 1904 que tiene la ventaja de ser consistente e independiente. 2 Axiomas. 1. Existe un conjunto G de objetos, sujetos a una relación de equivalencia, denotada por "=" que satisface el principio de sustitución. Esto significa que si a = b, b puede sustituir a a en cualquier expresión que la contenga, sin alterar la validez de la expresión. 2. (a) Se define una regla de combinación "+" en tal forma que a + b está en G siempre que al menos a o b lo estén. (b) Se define una regla de combinación "" en tal forma que a  b está en G siempre que tanto a como b lo estén. 3. Neutros. (a) Existe un elemento 0 en G tal que para cada a de G: a + 0 = a (b) Existe un elemento 1 en G tal que para cada a de G: a  1 = a 4. Conmutativos. Para todo par de elementos a y b pertenecientes a G se cumple: (a) a + b = b + a (b) a  b = b  a 5. Distributivos. Para toda terna de elementos a, b, c pertenecientes a G se cumple: a (a) a + (b  c) = (a + b)  (a + c) b (b) a  (b + c) = a . b + a  c Fing/CETP – Tecnólogo en Informática 1 Arquitectura de Computadoras – Algebra de Boole Notas de Teórico Basadas en las Notas de Teórico Versión 5.0 del Dpto. de Arquitectura-InCo-FIng 6. Complemento. Para cada elemento a de G existe un elemento a tal que: 1 0     a a a a 7. Existen por lo menos dos elementos x, y en G tal que x <> y Existe similitud de muchos de estos postulados con los del álgebra común. Sin embargo, la primera de las reglas distributivas (sobre la suma) y la existencia del complemento diferencian en forma fundamental esta álgebra de la común. 3 Modelo aritmético. El ejemplo más simple del álgebra de Boole se compone de un conjunto G de 2 elementos: "0" y "1". Como es natural estos dos elementos deben coincidir con los neutros de las reglas de combinación para satisfacer el axioma 3. Las reglas de combinación debemos definirlas de manera de satisfacer los axiomas. Así de acuerdo al axioma 3 : de acuerdo al axioma 4 y teniendo presente el axioma 5 : 1 1 1 (por axioma 3) 1 0 (1 1) 1 1 (1 0) (1 1) (1 0) (5a con a 1, b 1, c 0)                0 0 0 (por axioma 3) 0 1 0 0 0 0 (0 1) 0 0 0 1 (5b con a 0,b 0,c 1)                Por lo tanto las reglas completas son: Nosotros usaremos esta versión "binaria" del álgebra de Boole. Fing/CETP – Tecnólogo en Informática 2 0 1  1 1 0  0 1 1 1 1 1 1 1 0 1 1 0 0 0 1 1 0 1 0 0 0 0 0 0 0                 Arquitectura de Computadoras – Algebra de Boole Notas de Teórico Basadas en las Notas de Teórico Versión 5.0 del Dpto. de Arquitectura-InCo-FIng 4 Propiedades.  Dualidad Si analizamos los postulados veremos que los mismos se presentan de a pares y en tal forma que uno de la pareja se obtiene de otro cambiando "0" por "1" junto con "+" por "" (y viceversa). Esto asegura que cada propiedad que se demuestre en esta Álgebra tiene una "dual" que también es cierta (para demostrar la dual bastaría con repetir la demostración realizada sustituyendo cada postulado o propiedad utilizada por su dual).  Asociativa a) a  (b  c)  (a  b)  c b) a (b  c)  (a b) c Si bien las leyes asociativas son muchas veces incluidas dentro del cuerpo axiomático, de hecho son demostrables a partir de los axiomas aquí presentados (demostración que no haremos) por lo cual las presentamos como propiedades.  Idempotencia Para todo elemento en G se cumple: a a a a a a     Demostración: (Dualidad) 0 (6) ( ) (5a) ( ) ( ) (6) ( ) 1 (3b) a a a a a a a a a a a a a a a a a a a a a a a a                        Neutros Cruzados Para todo elemento en G se cumple 0 0 1 1     a a Demostración: Fing/CETP – Tecnólogo en Informática 3 Arquitectura de Computadoras – Algebra de Boole Notas de Teórico Basadas en las Notas de Teórico Versión 5.0 del Dpto. de Arquitectura-InCo-FIng 0 0 (Dualidad) 1 1 1 (idempotencia) 1 ( ) (asociativa) 1 ( ) (6)                  a a a a a a a a a a a a a Entonces los axiomas 1, 2, 3, 4, 5 y 7 se satisfacen por definición y es fácil verificar que el G (complemento) también es cierto. Construimos por lo tanto un modelo "aritmético" de álgebra de Boole que podemos denominar "binario" y es en definitiva con la que trabajaremos. Muchas veces las reglas de combinación se presentan como tablas (como las funciones booleanas más generales que veremos más tarde) a b a+b a b ab 0 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 0 1 1 1 1 1 1 En general notaremos ab como ab, además la operación “” tendrá mayor precedencia que la operación “+”.  Complemento de complemento Para cada elemento de G se cumple : a  a Para todo par de elementos de G se cumple : a a b a a ab a     ( ) Para todo par de elementos de G se cumple : a a b ab a ab a b      ( )  Ley de De Morgan Para todo par de elementos de G se cumple : ab a b a b ab     ( ) ( ) Estas reglas de De Morgan pueden generarse para cualquier número de variables. Fing/CETP – Tecnólogo en Informática 4 Arquitectura de Computadoras – Algebra de Boole Notas de Teórico Basadas en las Notas de Teórico Versión 5.0 del Dpto. de Arquitectura-InCo-FIng n n n n a a a a a a a a a a a a         ( ... ) ... ( ... ) ... 1 2 1 2 1 2 1 2 5 Modelo lógico. Los valores que pueden asignarse a un juicio, desde el punto de vista lógico, son dos: verdadero (V) o falso (F). Un juicio al cual se le aplica el operador lógico no (negación) forma un nuevo juicio. Dos juicios pueden combinarse para formar un tercero mediante los operadores lógicos "o" e "y". Si vinculamos los valores booleanos 0 y 1 con los valores lógicos F y V respectivamente, encontramos que las operaciones del álgebra de Boole "binaria" asigna correctamente los valores lógicos del juicio combinación. Esto se comprueba observando que: verdadero o verdadero es verdadero verdadero o falso es verdadero falso o verdadero es verdadero falso o falso es falso verdadero y verdadero es verdadero verdadero y falso es falso falso y verdadero es falso falso y falso es falso Por lo cual se puede concluir que el modelo "lógico" es isomorfo con el "aritmético" (binario) realizando la correspondencia. F ⇔0 V ⇔1 ¿⇔+ ¿⇔. ¬⇔ Es posiblemente consecuencia de este isomorfismo que las reglas de combinación "+" y "." del álgebra de Boole reciban los nombres de OR ("o" en inglés) y AND ("y" en inglés) respectivamente. 6 Modelo circuital. Otro modelo posible es el que surge de considerar llaves eléctricas y asociar el valor A a la llave abierta (no pasa corriente, circuito abierto) y el valor C con la llave cerrada (pasa corriente, circuito cerrado). Es fácil comprobar que la combinación de llaves en paralelo o en serie cumplen las mismas reglas definidas en el modelo aritmético para "+" y "." respectivamente. Fing/CETP – Tecnólogo en Informática 5 Arquitectura de Computadoras – Algebra de Boole Notas de Teórico Basadas en las Notas de Teórico Versión 5.0 del Dpto. de Arquitectura-InCo-FIng LL1 LL2 Circuito PQ “+” LL1 LL2 Circuito PQ “” A A A A A A A C C A C A C A C C A A C C C C C C Entonces existe también un isomorfismo entre el modelo "circuital" y el "aritmético" si hacemos la asociación       serie paralelo 1 0 C A Este isomorfismo es de fundamental importancia para la construcción práctica de las computadoras binarias. 7 Expresiones booleanas. Llamamos constante a todo elemento del conjunto G que define al álgebra. Las variables podrán tomar como valor cualquier elemento de G ( 0 o 1 en el caso en que trabajamos). Una expresión la podemos definir recursivamente como 1) las constantes y las variables 2) el complemento de una expresión booleana 3) el OR (+) o el AND () de dos expresiones booleanas. 8 Funciones booleanas. Una función "F" de n variables x1 ... x n booleanas es una aplicación del espacio Gn sobre el espacio G de tal forma que para cada valor posible de la n-upla x 1 ... x n, donde cada variable puede tomar cualquier valor del conjunto (en nuestro caso {0, 1} ), se asocia un valor del recorrido G. Una de las formas de expresar F es a través de las denominadas tablas de verdad que indican el resultado de F para cada valor posible de la n-upla; por ejemplo : a b c F 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 0 1 1 1 1 Otras formas de representar F incluyen el método de indicar sólo los puntos en los cuales F vale 1 o sólo los puntos en los cuales vale 0 (representaciones  y  Fing/CETP – Tecnólogo en Informática 6 Arquitectura de Computadoras – Algebra de Boole Notas de Teórico Basadas en las Notas de Teórico Versión 5.0 del Dpto. de Arquitectura-InCo-FIng respectivamente). Para indicar los puntos en que la función vale 1 puede usarse la notación  en lugar de . Por ejemplo, la función anterior se puede expresar : f (a, b, c)  (1,4,5,7) f (a, b, c)  (0,2,3,6) Otra forma de expresar las funciones es a través de expresiones; ejemplo, la función anterior sería: f  ac  ab  abc 8.1 Conectivas binarias. Un caso interesante de estudiar es el de las funciones booleanas de 2 variables. Por ser dos variables las combinaciones posibles son 4, es decir "F" tiene 4 duplas (4 puntos) por tanto existen 16 funciones booleanas de dos variables posibles. Algunas de ellas no son de interes, veamos las tablas de verdad de las más útiles. a b OR AND XOR NOR NAND Equiv. Idemp Tautol. 0 0 0 0 0 1 1 1 0 1 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 0 1 1 1 1 1 0 0 0 1 0 1 Nota : la NOR es el complemento de la OR la NAND es el complemento de AND la XOR ("O" exclusivo) puede definirse como: a  b  ab  ab 8.2 OR exclusivo. El XOR es una función muy importante (es la suma aritmética binaria módulo 2) y cumple las propiedades : 1) Asociativa 2) Conmutativa 3) Distributiva: a(b  c)  ab  ac 4) a  0  a 5) a 1  a 6) a  a  0 7) Cancelativa: a  b  a  c  b  c 9 Simplificación. Hasta ahora hemos visto un método sistemático de expresar las funciones booleanas como expresión de sus variables. Pero este método no asegura que la expresión lograda sea la más simple posible. El hecho que la expresión de una función sea lo más simple posible no es algo trivial o caprichoso, es de fundamental importancia en la construcción práctica de circuitos lógicos, por eso analizaremos algunos métodos para simplificar expresiones booleanas, de manera de aplicarlos a las expresiones obtenidas como sumas de productos canónicos. Fing/CETP – Tecnólogo en Informática 7 Arquitectura de Computadoras – Algebra de Boole Notas de Teórico Basadas en las Notas de Teórico Versión 5.0 del Dpto. de Arquitectura-InCo-FIng 9.1 Método algebraico. El método consiste en la aplicación, más o menos ingeniosa, de transformaciones algebraicas de manera de lograr expresiones más sencillas. Por supuesto que este no es un método sistemático, pero es la base, al fin, de los métodos sistemáticos. Resumamos aquí algunas propiedades vistas del álgebra que serán de utilidad en la tarea de simplificar: 1) f  f  0 2) f  f  1 3) g  f  g f  f 4) g  f  f  f 5) f  f  g  f  g Veamos un par de ejemplos de como se aplican estas propiedades para reducir expresiones: a) Sea f 1=a bc+a b c+ab c Por la aplicación de la propiedad 3 a los primeros dos términos y a los dos últimos queda f 1  ab  bc b) Sea f 2=a b c+a b c+a b c+a bc Aplicando la propiedad 3 a los dos primeros términos queda f 2  bc  abc  abc f 2  b(c  ac)  abc (por la propiedad distributiva) f 2  b(c  a)  abc (por la propiedad 5 al paréntesis) f 2  c(b  ab)  ab (por distributiva aplicada dos veces) f 2  c(a  b)  ab (por propiedad 5 al paréntesis) Entonces la expresión de f2 a la que llegamos es: f 2  ab  ac  bc Esta sin embargo no es la expresión más reducida de f2. Vemos como hubiera quedado aplicando la propiedad 3 al primer y cuarto miembro y al segundo y tercero f 2  ac  ab siendo esta sí, la expresión más reducida. Como vemos entonces el procedimiento descrito no asegura reducir la expresión a un mínimo ya que depende de como se elijan las propiedades a aplicar y los términos sobre los que se aplican.

VIDEO EXPLICANDO COMO RESOLVER LOS EJERCICIOS DE ALGEBRA BOOLEANA

FUNCIONES

Las funciones son reglas que relacionan los elementos de un conjunto con los elementos de un segundo conjunto.

Cuando una magnitud depende de otra, se dice que está en función de ésta.

Una función f es una relación que asigna a los elementos de un primer conjunto (conjunto inicial X) un elemento de un segundo conjunto (conjunto final Y). A cada elemento de X le corresponde, un y solo un elemento de Y.

El elemento x del primer conjunto es la variable independiente. Es un valor que se fija previamente.

La letra y es la variable dependiente y corresponde a los elementos del conjunto final. Ésta variable depende del valor de la variable independiente x.

A f(x) se le denomina imagen de x, mientras que a x se le llama antiimagen de f(x).

¿Qué no es una función?

Si a un valor de la variable x le corresponde más de un valor de y, entonces esa relación no es una función.

Un ejemplo de lo que no es una función es cuando asignamos al conjunto de entrada las estaturas y al de salida, los alumnos un colegio. Esta relación no sería una función, pues podrían haber casos de valores de estaturas que tuviesen varios alumnos.

Otro ejemplo de lo que no sería una función: la ecuación de la elipse (para simplificar, centrada en el origen O).

Y sabemos que la ecuación de la elipse centrada en O es:

Por la imagen y por la ecuación, podemos ver que a valores concretos de x les corresponden dos valores de y. Por lo tanto, esta ecuación tampoco se corresponde con una función.

Como se ha dicho que la condición de una función es que a cada elemento del conjunto inicial X le corresponda, un y solo un elemento del conjunto final Y, de eso se deduce que:

Toda relación no tiene porqué ser necesariamente una función, aunque toda función sí que es una relación.
Por lo tanto, una ecuación (que es una relación) no tiene que ser necesariamente una función.

Ejercicio

ANUNCIOS

Por ejemplo, una función podría ser hacer corresponder a cada número x el doble de dicho número (2x).

Dominio de la función

El dominio de una función f es el subconjunto Dom f (o D) de elementos que tienen imagen. Es decir, el conjunto de elementos x de la variable independiente X que tienen imagen en Y. También se le llama campo de existencia de la función.

Recorrido de la función

El recorrido de una función f es el conjunto Im f (o Rec f) de todos los elementos que toma la variable dependiente. Es decir, el conjunto de todas las imágenes que se obtienen realmente a partir de la función f.

También se le llama rango de una función o conjunto de llegada.

El codominio es el conjunto de valores sobre los que se ha definido la función f, aunque no todos los elementos del codominio sean necesariamente imágenes (es decir, que pertenezcan necesariamente al rango de f).

Formalmente se define el recorrido de una función como:

Las funciones en que el recorrido de la función Im f es el mismo que el conjunto final Y son funciones sobreyectivas.

Crecimiento y decrecimiento

La tasa de variación indica cómo cambia una función al pasar de un punto a otro. Esta tasa examina si la función crece o decrece en una región.

El crecimiento o decrecimiento de una función f se puede estudiar en un intervalo [a,b], en un punto x o en todo el dominio.

Máximos y mínimos

Los máximos y mínimos en una función f son los valores más grandes (máximos) o más pequeños (mínimos) que toma la función, ya sea en una región (extremos relativos) o en todo su dominio (extremos absolutos).

Los máximos y mínimos también se llaman extremos de la función.

Continuidad y discontinuidad

Una función es continua si su gráfica puede dibujarse de un solo trazo. Diríamos que es continua si puede dibujarse sin separar el lápiz de la hoja de papel.

Se dice que la función es discontinua si no es continua, es decir, presenta algún punto en el que existe un salto y la gráfica se rompe.

La continuidad de una función se estudia en diferentes sectores de la función: