8/7/2019 edig_2

1/13

DIES

IA

TE

MAII.-L

GEBRADEB

OOLE

UNSISTEMADE

ELEMENTOSBYDOSOPERACION

ESBINARIASCE

RRA-

DAS

()

Y

(+)

SE

DENOMINA

A

LGEBRA

DE

BOOL

E

SIEMPRE

Y

CU

ANDO

SECUMPLANLA

SSIGUIENTESP

ROPIEDADES:

PROPIEDADCONMUTATIVA:

A+B=B+A

AB=BA

PROPIEDADDISTRIBUTIVA:

A+(BC)=(A+B)(A+C)

A(B+C)=AB+AC

ELEMENTOSNEUTROSDIFERENTES:

A+0=A

A1=A

SIEMPREEXISTEELCOMPLEMENTO

DEA,DENOMINADOAO

A

A+A=1

AA=0

8/7/2019 edig_2

2/13

DIESIA

PRINCIPIO DE DUALIDAD: CUALQUIER

TEOREMA O IDENTIDAD ALGEBRAICA DEDU-

CIBLE DE LOS POSTULADOS ANTERIORESPUEDE TRANSFORMARSE EN UN SEGUNDO

TEOREMA O IDENTIDAD VLIDA SUSTITU-

YENDO 1S POR 0S Y (+) POR ()

CONSTANTE: CUALQUIER ELEMENTO DEL

CONJUNTO B

VARIABLE: SMBOLO QUE REPRESENTA UN

ELEMENTO ARBITRARIO DEL LGEBRA, YA

SEA CONSTANTE O UNA FRMULA

TEOREMA 1: EL ELEMENTO COMPLEMENTO,

A, ES NICO

TEOREMA DE LOS ELEMENTOS NULOS: PARA

CADA ELEMENTO DE B, SE VERIFICA:

A + 1 = 1

A 0 = 0

TEOREMA 3: CADA ELEMENTO IDENTIDAD

ES EL COMPLEMENTO DEL OTRO

TEOREMA DE IDEMPOTENCIA: PARA CADA

ELEMETO DE B, SE VERIFICA:

A + A = A

A A = A

8/7/2019 edig_2

3/13

DIESIA

TEOREMA DE INVOLUCIN: PARA CADA

ELEMENTO DE B, SE VERIFICA:

(A) = A

TEOREMA DE ABSORCIN: PARA CADA

PAREJA DE ELEMENTOS DE B, SE VERI-

FICA:

A + A B = A

A (A + B) = A

TEOREMA 7: PARA CADA PAREJA DE ELE-

MENTOS DE B, SE VERIFICA:

A + A B = A + B

A (A + B) = A B

LEYES DE DEMORGAN: PARA CADA PAREJA

DE ELEMENTOS DE B, SE VERIFICA:(A + B) = A B

(A B) = A + B

LEYES DE DEMORGAN GENERALIZADAS:

PARA CADA CONJUNTO DE B, SE VERIFICA

(A+B+...+Q) = AB...Q

(AB...Q) = A+B+...+Q

TEOREMA DE ASOCIATIVIDAD: CADA UNO

DE LOS OPERADORES BINARIOS (+) Y ()

CUMPLEN LA PROPIEDAD ASOCIATIVA

A+(B+C) = (A+B)+C

A(BC) = (AB)C

8/7/2019 edig_2

4/13

DIESIA

LGEBRA DE CONMUTACIN: UN SISTEMA

DE ELEMENTOS B={0,1} Y LOS OPERADO-

RES DEFINIDOS DE LA SIGUIENTE FORMA

ES UN LGEBRA DE BOOLE

OPERADOR + --> OPERADOR OR

OPERADOR --> OPERADOR AND

OPERADOR --> OPERADOR NOT

FUNCIN COMPLETA: UNA FUNCIN QUE SEENCUENTRA DEFINIDA PARA TODAS LAS

COMBINACIONES DE LAS VARIABLES DE

ENTRADA

TABLA DE COMBINACIONES: FORMA DE

REPRESENTAR FUNCIONES

A B A+B AB A

0 0 0 0 1

0 1 1 0

1 0 1 0 0

1 1 1 1

X1 X0 F(X1,X0)

0 0 F(0,0)

0 1 F(0,1)

1 0 F(1,0)

1 1 F(1,1)

8/7/2019 edig_2

5/13

DIES

IA

FRMULASDECO

NMUTACIN:EXPRESINDEUNA

FUNCINDECO

