cátedra: fundamentos de tic’s · trabajo prÁctico nº 3 ... 4) dada la expresión a . b. ......

Giulianelli, Juan Ignacio Giulianelli, Daniel A

Doctorado en Ciencias Economías Universidad Nacional de la Matanza

Departamento:

Ingeniería e Investigaciones Tecnológicas Cátedra:

Fundamentos de TIC’s (Tecnologías de la Información y la Comunicación)

e-mail: [email protected]

JEFE DE CÁTEDRA: Mg. Daniel A. Giulianelli

TRABAJO PRACTICO NRO. 3 INTRODUCCIÓN A LAS ESTRUCTURAS

LÓGICAS

COLABORACIÓN: DOCENTES DE LA CÁTEDRA

CICLO LECTIVO:

2012

Universidad Nacional de la

Matanza

Universidad Nacional de La Matanza. Departamento: Ingeniería e Investigaciones Tecnológicas

Cátedra: Fundamentos de TIC’s

Trabajo Practico Nro 3 – 2012 2/56

TRABAJO PRÁCTICO Nº 3

PARTE A - CIRCUITOS LOGICOS

1) Dados los siguientes ejemplos, identifique la correspondiente combinación de la tabla de verdad de

la función lógica “Implicación” válida:

a) Hipótesis:

i) Todos los triángulos son poliedros.

ii) Todos los poliedros son figuras planas.

Tesis: Todos los triángulos son figuras planas.

b) Hipótesis:

i) Todos los triángulos son poliedros.

ii) Todos los poliedros son números primos.

Tesis: Todos los triángulos son números primos.

c) Hipótesis:

i) Todos los triángulos son polígonos.

ii) Todos los polígonos son figuras planas.

Tesis: Todos los triángulos son figuras planas.

d) Hipótesis:

i) El Sol es un astro.

ii) Todos los planetas son astros.

Tesis: El Sol es un planeta.

Sugerimos construir los diagramas de conjuntos para analizar las respuestas.

Hipótesis

Tesis

Hipótesis Tesis Corresponde al

caso:

F F V

F V V

V F F

V V V

2) Demostrar las siguientes propiedades a partir de los postulados de Huntington:

3) Indicar cuáles son las expresiones duales del punto anterior.

4) Dada la expresión a . b . 0 = 0, seleccione la demostración que emplea los postulados de

Huntington:

a) Como b . b = 0, luego a .0 = a . (b . b ), y reagrupando los paréntesis (a . b) . b ; y como

a . b = a, se cumple a . a = 0




b) Como b . b = 0, entonces: a .0 = a . (b . b ), reagrupando (a . b). b ; y como a .b = b; se

cumple b . b = 0.

c) Como a . a = 0 y a + 0 = a , entonces 0 = a . ( a + 0) aplicando distributiva

(a . a ) + (a . 0) por lo tanto se cumple que: 0 + a . 0 = 0 y a . 0 = 0

d) Como a + 0 = a y a . 1 = a, entonces: a . 1 + 0 = a, aplicando distributiva

(a + 0) . (1 + 0) = a, como “a” solo toma los valores 0 o 1, entonces: a + a = a.

e) a . b . 0 = 0, es el postulado del elemento neutro del producto, no requiere demostración.

5) El resultado de simplificar la siguiente expresión aplicando los postulados de Huntington,

da como resultado:

a) f = c . b + a

b) f = a + b + c

c) f = c + a . b

d) f = c + a

e) f = b + a . c

6) Escribir la expresión booleana correspondiente a la función dada en la siguiente tabla de verdad en

sus dos formas canónicas (minitérminos y maxitérminos)

7) Simplificar la siguiente expresión:

f ( d, c, b, a) = b . a . c . d + d . c . b . a + d . c . b + d . c . b . a + b . a . c + d . a . c . b

Utilizando los siguientes métodos:

c b a f

0 0 0 1

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 1

1 1 1 0

MINITÉRMINOS MAXITÉRMINOS




Aplicando los postulados de Huntington

Aplicando el método de Karnaugh

Aplicando el método numérico de Quine McKlusky

Expresarlo en Minitérminos y Maxitérminos

a) f = b . a + d . c. b + d . c . b; 4(3,4,5,7,10,15); 4 (1,2,3,6,7,9,13,14,15)

b) f = b . a + d . c . b + d. c . b; 4 (1,2,3,6,7,9,13,14,15); 4 (1,2,3,4,10,11,15)

c) f = b . a + d . c . b + d. c . b; 4 (3,4,5,7,10,11,15); 4 (1,2,3,6,7,9,13,14,15)

d) f = b . a + d . c . b + d. c . b; 4 (3,5,7,10,11,15); 4 (1,2,3,6,13,14,15)

e) Ninguna de las anteriores

8) Dada la siguiente función f(d,c,b,a), plantear su tabla de verdad y expresarla en las dos formas

canónicas.

a) 4(1,2,3,4,5,6,7,9,11,12,13,14,15)

b) 4(0,2,3,4,5,9,12,13,14,15)

c) 4(1,2,3,4,5,6,7,9,11,13,15)

d) 4(5,6,7,10,13,14,15)

e) 4(1,2,3,5,8,9,11,14,15)

f) ninguna es correcta

a) 4 (0,1,2,3,12,15)

b) 4 (3,4,6,7,11,12,13,14,15)

c) 4 (3,7,10,12,15)

d) 4 (0,1,2,3,7,9,1012,15)

e) 4 (0,1,2,5,7,8,12,15)

f) ninguna es correcta

9) Dada la función f1 representada mediante la expresión canónica de suma de productos:

f1(d,c,b,a) = 4 (0,1,2,3,12,15)

a) Indicar cuál de las siguientes es la expresión canónica correcta de producto de sumas.

a) 4(1,2,3,6,7,9,11,14,15)

b) 4(1,2,4,5,6,7,8,9,10,11)

c) 4(1,2,3,6,7,9,11,13,15)

d) 4(0,2,3,6,8,9,11,14,15)

e) 4(1,2,3,5,8,9,11,14,15)

b) Obtener las dos expresiones canónicas algebraicas de esta función.




c) Indicar cuál de las siguientes alternativas (a,b,c,d,e) representar la tabla de verdad de la

función.

d c b a a) f b) f c) f d) f e) f

0 0 0 0 0 1 0 1 1

0 0 0 1 0 1 1 1 1

0 0 1 0 0 0 1 1 1

0 0 1 1 1 0 0 1 1

0 1 0 0 1 0 0 0 0

0 1 0 1 0 1 1 0 0

0 1 1 0 1 1 0 0 0

0 1 1 1 1 0 0 1 0

1 0 0 0 1 1 0 1 0

1 0 0 1 0 1 1 0 0

1 0 1 0 0 1 1 1 0

1 0 1 1 0 0 0 1 0

1 1 0 0 0 0 1 1 1

1 1 0 1 1 1 1 0 0

1 1 1 0 0 0 1 1 0

1 1 1 1 1 1 0 0 1

10) Sea la función f1(d,c,b,a) = 4 (2,3,5,7,10,11,15) = 4(1,2,3,6,7,9,11,14,15)

Aplicar el método de Karnaugh para obtener la expresión mínima, para las dos formas canónicas.

11) Sean dos variables booleanas, analizar las 16 funciones lógicas posibles como f (a , b) realizando

sus tablas de verdad




AB

0

A.B

_

A.B

A

_

A.B

B

A B

A+B

_ _

A.B

____

A B

_

B

_

A+B

_

A

__

A+B

___

A.B

1

00

01

10

11

12) La función f (c, b, a) = c + b . a fue simplificada con el método de Karnaugh.

Indique la tabla que le corresponde.

a) b) c)

0 1 3 2

4 5 7 6

b a c 0 0 0 1 1 1 1 0

0

1

1

1 1

1 1

0 1 3 2

4 5 7 6

b a c 0 0 0 1 1 1 1 0

0

1

1 1 1

1 1

1

1 1

d) e)

0 1 3 2

4 5 7 6

b a c 0 0 0 1 1 1 1 0

0

1

1 1

1 1 1

0 1 3 2

4 5 7 6

b a c 0 0 0 1 1 1 1 0

0

1

1

1

1

1

1 1 1

13) Dada la siguiente función expresada en su versión simplificada a través de la sumatoria

f (c, b, a) = 3 (0, 4, 6)

Hallar cual de las expresiones booleanas simplificadas a través de Karnaugh la representa a partir

de su segunda forma canónica (maxitérminos).

a) ( b + a) ( c + b) ( c + b + a )

b) ( a ) (c + b )

c) (b + a) ( c + a)

d) ( c + b) (c + b + a )


14) Expresar la siguiente función como minitérminos

no f (c, b, a) = 3 (1, 4, 7)

0 1 3 2

4 5 7 6

b a

c 0 0 0 1 1 1 1 0

0

1

1 1

1 1 1




a) ( c + b + a ) ( c + b + a) (c + b + a )

b) ( c + b + a ) (c + b + a ) (c + b + a)

c) ( c . b . a ) + (c . b . a ) + (c . b . a)

d) ( c . b . a ) + ( c . b . a) + (c . b . a )


15) Dada la siguiente expresión lógica

F = NOT (A AND B) OR (C AND (NOT A))

a) Indicar cuál de las siguientes alternativas (a,b,c,d,e) corresponde a su tabla de verdad.

Tomando los siguientes pesos para las variables: A = 4; B = 2; C = 1, es decir f(a,b,c)

a) F b) F c) F d) F e) F

1 1 0 1 1

1 0 0 1 1

1 1 1 1 1

1 1 1 1 1

0 0 1 1 0

0 0 1 1 1

0 0 1 0 0

0 0 1 0 1

b) Dibujar el circuito lógico.

16) Para la siguiente tabla de verdad:

a) Indicar cuál de las siguientes expresiones algebraicas la representa

