Matemáticas Discretas 2.11.12 B.docx

8/18/2019 Matemáticas Discretas 2.11.12 B.docx

1/57

icación de Matemáticas

2012

Lic. Narciso Torres Irigoyen

Conalep Mazatlán IIemestre 2.11.12

Índice


2/57

A!LICACI"N D# MAT#M$TICA DIC%#TA 2.11.12

Unidad I

Identificación de sistemas numéricosConcepto de sistema numérico…………………………………………………………………………..Sistema decimalSistema binario

Sistema octalSistema hexadecimalOperaciones con sistemas numéricosConversionesSuma de dos cantidadesAplicación de los sistemas numéricosIdentificación de métodos de conteoConceptorincipios fundamentales del conteoermutacionesCombinacionesAplicaciones en el !rea de la computación"ri!n#ulo de ascal

Unidad II

$epresentación de con%untosConcepto de con%untoSubcon%untos&ia#ramas de 'ennOperaciones ( le(es de con%untosUniónIntersección)e( distributiva**Complemento)e( de +or#an**&iferencia&iferencia simétrica**Simplificación de expresiones usando le(es de con%untos**$elación entre teor,a de con%untos- ló#ica matem!tica ( !l#ebra booleana***enerali/ación de con%untos finitos**0mpleo de ló#ica matem!tica con preposicionesConceptoroposiciones 11$epresentación de tablas de verdad"autolo#,aContradicciónContin#encia

Uso de inferencia ló#icaInductiva&eductiva02uivalencia ló#icaAr#umentos v!lidos ( no v!lidos&emostración formal de ar#umentos+ane%o de predicados ( sus valores de verdad)ó#ica de predicados

Lic. Narciso Torres IrigoyenPágina 2


3/57


Inducción matem!ticaAplicación de la ló#ica matem!ticaSimplificación de expresiones booleanasIntroducción0xpresiones booleanasropiedades de las expresiones booleanas

Optimi/ación de expresiones booleanasSimplificación de expresiones booleanas con teoremas del !l#ebra de 3oole+apas de 4arnau#hCompuertas ló#icas&efiniciónCompuertas b!sicasCompuertas compuestasAplicaciones del !l#ebra booleana

Unidad III

Uso de relaciones0lementos de una relación

Clasificación por tipo de relaciones$elaciones de e2uivalencia- clases de e2uivalencia ( particionesOperaciones entre relacionesropiedades de las relacionesAplicaciones de las relaciones0mpleo de funcionesComposición de funciones"ipos de funciones5unciones invertiblesAplicación de las funciones0mpleo de #rafosartes de un #rafo"ipos de #rafos$epresentación matricialCaminos ( circuitosIsomorfismorafos planosUso de !rbolesropiedades de los !rboles"ipos de !rboles3os2ues



4/57


Identificación de Sistemas Numéricos

Sistema Decimal

#ste sistema es &tilizado por la '&manidad desde 'ace m&c'os a(os para contar. #s &n deri)ado de la n&meración 'ind*+ introd&cido a la

#&ropa Mediterránea por los ára,es. e caracteriza por ser posicional+ es decir+ -&e el )alor de cada sm,olo /0+ 1+ 2+ + + + 3+4+ 5+ 67 depende de la posición donde se &,i-&e+ dentro de la presentación de &n n*mero+ en 8&nción de &n p&nto /llamadodecimal7.

#9iste &na 8órm&la para relacionar &na cantidad e9presada enc&al-&ier otro sistema n&m:rico con el decimal /teorema8&ndamental de la n&meración7; No. < s&matoria de i < =d 'asta i <n+ de /dgito71 > /,ase71

Donde;

No. < la cantidad en decimal /el )alor ,&scado7

i < la posición respecto al p&nto

d < el n*mero de dgitos a la derec'a del p&nto

n < el n*mero de dgitos a la iz-&ierda del p&nto menos 1


?nidad I

#mplea sistemasn&m:ricosy m:todos de conteo


5/57


dgito < cada &no de los componentes del n*mero

,ase < la ,ase re8erenciada como patrón / -&e para el sistema decimal es 107

!or lo -&e el n*mero @LMB con ,ase @B+ en decimal -&edara;

No. < > 2 L > 1 M > 0

iendo + L y M los *nicos sm,olos empleados por este sistema.

i '&,iera &n sistema -&e contemplara sólo los n*meros 0+ 1+ 2 y /,ase 7 y representarael n*mero 5623+ en decimal sera;

5 > 6 > > 2 2 > 1 3 > 0 <

205 43 3 5 3 < 2+402

Sistema Binario

La ,ase de este sistema es dos. Considera sólo los dgitos 1 y 0. #sta es la razón de s&&tilización en la representación interna de datos en las comp&tadoras / 1 < imp&lso el:ctrico+ 0 < no'ay imp&lso7+ y cada dgito reci,e el nom,re de ,it /contracción de EInary digiT7.

Agr&paciones de ,its reci,en di8erentes nom,res como se menciona a contin&ación;

1 c&arteto < ,its

1 octeto < 5 ,its

1 F < 1+02 ,ytes < 1+02 > 5 ,its < 5+162 ,its

1 mega < 1+02 F,ytes < 1+02 > 1+02 > 5 ,its < 5G55+305 ,its

1 giga < 1+02 megas < < 1+02 > 1+02 > 1+02 > 5 ,its < 5+56G6+62 ,its

De esta 8orma+ con el empleo del teorema 8&ndamental de la n&meración /HTN7+ el n*mero ,inario 111000 en decimal sera;

1 > 2 1 > 2 1 > 2 0 > 22 0 > 21 0 > 20 < 2 13 5 < 3

Sistema Octal

La ,ase de este sistema es 5+ considera sólo los dgitos 0+ 1+ 2+ + + + 3 y 4.

Al ig&al -&e el sistema decimal+ el octal es posicional+ de esta manera la n&meración del 0al 1 decimal sera en octal;



6/57


0+ 1+ 2+ + + + 3+ 4+ 10+ 11+ 12+ 1+ 1+ 1+ 13+ 14

donde de ac&erdo con la posición se interpretara;

10 < 5 0 < 5

11 < 5 1 < 6

12 < 5 2 < 10

1 < 5 < 11

1 < 5 < 12

Sistema Hexadecimal

La ,ase de este sistema es 13 y emplea los sig&ientes sm,olos para representar cantidades;

0+ 1+ 2+ + + + 3+ 4+ 5+ 6+ A+ E+ C+ D+ #+ H

asignando )alores a,sol&tos a las letras como sig&e;

A < 10

E < 11

C < 12

D < 1

# < 1

H < 1

al ig&al -&e los sistemas anteriores es posicional+ de tal 8orma -&e la n&meración del 0 al20+ en 'e9adecimal sera;

0+ 1+ 2+ + + + 3+ 4+ 5+ 6+ A+ E+ C+ D+ #+ H+ 10+ 11+ 12+ 1+ 1

as&miendo posicionalmente -&e;

Je9. 10 < 13 0 < 13 Decimal

11 < 13 1 < 14

12 < 13 2 < 15

1 < 13 < 16



7/57


1 < 13 < 20

etc:tera.

Operaciones con Sistemas Numéricos

Conversiones

Conversión de Decimal a Binario, Octal y Hexadecimal

