Algebre booleane e progetto logico dei calcolatori digitali/Algebra delle classi - Algebra della logica

Insiemi

Introduciamo il concetto di insieme mediante esempi.

L'insieme degli italiani, l'insieme dei numeri interi, ecc. Gli enti che fanno parte di un insieme vengono chiamati elementi.

Per scrivere che un elemento X appartiene ad un insieme A, si usa la notazione:

$X\in A$

Inversamente, se X non appartiene ad A si scriverà:

$X\notin A$

Inoltre, per rappresentare un insieme, si utilizzeranno delle parentesi, all'interno delle quali si troveranno gli elementi stessi, oppure il simbolo dell'elemento generale con l'enuncuato della proprietà comune a tutti gli elementi dell'insieme.

Così se R è l'insieme delle radici della equazione.

$x^{3}-6x^{2}+11x-6=0$

si avrà:

R={1,2,3}

oppure:

R={x|x³-6x²+11x-6=0}

e questa seconda notazione si leggerà: R è l'insieme degli elementi x tali che si abbia:

$x^{3}-6x^{2}+11x-6=0$

Si dice che due insiemi, A e B, sono uguali (0 identici)se essi sono formati dagli stessi elementi: e si scrive A=B.

In altri termini, ogni elemento x appartenente ad A appartiene a B e viceversa.

Esempio 1. gli insiemi:

${\begin{cases}A=\{x\ |\ e\ un\ numero\ pari\}\\B=2\end{cases}}$

dove {x} è l'insieme costituito dal solo elemento 2, sono uguali.

Si dice che un insieme A è un sottoinsieme di un insieme Bse ogni elemento di A appartiene a B (si dice anche che A è incluso in B o che A è una parte di B, o infine, che B contiene A) e si utilizzano le notazioni:

$1)\qquad \qquad A\subseteq B$

$2)\qquad \qquad B\supseteq A$

Nella definizione data, come nelle notazioni 1) e 2), non si esclude il caso in Dato un insieme A come sottoinsieme di un insieme U, si chiama complemento di A rispetto ad U l'insieme dei punti di U che non appartengono ad A.

Si scrive:

$U-A\qquad \qquad oppure\qquad C_{u}(A)$

Si può scrivere, utilizzando le notazioni di cui sopra:

$U-A=\{x|\ x\in U\qquad e\qquad x\notin A\}$

Esempio 2. Se U è l'insieme dei numeri reali e A quello dei numeri razionali, U-A è l'insieme dei numeri irrazionali.

L'insieme U-A è un complemento relativo. Quando non vi è ambiguità sull'insieme U da considerare, si può definire un complemento assoluto come l'insieme dei punti che non appartengono ad A e lo si denota con la espressione:

${\bar {A}}=\{x\ |\ x\ \notin A\}$

Si noti che l'operazione con la quale si ottiene ${\bar {A}}$ da A, cioè la complementazione, è una operazione ad un solo termine.

Definiamo ora operazioni a 2 termini (binarie).

a) L'unione di due termini A e B è l'insieme dei punti che appartengono ad A o a B oppure ad entrambi contemporaneamente.

L'unione di A e B è rappresentata:

$A\cup B=\{x\ |\ x\in A\quad oppure\quad x\in B\quad oppure\quad x\in A\quad e\quad x\in B\}$.

Così l'unione dell'insieme dei punti del segmento 0≤x≤1 e del segmento 0,5≤x≤1,5 è l'insieme dei punti del segmento 0≤x≤1,5.

b) L'intersezione di due insiemi A e B è l'insieme dei punti che appartengono contemporaneamente ad A ed a B e si rappresenta:

$A\cap B=\{x\ |\ x\in A\quad e\quad x\in B\}$.

Per esempio l'intersezione dei numeri primi e dell'insieme dei numeri pari è l'insieme {2}.

È comodo introdurre un insieme il quale non possiede alcun elemento: esso si chiama elemento vuoto e lo si rappresenta con il simbolo Φ.

Segue che l'uguaglianza

$A\cap B=\Phi$

significa che gli insiemi A' e B non hanno alcun punto in comune. Si dice anche che essi sono disgiunti. Analogamente è conveniente introdurre un insieme contenente tutti gli elementi possibili: insieme universale o universo (e lo si noterà con il simbolo U.I, ecc.).

