Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si...

Fondamenti di InformaticaAlgebra d i Boole

P r o f. R a f fa e l e P i z zo l a n t e

A . A . 2 0 1 6 / 1 7

L’Algebra di Boole – 1/4• Storia• Il matematico inglese George Boole nel 1847 fondò un campo della

matematica e della filosofia chiamato logica simbolica

• Shannon per primo applicò la logica simbolica ai circuiti logici nel 1939

• Basi• Variabili booleane (o binarie)

• Variabili i cui valori possono essere 0 oppure 1

• Funzioni booleane

• Funzioni i cui input ed output sono variabili booleane

Algebra di Boole

L’Algebra di Boole – 2/4•Relazione con i circuiti logici• Si studia l’algebra booleana poiché le sue funzioni sono

isomorfe ai circuiti digitali:• un circuito digitale può essere espresso tramite un’espressione booleana e

viceversa

• Le variabili booleane corrispondono a segnali

• Le funzioni booleane corrispondono a circuiti

Algebra di Boole

L’Algebra di Boole – 3/4• Una variabile booleana è• Una variabile che può assumere esclusivamente UN valore fra 0 o 1

• Sia 𝑥 una variabile booleana, allora 𝑥 = 0 oppure 𝑥 = 1

• Contempla quindi due stati che si escludono a vicenda: 0 e 1 (falso e vero)• Gli stati possono descrivere, ad esempio, lo stato di apertura o chiusura di un

circuito, ecc.

Algebra di Boole

L’Algebra di Boole – 4/4 • Sulle variabili e i valori booleani si definiscono gli operatori• AND• OR• NOT• Ed altri definiti a partire da essi

•Gli operatori AND e OR sono operatori binari: agiscono su dueoperandi

•L’operatore NOT è un operatore unario: agisce su un solo operando

•Un operando può essere:• Variabile booleana• Valore booleano (1 o 0)

Algebra di Boole

Gli operatori (o funzioni)• Gli operatori (o funzioni)• AND

• OR

• NOT

Algebra di Boole

• OR

• NOT

Algebra di Boole

AND – Prodotto Logico• Il risultato dell’operatore (o funzione) AND è 1 se il valore di entrambi gli operandi è 1. Il risultato è 0 negli altri casi

• Date n variabili binarie indipendenti, il loro prodotto logico (AND) è dato da

x1 x2 … xn =0 se almeno una xi vale 0, 𝑐𝑜𝑛 1 ≤ 𝑖 ≤ 𝑛

1 se x1= x2= …= xn = 1

𝑥1 𝑥2 𝐹 𝑥1, 𝑥2 = 𝑥1 × 𝑥20 0 0

Algebra di Boole

AND – Prodotto Logico• Il risultato dell’operatore (o funzione) AND è 1 se il valore di entrambi gli operandi è 1. Il risultato è 0 negli altri casi

• Date n variabili binarie indipendenti, il loro prodotto logico (AND) è dato da

x1 x2 … xn =0 se almeno una xi vale 0, 𝑐𝑜𝑛 1 ≤ 𝑖 ≤ 𝑛

1 se x1= x2= …= xn = 1

𝑥1 𝑥2 𝐹 𝑥1, 𝑥2 = 𝑥1 × 𝑥20 0 0

Tavola di verità

Algebra di Boole

AND – Prodotto LogicoPossibili Rappresentazioni• x & y

• x and y

• x ∧ 𝒚

• x ∩ 𝒚

• x * y

• x × 𝒚

• xy

Algebra di Boole

AND – Prodotto LogicoPossibili Rappresentazioni• x & y

• x and y

• x ∧ 𝑦

• x ∩ 𝑦

•x * y

• x × 𝒚

• xy

Algebra di Boole

• OR

• NOT

Algebra di Boole

OR – Somma Logica• Il risultato dell’operatore (o funzione) OR è 1 se almeno uno degli operandi vale 1. Il risultato è 0 negli altri casi

• Date n variabili binarie, la loro somma logica (OR) è data da

x1+ x2+ …+ xn =

1 se almeno una xi vale 1, 𝑐𝑜𝑛 1 ≤ 𝑖 ≤ 𝑛

0 se x1= x2= …= xn = 0

𝑥1 𝑥2 𝐹 𝑥1, 𝑥2 = 𝑥1 + 𝑥20 0 0

Algebra di Boole

OR – Somma LogicaPossibili Rappresentazioni• x | y

• x # y

• x or y

• x ∪ 𝒚

• x ∨ 𝒚

• x + y

Algebra di Boole

OR – Somma LogicaPossibili Rappresentazioni• x | y

• x # y

• x or y

• x ∪ 𝑦

• x ∨ 𝑦

• x + y

Algebra di Boole

• OR

• NOT

Algebra di Boole