A B F

0 0 0

0 1 1

1 0 1

1 1 0

b) Realizar el esquema lógico, empleando una compuerta AND u OR y una NOT (si fuere

necesaria)

17) Para entradas binarias de un bit “A” y “B” y las salidas suma “S”, y acarreo “C”, de acuerdo al

principio del semi-sumador aritmético (half adder):

a) A XOR NOT B

b) A AND NOT B

c) NOT A AND B

d) NOT ((NOT A AND NOT B) OR (A AND B))

e) (NOT A AND B) OR (A AND B)




a) Desarrolle la tabla de verdad

A

+ B

C S

b) Desarrolle el esquema lógico

c) Identifique cual de las siguientes expresiones corresponde a cada salida

a) C = A OR B Y S = A XOR B

b) C = A XOR B Y S = A AND B

c) C = A AND B Y S = A XOR B

d) C = NOT A OR B Y S = A OR B

e) C = A AND B Y S = NOT (A OR B)

18) Los “conjuntos” tienen sus equivalentes en el álgebra de Boole y el álgebra proposicional respectivamente a:

a) Señales y Compuertas b) Compuertas Lógicas y Relaciones

c) Elementos y Proposiciones d) Variables e Hipótesis

e) Proposiciones y Compuertas Lógicas

19) La “conjunción” tiene sus equivalentes en Conmutación (positiva) y Circuitos Lógicos,

respectivamente a:

a) Circuito Paralelo y OR b) Circuito Serie y AND

c) Negación y Complementos d) Inversor y NOT

e) Circuito Serie y NAND

20) Para el siguiente circuito lógico:

Indique el nombre con el que se conoce el siguiente circuito lógico. Realice su tabla de verdad y

escriba su expresión lógica.

A B C S

0 0

0 1

1 0

1 1




a) Indique el nombre con el que se lo reconoce

a) SEMISUMADOR

b) VERIFICADOR DE PARIDAD

c) MULTIPLEXOR

d) DECODIFICADOR

e) SUMADOR DE 4 BITS

b) Realice su tabla de verdad

c) Identifique cual de las siguientes expresiones lo representa

a.) F0=(NOT A) AND (NOT B) F1=(NOT A) AND B F2=A AND (NOT B) F3 =A OR B

b.) F0=(NOT A) AND (NOT B) F1=(NOT A) AND B F2=A AND (NOT B) F3 =A AND B

c.) F0= A AND (NOT B) F1=(NOT A) AND B F2=A AND (NOT B) F3 =A AND B

d.) F0=(NOT A) AND (NOT B) F1=(NOT A) AND B F2=A AND (NOT B) F3=NOT (A AND B)

e.) F0=(NOT A) AND (NOT B) F1=A XOR B F2=A AND (NOT B) F3 =A AND B

21) Sabiendo que A B es equivalente a ( b . a) + ( b . ā ); indicar cuál de las siguientes es la

expresión equivalente a BA , aplicando De Morgan:

a) ā . b + b . a b) ( b + a ) . (b + ā ) c) ā . b + a . b

d) ba.. + a . b e) a . b + ab.

22) ¿Qué función le corresponde al siguiente circuito?

a) F = ).).(( BABA

b) F = ).()( BABA

c) F = ( A + B) + ( B . A)

d) F = ( BA ) + (A.B)


23) Dada la siguiente tabla de verdad, indique las expresiones que equivalen a cada función.

A

B

F




24) Indique para el siguiente circuito lógico a cuál de las salidas le corresponde la expresión lógica:

F(A,B) = (A + B) . (A + B ) . ( A + B )

a) F3

b) F2

c) F1

d) F0


25) Para el siguiente circuito secuencial, indique la expresión lógica equivalente y la función que tiene

cada una de las variables (set o reset)

a.) m = b. (a+ c) + c. a; s = a ( c . b + c. b ) + a. ( c .b + c.

b) b.) m = b . (a + c) + c. a; s = (c b ) a

c.) m= c b a + c . b . a; s = (c b) a

d.) m= b. (a + c) + c. a ; s = (c b) a

e.) m= c .b . a + c. b. a ; s= (c b) a

c b a m s

0 0 0 0 1

0 0 1 1 0

0 1 0 0 0

0 1 1 0 1

1 0 0 1 0

1 0 1 1 1

1 1 0 0 1

1 1 1 1 0




a) St= B + A + S(t-1), “no A” corresponde al reset; “no B” al set.

b) St= B +A + S(t-1), “ A” corresponde al reset; “B” al set.

c) St= B + (A . S(t-1)), “no A” corresponde al reset; “no B” al set.

d) St= B .A . S(t-1), “ A” corresponde al reset; “B” al set.

e) Ninguna es correcta

26) Para el siguiente circuito, indique la expresión lógica que corresponde:

a) A * b) * B c)

* d) + B e)

*

27) Para el siguiente circuito secuencial, indique la expresión lógica correspondiente y la función que

cumple cada una de las entradas (set o reset)

a) Sf = iSA . ; A es el set, B es el reset

b) Sf = iSA. . ; A es el set, es el reset

c) Sf = A + Si + B ; B es el set ; A es el reset

d) Sf = ; es el reset,

A es el set

e) Sf = iSA. + ; B es el set, A es el reset

28) Indique cual es la función de la señal del reloj (clock) en un Flip Flop.

a) Poner en uno la salida del Flip Flop.

b) Cumple la función de la entrada “Reset”.

c) Modificar los valores de entrada del Flip Flop.

d) Mantener el ritmo de los cambios de las variables de entrada.

e) Habilitar el ingreso de las variables de entrada.

+

B A

Lógica positiva

B A A B A A B

B

B B

B

B




29) Diferencie un Flip flop sincrónico activado por niveles de uno activado por flancos.

a) El de niveles permite los cambios de estado solo durante las transiciones de la señal aplicada al

reloj, mientras el de flancos lo hará durante todo el tiempo en que la señal de reloj está en estado

activo.

b) El de flancos permite los cambios de estado durante todo el tiempo en que la señal de reloj está en

estado activo.

c) El de niveles permite los cambios de estado durante el tiempo en que la señal de reloj está en estado

inactivo, mientras el de flancos lo hará durante el activo.

d) El de niveles permite los cambios de estado durante todo el tiempo en que la señal de reloj está en

estado activo, mientras el de flancos lo hará solo durante las transiciones de la señal aplicada al reloj.

e) El de niveles permite los cambios de estado solo durante las transiciones de la señal aplicada al

reloj, mientras el de flancos lo hará durante todo el tiempo en que la señal de reloj está en estado

inactivo.

30) Defina qué significa que un Flip Flop sea activado por flancos descendentes.

a) Cuando la entrada “T” pasa de “1” a “0”.

b) Cuando cambia con los valores descendentes de un contador.

c) Cuando la entrada “Set” pasa de “0” a “1”.

d) Cuando la entrada “Reset” pasa de “0” a “1”.

e) Cuando responde a los cambios de “1” a “0” del clock.

31) Señale una característica fundamental de un Flip Flop tipo “T”.

a) La salida adopta el valor de la entrada “T” en el momento en que el clock lo habilita.

b) La salida invierte su valor cada vez que el clock lo habilita, si la entrada “T” está en “1”.

c) La entrada “T” resulta de unir mediante un inversor las entradas “Set” y “Reset”.

d) La entrada “T” resulta de unir mediante un inversor las entradas “J” y “K”.

e) Es igual a un Flip Flop “RS” pero sin estado prohibido.

32) Considerando el estado inicial de las salidas Q0 y Q1, determine el estado de las salidas del

siguiente circuito inmediatamente después del segundo pulso del clock en la entrada marcada como

“Pulsos”.

T

Ck

Q

QT

Ck

Q

Q T

Ck

Q

QT

Ck

Q

Q

“1” “1”

0 1

Q0=0 Q1=0

Pulsos




a) Q0=0 y Q1=1.

b) Q0=0 y Q1=0.

c) Q0=1 y Q1=1.

d) Q0=1 y Q1=0.

e) No se produce ningún cambio pues el valor de las entradas “T” no lo permiten.

33) Considerando el estado inicial de las salidas Q0=0, Q1=0 y Q2=0, analice el diagrama de tiempo

siguiente e indique el estado en el que se encuentran las salidas del sistema Q2, Q1 y Q0, en el momento

marcado.

a) Q2=1, Q1=1 y Q0=1.

b) Q2=0, Q1=0 y Q0=1.

c) Q2=0, Q1=1 y Q0=1.

d) Q2=1, Q1=1 y Q0=0.

e) Q2=1, Q1=0 y Q0=0.

34) Teniendo en cuenta que los valores de las variables de salida sean inicialmente nulos, determine el

valor de las variables de salida al aplicar 5 pulsos de clock y los datos en la entrada serie: 11001 (en

ese orden).

Observe que, se ingresan 5 bits mediante 5 pulsos de clock. Solo hay 4 Flip Flop, por lo tanto el

sistema perderá uno de los bits, el primero ingresado.

a) Q3=1, Q2=1, Q1=0 y Q0=0.

b) Q3=1, Q2=0, Q1=0 y Q0=1.

c) Q3=0, Q2=0, Q1=1 y Q0=0.

d) Q3=1, Q2=0, Q1=1 y Q0=1.

e) Q3=0, Q2=1, Q1=0 y Q0=0.

D

Ck

Q

Q D

Ck

Q

Q D

Ck

Q

Q

2 1 0

Ck

Q0Q1Q2

Datos de entrada

en serie

t

t

Ck0

D2

1 01

D

Ck

Q

Q D

Ck

Q

Q

3 2

Ck

Q2Q3

Datos de entrada

en serie

D

Ck

Q

Q D

Ck

Q

Q

1 0

Q0Q1




