UNIVERSIDAD MARIANO GALVEZ COATEPEQUE, QUETZALTENANGO GUATEMALA, C.A.

TRABAJO DE INVESTIGACION
MATEMATICA DISCRETA

MATEMATICA DISCRETA
UNION:

= A B = { 0, 1, 2, 3, 4, 5, 7, 9 } B

A B = {X|X AV X B} Ejemplo: A = { 0, 1, 2, 3, 4, 5 } B = { 1, 3, 5, 7, 9 } A A B=

INTERSECCION:

AB= {X|X A X B} Ejemplo: A = { 0 , 1, 2, 3, 4, 5 } B = { 1, 3, 5, 7, 9 } A A B = = A B = { 1, 3, 5 } B

DIFERENCIA:
A B= {X|X A X B} Ejemplo: A = { 0, 1, 2, 3, 4, 5 } B = { 1, 3, 5, 7, 9 } A AB = = A B = { 0, 2, 4 } B

A B A=

DIFERENCIA SIMETRICA:
A B = {X | X Ejemplo:

(AB)VX (BA)}
B = { 1, 3, 5, 7, 9 } A = A B = { 0, 2, 4, 7, 9 } B

A = { 0, 1, 2, 3, 4, 5 }

A B =

RELACION DE PERTENENCIA:
Es Verificar si algn elemento de un conjunto pertenece a otro conjunto. Se representa por : Ejemplo: De acuerdo al siguiente conjunto, verificar la relacin de pertenencias: E A B

3 10
9 30

A B A E

5 A 30 E 3 B 10 A

RELACION DE CONTENCION:
Es verificar si un elemento de un conjunto est contenido en otro conjunto. Su smbolo es: Ejemplo: A = { 0, 1, 2 } D = { 1, 3, 5 } A E B = { 0, 1, 2, 3, 4, 5 } E = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, } A C C B A D B C B D C = { 2, 0, 1 } C D C E

B B

DEFINICIONES
LOGICA Es la disciplina que trata del mtodo del razonamiento. PROPOSICION: Es una oracin que declara que algo es Verdadero o Falso ( V / F ), pero no ambos. RAZONAMIENTO INDUCTIVO: Es aquel que a partir de un nmero de observaciones particulares se concluyen leyes generales o sea casos particulares a idea generales. METODO DEDUCTIVO: Concluimos ciertos pensamientos particulares a partir de otros generales. Ej. Todas las ballenas son mamferas; todos los mamferos tienen pulmones; conclusin: Las ballenas tienen pulmones. METODO INTUITIVO: De ah corazonadas, presentimientos, intuicin. Etc. Las proposiciones por lo general se escriben con letras minsculas: p, q, r, s . Ej. p: la tierra es redonda.

OPERADORES DE LA PORPOSICION COMPUESTA: NEGACION:

p 1 0

-p 0 1

COMPUERTA: NOT

CONJUNCION:
p.q 0 0 0 0

p q V F F F V V V F

p V F F F

Mtodo Binario:

p 1 1 0 0

q 1 0 1 0

Cuando las dos sean Verdaderas, la conjuncin ser verdadera, las dems, falsas.

COMPUERTA: AND p q

DISYUNCION:
Dentro de la Disyuncin existe la Disyuncin Inclusiva y la Disyuncin Exclusiva.

DISYUNCIN INCLUSIVA:
p q V V F F pVq Mtodo Binario: p 1 1 0 0 q 1 0 1 0 pV q 1 1 1 0
Con una que sea verdadera

V V F V V V F V

La disyuncin ser verdadera.

COMPUERTA : OR

DISYUNCION EXCLUSIVA:
Cuando las dos sean iguales, La disyuncin Exclusiva ser falsa, y si son diferentes, Ser verdadera. Mtodo Binario: p V V F F q V F V F pVq F V V F p 1 1 0 0 q 1 0 1 0 pV q 0 1 1 0

COMPUERTA EXCLUSIVA :

PROPOSICION CONDICIONAL:

p V V F F

q V F V F

p V F V V

Mtodo Binario

p 1 1 0 0

q 1 0 1 0

p 1 0 1 1

Cuando el Antecedente es Verdadero y el Consecuente es Falso, la Condicin es Falsa; Todas las dems sern Verdaderas.

PROPOSICION BICONDICIONAL:

p V V F F

q V F V F

pVq F V V F

p 1 1 0 0

q 1 0 1 0

pV q 0 1 1 0

CONVERSA:

INVERSA:

1 p
V V F F

2 q q
V F V V

q
V F V F

q
F V F V

p
F F V V

p
V F V V

1
V V V V

Cuando en la respuesta todas son Verdaderas, se le llama TAUTOLOGIA.

PROPIEDADES:
CONMUTATIVA: pVq = qVp | 2+4 = 4+2 p q = qp | 2*4 = 4*2 ASOCIATIVA: p V q ( q V r ) = ( p V q ) V r | 2 + ( 4+3 ) = ( 2+4 ) + 3 p q ( q r ) = ( p q ) r | 2 * ( 4+3 ) = ( 2*4 ) + 3

DISTRIBUTIVA: pV(qr) = (pVq) ( pVr) p(qV r) = (pq) V ( pr) IDEMPOTENCIA: pVp = p p p =p p 1= p pV1 = 1 p 0 = 0 p V 0 = 0

LEYES DE MORGAN: ( p)= p ( p V q ) = p q

(p q) pV q

p
V V F F

q
V F V F

p
F F V V

pq
V F F V

pq
V F V V

1 ~p V (p q )
V F V V

2 pq q
V F F F

12
V F F F

( a, b) PAR ORDENADO:
Un Par Ordenado es en un orden predeterminado donde [ a ] aparece en el primer trmino y [ b ] en el segundo trmino. Ej. ( a1, b1) = ( a2, b2 ) a1 = a2 b1 = b2 ( 3x + 1, 2) = ( 7, 2 ) 3x + 1 = 7 2=2 x=2

PRODUCTO CARTESIANO:

AXB
A X B = { ( a, b ) | a A b B } A = { 1, 2, 3 } B = { r, s } A X B = { (1,r), (1,s), (2,r), (2,s), (3,r), (3,s) }

AXA A = { 1, 2, 3 } A X A = { ( 1,1 ), ( 1,2 ), ( 1,3 ), ( 2,1), ( 2,2 ), ( 2,3 ), ( 3,1 ), ( 3,2 ), ( 3,3 ) }

Ejercicio: Una Compaa de Software proporciona las 2 caractersticas siguientes para cada programa que se vende: Lenguaje: Fortran ( f ); Pascal ( p ); C++ ( c ) Memorias: 2MB ( 2 ); 4MB ( 4 ); Determinar las categoras posibles. L X M = { ( f,2 ), ( f,4 ), ( p,2 ), ( p,4 ), ( c,2 ), ( c,4 ) }

PARTICION:
Una Particin o conjunto cociente de un conjunto no vaco A es una coleccin de P de subconjuntos no vacos de A tales que: 1. 2. Cada elemento de A pertenece a uno de los conjuntos en P. Si A1 y A2 son elementos distintos de P entonces: A1 y A2 A1 A2 = Ejemplo: Z = conjunto de todos los enteros A1 = conjunto de nmeros pares A2 = conjunto de nmeros impares Ejemplo No.2 A = { a, b, c, d, e, f, g, h } A1 = { a, b, c, d } A2 = { a, c, e, f, g, h } A4 = { b, d } A5 = { f, h } A3 = { a, c, e, g }

A1 Z A2 Z A1 A2 =

{ A1, A2 } = No es particin porque si hay interseccin { A1, A5 } = No es particin. { A3, A4, A5 } = Si es particin.

RELACIONES Y SUS GRAFICAS

Sea A = { 1, 3, 5 } Definir la siguiente relacin: R menor que ( A < B ) R = { ( 1,3 ), ( 1,5 ), ( 3,5 ) } Ejemplo: Una Lnea area da servicio a 3 ciudades: C1, C2, C3 C1 C1 C2 C3 190 110 C2 140 180 C3 100 200 Encontrar los valores menores o iguales a 140 R <= 140 = { ( C1, C2 ), ( C1, C3 ), ( C3, C1 ) }

LA MATRIZ DE UNA RELACION Es posible representar una relacin entre 2 conjuntos finitos con una matriz de la siguiente manera:

Si

A = { a1, a2, a3, a4.aN } B ={ b1, b2, b3, b4.bN }

A tiene N elementos B tiene N elementos

MATRIZ DE RELACION NXM MR = 1 Si ( a,b ) R 2 Si ( a,b ) R 100 200 0 C1 C2 C3 C1 0 1 1 C2 1 0 1 C3 1 1 0

0 MR = 190 110

140 0 180

GRAFICA DIRIGIDA O DIGRAFO DE R