Los n*meros decimales p&eden ser enteros+ 8racciones o am,os+ por lo -&e s& con)ersión a ,inario es realizada por separado. !ara los enteros+ se di)ide s&cesi)amente entre dos el n*merodecimal 'asta llegar a @0BK los resid&os se consideran en orden in)erso a s& o,tención y as seo,tiene el n*mero ,inario+ por eemplo+ para con)ertir el n*mero decimal 52+ al sistema ,inario;

2 ; 52 0

2 ; 1 1

2 ; 20 0

2 ; 10 0

2 ; 1

2 ; 2 0

2 ; 1 1

0

!or lo -&e el n*mero 52 decimal+ en ,inario es 10100010.

#n el caso de las 8racciones decimales+ :stas se m&ltiplican por 2+ se toma el )alor del entero de laoperación como parte del n*mero ,inarioK se elimina de la 8racción decimal y se )&el)e am&ltiplicar+ reptieno el proceso 'asta desaparecer la cantidad 8raccionada o+ ,ien+ 'asta &ndeterminado n*mero de dgitos ,inarios -&e permitan operar sin error+ por eemplo;

!ara con)ertir la 8racción decimal 0.42+ a ,inario;

0.42 > 2 < 1.0 ... 1

0.0 > 2 < 1.005 ... 1



8/57


0.005 > 2 < 0.013 ... 0

0.013 > 2 < 0.02 ... 0

0.02 > 2 < 0.03 ... 0

0.03 > 2 < 0.125 ... 0

0.125 > 2 < 0.23 ... 0

0.23 > 2 < 0.12 ... 0

0.12 > 2 < 1.02 ... 1

-&edando 0.42 /10 < 0.110000001 /2 con error in8erior de 2=6

!ara con)ertir enteros decimales a octal+ tam,i:n se di)ide s&cesi)amente entre 5 'astallegar a @0B y se consideran los resid&os de 8orma in)ersa a s& o,tención+ eemplo;

5 ; 543

5 ; 106

5 ; 1

5 ; 1 1

0

!or lo -&e el n*mero decimal 543 en octal es 1.

#n el caso de los n*meros 8raccionarios decimales es el mismo proceso para el ,inario+incl&si)e para 'e9adecimal+ sólo -&e se m&ltiplica por 5 y por 13 respecti)amente. !or eemplo+con)ertir el n*mero 8raccionario decimal 0.36 al sistema octal;

0.36 > 5 < .2 ...

0.2 > 5 < .13 ...

0.13 > 5 < .25 ...

0.25 > 5 < 2.32 ... 2

0.32 > 5 < .662 ...

0.662 > 5 < 4.63 ... 4

0.63 > 5 < 4.55 ... 4

0.55 > 5 < .60 ...



9/57


As+ el n*mero 8raccionario decimal 0.36 en el sistema octal es ig&al a 0.442 con &n error menor a 5=5

!ara con)ertir enteros decimales a 'e9adecimal es el mismo proceso de di)isión+ con la)ariante de emplear los )alores a,sol&tos asignados a las letras A+ E+ C+ D+ # y H+ eemplo;

13 ; 241 ..1........ H

13 ; 13 0 ..........

13 ; 1 1 ..........

0

!or lo -&e el n*mero 241 decimal+ en 'e9adecimal es 10H.

De ig&al modo+ las 8racciones se o,tienen mediante la m&ltiplicaciónK con)ertir el n*mero8raccionario decimal 0.65 a 'e9adecimal;

0.65 > 13 < 1.005 ... 1 ... H

0.005 > 13 < 0.125 ... 0

0.125 > 13 < 2.05 ... 2

0.05 > 13 < 0.435 ... 0

0.435 > 13 < 12.255 ... 12 ... C

0.255 > 13 < .305 ...

!or lo -&e el n*mero 8raccionario decimal 0.65 es en el sistema 'e9adecimal ig&al a0.C020H. Con &n error in8erior a 13=3

Conversión de Binario a Decimal, Octal y Hexadecimal

!ara con)ertir &n n*mero ,inario a decimal e9isten dos 8ormas; primero se de,e colocar el ,inario de manera )ertical+ con el dgito de la derec'a en la parte s&periorK se comienza el procesodesde la parte in8erior y se s&ma el dgito al prod&cto de dos por el res&ltado de la operaciónanterior considerando cero para la primera iteración+ y el res&ltado será el de la *ltima operaciónK para con)ertir el n*mero ,inario 110010 al sistema decimal;

0 2 > 2 < 0

1 2 > 12 < 2



10/57


0 2 > 3 < 12

0 2 > < 3

1 2 > 1 <

1 2 > 0 < 1

%es&ltando -&e 110010/2 < 0/10

#l seg&ndo m:todo s&ma las potencias de dos+ de ac&erdo con el sistema ,inario+ y sólo dea-&:llas con )alor ig&al a &noK del eemplo anterior se tendrá;

Einario; 1 1 0 0 1 0

!osición; 2 1 0

!otencia de 2; 2 2 2 22 21 20

&mas; 2 13 2 < 0 decimal

A'ora ,ien+ para con)ertir &n n*mero ,inario a octal se realizan agr&pamientos de tresdgitos /dado -&e se necesitan tres ,its para representar del 0 al 4 en ,inario7+ y se da s&e-&i)alencia en octalK por eemplo+ para con)ertir el n*mero ,inario11111010001 al sistema octal;

e agr&pa por tres dgitos el n*mero ,inario;

11 111 010 001 y se asigna s& )alor correspondiente;

4 2 1 por lo tanto

1111101 0001/2 < +421/5

#l proceso para la con)ersión de ,inario a 'e9adecimal es semeante al anterior+ con ladi8erencia de -&e se 'acen agr&pamientos de c&atro dgitos /por la representación ,inaria de 0 al 13con c&atro ,its7K por eemplo+ se con)ierte el n*mero ,inario 1010111111010011 a 'e9adecimaldi)idiendo el n*mero en gr&pos de ,its;

1010 1111 1101 0011 se asignan s& )alor correspondiente;

10 1 1 y se s&stit&ye el )alor de las letras;

A H D -&eda 8inalmente -&e

1010111111010011 /2 < AHD/13

!ara realizar estas operaciones es con)eniente tener en c&enta &na ta,la de e-&i)alenciascomo la sig&iente;



11/57


Decimal ctal Je9adecimal Einario0 0 0 00001 1 1 00012 2 2 0010 0011 0100

01013 3 3 01104 4 4 01115 10 5 10006 11 6 100110 12 A 101011 1 E 101112 1 C 11001 1 D 11011 13 # 11101 14 H 1111

Conversión de Octal a Decimal, Binario y Hexadecimal

#l m:todo más generalizado para la con)ersión de n*meros octales a decimales es el delTHN+ &sando ,ase 5K por eemplo+ para con)ertir el n*mero octal 43 a decimal se realiza

43/5 < > 52 4 > 51 3 > 50 < 52/10

!ara la con)ersión de octales a ,inarios+ se separa cada dgito y se le asigna s&correspondiente ,inario en 8&nción de tres ,itsK por eemplo+ para con)ertir el n*mero octal 4 a ,inario;

4/5 < 100 111 101 < 100111101/2

Como se nota+ el proceso es in)erso a la con)ersión ,inario octal.

!ara la con)ersión de octal a 'e9adecimal es necesario 'acer &n paso intermedio+ el de lacon)ersión octal a ,inario y de :ste a 'e9adecimalK por eemplo+ para con)ertir el n*mero octal4+1 a 'e9adecimal;

!rimero se con)ierte a ,inario

4+1/5 < 111 100 101 001/2

