Leggi di Morgan

Gli occhi di Morgan sono regole di inferenza usate nella logica proposizionale, che stabiliscono ciò che è il risultato di negare una disgiunzione e una congiunzione di proposizioni o variabili proposizionali. Queste leggi furono definite dal matematico Augustus De Morgan.

Le leggi di Morgan rappresentano uno strumento molto utile per dimostrare la validità di un ragionamento matematico. Più tardi furono generalizzati all'interno del concetto di serie del matematico George Boole.

Questa generalizzazione fatta da Boole è completamente equivalente alle leggi iniziali di Morgan, ma è sviluppata specificamente per gli insiemi piuttosto che per le proposizioni. Questa generalizzazione è anche nota come legge di Morgan.

Revisione della logica proposizionale

Prima di esaminare quali sono le leggi di Morgan e in che modo vengono utilizzate, è opportuno ricordare alcune nozioni di base della logica proposizionale. (Per maggiori dettagli vedi l'articolo sulla logica proposizionale).

Nel campo della logica matematica (o proposizionale), un'inferenza è una conclusione che viene emessa da un insieme di premesse o ipotesi. Questa conclusione, insieme alle premesse menzionate, dà origine a ciò che è noto come ragionamento matematico.

Questo ragionamento deve poter essere dimostrato o negato; vale a dire che non tutte le inferenze o conclusioni in un ragionamento matematico sono valide.

fallacia

Una falsa inferenza emessa da alcuni presupposti che si presumono veri è nota come errore. Gli errori hanno la particolarità di essere argomenti che sembrano corretti, ma matematicamente non lo sono.

La logica proposizionale ha il compito di sviluppare e fornire precisamente metodi mediante i quali si può, senza alcuna ambiguità, validare o smentire un ragionamento matematico; cioè, dedurre una conclusione valida dalle premesse. Questi metodi sono noti come regole di inferenza, di cui le leggi di Morgan fanno parte.

proposizioni

Gli elementi essenziali della logica proposizionale sono proposizioni. Le proposizioni sono affermazioni su cui si può dire se sono valide o meno, ma che non possono essere vere o false allo stesso tempo. Non ci dovrebbero essere ambiguità in questa materia.

Proprio come i numeri possono essere combinati mediante operazioni di addizione, sottrazione, moltiplicazione e divisione, le proposizioni possono essere gestite mediante il noto connettivo (o connettori) logico: negazione (, "no"), disgiunzione (V, "O"), congiunzione (Ʌ, "e"), condizionale (→, "se ..., quindi ...") e bicondizionale (↔, "sì, e solo se").

Per lavorare più in generale, invece di considerare proposizioni specifiche, consideriamo le variabili proposizionali che rappresentano qualsiasi proposizione e sono solitamente indicate da lettere minuscole p, q, r, s, ecc.

Una formula proposizionale è una combinazione di variabili proposizionali attraverso alcuni dei connettivi logici. In altre parole, è una composizione di variabili proposizionali. Di solito sono denotati con lettere greche.

Si dice che una formula proposizionale ne implichi logicamente un'altra quando quest'ultima è vera ogni volta che la prima è vera. Questo è denotato da:

Quando l'implicazione logica tra due formule proposizionali è reciproca - cioè, quando l'implicazione precedente è valida anche nella direzione opposta - si dice che le formule sono logicamente equivalenti, ed è denotata da

L'equivalenza logica è una sorta di uguaglianza tra le formule proposizionali e consente di sostituirne l'altra quando necessario.

Leggi di Morgan

Le leggi di Morgan consistono in due equivalenze logiche tra due forme proposizionali, vale a dire:

Queste leggi permettono di separare la negazione di una disgiunzione o congiunzione, come negazioni delle variabili coinvolte.

Il primo può essere letto come segue: la negazione di una disgiunzione è uguale alla congiunzione delle negazioni. E la seconda legge così: la negazione di una congiunzione è la disgiunzione delle negazioni.

In altre parole, negare la disgiunzione di due variabili proposizionali equivale alla congiunzione delle negazioni di entrambe le variabili. Allo stesso modo, negare la congiunzione di due variabili proposizionali equivale alla disgiunzione delle negazioni di entrambe le variabili.

Come accennato in precedenza, la sostituzione di questa equivalenza logica aiuta a dimostrare risultati importanti, insieme alle altre regole di inferenza esistenti. Con questi puoi semplificare molte formule proposizionali, in modo che siano più utili con cui lavorare.

Quello che segue è un esempio di prova matematica che utilizza le regole di inferenza, tra le leggi di Morgan. Nello specifico, viene mostrato che la formula:

è equivalente a:

Quest'ultimo è più semplice da capire e sviluppare.

spettacolo

Vale la pena ricordare che la validità delle leggi di Morgan può essere dimostrata matematicamente. Un modo è confrontando le tue tabelle di verità.

set

Le stesse regole di inferenza e le nozioni di logica applicate alle proposizioni possono anche essere sviluppate considerando gli insiemi. Questa è la cosiddetta algebra booleana, secondo il matematico George Boole.

Per differenziare i casi, è necessario cambiare la notazione e trasferire agli insiemi, tutte le nozioni già viste della logica proposizionale.

Un set è una collezione di oggetti. Gli insiemi sono indicati con le maiuscole A, B, C, X, ... e gli elementi di un insieme sono indicati con lettere minuscole a, b, c, x, ecc. Quando un elemento a appartiene a un insieme X, è indicato da:

Quando non appartiene a X, la notazione è:

Il modo di rappresentare i set è posizionare i loro elementi all'interno delle chiavi. Ad esempio, l'insieme di numeri naturali è rappresentato da:

I set possono anche essere rappresentati senza scrivere un elenco esplicito dei loro elementi. Possono essere espressi nella forma {:}. I due punti sono letti "così". Una variabile che rappresenta gli elementi dell'insieme è posta a sinistra dei due punti e la proprietà o condizione che soddisfano è posta sul lato destro. Questo è:

Ad esempio, l'insieme di numeri interi superiori a -4 può essere espresso come:

O in modo equivalente, e più abbreviato, come:

Allo stesso modo, le seguenti espressioni rappresentano gli insiemi di numeri pari e dispari, rispettivamente:

Unione, intersezione e complementi di insiemi

Successivamente vedremo gli analoghi del connettivo logico nel caso di insiemi, che fanno parte delle operazioni di base tra insiemi.

Unione e intersezione

L'unione e l'intersezione di insiemi sono definiti, rispettivamente, nel modo seguente:

Ad esempio, considera i set:

Quindi, devi:

complemento

Il complemento di un insieme è formato dagli elementi che non appartengono a quell'insieme (dello stesso tipo rappresentato dall'originale). Il complemento di un insieme A, è indicato da:

Ad esempio, all'interno dei numeri naturali, il complemento dell'insieme di numeri pari è quello dei numeri dispari e viceversa.

Per determinare il complemento di un insieme deve essere chiaro fin dall'inizio l'insieme universale o principale di elementi che vengono considerati. Ad esempio, non è uguale considerare il complemento di un insieme sui numeri naturali che su quelli razionali.

La seguente tabella mostra la relazione o l'analogia che esiste tra le operazioni su insiemi precedentemente definiti e quelli connettivi della logica proposizionale:

Leggi di Morgan per set

Infine, le leggi di Morgan sugli insiemi sono:

In parole: il complemento di un'unione è l'intersezione dei complementi, e il complemento di un'intersezione è l'unione dei complementi.

Una prova matematica della prima uguaglianza sarebbe la seguente:

La dimostrazione del secondo è analoga.