NOT – Negazione • L’operatore (o funzione) NOT, inverte il valore dell’operando su cui opera

•Doppia negazione:

• L’elemento ҧ𝑥 viene detto complemento di x

𝑥1 𝐹 𝑥1 = 𝑥10 1

Algebra di Boole

NOT – NegazionePossibili Rappresentazioni• y = ~x

• y = !x

• y = not x

• y = x’

• y = ¬𝒙

• y = ഥ𝒙

Algebra di Boole

NOT – NegazionePossibili Rappresentazioni• y = ~x

• y = !x

• y = not x

• y = x’

• y = ¬𝑥

• y = ഥ𝒙

Algebra di Boole

Algebra di Boole: Alcune Identità

Funzione AND Funzione OR Funzione NOT

0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1

0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0

1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥

1 × 1 = 1 1 + 1 = 1

x × 0 = 0 x + 0 = x

0 × x = 0 0 + x = x

x × 1 = x x + 1 = 1

1 × x = x 1 + x = 1

x × x = x x + x = x

Algebra di Boole

0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1

0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0

1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥

1 × 1 = 1 1 + 1 = 1

x × 0 = 0 x + 0 = x

0 × x = 0 0 + x = x

x × 1 = x x + 1 = 1

1 × x = x 1 + x = 1

x × x = x x + x = x

Prodotto Logico

Algebra di Boole

0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1

0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0

1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥

1 × 1 = 1 1 + 1 = 1

x × 0 = 0 x + 0 = x

0 × x = 0 0 + x = x

x × 1 = x x + 1 = 1

1 × x = x 1 + x = 1

x × x = x x + x = x

Somma Logica

NOTA: 1+1=1

Algebra di Boole

0 × 0 = 0 0 + 0 = 0 x+ ҧ𝑥 = 1

0 × 1 = 0 0 + 1 = 1 x × ҧ𝑥 = 0

1 × 0 = 0 1 + 0 = 1 Ӗ𝑥 = 𝑥

1 × 1 = 1 1 + 1 = 1

x × 0 = 0 x + 0 = x

0 × x = 0 0 + x = x

x × 1 = x x + 1 = 1

1 × x = x 1 + x = 1

x × x = x x + x = x

Legge dell’idempotenza

Algebra di Boole

Algebra di Boole: Proprietà e Leggi

Proprietà Commutativa Leggi di Assorbimento

Proprietà Distributiva Leggi di De Morgan

Proprietà Associativa Altre Note

𝑥1𝑥2 = 𝑥2𝑥1𝑥1+ 𝑥2 = 𝑥2+ 𝑥1

𝑥1+ 𝑥1𝑥2 = 𝑥1𝑥1(𝑥1+ 𝑥2) = 𝑥1

𝑥1 𝑥2+ 𝑥3 = 𝑥1𝑥2+ 𝑥2𝑥3𝑥1+ 𝑥2𝑥3 = 𝑥1+ 𝑥2 + (𝑥1+ 𝑥3)

𝑥1 𝑥2𝑥3 = (𝑥1𝑥2)𝑥3𝑥1+ 𝑥2+ 𝑥3 = 𝑥1+ 𝑥2 + 𝑥3

𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2

𝑥1+ ഥ𝑥1𝑥2 = 𝑥1+ 𝑥2𝑥1( ഥ𝑥1+ 𝑥2) = 𝑥1𝑥2

Algebra di Boole

Leggi di De Morgan

Leggi di De Morgan – 1/2

𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2

Algebra di Boole

Leggi di De Morgan

𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2

• Il complemento di due o più variabili poste in OR è uguale all’AND dei complementi delle singole variabili

Algebra di Boole

Leggi di De Morgan

𝑥1+ 𝑥2 = ഥ𝑥1 × ഥ𝑥2𝑥1 × 𝑥2 = ഥ𝑥1+ ഥ𝑥2

• Il complemento di due o più variabili poste in AND è equivalente all’OR dei complementi delle singole variabili

Algebra di Boole

Osservazioni• Dalle leggi di De Morgan si evince che la sceltadelle funzioni OR, AND e NOT, come operatoriprimitivi, è ridondante• L’operazione logica AND può essere espressa in funzione

delle operazioni OR e NOT

• In modo analogo, l’operazione OR può essere espressatramite AND e NOT

Algebra di Boole

Funzioni Logiche (o Booleane) – 1/5• Date n variabili booleane indipendenti: x1, x2,…, xn,queste possono assumere 2n configurazioni distinte• Ad esempio per n = 4 si hanno 16 (24) configurazioni

• Esempio di configurazione su n = 4

• 𝑥1 = 1, 𝑥2 = 0, 𝑥3 = 0, 𝑥4 = 1

• Ogni riga mostra (in rosso) il valore restituito da F apartire da una particolare configurazione dell’input

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Algebra di Boole