35) El siguiente esquema corresponde a un circuito que permite transmitir de modo “serie” (serializar),

un dato de 5 bit más un bit de paridad. Identifique el Flip Flop que corresponde a la salida serie de

transmisión.

a) Q1.

b) Q0.

c) Q2.

d) Q3.

e) Qp.

36) El siguiente esquema corresponde a un circuito que permite recibir en modo “serie” y convertir en

paralelo (paralelializar), un dato de 5 bit más un bit de paridad colocado a la izquierda del bit más

significativo. Identifique el Flip Flop que corresponde a la entrada serie del receptor.

a) Q0.

b) Q1.

c) Q2.

d) Q3.

e) Q5.

D

Ck

Q

Q

Qp

pD

Ck

Q

Q

Q4

4D

Ck

Q

Q

Q3

3D

Ck

Q

Q

Q2

2D

Ck

Q

Q

Q1

1D

Ck

Q

Q

Q0

0

“0”

Ck

D

Ck

Q

Q

Q5

5D

Ck

Q

Q

Q4

4D

Ck

Q

Q

Q3

3D

Ck

Q

Q

Q2

2D

Ck

Q

Q

Q1

1D

Ck

Q

Q

Q0

0

Ck

Entrada

serie




EJERCICIOS RESUELTOS- ENUNCIADOS


I) a + 1 = 1 II) a + a.b = a


39) A partir de los postulados de Huntington y los teoremas, simplificar la siguiente expresión

booleana:

f = (a + 1) . b . b + c . 0 . (a + a ) + ( a + a) . c . c

40) Mostrar que la función XOR puede realizarse a partir de las funciones AND, OR y NOT.

41) Establecer mediante una tabla la correspondencia entre el Álgebra Proposicional, los circuitos

digitales, el Álgebra de Conmutación y el Álgebra de Boole.

CIRCUITOS DIGITALES PROPOSICIONAL BOOLE CONMUTACION

Compuerta OR

Compuerta AND

Compuerta NOT

0

1

42) Sean dos variables booleanas, implementar las funciones lógicas:

I) a + b II) ba III) a . b

utilizando únicamente compuertas NAND (NOT AND) y/o compuertas NOR (NOT OR).

43) Dado el siguiente circuito:

Obtener la función de salida y desarrollar la Tabla de Verdad. Extraer conclusiones.

44) Dadas las siguientes expresiones lógicas confeccionar las tablas de verdad y los circuitos lógicos

correspondientes:




a) (NOT A) AND B

b) A OR (NOT B)

45) Para cada una de las siguientes tablas de verdad: Desarrollar el esquema lógico y construir su

expresión algebraica, empleando una compuerta AND u OR y una NOT (si fuere necesaria).

a)

b)

B A X

0 0 0

0 1 1

1 0 0

1 1 0

c)

46) Indique el circuito lógico y la expresión algebraica correspondiente a la siguiente tabla de

verdad. Impleméntelas mediante un circuito lógico con compuertas AND, OR e inversoras.

B A Z

0 0 1

0 1 1

1 0 1

1 1 0

B A Y

0 0 1

0 1 0

1 0 0

1 1 1

B A W

0 0 1

0 1 1

1 0 0

1 1 1




47) Confeccione la tabla de verdad de la siguiente expresión algebraica.

Impleméntela mediante un circuito lógico con compuertas AND, OR e inversoras.

¿Cómo se conoce esta expresión? ¿Cuál es su símbolo?

48) Implemente un circuito lógico que ponga en “1” su salida “X”, cuando las entradas “A” y “B” se

encuentren en distinto estado lógico. ¿Con qué nombre se conoce este circuito?

49) Implemente un circuito lógico que ponga en “1” su salida “Y”, cuando ambas entradas “A” y “B”

se encuentren en el mismo estado lógico. ¿Con qué nombre se conoce este circuito?

50) Resuelva las siguientes situaciones:

a) Complete la tabla de verdad e implemente un circuito lógico que ponga su salida “S1”, en el

mismo estado lógico que su entrada “A”, y su salida “S2” en el estado lógico inverso a su

entrada “A”.

b) Indique la expresión lógica de “S1” y “S2”, en función de “A”.

¿Con qué nombre se conoce este circuito?

51) Realice el circuito lógico de un sumador (full adder), para entradas binarias de

dos bits A y dos bits B , C (acarreo de entrada), S (suma) y C (acarreo de salida).

¿Cuántas veces se necesita repetir este circuito para sumar palabras de 8 bits, 16 bits, 32 bits?

52) Indique como se conocen los siguientes circuitos lógicos. Realice su tabla de verdad y escriba

su expresión lógica.

I) II)

A S1 S2

0

1




53) Explicar porque se dice que los circuitos secuenciales son los que proveen la capacidad de

memorizar información a un sistema digital. Ejemplificar

54) Dada la expresión a + a . b = a , seleccione la demostración que emplea los postulados de

Huntington

a) Como a .1 = a ; a . 1 + a. b = a . (1 + b), aplicamos la reciproca de la distributiva y como

b + 1 = 1 y a .1 = a , a = a + a .b

b) Como a . 1 = a luego a .1 + a . b será a . (1 + b) . Por otra parte: 1 = b + b .1 y aplicando

distributiva: 1 = (b + b ) . (b + 1); entonces: 1 = 1 . (b + 1) luego: a.(1 + b) = a.

c) Como a . 1 = a y 1 = b + 1, aplicando distributiva: a . (1 + b) = a + a. b

d) Aplicada la reciproca de la distributiva: a . (1 + b) y como: b + 1 = 1; a + a. b = a.

e) a + a . b = a, es el postulado de absorción y no requiere demostración.


f = a . c + a . b. c + a. b. c + a. c


a) Aplicando los postulados de Huntington

b) Aplicando el método de Karnaugh

c) Aplicando el método de Quine Mc.Cluskey



A

B S

57) Señale una característica fundamental de un Flip Flop tipo “D”.

a) La salida adopta el valor de la entrada “D” en el momento en que el ck lo habilita.

b) La salida invierte su valor cada vez que el ck lo habilita, si la entrada “D” está en “0”.

c) La entrada “D” resulta de unir directamente las entradas “Set” y “Reset”.

d) La entrada “D” resulta de unir directamente las entradas “J” y “K”.


58) Señale una característica fundamental de un Flip Flop tipo “JK”.

a) La entrada “K” resulta de unir mediante un inversor las entradas “Set” y “Reset”.

b) La salida adopta el valor de la entrada “J” en el momento en que el ck lo habilita.




c) La salida invierte su valor cada vez que el ck lo habilita, si las entradas “J” y “K” están

simultáneamente en “1”.

d) La entrada “J” resulta de unir mediante un inversor las entradas “D” y “T”.

e) Es igual a un Flip Flop “RS” pero con estado prohibido.

59) Considerando el estado inicial de las salidas Q0=1, Q1=1 y Q2=0, determine el estado de las salidas

del siguiente circuito inmediatamente después del segundo pulso del clock en la entrada marcada como

“Pulsos”.

a) Q0=1, Q1=1 y Q2=1.

b) Q0=1, Q1=0 y Q2=0.

c) Q0=0, Q1=1 y Q2=1.

d) Q0=1, Q1=1 y Q2=0.

e) Q0=1, Q1=0 y Q2=1.

60) Se desea transmitir una palabra de 5 bit, más un bit de paridad, en una línea de transmisión. Dibuje

y explique el circuito que emplearía y explique el proceso.



marcado. Los datos ingresados a D2 de a uno a la vez (entrada en serie) son 1,1,0 (en ese orden,

primero el 0, luego el 1, y después el siguiente 1)

a) Q2=1, Q1=1 y Q0=1.

b) Q2=0, Q1=0 y Q0=1.

c) Q2=0, Q1=1 y Q0=1.

d) Q2=1, Q1=1 y Q0=0.

e) Q2=1, Q1=0 y Q0=0.

T

Ck

Q

QT

Ck

Q

Q T

Ck

Q

QT

Ck

Q

Q T

Ck

Q

QT

Ck

Q

Q

“1” “1” “1”

0 1 2

Q0=1 Q1=1 Q2=0

Pulsos

D

Ck

Q

Q D

Ck

Q

Q D

Ck

Q

Q

2 1 0

Ck

Q0Q1Q2

Datos de entrada

en serie




RESOLUCION DE LOS EJERCICIOS 37 A 60


I) a + 1 = 1 II) a + a.b = a

I) a + 1 = 1

1 = a + a Postulado 6a

1 = a + a . 1 Postulado 5b

1 = (a + a ) . (a + 1) Postulado 4b

1 = 1 . ( a + 1) Postulado 6a

1 = (a + 1) Postulado 5b

II) a + a . b = a Ley de absorción

a + a . b = a. (1 + b) Postulado 4a

a + a . b = a. 1 Teorema demostrado en I)

a + a . b = a Postulado 5b


Para hallar la expresión dual cambiamos cero por uno y uno por cero; producto por suma y suma

por producto.

I) a + 1 = 1 expresión dual a . 0 = 0

II) a + a . b = a expresión dual a (a + b) = a

39) A partir de los postulados de Huntington y los teoremas, simplificar la siguiente expresión

Booleana:

f = (a + 1) . b . b + c . 0 . (a + a ) + ( a + a) . c . c

f = (a + 1). b. b + c. 0. (a + a ) + ( a + a). c. c

Teorema II

Unicidad

Teorema II

Postulado 6a

Teorema

Unicidad

Teorema Unicidad




f = 1 . b + 0 . 1 + a . c

f = b + 0 + a . c ; puesto que 0 + a . c = a . c

f = b + a. c ( Postulado 5a )

40) Mostrar que la función XOR puede realizarse a partir de las funciones AND, OR y NOT.

Lo demostramos a través a través de las tablas de verdad equivalentes.

B A A XOR B

0 0 0

