Algebra booleana (logica)

L' algebra booleana o calcolo booleano, è la parte della matematica che si occupa di un approccio algebrico la visione logica in termini di variabili , di operatori e funzioni su variabili logiche, che permette di utilizzare tecniche algebriche per trattare espressioni a due valori del calcolo di proposte . Fu iniziato nel 1854 dal matematico britannico George Boole . Oggi l'algebra booleana trova molte applicazioni nell'informatica e nella progettazione di circuiti elettronici .

È stato utilizzato per la prima volta per i circuiti di commutazione telefonica da Claude Shannon .

Esempio introduttivo

L'algebra booleana delle funzioni logiche permette di modellare il ragionamento logico , esprimendo uno “stato” in funzione delle condizioni. Ad esempio, se studiamo l'espressione Comunicazione e l'espressione Pick up;

Comunicazione

Comunicazione = Trasmettitore E Ricevitore

La comunicazione sarebbe "VERA" se entrambe le variabili Mittente E Destinatario fossero attive (questa è una funzione logica che dipende dalle variabili Mittente e Destinatario )

Raccogliere

Rispondi = (Squillo E Decisione di rispondere) OPPURE Decisione di chiamare

Per prendere sarebbe “TRUE” o se si sente la suoneria contemporaneamente E si decide di rispondere , o ( OR ) se semplicemente decidere di chiamare .

Essendo l'algebra booleana un dominio comune a tre discipline, incontriamo notazioni diverse per designare lo stesso oggetto. Nel resto dell'articolo indicheremo le varie notazioni, ma ne privilegiamo una per mantenere una certa omogeneità.

Algebra booleana dei valori di verità

Chiamiamo B l' insieme formato da due elementi chiamati valori di verità {VERO, FALSO}. Questo set è anche notato

• B={1,0}{\ stile di visualizzazione B = \ {1.0 \}}
• B={⊤,⊥}{\ displaystyle B = \ {\ top, \ perp \}}.

con per e per . ⊤{\ displaystyle \ top}1{\ stile di visualizzazione 1}⊥{\ displaystyle \ perp}0{\ stile di visualizzazione 0}

La notazione sarà favorita nel seguito . B={1,0}{\ stile di visualizzazione B = \ {1.0 \}}

Su questo insieme possiamo definire due leggi (o operazioni) binarie, le leggi AND e OR, e un'operazione unaria, la negazione (o il complemento).

Per tutti i seguenti esempi e proprietà, {a,b,vs}⊂B{\ displaystyle \ {a, b, c \} \ sottoinsieme B}

Congiunzione

Tabella della legge ET
b \ a	0	1
0	0	0
1	0	1

È definito come segue: a AND b è VERO se e solo se a è VERO e b è VERO.

Si segnala anche questa legge:

• ⋅{\ displaystyle \ cdot \,} ;
• ∧{\ displaystyle \ cuneo} :
• "&" O "&&": questa implementazione fa parte di diversi linguaggi di programmazione come Perl , C , PHP , Swift  ;
• "  AND  ": la maggior parte dei linguaggi di programmazione come, ad esempio, Ada , Pascal , Perl , Python , PHP offrono questa funzione;
• “∧”: usato in diverse notazioni algebriche e in APL  ;
• "*"; il simbolo di una moltiplicazione ordinaria viene utilizzato in alcune lingue che non hanno una funzione adeguata.

Nel seguito  sarà privilegiata la notazione “  ”. ⋅{\ displaystyle \ cdot}

La tavola di questa legge (analoga a una tavola di addizione o moltiplicazione ) non è una tavola di verità .

Disgiunzione

Tabella della legge OR
b \ a	0	1
0	0	1
1	1	1

È definito come segue: a OR b è TRUE se e solo se a è TRUE ob è TRUE. (In particolare, se a è vero e anche b è vero, allora a OR b è vero.)

Si segnala anche questa legge:

• +{\ stile di visualizzazione +}.
• "∨" ("   ") in matematica (e in logica matematica) o in APL.∨{\ displaystyle \ v}
• "|" o "||" in alcuni linguaggi di programmazione.
• Scritto "or" o "OR" nella logica o in alcuni linguaggi di programmazione.

Sarà data la preferenza nel seguente notazione ma si avrà cura del fatto che questa legge non è la solita aggiunta in Z / 2 Z . Ecco perché, in matematica e in logica matematica , la notazione non è usata per designare il "o inclusivo": è riservata al "  o esclusivo  ", operazione che (unita alla "e") rende qualsiasi algebra di booleano un anello booleano , in particolare una Z /2 Z - algebra . +{\ stile di visualizzazione +}+{\ stile di visualizzazione +}