desp&:s se agr&pa en c&artetos y se o,tiene;

1111 0010 1001/2 < H26/13

Conversión de Hexadecimal a Decimal, Binario y Octal



12/57


!ara la con)ersión de 'e9adecimal a decimal es con)eniente emplear la 8órm&la del THN/ig&al al caso octal decimal7+ por ser más generalizadaK as+ con el empleo de ,ase 13 se tiene -&e + para con)ertir #1H 'e9adecimal a decimal;

#1H/13 < # > 132 1 > 131 H > 130

< 1 > 132 1 > 131 1 > 130

< +5 13 1 < +31/10

i se &sa la ta,la descrita anteriormente+ se realiza la con)ersión de 'e9adecimal a ,inario+empleando c&atro ,its para representar cada carácter+ por eemplo;

6EA/13 < 1001 1011 1010 0101/2 < 1001101110100101/2

Asimismo+ para la con)ersión de 'e9adecimal a octal se necesita n&e)amente del sistema ,inario como paso intermedio de la con)ersiónK por eemplo+ para con)ertir el n*mero 'e9adecimal

AH6 a octal;

!rimero se con)ierte a ,inario y se agr&pa en c&artetos;

AH6/13 < 0100 1010 1111 1001/2

y l&ego se agr&pan por tres y se asigna el )alor octal;

AH6/13 < 100 101 011 111 001/2

< 4 1/5

Suma de dos cantidades

Suma y Resta Binaria

Las s&mas en el sistema ,inario son semeantes a lo e8ect&ado en el sistema decimalK tienecomo ,ase la sig&ientes ta,la;

0 0 < 0

0 1 < 1

1 0 < 1

1 1 < 10 /cero y se acarrea 17

1 1 1 < 11 /1 y se acarrea 17



13/57


#n el caso de la resta de,emos tener en c&enta lo sig&iente;

a7 i el n*mero a restar /s&straendo7 es menor -&e el min&endo /Caso 17 ,7 i el n*mero a restar es mayor -&e el min&endo /Caso 27

Caso 1

101111= 101010

OOOOOOOOOOO

%ealice los sig&ientes pasos;

Complementar a 1 el n*mero a restar / complementar a 1 signi8ica cam,iar el )alor de todos los ,its7

101010 < 010101

&mar el primer )alor /min&endo7 con el complemento a 1

101111 010101

OOOOOOOO 100100

Tomar el ,it de la iz-&ierda y s&marlo con el resto

00100 1

OOOOOOOO 00101

Caso 2

101010

= 101111 OOOOOOOOOOO

%ealice los sig&ientes pasos;

Complementar a 2 el n*mero a restar / complementar a 1 signi8ica cam,iar el )alor de todos los ,itsdesp&:s de encontrar el primer dgito signi8icati)o @1B7



14/57


101111 < 010001

&mar el primer )alor /min&endo7 con el complemento a 2

101010 010001

OOOOOOOO 111011

Complementar a 2 el res&ltado a e9cepción del ,it de la iz-&ierda /el c&al representa el signo @=@7

100100

Suma y Resta Octal

La s&ma en el sistema octal es semeante al sistema decimal. i al momento de e8ect&ar las&ma el res&ltado es ig&al o mayor a la ,ase /57 se le resta 5 y acarreamos 1.

34 3

OOOOOOO 1 0

#n el caso de la resta seg&imos los sig&ientes pasos;

34= 43

OOOOOOO

Tomar el n*mero a restar y representar el mayor n*mero posi,le en la ,ase seg*n el n*mero dedgitos

N*mero de dgitos ; 43Mayor n*mero -&e se p&ede representar en octal con dgitos; 444

%estar el mayor n*mero -&e se p&ede representar menos el min&endo

444= 43

OOOOOOO 01

&mar el res&ltado con el primer n*mero de la resta

34 01



15/57


OOOOOOOO 1130

Tomar el dgito de la iz-&ierda y s&marlo con el resto

130

1 OOOOOO

131

Suma y Resta Hexadecimal

La s&ma en el sistema 'e9adecimal es semeante al sistema decimal. i al momento dee8ect&ar la s&ma el res&ltado es ig&al o mayor a la ,ase /137 se le resta 13 y acarreamos 1.

3A4 E3

OOOOOOO 120C6

#n el caso de la resta seg&imos los sig&ientes pasos /tal y como se 'izo con el sistema octal7;

A3E4= 5CD

OOOOOOO

Tomar el n*mero a restar y representar el mayor n*mero posi,le en la ,ase seg*n el n*mero dedgitos

N*mero de dgitos ; 5CDMayor n*mero -&e se p&ede representar en octal con dgitos; HHHH

%estar el mayor n*mero -&e se p&ede representar menos el min&endo

HHHH= 5CD

OOOOOOO 4E2

&mar el res&ltado con el primer n*mero de la resta

A3E4 4E2

OOOOOOOO 11A36

Tomar el dgito de la iz-&ierda y s&marlo con el resto



16/57


1A36 1

OOOOOO 1A3A

Aplicación de los sistemas numéricos

#l sistema ,inario se &tiliza a ni)el de 'ardPare+ en ese ni)el todo se red&ce a p&lsos el:ctricos enlos c&ales solo se entiende QencendidoQ o QapagadoQ es decir &nos y ceros a estos imp&lsos se lesllama ,its+ el octal se &sa al momento de Qempa-&etarQ los ,its en gr&pos de 5 meor conocidoscomo octetos o ,ytes y son *tiles para sa,er el anc'o de ,anda de alg*n ,&s o peri8:rico+ es decir c&anta in8ormación p&ede mandarse a tra):s de tal dispositi)o en &n solo ciclo de relo+ el'e9adecimal se &tiliza para Qinde9arQ las direcciones de memoria ya -&e al tener mas dgitos es &nsistema de n&meración -&e permite representar n*meros mas grandes con menos in8ormación. #ldecimal solo se &sa al momento de com&nicarse con el &s&ario.

Identificación de métodos de conteo

Concepto

Los métodos de conteo son estrategias &tilizadas para determinar el n*mero de posi,ilidades di8erentes -&e e9isten al realizar &n e9perimento+ son reglas o procedimientos -&e se'an desarrollado para contar sin tener -&e listar o en&merar.

Principio Fundamental de Conteo

#l principio 8&ndamental de conteo es tam,i:n llamado regla del prod&cto.

e!la del Producto "dos pasos#

&pongamos -&e &n proceso consiste de dos pasos. i 'ay n1 maneras de 'acer el primer paso y n2maneras de 'acer el seg&ndo paso+ entonces 'ay n1 9 n2 maneras de 'acer el proceso completo.

e!la de Producto "$ pasos#

&pongamos -&e &n proceso consiste de k pasos. i 'ay n1 maneras de 'acer el primer paso+n2 maneras de 'acer el seg&ndo paso+ R+ y nk maneras de 'acer el *ltimo paso+ entonces 'ay n1 x n2 x … x nk maneras de 'acer el proceso completo.

La regla del prod&cto es sin l&gar a d&das la 'erramienta más importante -&e se &sa pararesol)er prolemas de conteo.



17/57


!lanteada de manera in8ormal+ la regla del prod&cto dice -&e cuando un evento ocurre devarias etapas, para encontrar el n!mero total de maneras en "ue ocurre, se multiplican los

n!meros de maneras "ue en cada etapa individual ocurre.

Permutaciones

A &n arreglo de o,etos en &n orden de8inido se le llama &na permutación.

