Apuntes de Álgebra Booleana - Compuertas Lógicas

Compuertas Lógicas



Las Compuertas Lógicas son circuitos electrónicos conformados internamente por transistores que se encuentran con arreglos especiales con los que otorgan señales de voltaje como resultado o una salida de forma booleana, están obtenidos por operaciones lógicas binarias (suma, multiplicación). También niegan, afirman, incluyen o excluyen según sus propiedades lógicas. Estas compuertas se pueden aplicar en otras áreas de la ciencia como mecánica, hidráulica o neumática.

Existen diferentes tipos de compuertas y algunas de estas son más complejas, con la posibilidad de ser simuladas por compuertas más sencillas. Todas estas tienen tablas de verdad que explican los comportamientos en los resultados que otorga, dependiendo del valor booleano que tenga en cada una de sus entradas.










Trabajan en dos estado, "1" o "0, los cuales pueden asignarse a la lógica positiva o lógica negativa. El estado 1 tiene un valor de 5v como máximo y el estado 0 tiene un valor de 0v como mínimo y existiendo un umbral entre estos dos estados donde el resultado puede variar sin saber con exactitud la salida que nos entregara. Las lógicas se explican a continuación:


La lógica positiva es aquella que con una señal en alto se acciona, representando un 1 binario y con una señal en bajo se desactiva. representado un 0 binario.


La lógica negativa proporciona los resultados inversamente, una señal en alto se representa con un 0 binario y una señal en bajo se representa con un 1 binario. A continuación te mostrare algunas compuertas lógicas:






Compuerta AND


Esta compuerta es representada por una multiplicación en el Algebra de Boole. Indica que es necesario que en todas sus entradas se tenga un estado binario 1 para que la salida otorgue un 1 binario. En caso contrario de que falte alguna de sus entradas con este estado o no tenga si quiera una accionada, la salida no podrá cambiar de estado y permanecerá en 0. Esta puede ser simbolizada por dos o más interruptores en serie de los cuales todos deben estar activos para que esta permita el flujo de la corriente.








Compuerta OR


En el Algebra de Boole esta es una suma. Esta compuerta permite que con cualquiera de sus entradas que este en estado binario 1, su salida pasara a un estado 1 también. No es necesario que todas sus entradas estén accionadas para conseguir un estado 1 a la salida pero tampoco causa algún inconveniente. Para lograr un estado 0 a la salida, todas sus entradas deben estar en el mismo valor de 0. Se puede interpretar como dos interruptores en paralelo, que sin importar cual se accione, será posible el paso de la corriente.








Compuerta NOT


En este caso esta compuerta solo tiene una entrada y una salida y esta actúa como un inversor. Para esta situación en la entrada se colocara un 1 y en la salida otorgara un 0 y en el caso contrario esta recibirá un 0 y mostrara un 1. Por lo cual todo lo que llegue a su entrada, será inverso en su salida.












Compuerta NAND

También denominada como AND negada, esta compuerta trabaja al contrario de una AND ya que al no tener entradas en 1 o solamente alguna de ellas, esta concede un 1 en su salida, pero si esta tiene todas sus entradas en 1 la salida se presenta con un 0.








Compuerta NOR


Así como vimos anteriormente, la compuerta OR también tiene su versión inversa. Esta compuerta cuando tiene sus entradas en estado 0 su salida estará en 1, pero si alguna de sus entradas pasa a un estado 1 sin importar en qué posición, su salida será un estado 0.








Compuerta XOR


También llamada OR exclusiva, esta actúa como una suma binaria de un digito cada uno y el resultado de la suma seria la salida. Otra manera de verlo es que con valores de entrada igual el estado de salida es 0 y con valores de entrada diferente, la salida será 1.









Compuerta XNOR


Esta es todo lo contrario a la compuerta XOR, ya que cuando las entradas sean iguales se presentara una salida en estado 1 y si son diferentes la salida será un estado 0.










Compuerta IF


Esta compuerta no es una muy utilizada o reconocida ya que su funcionamiento en estados lógicos es parecido a si solo hubiera un cable conectado porque exactamente lo que se le coloque en la entrada, se encontrara en la salida. Pero también es conocido como un buffer, en la práctica se utiliza como amplificador de corriente o como seguidor de tensión para adaptar impedancias.

¡Aquí te muestro un vídeo para que entiendas mejor! :D

Teoría de Grafos y Arboles

Teoría de Grafos


¿Que es la Teoría de Grafos?