2. 3.

Marque el circulo con el elemento correspondiente de A Trace una flecha (lado o arco) del vrtice Ai al vrtice Aj.

Ai R Aj

GRADO INTERNO: Grado interno de un vrtice es el nmero de arcos que terminan en el vrtice. GRADO EXTERNO: Es el nmero de arcos que salen del vrtice. Ejemplo: Sea A = { 1, 2, 3, 4 } encontrar los grados internos y externos para cada uno de los elementos. 1 Grado Interno 3 Grado Externo 2 2 2 4 3 1 1 4 2 1

ALGEBRA BOLEANA:
(FUNCION BOLEANA O FUNCION LOGICA) Es un conjunto finito de smbolos, cada uno representa una constante o una variable combinadas mediante las sumas, productos o complementacin. . And y + Or o V Not no

DEFINICIONES: LITERAL: Se refiere a una variable o a su complemento. Por ejemplo: A, ( a, no a )

TERMINO PRODUCTO: Es un grupo de literales que se encuentran relacionados entre s por un And ( . ) A.B X.Y.Z TERMINO SUMA: Es un grupo de literales que se encuentran relacionadas entre s por un Or ( + ) A+B X+Y+Z TERMINO NORMAL: Es un trmino producto o un trmino suma en el que una literal no aparece ms de una vez. TERMINO CANONIMO: Termino en el que se encuentra exactamente uno de cada uno de las literales de la funcin. Si el trmino canonimo es producto, se denomina MINTERMINO.