0 1 1

1 0 1

1 1 0

Ahora vamos a verificar la tabla de verdad de la función equivalente a A B que es

f = A . B + A. B

A

B

A. B

A . B

A . B + B . A

0 0 0 0 0

0 1 1 0 1

1 0 0 1 1

1 1 0 0 0

Las tablas de verdad son iguales por lo tanto las funciones son equivalentes.

A

B

A + B

Postulado 5b Teorema II

Sabemos por definición

que la tabla de Verdad de

A B es esta.




41) Establecer mediante una tabla la correspondencia entre el Álgebra Proposicional, los circuitos

digitales, el Álgebra de Conmutación y el Álgebra de Boole.

CIRCUITOS DIGITALES PROPOSICIONAL BOOLE CONMUTACION

Compuerta OR Disyunción (V) Suma Lógica (+) Conexión en Paralelo

Compuerta AND Conjunción ( ) Producto Lógico (.) Conexión en Serie

Compuerta NOT Negación (no) Elemento opuesto Inversor

0 Falsedad (F) Elemento neutro de la

suma (0)

Circuito abierto

1 Certeza (V) Elemento neutro del

Producto (1)

Circuito cerrado

42) Sean dos variables booleanas, implementar las funciones lógicas:

I) a + b II) ba III) a . b

utilizando únicamente compuertas NAND (NOT AND) y/o compuertas NOR (NOT OR).

I) a + b ; partimos de una compuerta OR

Aplicamos doble negación ; (teorema de la doble negación a = a ):

a + b = ba

Aplicamos de Morgan:

a + b = ba.

Aplicamos teorema de la doble negación (variable b)

Se obtuvo una expresión equivalente expresada con una

compuerta NAND.

II) ba

Esta función ya está expresada por medio de una compuerta NOR

III) a . b partimos de una compuerta AND

Aplicamos el teorema de la noble negación

a . b = ba.

Aplicamos de Morgan:

a . b = ba Aplicamos teorema de la doble negación (variable a)

Se obtuvo una expresión equivalente expresada con una

compuerta NOR.

a + b = ba.

a . b = ba




43) Dado el siguiente circuito:

Obtener la función de salida y desarrollar la Tabla de Verdad. Extraer conclusiones.

Función de salida: F(A,B) = ((A XOR B) NOR (A AND B) AND (NOT B)

Tabla de verdad

A B A XOR B A AND B OR NOR NOT B F

0 0 0 0 0 1 1 1

0 1 1 0 1 0 0 0

1 0 1 0 1 0 1 0

1 1 0 1 1 0 0 0

Conclusiones:

Este circuito tiene salida verdadera solo cuando a y b son falsas.

Su tabla de verdad es igual a la de NOR.

44) Dadas las siguientes expresiones lógicas confeccionar las tablas de verdad y los circuitos lógicos

correspondientes:

a) (NOT A) AND B

A

B

_

A

_

A . B

0 0 1 0

0 1 1 1

1 0 0 0

1 1 0 0

A .B A

B




NOT (A AND B)

(NOT A) OR (NOT

B)

b) A OR (NOT B)

45) Para cada una de las siguientes tablas de verdad:

Desarrollar el esquema lógico y Construir su expresión algebraica, empleando una compuerta

AND u OR y una NOT (si fuere necesaria).

a)

Dada esta tabla podemos resolverlo por Karnaugh:

0 1

2 3

a b 0 1

0

1

1

1

1

b)

B A X

0 0 0

0 1 1

1 0 0

1 1 0

A

B

_

B

_

A + B

0 0 1 1

0 1 0 0

1 0 1 1

1 1 0 1

B A Z

0 0 1

0 1 1

1 0 1

1 1 0

A AND NOT B

A

B

A + B

BA. A

B

A + B A

B

Obtenemos: A + B

Por leyes de De Morgan es equivalente BA.

A

B

A. B




Dada esta tabla podemos resolverlo por Karnaugh:

0 1

2 3

a b 0 1

0

1

1

c)

Como A B = ( A . B) + ( A. B ) entonces:

BA = ) B A. ( + B) .A( Aplicando De Morgan:

BA = ( BA. ). ( BA. ) Aplicando De Morgan:

BA = ( A + B ). ( A + B ) Por teorema de la doble negación:

BA = (A + B ) . ( A + B) Utilizamos distributiva (Postulado 4):

BA = A. A + B . A + A. B + B . B Por postulado 6:

BA = 0 + B . A + A. B + 0

46) Indique el circuito lógico y la expresión algebraica correspondiente a la siguiente tabla de

verdad. Impleméntelas mediante un circuito lógico con compuertas AND, OR e inversoras.

B A Y

0 0 1

0 1 0

1 0 0

1 1 1

Esta tabla es justo la inversa del XOR por lo tanto es BA

Obtenemos: A . B

A

B

BA

BA = A. B + A . B ( A AND B) OR (NOT A AND NOT B)




Realizando el mapa de Karnaugh:

47) Confeccione la tabla de verdad de la siguiente expresión algebraica.

Impleméntela mediante un circuito lógico con compuertas AND, OR e inversoras.

¿Cómo se conoce esta expresión? ¿Cuál es su símbolo?

Podemos ver el ejercicio 36 c) que es la inversa de BA , entonces negamos la expresión

anterior BA y por teorema de la doble negación obtenemos: A B.

A

B

_

A

_

B

A.B

_ _

A.B

_ _

A.B + A.B

_________

_ _

A.B + A.B

0 0 1 1 0 1 1 0

0 1 1 0 0 0 0 1

1 0 0 1 0 0 0 1

1 1 0 0 1 0 1 0

Es el XOR llamado OR EXCLUSIVO

B A W

0 0 1

0 1 1

1 0 0

1 1 1

(NOT B) OR A

A

B

A + B

0 1

2 3

a b 0 1

0

1

1

1

1

B + A

A

B

A + B




48) Implemente un circuito lógico que ponga en “1” su salida “X”, cuando las entradas “A” y “B” se

encuentren en distinto estado lógico. ¿Con qué nombre se conoce este circuito?

Armamos la tabla:

Haciendo el mapa de Karnaugh obtenemos:

Circuito:

49) Implemente un circuito lógico que ponga en “1” su salida “Y”, cuando ambas entradas “A” y “B”

se encuentren en el mismo estado lógico. ¿Con qué nombre se conoce este circuito?

Realizamos la tabla:

Se conoce con el nombre de NOT XOR

B A F

0 0 0

0 1 1

1 0 1

1 1 0

B A NOT XOR

0 0 1

0 1 0

1 0 0

1 1 1

La función queda ( A . B) + ( A. B ).

( Coincide con la función XOR)

Tabla típica de XOR

0 1

2 3

a b 0 1

0

1

1

1

Podemos observar que coincide con la

tabla de A B.

A

B

A + B ó

_ _

A B o A . B + A . B




A

B

A + B

Haciendo el mapa de Karnaugh obtenemos:

También puede ser el siguiente circuito:

50) Resuelva las siguientes situaciones:

a) Complete la tabla de verdad e implemente un circuito lógico que ponga su salida “S1”, en el

mismo estado lógico que su entrada “A”, y su salida “S2” en el estado lógico inverso a su

entrada “A”.

b) Indique la expresión lógica de “S1” y “S2”, en función de “A”.

¿Con qué nombre se conoce este circuito ?

a) Completamos la tabla según el enunciado:

A S1 S2

0

1

A S1 S2

0 0 1

1 1 0

0 1

2 3

a b 0 1

0

1

1

1

La función queda ( A . B ) + ( A.B).

Coincide con la función BA

A

B

BA




Implementación del circuito

b) Expresión lógica: S1 simplemente es igual a A y S2 es el inverso de A.

El circuito se conoce como

51) Realice el circuito lógico de un sumador (full adder), para entradas binarias de

dos bits A y dos bits B , C (acarreo de entrada), S (suma) y C (acarreo de salida).

¿Cuántas veces se necesita repetir este circuito para sumar palabras de 8 bits, 16 bits, 32 bits ?

Se necesitan:

para 8 bits = 7 sumadores y 1 semisumador para el bit menos significativo.



para n bits = n-1 sumadores y 1 semisumador para el bit menos significativo.

Los sumadores (full adder) tienen tres entradas (bi, ai y Cyi-1) y dos salidas (Cyi y Si).

El semisumador (half adder) tiene dos entradas (b0 y a0) y dos salidas (Cy0 y S0).

Decodificador

A

S1

S2

S0 S1

Cy0

Cy1 Cy0

1 0

a1 b1 a0 b0




52) Indique como se conocen los siguientes circuitos lógicos. Realice su tabla de verdad y escriba

su expresión lógica.

I) II)

I) Escribimos la función según el circuito: f = (A B) (C D)

D C B A D C B A (D C) C (B A)

0 0 0 0 0 0 0

0 0 0 1 0 1 1

0 0 1 0 0 1 1

0 0 1 1 0 0 0

0 1 0 0 1 0 1

0 1 0 1 1 1 0

0 1 1 0 1 1 0

0 1 1 1 1 0 1

1 0 0 0 1 0 1

1 0 0 1 1 1 0

1 0 1 0 1 1 0

1 0 1 1 1 0 1

1 1 0 0 0 0 0

1 1 0 1 0 1 1

1 1 1 0 0 1 1

1 1 1 1 0 0 0

AMBOS SON GENERADORES DE BITS DE PARIDAD




Observando esta tabla vemos que la función agrega a cada combinación de D, C , B, A un bit

de paridad par en los unos.

II) Escribimos la función según el circuito f = ((A B) C) D

Aquí también comprobamos que la función agrega a cada combinación de D, C, B, A un bit de

paridad par en los unos.

53) Explicar porque se dice que los circuitos secuenciales son los que proveen la capacidad de

memorizar información a un sistema digital. Ejemplificar

