“ Algebra Boole - Appunti di lezione 1 PDF

Preview

Summary

algebra di boole...

Description

Algebra di Boole

In matematica, informatica ed elettronica, l'algebra di Boole, anche detta algebra booleana, è un ramo dell'algebra astratta che consente di operare utilizzando i soli valori di verità 0 o 1, detti variabili booleane o logiche. Eʼ costruita su dati che possono assumere due valori:

•  Vero indicato di solito con 1 (true, on, chiuso)

•  Falso indicato di solito con 0 (false, off, aperto)

1

Algebra di Boole

I dati 0 e 1 possono rappresentare delle frasi (“oggi piove”, “2 è pari”) che possono essere giuste (vero) o sbagliate (falso), o degli interruttori elettrici chiusi (vero) o aperti (falso). Su questi dati si compiono vari tipi di operazioni.

Il nome viene da George Boole, un matematico che definì delle strutture matematiche, dette appunto algebre di Boole.

2

Algebra di Boole

Si studia lʼalgebra Booleana perchè le funzioni dellʼalgebra booleana sono isomorfe ai circuiti digitali. Cioè un circuito digitale può essere espresso tramite unʼespressione booleana e viceversa. Una funzione booleana ha una o piu variabili in input e fornisce risultati che dipendono solo da queste variabili.

Poiche le variabili possono assumere solo i valori 0 e 1, una funzione booleana con n variabili di input ha solo 2n combinazioni possibili. 3

Algebra di Boole

Lʼalgebra Booleana è adatta per rappresentare ʻeventi binariʼ, cioè condizioni che possono assumere solo due valori.

ESEMPIO: una lampadina può essere accesa (a questa condizione si associa il valore 1 o vero) oppure spenta (valore 0 o falso)

Le funzioni che operano sulle variabili booleane sono dette FUNZIONI BOOLEANE e possono anchʼesse produrre solo i valori 0 e 1.

4

Algebra di Boole

Una funzione booleana F, funzione di variabili booleane, v1, v2, ..., vn, si indica:

F(v1,v2,...,vn)

La funzione può essere definita specificando i valori di F per tutte le possibili combinazioni delle variabili da cui essa dipende. Questo elenco di possibilità è detto TABELLA DELLE VERITAʼ.

5

Algebra di Boole Una funzione booleana F(v1,v2,...,vn) può essere descritta come:

Ogni variabile booleana può assumere due valori, quindi con n variabili si possono avere 2n possibili combinazioni

6

Algebra di Boole ESEMPIO: Descrizione di un evento mediante una funzione booleana Uno studente passa lʼesame se si verifica almeno una delle seguenti condizioni: •  supera sia la prova pratica, sia la prova orale •  non supera la prova pratica, ma è sufficiente alla prova scritta di un appello e supera la prova orale Si può assegnare ad ogni evento una variabile booleana: a = pratica b = scritto c = orale

7

Algebra di Boole Con 3 variabili booleane, ci sono 23 combinazioni possibili. La tabella della verità della funzione booleana “superamento dellʼesame” S (a,b,c) sarà:

8

Opearatori logici Le variabili booleane possono essere combiante da operatori logici. Questi operatori restituiscono anchʼessi un valore logico.

Gli operatori principali sono:

•  AND •  OR •  NOT

9

Opearatori logici Operatore AND • 

Questo operatore è indicato con il simbolo · ( a volte è sottinteso)

• 

Si applica a due operandi e produce un valore secondo le seguenti regole:

Il risultato è vero se entrambi gli operandi sono veri. 10

Opearatori logici Operatore OR • 

Questo operatore è indicato con il simbolo +

• 

Si applica a due operandi e produce un valore secondo le seguenti regole:

Il risultato è vero se almeno uno degli operandi è vero. 11

Opearatori logici Operatore NOT • 

Questo operatore è indicato con il simbolo negare ( es:

• 

a

!

sopra la variabile da

)

Si applica ad un solo operando e produce un valore secondo le seguenti regole:

Il risultato è il valore opposto di quello dellʼoperando; cioè, se lʼoperando è falso lʼuscita è vera e viceversa

12

ESEMPI: Consideriamo le seguenti proposizioni: A: la mela è un frutto

(VERO)

B: il sole è una stella

(VERO)

C: il gatto è un vegetale

(FALSO)

D: lʼerba è blu

(FALSO) AND

A and B: la mela è un frutto AND il sole è una stella

(VERO)

C and B: Il gatto è un vegetale AND il sole è una stella

(FALSO)

A and D: la mela è un frutto AND lʼerba è blu