Si el trmino cannimo es suma, se denomina MAXTERMINO. FORMA NORMAL DE UNA FUNCION: Es la que est constituida por trminos normales, pueden estar en la forma de: Suma de Trminos Productos ( STP ) o Producto de Trminos de Suma ( PTS 9 Suma de productos: X.Y + X.Z Producto de suma: ( X + Y ) ( Z + X + Y ) FORMA CANONIMA DE UNA FUNCION: Es aquella constituida exclusivamente por trminos canonicos que aparecen una sola vez.

PERMUTACIONES: Las permutaciones se definen como las distintas formas que se pueden ordenar n elementos de determinado conjunto; las permutaciones de representan as: n! y se lee n factorial o factorial de n. Ejemplo: Imaginemos 5 bolas ordenadas de izquierda a derecha en un cajn. Cuntos arreglos se pueden realizar? Utilizando el principio de la multiplicacin decimos que hay cinco maneras de seleccionar la primera bola, cuatro maneras de seleccionar la segunda, tres maneras de seleccionar la tercera, dos maneras de seleccionar la cuarta y una manera de seleccionar la quinta. Solucin: por lo tanto los arreglos se realizan as: 4*3*2*1 = 24 y de otra manera se demuestra como sigue: 4! = 24 Permutacin de n elementos tomando s a la vez: Su frmula es P(n, s) = _ n!__ (n s)! Donde s representa el nmero de veces que se tomarn determinados elementos de un conjunto de n elementos. Ejemplo: Un grupo musical est formado por siete personas, encontrar la cantidad de maneras de acomodar la posicin de los primeros tres vocalistas. Solucin: Se desea hallar el nmero de permutaciones de 7 objetos tomados 3 a la vez. n=7 s=3

P (7, 3) = ___7!___ = __8!__ = 7*6*5*4*3*2*1 = 210 (8 4)! 4! 4*3*2*1 Permutaciones Distinguibles. Existen tambin arreglos de objetos, algunos de los cuales son distinguibles y su frmula para calcularlo es: P = n! s! Ejemplo: Encontrar la cantidad de permutaciones distinguibles de la palabra rama.

sa = 2 P = __ 4!___ = 2! 1! 1!

sr = 1;

sm = 1; n = 4

4*3*2*1 = 12 (2*1)(1)

COMBINACIONES.
Combinacin Simple: A todas las agrupaciones de R elementos, dispuestos linealmente que se pueden formar a partir de n elementos distintos (r, n), sin que ninguno se repita se le llama combinaciones simples. n Frmula: C = ________n!________ R R! * (n - R)! Ejemplo: Un maestro desea que tres de sus cinco mejores alumnos saquen las mejores notas de la escuela. 5 Respuesta: C = _____5!_____ = ___5!___ = 20 3 3! * (5 - 3)! 3! * 2!

Combinacin con repeticin: Las combinaciones con repeticin, son aquellas agrupaciones de R elementos, que se encuentran linealmente, que se pueden formar a partir de n elementos distintos, donde cada uno de los elementos puede formar parte de la agrupacin, tantas veces como sea posible y sin que pueda importar el orden de ellos. n Frmula: Ckk = ( n + k 1)! k! * (n 1)!

Ejemplo: al lanzar 2 monedas al aire cuntas opciones existen: n Respuesta Ckk = (2 + 2 1)! = ___3!___ = 3*2*1 = 3 2!(2 1)! 2! * 1! 2*1*1 RBOLES Los rboles representan las estructuras no lineales y dinmicas de los datos ms importantes en computacin. Se le llama dinmicas porque la estructura rbol puede cambiar durante la ejecucin de un programa. No lineales, puesto que a cada elemento del rbol seguirle varios elementos.

C D F G

E H I J

A B C

Componentes de un rbol: Un rbol esta formado de varios componentes los cuales son: RAMA: Es la lnea que une a dos nodos. NODO DE BIFURCACION: Es el que se caracteriza como eje y de el se hace una ramificacin ( no vaco) o subrboles. HOJA: Es el que llamamos nodo terminal que encontramos al terminar la ramificacin y lo podemos representar as.

A Nodo de bifurcacin B D E F C H Rama

Hoja

DEFINICIONES BSICAS Son las que nos dice la definicin bsica de un rbol. CAMINO: Es la frecuencia que se lleva al formar un rbol siempre de arriba hacia abajo por ejemplo: A C F G. BOSQUE: Esta formado por un grupo ordenado de rboles. PADRE: Es el nodo que puede o no tener ramificaciones o en otras palabras, todos los nodos excepto el de la raz tiene padre, as el nodo B que es el hijo de A , se dice que este es el padre media vez no all otro en medio. HIJO: Es el que desciende del nodo padre, cuando no hay mas nodos entre A y B. HERMANO: Son los que descienden del nodo B y a la vez se convierten en hermanos de raz. ANCESTRO: Es el cual une a otros nodos, por ejemplo: A es ancestro de G y a la vez es descendiente de A. GENERACIN: Son los que encontramos dentro de un mismo rbol que se encuentra situados en el mismo nivel, sin importar si dependen del mismo padre, por ejemplo: D, E, F, G, son de la misma generacin. LONGITUD DE UN CAMINO: Es l numero de arcos que recorremos para llegar a un nodo en particular desde la raz. As, A tiene longitud 1, B tiene longitud 2, D tiene longitud 3, y as hasta llegar a la hoja. La longitud de un camino puede ser interna y la definimos como la sumatoria de las longitudes que tiene el rbol tal que la podemos llega a calcular as: 1*1 + 2*2 + 4*3 = 21 GRADO: Son los nodos descendientes directos de un nodo en particular. Como en el ejercicio ya visto observamos cuantas ramificaciones tiene cada nodo as Serra el grado que tenga por ejemplo: El grado A es 2 El grado B es 2 El grado C es 2 El grado F es 1 NIVEL: es el numero de arcos que deben ser recorridos para llegar a un determinado nivel, el nodo raz tiene 1 aunque algunos lo definen como 0 , entonces los hijos tendrn como nivel el de su padre + 1. El nivel de A es 1 El nivel de B es 2 El nivel de D es 3 El nivel de E es 3 El nivel de C es 2 El nivel de F es 3 El nivel de G es 4 El nivel de H es 3 PESO: Es el numero de nodos que dependen de l sin contar el mismo.

Caractersticas
Son las que nos permiten conocer las diferentes clases de rboles que existen por ejemplo: RBOLES QUE APARECEN EN OTRO RBOL: Decimos que el rbol L1 aparece en otro rbol L2, si todos los del elemento del primero estn en el segundo y adems cumplen la misma relacin jerrquica entre ellos por ejemplo:

A
B

C E F H F

L2

L1

ARBOL ESTRICTAMENTE BINARIO: Es un rbol donde podemos encontrar que todo nodo que no es hoja tiene asociaciones. En el siguiente ejemplo el rbol L no es estrictamente binario, mientras que el L1 si lo es. En el rbol binario l numero de nodos es igual a 2n-1, donde n indica cuantas hojas tiene el rbol. Ejemplo:

H L G F L1 H

ARBOL BINARIO COMPLETO: Es el rbol en el que todo elemento tiene asociados exactamente 2 sub rboles no vacos ( hijos) y las hojas siempre estn en ultimo nivel. A B C

ARBOL BINARIOS CASI COMPLETOS: Para que un rbol sea cuasi completo debe de cumplir las condiciones siguientes: 1. 2. Cada hoja esta en el nivel d o en el nivel d1. Para todo nodo Nd del rbol con un descendiente derecho en el nivel d , todos los descendientes izquierdos de nd que sea hojas tambin estn en el nivel d .

C H

D K J

NO ES CUASI COMPLETO A

CUASI COMPLETO

RBOLES BINARIOS IGUALES: Son los que si el contenido de los nodos es igual al otro y tiene la misma relacin de parentesco. Por ejemplo.

A B B

A B

==

<>
J

RBOLES BINARIOS SEMEJANTES: Son semejantes si poseen el mismo nmero de elementos y los valores de los nodos del primer rbol son los mismos que los valores del segundo rbol sin importar la relacin entre los mismos. Por ejemplo.

B E

L1 J K

L2

RBOLES ISOMORFOS: Son isomorfos si los dos rboles tienen la misma estructura y el valor de los nodos no es el mismo. Ejemplo:

A B

M E L E

L1

L2 K

RBOLES PERFECTAMENTE EQUILIBRADOS: Un rbol esta perfectamente equilibrado, para todo nodo en el subrbol izquierdo tiene los mismos que en el derecho pero con diferente unidad.

B B D E D E

MANIPULACIN DE ARBOLES
ENUMERACION DE NODOS: En un rbol cuasi completo los nodos se pueden enumerar tal que a la raz de le asigne el 1 , a todo nodo izquierdo se le asigne el doble de su padre y a todo nodo derecho el doble de su padre + 1.

D H I J

E K L

F M N

G O

ARBOL BINARIO EXTENDIDO: Es aquel rbol que se le completan todos sus nodos de manera que debe tener su nodo derecho e izquierdo , y cuando se desea agregar otra hoja se representa por medio de un cuadro . Ejemplo: En el ejemplo podemos observar que el rbol A1 tiene su ramificacin terminada . Y el rbol A2 se le agregaron mas hojas.

A1

A2

ARBOL BINARIO ORDENADO: Es rbol binario ordenado cuando todos los elementos del lado izquierdo son menores que la raz y los del lado derecho son mayores que la raz. Por ejemplo:

2 4

2 5

1 0

2 1

3 0

1 2

2 7

3 1

RECORRIDO DE RBOLES PREORDEN: Primero se visita la raz , luego el subrbol izquierdo y por ultimo el subrbol derecho. INORDEN: Primero visitamos subrbol izquierdo , despus de la raz y por ultimo el subrbol derecho. POSTORDEN: Primero se visita el rbol izquierdo , luego el derecho y por ultimo la raz.

POR NIVELES: De esta forma se visita primero los elementos del nivel 0 ( la raz) , luego todos los del nivel 1 de izquierda a derecha, y as sucesivamente hasta haber visitado todos los elementos . Para poder tener mas claro lo explicado anteriormente es mas fcil saber las formulas siguientes. Preorden: Inorde: Postorden. *+a/bcd*ef a+b/c*de*f abc/+def*-*

Y la grafica es as.

* _ _ / a *

b
RBOLES BINARIOS BALANCEADOS

Para tener un acceso a la informacin, los rboles deben buscar o tener en sus subrboles el mismo nmero de componentes garantizando que en la bsqueda se descarte la mitad de los elementos del conjunto, los rboles con dicha descripcin reciben el nombre de BALANCEADOS BALANCE: Define con la altura de su subrbol izquierdo menor la altura de su rbol derecho. Cada nodo en un rbol binario balanceado tiene balance igual a 1, -1 0, dependiendo si la altura de su subrbol izquierdo es mayor que o igual a la altura de su subrbol derecho. TIPOS DE BALANCE: Existen dos tipos de balance y son:

POR ALTURA: En este rbol la altura de los subrboles asociados con cada elemento no pueden diferir en ms de 1 y 2 subrboles. POR PESO: en este rbol el nmero de elementos en cada uno de los subrboles asociados no puede diferir en ms de uno. RBOLES AVL: Estos tienen la propiedad de que la altura de la rama izquierda menos la altura de la derecha difiere en mximo nivel. FACTOR DE BALANCE Es el factor de balance de cada nodo, la diferencia de las alturas de las ramas izquierda y derecha pertenecen a dicho nodo. Podemos decir que toda hoja tiene un factor de balance igual a 0 y que un rbol es AVL si el factor de balance de todos y cada uno de los nodos que componen el rbol esta en el rango [-1,1 ]. IMPLEMENTACION: Se establece los requerimientos para la implementacin de cada nodo AVL , en memoria lo cual explica que hay que disear cada nodo de la siguiente manera ( empleando el lenguaje C++ ). struct nodo { int info; int balance; struct nodo * izq; struct nodo * der; } RBOLES N-BINARIOS

Un rbol n arios es un grafo dirigido en el cual de cada nodo pueden partir n aristas , sin que sea obligatorio que de cada nodo salga el mismo numero de aristas, y cumpliendo con la definicin formal del rbol a cada nodo solo puede llegar una arista. REPRESENTACIN EN MEMORIA Los rboles n-arios no tienen el nmero constante de nodos hijos lo que hace que la representacin interna en memoria consista en un apuntador a la estructura de datos donde se encuentra el elemento de la raz y donde adems, se mantienen apuntadores a cada uno de sus respectivos subrboles. Esto se puede representar como un vector de apuntadores de tamao M , donde habrn M-1 apuntadores hacia los hijos y un apuntador hacia el contenido del nodo. HIJO IZQUIERDO HERMANO DERECHO La representacin de rboles n-arios en memoria vista anteriormente , presenta dos desventajas fundamentales.

El limitante de la constante definida previamente que nos da la informacin de cual es el nmero mximo de hijos; y el problema del espacio ocupado, ya que aunque tenga un solo hijo la estructura de datos en memoria aparta espacio para representar M-2 hijos mas. La representacin hijo izquierdo hermano derecho no tiene estas limitaciones aunque tiene el problema que es un poco mas complicada la implementacin en los algoritmos. Por medio de esta tcnica el rbol n-arios esta definido como un apuntador a la raz y los hijos , por su parte se encuentra encadenados entre si de izquierda a derecha por medio de apuntadores . Para obtener los subrboles asociados con un nodo , se toma el apuntador de dicho nodo al hijo ms izquierdo y a travs de este, se sigue el encadenamiento definido anteriormente sobre sus hermanos.

A B D E C F

RELACION BINARIA

La relacin binaria considera como un cuadro que muestra las correspondencias de unos elementos con respecto a otros. RELACIONES BINARIAS Una relacin binaria R de un conjunto X a un conjunto Y es un subconjunto del producto cartesiano X x Y. Si (x, y) E R se escribe x R y y se dice que x esta relacionado con y . En el caso X = Y se afirma que R es una relacin binaria sobre X. El conjunto { x E X | (x, y) E R para algn y E Y }, se llama dominio de R. El conjunto { y E Y | (x, y) E R para algn contradominio o mbito de R. EJEMPLO Sea R la relacin sobre X ={1,2,3,4} definida por (x,y) E R si x <= y, x , y E x. Entonces R = {(1, 1),(1, 2), (1,3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

REPRESENTACIN MEDIANTE GRAFICO DIRIGIDO Para establecer el dgrafo de una relacin en un conjunto X, se marca primero los puntos o vrtices que representan los elementos de X. A continuacin, si el elemento (x, y) esta en la relacin , se traza una flecha ( arco dirruido) desde x hasta y. La grafica correspondiente al ejemplo mencionado es:

FORMA NORMAL DISYUNTIVA: La funcin boleana adopta una forma normal disyuntiva . Si esta escrita como una suma de trminos en 3 4 la cual cada trmino es un producto que involucra todos las N variables con negacin y sin ella cada trmino se llama TERMINO MINIMO o MINTERMINO. Y lo podremos definir as:

Fila 0 1 2 3 4 5 6 7

x 0 0 0 0 1 1 1 1

y z 0 0 0 1 1 0 1 1 0 0 1 1 0 0 1 1

f 0 1 0 0 0 1 1 0

f (x, y, z,) x. y. z x. y. z x . y. z x. y. z x. y. z x. y. z x. y. z x. y. z

f ( x, y, z )= x. y. z + x. y. z + x. y. z y. z ( x + x ) + x y z f ( x, y, z ) 0 m ( 1, 5, 6)

FORMA NORMAL CONJUNTIVA: La funcin boleana adopta la funcin normal conjuntiva si esta escrita como un producto de trminos en el cual el termino es una suma que involucra todos los N variables con complementacin o sin ella. Cada termino se llama: Termino Mximo , la forma normal conjuntiva completada N variable es = 0 y se obtiene de las variables complementadas.