#l n*mero de perm&taciones de n o,etos distintos es nS

A &n arreglo ordenado de r o,etos seleccionados de &n con&nto de n o,etos /r n7 se lellama permutación de n ob%etos tomados r a la ve/.

5órmula para ermutaciones

n

r # < 7S/

Sr n n−

#l n*mero de perm&taciones de n o,etos+ de los c&ales a o,etos son ig&ales+ otros o,etos son ig&ales+ otros c o,etos son ig&ales+ etc.+ es;

...SSS

S

x xc xa

n

Com%inaciones

?na combinación es &na selección de o,etos en la -&e el orden no es importante.

A &n arreglo de r o,etos /sin importar el orden7 seleccionados de &n con&nto de n o,etosdistintos le llamamos &na combinación de n ob%etos tomados r a la ve/.

5órmula para Combinaciones

n

r C < S7S/

S

xr r n

n

−

Aplicaciones en el &rea de la computación'ri&n!ulo de Pascal

#s &n arreglo de n*meros ,a&tizado as en 'onor al matemático 8ranc:s Elaise !ascal -&ienlo introd&o al m&ndo occidental en 133. sin em,argo+ el triáng&lo ya 'a,a aparecido más de 200a(os antes+ en p&,licaciones de los matemáticos c'inos a& &i y C'& 'i'=C'ie'.



18/57


Renglones

0 11 1 12 1 2 13 1 3 3 1

4 1 4 6 4 15 1 5 10 10 5 16 1 6 15 20 15 6 17 1 7 21 35 35 21 7 18 1 8 28 56 70 56 28 8 19 1 9

36 84126

126 84 36 9 1

10 1 10 45 120

210

252

210

120 45 10 1

11 1 11 55 165

330

462

462

330

165 55 11 1


?nidad II

Manea lógicamatemática yálge,ra ,ooleana


19/57


epresentación de con(untos

Concepto de con(unto



20/57


Llamamos con&nto a &na colección de o,etos.

?n con&nto es toda colección de o,etos ,ien de8inidos e identi8ica,les. A los o,etos se lesllama elementos o miem,ros del con&nto. A los con&ntos &s&almente se les denota con letrasmay*sc&las /A+ E+ C+ R7K a los elementos por lo general se les designa mediante letras min*sc&las

/a+ ,+ c+ R+ 9+ y+ z7.

#l &so de lla)es U...V indicará &n con&nto c&yos elementos aparecerán entre estas.#emplo;

A < U a+ ,+ c+ d V

e reconocen 2 m:todos para e9presar con&ntos. #stos m:todos son el de e9tensión/en&meración7 y el de comprensión /caracterstico7.

?n con&nto está descrito por en&meración si se 'an dado e9plcitamente todos s&selementos. /27

?n con&nto está descrito por comprensión si s&s elementos están dados en 8orma implcitamediante &na 8rase -&e los descri,a. /27

#emplos por en&meración;A < U 0+ 1+ 2+ + + + 3+ 4+ 5+ 6 VE < U 2+ + + 4+ 11+ 1+ 14+ 16 VC < U Wos:+ Eert'a+ %a8ael+ %o,erto+ Mara VD < U X&atemala+ Eelice+ #stados ?nidos V

#emplos por en&meración;A < U ,reros me9icanos -&e tra,aan en #stados ?nidos VE < U !ases Latinoamericanos V

C < U Manzanas prod&cidas en M:9ico VD < U !ersonas a -&ienes se les 'a otorgado &n premio No,el V

La Cardinalidad de &n con&nto es el n*mero de elementos de este. /27

#emplos;i A < U 2 V entonces Y/A7 < 1i E < U + + V entonces Y/E7 < i C < U a+ ,+ c V entonces Y/C7 <

!ara indicar -&e &n o,eto es elemento de &n con&nto o pertenece a &n con&nto se emplea

el sm,olo ∈.

#emplo;a ∈ A /a es &n elemento de A Z a pertenece al con&nto A7

in &n elemento no pertenece al con&nto se &tiliza el sm,olo ∉.



21/57


#emplo;i A < U a+ ,+ c+ d V entonces ∉ A

#n general+ no es signi8icati)o el orden en -&e se anotan los elementos de &n con&ntoKademás se entiende -&e los elementos de &n con&nto son distintos.

#emplos;U a+ ,+ c V y U c+ a+ , V se consideran &no mismo

La colección a+ ,+ c+ d+ ,+ c+ a no constit&ye &n con&nto de 4 elementos+ sino &n con&nto de elementos U a+ ,+ c+ d V.

Su%con(unto

i cada elemento del con&nto A es tam,i:n elemento del con&nto E se dice -&e A ess&,con&nto de E.

!ara indicar &n s&,con&nto se &tiliza el sm,olo ⊆.i A no es s&,con&nto de E se &tiliza el sm,olo .#emplos;i A < U a+ ,+ c V y E < U a+ ,+ c+ d V entonces A⊆ E i A < U a+ ,+ e V y E < U a+ ,+ c+ d Ventonces A Ei A < U 3+ 5 V y E < U 2+ + 3+ 5+ 10 V entonces A ⊆ E i A < U + + 3+ 4 V y E < U + + 3 Ventonces A Ei A < U + + 3 V y E < U + + 3 V entonces A ⊆ E i A < U r+ s+ t V y E < U r+ s+ t Ventonces A ⊆ E

#n relación con los dos *ltimos eemplos A ⊆ A+ por lo tanto todo con&nto es s&,con&ntode si mismo.

Sucon$unto #ropio

i A es &n s&,con&nto de E+ y si 'ay por lo menos &n elemento de E -&e no sea elementode A+ se dice -&e A es &n s&,con&nto propio de E.

!ara indicar &n s&,con&nto se &tiliza el sm,olo ⊂.i A no es s&,con&nto de E se &tiliza el sm,olo ⊄.

#emplos;i A < U a+ ,+ c V y E < U a+ ,+ c+ d V entonces A⊂ Ei A < U 3+ 5 V y E < U 2+ + 3+ 5+ 10 V entonces A ⊂ Ei A < U + + 3 V y E < U + + 3 V entonces A ⊄ E

e o,ser)a -&e si A es &n s&,con&nto propio de E+ entonces con toda seg&ridad A es &ns&,con&nto de E.

Con$unto vac%o



22/57


#l con&nto )aco es el -&e no tiene elementos.!ara designar a este tipo de con&ntos se &tiliza el sm,olo ∅.

#emplo;A < U V o A < U ∅ V

Nota; #l con&nto )aco es &n s&,con&nto de c&al-&ier otro.

&niverso

#l con&nto de todos los elementos -&e -&eremos considerar en &n est&dio partic&lar reci,eel nom,re de Con&nto ?ni)ersal o ?ni)erso. #n consec&encia+ cada &no de los con&ntos &tilizadosen &n caso partic&lar+ será &n s&,con&nto del Con&nto ?ni)erso.

!ara denotar el con&nto &ni)erso se &tiliza la letra ?.

Con$untos i'uales (i'ualdad de con$untos)

C&ando los con&ntos A y E tienen e9actamente los mismos elementos se dice -&e talescon&ntos son ig&ales y se denota la ig&aldad con el signo


23/57


.nión

La &nión de los con&ntos A y E es el con&nto de o,etos -&e son elementos de por lo

menos &no de los dos con&ntos A y E.

Intersección

Dados dos con&ntos A y E+ la intersección de A y E+ -&e se escri,e A ∩ E+ es el con&nto 8ormado por todos a-&ellos elementos -&e son com&nes al con&nto A y al con&nto E.