(FALSO) 13

OR A or B: la mela è un frutto OR il sole è una stella

(VERO)

C or B: Il gatto è un vegetale OR il sole è una stella

(VERO)

A or D: la mela è un frutto OR lʼerba è blu (VERO) C or D: Il gatto è un vegetale OR lʼerba è blu

(FALSO) NOT

not A: la mela NON è un frutto

(FALSO)

not D: lʼerba NON è blu

(VERO) 14

ESPRESSIONI LOGICHE • 

Sono espressioni contenenti solo: !  Variabili booleane !  Le costanti 0 e 1 !  Gli operatori logici

(a + b )! c

Esempio:

Le funzioni logiche possono essere definite da espressioni logiche:

(

)

F1 = a + b ! c 15

Esempio di Tavola di Verità per due ESPRESSIONI LOGICHE:

16

Circuiti logici

• 

Una funzione logica può essere rappresentata da un circuito logico.

• 

Le variabili corrispondono ai fili in ingresso

• 

Il risultato corrisponde allʼuscita del circuito

• 

Gli operatori logici corrispondono alle PORTE LOGICHE

17

PORTE LOGICHE

Sono elementi circuitali che corrispondono alle operazioni logiche e che possono essere combinati per effettuare operazioni più complesse.

18

PORTE LOGICHE Una porta AND può essere sosituita da una porta OR ( e viceversa ) negando gli ingressi e le uscite.

Esistono porte a ingressi multipli:

19

20

CIRCUITI LOGICI Circuito logico equivalente ad una funzione.

21

22

23

DIAGRAMMI DI VENN Visualizzazione grafica delle operazioni nel modello di Algebra di Boole.

John Venn (1834-1923) logico inglese. Studiò logica simbolica approfondendo lʼopera di Boole. Affrontò questioni di logica induttiva e logica tradizionale.

24

Simbologia '

Simb olo di appartenen za

& %

Simb olo di non appartenen za Simb olo di unione tra in siemi

$

Simb olo di in ters ezio ne tra in siemi

#

Simb olo di differenza tra in siemi

/ "

Tale che Simb olo di congi unzione tra propo sizioni

!

Simb olo di disgiun zione tra propo sizioni

Insieme vuo to

A Complementare dell'in sieme A risp etto all' ambiente universo U C UA Complementare dell'in sieme A risp etto all' ambiente universo U 25

LʼOPERAZIONE “ ! ” (AND)

Lʼoperazione “ · ” è lʼoperazione di intersezione di due insiemi 26

Insieme intersezione Dati due insiemi, A e B, si chiama loro intersezione lʼinsieme

degli

elementi

appartenenti

contemporaneamente sia ad A sia a B.

A

B !! B

Nella figura la parte tratteggiata in rosso rappresenta lʼintersezione

A ! B = {x/x ! A " x ! B}

27

Insieme intersezione Quando due insiemi A e B non hanno elementi in comune si dicono disgiunti.

A

B

A!B=! 28

Insieme intersezione Esempio

Se A = {a; b; c; d;} e B = {c; d; e}, risulta A ! B = {c; d} Con i diagrammi di Eulero-Venn A

. . . .d .e

a b

c

B

29

LʼOPERAZIONE “ + ” (OR)

Lʼoperazione “ + ” è lʼoperazione di unione di due insiemi 30

Insieme unione Chiamasi unione di due insiemi A e B lʼinsieme degli elementi appartenenti ad A o a B.

A

B

A!B

Nella figura la parte colorata in turchese rappresenta l’unione

A ! B = {x/x ! A " x ! B} 31

Insieme unione Esempio

{

}

{

}

Se A = a; b; c; d; e B = c; d; e , ris ulta A ! B = a; b; c; d; e

{

}

Con i diagrammi di Eulero-Venn A

. . . .d .e

a b

c

B

32

LʼOPERAZIONE “ " ” (NOT)

33

Insieme differenza Si dice differenza di due insiemi A e B considerati nellʼordine, lʼinsieme, che indicheremo con A-B, costituito dagli elementi di A che non appartengono a B. A

B

A B

A-B

La parte colorata in rosa rappresenta lʼinsieme differenza

A-B

A - B = {x/x # A " x ! B}

34

Insieme complementare Si definisce complementare di un insieme A rispetto ad un insieme ambiente o universo U, lʼinsieme degli elementi di U che non appartengono ad A. U CUA

Nella figura la parte colorata in verde

A

rappresenta il complementare di A e si può indicare sia con CUA

A=CUA= {x/x # U " x ! A}

sia con

A 35...