Apuntes Estructuras Discretas

Índice:

Algebra Booleana
​ Leyes fundamentales
​ Minterminos
​ Maxterminos
​ Formas de Representación
​ ​ Forma canónica
​ ​ Forma estándar
​ Tabla de verdad
​ ​ Tabla de suma de productos (Forma abreviada)
​ ​ Tabla de producto de sumas (Forma abreviada)
​ Mapa de Karnaugh
GRAFOS:
• Matriz de incidencia - El grafo está representado por una matriz de A (aristas) por V
(vértices), donde [arista, vértice] contiene la información de la arista (1 - conectado, 0 - no
conectado)

• Matriz de adyacencia - El grafo está representado por una matriz cuadrada M de tamaño
, donde es el número de vértices. Si hay una arista entre un vértice x y un vértice y,
entonces el elemento es 1, de lo contrario, es 0.

Ciclos y caminos hamiltonianos

Un ciclo es una sucesión de aristas adyacentes, donde no se recorre dos veces la misma
arista, y donde se regresa al punto inicial. Un ciclo hamiltoniano tiene además que recorrer
todos los vértices exactamente una vez (excepto el vértice del que parte y al cual llega).

Grafo simple: Si solo una arista une dos vértices.

Grafo multigrafo: Más de una arista une dos vértices.
Grafo planar: Si se puede dibujar el grafo sin aristas que se crucen
Grafo conexo: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.

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.

grafo dual:
grafo pesado:
coloración de grafos:
Árboles:
Representa una jerarquía ,un árbol no puede tener ciclos [Link] le dice raíz a la parte
más superior del árbol(al padre) y hoja al que no tiene más ramificaciones.​
-grado del nodo:Es el número de flechas que salen de ese nodo.

ir a Índice 👈
-grado de un árbol:Es el mayor grado de todos sus nodos.
-nivel de un vértice : Es cuánto se aleja de la raíz.
-Altura de un árbol:Es la cantidad de niveles que tiene.
-Arbol m-ario: Cuando todos tienen la misma cantidad de hijos se reemplaza m por la
cantidad de hijos de cada vé[Link] no tiene la misma cantidad se dice que no es completo.
-Árbol minimal : significa buscar el árbol de un grafo,si es un grafo con pesos se deben
eliminar las aristas con mayor peso.
-Algoritmo de Huffman
-Árbol de expansión:Un árbol t es un árbol de expansión de un grafo g si t es un subgrafo
de g que contiene todos los vértices de g.
Convertir árbol a árbol binario:Primero se enlazan los hermanos horizontalmente luego se
gira todo el árbol y ya está.
-Recorrido preorden: raiz-izquierda-derecha
-Recorrido inorden: izquierda-raíz-derecha
-Recorrido postorden: izquierda-derecha-raiz
Operaciones Binarias:
Anillo:

ALGEBRA BOOLEANA:

Representa las matemáticas de los sistemas digitales.

La lógica booleana sólo permite dos estados del circuito, como True y False.
Estos dos estados están representados por 1 y 0, donde 1 representa el
estado "Verdadero" y 0 representa el estado "Falso".
Variable : toma el valor de 1 o 0 ,ejm A , B , C.
Literal: Es toda ocurrencia de una variable, ya sea complementada o sin
complementar, en una expresión de conmutación. ,ejem A ,A’.
En AB + A’B →Hay 3 literales

LEYES FUNDAMENTALES:

ir a Índice 👈
Leyes conmutativas

A+B=B+A
A∙B=B∙A
Leyes asociativas

(A + B) + C = A + (B + C)
(A ∙ B) ∙ C = A ∙ (B ∙ C)
Leyes distributivas

A ∙ (B + C) = (A ∙ B) + (A ∙ C)
A + (B ∙ C) = (A + B) ∙ (A + C)
Leyes de Morgan

𝐴 + 𝐵 + 𝐶.... = 𝐴 ∙ 𝐵 ∙ 𝐶 …
𝐴 ∙ 𝐵 ∙ 𝐶.... = 𝐴 + 𝐵 + 𝐶 …
Otras identidades útiles

A + (A ∙ B) = A
A ∙ (A + B) = A
A + (A ∙ B) = A + B
(A + B) ∙ (A + B) = A
(A + B) ∙ (A + C) = A + (B ∙ C)
A + B + (A ∙ B) = A + B
(A ∙ B) + (B ∙ C) + (B ∙ C) = (A ∙ B) + C
(A ∙ B) + (A ∙ C) + (B ∙ C) = (A ∙ B) + (B ∙ C)
A + 𝐴B = A + B
A ∙ (𝐴 + B) = A ∙ B
(A+B) ∙ ( A+𝐵) = A

