Algoritmi Iterativi con Cicli, Logica Booleana e Mappe di Karnaugh

(1)

Prima&esercitazione&

Riccardo(Ca*aneo(

Dipar/mento(di(Ele*ronica,(Informazione(e(Biomedica(( Politecnico(di(Milano&

Prima&esercitazione&

Riccardo(Ca*aneo(

(

Dipar/mento(di(Ele*ronica,(Informazione(e(Biomedica(

Politecnico(di(Milano&

1

Algoritmi Iterativi con Cicli, Logica Booleana e Mappe di Karnaugh

Alessandro A. Nacci

alessandro.nacci@polimi.it

(2)

2

Riccardo Cattaneo

-  Studente PhD al NECSTLab

-  Autonomic (Operating) Systems (CHANGE project)

-  Reconfigurable architectures for HPC systems (FASTER project)

- exaFPGA (accelerazione hardware)

Ciao!

2

(Scorsa esercitazione) Esercizio 5: trova il maggiore

Trovare il maggiore tra N numeri positivi inseriti da tastiera

Pseudocodice:

• Richiedere quanti numeri si vogliono inserire

• Acquisire il numero di numeri da inserire (= contatore)

• Finché ho ancora numeri da inserire

• Richiedo un numero

• Acquisisco il numero

• se è il più grande che ho visto fino ad ora

• è il mio nuovo massimo

(3)

2

Ciao!

3

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(4)

2

Ciao!

4

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(5)

2

Ciao!

5

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(6)

2

Ciao!

6

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(7)

2

Ciao!

7

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(8)

2

Ciao!

8

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(9)

2

Ciao!

9

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(10)

2

Ciao!

Si può fare in un altro modo? 10

(Scorsa esercitazione) Esercizio 5: trova il maggiore

(11)

2

Ciao!

11

Il ciclo for

(12)

2

Ciao!

12

Il ciclo for

(13)

2

Ciao!

13

Il ciclo for

(14)

2

Ciao!

14

Esercizio 1: trova il maggiore con ciclo for

(15)

2

Ciao!

Esercizio 1: trova il maggiore con ciclo for

15

(16)

2

Ciao!

16

Esercizio 1: trova il maggiore con ciclo for

(17)

2

Ciao!

17

Esercizio 1: trova il maggiore con ciclo for

(18)

2

Ciao!

18

Esercizio 1: trova il maggiore con ciclo for

(19)

2

Ciao!

19

Esercizio 1: trova il maggiore con ciclo for

(20)

2

Ciao!

20

Cicli a confronto

(21)

2

Ciao!

21

Esercizio 2: fattoriale con ciclo for

(22)

2

Ciao!

22

Esercizio 2: fattoriale con ciclo for

(23)

2

Ciao!

23

Esercizio 2: fattoriale con ciclo for

(24)

2

Ciao!

24

Esercizio 2: fattoriale con ciclo for

(25)

2

Ciao!

25

Esercizio 2: fattoriale con ciclo for

(26)

2

Ciao!

26

Esercizio 2: fattoriale con ciclo for

(27)

2

Ciao!

27

Esercizio 2: fattoriale con ciclo for

(28)

2

Ciao!

28

Esercizio 2: fattoriale con ciclo for

(29)

2

Ciao!

29

Esercizio 2: fattoriale con ciclo for

(30)

2

Ciao!

30

Esercizio 2: fattoriale con ciclo for

(31)

2

Ciao!

31

Esercizio 2: fattoriale con ciclo for

(32)

2

Ciao!

32

Esercizio 2: fattoriale con ciclo for

(33)

2

Ciao!

33

Esercizio 2: fattoriale con ciclo while?

(34)

34

Logica Booleana e

Mappe di Karnaugh

(35)

George Boole

George Boole (Lincoln, 2

novembre 1815[1] – Ballintemple, 8 dicembre 1864[1]) è stato un

matematico e logico britannico, ed è considerato il fondatore della

logica matematica[1]. La sua opera influenzò anche settori della

filosofia e diede vita alla scuola degli algebristi della logica.

35

(36)

Le operazioni logiche (booleane)

36

A B A and B

F F F

F V F

V F F

V V V

A B A or B

F F F

F V V

V F V

V V V

A not A

F V

V F

Operazione “and” Operazione “or”

Operazione “not”

Ci sono altri operatori?

(37)

Le operazioni logiche (booleane) - 2

37

Un riassunto non esaustivo su…

https://it.wikipedia.org/wiki/Algebra_di_Boole#NOT

(38)

Proprietà logiche

38

(39)

Dimostrazione della proprietà di

39

Dimostrazione

(40)

Leggi di De Morgan

40

(41)

Esercizi sulla Algebra di Boole

ATTENZIONE!

Questi li facciamo alla lavagna ;) Trovate delle scansioni sul mio

sito internet alessandronacci.it

41

(42)

Esercizio sulla Algebra di Boole

42

AXO – esame di giovedì 4 marzo 2010 - CON SOLUZIONI pagina 13 di 22

seconda parte – algebra booleana

Si consideri la funzione booleana di 3 variabili G(a ,b, c) espressa dall’equazione seguente:

G(a, b, c) = a b c + !a !b c + !a b c + a b !c

Si trasformi - tramite le proprietà dell’algebra di commutazione - l’equazione di G in modo da ridurre il co- sto della sua realizzazione, indicando le singole operazioni svolte e il nome oppure la forma della proprietà utilizzata.

Soluzione via breve

a b c + !a !b c + !a b c + a b !c distributiva

!a c (b + !b) + a b (c + !c) elemento neutro

!a c 1 + a b 1 elemento neutro

!a c + a b forma minima

oppure (ma è più lunga)

a b c + !a !b c + !a b c + a b !c

a b c + !a !b c + !a b c + a b !c + a b c + !a b c idempotenza a b c + !a b c + !a b c + !a !b c + a b c + a b !c commutativa (a + !a) b c + !a (b + !b) c + a b (c + !c) distributiva

1 b c + !a 1 c + a b 1 elemento neutro

b c + !a c + a b elemento neutro

1 b c + !a c + a b elemento inverso

(a + !a) b c + !a c + a b distributiva

a b c + !a b c + !a c + a b commutativa

a b c + a b + !a b c + !a c assorbimento

a b + !a c forma minima

(43)

Esercizio sulla Algebra di Boole (soluzione)

43

a b c + !a !b c + !a b c + a b !c

(44)

Esercizio sulla Algebra di Boole (soluzione)

44

a b c + !a !b c + !a b c + a b !c

MOLTO CARIN O MA…

Troppo intuiti vo! Ergo, poco automatizzati le…

Esiste quindi un metodo pi ù meccanico?

(45)

Mappe di Karnaugh (1)

45

f (a, b, c) =

∑

(001, 011,101,110,111) 0 0 0 0 1

0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1

a b c d f

00 01 11 10 00 1 1 0 0

1 1 1 1 0 0 1 1 1 0 0 1 c,da,b

(46)

46

f (a, b, c) =

∑

(001, 011,101,110,111) 0 0 0 0 1

0 0 0 1 1 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1

a b c d f

a'c'; ad

a'b'd'; b'cd'; ab'c; c'd

00 01 11 10 00

01 11 10

1 1 0 0 1 1 1 1 0 0 1 1 1 0 0 1 c,da,b

Implicanti primi essenziali

Implicanti primi

Completamente ridondante

Un implicante si dice implicante primo essenziale se esiste almeno un mintermine che non è coperto da nessun altro implicante primo.

(47)

47

a'c'; ad

a'b'd'; b'cd'; ab'c; c'd

00 01 11 10 00

01 11 10

0 0 0 0 1 0 0 1 c,d a,b

Implicanti primi essenziali

Implicanti primi

f(a,b,c,d)= a'c'+ad+b'cd‘

Forma minima (unica)

Parzialmente ridondanti

Tabella ottenuta dopo la selezione degli implicanti primi essenziali

1 da coprire

Un implicante si dice implicante primo essenziale se esiste almeno un mintermine che non è coperto da nessun altro implicante primo.

(48)

48

( )

∑

= 0,2,4,5,10,11,13,15 )

, , ,

(a b c d f

Nessuno

a'c'd'; bc’d; acd; b’cd’;

a’b’d’; a’bc’; abd; ab’c

00 01 11 10 00

01 11 10

1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1 c,da,b

Implicanti primi essenziali Implicanti primi

f(a,b,c,d)= a'c'd'+ bc’d+ acd+ b’cd’

f(a,b,c,d)= a’b’d’+ a’bc’+ abd+ ab’c Due forme minime

a b c d f 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0 0 1 0 0 1 0 1 0 1 1 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1

Un implicante si dice implicante primo essenziale se esiste almeno un mintermine che non è coperto da nessun altro implicante

primo.

(49)

• Online trovate una dispensa che le spiega con un altro esempio! :)

49

(50)

50