Operaciones Binarias

Operaciones binarias 

Se define como operación binaria a aquella operación matemática que necesita un operador y dos operandos (argumentos) para que se calcule un valor.

Clase de operación binaria.

Según los conjuntos A, B y C podemos diferenciar dos tipos de operaciones, las internas en las que A = B = C, y las externas que son todas las demás, se denomina Ley de composición a un subtipo de operación binaria.

Si a cada par de valores (a, b) de ${\displaystyle A}$ la operación le corresponde un valor c de A:

${\displaystyle {\begin{array}{rccl}\circledast :&A\times A&\longrightarrow &A\\&(a,b)&\longmapsto &c=a\circledast b\end{array}}}$

se dice que esta operación es interna, también se llama ley de composición interna, así por ejemplo dado el conjunto de vectores de tres dimensiones ${\displaystyle V^{3}}$ y la adición de vectores, se tiene:

${\displaystyle {\begin{array}{rccl}+:&V^{3}\times V^{3}&\longrightarrow &V^{3}\\&(\mathbf {a} ,\mathbf {b} )&\longmapsto &\mathbf {c} =\mathbf {a} +\mathbf {b} \end{array}}}$

que la suma de dos vectores de ${\displaystyle V^{3}}$ es otro vector de ${\displaystyle V^{3}}$, por ejemplo, dados los vectores:

${\displaystyle \mathbf {a} =a_{x}\mathbf {i} +a_{y}\mathbf {j} +a_{z}\mathbf {k} }$

${\displaystyle \mathbf {b} =b_{x}\mathbf {i} +b_{y}\mathbf {j} +b_{z}\mathbf {k} }$

su suma es:

${\displaystyle \mathbf {c} =\mathbf {a} +\mathbf {b} }$

${\displaystyle \mathbf {c} =(a_{x}\mathbf {i} +a_{y}\mathbf {j} +a_{z}\mathbf {k} )+(b_{x}\mathbf {i} +b_{y}\mathbf {j} +b_{z}\mathbf {k} )}$

${\displaystyle \mathbf {c} =(a_{x}+b_{x})\mathbf {i} +(a_{y}+b_{y})\mathbf {j} +(a_{z}+b_{z})\mathbf {k} }$

${\displaystyle \mathbf {c} =c_{x}\mathbf {i} +c_{y}\mathbf {j} +c_{z}\mathbf {k} }$

Operación externa

Artículo principal: Operación externa

Si la operación no es interna entonces es externa, pudiéndose presentar los siguientes casos:

• Si a cada par de valores a de A y b de B, se le asigna un valor c de A,

${\displaystyle {\begin{array}{rccl}\star :&A\times B&\longrightarrow &A\\&(a,b)&\longmapsto &c=a\star b\end{array}}}$

a esta operación también se denomina ley de composición externa, un ejemplo claro, de esta operación, es el producto de un vector por un escalar:

${\displaystyle {\begin{array}{rccl}\cdot :&V^{3}\times R&\longrightarrow &V^{3}\\&(\mathbf {a} ,b)&\longmapsto &\mathbf {c} =\mathbf {a} \cdot b\end{array}}}$

así, dado el vector:

${\displaystyle \mathbf {a} =a_{x}\mathbf {i} +a_{y}\mathbf {j} +a_{z}\mathbf {k} }$

el resultado de multiplicarlo por un escalar b, será:

${\displaystyle \mathbf {c} =\mathbf {a} \cdot b\;,\quad \mathbf {c} =(a_{x}\mathbf {i} +a_{y}\mathbf {j} +a_{z}\mathbf {k} )\cdot b\;,\quad \mathbf {c} =(a_{x}\cdot b)\mathbf {i} +(a_{y}\cdot b)\mathbf {j} +(a_{z}\cdot b)\mathbf {k} }$

• Si la operación es de la forma:

${\displaystyle {\begin{array}{rccl}\star :&A\times A&\longrightarrow &B\\&(a,b)&\longmapsto &c=a\star b\end{array}}}$

