Post on 01-May-2015
transcript
Pirini Ilario 3^ EA Istituto tecnico I.I.S. Maserati
Indice:
o L’algebra di Booleo Applicazione dell’algebra di
Booleo Esercizi e testo Approfondimenti e curiosità
Chi era George Boole?
Boole George nasce il 2 novembre 1815 a
Lincolnshire in Gran Bretagna. Sviluppò
assieme ad Auguste De Morgan la logica
matematica moderna e il metodo
simbolico. Boole e De Morgan fondarono
l'algebra della logica o algebra booleana.
www.dizionarioinformatico.com
L’ algebra BooleanaL’ algebra Booleana Contempla due costanti 00 e 11 (falsofalso e verovero) Corrispondono a due stati che si escludono a vicenda Possono descrivere lo stato di apertura o chiusura di un generico contatto o di un circuito a più contatti
Si definiscono delle operazioni fra i valori booleani:ANDAND, OROR, NOTNOT sono gli operatori fondamentali
0 1
www.dizionarioinformatico.com
L’operazione diL’operazione di ANDAND
Si definisce l’operazione di prodotto logicoprodotto logico (AND):il valore del prodotto logico è il simbolo 1 se il valore di tutti gli operandi è il simbolo 1
00 = 001 = 010 = 011 = 1
11
11
01
10
10
01
00
00
www.wikipedia.org
L’operazione di L’operazione di OROR
Si definisce l’operazione di somma logicasomma logica (OR):il valore della somma logica è il simbolo 1 se il valore di almeno uno degli addendi è il simbolo 1
0
0
0
1
0+0 0+1
0+0 = 00+1 = 11+0 = 11+1 = 1
1
1
1
0
1+0 1+1
www.wikipedia.org
La negazioneLa negazione NOTNOT Si definisce l’operatore di negazionenegazione (NOT):
l’operatore inverte il valore della costante su cui opera
Dalla definizione…
0 = 11 = 0
0 = 01 = 1
www.wikipedia.org
La tabella di veritàLa tabella di verità• Dalle otto combinazioni si ottiene la tabella di veritàtabella di verità della funzione logica
• Si può scrivere la funzione Y come somma logica di prodotti logicisomma logica di prodotti logici A B C Y0 0 0 00 0 1 10 1 0 10 1 1 01 0 0 11 0 1 01 1 0 01 1 1 1
Y = ABC + ABC + ABC + ABC
Una variabile y è una funzione delle n variabili indipendenti x1, x2,…, xn, se esiste un criterio che fa corrispondere in modo univoco ad ognuna delle 2n configurazioni delle xi un valore di y
Una rappresentazione esplicita di una funzione è la tabella di veritàtabella di verità, in cui si elencano tutte le possibili combinazioni di x1, x2, …, xn, con associato il valore di y
Funzioni logicheFunzioni logiche
y = F(x1,x2,…,xn)
x1 x2 y0 0 00 1 11 0 11 1 1
y = x1+x2
La forma canonica La forma canonica Date tre variabili booleane (A,B,C), si scriva la funzione Y
che vale 1 quando solo due di esse hanno valore 1
Si può scrivere la funzione come somma logica delle configurazioni corrispondenti agli 1
Y = ABC + ABC + ABC
A B C Y0 0 0 00 0 1 00 1 0 00 1 1 11 0 0 01 0 1 11 1 0 11 1 1 0
Forma canonica: somma di prodotti (OR di AND)Forma canonica: somma di prodotti (OR di AND) tutte le funzioni logiche si possono scrivere in questa forma
Variabili binarieVariabili binarie
Una variabile binaria indipendente può assumere uno dei due valori 0 e 1
Date n variabili binarie indipendenti, la loro somma logica (OR) è
x0
1
x1+ x2+ …+ xn =
1 se almeno una xi vale 1
0 se x1= x2= …= xn = 0
www.wikipedia.org
ANDAND ee NOTNOT con variabili binariecon variabili binarie
x1 x2 … xn =
0 se almeno una xi vale 0
1 se x1= x2= …= xn = 1
Date n variabili binarie indipendenti, il loro prodotto logico (AND) è
La negazione di una variabile x è
x = 0 se x = 1x = 1 se x = 0
www.wikipedia.org
Date n variabili binarie indipendenti x1, x2,…, xn, queste possono assumere 2n configurazioni distinte
Una configurazione specifica è individuata univocamente da un AND (a valore 1) di tutte le variabili, dove quelle corrispondenti ai valori 0 compaiono negate
Configurazioni delle variabiliConfigurazioni delle variabili
Ad esempio per n=3 si hanno 8 configurazioni
x1x2x3000 001 010 011100 101 110 111
x1x2x3010
www.wikipedia.org
Minterm
Se in una configurazione una variabile compare con 1 si assume il valore diretto se invece compare con uno 0 si assume il valore negato.
Prendendo una funzione in esempio scriveremo:
y = x1x2x3 + x1x2x3 + x1x2x3
Ciascuno di questi prodotti si chiama MINTERM
www.wikipedia.org
Minterm
La funzione conoscendo la sua tabella di verità, potrà essere espressa sotto forma di somme di prodotti dei termini minimi.
Se una funzione è direttamente espressa sotto forma di somme di minterm sarà possibile costruire la sua tabella di verità, mettendo 1 nelle configurazioni relative ai minterm, e 0 negli altri casi.
www.wikipedia.org
Maxterm
Dalla tabella di verità si può affermare ogni maxterm è la somma di tutte le variabili dirette o negate a seconda che la configurazione contenga 1 o 0.
y = (x1+x2+x3)· (x1+x2+x°3)· (x1+x°2+x°3)· (x°1+x°2+x3)· (x°1+x°2+x°3)
ossia sotto forma di prodotto di somme.
Ciascuna delle somme chiama maxterm (termine massimo).
Applicazione dell’algebra di Boole ai
circuiti digitali In questa presentazione l'algebra di Boole
verrà utilizzata in un diagramma di flusso per rendere più intuitivo comprendere il funzionamento di quei semplici circuiti digitali che costituiscono la base dei computer.
"esco se è bel tempo ed è caldo.“ "esco se è bel tempo o se è caldo".
www.nemesi.net
Tenendo presente la seguente tabella possiamo verificare le due frasi
Quindi avremo:
•"esco se è bel tempo ed è caldo”= AND•"esco se è bel tempo o se è caldo“ = OR
Applicazione dell’algebra di Boole ai
circuiti digitali
www.nemesi.net
Applicazione dell’algebra di Boole ai circuiti digitali
Nel Primo caso la lampadina si accenderà quando:
A=0 B=0
YA
B
Nel secondo invece la lampadina si accenderà quando:
A=0 B=1
YA
B
www.nemesi.net
Un esercizioUn esercizio Progettare un circuito per accendere e spegnere una
lampada da uno qualsiasi di tre interruttori indipendenti
A B C
1 1 1
0 0 0
A B C
1 1
0
1
0 0
0 00
0 01
Cambia lostato di uninterruttorequalsiasi
Y = 0
Y = 1
Un circuito con due interruttoriUn circuito con due interruttori
I due interruttori corrispondono a due variabili (A,B) a valori booleani le variabili assumono i
due valori 0 e 1 che corrispondono alle due posizioni dell’interruttore
A B Y
0 0 1 0 1 0 1 0 0 1 1 1
Y = AB+ABA B
A B0
11
0
A=1 B=0
Y
A B
A B0
11
0
A=1 B=1
Y
A B
A B0
11
0
A=0 B=1
Y
A B
A B0
11
0
A=0 B=0
Y
Per gli operatori AND e OR valgono le seguenti proprietà:
Per l’operatore NOT si provano le seguenti identità:
Altre proprietàAltre proprietà
commutativacommutativa x1+x2 = x2+x1 x1 x2 = x2 x1
associativaassociativa x1+x2+x3 = x1+(x2+x3) x1 x2 x3 = x1(x2 x3)
distributiva deldistributiva del prodotto rispetto alla sommaprodotto rispetto alla somma x1 x2 + x1 x3 =
x1(x2+x3)
x + x = 1x x = 0
x = x
Mappe di KARNAUGH
Le mappe di Karnaugh sono delle tabelle che permettono in modo immediato la rappresentazione e la semplificazione di funzioni booleane fino 6 variabili.
Le Mappe di K. costituiscono un altro metodo per rappresentare una funzione booleana;
xy00 01 11 10
z
0 1 1 0 0
1 0 1 1 1
Rappresentazione con Mappa di K. di una funzione.
Analisi delle combinazioniAnalisi delle combinazioni Si considera cosa accade a partire dalla configurazione di
partenza, cambiando lo stato di un interruttore per volta
A B C
0 00
Y = 0
Y = 1A B C
0 10
A B C
0 01
Y = 1
A B C
1 00
Y = 1 Y = 0A B C
1 01
A B C
1 11
Y = 10 11
A B CY = 0
1 10
A B CY = 0