NMU-

TACIN.

1Y0SONFRMULASDECONMUTAC

IN

XIESUNAFRMULASIPERTENECE

A{0,1}

SIAESUNAFRMULA,ATAMBI

NLOES

SIAYBSONFRMULAS,A+BYA

B

LOSON

NADA

MS

ES

UN

A

FRMULA

A

MENO

S

QUE

SIGAN

LOS

P

UNTOS

ANTERIORES

EN

UN

NMEROFINITO

DEPASOS.

TEOREMA11:CA

DAFRMULADESCRIBEUNANI

CAFUNCIN

DOS

FRMULAS,

A

Y

B,

SON

EQUIVALENTES

(A=

B)

SI

DESCRIBE

N

LA

MISMAFUNCIN

DECONMUTACI

N

TRMINOPRODUC

TO:OPERACINANDDEUNNM

ERODELITERAL

ES

FRMULANORMAL

DISYUNTIVA:SUMADETRMIN

OSPRODUCTOS

8/7/2019 edig_2

6/13

DIES

IA

TRMINOSUMA:

OPERACINORDEUNNMEROD

ELITERALES

FRMULANORMAL

CONJUNTIVA:PRODUCTODET

RMINOSSUMA

MINTRMINO(mi):TRMINOPRODUCTOENELQ

UEAPARECENTO

DAS

LASVARIABLES

,YASEANCOMP

LEMENTADASOS

INCOMPLEMENTAR

FRMULACANNI

CADISYUNTIVAODEMINTRMI

NOS:SUMADEM

IN-

TRMINOS

TEOREMA12:DA

DALALISTACOMPLETADEMIN

TRMINOSYASI

G-

NANDO

1S

Y

0

S

ARBITRARIAMENTE

A

LAS

VARI

ABLES,

SIEMPRE

HAY

UNYSLOUN

MINTRMINOQUE

TOMAELVALOR

1.

TEOREMA13:LA

FRMULACOMPUESTAPORTODO

SLOSMINTRMI

NOS

SERIDNTICA

MENTE1.

8/7/2019 edig_2

7/13

DIES

IA

TEOREMA14:CA

DAFUNCINPUEDEEXPREASRSE

COMOSUMADE

MIN-

TRMINOS

TEOREMA15:LA

FRMULADEMINTRMINOSES

NICA

PRIMERTEOREMA

DEEXPANSIN:SIEMPRESEV

ERIFICA:

F(X1,...,XN)=X1F(1,.

.

.,XN)+X1F

(0,...,XN)

TEOREMA17:CA

DAFUNCINCOMPLETAPUEDEE

XPRESARSECOMO

:

F(X1,...,XN)=

iF(i)mi(X1,

.

.

.,XN)

F(X,Y,Z)=

XYZ+XYZ+

XYZ=

m7

+m2+m0

MAXTRMINO(MI):TRMINOSUMAENELQUEA

PARECENTODAS

LAS

VARIABLES,YA

SEANCOMPLEME

NTADASOSINC

OMPLEMENTAR

FRMULACANNI

CACONJUNTIVAODEMAXTRMI

NOS:PRODUCTO

DE

MAXTRMINOS

8/7/2019 edig_2

8/13

DIES

IA

TEOREMA18:DA

DALALISTACOMPLETADEMAX

TRMINOSYASI

G-

NANDO

0S

Y

1

S

ARBITRARIAMENTE

A

LAS

VARI

ABLES,

SIEMPRE

HAY

UNYSLOUN

MAXTRMINOQUE

TOMAELVALOR

0.

TEOREMA19:LA

FRMULACOMPUESTAPORTODO

SLOSMAXTRMI

NOS

SERIDNTICA

MENTE0.

TEOREMA20:CA

DAFUNCINPUEDEEXPRESARSE

COMOPRODUCTO

DE

MAXTRMINOS

TEOREMA21:LA

FRMULADEMAXTRMINOSES

NICA

SEGUNDOTEOREM

ADEEXPANSIN:SIEMPRESE

VERFICA:

F(X1,...,XN)=[

X1+F(0,...,XN)

][X1+F(1,...

,XN)]

TEOREMA23:CA

DAFUNCINCOMPLETAPUEDEE

SCRIBIRSECOMO

:

F(X1,...,XN)=

i

[F(i)+M(X1,...

,XN)]

F(X,Y,Z)

=(X+Y+Z)

(X+Y+Z)(X+Y+

Z)=M7M2

M0

