Leggi de Morgan

Spieghiamo quali sono le leggi di Morgan, le dimostriamo e mettiamo esempi

Figura 1.- Il matematico Augustus di Morgan (1806-1871) e le sue leggi di logica proposizionale. Fonte: f. Zapata.

Quali sono le leggi di De Morgan?

Le leggi di De Morgan sono due leggi logiche appartenenti alla logica proposizionale che furono formulate dal matematico inglese Augustus di Morgan (1806-1871). Stabiliscono quanto segue, rispetto a una proposta logica composta:

1. L'opposto di una congiunzione è equivalente alla disgiunzione che si forma con gli opposti o le negazioni delle proposte che compongono la congiunzione.
2. La negazione della disgiunzione può essere espressa come una congiunzione composta dagli opposti o dalle negazioni delle proposizioni coinvolte nella disgiunzione.

Nella notazione della logica proposizionale, le leggi di De Morgan sono espresse in modo compatto e più formale come questo:

1. ∼ (P ∧ Q) ⇔ ∼P ∨Q
2. ∼ (P ∨ Q) ⇔ ∼P ∧Q

Ciò che queste leggi esprimono è che, nella negazione della congiunzione o della disgiunzione, il risultato è equivalente a negare separatamente ciascuna delle proposizioni partecipanti e investire il connettore che le collega.

Per una migliore comprensione delle leggi di De Morgan, è necessario rivedere il significato delle proposizioni e dei simboli usati nella logica proposizionale, per vedere come si applicano queste leggi convenientemente.

Notazione logica

Lo strumento di base della logica proposizionale sono le proposizioni. Una proposta logica è un'affermazione che ammette a valore reale, Che sia vero o falso, ma non entrambi allo stesso tempo. In questo non è consentita alcuna ambiguità, cioè non ci possono essere dubbi.

Una proposta è indicata con un minuscolo, come nei seguenti esempi:

• D: Città del Messico è la capitale del Messico (True).
• D: aggiungendo 2 e 3, 4 (falso).
• A: Tutti i mammiferi sono animali terrestri (falsi).

Può servirti: Eptagon

Esistono anche proposizioni più complesse, che sono strutturate attraverso l'uso di proposizioni semplici, come queste:

• D: Carlos andrà al cinema se non piove.
• D: Ana è un chimico o un biologo marino.
• A: Juan andrà a cena o Pedro vedrà il gioco in televisione.

Connettori logici

I connettori logici sono simboli usati per collegare proposizioni semplici e quindi costruire proposizioni più complesse. Nella logica proposizionale ognuno di essi ha un significato particolare.

I connettori più usati sono congiunzioni, disgiunzione, disgiunzione esclusiva, negazione, condizionalità e bi-condizionalità.

Congiunzione

La congiunzione è indicata con una lettera "V" invertita. Una proposta composita attraverso una congiunzione è simboleggiata P ∧ Q, come segue:

• P ∧ Q: Città del Messico è la capitale del Messico ed è in Nord America.

È facile identificare qui che P è "Città del Messico è la capitale del Messico" e Q è "è in Nord America".

Disgiunzione

Si distinguono due tipi di disgiunzione: i deboli ed esclusivi. UN debole disgiunzione È simboleggiato da ∨ e in notazione logica sarebbe p ∨ q. Esempio di questo tipo di disgiunzione è:

• P ∨ Q: Juan è un calciatore o Juan è un tennista.

Invece, il disgiunzione esclusiva È simboleggiato dal segno ⊻ e implica che una delle proposizioni deve essere esclusa, ad esempio:

P ⊻ Q: Alicia ha 20 anni o Alicia ha 22 anni.

La differenza tra i due tipi è chiara, nella disgiunzione esclusiva, una delle proposizioni è esclusa, poiché se Alicia ha 20 anni, non può avere 22 e viceversa. D'altra parte, nella debole disgiunzione, Juan può essere un calciatore e un tennista allo stesso tempo.

Rifiuto

Mettendo il simbolo ∼ una proposta, questo viene negato, come in:

• D: ∼ (Veracruz è la capitale del Messico).

Questo viene letto come "Veracruz non è la capitale del Messico". Altri modi per esprimere una negazione, a parte "no", sono attraverso frasi come "è falso", "è una bugia che" e "non è vero che".