Complemento

i tenemos &n &ni)erso ? y A es &n s&,con&nto de ?+ el con&nto 8ormado por todos a-&elloselementos de ? -&e no pertenecen a A+ se llama complemento de A y se denota AG.

Diferencia



24/57


La di8erencia del con&nto A y el con&nto E+ denotada A E+ es el con&nto 8ormado por loselementos -&e están en A pero no están en E.

#ercicios

1. Determinar c&ales de los sig&ientes en&nciados son )erdaderos y c&ales son 8alsos

2. %ealice lo sig&iente;a7 Jaga &na lista de los s&,con&ntos de U 1+ 2 V ,7 \ C&ales de estos son s&,con&ntos propios de U 1+ 2 V]

. %ealice lo sig&iente;a7 Jaga &na lista de los s&,con&ntos de U 1+ 2+ V ,7 \ C&ales de estos son s&,con&ntos propios de U 1+ 2+ V]

. Jaga &na lista de los s&,con&ntos de U 1+ 2+ + + V -&e tengan e9actamente elementos. i A < U 1+ 2+ + V+ \c&áles son los con&ntos de E tales -&e U 1+ 2 V ⊂ E y E ⊂ A]3. Complete cada &no de los en&nciados sig&ientes para dar &na resp&esta correcta

a7 U 1+ 2+ + V ∪ U 2+ + V ,7 U 1+ 2+ + V ∪ U + Vc7 U 1+ 2+ + V ∩ U 2+ + Vd7 U 1+ 2+ + V ∩ U + 3+ 4 Ve7 U 1+ + + 4V ∩ U 2+ + + + 3 V87 U 1+ + + 4V ∪ U 2+ + + + 3 Vg7 U 2+ + 3 V ∩ U 3+ 10+ 1 V

4. !ara los con&ntos A < U a+ ,+ c+ d V y E < U ,+ d+ e V 'allar;a7 A∩ E ,7 A∪ Ec7 A∩ Ad7 A∪ Ae7 A∩ ∅

87 A∪ ∅5. i ? < U 1+ 2+ + + + 3 V+ A < U 1+ 2+ V+ E < U 2+ V y C < U V o,tener AG+ EG y CG6. i ? < U 1+ 2+ + + + 3+ 4+ 5+ 6 Vo,tenre el complemento para cada &no de los con&ntos

sig&ientes;a7 A < U 1+ 2+ + V ,7 E < U 1+ + + 4+ 6 Vc7 C < U 2+ + 3 V ∪ U 1+ 2+ + 4 V



25/57


10. #n&mere cada &no de los sig&ientes con&ntos por el m:todo de e9tensión /en&meración7a7 #l -&e tiene por elementos las letras -&e 8orman la pala,ra @estadsticaB ,7 #l -&e tiene por elementos los dgitos -&e aparecen en el n*mero 450000000000c7 #l -&e tiene por elementos las letras -&e entran en la 8ormación de la e9presión @in8erencia

estadsticaB11. #scri,a por el m:todo de comprensión cada &no de los anteriores con&ntos

12. Determine c&ales de los sig&ientes con&ntos son 8initos y c&ales in8initosa7 #l con&nto de los enteros entre 10 y 30

,7 #l con&nto de los enteros no negati)os paresc7 #l con&nto de los ,ecerros -&e 'an nacido y -&e )an a nacer en todo el m&ndod7 #l con&nto de todas las sociedades anónimase7 #l con&nto de los enteros s&periores a 1+0001. #n &n reconocimiento de 100 atletas se encontró -&e se especializaron as; en ,ase,all+

0 en ,asFet,all+ 0 en 8&t,olK en ,ase,all y ,asFet,all 1+ en ,ase,all y 8&t,ol 10+ en ,asFet,all y 8&t,ol 1 y en los tres deportes .

\C&ántos atletas no se especializaron en ning*n deporte]\C&ántos atletas se especializaron sólo en 8&t,ol]1. #n &n est&dio so,re las matemáticas de 0 est&diantes inscritos en estadstica+ se encontró

-&e el n*mero de est&diantes -&e 'a,ian c&rsado distintas asignat&ras de matemáticas eracomo sig&e; álge,ra de matrices 2+ geometra analtica 15+ matemática 8inita 1+ álge,ra de

matrices y geometra analtica + álge,ra de matrices y matemática 8inita 3+ geometraanaltica y matemática 8inita + y todas las materias 1.

a7 \C&ántos est&diantes 'ay -&e amás 'an tomado ning&na de las tres materias] ,7 \C&ántos est&diantes 'an tomado solo álge,ra de matrices]+ \solo geometra analtica]+

\solo matemática 8inita]c7 \C&ántos est&diantes 'an tomado solamente álge,ra de matrices y geometra analtica]d7 \C&ántos est&diantes 'an tomado solo álge,ra de matrices y matemática 8inita] \solo

geometra analtica y matemática 8inita]

/mpleo de ló!ica matem&tica con preposiciones

Concepto

La lógica matemática es la disciplina -&e trata de m:todos de razonamiento. #n &n ni)elelemental+ la lógica proporciona reglas y t:cnicas para determinar si es o no )alido &n arg&mentodado. #l razonamiento lógico se emplea en matemáticas para demostrar teoremasK en ciencias de lacomp&tación para )eri8icar si son o no correctos los programasK en las ciencias 8sica y nat&rales+ para sacar concl&siones de e9perimentosK y en las ciencias sociales y en la )ida cotidiana+ para



26/57


resol)er &na m&ltit&d de pro,lemas. Ciertamente se &sa en 8orma constante el razonamiento lógico para realizar c&al-&ier acti)idad.

?na tabla de verdad es &n c&adro o diagrama -&e presenta los posi,les )alores de )erdadde &n en&nciado más o menos compleo+ determinado por cierto conecti)o+ y en correspondenciacon los )alores de )erdad posi,les de s&s en&nciados componentes.

Proposiciones

#n general+ &na proposición es &n en&nciado declarati)o -&e p&ede considerarse como 8alsoo )erdadero+ pero no am,as cosas al mismo tiempo. #sta capacidad de ser clasi8icadas como 8alsaso )erdaderas 'ace -&e las proposiciones di8ieran de las preg&ntas+ órdenes o e9clamaciones.

#emplos de proposiciones;

• Caracas es la capital de [enez&ela• Dos es &n n*mero par y es menor -&e )einte• #n Miami 'ay cinco mil millones de granos de arena• est&dias diariamente o repr&e,as este c&rso

#emplo de No proposiciones

o \-&: 'ora es]o SWim:nez para presidenteSo Cierra la p&erta

Las proposiciones p&eden ser simples o comp&estas. !or eemplo+ @W&an mide 1.60 mts es &na

proposición simple. !or otra parte+ el en&nciado @W&an mide 1.60 mts y &ega ,asFet,olB es &na proposición comp&esta.

Como podemos darnos c&enta+ e9isten m&c'as maneras de com,inar proposiciones simples para 8ormar proposiciones comp&estas. Tales com,inaciones se 8orman &tilizando conecti)os+ losc&ales &nen a las proposiciones. Dos de las más importantes son y y o.

&pongamos -&e se &san las letras p y - para representar a las sig&ientes proposiciones;

!; Joy 'ace calor ^; #l acondicionador de aire de esta 'a,itación está descomp&esto.

!&eden 8ormarse las sig&ientes proposiciones comp&estas;