en la que a cada par de valores a, b de A se le asigna un c de B, esta operación no se denomina ley de composición, como ejemplo podemos poner el producto escalar de dos vectores, que da como resultado un número real:

${\displaystyle {\begin{array}{rccl}\circ :&V^{3}\times V^{3}&\longrightarrow &R\\&(\mathbf {a} ,\mathbf {b} )&\longmapsto &c=\mathbf {a} \circ \mathbf {b} \end{array}}}$

así dados los vectores:

${\displaystyle \mathbf {a} =a_{x}\mathbf {i} +a_{y}\mathbf {j} +a_{z}\mathbf {k} }$

${\displaystyle \mathbf {b} =b_{x}\mathbf {i} +b_{y}\mathbf {j} +b_{z}\mathbf {k} }$

su producto escalar será:

${\displaystyle \mathbf {c} =\mathbf {a} \circ \mathbf {b} \;,\quad \mathbf {c} =(a_{x}\mathbf {i} +a_{y}\mathbf {j} +a_{z}\mathbf {k} )\circ (b_{x}\mathbf {i} +b_{y}\mathbf {j} +b_{z}\mathbf {k} )\;,\quad \mathbf {c} =a_{x}\cdot b_{x}+a_{y}\cdot b_{y}+a_{z}\cdot b_{z}}$

• Si la operación asigna a cada par de valores a de A y b de B un c de C, siendo A, B y C conjuntos distintos:

${\displaystyle {\begin{array}{rccl}\star :&A\times B&\longrightarrow &C\\&(a,b)&\longmapsto &c=a\star b\end{array}}}$

es el caso más general, y tampoco se denomina ley de composición, podemos ver el ejemplo de la división de un número entero entre un número natural para dar como resultado un número racional

${\displaystyle {\begin{array}{rccl}/:&Z\times N&\longrightarrow &Q\\&(a,b)&\longmapsto &c=a/b\end{array}}}$

TEORÍA DE GRAFOS
♥Un grafo es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.

APLICACIONES DE LOS GRAFOS:

Las aplicaciones de los grafos es en diversas áreas:

♪Resolución de problemas 

♪Algoritmos compuestos

♪Dibujos computacionales

♪Planos,etc.

Árbol: es un grafo en el que cualesquiera dos vértices están conectados por exactamente un camino.
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.

Composición de los grafos 

• Aristas: Son las líneas con las que se unen los vértices de un grafo.
• Aristas adyacentes: 2 aristas son adyacentes si convergen en el mismo vértice.
• Aristas paralelas: Son dos aristas conjuntas si el vértice inicial y final son el mismo.
• Arista cíclicas: Es la arista que parte de un vértice para entrar en sí mismo.
• Cruce: Son 2 aristas que cruzan en un mismo punto.
• Vértices: Los vértices son los elementos que forman un grafo. Cada uno lleva asociada una valencia característica según la situación, que se corresponde con la cantidad de aristas que confluyen en dicho vértice.
• Camino: Se denomina camino de un grafo a un conjunto de vértices interconectados por aristas. Dos vértices están conectados si hay un camino entre ellos.

Tipos de grafos

• Grafo simple: O simplemente grafo es aquel que acepta una sola arista uniendo dos vértices cualesquiera. Esto es equivalente a decir que una arista cualquiera es la única que une dos vértices específicos. Es la definición estándar de un grafo.
• Multigrafo: o pseudografo: Es el que acepta más de una arista entre dos vértices. Estas aristas se llaman múltiples o lazos (loops en inglés). Los grafos simples son una subclase de esta categoría de grafos. También se les llama grafos general.
• Grafo orientado: grafo dirigido o digrafo. Son grafos en los cuales se ha añadido una orientación a las aristas, representada gráficamente por una flecha.
• Grafo etiquetado: Grafos en los cuales se ha añadido un peso a las aristas (número entero generalmente) o un etiquetado a los vértices.
• Grafo aleatorio: Grafo cuyas aristas están asociadas a una probabilidad.
• Hipergrafo: Grafos en los cuales las aristas tienen más de dos extremos, es decir, las aristas son incidentes a 3 o más vértices.
• Grafo infinito: Grafos con conjunto de vértices y aristas de cardinal infinito.
• Grafo plano: Los grafos planos son aquellos cuyos vértices y aristas pueden ser representados sin ninguna intersección entre ellos. Podemos establecer que un grafo es plano gracias al Teorema de Kuratowski.