En los circuitos secuenciales, la salida es una función de las variables de entrada y del valor del

estado anterior de la salida.

Veamos el siguiente ejemplo:

D C B A A B (A B) C ((A B) C) D

0 0 0 0 0 0 0

0 0 0 1 1 1 1

0 0 1 0 1 1 1

0 0 1 1 0 0 0

0 1 0 0 0 1 1

0 1 0 1 1 0 0

0 1 1 0 1 0 0

0 1 1 1 0 1 1

1 0 0 0 0 0 1

1 0 0 1 1 1 0

1 0 1 0 1 1 0

1 0 1 1 0 0 1

1 1 0 0 0 1 0

1 1 0 1 1 0 1

1 1 1 0 1 0 1

1 1 1 1 0 1 0

A

B St

St-1




La función St = B . A .S 1-t se calcula en base a las variables de entrada A y B, pero también a St-1

que es el estado anterior de St. Aquí radica el concepto de memoria.

Si hacemos la tabla de verdad:

54) Dada la expresión a + a . b = a , seleccione la demostración que emplea los postulados de

Huntington

a) Como a .1 = a ; a . 1 + a. b = a . (1 + b), aplicamos la reciproca de la distributiva y como b +

1 = 1 y a .1 = a , a = a + a .b

b) Como a . 1 = a luego a .1 + a . b será a . (1 + b) . Por otra parte: 1 = b + b .1 y aplicando

distributiva: 1 = (b + b ) . (b + 1); entonces: 1 = 1 . (b + 1) luego: a.(1 + b) = a.

c) Como a . 1 = a y 1 = b + 1, aplicando distributiva: a . (1 + b) = a + a. b

d) Aplicada la reciproca de la distributiva: a . (1 + b) y como: b + 1 = 1; a + a. b = a.

e) a + a . b = a, es el postulado de absorción y no requiere demostración.

Comenzamos por analizar opción por opción y paso por paso para ver si se aplicaron Postulados

o Teoremas. En cuanto se aplica un teorema esa opción NO es la correcta.

Nota: la numeración de los Postulados es la citada en el libro Introducción a los Sistemas

Digitales 2° edición (Ing. Fernando I. Sklanny)

a) Como

a . 1 = a Postulado 5b

a .1 + a. b = a . (1 + b) Postulado 4a (reciproco)

b + 1= 1 Esto es un teorema NO un postulado

NO ES LA CORRECTA

b) Como

a. 1 = a Postulado 5b

a .1 + a . b será a .(1 + b) Postulado 4a

1 = b + b .1 Postulados 6a y 5b (aplicamos distributiva)

1 = (b + b ) . (b + 1) Postulado 4b

1 = 1 . (b + 1) Postulado 6a

a . (1 + b) = a Postulado 5b

ES LA OPCION CORRECTA PORQUE SÓLO USÓ POSTULADOS.

A B St-1 St

0 0 0 1

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 0

1 1 1 1

Observamos que:

B = 0 pone el circuito siempre en 1 => B = 0 es el SET.

A = 0 pone el circuito siempre en 0, por lo tanto A = 0 es el

RESET.

Los estados prohibidos son los dos primeros A = 0 y B = 0.

En las últimas dos filas, observamos como el estado actual St es

igual al estado anterior St-1, que es la forma de memorizar la

información.




c) Como

a . 1 = a Postulado 5b

1 = b + 1 Esto es un teorema NO un postulado

NO ES LA RESPUESTA CORRECTA

d) Como

a . (1 + b) Postulado 4b (aplicamos la reciproca de la distributiva)

b + 1= 1 Esto es un teorema NO un postulado


e) a + a . b = aEsto es un teorema NO un postulado



f = a . c + a . b. c + a. b. c + a. c



b) Aplicando el método de Karnaugh

c) Aplicando el método de Quine Mc.Cluskey


f = a . c + a . b. c + a. b. c + a. c

Aplicando conmutatividad:

f = a . c + a. c + a. b. c + a. b .c

Aplicamos la inversa de la distributiva:

f = ( a + a). c + ( c + c) . a. b

Por el postulado del elemento opuesto:

f = 1 . c + 1. a. b

Por el postulado del elemento neutro del producto obtenemos:

b) Por Karnaugh

f = a . c + a . b. c + a. b. c + a. c

La función está expresada como suma de productos, si bien estos no incluyen todas las

variables de la función. Para llevar la misma a su primer forma canónica basta agregar en cada

término las variables ausentes en el mismo, de forma que no se modifique la expresión original;

para ello usamos

a . 1 = a (elemento neutro del producto)

a + a = 1 (elemento opuesto de la suma)

f = a . c . ( b + b ) + a. b. c + a. b. c + a. c. ( b + b )

Por el postulado de distributividad

f = a . c .b + a . c. b + a. b. c + a. b. c + a. c. b + a. c. b

f = c + a . b




Los términos duplicados los eliminamos aplicando el teorema de unicidad

f = a . c .b + a . c. b + a. b. c + a. b. c + a. c. b

Aplicando conmutatividad

f = c .b. a + c. b . a . + c . b. a + c. b. a + c. b . a

Ordenando la función obtenemos como expresión de la misma:

f (c, b, a) = 3 (3, 4, 5, 6 , 7)

Representamos la función en un mapa de Karnaugh de tres variables:

0 1 3 2

4 5 7 6

b a c 0 0 0 1 1 1 1 0

0

1

1

1

1

1

1 1 1

Agrupamos los unos de manera de tener la menor cantidad de grupos posibles y cada uno

de ellos con la mayor cantidad (potencia de dos) de unos posibles. Así obtuvimos dos grupos,

uno formado por los minitérminos 3 y 7 y otro por los minitérminos 4, 5, 6 y 7.

En el primer grupo 3 y 7 (diferencia 4), desaparece la variable de ese peso, o sea la variable

c y queda: b. a ( tal como aparece en la tabla, sin negar, con valor 1).

En el segundo grupo (4, 5, 6 y 7) desaparecen las variables a y b (la variable a aparece la

misma cantidad de veces con valor cero que con valor 1, por lo tanto se simplifica. Lo mismo

ocurre con la variable b). La variable c aparece siempre con valor uno, por lo tanto queda

directa.

La función simplificada resulta:

c) Por Quine Mc. Cluskey

f (c, b, a) = 3 (3, 4, 5, 6, 7)

Armamos la tabla 1 formando grupos en orden creciente de acuerdo a la cantidad de unos que

posee cada término; por ejemplo: 3 (011) está en el grupo de los términos que poseen dos unos,

el 7 (111) está en el grupo de los que poseen tres unos, etc.

Tabla 1:

Cantidad de unos Término ¿ Utilizó?

1 4 X

2 3 X

5 X

6 X

3 7 X

Armamos la tabla 2 buscando entre grupos adyacentes pares de minitérminos en los cuales el

primer minitermino sea menor que el segundo y cuya diferencia sea una potencia entera de 2;

por ejemplo: el 4 del primer grupo con el 5 del segundo grupo, 5 – 4 = 1, diferencia; 1 = 20

f (c, b, a) = c + a. b




A cada término de la tabla 1 que se utilizó en la tabla 2, se la marca con una X (en este caso se

utilizaron todos).

Pares Difiere ¿ Utilizó?

4 - 5 1 X

4 - 6 2 X

3 - 7 4 No (A)

5 - 7 2 X

6 - 7 1 X

Armamos la tabla 3 analizando los sectores adyacentes de la tabla 2. Busco en la tabla 2 los

pares que tengan el mismo valor de diferencia, y además que la diferencia entre pares sea una

potencia entera de dos. Por ejemplo: el par 4 – 5 del primer sector y el par 6 – 7 del segundo

sector (difieren en 1)

6 7

-4 -5

2 2

Se marcan en la tabla 2 los que se utilizan en la tabla 3.

Los que no se utilizaron (A) son implicantes primos.

Pares de Pares Difiere

4 – 5 6 – 7 1 – 2 (B)

4 – 6 5 – 7 2 – 1 (C)

Analizando la tabla 3, vemos que no hay términos con diferencias iguales, entonces

terminamos el proceso de agrupación.

Los términos (B) y (C) no fueron incluidos en tablas posteriores, pero como contienen los

mismos minitérminos usamos cualesquiera de ellos; por ejemplo el (B).

Armamos ahora la tabla de implicantes primos:

Términos Primos 3 4 5 6 7

A 3 – 7 X X

B 4 – 5 – 6 – 7 X X X X

Los términos 4, 5 y 6 sólo se resuelve en la agrupación B (término esencial), porque en la

tabla tiene una sola cruz cada uno en B. Es decir B es el único que representa a los

minitérminos 4, 5 y 6.

B 4 – 5 6 – 7 4 – 6 5 – 7

1 1 2 2

Podemos observar que los pares de valores difieren en 1 (4-5) o en 2 (4-6), según el peso de nuestras variables (c b a); por lo tanto se van las variables a y b de pesos uno y dos

respectivamente. Queda la variable c.

Usamos el términos esencial A para dar solución al minitérmino 3 (tiene una sola cruz y

corresponde a A) y, en este ejemplo también al 7; el A: 3 – 7 (difiere en 4), se va la variable

c por tener peso 4, quedan a y b.




La función simplificada resulta:



A

B S

Comenzaremos escribiendo la ecuación según el circuito dado:

St = ( 1tSA ) + B

Ahora (si es necesario) la escribimos de forma de lograr que B resulte con un producto. Para

ello aplicamos De Morgan y queda:

St = ( 1tSA ) . B = ( A + S t-1 ). B

Ahora comenzamos a analizar esta expresión

Si B = 0 (es decir NO B) nos queda:

St = ( A + S t-1 ) . 0 resulta

St = ( A + S t-1 ) . 1

St = ( A + S t-1 ) No podemos sacar ninguna conclusión de esta expresión.