! y -; Joy 'ace calor y el acondicionador de aire de esta 'a,itación está descomp&esto.

! o -; Joy 'ace calor o el acondicionador de aire de esta 'a,itación está descomp&esto.

#l conecti)o @yB se sim,oliza por @_@ mientras -&e el conecti)o @oB se sim,oliza por @[B.



27/57


i dos proposiciones están &nidas por la pala,ra @yB+ a la proposición res&ltante se le llamacon&nción.

La ta,la de )erdad para el conecti)o y /con&nción7 es;

p q p y q / p _ qV V VV F F

F V F

F F F

i dos proposiciones están &nidas por la pala,ra @oB+ a la proposición res&ltante se le llamadisy&nción.

La ta,la de )erdad para el conecti)o o /disy&nción7 es;

p q p o q / p [ qV V V

V F VF V V

F F F

La negación de &na proposición se 8orma intercalando la pala,ra @noB o anteponiendo &na8rase como @no es cierto -&eB. #l sm,olo ` /tilde7 se emplea para indicar la negación de &na proposición.

La ta,la de )erdad para la negación es;

p ~ p

V F

F V

?na proposición -&e siempre es )erdadera reci,e el nom,re de ta&tologa.

?na proposición -&e siempre es 8alsa se conoce como &na contradicción.

*+*+0 Conectivos

Condicional

#n matemáticas nos encontramos con e9presiones como @i a y , son n*meros paresentonces a , es &n n*mero par.

#n general+ si p y - son dos proposiciones+ podemos 8ormar &na n&e)a proposición de lasig&iente manera; @si p entonces -B+ -&e llamaremos proposición condicional y -&e será denotadamediante p -. Al sm,olo lo llamamos conecti)o condicionalK p es llamada antecedente o'ipótesis y - consec&ente o concl&sión.



28/57


La condicional es tam,i:n llamada implicación.

La ta,la de )erdad para la condicional es;

p q p → q

V V V

V F FF V V

F F V

Bicondicional

Consideremos las sig&ientes proposiciones;! ; 2 < ^ ; 0 <

!odemos 8ormar la sig&iente proposición; p - _ - p+ esto es;

i 2 < entonces 0 < y si 0 < entonces 2 <

#sta n&e)a proposición @p - _ - pB está 8ormada mediante dos implicaciones y &nacon&nción.

!odemos escri,ir esta proposición como p b - y se lee @p si y sólo si -B

#l sm,olo b es llamado el conecti)o ,icondicional o do,le implicación.

La ta,la de )erdad para la condicional es;

p q p → q

V V V

V F F

F V F

F F V

Cuantificadores

?n c&anti8icador es &n sm,olo -&e e9presa &na idea de cantidad. !ara reemplazar la 8rase@para todoB se &tiliza el sm,olo ∀. #sto es+ el sm,olo @∀B e9presará -&e la proposición de,e ser

)erdadera para todos los )alores de la )aria,le.

Al sm,olo @∀B le llamaremos c&anti8icador &ni)ersal.

#emplo;

∀ a+, ∈ enteros si a y , son pares entonces a , es par



29/57


!ara reemplazar la 8rase @e9iste al menos &n elementoB se &tiliza el sm,olo ∃. #sto es+ elsm,olo @∃B e9presará -&e la proposición de,e ser )erdadera por lo menos para &n )alor de 9 en eldominio.

Al sm,olo @∃B le llamaremos c&anti8icador e9istencial o partic&lar.

#emplo;

∃ 9 ∈ #9=!residentes de M:9ico 9 es originario de !&e,la

'autolo!1a

#s &na proposición -&e siempre es )erdadera

Contradicción

#s &na proposición -&e siempre es 8alsa

Contin!encia



30/57




31/57




32/57




33/57




34/57




35/57




36/57




37/57




38/57


*+,+0 elaciones

?na relación es &n con&nto de pares ordenados.#l con&nto de todos los )alores posi,les de 9 se conoce

como Dominio de la relación.#l con&nto de todos los )alores posi,les de y se conoce

como Codominio+ Imagen+ Contradominio o %ango de larelación.

#emplo; encontrar dominio+ imagen y el con&nto de paresordenados.

%


39/57


a7 %


40/57


La notación 8/97 /denominada notación de 8&nción7 es más con)eniente+ p&esto -&e pone demani8iesto @el )alor de la 8&nciónB para el )alor dado de 9.

8 / 9 7 < 29

8 / 1 7 < 2/17 < 2 <

8 / =3 7 < 2/=37 < =12 < =6

La de8inición de 8&nción no pone restricciones a los elementos del con&nto de llegada/Codominio7+ de tal 8orma -&e p&ede 'a,er elementos en el seg&ndo con&nto -&e no est:nrelacionados con elementos del primer con&nto y elementos del seg&ndo con&nto -&e lescorrespondan más de &n elemento en el primer con&nto+ eemplos;



41/57


Como &na 8&nción 8 de A en E es &na relación se p&ede representar as; 8 ; A E. si &na parea / a + , 7 pertenece a 8 se p&ede indicar como 8 / a 7 < ,+ -&e es la 8orma más

com*n para representar &na 8&nción.

Función In-ectiva

?na 8&nción + ; A E es inyecti)a si solo si se satis8ace la sig&iente propiedad;

i a , entonces + / a 7 + / , 7

?na 8&nción no es inyecti)a si &n elemento de s& imagen está relacionado con 2 elementosde s& dominio.



42/57


H&nción Inyecti)a



43/57


H&nción No Inyecti)a

#ercicios;

ean ;

A < U 9 + y + z V E < U 1 + 2 + + + V 8 < U / 9 + 1 7 + / y + 7 + / z + 7 V

ean ;A < U a + e + i + o + & V E < U 1 + 2 V 8 < U / a + 1 7 + / i + 1 7 + / & + 1 7 + / e + 2 7 V

ean ;A < U 0 + 1 + 2 + + + V E < U dgitos V

' ; A E de8inida como g < U / a + , 7 g / a 7 < , < a 1 V

ean ;A < U letras del al8a,eto V E < U 0 + 1 V

; A E de8inida como ' < U / a + , 7 , < 0 si a es )ocal y , < 1 si a es consonante V

Función So%re-ectiva

?na 8&nción + ; A E es so,reyecti)a si solo si se satis8ace la sig&iente propiedad;

!ara todo , E e9iste a A tal -&e 8 / a 7 < ,



44/57


H&nción o,reyecti)a



45/57


H&nción No o,reyecti)a

#ercicios;

ean ;A < U =2 + =1 + 0 + 1 + 2 V E < U = + = + =2 + =1 + 0 + 1 + 2 + + V

+ ; A E de8inida como 8 / 9 7 < 92

ean ;A < U =2 + =1 + 0 + 1 + 2 V E < U 0 + 1 + V

+ ; A E de8inida como 8 / 9 7 < 92

ean ;

A < U =2 + =1 + 0 + 1 + 2 V + ; A A de8inida como 8 / 9 7 < 0

ean ;A < U 2 + + + 4 V E < U 2 + V 8 < U / 2 + 2 7 + / 4 + 7 V



46/57


Función Bi-ectiva

?na 8&nción + ; A E es ,iyecti)a si solo si;a7 + es inyecti)a

,7 + es so,reyecti)a

H&nción Eiyecti)a



47/57


H&nción No Eiyecti)a#ercicios;

ean ;A < U 0 + 1 + 2 + + + V E < U 1 + 2 + + + + 3 V