Funzioni Logiche (o Booleane) – 2/5• 010 indica la configurazione in cui

• 𝒙𝟏 = 0• 𝒙𝟐 = 1• 𝒙𝟑 = 0

• Questa configurazione si scrive semplicemente con ilprodotto logico

• 𝒙𝟏𝒙𝟐𝒙𝟑

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Algebra di Boole

Funzioni Logiche (o Booleane) – 2/5• 010 indica la configurazione in cui

• 𝒙𝟏 = 0• 𝒙𝟐 = 1• 𝒙𝟑 = 0

• Questa configurazione si scrive semplicemente con ilprodotto logico

• 𝒙𝟏𝒙𝟐𝒙𝟑

• Una configurazione specifica è individuataunivocamente da un AND (prodotto logico) di tutte levariabili, dove quelle corrispondenti ai valori 0compaiono negate

• Prodotto fondamentale o prodotto minimo

• minterm

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

x1x2x3010

Algebra di Boole

Funzioni Logiche (o Booleane) – 2/5

ഥ𝑥1 ഥ𝑥2 ഥ𝑥3

ഥ𝑥1 ഥ𝑥2 𝑥3

ഥ𝑥1 𝑥2 ഥ𝑥3

ഥ𝑥1 𝑥2𝑥3

𝑥1 ഥ𝑥2 ഥ𝑥3

𝑥1 ഥ𝑥2 𝑥3

𝑥1 𝑥2 ഥ𝑥3

𝑥1 𝑥2𝑥3

Configurazioni x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Tutte le configurazioni della tavola di verità dell’esempio

Algebra di Boole

Funzioni Logiche (o Booleane) – 3/5• Una variabile y è una funzione booleana delle n variabili indipendentix1, x2,…, xn, se esiste un criterio che fa corrispondere in modo univocoad ognuna delle 2n configurazioni delle variabili xi un valore di y (chepotrà essere 0 oppure 1)

• Una funzione può essere rappresentata in maniera esplicita tramite latabella (o tavola) di verità, in cui si elencano tutte le possibilicombinazioni di x1, x2, …, xn, con associato il valore di y

y = F(x1, x2, …, xn)

y = x1+ x2

𝑥1 𝑥2 𝑦

Algebra di Boole

Funzioni Logiche (o Booleane) – 3/5– Tavola di verità –

• Modo sistematico per specificare il valore di una funzione per tutte le possibili combinazioni di valori di input• Una funzione che prende 2 input ha 4 = 22 righe

• Una funzione che prende n input ha 2n righe

• Esempio (2 variabili: x e y 4 righe):

x 𝑦 𝐹𝑢𝑛𝑧𝑖𝑜𝑛𝑒 𝐹

Algebra di Boole

Funzioni Logiche (o Booleane) – 4/5• Oltre che con la tavola di verità, ogni funzione booleana può esseredeterminata tramite la sua espressione booleana

• Per passare dalla rappresentazione mediantetavola di verità alla notazione tramiteespressione booleana è necessario:

1. Identificare tutte le righe della tavola di veritàche danno 1 in output

2. Per ogni riga con un 1 in output, scrivere ilminterm della configurazione delle variabiliche la definiscono

3. Collegare tramite OR tutti i minterm ottenuti

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

ഥ𝑥1 𝑥2𝑥3

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

ഥ𝑥1 𝑥2𝑥3 𝑥1 ഥ𝑥2 𝑥3

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

ഥ𝑥1 𝑥2𝑥3 𝑥1 ഥ𝑥2 𝑥3 𝑥1 𝑥2 ഥ𝑥3 𝑥1 𝑥2𝑥3

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

ഥ𝑥1 𝑥2𝑥3 𝑥1 ഥ𝑥2 𝑥3 𝑥1 𝑥2 ഥ𝑥3 𝑥1 𝑥2𝑥3

Algebra di Boole

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

ഥ𝑥1 𝑥2𝑥3+ 𝑥1 ഥ𝑥2 𝑥3+ 𝑥1 𝑥2 ഥ𝑥3+𝑥1 𝑥2𝑥3

Algebra di Boole

Funzioni Logiche (o Booleane) – 5/5• 𝐹 𝑥1, 𝑥2, 𝑥3 = ഥ𝑥1 𝑥2𝑥3+ 𝑥1 ഥ𝑥2 𝑥3+ 𝑥1 𝑥2 ഥ𝑥3+ 𝑥1 𝑥2𝑥3

• Con l’uso dei minterm possiamo determinarel’espressione booleana di una funzionebooleana a partire dalla tavola di verità

• L’espressione booleana trovata si chiamaforma canonica della funzione e si ottiene conuno sviluppo in minterm• Una somma (OR) di prodotti (AND)

• Se un minterm assume valore 1 anche lafunzione F assume il valore 1