Es una rama de las matemáticas y las ciencias de la computación que permite el estudio de grafos, un grafo es una par (V,E) donde V es un conjunto de vértices y E es un conjunto de aristas, junto con una relación que relaciona dos vertices a través de una arista. Esta rama permite su clasificación, análisis de propiedades y sus aplicaciones prácticas para un fin. Por ejemplo, los problemas relacionados con posibilidades de comunicación (redes de comunicación y de transporte), relaciones de orden entre actividades (planificaciones de proyectos mediante PERT) o estructuras de producto complejas(gestión de inventarios). Los grafos son una herramienta que permite modelizar relaciones de esta naturaleza, de modo que sea posible resolver problemas asociados a esas circunstancias de manera menos costosa que con otras técnicas.


Ejemplos de grafos:


Mapa de carreteras,planos de metro, redes de PCs,Plano de un circuito eléctrico, árboles genealógicos.


Entre sus aplicaciones se destacan las áreas de:


Compiladores y traductores, estructuras de datos, autómatas computacionales, redes, etc.

Vértice: Los vértices constituyen uno de los dos elementos que forman un grafo. Como ocurre con el resto de las ramas de las matemáticas, a la Teoría de Grafos no le interesa saber qué son los vértices. Diferentes situaciones en las que pueden identificarse objetos y relaciones que satisfagan la definición de grafo pueden verse como grafos y así aplicar la Teoría de Grafos en ellos. 

Grafo:Un grafo es una pareja de conjuntos donde es el conjunto de vértices, y es el conjunto de aristas, este último es un conjunto de pares de la forma tal que . Para simplificar, notaremos la arista como . En teoría de grafos, sólo queda lo esencial del dibujo: la forma de las aristas no son relevantes, sólo importa a qué vértices están unidas. La posición de los vértices tampoco importa, y se puede variar para obtener un dibujo más claro.

Subgrafo: Un subgrafo de un grafo G es un grafo cuyos conjuntos de vértices y aristas son subconjuntos de los de G. Se dice que un grafo G contiene a otro grafo H si algún subgrafo de G es H o es isomorfo a H (dependiendo de las necesidades de la situación). 

El subgrafo inducido de G es un subgrafo G' de G tal que contiene todas las aristas adyacentes al subconjunto de vértices de G.

Entre Otros.

Teoría de Arboles

Árbol: Es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.
Los árboles corresponden a una de las subclases de grafos de uso más amplio, particularmente en computación.
Los grafos se pueden clasificar en dos grupos: dirigidos y no dirigidos. Los arboles forman parte de los no dirigidos.
Sirven para organizar y relacionar datos en una base de datos, por ejemplo. Esto permite realizar operaciones de manera eficiente. Por ejemplo, un árbol de definición jerárquica se utiliza para configurar una base de datos para los registros de libros existentes en diversas bibliotecas.
Otro ejemplo de la utilización de árboles son los diccionarios. A partir de una palabra, se realiza una búsqueda en el árbol para saber si está incluida en el conjunto, y si existe, se obtienen sus datos asociados (por ejemplo, si es un verbo, un sustantivo, un artículo, etc.).

Árboles binarios

Definición: un árbol binario es un árbol con raíz en el cual cada vértice tiene cero, uno o dos hijos. Si un vértice tiene un hijo, ese hijo se designa como un hijo izquierdo o un hijo derecho (pero no ambos). Si un vértice tiene dos hijos, uno de ellos se designa como un hijo izquierdo y el otro se designa como un hijo derecho.

Un árbol de búsqueda binaria es un árbol binario T en el cual se asocian ciertos datos con los vértices. Los datos están ordenados de modo que, para cada vértice v en T, cada elemento de dato en el subárbol izquierdo de v sea menor que el elemento de dato en v y cada elemento de dato en el subárbol derecho de v es mayor que el elemento de dato en v.




Los arboles de búsqueda binaria son útiles para localizar datos. Es decir, dado un elemento D, podemos determinar con facilidad si D está en un árbol de búsqueda binaria y, de estar presente, conocer su posición. Para determinar si un elemento de dato D esta en un árbol de búsqueda binaria, comenzaríamos en la raíz. Luego compararíamos de manera sucesiva D con el elemento de dato del vértice en cuestión. Si D es igual al elemento de dato del vértice en cuestión, hemos encontrado a D, por lo cual habremos concluido. Si D es menor que el elemento de dato en el vértice en cuestión v, nos movemos al hijo izquierdo de v y repetimos el proceso. Si D es mayor que el elemento de dato en el vértice en cuestión v, nos movemos al hijo derecho de v y repetimos el proceso. Si en algún momento no existe un hijo al cual moverse, podemos concluir que D no está en el árbol.