Negazione

La negazione di a è TRUE se e solo se a è FALSE.

Si nota la negazione di a:

• no-a, no a, non a.
• a¯{\ displaystyle {\ bar {a}}}.
• a/{\ stile di visualizzazione a /}.
• ¬a{\ displaystyle \ negativo a}.
• “~ A” in alcune notazioni algebriche, in APL e in alcuni linguaggi di interrogazione di database ( SQL …).
• "! »In alcuni linguaggi di programmazione (C, C++ ...)
• “1-” in alcune lingue che non hanno funzioni adatte ( Batch …) (poiché 1-0 = 1 e 1-1 = 0).

La notazione sarà favorita nel seguito . a¯{\ displaystyle {\ bar {a}}}

Quindi otteniamo e . 0¯=1{\ displaystyle {\ barra {0}} = 1}1¯=0{\ displaystyle {\ barra {1}} = 0}

Proprietà

Proprietà dell'operatore

Gli operatori sono interessati da diverse proprietà comuni:

• Associatività  : e  ;(a+b)+vs=a+(b+vs)=a+b+vs{\ stile di visualizzazione (a + b) + c = a + (b + c) = a + b + c}(a⋅b)⋅vs=a⋅(b⋅vs)=a⋅b⋅vs{\displaystyle (a\cdot b)\cdot c = a\cdot (b\cdot c) = a\cdot b\cdot c}
• Commutatività  : (l'ordine è irrilevante) e  ;a+b=b+a{\ stile di visualizzazione a + b = b + a}a⋅b=b⋅a{\ displaystyle a \ cdot b = b \ cdot a}
• Distributività  : e  ;a⋅(b+vs)=a⋅b+a⋅vs{\ displaystyle a \ cdot (b + c) = a \ cdot b + a \ cdot c}a+b⋅vs=(a+b)⋅(a+vs){\ displaystyle a + b \ cdot c = (a + b) \ cdot (a + c)}
• Idempotenza  : es. : e .a+a=a{\ stile di visualizzazione a + a = a}a⋅a=a{\ displaystyle a \ cdot a = a}

Inoltre, ogni operatore ha un elemento neutro e un elemento assorbente  :

• a+0=0+a=a{\ stile di visualizzazione a + 0 = 0 + a = a} ;
• a+1=1+a=1{\ stile di visualizzazione a + 1 = 1 + a = 1} ;
• a.1=1.a=a{\ stile di visualizzazione a.1 = 1.a = a} ;
• a.0=0.a=0{\ displaystyle a.0 = 0.a = 0} ;

Sono possibili semplificazioni quali:

• a+a⋅b=a{\ displaystyle a + a \ cdot b = a} ;
• a⋅(a+b)=a{\ displaystyle a \ cdot (a + b) = a} ;
• a+a¯.b=a+b{\ displaystyle a + {\ overline {a}}. b = a + b} ;
• a.(a¯+b)=a.b{\ displaystyle a. ({\ overline {a}} + b) = ab}.

il teorema del consenso si applica agli operatori di algebra booleana:

• a.b+a¯.vs=a.b+a¯.vs+b.vs{\ displaystyle a.b + {\ overline {a}}. c = a.b + {\ overline {a}}. c + bc}.

Infine, seguono il principio di complementarietà:

• Involuzione  : ( es: la proposizione "La luce è accesa" equivale a "la luce non è accesa" o, in altre parole, "la luce non è spenta").a=a¯¯{\ displaystyle a = {\ overline {\ overline {a}}}}
• Terzi esclusi  : (la proposta "luce accesa" OPPURE "luce spenta" è sempre TRUE.).a+a¯=1{\ displaystyle a + {\ overline {a}} = 1}
• Contraddizione o antilogia: (la proposizione "luce accesa" AND "luce non accesa" è sempre FALSA.).a.a¯=0{\ displaystyle a. {\ overline {a}} = 0}

Struttura

Troviamo quindi tutte le proprietà che danno a B una struttura di algebra booleana .

Priorità

Per semplificare le scritture, è consuetudine che le operazioni booleane siano soggette alle stesse regole di priorità delle normali operazioni aritmetiche: la funzione AND (moltiplicazione logica) ha quindi priorità sulla funzione OR (somma logica). In tal modo :

1+b⋅0=1+0=1{\ displaystyle 1 + b \ cdot 0 = 1 + 0 = 1}

È ancora possibile inserire parentesi nei calcoli per modificare l'ordine di priorità delle operazioni.

Il teorema di De Morgan

Prima legge di De Morgan (negazione della disgiunzione) è espresso dalla seguente uguaglianza a+b¯=a¯.b¯{\ displaystyle {\ overline {a + b}} = {\ overline {a}}. {\ overline {b}}} Tavolo della verità / Tavolo operatorio a b a+b{\ stile di visualizzazione a + b} a+b¯{\ displaystyle {\ overline {a + b}}} a¯{\ displaystyle {\ overline {a}}} b¯{\ displaystyle {\ overline {b}}} a¯.b¯{\ displaystyle {\ overline {a}}. {\ overline {b}}} 0 0 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0 In entrambi i casi, l'espressione sarà vero solo se un e b sono falsi .

Seconda legge di De Morgan (negazione della congiunzione) a.b¯=a¯+b¯{\ displaystyle {\ overline {ab}} = {\ overline {a}} + {\ overline {b}}} Tavolo della verità / Tavolo operatorio a b a.b{\ stile di visualizzazione ab} a.b¯{\ displaystyle {\ overline {ab}}} a¯{\ displaystyle {\ overline {a}}} b¯{\ displaystyle {\ overline {b}}} a¯+b¯{\ displaystyle {\ overline {a}} + {\ overline {b}}} 0 0 0 1 1 1 1 0 1 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 0 0 0 In entrambi i casi, l'espressione sarà solo FALSE se un e b sono vere .

Funzioni logiche

Matematicamente, una funzione logica o un operatore logico è un'applicazione a B n in B .

In elettronica , una funzione logica è una scatola nera che riceve in ingresso un certo numero di variabili logiche e che emette una variabile logica in funzione delle variabili di ingresso. La funzione logica dell'articolo spiega come costruire le scatole nere di alcune funzioni fondamentali.

Una tabella di verità permette di specificare lo stato dell'uscita secondo gli stati degli ingressi. Caratterizza la funzione logica.

Qualsiasi tabella di verità, e quindi qualsiasi funzione logica, può essere descritta utilizzando le tre operazioni fondamentali:

• disgiunzione (OR)
• congiunzione (AND)
• negazione (NO)

Dimostriamo anche che esistono esattamente funzioni logiche dei parametri. Basta infatti considerare tutte le possibili tavole di verità, oppure considerare lo sviluppo di una funzione di parametri. 22non{\ stile di visualizzazione 2 ^ {2 ^ {n}}}non{\ stile di visualizzazione n}non{\ stile di visualizzazione n}

Funzioni logiche fondamentali

Derivano dalle tre operazioni fondamentali e poi definiscono una funzione da B a B  : il complemento o inversione due funzioni da B 2 a B che sono la somma (OR) e il prodotto (AND)

Tabella della verità inversa a a¯{\ displaystyle {\ bar {a}}} 0 1 1 0

Tavola di verità della somma a b un b+{\ stile di visualizzazione + \,} 0 0 0 0 1 1 1 0 1 1 1 1

Tabella di verità del prodotto a b un b⋅{\ displaystyle \ cdot \,} 0 0 0 0 1 0 1 0 0 1 1 1

Funzioni logiche composte

Queste sono le funzioni logiche a due variabili. Tra questi, ce ne sono alcuni sufficientemente interessanti da poter dare un nome.

Disgiunzione esclusiva Exclusive

Tabella della verità XOR
a	b	un b⊕{\ displaystyle \ oplus}
0	0	0
0	1	1
1	0	1
1	1	0

L'OR finora studiato va inteso nel modo seguente: "uno o l'altro o entrambi". Viene anche chiamato "OR inclusivo". L'OR esclusivo (o XOR per 'e X clusive OR' ) è inteso come: "uno o l'altro, ma non entrambi".

a XOR b a XOR⁡ b=a⊕b=(a+b).(a.b)¯=ab¯+a¯b{\ displaystyle a \ \ operatorname {XOR} \ b = a \ oplus b = (a + b). {\ overline {(ab)}} = a {\ bar {b}} + {\ bar {a}} b}

Possiamo anche definirlo con un modulo su una somma ordinaria:

a XOR⁡ b=(a+b) modalità 2{\ displaystyle a \ \ nomeoperatore {XOR} \ b = (a + b) \ {\ bmod {\}} 2}

L'"o esclusivo" è talvolta indicato dal segno aritmetico ( diverso da ). Funzionalmente, usa anche un + circondato: . ≠{\ displaystyle \ neq}a⊕b{\ displaystyle a \ oplus b}

Proprietà - Qualsiasi tabella di verità, qualsiasi funzione logica, può essere descritta utilizzando la costante 1 e le due operazioni: disgiunzione esclusiva e congiunzione, perché:a¯=a⊕ 1{\ displaystyle {\ bar {a}} = a \ oplus \ 1}, e a+b=a⊕ b⊕ a⋅b{\ displaystyle a + b = a \ oplus \ b \ oplus \ a \ cdot b}

Equivalenza

Tabella della verità EQV
a	b	un b⇔{\ displaystyle \ Leftrightarrow}
0	0	1
0	1	0
1	0	0
1	1	1

L' equivalenza (denotata EQV o XNOR) è vera se i due ingressi hanno lo stesso valore e falsa altrimenti. È la negazione dell'"o esclusivo".

L' equivalenza si può scrivere a EQV⁡ b=a⊙b=a⊕b¯=ab¯+a¯b¯=(ab)+(a¯⋅b¯){\ displaystyle a \ \ operatorname {EQV} \ b = a \ odot b = {\ overline {a \ oplus b}} = {\ overline {a {\ overline {b}} + {\ overline {a}} b }} = (ab) + ({\ overline {a}} \ cdot {\ overline {b}})}

L'equivalenza è spesso indicata dal segno . Si può anche notare “==” in alcuni linguaggi (C, C++, PHP…) e “⊙” in elettronica. ⇔{\ displaystyle \ Leftrightarrow}

coinvolgimento

Tabella della verità IMP
a	b	un b⇒{\ displaystyle \ Freccia destra}
0	0	1
0	1	1
1	0	0
1	1	1

L' implicazione (nota IMP ) è scritta come segue a IMP⁡ b=a¯+b{\ displaystyle a \ \ nomeoperatore {IMP} \ b = {\ overline {a}} + b}

Questa operazione non è commutativa . a è una condizione sufficiente per b, che è una condizione necessaria per a.

Ma

a IMP⁡ b=b¯ IMP⁡ a¯{\ displaystyle a \ \ operatorname {IMP} \ b = {\ overline {b}} \ \ operatorname {IMP} \ {\ overline {a}}}

Disegno :

Dalla dichiarazione “SE vivo in Francia (metropolitana), ALLORA vivo in Europa. » , Possiamo dedurre « SE non vivo in Europa, ALLORA non vivo in Francia. » Ma non « SE non vivo in Francia, ALLORA non vivo in Europa. » Perché posso vivere in Europa altrove che in Francia, senza contraddire l'affermazione iniziale.

Inibizione

INH tabella di verità
a	b	a.b¯{\ displaystyle a. {\ overline {b}}}
0	0	0
0	1	0
1	0	1
1	1	0

L' inibizione (denotata INH ) è composta come segue a INH⁡ b=a.b¯{\ displaystyle a \ \ operatorname {INH} \ b = a. {\ overline {b}}}

Se a è VERO, l'espressione è VERA, TRANNE se b è VERO.

Questa operazione non è commutativa.

Esempio di funzioni logiche con tre o quattro variabili

Funzione logica a tre variabili

Tavolo della verità da sganciare
a	b	vs	d
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

Legalità Rispondi = (Squillo E Decisione di rispondere) OPPURE Decisione di chiamare traduce la seguente situazione pratica: Alziamo un telefono quando decidiamo di chiamare qualcuno o quando il telefono squilla e decidiamo di rispondere .

È composto da tre variabili:

• a = "Suoneria"
• b = "Decisione di rispondere"
• c = "Decisione di chiamare"

la variabile d = "Pick up" è una funzione logica delle 3 precedenti e si può scrivere d = ab + c

La tabella di verità di questa funzione d è quindi la seguente (a destra):

Tavola della verità di stallo2
a	b	vs	d2
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

La tabella indica una situazione assurda: quando decidi di chiamare qualcuno e il telefono squilla senza che tu voglia rispondere, risponderesti comunque. Una modifica della tabella al contrario correggerebbe questa assurdità. Questa tabella corrisponde ad una funzione logica Pick up d2 o d2 che può essere determinata e semplificata da . d2=a¯.vs+a.b{\ displaystyle d2 = {\ bar {a}}. c + ab}

Funzione logica a quattro variabili

Un bravo studente si chiede se sia saggio uscire una sera. Deve decidere in base a quattro variabili:

• a = ha abbastanza soldi
• b = ha finito i compiti
• c = il trasporto pubblico è in sciopero
• d = l'auto di suo padre è disponibile

Questo studente potrà partire se:

• ha abbastanza soldi, a = vero
• ha finito i compiti, quindi b = vero
• il trasporto pubblico non è in sciopero, quindi c = falso
• o se l'auto di suo padre è disponibile, quindi d = true

L'espressione logica per uscire in base allo stato delle variabili a, b, c e d può essere quindi scritta come segue:Esci =a.b.(vs¯+d){\ displaystyle ab ({\ bar {c}} + d)}

Fattorizzare un'espressione

È possibile determinare una funzione logica

• o come espressione che coinvolge le tre operazioni ( , , )+{\ stile di visualizzazione + \,}⋅{\ displaystyle \ cdot \,}¯{\ displaystyle {\ bar {}} \,}
• o nella forma della sua tavola di verità. In questo caso sarà sempre possibile eseguire un'espansione per scrivere questa funzione come somma di prodotti .

Esempio: nell'esempio di "Pick up2", la lettura della tabella mostra che è uguale a quando o o o .d2{\ stile di visualizzazione d2}1{\ stile di visualizzazione 1}(a,b,vs)=(0,0,1){\ stile di visualizzazione (a, b, c) = (0,0,1)}(0,1,1){\ stile di visualizzazione (0,1,1)}(1,1,0){\ stile di visualizzazione (1,1,0)}(1,1,1){\ stile di visualizzazione (1,1,1)}Questo rende possibile definire d2 da d2=a¯.b¯.vs+a¯.b.vs+a.b.vs¯+a.b.vs{\ displaystyle d2 = {\ bar {a}}. {\ bar {b}}. c + {\ bar {a}}. b.c + ab {\ bar {c}} + abc}

È possibile trovare un'espressione che minimizzi il numero di termini e il numero di lettere in ciascun termine. Questo è l'obiettivo di alcune tecniche come il metodo Quine-McCluskey , i diagrammi di Karnaugh , il metodo del consenso , la doppia polarizzazione...

Esempio (continua): la somma precedente può essere ridotta fattorizzando i primi due termini per e fattorizzando gli ultimi due termini pera¯.vs{\ displaystyle {\ bar {a}}. c}a.b{\ stile di visualizzazione ab \,}d2=a¯.vs+a.b{\ displaystyle d2 = {\ bar {a}}. c + ab}

albero delle espressioni

Le espressioni logiche sono spesso rappresentate in informatica come una struttura ad albero .

Vari sottoalberi (o rami) sono attaccati ad un primo vertice (radice). I vertici senza uscita sono chiamati foglie.

Ogni vertice interno corrisponde a un selettore booleano “se allora altrimenti  ”, che riduce una domanda a due sotto-domande più semplici, eventualmente ridotte a 1/vero o 0/falso. S(X,sì,z)={\ stile di visualizzazione S (x, y, z) =}X{\ stile di visualizzazione x}sì{\ stile di visualizzazione y}z{\ stile di visualizzazione z}X{\ stile di visualizzazione x}

La valutazione di una funzione f dipendente da una variabile q scelta per la prima domanda è quindi , che porta a due espressioni indipendenti di . f=S(q,f(q=1),f(q=0)){\ displaystyle f = S (q, f ​​​​(q = 1), f (q = 0))}q{\ stile di visualizzazione q}

O  ; possiamo scriveref=a.b+a.d.f+vs.d+e.f{\ displaystyle f = a.b + adf + c.d + ef}f=S(a,f(a=1),f(a=0))=S(a,b+vs.d+d.f+e.f,vs.d+e.f)=S(a,S(b,1,d.f+vs.d+e.f),S(vs,d+e.f,e.f))...{\ displaystyle f = S (a, f (a = 1), f (a = 0)) = S (a, b + c.d + d.f + ef, c.d + ef) = S (a , S (b, 1 , df + cd + ef), S (c, d + ef, ef)) \ punti}

Gli alberi dipendono dall'espressione e dall'ordine delle domande, per la stessa espressione alcuni questionari saranno più semplici di altri.

Note e riferimenti

Appendici

Bibliografia

• [Kuntzmann 1968] J. Kuntzmann, Algebra di Boole , Parigi, Dunod ,1968.
• [Picard 1965] Claude François Picard , Teoria dei questionari , Parigi, Gauthier-Villars ,1965.
• [Permingeat 1988] N. Permingeat, Algebra booleana: Teoria, metodi di calcolo, applicazioni, con esercizi , Paris, Dunod ,1988.

Articoli Correlati

• Funzione logica
• Tavolo Karnaughugh
• Calcolo delle proposte
• Sistema di numerazione
• Elettronica digitale
• neurone formale
• George boole
• Operazione bit a bit
• Teorema del consenso
• Elenco di argomenti relativi all'algebra booleana
• Tavolo della verità

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">