• Grafo regular: Un grafo es regular cuando todos sus vértices tienen el mismo grado de valencia.

Grafos conexos[editar]

Un grafo es conexo si cada par de vértices está conectado por un camino; es decir, si para cualquier par de vértices (a, b), existe al menos un camino posible desde a hacia b.

Un grafo es doblemente conexo si cada par de vértices está conectado por al menos dos caminos disjuntos; es decir, es conexo y no existe un vértice tal que al sacarlo el grafo resultante sea disconexo.

Es posible determinar si un grafo es conexo usando un algoritmo Búsqueda en anchura (BFS) o Búsqueda en profundidad(DFS).

En términos matemáticos la propiedad de un grafo (fuertemente) conexo permite establecer una relación de equivalenciapara sus vértices, la cual lleva a una partición de estos en "componentes (fuertemente) conexos", es decir, porciones del grafo, que son (fuertemente) conexas cuando se consideran como grafos aislados. Esta propiedad es importante para muchas demostraciones en teoría de grafos.

Grafo conexo y no conexo

Grafos completos[editar]

Artículo principal: Grafo completo

Un grafo es completo si existen aristas uniendo todos los pares posibles de vértices. Es decir, todo par de vértices (a, b) debe tener una arista e que los une.

El conjunto de los grafos completos es denominado usualmente ${\displaystyle \mathbb {K} }$, siendo ${\displaystyle \mathbb {K} _{n}}$ el grafo completo de n vértices.

Un ${\displaystyle \mathbb {K} _{n}}$, es decir, grafo completo de ${\displaystyle n}$ vértices tiene exactamente ${\displaystyle {\frac {n(n-1)}{2}}}$ aristas.

La representación gráfica de los ${\displaystyle \mathbb {K} _{n}}$ como los vértices de un polígono regular da cuenta de su peculiar estructura.

Grafos bipartitos[editar]

Artículo principal: Grafo bipartito

Un grafo G es bipartito si puede expresar como ${\displaystyle G=\{V_{1}\cup V_{2},A\}}$ (es decir, sus vértices son la unión de dos grupos de vértices), bajo las siguientes condiciones:

• ${\displaystyle V_{1}}$ y ${\displaystyle V_{2}}$ son disjuntos y no vacíos.
• Cada arista de A une un vértice de V₁ con uno de V₂.
• No existen aristas uniendo dos elementos de V₁; análogamente para V₂.

Bajo estas condiciones, el grafo se considera bipartito, y puede describirse informalmente como el grafo que une o relaciona dos conjuntos de elementos diferentes, como aquellos resultantes de los ejercicios y rompecabezas en los que debe unirse un elemento de la columna A con un elemento de la columna B.

Homeomorfismo de grafos[editar]

Artículo principal: Homeomorfismo de grafos

Dos grafos ${\displaystyle G_{1}}$ y ${\displaystyle G_{2}}$ son homeomorfos si ambos pueden obtenerse a partir del mismo grafo con una sucesión desubdivisiones elementales de aristas.

Árboles[editar]

Artículo principal: Árbol (teoría de grafos)

Ejemplo de árbol.

Un grafo que no tiene ciclos y que conecta a todos los puntos, se llama un árbol. En un grafo conn vértices, los árboles tienen exactamente n - 1 aristas, y hay n^n-2 árboles posibles. Su importancia radica en que los árboles son grafos que conectan todos los vértices utilizando el menor número posible de aristas. Un importante campo de aplicación de su estudio se encuentra en el análisis filogenético, el de la filiación de entidades que derivan unas de otras en un proceso evolutivo, que se aplica sobre todo a la averiguación del parentesco entre especies; aunque se ha usado también, por ejemplo, en el estudio del parentesco entre lenguas.