• Tutte le funzioni logiche possono essereriportate in forma canonica

x1 x2 x3 F(x1, x2, x3)

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 1

Algebra di Boole

Esempio (dalla tavola di verità alla funzione):

Funzione Exclusive OR (XOR) • Il comportamento della funzione Exclusive OR (XOR) su due variabili indipendenti può essere descritto con la seguente tavola di verità

• Sostanzialmente la funzione XOR verifica la disuguaglianza di due variabili• Restituisce 1 sse 𝑥1 e 𝑥2 sono diversi

• Restituisce 0 sse 𝑥1 e 𝑥2 sono uguali

𝑥1 𝑥2 𝑋𝑂𝑅

Algebra di Boole

Dalla Funzione alla Tavola di Verità• Vediamo un esempio per la funzione • 𝐹 = 𝑥 × (𝑦 + 𝑧)

x y z F

0 0 0 0

0 0 1 0

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 0

1 1 0 0

1 1 1 0

Algebra di Boole

Esercizio per Casa: Dalla Tavola di Verità all’Espressione Booleana

Tavola di Verità della funzione X

A B C X

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 0

1 0 1 1

1 1 0 1

1 1 1 0

X = ______________________________

Algebra di Boole

Riferimenti• Libro di testo• Capitolo 3

• Paragrafo 4

Algebra di Boole

Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si...

Documents

Transcript of Fondamenti di Informatica · L’Algebra di Boole –2/4 •Relazione con i circuiti logici •Si...

Algebra di Boole - University of CagliariA.A. 2013/2014 Elettronica M. Barbaro 3 Algebra di Boole Inizialmente l’algebra di Boole è stata concepita per gestire delle proposizioni

Modulo 2 “L’algebra dei polinomi”

Algebra di Boole, elementi di logica e Mappe di Karnaughhome.deib.polimi.it/santambr/dida/ieim/2016/doc/lezioni/... · 2016-03-18 · • L’algebra di Boole (inventata da G. Boole,

Algebra de Boole

Lezione 9 - Algebra di Boolewebuser.unicas.it/tortorella/CalcEl1_0708/PDF/Lezione 9 - Algebra di... · L’algebra di Boole • Consente di descrivere in forma algebrica le funzioni

Algebra Boole Circuiti Logici

Esercizio - Algebra di Boole, Aritmetica Binaria, Codifica ... · Esercizio - Algebra di Boole, Aritmetica Binaria, Codifica delle Informazioni ( 2,5 punti ) (a) Si costruisca la

2 algebra degli enunciati - Libero Community · 16/09/12 2 Algebradi’BOOLE’! L’algebra di Boole è rimasta pressoché ignorata per oltre 80 anni, cioè fino al 1937, quando

Algebra di Boole. Chi era Boole? George Boole, è stato un matematico e logico britannico, ed è considerato il fondatore della logica matematica. Nel 1854,

Fondamenti dell’Informatica Algebra di Boole

Struttura Programmi Algebra di Boole

PARTE VIII: L’algebra di Boole...Un po’ di storia della Logica Uno degli aspetti più interessanti è dato dai cosiddetti paradossi (parà + doxa = contro l'opinione comune) e

Algebra di Boole e circuiti dalle funzioni logiche ai ...pedersini.di.unimi.it/AER/AE13_L03-05.pdf · " Analisi dei circuiti digitali ! Descrizione del funzionamento in modo economico.

PARTE VIII: L’algebra di Boole · Sviluppò assieme ad Auguste De Morgan la logica matematica moderna e il metodo simbolico. Boole e De Morgan costruirono l'algebra della logica

Parte IV Indice - polito.it in italiano/4... · Fondamenti di Informatica IV.2 Algebra booleana L’algebra booleana deve il suo nome a Boole che ne formalizzò le regole L’algebra

Corso E Algebra di Boole - Dipartimento Informaticaarc1/boole.pdf · 2 Algebra di Boole L’algebra che useremo è dovuta a Boole ed è detta ALGEBRA BOOLEANA. Le variabili di questa

2 02-Algebra Boole - crescenziogallo.it€¦ · Algebra booleana • Valori: FALSE(=0); TRUE(=1); operatori: NOT, AND, OR • Applicazioni: - analisi dei circuiti digitali (descrizione

Algebra di Boole e circuiti dalle funzioni logiche ai ...pedersini.di.unimi.it/AER/AE1_14_L03-06.pdf · A.A. 2014/15 © F. Pedersini – DI, UniMI L 3 – 1 Architetture dei calcolatori

© 2010 Marco Mezzalama, Elio Piccolo, Capire linformatica 1 Marco Mezzlama, Elio Piccolo Capire linformatica Algebra di Boole e Circuiti Logici.

Tema 04 - Algebra de Boole