Teoremi di Base dell'Algebra Booleana

Concetti Chiave

I teoremi dell'algebra booleana sono relazioni fondamentali che possono essere utilizzate per semplificare espressioni booleane.
I teoremi possono essere dimostrati utilizzando tavole di verità, che verificano se entrambi i lati di una relazione producono gli stessi risultati per tutte le combinazioni delle variabili coinvolte.
Il principio di dualità stabilisce che ogni espressione algebrica deducibile rimane valida se gli operatori e gli elementi identità sono scambiati.
I teoremi di base dell'algebra booleana includono idempotenza, annullamento, involuzione, proprietà commutativa, proprietà associativa, proprietà distributiva, teorema di DeMorgan e teorema di assorbimento.

Principio di Dualità

Nella lezione precedente, i postulati di Huntington sono stati elencati in coppie e designati in due parti.

Una parte può essere ottenuta dall'altra se gli operatori binari e gli elementi identità sono scambiati. Questa importante proprietà dell'algebra booleana è chiamata principio di dualità e stabilisce che ogni espressione algebrica deducibile dai postulati dell'algebra booleana rimane valida se gli operatori e gli elementi identità sono scambiati.

In un'algebra booleana a due valori, gli elementi identità e gli elementi dell'insieme $B$ sono gli stessi: 1 e 0. Il principio di dualità ha molte applicazioni. Se si desidera il duale di un'espressione algebrica, semplicemente scambiamo gli operatori OR e AND e sostituiamo gli 1 con 0 e gli 0 con 1.

Ad esempio, se si considera l'espressione algebrica:

$x + y = 1$ , il suo duale è $xy = 0$ .

Teoremi di Base dell'Algebra Booleana

La Tabella che segue elenca sei teoremi dell'algebra booleana e quattro dei suoi postulati. La notazione è semplificata omettendo l'operatore binario ogni volta che ciò non porta a confusione. I teoremi e i postulati elencati sono le relazioni più basilari nell'algebra booleana. I teoremi, come i postulati, sono elencati in coppie; ogni relazione è il duale di quella con cui è accoppiata. I postulati sono assiomi basilari della struttura algebrica e non necessitano di dimostrazione. I teoremi devono essere dimostrati dai postulati. Le dimostrazioni dei teoremi con una variabile sono presentate di seguito. A destra è elencato il numero del postulato, che giustifica quel particolare passaggio della dimostrazione.

