stan.author
di stan.author
(0 punti)
5' di lettura

Formulazione

Le leggi di De Morgan sono due importanti teoremi di Logica proposizionale attraverso i quali possibile trasformare la congiunzione nella disgiunzione e viceversa. Esse sono date, nella versione pi semplice possibile, dalle formule seguenti:

Prima legge di De Morgan: Siano

[math]p[/math]
e
[math]q[/math]
due proposizioni. Allora
[math] \overline{p\wedge q}\leftrightarrow\overline{p}\vee\overline{q}[/math]
.

Seconda legge di De Morgan: Siano

[math]p[/math]
e
[math]q[/math]
due proposizioni.
Allora
[math] \overline{p\vee q}\leftrightarrow\overline{p}\wedge\overline{q}[/math]
.

Osservazione 1: Le leggi di De Morgan dicono, in buona sostanza, che la negazione della congiunzione è la disgiunzione, e viceversa. Naturalmente questo è solo un modo intuitivo di esprimere le precedenti formule, in quanto in Logica proposizionale non ha alcun senso negare un operatore.

Dimostrazioni

A titolo d'esempio, dimostreremo la prima delle due leggi di De Morgan nel solito modo delle tavole di verità, e poi faremo vedere come la seconda di esse possa essere ricavata dalla prima adoperando le proprietà elementari degli operatori che ci sono già note.

Dimostrazione della prima legge di De Morgan: Siano

[math]p[/math]
e
[math]q[/math]
due proposizioni qualsiasi; costruiamo come al solito la tabella di verità dell'espressione logica da dimostrare, avendo cura di assegnare alle proposizioni date tutte e
[math]2^2=4[/math]
le interpretazioni possibili:

Calcoliamo allo stesso tempo la congiunzione della terza colonna e le due negazioni delle colonne numero sei e nove:

Quindi, calcoliamo la negazione della prima colonna e la disgiunzione dell'ottava, e concludiamo infine il calcolo trovando i valori di verità relativi alla doppia implicazione:

Poiché la formula una tautologia, essa verificata in tutte le interpretazioni ed dunque una legge logica, proprio come volevamo dimostrare.

Dimostrazione della seconda legge di De Morgan: Siano

[math]p[/math]
e
[math]q[/math]
due proposizioni qualsiasi, e consideriamo le loro rispettive negazioni
[math] \overline{p} [/math]
e
[math] \overline{q}[/math]
. Dal momento che anche queste ultime due sono a tutti gli effetti delle proposizioni logiche, per esse vale la prima legge di De Morgan. Possiamo quindi a buon diritto scrivere

[math] \displaystyle \overline{(;\overline{p}\wedge\overline{q};)}\leftrightarrow(;\overline{\overline{p}}\vee\overline{\overline{q}};)
[/math]

Se queste espressione logica è, come è, una tautologia, allora i due termini separati dalla doppia implicazione hanno gli stessi valori di verità in tutte le interpretazioni. Se neghiamo entrambi i termini, i loro valori di verità risulteranno tutti invertiti, e quindi ancora uguali tra di loro. Anche la seguente formula è perciò una tautologia:

[math] \overline{\overline{(;\overline{p}\wedge\overline{q};)}}\leftrightarrow\overline{(;\overline{\overline{p}}\vee\overline{\overline{q}};)}
[/math]

A questo punto ricordiamo che due negazioni applicate in sequenza ad una proposizione equivalgono alla proposizione stessa non negata. Ne consegue che

[math] \overline{\overline{p}} \leftrightarrow p[/math]
,(;)
[math] \overline{\overline{q}}\leftrightarrow q[/math]
e
[math]\overline{\overline{(\overline{p}\wedge\overline{q})}}\leftrightarrow\overline{p}\wedge\overline{q}[/math]
, cosicché, effettuando le tre sostituzioni nella formula precedente,

[math] \overline{p}\wedge\overline{q}\leftrightarrow\overline{p\vee q}[/math]

Ulteriori osservazioni

Osservazione 2: Supponiamo di avere
[math]n[/math]
proposizioni
[math]p_1, p_2, ..., p_n[/math]
. Le leggi di De Morgan, in virtù delle dimostrate proprietà di associatività della congiunzione e della disgiunzione, possono essere scritte più in generale come segue:

[math]
\begin{array}{cc}
\displaystyle\overline{\bigwedge_{i=1}^n p_{i}}\leftrightarrow\displaystyle\bigvee_{i=1}^n\overline{p_{i}}, & \displaystyle\overline{\bigvee_{i=1}^n p_{i}}\leftrightarrow\displaystyle\bigwedge_{i=1}^n\overline{p_{i}}
\end{array}
[/math]

Osservazione 3: Le leggi De Morgan si estendono anc he alla Teoria degli Insiemi. Siano

[math]A[/math]
e
[math]B[/math]
due insiemi dati, e sia (complement) loperazione di complemento di un insieme rispetto a un determinato insieme
[math]U[/math]
tale che
[math]A\cup Bsubset U[/math]
; allora valgono le due formule

[math]
\begin{array}{cc}
\displaystyle\complement(A\cap B)=\complement A\cup\complement B, &
\displaystyle\complement(A\cup B)=\complement A\cap\complement B
\end{array}
[/math]

Ci indica che la validità delle leggi di De Morgan non dipende dal fatto che si stia parlando di proposizioni logiche o di insiemi, ma solo dalla struttura in cui tutti questi vari enti sono organizzati.

Vuoi approfondire Algebra – Esercizi e Appunti di Algebra con un insegnante esperto?
Trovalo su Ripetizioni.it