Può servirti: interpolazione lineare

Condizionalità

Sono proposizioni composite che di solito usano le parole "sì" e "allora ..." per collegare due proposizioni in cui esiste una condizionalità o coinvolgimento. La parte della proposizione che viene scritta immediatamente dopo il "sì" è il antecedente onda ipotesi della proposta e ciò che è dopo il termine "allora" è il conclusione O conseguente.

Il simbolo usato per la condizionalità è la freccia da sinistra a destra "→", quindi una condizionalità tra due proposizioni è rappresentata come p → q, che può essere letta come "se p, allora q". Per esempio:

P → Q: Se piove durante il pomeriggio, non giocherò a tennis.

Bi-condizionalità

In questo tipo di proposizione la frase "sì, e solo se" per collegare due proposizioni, chiamate prima e seconda membro bicondizionale. Il simbolo usato è la freccia bidirezionale "↔".

Le due proposizioni collegate tramite "sì e solo se" sono chiamate rispettivamente Primo E Secondo membro e la bi-condizionalità di due proposizioni p e q rimane come p ↔ q. Per esempio:

P ↔ Q: a Maria piace andare in bicicletta se e solo se la giornata è soleggiata.

Dimostrazione delle leggi di De Morgan

Le leggi di De Morgan fanno parte di equivalenze logiche e possono essere dimostrate attraverso le tabelle della verità, che sono usate per conoscere il valore della verità (vero o falso) di una proposta.

Poiché la congiunzione è vera solo quando P e Q sono vere, la sua tabella di verità è:

D'altra parte, in disgiunzione, la proposta è vera se P e Q sono vere o se almeno una di esse è, ma è falsa se entrambi lo sono:

Può servirti: permutazioni senza ripetizione: formule, dimostrazione, esercizi, esempi

Ora, la negazione trasforma la verità in falso e viceversa. In questo caso, i valori di verità di ∼ (p ∧ q) e ∼ (p ∨ q) sono l'opposto dei valori di verità (p ∧ q) e (p ∨ q):

E si deve verificare che questi risultati siano ottenuti quando si eseguono le rispettive tabelle di verità di (∼ P ˅ ∼ Q) e (∼ P ˄ ˄ Q):

E in effetti, quando si confrontano le rispettive tabelle di verità, si osserva che le leggi di De Morgan sono soddisfatte. Ora saranno visti due esempi della sua applicazione.

Esempio risolto 1

Applica le leggi di De Morgan per trovare l'espressione equivalente di: ∼ (∼P ˅ ∼q)

• Soluzione

L'espressione data viene confrontata ∼ (∼P ˅ ∼q) con la legge di Morgan:

∼ (P ∨ Q) ⇔ ∼P ∧Q

E si osserva che la negazione è già al di fuori della parentesi in entrambi i casi, pertanto vengono seguite le istruzioni della legge: rifiuta ∼P, nega ∼Q e il connettore viene modificato:

∼ (∼P ˅ ∼q) ⇔ ∼ (∼P) ∧ ∼ (∼q) ⇔ P ∧ Q

Esempio risolto 2

Determinare l'espressione equivalente di ∼ [∼p ˄ ∼ (∼q)] ≡

• Soluzione

Innanzitutto, la negazione di ∼Q è semplificata:

∼ [∼P ˄ ∼ (∼q)] ⇔ ∼ [∼P ˄ Q]

Poiché esiste già una negazione al di fuori della parentesi, l'espressione risultante viene confrontata con la legge di Morgan: ∼ (P ∧ Q) ⇔ ⇔ ∼Q

Per risolvere ∼ [∼P ˄ q] è necessario negare ∼P, negare Q e cambiare il connettore:

∼ [∼p ˄ q] ⇔∼ (∼P) ∨ ∼q ⇔ P ˅ ∼q

Riferimenti

1. Becerra, j.M.  Note logiche Unam.
2. Brillante. Dalle leggi di Morgan. Recuperato da: brillante.org.
3. Tutorial elettronici. Di Morgan's Teorema. Recuperato da: Electronics-Tormales.Ws.
4. López, f. Introduzione alla logica matematica. Recuperato da: YouTube.com
5. Muñoz, c. Introduzione alla logica. Estratto da: siti Web.Ucm.È.