Dato un insieme E, i suoi sottoinsiemi possono essere considerati come gli elementi dell'insieme potenza P(E) o 2^E (insieme delle parti di E costituito dai sottoinsiemi di E, inclusi l'insieme vuoto e quello improprio).

Esempio: $E=\{1,2,3\}$

$P(E)=\{\Phi ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

P(E) è dunque un insieme di insiemi dei suoi sottoinsiemi: sono particolarmente interessanti quelli chiamati ricoprenti di E o parti di E.

Dato un insieme E (appartenente all'insieme universale U), si chiama ricoprimento di E un insieme delle parti di E un insieme delle parti di E tale che E sia uguale alla loro unione.

Esempio. L'insieme dei numeri interi, dei numeri razionali, dei numeri irrazionali e dei numeri trascendenti, costituisce un ricoprimento dell'insieme dei numeri reali.

Un ricoprimento di E sia tale che due insiemi qualunque di esso siano disgiunti. Ogni punto di E si trova allora in un insieme della partizione, e uno solo.

Così l'insieme dei numeri razionali e dei numeri irrazionali, costituiscono una partizione dell'insieme dei reali.

Queste differenti definizioni possono ricevere una interpretazione grafica chiamata Diagrammi di Venn. L'insieme universale è rappresentato con un rettangolo e gli insiemi A, B ecc. sono rappresentati come cerchi.

Nelle figure seguenti si dà l'interpretazione delle diverse operazioni definite precedentemente:

Algebra delle classi

Si consideri un insieme I che starà a rappresentare, nel seguito, l'insieme universale. I differenti sottoinsiemi di I formano essi stessi un insieme, sul quale si possono definire le tre operazioni di: unione, intersezione e complementazione. L'insieme dei sottoinsiemi di I costituisce così un'algebra denominata algebra delle classi.

A partire dalle definizioni di insieme, sottoinsieme e delle 3 operazioni di cui sopra, si possono dimostrare diverse proprietà di questa algebra. Esse si possono giustificare con l'aiuto dei diagrammi di Venn, oppure con rigorose dimostrazioni, partendo dalle definizioni.

$E_{1})\qquad \qquad (A\cup B)\cup C=A\cup (B\cup C)$

È la proprietà detta dell'associatività dell'unione ∪.

$E_{2})\qquad \qquad (A\cap B)\cap C=A\cap (B\cap C)$

È la legge d'associatività dell'0perazione di intersezione.

$E_{3})\qquad \qquad A\cup B=B\cup A$

Essa è la legge di commutatività dell'operazione di unione ∪; risulta dalla definizione di A∪B: il risultato non dipende evidentemente dall'ordine dei due operandi A e B.

$E_{4})\qquad \qquad A\cap B=B\cap A$

Legge di commutatività dell'operazione d'intersezione.

$E_{5})\qquad \qquad A\cup \Phi =A$

Φ non contiene nessun elemento quindi la sua unione con l'insieme A non è altro che A stesso.

$E_{6})\qquad \qquad A\cap I=A$

Essendo A contenuto in I (per definizione), i punti comuni ad A e I sono tutti quelli di A.

$E_{7})\qquad \qquad A\cap (B\cup C)=(A\cap B)\cup (A\cap C)$

$E_{8})\qquad \qquad A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$

Legge di distributività dell'unione rispetto all'intersezione.

$E_{9})\qquad \qquad A\cap {\bar {A}}=\Phi$

Un insieme A ed il suo complementare ${\bar {A}}$ non hanno alcun punto in comune : essa è una conseguenza della definizione di ${\bar {A}}$

$E_{10})\qquad \qquad A\cup {\bar {A}}=I$

L'unione di un insieme A e del suo complementare ${\bar {A}}$ è sempre l'insieme universale. Esso è una conseguenza della definizione di ${\bar {A}}$. quindi il complementare ${\bar {A}}$ di A soddisfa alle due relazioni : E₉ e E₁₀.

Inversamente, se un insieme B soddisfa alle relazioni:

$E_{9}\quad A\cap B=\Phi \quad e\quad E_{10}\quad A\cup B=I$

Esso è il complemento di A; ossia:

$B={\bar {A}}$

Infatti, sia un elemento x∈B, la E'₉ afferma che x∉A e la E'₁₀ che x∈I.

Dunque x appartiene ad $I-A={\bar {A}}$, $x\in {\bar {A}}$. Dunque $B\subset {\bar {A}}$. Ma ogni elemento di A, d'altra parte, verifica E₉ ed E₁₀; dunque se $x\in {\bar {A}}$, $x\in B$; per cui ${\bar {A}}\subset B$.

