Uso de Diagramas de Decisión binaria, para la reducción de procesos.

Matemáticas Elementales
Proyecto Final.

Vicente García Serrano.
Profesora: Dra. Maria de Lourdes Sandoval Solis.
Otoño: 2014.

P
V
V
F
F

Q
V
F
V
F

P→Q
V
F
V
V

Aplicación de lógica matemática y tablas de verdad
para reducir procedimientos binarios.

Introducción.
●

●

En la actualidad pocos programadores siguen
utilizando el lenguaje de máquina para crear sus
programas, pero, aquellos que losiguen utilizando
tienen muchos problemas para trabajar si no saben
implementar un algoritmo que les ayude a realizar de
forma más eficaz y como mayor rapidez su trabajo.
En base a esto podemos decir que la lógica
proposicional puede ayudarlos a facilitar su trabajo,
mediante una serie de algoritmos y procesos usando
lógica matemática, tablas de verdad y un DDB.

Problemática.
●

●

Comointroducción uno de los grandes
problemas a la hora trabajar con lenguaje de
máquina, es realizar operaciones binarias.
Por ello los programadores deciden crear
fórmulas y descomponerlas en proposiciones
lógicas para poder resolver estas
operaciones, y para saber si esta fórmula
facilita el trabajo se debe de reducir una vez
hecho el mapa gráfico o mediante tablas de
verdad.

Conceptos de MatemáticasElementales que utiliza.
●

●

Para resolver este problema se requiere
del uso de lógica matemática.
Siendo los siguientes conceptos los que
se van a utilizar:
✔

Tablas de Verdad.

✔

Conectores lógicos.

✔

Proposiciones lógicas.

✔

Diagrama de Decisiones Binarias.

Como aplicarlo.
Antes de comenzar vamos a establecer
algunos puntos.
➢

➢

Para hacer la tabla de verdad necesitamos
ciertasproposiciones.
Para reducir la cantidad de tareas a hacer se
debe hacer una disyunción de casos, para
saber que resultado se espera al final y ver si
este se repite varias veces.

Primero que nada hay que saber la definición de
"Diagrama de Decisiones Binarias"(DDB); Un DDB es
una herramienta de estructura de datos que es
utilizada para representar el significado de una
fórmula en formato de lógicaproposicional.
Aplicando este método con alguna fórmula, por
ejemplo una fórmula 'A', con factores p,q y r.

Para poder reducir el trabajo primero debemos saber reducir
casos con tablas de verdad:

P

Q

R

P v (Q ^ R)

1 V

V

V

V

2 V

V

F

V

3 V

F

V

V

4 V

F

F

V

5 F

V

V

V

6 F

V

F

F

7 F

F

V

F

8 F

F

F

F

Si nos damos cuenta.
En la fila 1 y 2 el valor
final es Verdaderoindependientemente del
valor de 'R', de igual
forma en las filas 3 y 4.

De igual forma lo vemos
con Falso, en las filas 7 y
8.

Ahora vamos a ver un ejemplo de reducción mucho más notorio en una
tabla utilizando un XOR u OR Exclusivo.

P

Q

R

P ⴲ (Q ⴲ R)

1 V

V

V

V

2 V

V

F

F

3 V

F

V

F

4 V

F

F

V

5 F

V

V

F

6 F

V

F

V

7 F

F

V

V

8 F

F

F

F

Es difícil reducir casos
aquí,pero si observamos
5 y 6 tienen el mismo
resultado que 3 y 4.

Aquí observemos que el
patrón de 7 y 8 tienen el
mismo resultado que 1 y 2.

Y como se dan cuenta se ha reducido el tamaño de la tabla,
removiendo las repeticiones.

P

Q

R

P ⴲ (Q ⴲ R)

1

V

V

V

V

2

V

V

F

F

3

V

F

V

F

4

V

F

F

V

5y6

F

V

*

Valor de 3 y 4

7y8

F

V

*

Valor de 1 y 2
Observe que en el últimoRecuadro se ha sustituido el
Valor por un asterisco.
Esto se debe a que el valor
Final es independiente de
El valor de 'R'

Ahora utilizando el mismo algoritmo de reducción vamos
a reducir un DDB de la Fórmula A.
Nota: Con esto se quiere obtener una decisión binaria.
P

Q

Q

R

F

R

F

F

R

V

V

R

V

V

V

Solo debemos utilizar el mismo método que usamos con
las tablas de verdad.

P

Q

R

Q

RF

R

R

V

En esta parte del proceso podemos observar que cuando
todo da verdadero, independientemente del valor de la
última proposición, podemos ir directamente a verdadero.
Lo mismo pasa cuando todo es falso.
P

Q

Q

R

F

V

Aquí solo reducimos lo absurdo, que si falso y verdadero
al final dará verdadero, entonces decimos que todo será
verdad.
Como resultado solo deben
evaluarse los...