**Tabella 1:** Postulati e Teoremi dell'Algebra Booleana.
Enunciato	Versione OR	Versione AND
Postulato 2	$x + 0 = x$	$x \cdot 1 = x$
Postulato 5	$x + x' = 1$	$x \cdot x' = 0$
Teorema 1, idempotenza	$x + x = x$	$x \cdot x = x$
Teorema 2, annullamento	$x + 1 = 1$	$x \cdot 0 = 0$
Teorema 3, involuzione	$(x')' = x$
Postulato 3, proprietà commutativa	$x + y = y + x$	$xy = yx$
Teorema 4, proprietà associativa	$x + (y + z) = (x + y) + z$	$x(yz) = (xy)z$
Postulato 4, proprietà distributiva	$x(y + z) = xy + xz$	$x + yz = (x + y)(x + z)$
Teorema 5, Teorema di DeMorgan	$(x + y)' = x'y'$	$(xy)' = x' + y'$
Teorema 6, Teorema di Assorbimento	$x + xy = x$	$x(x + y) = x$

Teorema 1: Idempotenza

Definizione

Teorema di Idempotenza

Il teorema di idempotenza stabilisce se ad un elemento $x$ viene applicata l'operazione OR o AND con se stesso, il risultato è $x$ . In altre parole, l'operazione OR o AND di un elemento con se stesso non cambia il valore dell'elemento:

x + x = x

x \cdot x = x

Proviamo a dimostrare i due casi:

Dimostrazione

Dimostrazione del Teorema di Idempotenza: caso OR

Prendiamo l'espressione $x + x$ e applichiamo il postulato 2:

x + x = (x + x) \cdot 1

Successivamente, applichiamo il postulato 5:

x + x = (x + x)(x + x')

Poi, applichiamo il postulato 4:

x + xx'

Successivamente, applichiamo il postulato 5:

x + 0 = x

Quindi, abbiamo dimostrato che $x + x = x$ .

Dimostrazione

Dimostrazione del Teorema di Idempotenza: caso AND

Prendiamo l'espressione $x \cdot x$ e applichiamo il postulato 2:

x \cdot x = (x \cdot x) + 0

Successivamente, applichiamo il postulato 5:

x \cdot x = (x \cdot x)(x + x')

Poi, applichiamo il postulato 4:

x \cdot (x + x') = x \cdot 1

Successivamente, applichiamo il postulato 2:

x \cdot 1 = x

Abbiamo dimostrato che $x \cdot x = x$ .

Si noti che il teorema in versione AND è il duale del teorema in versione OR e che ogni passaggio della dimostrazione nella parte AND è il duale della sua controparte nella parte OR. Qualsiasi teorema duale può essere derivato allo stesso modo dalla dimostrazione del suo teorema corrispondente.

Teorema 2: Annullamento

Definizione

Teorema di Annullamento

Il teorema di annullamento stabilisce che se ad un elemento $x$ viene applicata l'operazione OR con 1, il risultato è 1, e se viene applicata l'operazione AND con 0, il risultato è 0:

x + 1 = 1

x \cdot 0 = 0

Dimostrazione

Dimostrazione del Teorema di Annullamento: caso OR

Prendiamo l'espressione $x + 1$ e applichiamo il postulato 2:

x + 1 = (x + 1) \cdot 1

Successivamente, applichiamo il postulato 5:

(x + 1) \cdot 1 = (x + 1)(x + x')

Poi, applichiamo il postulato 4:

(x + 1)(x + x') = x + x' \cdot 1

Successivamente, applichiamo il postulato 2:

x + x' \cdot 1 = x + x'

Quindi applichiamo il postulato 5:

x + x' = 1

Abbiamo dimostrato che $x + 1 = 1$ .

La versione AND del teorema di annullamento è il duale della versione OR. La dimostrazione segue lo stesso schema, ma con l'operatore AND e l'elemento identità 0:

x \cdot 0 = 0

Teorema 3: Involuzione

Definizione

Teorema di Involuzione

Il teorema di involuzione stabilisce che se ad un elemento $x$ viene applicata l'operazione di complemento due volte, il risultato è l'elemento stesso:

(x')' = x

Dimostrazione

Dimostrazione del Teorema di Involuzione

Dal postulato 5, abbiamo che:

x + x' = 1

x \cdot x' = 0

che insieme definiscono il complemento di x.

Il complemento di $x'$ è $x$ ed è anche $\left(x'\right)'$ . Pertanto, poiché il complemento è unico, abbiamo $\left(x'\right)' = x$ .

Teorema 6: Assorbimento

I teoremi che coinvolgono due o tre variabili possono essere dimostrati algebricamente dai postulati e dai teoremi che sono già stati dimostrati. Prendiamo, per esempio, il teorema di assorbimento:

Definizione

Teorema di Assorbimento

Il teorema di assorbimento stabilisce che se ad un elemento $x$ viene applicata l'operazione OR con il prodotto di $x$ e un altro elemento $y$ , il risultato è $x$ . In altre parole, l'operazione OR tra un elemento e il prodotto di quell'elemento con un altro elemento assorbe l'altro elemento:

x + xy = x

Analogo per la versione AND:

x(x + y) = x

Dimostrazione

Dimostrazione del Teorema di Assorbimento: caso OR

Prendiamo l'espressione $x + xy$ e applichiamo il postulato 2:

x + xy = x \cdot 1 + xy

Successivamente, applichiamo il postulato 4:

x \cdot 1 + xy = x(1 + y)

Poi, applichiamo il postulato 3:

x(1 + y) = x(y + 1)

Successivamente, applichiamo il teorema 2 (annullamento):

x(y + 1) = x \cdot 1

Infine, applichiamo il postulato 2:

x \cdot 1 = x

Quindi, abbiamo dimostrato che $x + xy = x$ .

La versione AND del teorema di assorbimento è il duale della versione OR. La dimostrazione segue lo stesso schema, ma con l'operatore AND e l'elemento identità 0:

x(x + y) = x

Dimostrazione dei Teoremi con Tavole di Verità

I teoremi dell'algebra booleana possono essere dimostrati per mezzo di tavole di verità. Nelle tavole di verità, entrambi i lati della relazione sono controllati per vedere se producono risultati identici per tutte le possibili combinazioni delle variabili coinvolte. La seguente tavola di verità verifica il primo teorema di assorbimento:

**Tabella 2:** Dimostrazione del primo teorema di assorbimento con tavola di verità.
$x$	$y$	$xy$	$x + xy$
0	0	0	0
0	1	0	0
1	0	0	1
1	1	1	1

Le dimostrazioni algebriche della legge associativa e del teorema di DeMorgan sono lunghe e non saranno mostrate qui. Tuttavia, la loro validità è facilmente mostrata con tavole di verità. Per esempio, la tavola di verità per il primo teorema di DeMorgan:

(x + y)' = x'y'

è la seguente:

**Tabella 3:** Dimostrazione del primo teorema di DeMorgan con tavola di verità.
$x$	$y$	$x + y$	$(x + y)'$	$x'$	$y'$	$x'y'$
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

La tavola di verità mostra che i risultati di $(x + y)'$ e $x'y'$ sono identici per tutte le combinazioni di $x$ e $y$ . Pertanto, il teorema è dimostrato.

Precedenza degli Operatori

La precedenza degli operatori per valutare le espressioni booleane è:

parentesi,
NOT,
AND, e
OR.

In altre parole, le espressioni dentro le parentesi devono essere valutate prima di tutte le altre operazioni. La prossima operazione che ha precedenza è il complemento, e poi segue l'AND e, infine, l'OR.

Come esempio, consideriamo la tavola di verità per uno dei teoremi di DeMorgan. Il lato sinistro dell'espressione è:

(x + y)'

Pertanto, l'espressione dentro le parentesi è valutata prima e il risultato viene poi complementato.

Il lato destro dell'espressione è $x'y'$ , quindi il complemento di $x$ e il complemento di $y$ sono entrambi valutati prima e il risultato viene poi sottoposto all'operazione AND. Si noti che nell'aritmetica ordinaria, la stessa precedenza vale (eccetto per il complemento) quando la moltiplicazione e l'addizione sono sostituite rispettivamente da AND e OR.

Esempio 1

Usando i teoremi di base e i postulati dell'algebra booleana, semplificare la seguente espressione booleana:

F = x'y'z + xyz + x'yz + xy'z.

Vediamo come si può semplificare questa espressione passo dopo passo:

Per prima cosa, sfruttando la proprietà distributiva, possiamo riscrivere l'espressione come:

$F = z(x'y' + xy) + z(xy' + x'y).$
Sfruttando il postulato 5, che ci dice che $x + x' = 1$ , possiamo semplificare ulteriormente.

Infatti $x'y' + xy$ vale 1 in quanto $xy$ e $x'y'$ sono complementari.

Allo stesso modo, $xy' + x'y$ vale 1.

Quindi, possiamo riscrivere l'espressione come:

$F = z \cdot 1 + z \cdot 1.$
Poi, sfruttiamo il postulato 2, che ci dice che $x \cdot 1 = x$ :

$F = z + z.$
Infine, applicando il teorema di idempotenza, che ci dice che $x + x = x$ , otteniamo:

$F = z.$

Quindi, l'espressione booleana semplificata è:

F = z.

Esempio 2

Realizzare la tavola di verità per l'espressione booleana:

F = x'y'z.

Il risultato è riportato nella seguente tabella:

**Tabella 4:** Tabella di verità per l'espressione booleana F = x'y'z.
$x$	$y$	$z$	$F$
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	0
1	1	1	0