Da cui ${\bar {A}}=B$. In altri termini, le due relazioni E'₉ e E'₁₀ hanno per soluzioni ${\bar {A}}$ e le si utilizzeranno, in pratica, per definire direttamente ${\bar {A}}$.

$E_{11})\qquad A\cup A=A$

Legge di idempotenza per la unione U.

$E_{12})\qquad A\cap A=A$

Legge di idempotenza per la intersezione ∩.

$E_{13})\qquad A\cup I=I$

$E_{14})\qquad A\cap \Phi =\Phi$

$E_{15})\qquad A\cup (A\cap B)=A$

Prima legge d'assorbimento.

L'intersezione E=A∩B è un sottoinsieme di A; l'ulteriore unione di E con A non può che dare A.

$E_{16})\qquad A\cap (A\cup B)=A$

Seconda legge di assorbimennto.

A è contenuto in E=A∪B, da cui A∩E=A.

$E_{17})\qquad A\cup ({\bar {A}}\cap B)=A\cup B$

$E_{18})\qquad A\cap A({\bar {A}}\cup B)=A\cap B$

$E_{19})\qquad {\overline {A\cup B}}={\bar {A}}\cap {\bar {B}}$

Primo teorema di Morgan per gli insiemi: esso si enuncia dicendo che il complementare della unione è uguale all'intersezione dei complementari.

Secondo teorema di De Morgan:

$E_{21})\qquad {\overline {A\cup B}}={\bar {A}}\cap {\bar {B}}$

Il complemento delle intersezioni è uguale all'unione dei complementari.

Algebra della logica

Proposizioni: valore logico delle proposizioni

Se si esamina il linguaggio di cui si fa uso ogni giorno, e più particolarmente quello che serve come mezzo per esprimere un ragionamento scientifico, se ne possono discernere degli elementi detti proposizioni: legandole tra di loro, si può costruire l'enunciato di un teorema, la dimostrazione di un teorema, una definizione, ecc..

Questa articolazione del linguaggio in proposizioni è, del resto, una delle caratteristiche fondamentali del linguaggio umano.

Così le espressioni:

1. "11 è un numero primo"
2. "il triangolo 'ABC è rattangolo"

costituiscono delle proposizioni.

Ciascuna di queste proposizioni, può essere esaminata sotto l'aspetto della sua verità o della sua falsità.

Per esempio: la proposizione 1) è vera mentre la 2) può essere esaminata con il criterio su accennato e deve essere possibile se essa è vera o falsa.

Nel seguito si studieranno le proposizioni e si supporrà che le proposizioni esaminate non possano essere che vere o false.

Operazioni sulle proposizioni

Continuando l'esame del linguaggio ordinario, si può mettere in evidenza tutta una classe di parole, o anche di espressioni più complesse, che però non sono proposizioni ma elementi di legame tra proposizioni: e, o, ma, oppure, "implica che", "equivale a dire che", ecc.. Nel linguaggio corrente, queste operazioni di legame delle proposizioni elementari, formando proposizioni più complesse, non sono prive di ambiguità.

Nondimeno, le nozioni di proposizione e di legami, forniscono lo spunto per un insieme di concetti matematici che, in questo caso, saranno dotati di una definizione rigorosa.

Prodotto logico: operazione AND

Consideriamo per esempio le due proposizioni:

"x è un numero primo"

"Il triangolo ABC è rettangolo"

Con l'aiuto della congiunzione "e" (AND) si può formare una nuova proposizione che si enuncerà: " x è un numero primo E il triangolo ABC è rettangolo".

Quando essa sarà vera?

Questa nuova proposizione sarà considerata come vera, quando le due proposizioni componenti sono vere tutte e due, e falsa in tutti gli altri casi. Ovviamente si sarebbe potuto considerare altre due proposizioni, ad esempio:

• "Roma è la capitale d'Italia"
• "Il clima italiano è mite"

e costruire in maniera analoga una proposizione nuova con la congiunzione "e"(AND).

Si vede dunque che l'operazione AND da una proposizione nuova, a partire da due proposizioni componenti, in una maniera caratterizzata essenzialmente dal modo in cui si determina se essa è falsa o vera, conoscendo la falsità o la verità delle componenti, ma, in fondo, indipendentemente dal senso e dalla natura delle proposizioni. Si può aòòora rappresentare ogni proposizione, con una variabile capace di prendere soltanto i due valori logici rappresentati von V (vero) e F (falso).