' ; A E de8inida como g < U / a + , 7 g / a 7 < , < a 1 V

ean ;A < U 1 + 2 + V E < U 1 + 2 + + + + 3 + 4 + 5 + 6 V

+ ; A E de8inida como 8 < U / 9 + y 7 y < 29 V

ean ;A < U 2 + + 3 + 5 V E < U 2 + + 3 + 5 V

+ ; A E de8inida como 8 / 9 7 < 9

ean ;A < U 0 + 1 + 2 + V E < U dgitos V

+ ; A E de8inida como 8 / 9 7 < 92



48/57


ean ;A < U 0 + 1 + 2 + V E < U 0 + 1 + 5 + 24 V

+ ; A E de8inida como 8 / 9 7 < 9

ean ;A < U 0 + 1 + V E < U 0 + 1 + 2 + V

+ ; A E de8inida como 8 / 9 7 < f9

ean ;A < U =1 + 0 + 1 V E < U 0 + 1 V

+ ; A E de8inida como 8 / 9 7 < 92

ean ;A < U 1 + 2 + + V E < U a + e + i + o + & V

+ ; A E de8inida como 8 < U / 1 + a 7 + / 2 + e 7 + / + & 7 + / + o 7 V

,+,+,+ 'eor1a de 3rafos

Conceptos B&sicos

La Teora de Xra8os est&dia las propiedades de los gra8os+ &n gra8o está dise(ado por &naserie de p&ntos llamados ):rtices /nodos7 conectados por lneas llamadas aristas -&e p&eden tener orientación.

)értice.= !&ntos de &na grá8ica+ tam,i:n se llaman nodos

Arista.= Lnea -&e conecta ):rtices+ tam,i:n se llaman arcos.

3r&fica.= Diagrama -&e consiste de &n con&nto 8inito no )aco de o,etos llamados ):rtices y de &ncon&nto de lneas llamadas aristas. Con 8rec&encia las grá8icas son &tilizadas para registrar in8ormación acerca relaciones o )nc&los entre o,etos.



49/57


3r&fica Diri!ida.= #s a-&ella grá8ica en la c&al las aristas están orientadas /tienen dirección7

4a5o.= #s &na arista -&e conecta a &n ):rtice con :l mismo

Camino o tra-ectoria.= #s el recorrido de &n ):rtice a otro

Circuito.= #s &n camino o Trayectoria -&e inicia y termina en el mismo ):rtice

3r&fica Conexa.= ?na grá8ica es cone9a si consiste de &na sola pieza.

6r%ol .= #s &na grá8ica cone9a -&e no contiene circ&itos

Su%!r&fica.= #s a-&ella grá8ica -&e incl&ye todos los ):rtices y sólo alg&nas aristas de la grá8icaoriginal

3r&fica No Diri!ida.= #s a-&ella grá8ica en la c&al las aristas no están orientadas /no tienendirección7

3r&fica Disconexa.= #s &na grá8ica -&e consiste de )arios pedazos llamados componentes

3r&fica Nula.= #s a-&ella grá8ica -&e solo consta de ):rtices+ es decir+ no tiene aristas

Xrá8ica Completa.= es a-&ella en la -&e c&al-&ier par de ):rtices está &nido por &na *nica arista

Puente.= #s &na arista -&e al eliminarla la grá8ica se )&el)e discone9a

Aristas 78ltiples.= #s c&ando más de &na arista conecta a los mismos dos ):rtices

3r&fica Ponderada o Pesada.= #s a-&ella grá8ica en la c&al las aristas están eti-&etadas conn*meros

Peso.= N*mero -&e se &,ica en &na arista+ representa &nidades de tiempo+ distancia+ etc.

,+,+* 6r%oles

edes 71nimas

#n m&c'as sit&aciones prácticas como en la instalación de redes el:ctricas o de tele8ona+ enla constr&cción de redes de transporte+ as como en el dise(o de circ&itos el:ctricos+ se re-&iereconectar p&ntos -&e representan locaciones geográ8icas /centrales tele8ónicas+ ci&dades+ etc.7 de tal

manera -&e se p&eda ir desde c&al-&ier p&nto a c&al-&ier otro. C&ando esto se logra+ tenemos &nared en la -&e las cone9iones son lneas tele8ónicas+ carreteras+ lneas 8:rreas+ d&ctos+ etc. Además dela posi,ilidad de conseg&ir &na red -&e interconecte a &n con&nto de p&ntos se re-&iere -&e esto se'aga de manera óptima donde &s&almente óptima+ signi8ica m-s arata o m-s corta. A los pro,lemas -&e se re8ieren a la posi,ilidad de encontrar redes c&yo costo total sea el menor posi,lese les conoce como pro,lemas de redes m%nimas.



50/57


#n t:rminos de grá8icas+ la constr&cción de &na red re-&iere la eliminación de alg&nasaristas+ pero por s&p&esto -&e no de todas. #n este sentido+ la red tiene -&e ser &na sub#r!fica de lagrá8ica original y esta sub#r!fica tiene -&e llegar a todos los ):rtices de la grá8ica original.

6r%oles?n ár,ol es &na grá8ica cone9a -&e no contiene circ&itos.

Caracterizaciones de ár,oles

1.= #n &n ár,ol c&ales-&iera dos ):rtices están &nidos por &na *nica trayectoria.2.= #n &n ár,ol todas las aristas son p&entes.= Todo ár,ol con n ):rtices tiene e9actamente n . 1 aristas

6r%oles 3eneradores

?n ár,ol generador de &na grá8ica cone9a X con n ):rtices es &na s&,grá8ica de X -&e tienen . 1 de las aristas de X y todos los n ):rtices de X

6r%oles 3eneradores 71nimos

?n ár,ol generador mnimo de &na grá8ica ponderada es a-&el -&e tiene el menor pesototal.

Al!oritmo de 9rus$al

#n 163 el matemático norteamericano Wosep' r&sFal desc&,rió &n algoritmo m&y simplec&ya aplicación garantiza encontrar &n ár,ol generador mnimo en c&al-&ier grá8ica ponderada.

%egla 1 #lige la arista de menor peso /en caso de empate elige &na ar,itrariamente7

%egla 2 #lige la sig&iente arista disponi,le de menor peso. i 'ay más de &na+ elige &naar,itrariamente.

%egla #lige la sig&iente arista de menor peso -&e no cierra &n circ&ito con las aristas yaelegidas. i 'ay más de &na+ elige &na ar,itrariamente.

%egla !ara &na grá8ica de n ):rtices+ repite la regla 'asta -&e se 'ayan elegido n 1

aristas de la grá8ica. Los ):rtices de la grá8ica y las n 1 aristas as elegidasconstit&yen el ár,ol generador mnimo.

4a uta m&s Corta



51/57


#l pro,lema de la r&ta más corta consiste en determinar &na trayectoria de menor pesototal -&e &ne a c&ales-&iera dos ):rtices de &na grá8ica ponderada cone9a.i recordamos -&e los pesos de las aristas p&eden representar distintas )aria,les /distancia+ tiempo+costo+ etc.7 y -&e los ):rtices p&eden representar distintos o,etos /ci&dades+ intersecciones decalles+ etc.7+ el pro,lema de la r&ta más corta estará in)ol&crado en c&al-&ier pro,lema práctico dela )ida real en el -&e el o,eti)o sea encontrar la manera más e8iciente de interconectar a