8/7/2019 edig_2

9/13

DIES

IA

TEOREMA24:EL

COMPLEMENTODEUNAFRMULA

DEMINTRMINO

S

ESTFORMADO

PORLASUMADE

LOSMINTRMIN

OSQUENOAPARECEN

TEOREMA25:EL

COMPLEMENTODEUNAFRMULA

DEMXTERMINO

S

ESTFORMADO

PORELPRODUCT

ODELOSMAXT

RMINOSQUENOAPA-

RECEN

TEOREMA26:

mi=MiYMi=

mi

LA

TRANSFORMAC

IN

DE

UNA

FRMULA

DE

MINT

RMINOS

(EN

GEN

ERAL

DISYUNTIVA)

EN

OTRA

DE

MAXT

RMINOS

(EN

GEN

ERAL

CONJUNTVA

)

SE

BASAENLADO

BLECOMPLEMENT

ACIN,(F)=

F

CRITERIOSDEM

INIMALIDAD:

MENORNMERODEVARIABLES

MENORNMERODETRMINOS

MENORVALORASOCIADO:

NTRMINOS+

NVARIABLES-NTRMINOSCONU

NSOLOLITERAL-1

8/7/2019 edig_2

10/13

DIES

IA

FUNCIONES

INCO

MPLETAS:

FUNCI

ONES

QUE

NO

ES

TN

DEFINIDAS

PARA

TODASLASCOM

BINACIONESDE

LASVARIABLES

DEENTRADA

FUNCINCOMPLETACONTODASLAS

INESPECIFICACIONESA0

FUNCININESPECIFICACIN

COMPLEMENTODE

UNAFUNCININCOMPLETA:OT

RAFUNCININC

OM-

PLETACONLA

MISMAFUNCIN

INESPECIFIFCAC

INYELCOMPLE-

MENTODELAF

UNCINCOMPLET

A

LASFRMULASD

EMINTRMINOSYMAXTRMINOS

DELASFUNCIO

NES

INCOMPLETASN

OSONNICAS

8/7/2019 edig_2

11/13

DIESIA

ARITMTICA BINARIA

SUMA BINARIA:

11111 100 22.375

+11011.110 --> +27.750

110010.001 --> 50.125

RESTA BINARIA:

10100.11 ---> 20.75

10110.00 -11.25

01001.10 9.50

A B SUMA ACARREO

0 0 0 0

0 1 1 0

1 0 1 0

1 1 0 1

A B RESTA DESBORDAMIENTO

0 0 0 0

0 1 1 1

1 0 1 0

1 1 0 0

8/7/2019 edig_2

12/13

DIESIA

COMPLEMENTO A DOS: NMERO BINARIO NEGA-

TIVO

INVERSIN DEL NMERO Y SUMAR 12(1011) --> 0100+1 = 0101

DESDE LA DERECHA, BUSCAR EL PRIMER 1, YA PARTIR DEL SIGUIENTE INVERTIR ELRESTO DE BITS.

2(1011) --> 0101

OPERACIONES DE DESPLAZAMIENTO

DESPLAZAMIENTO DE N DGITOS A LA

IZQUIERDA (AADIENDO CEROS EN CASONECESARIO) ES IGUAL QUE MULTIPLICAR

POR 2N

DESPLAZAMIENTO DE N DGITOS A LA DERE-CHA (AADIENDO CEROS EN CASO NECESA-

RIO) ES IGUAL QUE MULTIPLICAR POR 2-N

O DIVIDIR POR 2N

MULTIPLICACIN BINARIA:

SE MULTIPLICA DGITO A DGITO Y SE REALI-

ZAN LAS SUMAS SUCESIVAS:

101.11

101

101 11

0000 00

+10111 00

11100.11

A B AB

0 0 0

0 1 0

1 0 0

1 1 1

8/7/2019 edig_2

13/13

DIES

IA

DIVISINBINARIA:MEDIANTEALG

ORITMO

ALINEAR

ELDIVISORCON

LAPARTEMSIZQUIERDA

DELDIVIDENDO(QUESEA

MAYORQUEELDIVISOR)

ALCOCIENT

ESELE

AADEUN1.

BAJAELSIGUIENTE

DGITODELDI

VIDENDO

ALRESULTAD

ODELA

RESTA

ALCOCIENTESELE

AADEUN0.

BAJAELSIGUIENTE

D

GITODELDIVIDENDO

ALRESULTADODELA

RESTAANTERIOR

RESTA