ir a Índice 👈
 AB+ A𝐵C = AB + AC
(A+B) ∙ ( A+𝐵+C) = (A + B) ∙ (A + C)
A + (B ∙ C) = (A + B) ∙ (A + C)
AB+ 𝐴C+BC = AB + 𝐴C
(A + B) ∙ (𝐴 + C) ∙ (B + C) = (A + B) ∙ (𝐴 + C)
AB+ 𝐴C = (A + C) ∙ (𝐴 + B)
(A + B) ∙ (𝐴 + C) = AC + 𝐴B

Minterminos:
Para que sea llamado mintérmino tiene que estar todas las variables correspondientes
como multiplicación,ejem:
Al reducir una expresión de mintérminos me debe dar igual que al reducir la misma
expresión expresada en sus maxtérminos.

Fm(A,B,C) = A’B’C

No es mintérmino→ F(A,B,C) = A’B falta la C

Maxterminos:
Para que sea llamado mintérmino tiene que estar todas las variables correspondientes
como suma,ejem:

FM(A,B,C) = (A+B’+C)

FORMAS DE REPRESENTACIÓN

●​ Forma canónica:
Es la representación de una expresión en forma abreviada ejem:

F(A,B,C)= ∑(1,4,5,6,7) significa sumatoria de mintérminos.

donde su complemento es la suma de lo que le falta.

F(A,B,C)= Π(0,2,3) significa producto de maxtérminos.

ir a Índice 👈
Los números indican la posición que ocupa en la tabla de verdad(empezando de 0).

●​ Forma estándar:

Es la representación de forma extensa ,tomando en cuenta el ejemplo anterior,tenemos:

​ Fm(A,B,C)= A’B’C + AB’C’ + AB’C + ABC’ + ABC

​ FM(A,B,C)= (A + B + C) (A + B’ + C)(A + B’ + C’)

TABLA DE VERDAD:
Para la comprobación de la tabla de verdad se reemplaza los valores 0 y 1 según
corresponda en los términos del producto y después de reducir me debe quedar la salida.

●​ Tabla de Suma de productos (Forma abreviada):

Ejm:
Desarrollar la tabla de verdad para : ABC + AB’C
La variable representada con 0 se complementa.

ir a Índice 👈
 X= Salida.
T.P=Términos del producto.

Para los elementos que quieres

representar ,en la salida se pone 1 y
para los demás se pone 0.

●​ Tabla de Producto de sumas (Forma abreviada):

Ejm:
Desarrollar la tabla de verdad para : (A’ + B + C’) (A’ + B’ + C)
La variable representada con 1 se complementa.

X= Salida.
T.P=Términos del producto.

ir a Índice 👈
Para los elementos que quieres representar ,en la salida se pone 0 y para los
demás se pone 1.

●​ Tabla de sumas y productos (Forma general) :

Desarrolla la tabla de verdad para la siguiente expresión booleana: A (A’ + B)

ir a Índice 👈
Desarrolla la tabla de verdad para la siguiente expresión booleana: AB + AB’

ir a Índice 👈
MAPA DE KARNAUGH:
1=normal 0=complemento
Al simplificar se quedan los que no cambian de valor

-En cuanto al cuadradito rojo,podemos observar

que tiene en común la A y la C ,la B no porque
cambia de valor.
entonces el rojo me quedaría : AC
-En cuanto al cuadradito verde,podemos observar
que tiene en común la A y la B ,la C no porque
cambia de valor.
entonces el verde me quedaría : AB

-En cuanto al cuadradito naranja,podemos observar que tiene en común la B y la C ,la A no

cambia de valor.
entonces el naranja me quedaría : BC
La simplificación en minterminos me quedaría: AC + AB + BC
Para hallar el complemento o maxterminos sería lo contrario:
1=complemento 0=normal
-En cuanto al cuadradito naranja,podemos
observar que tiene en común la B y la C ,la A no
porque cambia de valor.
entonces el naranja me quedaría : (B + C)
-En cuanto al cuadradito rojo,podemos observar
que tiene en común la A y la B ,la C no porque
cambia de valor.
entonces el rojo me quedaría : (A + B)

-En cuanto al cuadradito azul,podemos observar que tiene en común la A y la C ,la B no

cambia de valor.
entonces el azul me quedaría : (A + C)
La simplificación en maxterminos me quedaría: (B + C) (A + B) (A + C)

ir a Índice 👈