c&ales-&iera de estos o,etos.#l algoritmo de Distra permite encontrar la trayectoria más corta de &n ):rtice de &na

grá8ica 'acia cada &no de los otros ):rtices de la grá8ica.

%egla 1. Marca con &n crc&lo el ):rtice inicial. #9amina todas las aristas -&e llegan al):rtice inicial y elige la de menor peso. Marca la arista elegida con lnea p&nteada ymarca con &n crc&lo el ):rtice del otro e9tremo de la lnea p&nteada.

%egla 2. #9amina todos lo ):rtices -&e no 'an sido marcados con crc&lo y -&e sonadyacentes a los ):rtices marcados con crc&lo en la grá8ica.

%egla . ?sa *nicamente ):rtices marcados con crc&lo y aristas marcadas con lnea

p&nteada y enc&entra los pesos totales de todas las trayectorias -&e )an del ):rticeinicial 'acia cada &no de los ):rtices -&e e9aminaste. #lige el ):rtice y la arista -&e'ayan dado l&gar a la trayectoria de menor peso total. Marca con &n crc&lo el):rtice -&e elegiste y con lnea p&nteada la arista -&e elegiste.

%egla . %epite las reglas 2 y 'asta -&e 'ayas marcado todos los ):rtices con &n crc&lo.Las aristas p&nteadas de la grá8ica 8orman la r&ta más corta del ):rtice inicial 'aciac&al-&ier otro ):rtice de la grá8ica.

#l ár,ol generador -&e se o,tiene al aplicar el algoritmo de Distra especi8icando &n ):rticeinicial se s&ele llamar !rbol #enerador de rutas m!s cortas y sa,emos -&e en general este ár,olno es mnimo.



52/57


*+*+, 'a%las de )erdad

*+0+, 6l!e%ra Booleana

#l álge,ra Eooleana es &na 8orma de lógica sim,ólica -&e m&estra como operan loscirc&itos lógicos.



53/57


?na e9presión Eooleana es &n @m:todo ta-&igrá8icoB de mostrar lo -&e s&cede en &ncirc&ito lógico.

Las operaciones del álge,ra ,ooleana son complemento /Not7+ s&ma /r7 y prod&cto/And7 ,ooleano.

*+0+* Circuitos 4ó!icos

La comp&erta lógica es el elemento ,ásico en los sistemas digitales y operan con n*meros ,inarios+ por esta razón se llaman comp&ertas lógicas ,inarias.

Todos los )oltaes &sados en las comp&ertas lógicas serán; alto )oltae / 1 7 o ,ao )oltae/ 0 7.

Todos los sistemas digitales se constr&yen &sando solo comp&ertas lógicas ,ásicas; AND /y 7+ % / o 7 y NT / negación7.

Compuerta And

A la comp&erta And se le llama comp&erta de @todo o nadaB. La lámpara / y 7 se encenderásolo c&ando am,os interr&ptores de entrada / A y E 7 están cerrados.

CONMUTADORES DEENTRADA

LUZ DESALIDA

ENTRADAS SALIDA

A B A B Y

ABIERTO ABIERTO NO 0 0 0

ABIERTO CERRADO NO 0 1 0

CERRADO ABIERTO NO 1 0 0

CERRADO CERRADO SI 1 1 1



54/57


#l 0 ,inario se de8ine como &n ,ao )oltae o tierra. #l 1 ,inario se de8ine como &n alto)oltae / apro9. )olts 7.

La #9presión Eooleana para la 8&nción And es;

A E < / A y E ig&al a la salida 7A E <

Las Leyes del $lge,ra Eooleana go,iernan la operación de las comp&ertas AND. Las LeyesHormales para la 8&nción AND son;

A 0 < 0A 1 < AA A < AA h < 0

Las comp&ertas AND de,en seg&ir estas leyes.

Compuerta Or

A la comp&erta r se le llama comp&erta de @c&al-&iera o todoB. La lámpara / y 7 seencenderá c&ando c&al-&ier interr&ptor / A o E 7 est: cerrado. La lámpara tam,i:n se encenderác&ando los 2 interr&ptores / A y E 7 están cerrados.

CONMUTADORES DEENTRADA

LUZ DESALIDA

ENTRADAS SALIDA

A B A B Y

ABIERTO ABIERTO NO 0 0 0



55/57


ABIERTO CERRADO SI 0 1 1

CERRADO ABIERTO SI 1 0 1

CERRADO CERRADO SI 1 1 1

La #9presión Eooleana para la 8&nción r es;

A E < / A o E ig&al a la salida 7

Las Leyes del $lge,ra Eooleana go,iernan la operación de las comp&ertas %. Las LeyesHormales para la 8&nción % son;

A 0 < AA 1 < 1A A < AA h < 1

#stas proposiciones generales siempre son )erdaderas para la 8&nción %.

Compuerta Not

A la comp&erta NT tam,i:n se le conoce como In)ersor+ es &na comp&erta no &s&al. Tienesolamente &na entrada y &na salida.

ENTRADAS SALIDA

A B Y

0 0 0

0 1 1

1 0 1

1 1 1



56/57


#sta in)ersión tam,i:n se llama Negación o Complemento.

La #9presión Eooleana para la 8&nción Not es;

A < h /A es ig&al a la salida No A7

Las Leyes del $lge,ra Eooleana go,iernan las acciones del In)ersor o comp&erta Not. LasLeyes Hormales del $lge,ra Eooleana para la comp&erta Not son;

O O 0 < 1 1 < 0

i A < 1 entonces h < 0i A < 0 entonces h < 1

< A < A

*+0+0 Funciones Booleanas

e denomina función ló#ica o %ooleana a a-&ella 8&nción matemática c&yas )aria,les son ,inarias y están &nidas mediante los operadores del álge,ra de Eoole s&ma lógica /7+ prod&ctológico /7 o negación/7.

#emplos de H&nciones Eooleanas;

a7 H < j/A ECG7G AECkG AEGC ,7 H < AGECG AEGCG AEGC AECGc7 H < /A E C7/A E CG7/A EG CG7/AG EG CG7d7 H < ECG AEGe7 H < /A E7/EG CG787 H < j/ECG7G /AEG7GkGg7 H < j/A E7G /EG CG7GkG

#emplo;

#nc&entre el res&ltado de la sig&iente 8&nción ,oleana H < // A E 7G / AG E D 7G 7 C si;

A < 1 E < 0 C < 1 D < 1

< // 1 0 7G / 0G 0 0 7G 7 1



57/57


< / / 0 7G / 0 7G 7 1

< / 1 1 7 1

< 1 1

< 1

Bi%lio!raf1a

• H&ndamentos de matemáticasW&an Man&el il)aZAdriana Lazo#ditorial Lim&sa

• Matemáticas contemporáneasWacF %. ErittonZIgnacio Eello#ditorial Jarla

• Matemáticas Discretas#las Mic'a#ditorial Lim&sa

• #l álge,ra ,inaria de Eoole y s&s aplicaciones a la in8ormática%ao&l de !almaMarcom,o #ditores

• #stadstica y pro,a,ilidadEaltasar !:rez JernándezZWos: Al8redo W&árez D&arteZArt&ro le MartnezZWos: !ilar X&zmán Ta,oada#ditado por la ?ni)ersidad A&tónoma de inaloa

PPP.,&enastareas.comPPP.monogra8ias.com
http://www.buenastareas.com/http://www.monografias.com/http://www.monografias.com/http://www.buenastareas.com/

Documents

Matemáticas Discretas 2.11.12 B.docx