Ahora analizamos el otro valor de B, es decir B = 1

St = ( A + S t-1 ). 1 resulta

St = ( A + S t-1 ). 0 esto siempre da:

St = 0 Independientemente de los valores de A y S t-1

Por lo tanto B = 1 (es decir B) es el RESET, porque siempre hace St = 0

Una vez que encontramos el RESET, buscamos el SET, o viceversa de acuerdo al ejercicio.

En este caso, buscaremos el SET, para lo cual analizamos la tabla de acuerdo al circuito:

B A S t-1 St

0 0 0 0

0 0 1 1

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 X

1 1 1 X

Observamos que para A = 0, St toma valores 0 y 1. Pero para A =1, St siempre toma valor 1.

Por lo tanto A = 1 (es decir A) es el SET

En esta parte de la tabla investigamos cual es el SET (en este caso).

Debe ser un valor de A para el cual el circuito siempre vale 1 (St =1).

En esta parte de la tabla B = 1 por lo tanto St =0 como explicamos

arriba.

Estados imposibles (combinaciones no válidas)

f (c, b, a) = c + a . b




Los dos estados imposibles se dan cuando A y B están en SET y RESET al mismo tiempo, es

decir:

A = 1 y B = 1.

Entonces B = 0 y A = 0 son los estados donde St = S t-1 (Se mantiene el estado anterior)

La tabla reducida queda:

B A St

0 0 S t-1 ESTADO ANTERIOR

0 1 1 SET

1 0 0 RESET

1 1 X PROHIBIDO

Respuesta:

St = ( A + S t-1 ). B (o expresión equivalente). A es el SET y B es el RESET

57) Señale una característica fundamental de un Flip Flop tipo “D”

a) La salida adopta el valor de la entrada “D” en el momento en que el clock lo habilita. *

b) La salida invierte su valor cada vez que el ck lo habilita, si la entrada “D” está en “0”.

c) La entrada “D” resulta de unir directamente las entradas “Set” y “Reset”.

d) La entrada “D” resulta de unir directamente las entradas “J” y “K”.


58) Señale una característica fundamental de un Flip Flop tipo “JK”.

a) La entrada “K” resulta de unir mediante un inversor las entradas “Set” y “Reset”.

b) La salida adopta el valor de la entrada “J” en el momento en que el ck lo habilita.

c) La salida invierte su valor cada vez que el ck lo habilita, si las entradas “J” y “K” están

simultáneamente en “1”. *

d) La entrada “J” resulta de unir mediante un inversor las entradas “D” y “T”.

e) Es igual a un Flip Flop “RS” pero con estado prohibido.

59) Considerando el estado inicial de las salidas Q0=1, Q1=1 y Q2=0, determine el estado de las salidas

del siguiente circuito inmediatamente después del segundo pulso del clock en la entrada marcada como

“Pulsos”.

T

Ck

Q

QT

Ck

Q

Q T

Ck

Q

QT

Ck

Q

Q T

Ck

Q

QT

Ck

Q

Q

“1” “1” “1”

0 1 2

Q0=1 Q1=1 Q2=0

Pulsos




a) Q0=1, Q1=1 y Q2=1.

b) Q0=1, Q1=0 y Q2=0.

c) Q0=0, Q1=1 y Q2=1.

d) Q0=1, Q1=1 y Q2=0.

e) Q0=1, Q1=0 y Q2=1. *

Dado que cada uno de los tres Flip Flop tipo “T”, mantienen un uno lógico en sus entradas (T), cada

uno de dichos Flip Flop cambiará su estado de salida cuando reciba en su entrada de Ck un flanco

descendente.

Analizaremos en un diagrama de tiempos el estado de las salidas del circuito presentado: primero, en

el estado inicial, después del primer pulso de clock e inmediatamente antes del segundo.

Estado inicial

Inmediatamente después del primer pulso de clock descendente

El Flip Flop “0” cambia su estado de salida Q0 de 1 a 0

con el flanco descendente del pulso de entrada.


con el flanco descendente de la salida Q0.


con el flanco descendente de la salida Q1.

Primer pulso descendente Entrada T = 1 siempre

Estado Inicial

T = 1

Q0 = 1

Q1 = 1

Q2 = 0




Inmediatamente después del segundo pulso de clock descendente

Respuesta

e) Luego del segundo pulso de clock descendente Q0=1, Q1=0 y Q2=1.

60) Se desea transmitir una palabra de 5 bit, más un bit de paridad, en una línea de transmisión. Dibuje

y explique el circuito que emplearía y explique el proceso.

Circuito empleado FLIP FLOP D (registro de desplazamiento):

El dato a transmitir se coloca en el registro mediante las entradas de cada Flip Flop :

En este ejemplo la palabrea es 100111 donde el primer uno de la izquierda corresponde al bit de

paridad par en los unos.

Luego se aplican los pulsos de ck y cada bit se va desplazando hacia la derecha.

D

Ck

Q

Q

Qp

pD

Ck

Q

Q

Q4

4D

Ck

Q

Q

Q3

3D

Ck

Q

Q

Q2

2D

Ck

Q

Q

Q1

1D

Ck

Q

Q

Q0

0

“0”

Ck


con el flanco descendente del 2º pulso de entrada.

El Flip Flop “1” mantiene su estado de salida Q1 en 0

ya que el flanco de la salida Q0 es ascendente.

El Flip Flop “2” mantiene su estado de salida Q2 en 1

dado que la salida Q1 no cambió.

Segundo pulso descendente

Entrada T = 1 siempre

ENTRADA DE BITS EN PARALELO

1 0 0 1 1 1




La salida serie se obtiene en la salida del Flip Flop “0” (Q0), que va recibiendo los bits 100111

comenzando por el 1 de la derecha.



marcado. Los datos ingresados a D2 de a uno a la vez (entrada en serie) son 1,1,0 (en ese orden,

primero el 0, luego el 1, y después el siguiente 1)

Contamos con tres Flip Flop D acoplados, en los cuales cada pulso de habilitación del Ck, desplazará

los datos a la posición del Flip Flop siguiente.

Realizando un diagrama de tiempo veremos el estado de las salidas del circuito en el momento

indicado (inmediatamente después del tercer ciclo de Ck habilitante.).

Estado inicial

D

Ck

Q

Q

Qp

pD

Ck

Q

Q

Q4

4D

Ck

Q

Q

Q3

3D

Ck

Q

Q

Q2

2D

Ck

Q

Q

Q1

1D

Ck

Q

Q

Q0

0

“0”

Ck

D

Ck

Q

Q D

Ck

Q

Q D

Ck

Q

Q

2 1 0

Ck

Q0Q1Q2

Datos de entrada

en serie

Estado Inicial

D = 0

Q2 = D1 = 0

Q1 = D0 = 0

Q0 = 0

SALIDA SERIE 100111




Inmediatamente después del primer pulso de clock descendente

En el primer pulso habilitante, el dato de entrada (en nuestro caso el 0) se copia a la salida del flip flop

2, Q1 copia el valor que tenía Q2 (0) y Q0 el que tenía Q1 (también 0).

Inmediatamente después del segundo pulso de clock descendente

El dato de entrada (en nuestro caso el 0) se

copia a la salida del flip flop 2

Q1 copia el valor que tenía Q2 (0)

Q0 copia el valor el que tenía Q1 (también 0).

Primer pulso descendente habilitante

Dato de entrada D2 = 0

Con el segundo pulso ingresa el siguiente

dato (1), que se copia en Q2 (queda Q2=1)

Al mismo tiempo que el Q2 (0) se copia en

Q1 (quedando Q1= 0),

Simultáneamente Q1 se copia en Q0 (Q0=0).

Segundo pulso descendente habilitante

Dato de entrada D2 = 1




Inmediatamente después del tercer pulso de clock descendente

Luego del tercer pulso de Ck, quedan en las salidas Q2 =1, Q1 =1 y Q0 =0 (respuesta d). Se puede

observar que la información ingresada en serie ahora está en paralelo.

Con el tercer pulso ingresa el siguiente dato

(1), que se copia en Q2 (queda Q2=1)

Al mismo tiempo que el Q2 (1) se copia en

Q1 (quedando Q1= 1),

Simultáneamente Q1 = 0 se copia en Q0

(Q0=0).

Tercer pulso descendente habilitante

Tercer dato de entrada D2 = 1




TRABAJO PRACTICO Nº 3

PARTE B- INTELIGENCIA ARTIFICIAL

1) En la siguiente figura, se describe una porción del árbol que representa el problema de descarga

de líquidos en recipientes de 8, 5 y 3 litros (l.) de capacidad, respectivamente.

El estado inicial, es 8 litros en el primero y los demás vacíos (800). El objetivo es llegar a obtener 4

litros en alguno de los 2 primeros.

800

350 503

053 323 800 053 800 530

Indique la producción o regla necesaria para pasar del estado 800 al 350:

Si se cumple: Entonces:

a)

b)

c)

d)

e) f)

g)

2) Indique para la figura anterior, cuales son los truncamientos que deben realizarse para evitar

repeticiones en la búsqueda en amplitud, de arriba hacia abajo y de izquierda a derecha, luego

del segundo nivel.

3) Indique para la figura anterior, cuales son los truncamientos que deben realizarse para evitar repeticiones en la búsqueda en amplitud, de arriba hacia abajo y de derecha a izquierda, luego

del segundo nivel.

4) Relacione las siguientes afirmaciones con el nivel de análisis correspondiente en el proceso de

entender un lenguaje natural, dado el siguiente enunciado:

“El tiempo cambió de repente”

A (3 - C) > 0 ; A = A - (3 - C) y C = 3

(5 - B) A > 0 ; B = B + A y A = 0

(5 - B) C > 0 ; B = B + C y C = 0