L'operazione di AND allora, tra due proposizioni generiche P e Q verrà definita dalla tavola AND.

Si definisce così una delle operazioni della logica matematica: essa viene indicata con il simbolo ∧ e si chiama operazione di AND o prodotto logico. Una tavola come quella a fianco prende il nome di tavola della Verità: essa descrive, per tutte le combinazioni possibili, il valore (vero o falso) della proposizione composta, in funzione dei valori delle proposizioni componenti.

Operazione di OR inclusivo (somma logica)

Si consideri la frase (nell'algebra ordinaria)

"il prodotto X Y è nullo se x=0, y≠0; oppure se x≠0, y=0; oppure x=0, y=0."

La proposizione (x=0) oppure (y=0) fornisce un esempio di una nuova operazione che si può definire rigorosamente mediante una tavola

Date due proposizioni P e Q si chiamerà "proposizione P OR Q" e si scriverà "P V Q", la proposizione composta definita dalla tavola affiancata.

L'operazione V, così definita, prende il nome di somma logica.

Negazione di una proposizione

A partire da una proposizione come "oggi piove", possiamo formulare una seconda proposizione "oggi non piove". È chiaro che se la prima è vera, la seconda è falsa e viceversa. Si può quindi definire l'operazione di negazione: la negazione di una proposizione P viene rappresentata con il simbolo ()P; ed è data dalla tavola affiancata. Conformemente all'uso generale, si preferisce rappresentare i due valori logici di una variabile, non con i simboli V ed F ma con i simboli 0 ed 1; si noti però che si tratta di una convenzione pratica alla quale l'aritmetica è completamente estranea. Tra le due convenzioni possibili si è scelta la seguente:

$V=1\qquad F=0$

È facile riscrivere la tavole precedenti con il nuovo simbolismo.

Oltre alle tre operazioni logiche fin qui studiate, possiamo, con lo stesso metodo di definizione, costruire 2⁴=16 tavole della verità di due variabili che definiscono altrettante operazioni o funzioni logiche:

Funzione OR esclusiva (F6)

È il nome dato alla funzione F6: si confrontino le due tavole della verità di P⊕Q e P v Q

Si noti che P ⊕ Q ha il valore 1 quando P e Q hanno valori logici differenti e 0 altrimenti.

Al contrario la proposizione P v Q assume il valore 1 anche per P=1 e Q=1

Esempio. Il prodotto delle variabili algebriche non nulle A e B è negativo se A oppure B sono negative.

Equivalenza P ↔ Q (F9)

Con l'operazione ⇔ si otterrà una nuova proposizione e si scriverà P ↔ Q; vera quando P e Q hanno lo stesso valore logico e falsa nel caso contrario: essa si chiama equivalenza di P e Q; oppure implicazione reciproca di P e Q.

Si noti come le due proposizioni P ↔ Q e P ⊕ Q sono l'una la negazione dell'altra. Il nome di implicazione di P ↔ Q trova giustificazione nella operazione seguente.

Implicazione (F11)

È la funzione P → Q. Essa traduce il senso, talvolta vago, della nozione di implicazione nel linguaggio ordinario: quando P è vero, anche Q è vero (se piove allora ci sono le nubi): quindi P → Q è vero se P=1 e Q=1.

Inoltre, quando P è falso, niente impedisce che Q assuma un valore arbitrario 1 o 0 e quindi P → Q è considerata vera nei due casi in cui P=0. In breve: Q non può essere falsa quando P è vera.

Il simbolo P → Q si legge: P implica Q oppure P è una condizione sufficiente per avere Q.

La funzione F13 rappresenta in maniera analoga la funzione Q → P. Si consideri la proposizione (P → Q)∧(Q → P): si può costruire la tabella della verità affiancata.

La colonna di destra è la stessa di quella della operazaione P ↔ Q ciò che giustifica il simbolo e il nome di implicazione reciproca della operazione ↔.

Funzione di Scheffer P/Q o incompatibilità (NAND)

È la funzione F7. La proposizione P/Q è falsa quando P e Q sono entrambi veri, e vera in tutti gli altri casi. Questo giustifica il nome di Incompatibilità di P e Q. Essa è anche uguale alla negazione della funzione F8.

Funzione di Peirce (funzione NOR) $P\downarrow Q$

È la funzione F1. La proposizione $P\downarrow Q$ è vera quando né P né Q sono vere. Essa è anche uguale a:

${\overline {P\vee Q}}$.

Tautologie e contraddizioni

Una proposizione composta che è falsa per tutti i valori logici possibili delle n proposizioni componenti, è una contraddizione.

Una proposizione composta che è vera per tutti i valori logici delle n proposizioni componenti, è una tautologia.

Esempio 1. Principio della doppia negazione (tautologia): ogni proposizione equivale alla negazione della sua negazione.

$P\leftrightarrow {\bar {\bar {P}}}$

Esempio 2. Principio d'identità: ogni proposizione implica se stessa.

Esempio 3. Principio del terzo escluso: ogni proposizione è vera o falsa.

$P\vee {\bar {P}}$

Esempio 4. $P\land {\bar {P}}$: contraddizione.

• Ogni proposizione non può essere contemporaneamente vera o falsa.
• Qualche proprietà delle funzioni AND, OR e negazione.
• Nel seguito compaiono un certo numero di identità algebriche che legano le tre operazioni AND, OR e negazione (∧, ∨, -).

Esse si presentano sotto forma di tautologie e di contraddizioni che figurano in certe identità.

$L_{1}$	$(P\vee Q)\vee R\leftrightarrow P\vee (Q\vee R)$	associativita dell'operazione OR
$L_{2}$	$(P\land Q)\land R\leftrightarrow P\land (Q\land R)$	associativita dell'operazione AND
$L_{3}$	$P\vee Q\leftrightarrow Q\vee P$	commutativita dell'operazione OR
$L_{4}$	$P\land Q\leftrightarrow Q\land P$	commutativita dell'operazione AND
$L_{5}$	$P\vee P$	tautologia
$L_{6}$	$P\land P$	contraddizione
$L_{7}$	$P\land (Q\vee R)\leftrightarrow (P\land Q)\vee (P\land R)$	distributiva di AND rispetto ad OR
$L_{8}$	$P\vee (Q\land R)\leftrightarrow (P\vee Q)\land (P\vee R)$	distributiva di OR rispetto ad AND
$L_{9}$	$\neg (P\land \neg P)$	principio di contraddizione
$L_{10}$	$P\vee \neg P$	principio del terzo escluso
$L_{11}$	$P\vee P\leftrightarrow P$	idempotenza diOR
$L_{15}$	$P\vee (P\land Q)\leftrightarrow P$	assorbimento
$L_{16}$	$P\land (P\vee Q)\leftrightarrow P$	assorbimento
$L_{17}$	$P\vee (\neg P\land Q)\leftrightarrow P\vee Q$
$L_{18}$	$P\land (\neg P\vee Q)\leftrightarrow P\land Q$
$L_{19}$	$\neg (P\vee Q)\leftrightarrow (\neg P\land \neg Q)$	teorema di Morgan
$L_{20}$	$\neg (P\land Q)\leftrightarrow (\neg P\vee \neg Q)$	teorema di Morgan

Esempi d'applicazione

Nullità di un prodotto algebrico ordinario

Nell'algebra ordinaria perché un prodotto m = a x b x c sia ≠ 0 è necessario e sufficiente che sia a ≠ 0, b ≠ 0, c ≠ 0.

Si ha dunque:

$(a\times b\times c\neq 0)\leftrightarrow (a\neq 0)\land (b\neq 0)\land (c\neq 0)$

Inversamente perché sia m = 0:

$(a\times b\times c=0)\leftrightarrow (a=0)\vee (b=0)\vee (c=0)$

Regole dei segni nell'algebra ordinaria

Si consideri il prodotto M = a x b

$a\ \neq 0\qquad \qquad b\ \neq 0$

La regola dei segni si scriverà:

$(a\times b>0)\leftrightarrow {[(a<0)\land (b<0)]\vee [(a>0)\land (b>0)]}$

$(a\times b>0)\leftrightarrow {[(a<0)\leftrightarrow {(b<0)}]}$

$(a\times b>0)\leftrightarrow {[(a>0)\leftrightarrow {(b<0)}]}$

Inversamente:

$(a\times b<0)\leftrightarrow {[(a<0)\oplus (b<0)]}$

$(a\times b<0)\leftrightarrow {[(a>0)\oplus (b>0)]}$

$(a\times b<0)\leftrightarrow {[(a<0)\leftrightarrow {(b>0)}]}$