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.