B (3 - C) > 0 ; B = B - (3 - C) y C = 3

C (5 - B) > 0 ; C = C - (5 - B) y B = 5

(3 - C) B > 0 ; C = C + B y B = 0

A (5 - B) > 0 ; A = A - (5 - B) y B = 5




AFIRMACIÓN NIVEL

“El tiempo” es el sujeto de la oración.

Identifica la acción en cuestión: cambiar de

repente.

En un informe meteorológico significa que

cambió bruscamente el clima.

Identifica el papel gramatical de cada palabra

En un cuento de ciencia ficción se interpreta

como que se cambió de época

Identifica el papel semántico de cada palabra

5) Ubique la cruz en el lugar correcto:

Búsqueda Información

heurística

Reconocimiento de

imágenes

Reconocimiento

automático de voz

Información empírica no

comprobada, que las

personas obtienen

utilizando su intuición

Comparación de

patrones

Ayuda a controlar el

tamaño del árbol de

búsqueda

Extracción y evaluación

de rasgos de la imagen

procesada

Los sistemas apuntan a

ser independientes del

hablante

Evita el desarrollo de

ramas improductivas en

al árbol de búsqueda

Prever todas las

posibilidades que genera

cada movimiento

posible




6) Explique los 3 componentes de un sistema de producción (Colección de estados, colección de

producciones, sistemas de control). Ejemplifique cada uno para el caso del rompecabezas de 8.

7) Partiendo del siguiente estado inicial, desarrolle el árbol de búsqueda hasta el tercer nivel.

Calcule el costo probable de cada nodo, mediante la cantidad de movimientos para llegar a la meta.

Asigne una letra a cada estado, en orden alfabético, siguiendo el orden dado por la asignación en

amplitud de izquierda a derecha y de arriba abajo.

8) Indique la secuencia de estados con mayor probabilidad de éxito del ejercicio anterior empleando

el método heurístico que emplea la cantidad de movimientos para llegar a la meta como mecanismo

de costos.

9) ¿Qué forma tendría el árbol de búsqueda producido por el siguiente algoritmo si el costo

proyectado de todos los estados fuera el mismo?

- Establecer el nodo inicial del grafo de estados como raíz del árbol de búsqueda y registrar su

costo proyectado.

- MIENTRAS (no se haya llegado al nodo objetivo) HACER

[Seleccionar el nodo hoja más a la izquierda que tenga el menor costo proyectado de todos los

nodos hojas, y conectar como hijos al nodo seleccionado aquellos nodos a los que se pueda llegar

con una sola producción desde el nodo seleccionado.

Registrar el costo proyectado de cada uno de estos nuevos nodos junto al nodo en el árbol de

búsqueda].

- Recorrer hacia arriba el árbol búsqueda desde el nodo meta hasta el raíz, metiendo en una pila

la producción asociada a la producción asociada a cada arco recorrido.

- Resolver el problema original ejecutando las producciones conforme se desempilan.

10) ¿Qué forma tendría el árbol de búsqueda producido por el siguiente algoritmo si el costo

proyectado de todos los estados fuera el mismo?


costo proyectado.


[Seleccionar el nodo hoja más a la derecha que tenga el menor costo proyectado de todos los




búsqueda].



- Resolver el problema original ejecutando las producciones conforme se desempilan

3 4 2

5 6 1

7 8




11) En la siguiente figura se representa el problema de ordenar las piezas del rompecabezas de 8

piezas de acuerdo al esquema inicial que se indica para llegar a la solución conocida:

Se representa a continuación, una porción del árbol de búsqueda de la solución.

8 7 6

5 4 3 a)

2 1

Identificamos cada estado por medio de una letra.

Se emplea la cantidad de movimientos para llegar a la meta como mecanismo de costos en la

búsqueda heurística.

Utilizar el siguiente algoritmo para indicar la secuencia de estados con mayor probabilidad de

éxito:


costo proyectado.


[Seleccionar el nodo hoja más a la izquierda que tenga el menor costo proyectado de todos los




búsqueda].




8 7 6

5 4 3 b)

2 1

8 7 6

5 4 c)

2 1 3

8 7

5 4 6 f)

2 1 3

8 7 6

5 4 g)

2 1 3

8 7 6

5 4 3 e)

2 1

8 7 6

5 3 d)

2 4 1

8 7 6

5 3

2 4 1

h)

8 7 6

5 3

2 4 1

i)

8 6

5 7 3

2 4 1

j)

8 7

5 4 6

2 1 3

l)

8 6

5 7 4

2 1 3

n)

8 7 6

5 4

2 1 3

m)

8 7 6

5 1 4

2 3

o)

8 7 6

4 3

5 2 1

k)

1 2 3

4 5 6

7 8

8 7 6

5 4 3

2 1

:

nto

Departame

Ingeniería e Investigaciones Tecnológicas Cátedr




a) a, b, d, h

b) a, c, g, o

c) a, b, d, j

d) a, b, e, k

e) a, c, f, l




8 7 6

5 4 3 a)

2 1




Utilizar el siguiente algoritmo para indicar la secuencia de estados con mayor probabilidad de

éxito:


costo proyectado.

8 7 6

5 4 3 b)

2 1

8 7 6

5 4 c)

2 1 3

8 7

5 4 6 f)

2 1 3

8 7 6

5 4 g)

2 1 3

8 7 6

5 4 3 e)

2 1

8 7 6

5 3 d)

2 4 1

8 7 6

5 3

2 4 1

h)

8 7 6

5 3

2 4 1

i)

8 6

5 7 3

2 4 1

j)

8 7

5 4 6

2 1 3

l)

8 6

5 7 4

2 1 3

n)

8 7 6

5 4

2 1 3

m)

8 7 6

5 1 4

2 3

o)

8 7 6

4 3

5 2 1

k)

1 2 3

4 5 6

7 8

8 7 6

5 4 3

2 1





[Seleccionar el nodo hoja más a la derecha que tenga el menor costo proyectado de todos los




búsqueda].




a) a, b, d, h

b) a, c, g, o

c) a, b, d, j

d) a, b, e, k

e) a, c, f, l

13) Ajuste los pesos y el valor umbral de la unidad de proceso siguiente de modo que su salida sea 1

si y solo por lo menos si dos de sus entradas son 1.

14) ¿Cuál es la salida de la unidad de proceso siguiente cuando sus dos entradas son 1?

¿Qué sucede con los patrones de entrada 0,0 0,1 y 1,0 ?

EJERCICIOS RESUELTOS



El estado inicial, es 8 litros en el primero y los demás vacíos (800). El objetivo es llegar a obtener 4

litros en alguno de los 2 primeros.

800

350 503

053 323 800 053 800 530

1 0.5

-1




Indique la producción o regla necesaria para pasar del estado 350 al 323

Si se cumple : Entonces :

a) (3 – C)≥ A > 0 ; C = C + A y A = 0

b) (5 – B)≥ A > 0; B = B + A y A = 0

c) (5 – B)≥ C > 0 ; B = B + C y C = 0

d) B ≥(3 – C) > 0 ; B = B – (3 – C) y C = 3

e) A≥(5 – B) > 0 ; A = A – (5 – B) y B = 5

f) (8 – A)≥B > 0; A = A + B y B = 0

g) A≥(5 – B) > 0; A = A – (5 – B) y B = 5

En primer lugar nos fijamos cuales recipientes modificaron su contenido al pasar del estado 350 al

323, (recordemos que en cada producción sólo se puede intercambiar líquido entre dos recipientes).

El estado 350 significa que:

Y hay que pasar al estado 323 que significa

que:

Balde A contiene 3 lts. QUEDÓ IGUAL

Balde B contiene 5 lts. MODIFICÓ SU ESTADO

Balde C contiene 0 lts. MODIFICÓ SU ESTADO

Balde A contiene 3 lts.

Balde B contiene 2 lts.

Balde C contiene 3 lts.

Vemos que el recipiente A no modificó su contenido, el B pasó de contener 5 lts. a 2 lts. y el recipiente

C que no contenía líquido (0 lts.) quedó con 3 lts. luego de aplicarse la producción.

Por lo tanto los recipientes que modificaron su contenido al pasar del estado 350 al 323 son el B y el C,

lo que implica que la producción necesaria para que se produzca dicho cambio de estado debe

involucrar solo los recipientes B y C, con lo cual podemos descartar las opciones a), b), e), f), y g).

Analicemos ahora las restantes opciones c) y d).

En la regla de la opción c), si B tiene lugar para recibir todo lo que tiene C, se vuelca todo el líquido

del recipiente C en B, quedando C vacío y B con lo que tenía más lo de C. En otras palabras vacía C en

B.Esta no es la regla que se aplicó al pasar del 350 al 323, ya que no se vació C en B, sino se llenó C

con B.

En la regla de la opción d), si B contiene más de lo que le falta a C, y a este recipiente a su vez le falta

completar, entonces se puede llenar el recipiente C con líquido de B, quedando C con 3 lts. y B con lo

que tenía menos lo que se volcó en C. Se llenó C con líquido de B. Esta es la producción que se aplicó

al pasar del estado 350 al 323 o sea la respuesta correcta es la opción d).

16) Indique para la figura el ejercicio anterior, cuales son los truncamientos que deben realizarse para

evitar repeticiones en la búsqueda en amplitud, de arriba hacia abajo y de derecha a izquierda, luego

del segundo nivel.




Iniciamos la búsqueda desde la raíz del árbol es decir el estado inicial 800. Como la búsqueda es en

amplitud y de derecha a izquierda, vamos al estado 503,

800

350 503

053 323 800 053 800 530

seguimos por el 350, completando este nivel.

Como no llegamos al objetivo seguimos por el nivel siguiente, y de derecha a izquierda, 530 y luego

800. Como este último estado ya está representado anteriormente en el árbol de búsqueda, se trunca.