Grafos ponderados o etiquetados[editar]

En muchos casos, es preciso atribuir a cada arista un número específico, llamado valuación, ponderación o coste según el contexto, y se obtiene así un grafo valuado.
Formalmente, es un grafo con una función v: A → R₊.

Por ejemplo, un representante comercial tiene que visitar n ciudades conectadas entre sí por carreteras; su interés previsible será minimizar la distancia recorrida (o el tiempo, si se pueden prever atascos). El grafo correspondiente tendrá como vértices las ciudades, como aristas las carreteras y la valuación será la distancia entre ellas.Si embargo, hasta ahora no ha sido posible encontrar métodos generales para hallar un ciclo de valuación mínima, pero sí para los caminos desde ahasta b, sin más condición.

EJEMPLOS DE ARBOLES Y GRAFOS 

Apuntes de matemáticas discretas

                  ALGEBRA BOOLEANA
Esta fue desarrollada por George Boole.
Esta se divide en:
♥Minitérmino:Es un producto booleano en que cada vez;es decir,es una expresión lógica que se compone de variables y los operadores lógicos AND y NOT.
♥Maxitérmino:Es una expresión lógica que se compone de variables y los operadores lógicos OR y NOT.
PROPIEDADES DE LAS EXPRESIONES BOOLEANAS.
a)Formadas por variables booleanas .
b)Valores de 1 (verdadero) ó 0 (falso).
c)Puede tener constantes booleanas (1 ó 0).
d)Puede tener operadores lógicos: AND (&,^), OR (V) y NOT (`,-,~).
♪Multiplicación lógica: AND
          ♥XY=X•Y=(X)(Y)
♪Suma lógica: OR
           ♥X+Y
♪Complemento negación: NOT
            ♥X'
LEYES DE LA ALGEBRA BOOLEANA
1.Existencia de neutros:
         X+0=X
         X•1=X
2.Conmutatividad:
         X+Y= Y+X
         X•Y =Y•X
3.Asociatividad:
        X+(Y+Z)=(X+Y)+Z
        X•(Y+Z)=(X•Y)•Z
4.Distributividad:
        X+(Y•Z)=(X+Y)•(X+Z)
        X•(Y•Z)=(X•Y)•Z
5.Complementos:
       X+X'=1
       X•X'=0
FUNCIONESFUNCFUNCIONAMIENTO DEL MICROPROCESADOR
Funcionamiento
•Fases MP
•Refetch
•Fetch
•Decodificación de la circulación
•Lectura del operando
•Ejecución
•Escribe los resultados en registros
UNIDAD CENTRAL DE PROCESO

La memoria caché está en el microprocesador
COMPUERTAS LÓGICAS BINARIAS
MAPAS DE KARNAUGH

Mapa de Karnaugh

Ir a la navegaciónIr a la búsqueda

Ejemplo de mapa de Karnaugh.

Un mapa de Karnaugh (también conocido comotabla de Karnaugh o diagrama de Veitch, abreviado como Mapa-K o Mapa-KV) es undiagrama utilizado para la simplificación defunciones algebraicas Booleanas. El mapa de Karnaugh fue inventado en 1953 por Maurice Karnaugh, un físico y matemático de loslaboratorios Bell.

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 muy inmensas.

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^N filas, el mapa K correspondiente debe poseer también 2^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 fácilmente realizar a mano con funciones de hasta 6 variables, para funciones de mayor cantidad de variables es más eficiente el uso de software especializado.

Construcción del mapa-K.

Las variables de entrada pueden combinarse de 16 formas diferentes, por lo que el mapa de Karnaugh tendrá 16 celdas, distribuidas en una cuadrícula de 4 × 4.

Otras formas de notación del álgebra de Boole[editar]

En Lógica binaria se suele emplear la notación ${\displaystyle (\{0,1\},{\bar {}},+,\cdot )}$, común en la tecnología digital, siendo la forma más usual y la más cómoda de representar.

Por ejemplo las leyes de De Morgan se representan así:

${\displaystyle {\overline {a+b}}={\bar {a}}\cdot {\bar {b}}\,}$

${\displaystyle {\overline {a\cdot b}}={\bar {a}}+{\bar {b}}\,}$

Cuando el álgebra de Boole se emplea en electrónica, suele emplearse la misma denominación que para las puerta lógica AND (Y), OR (O) y NOT (NO), ampliándose en ocasiones con X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y X-NOR (equivalencia). las variables pueden representarse con letras mayúsculas o minúsculas, y pueden tomar los valores {0, 1}.

Empleando esta notación las leyes de De Morgan se representan:

${\displaystyle {\mbox{NOT }}(a{\mbox{ OR }}b)={\mbox{NOT }}a{\mbox{ AND }}{\mbox{NOT }}b\,}$

${\displaystyle {\mbox{NOT }}(a{\mbox{ AND }}b)={\mbox{NOT }}a{\mbox{ OR }}{\mbox{NOT }}b\,}$

En su aplicación a la lógica se emplea la notación ${\displaystyle \land \lor \lnot }$ y las variables pueden tomar los valores {F, V}, falso o verdadero, equivalentes a {0, 1}

Con la notación lógica las leyes de De Morgan serían así:

${\displaystyle \lnot {(a\lor b)}=\lnot {a}\land \lnot {b}\,}$

${\displaystyle \lnot {(a\land b)}=\lnot {a}\lor \lnot {b}\,}$

En el formato de Teoría de conjuntos el Álgebra de Boole toma el aspecto: ${\displaystyle ({\mathcal {P}}(U),\sim ,\cup ,\cap )}$

En esta notación las leyes de De Morgan serían así:

${\displaystyle \sim {(a\cup b)}=\;\sim {a}\;\cap \sim {b}\,}$

${\displaystyle \sim {(a\cap b)}=\;\sim {a}\;\cup \sim {b}\,}$

Otra forma en la álgebra de conjuntos del Álgebra de Boole, las leyes de De Morgan serían así:

${\displaystyle {(A\cup B)}^{C}=\;{A}^{C}\cap {B}^{C}}$

${\displaystyle {(A\cap B)}^{C}=\;{A}^{C}\cup {B}^{C}}$

TABLA DE VERDAD 

Una tabla de verdad, o tabla de valores de verdad, es una tabla que muestra el valor de verdad de una proposición compuesta, para cada combinación de verdad que se pueda asignar.¹​

Fue desarrollada por Charles Sanders Peirce por los años 1880, pero el formato más popular es el que introdujo Ludwig Wittgenstein en su Tractatus logico-philosophicus, publicado en 1921.

Variable[editar]

Para una variable lógica A, B, C, ... pueden ser verdaderas V, o falsas F, los operadores fundamentales se definen así:

${\displaystyle {\begin{array}{|c|c|}\hline A&A\\\hline V&V\\F&F\\\hline \end{array}}}$

Negación[editar]

La negación operador que se ejecuta, sobre un único valor de verdad, devolviendo el valor contradictorio de la proposición considerada.

${\displaystyle {\begin{array}{|c|c|}\hline A&\thicksim A\\\hline V&F\\F&V\\\hline \end{array}}}$

Conjunción[editar]

La conjunción es un operador, que actúa sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdadverdadero cuando ambas proposiciones son verdaderas, yfalso en cualquier otro caso. Es decir, es verdadera cuando ambas son verdaderas.

En términos mas simples, será verdadera cuando las dos proposiciones son verdaderas.

La tabla de verdad de la conjunción es la siguiente:

${\displaystyle {\begin{array}{|c|c|c|}\hline A&B&A\land B\\\hline V&V&V\\V&F&F\\F&V&F\\F&F&F\\\hline \end{array}}}$

Que se corresponde con la columna 8 del algoritmo fundamental.

en simbología "^" hace referencia a el conector "y"

Disyunción[editar]

La disyunción es un operador lógico que actúa sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de verdad verdaderocuando una de las proposiciones es verdadera, o cuando ambas lo son, y falso cuando ambas son falsas.

En términos mas simples, será verdadera cuando por lo menos una de las proposiciones es verdadera de lo contrario será falsa.

La tabla de verdad de la disyunción es la siguiente:

${\displaystyle {\begin{array}{|c|c|c|}\hline A&B&A\lor B\\\hline V&V&V\\V&F&V\\F&V&V\\F&F&F\\\hline \end{array}}}$

Que se corresponde con la columna 2 del algoritmo fundamental.

Implicación o Condicional[editar]

El condicional material es un operador que actúa sobre dos valores de verdad, típicamente los valores de verdad de dos proposiciones, devolviendo el valor de falso sólo cuando la primera proposición es verdadera y la segunda falsa, yverdadero en cualquier otro caso.

La tabla de verdad del condicional material es la siguiente:

${\displaystyle {\begin{array}{|c|c|c|}\hline A&B&A\Rightarrow B\\\hline V&V&V\\V&F&F\\F&V&V\\F&F&V\\\hline \end{array}}}$

Que se corresponde con la columna 5 del algoritmo fundamental.

Equivalencia, doble implicación o Bicondicional[editar]

El bicondicional o doble implicación es un operador que funciona dando el valor de verdad cuando ambos valores son iguales y dando el valor de falsedad cuando ambos valores son diferentes.

La tabla de verdad del bicondicional es la siguiente:

${\displaystyle {\begin{array}{|c|c|c|}\hline A&B&A\Leftrightarrow B\\\hline V&V&V\\V&F&F\\F&V&F\\F&F&V\\\hline \end{array}}}$

Que se corresponde con la columna 7 del algoritmo fundamental.

Tablas de verdad[editar]

Las tablas nos manifiestan los posibles valores de verdad de cualquier proposición molecular, así como el análisis de la misma en función de las proposicíones que la integran, encontrándonos con los siguientes casos:

Verdad Indeterminada o Contingencia[editar]

${\displaystyle {\begin{array}{|c|c|c|c|c|}\hline 1&2&3&4&5\\\hline A&B&C&B\lor C&A\land (B\lor C)\\\hline V&V&V&V&V\\V&V&F&V&V\\V&F&V&V&V\\V&F&F&F&F\\F&V&V&V&F\\F&V&F&V&F\\F&F&V&V&F\\F&F&F&F&F\\\hline \end{array}}}$

Se entiende por verdad contingente, o verdad de hecho, aquella proposición que puede ser verdadera o falsa, según los valores de las proposiciones que la integran. Sea el caso: ${\displaystyle A\land (B\lor C)}$.

Su tabla de verdad se construye de la siguiente manera:

Ocho filas que responden a los casos posibles que pueden darse según el valor V o F de cada una de las proposiciones A, B, C.(Columnas 1, 2, 3)

Una columna (Columna 4) en la que se establecen los valores de ${\displaystyle B\lor C}$ aplicando la definición del disyuntor a los valores de B y de C en cada una de las filas.(Columnas 2,3 → 4)

Una columna (columna 5) en la que se establecen los valores resultantes de aplicar la definición de la conjunción entre los valores de A (columna 1) y valores de la columna ${\displaystyle B\lor C}$,(columna 4) que representarán los valores de la proposición completa ${\displaystyle A\land (B\lor C)}$, cuyo valor de verdad es V o F según la fila de los valores de A, B, y C que consideremos.(Columnas 1,4 → 5)

Donde podemos comprobar cuándo y por qué la proposición ${\displaystyle A\land (B\lor C)}$ es V y cuándo es F.