Espressioni e funzioni booleane

L'algebra booleana è l'algebra della logica. Si occupa di variabili che possono avere due valori discreti, 0 (False) e 1 (True); e operazioni che hanno un significato logico. Il primo metodo di manipolazione della logica simbolica fu inventato da George Boole e successivamente divenne noto come Algebra booleana.

L'algebra booleana è diventata uno strumento indispensabile nell'informatica per la sua ampia applicabilità nella teoria della commutazione, nella costruzione di circuiti elettronici di base e nella progettazione di computer digitali.

Funzioni booleane

A Boolean functionè un tipo speciale di funzione matematica $ f: X ^ n \ freccia destra X $ di grado n, dove $ X = \ lbrace {0, 1} \ rbrace $ è un dominio booleano e n è un numero intero non negativo. Descrive il modo in cui derivare l'output booleano dagli input booleani.

Example- Sia, $ F (A, B) = A'B '$. Questa è una funzione di grado 2 dall'insieme di coppie ordinate di variabili booleane all'insieme $ \ lbrace {0, 1} \ rbrace $ dove $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ e $ F (1, 1) = 0 $

Espressioni booleane

A Boolean expressionproduce sempre un valore booleano. Un'espressione booleana è composta da una combinazione di costanti booleane (Vero o Falso), variabili booleane e connettivi logici. Ogni espressione booleana rappresenta una funzione booleana.

Example - $ AB'C $ è un'espressione booleana.

Identità booleane

Legge del doppio complemento

$ \ sim (\ sim A) = A $

Legge del complemento

$ A + \ sim A = 1 $ (modulo OR)

$ A. \ sim A = 0 $ (modulo AND)

Legge idempotente

$ A + A = A $ (modulo OR)

$ A. A = A $ (modulo AND)

Legge sull'identità

$ A + 0 = A $ (modulo OR)

$ A. 1 = A $ (modulo AND)

Legge sulle dominanze

$ A + 1 = 1 $ (modulo OR)

$ A. 0 = 0 $ (modulo AND)

Diritto commutativo

$ A + B = B + A $ (modulo OR)

$ A. B = B. A $ (modulo AND)

Diritto associativo

$ A + (B + C) = (A + B) + C $ (modulo OR)

$ A. (B. C) = (A. B). C $ (modulo AND)

Legge di assorbimento

$ A. (A + B) = A $

$ A + (A. B) = A $

Legge sulla semplificazione

$ A. (\ sim A + B) = A. B $

$ A + (\ sim A. B) = A + B $

Legge distributiva

$ A + (B. C) = (A + B). (A + C) $

$ A. (B + C) = (A. B) + (A. C) $

Legge di De-Morgan

$ \ sim (A. B) = \ sim A + \ sim B $

$ \ sim (A + B) = \ sim A. \ sim B $

Forme canoniche

Per un'espressione booleana esistono due tipi di forme canoniche:

• La forma della somma dei termini (SOM)
• Il prodotto di maxterms (POM) form

Il modulo Somma di Minterm (SOM) o Somma di prodotti (SOP)

Un minterm è un prodotto di tutte le variabili prese nella loro forma diretta o completata. Qualsiasi funzione booleana può essere espressa come somma dei suoi 1 minterm e l'inverso della funzione può essere espressa come una somma dei suoi 0 minterm. Quindi,

F (lista di variabili) = ∑ (lista di indici a 1 termine)

e

F '(lista di variabili) = ∑ (lista di indici a termine 0)

UN	B	C	Termine	Minterm
0	0	0	x'y'z '	m 0
0	0	1	x'y'z	m 1
0	1	0	x'yz '	m 2
0	1	1	x'yz	m 3
1	0	0	xy'z '	m 4
1	0	1	xy'z	m 5
1	1	0	xyz '	m 6
1	1	1	xyz	m 7

Example

Sia, $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $

Oppure $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $

Quindi,

$ F (x, y, z) = \ sum (0, 5, 6, 7) $

Ora troveremo il complemento di $ F (x, y, z) $

$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $

Oppure $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $

Quindi,

$ F '(x, y, z) = \ sum (3, 1, 2, 4) = \ sum (1, 2, 3, 4) $

Il modulo Product of Maxterms (POM) o Product of Sums (POS)

Un maxterm è l'aggiunta di tutte le variabili prese nella loro forma diretta o completata. Qualsiasi funzione booleana può essere espressa come un prodotto dei suoi 0-maxterms e l'inverso della funzione può essere espresso come un prodotto dei suoi 1-maxterms. Quindi,

F (lista di variabili) = $ \ pi $ (lista di indici 0-maxterm).

e

F '(lista di variabili) = $ \ pi $ (lista di indici 1-maxterm).

UN	B	C	Termine	Maxterm
0	0	0	x + y + z	M 0
0	0	1	x + y + z '	M 1
0	1	0	x + y '+ z	M 2
0	1	1	x + y '+ z'	M 3
1	0	0	x '+ y + z	M 4
1	0	1	x '+ y + z'	M 5
1	1	0	x '+ y' + z	M 6
1	1	1	x '+ y' + z '	M 7

Esempio

Sia $ F (x, y, z) = (x + y + z). (x + y + z '). (x + y '+ z). (x '+ y + z) $

Oppure $ F (x, y, z) = M_0. M_1. M_2. M_4 $

Quindi,

$ F (x, y, z) = \ pi (0, 1, 2, 4) $

$ F '' (x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y' + z). (x '+ y' + z ') $

Oppure $ F (x, y, z) = M_3. M_5. M_6. M_7 $

Quindi,

$ F '(x, y, z) = \ pi (3, 5, 6, 7) $

Porte logiche

Le funzioni booleane vengono implementate utilizzando porte logiche. Le seguenti sono le porte logiche:

NON Gate

Una porta NOT inverte un singolo bit di ingresso in un singolo bit di uscita.

UN	~ A
0	1
1	0

AND Gate

Una porta AND è una porta logica che fornisce un'uscita alta solo se tutti i suoi ingressi sono alti, altrimenti dà un'uscita bassa. Un punto (.) Viene utilizzato per mostrare l'operazione AND.

UN	B	AB
0	0	0
0	1	0
1	0	0
1	1	1

OR Gate

Una porta OR è una porta logica che fornisce un'uscita elevata se almeno uno degli ingressi è alto. Un segno più (+) viene utilizzato per mostrare l'operazione OR.

UN	B	A + B
0	0	0
0	1	1
1	0	1
1	1	1

Gate NAND

Una porta NAND è una porta logica che fornisce un'uscita bassa solo se tutti i suoi ingressi sono alti, altrimenti dà un'uscita alta.

UN	B	~ (AB)
0	0	1
0	1	1
1	0	1
1	1	0

NOR Gate

Una porta NOR è una porta logica che fornisce un'uscita alta se entrambi gli ingressi sono bassi, altrimenti dà un'uscita bassa.

UN	B	~ (A + B)
0	0	1
0	1	0
1	0	0
1	1	0

Porta XOR (OR esclusivo)

Una porta XOR è una porta logica che fornisce un output elevato se gli ingressi sono diversi, altrimenti fornisce un output basso.

UN	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Cancello X-NOR (NOR esclusivo)

Una porta EX-NOR è una porta logica che fornisce un output elevato se gli ingressi sono gli stessi, altrimenti fornisce un output basso.

UN	B	A X-NOR B
0	0	1
0	1	0
1	0	0
1	1	1