Luego, se sigue recorriendo el árbol de derecha a izquierda, pasando al estado 053, y nuevamente nos

encontramos con el estado 800 que no será conectado al árbol, se trunca, pues ya está presente con

anterioridad. Se sigue la búsqueda con el 323 y por último, en este nivel, el 053 que también será

truncado para evitar redundancias.

En definitiva, en el segundo nivel, se truncan los 800 de ambas ramas y el 053 de la rama más a la

izquierda.




1 2 3

4 5 6

7 8

1 7 5

3 4 8

2 6

VAMOS DE

DERECHA A

IZQUIERDA

VAMOS DE

DERECHA A

IZQUIERDA

800

350 503

053 323 800 053 800 530

NO ES

ESTADO

OBJETIVO

NO ES

ESTADO OBJETIVO

O

NO ES

ESTADO

OBJETIVO

TRUN

CAR

TRUN

CAR

TRUN

CAR




1 7 5

3 4 8 a)

2 6

1 7 5

3 4 8 b)

2 6




Utilizar el siguiente algoritmo para indicar la secuencia de estados con mayor probabilidad de éxito:


costo proyectado.


[Seleccionar el nodo hoja más a la izquierda que tenga el menor costo proyectado de todos los nodos

hojas, y conectar como hijos al nodo seleccionado aquellos nodos a los que se pueda llegar con una

sola producción desde el nodo seleccionado.


búsqueda].


la producción asociada a cada arco recorrido.

- Resolver el problema original ejecutando las producciones conforme se desempilan.

Opciones:

a) a, b, d, h

b) a, c, g, o

c) a, b, d, j

d) a, b, e, k

e) a, c, f, l

1 7 5

3 4 c)

2 6 8

1 7

3 4 5 f)

2 6 8

1 7 5

3 4 g)

2 6 8

1 7 5

3 4 8 e)

2 6

1 7 5

3 8 d)

2 4 6

1 7 5

3 8

2 4 6

h)

1 5

3 7 8

2 4 6

i)

1 7 5

3 8

2 4 6

j)

1 7

3 4 5

2 6 8

l)

1 5

3 7 4

2 6 8

n)

1 7 5

3 4

2 6 8

m)

1 7 5

3 6 4

2 8

o)

1 7 5

4 8

3 2 6

k)




Resolución:

- Calculamos el costo proyectado de cada estado (suma de la cantidad mínima de movimientos que se

debe hacer para ubicar cada ficha en su posición final, sin tener en cuenta la existencia del resto de las

fichas), por ejemplo para el estado inicial:

Anotamos el costo proyectado de cada nodo en el árbol de búsqueda:

(h) (i) (j) (k) (l) (m) (n) (o)

15 15 15 15 15 15 15 15

Se empieza a recorrer el árbol por el nodo inicial (a), cuyo costo proyectado es 16. Luego se conectan

los nodos hojas b) y c) ambos con un costo de 15, el algoritmo elije el nodo más a la izquierda que

tenga el menor costo proyectado, en este caso b), al cual se le conectan sus nodos hojas d) y e).

Nuevamente el algoritmo elige el nodo más a la izquierda de menor costo proyectado, en este caso el

e), al cual se conectan sus nodos hojas, el nodo k).

La secuencia de estados más prometedora según el algoritmo dado es: a,b,e,k o sea la respuesta d).

FICHA MOVIMIENTOS

1 0

2 3

3 3

4 1

5 2

6 2

7 3

8 2

TOTAL 16 MOVIMIENTOS

1 7 5

3 4 8

2 6

(f)

14

(a)

16

(b)

15

(e)

14

(d)

16

(c)

15

(g)

16

1 7

3 4 5

2 6 8

1 7 5

3 4 8

2 6

1 7 5

3 4 8

2 6

1 7 5

3 4 8

2 6

1 7 5

3 8

2 4 6

1 7 5

3 4

2 6 8

1 7 5

3 8

2 4 6

1 7 5

3 8

2 4 6

1 5

3 7 8

2 4 6

1 7 5

4 8

3 2 6

1 7

3 4 5

2 6 8

1 7 5

3 6 4

2 8

1 5

3 7 4

2 6 8

1 7 5

3 4

2 6 8

1 7 5

3 4

2 6 8




18) ¿Cuál es la salida de la unidad de proceso siguiente cuando sus dos entradas son iguales?

E1

E2

a) salida = 1.

b) salida = 0.

c) salida = -1.

d) salida igual a la suma de sus entradas.

e) salida = 0.5

Resolución:

Una unidad de proceso produce una salida de 1 ó 0 (las opciones c), d) y e) son imposibles),

dependiendo de si la entrada efectiva de la unidad (suma de los productos de cada una de sus entradas

por los pesos asignados a cada entrada) excede o no el valor del umbral.

Calculemos la entrada efectiva, para el caso en que las dos entradas sean 0:

Entrada1 x peso E1 + Entrada2 x peso E2 = 0 x 1 + 0 x -1= 0 => entrada efectiva igual a 0.

Calculemos la entrada efectiva, para el caso en que las dos entradas sean 1:

Entrada1 x peso E1 + Entrada2 x peso E2 = 1 x 1 + 1 x -1= 0 => entrada efectiva igual a 0.

Por lo tanto, vemos que cuando las dos entradas de la unidad de proceso son iguales la entrada efectiva

es igual a 0, como la misma no supera el umbral fijado de 0,5 la salida de esta unidad de proceso es 0.

Respuesta: b).

EJERCICIOS CON RESULTADOS - ENUNCIADOS



El estado inicial, es 8l. en el primero y los demás vacíos (800). El objetivo es llegar a obtener 4l. en

alguno de los 2 primeros.

800

350 503

053 323 800 053 800 530

1 umbral

0.5 -1






evitar repeticiones en la búsqueda en amplitud, de arriba hacia abajo y de izquierda a derecha, luego

del segundo nivel.




Si se cumple: Entonces:

a) (3 – C) ≥ A > 0 C = C + A y A = 0

b) (5 – B) ≥ A > 0 B = B + A y A = 0

c) (5 – B) ≥ C > 0 B = B + C y C = 0

d) B ≥ (3 – C) > 0 B = B - (3 – C) y C = 3

e) A ≥ (5 – B) > 0 A = A - (5 – B) y B = 5

f) (8 – A) ≥ B > 0 A = A + B y B = 0

g) C ≥ (5 – B) > 0 C = C - (5 – B) y B = 5

1 2 3

4 5 6

7 8

5 6 3

1 2 4

8 7

5 6 3

1 2 4

8 7

(f)

5 6 3 1 2 4 8

7 7

(a)

5 6 3 1 2 8 7 4

(b)

5 6 1 2 3 8 7 4

(e) 5 6 3 1 2

8 7 4

(d)

5 6 3 1 2 4 8 7

(c)

5 6 3

1 4

8 2 7

(g)

5 6 3

1 7 2

8 4

(h)

5 6 3

1 2

8 7 4

(j)

5 3

1 6 2

8 7 4

(i)

5 6

1 2 3

8 7 4

(k)

5 6 3

2 4

1 8 7

(l)

5 6 3

1 4

8 2 7

(m)

5 6 3

1 4

8 2 7

(o)

5 3

1 6 4

8 2 7

(n)

5 6 3

1 2 4

8 7

(f)

5 6 3 1 2 4 8

7 7

(a)

5 6 3 1 2 8 7 4

(b)

5 6 1 2 3 8 7 4

(e) 5 6 3 1 2

8 7 4

(d)

5 6 3 1 2 4 8 7

(c)

5 6 3

1 4

8 2 7

(g)

5 6 3

1 7 2

8 4

(h)

5 6 3

1 2

8 7 4

(j)

5 3

1 6 2

8 7 4

(i)

5 6

1 2 3

8 7 4

(k)

5 6 3

2 4

1 8 7

(l)

5 6 3

1 4

8 2 7

(m)







Indique la secuencia de estados con mayor probabilidad de éxito, empleando el método heurístico

mencionado de costos sobre la rama de la derecha (identificada con la letra c).

a) a,c,g,n..

b) a,c,e,l.

c) a,c,g,j.

d) a,c,f,l.

e) a,c,g,o.

Resultado de los ejercicios 19 a 21



El estado inicial, es 8l. en el primero y los demás vacíos (800). El objetivo es llegar a obtener 4l. en

alguno de los 2 primeros.

800

350 503

053 323 800 053 800 530


RESPUESTA: c)


evitar repeticiones en la búsqueda en amplitud, de arriba hacia abajo y de izquierda a derecha, luego

del segundo nivel.

RESPUESTA: Se trunca los 800 de ambas ramas y el 053 de la rama más a la derecha.



1 2 3

4 5 6

7 8

5 6 3

1 2 4

8 7








Indique la secuencia de estados con mayor probabilidad de éxito, empleando el método heurístico

mencionado de costos sobre la rama de la derecha (identificada con la letra c).

RESPUESTA: d) a,c,f,l

5 6 3

1 2 4

8 7

(f)

5 6 3

1 2

8 7 4

(b)

5 6

1 2 3

8 7 4

(e) 5 6 3

1 2

8 7 4

(d)

5 6 3

1 2 4

8 7

(c)

5 6 3

1 4

8 2 7

(g)

5 6 3

1 7 2

8 4

(h)

5 6 3

1 2

8 7 4

(j)

5 3

1 6 2

8 7 4

(i)

5 6

1 2 3

8 7 4

(k)

5 6 3

2 4

1 8 7

(l)

5 6 3

1 4

8 2 7

(o)

5 3

1 6 4

8 2 7

(n)

5 6 3

1 4

8 2 7

(m)

5 6 3

1 2 4

8

7

7

(a)

cátedra: fundamentos de tic’s · trabajo prÁctico nº 3 ... 4) dada la expresión a . b. ......

Documents