<< pagina principale < ······················ << articoli < ······················

Grafici per il calcolo proposizionale

Roberto Ricci

Liceo Scientifico "A.Righi", Bologna

Introducendo la logica proposizionale in un corso di matematica per alunni delle scuole superiori è bene sottolineare che il concetto di operazione è più generale di quanto l'abitudine, quella di lavorare con numeri di N, Z, Q o R, ci porti a credere. Infatti, i connettivi possono essere interpretati come operazioni nell'insieme { vero, falso }. In questo modo le tavole di

verità si riducono a tabelline pitagoriche; ad esempio, la tabellina della congiunzione ha la forma seguente:

In questo modo la logica delle proposizioni può essere ridotta a un calcolo come quello aritmetico, il calcolo booleano. Più raramente capita di mostrare come i connettivi siano interpretabili come relazioni nell'insieme {vero, falso}. Ciò può essere particolarmente utile, ad esempio, per consolidare o approfondire la conoscenza delle proprietà delle relazioni basandosi su esempi meno artificiosi o estemporanei di quelli che si tende in generale a proporre. Inoltre, a partire da semplici grafici che rappresentano tali relazioni, si può costruire un calcolo proposizionale alternativo alle tavole di verità, basato su operazioni insiemistiche facilmente visualizzabili.

1.

Mostriamo dunque come i connettivi siano interpretabili con relazioni binarie sull'insieme dei valori di verità, cioè con sottinsiemi del prodotto cartesiano { vero, falso }´ { vero, falso }; in particolare il loro numero, come quello di tali sottinsiemi, è 2⁴ = 16.

Per primo esaminiamo la congiunzione. Essendo la proposizione composta PÙ Q vera sse entrambe le proposizioni P e Q sono vere, nella interpretazione proposta considereremo la relazione il cui grafico cartesiano è

che potremmo anche sintetizzare nel grafico

Poiché in seguito indagheremo le proprietà di tali relazioni binarie, ricordiamo le definizioni di alcune fra queste, l'antiriflessiva e l'antisimmetrica. Una relazione binaria R definita su un insieme A si dice:

non antiriflessiva sse $ x Î A tale che x R x,

non antisimmetrica sse $ x,y Î A, x¹ y, tali che xRy e yRx.

Guardando il grafico della relazione che interpreta la congiunzione, si rilevano facilmente le seguenti proprietà: non riflessiva, non antiriflessiva, simmetrica, antisimmetrica, transitiva. Ciò permette di sciogliere alcuni possibili dubbi sulla coesistenza della proprietà "taldeitali" con l'"antitaldeitali" in una stessa relazione.

La disgiunzione sarà interpretata dalla relazione {(vero,vero),(vero,falso),(falso,vero)} con grafico cartesiano

che possiamo anche sintetizzare nel grafico seguente

Tale relazione, come visibile dal grafico, soddisfa evidentemente le proprietà: non riflessiva, non antiriflessiva, simmetrica, non antisimmetrica, non transitiva.

La disgiunzione esclusiva, che potremmo indicare con il simbolo , è interpretata dalla relazione { (vero,falso), (falso,vero) } di grafico

che ne evidenzia le proprietà non riflessiva, antiriflessiva, simmetrica, non antisimmetrica, non transitiva.

L'implicaziene materiale, che indichereìiio con il simbolo Þ , è interpretata dalla relazione { (vero,vero), (falso,vero), (falso,falso) } di grafico

la quale verifica le proprietà: riflessiva, non antiriflessiva, non simmetrica, antisimmetrica, transitiva; è quindi una relazione di ordine largo.

Infine, per concludere l'elenco dei connettivi più frequentemente presi in considerazione, la doppia implicazione, che indicheremo con il simbolo , Û è interpretata dalla relazione {(vero,vero), (falso,falso)} che ha grafico

e dunque gode delle proprietà: riflessiva, non antiriflessiva, simmetrica,antisimmetrica, transitiva, essendo la relazione identica, ovviamente si tratta di una relazione di equivalenza; può stupire riconoscere che la relazione è anche di ordine largo.

2.

Tra i connettivi binari è utile considerare anche quelli che potremmo chiamare proiezione: il primo, interpretabile mediante la relazione {vero}´ {vero,falso}, consente di vedere la formula proposizionale P come formula nelle due lettere proposizionali P e Q, il secondo, interpretabile dalla relazione {vero,falso} ´ {vero}, è l'analogo per la formula costituita dalla sola lettera Q, e sono interpretabili rispettivamente dai grafici

In tal modo la congiunzione P Ù Q e la disgiunzione P Ú Q si possono interpretare anche, rispettivamente, come "intersezione" e "unione" tra le relazioni binarie che interpretano le due proiezioni; inoltre la formula Ø P è interpretata dal complementare della relazione che interpreta la formula P, di grafico come il seguente:

Più in generale congiunzione e disgiunzione di due generiche formule proposizionali sono interpretabili con intersezione e unione delle espressioni insiemistiche che interpretano ciascuna delle due formule proposizionali, mentre la negazione di una generica formula proposizionale è interpretabile con il complementare della espressione insiemistica che interpreta la formula data.

Due formule proposizionali saranno logicamente equivalenti sse le espressioni insiemistiche che ne sono interpretazione hanno per risultato lo stesso insieme, cioè la stessa relazione. Così, ad esempio:

mostra l'equivalenza logica (P Ú Q) Ù P º P. Inoltre:

mostra la tautologia P Ú Ø P interpretata nell'insieme {vero,falso}´{vero,falso}, mentre

mostra l'equivalenza logica Ø P Ú Q º PÞ Q.

Indicato con $ un qualsiasi connettivo binario, si può osservare che le formule proposizionali Ø P $ Q, P $ Ø Q , Ø P $ Ø Q sono interpretate da relazioni i cui grafici si ottengono mediante simmetrie dei grafici delle relazioni che interpretano la formula P $ Q , l'ultima delle quali è ad esempio una simmetria rispetto alla diagonale secondaria.

Si possono così "vedere" diverse equivalenze logiche, come quelle di De Morgan; ad esempio si può vedere che P Û Q è logicamente equivalente a Ø ( P Q )confrontando i due grafici cartesiani seguenti

che interpretano rispettivamente P Û Q e P Q, oppure che P Þ Qequivale a Ø ( P Ù Ø Q) confrontando i due grafici

che interpretano rispettivamente P Þ Q e P Ù Ø Q.Questa interpretazione grafica permette anche di vedere come ogni formula proposizionale nelle due lettere P e Q , oltre a essere logicamente equivalente a uno dei 16 connettivi, possa essere riscritta come disgiunzione di alcune delle congiunzioni P Ù Q, P Ù Ø Q , Ø P Ù Q, Ø P Ù Ø Q, ciascuna interpretata da una "casella" del grafico, in una forma detta canonica disgiuntiva. Ad esempio

P Þ Q º (P Ù Q) Ú (Ø P Ù Q) Ú (Ø P Ù Ø Q).

Il concetto di implicazione logica, che indicheremo con il simbolo |= e che deve essere distinto chiaramente dal connettivo Þ , l'implicazione materiale, può essere interpretato con l'inclusione insiemistica: dette … e † due formule proposizionali, À e Á le relazioni che le interpretano, … |= † sse À Í Á .Ad esempio il fatto che

suggerisce che Q consegue logicamente da P Ù Q. Ad esempio la validitàdella implicazione logica P Ù Q |= P Û Q si può vedere da

Da

e da

si conferma la validità della implicazione logica: Ø P, P Ú Q ú = Q. Da

e da

si può controllare la validità della implicazione logica P , PÞ Q ú = Q.

Da

e da

si controlla la correttezza della implicazione logica Ø Q , P Þ Q ú = Ø P.Da

non si vede invece alcuna novità rispetto alle premesse Ø P , P Þ Q poichéinfatti da

non risultano conseguenze degne di rilievo.

3. Le formule proposizionali in tre lettere, come (P Ù Q) Ú R, possono essere a loro volta interpretate con relazioni ternarie; nel caso preso ad esempio dovremo considerare la relazione { (vero, vero, vero) ,(vero, vero, falso), (vero,falso,vero) ,(falso,vero,vero), (falso,falso,vero)}, il cui grafico cartesiano è tridimensionale ma può anche essere rappresentato bidimensionalmente; ad esempio con le mappe di Karnaught, dette anche diagrammi di Veitch, formule su 4 lettere proposizionali si rappresentano in un grafico come il seguente

dove le colonne riportano le disposizioni con ripetizione dei valori di verità delle prime due lettere proposizionali mentre le righe rappresentano quelle delle ultime due lettere proposizionali, con la particolarità che colonne o righe contigue variano solo per un valore.

Ci serviremo qui, equivalentemente, della seguente generalizzazione, più chiaramente basata su un procedimento di bipartizione sopra-sotto e sinistra-destra di un rettangolo:

e così via, che chiameremo rispettivamente P₁, P₂, P₃, P₄, P₅, P₆ e così via, con una suddivisione in 2^(n+1)/2 righe se n è dispari, 2^n/2 colonne se n è pari.In questa interpretazione del linguaggio proposizionale le figure chiamate P₁,P₂,... costituiscono il dominio dell'interpretazione e vengono fatte corrispondere alle omonime variabili proposizionali.

Il vantaggio di ridurre il calcolo proposizionale al calcolo insiemistico, di visualizzarlo graficamente ed in modo più sintetico di quanto non accada ad esempio con le tavole di verità, è così uno scopo nuovamente raggiunto.

Ad esempio si voglia rappresentare la proposizione

P₃ Un altro vantaggio di tali rappresentazioni grafiche è che ognuna delle 2^[(n+1)/2]·2^[n/2] "caselle" del grafico della relazione corrisponde a una congiunzione di proposizioni P₁, P₂ ,.... o delle loro negazioni, detta congiunzione fondamentale. Ad esempio:

la seconda di queste formule proposizionali, ad esempio, può essere vista come processo finale dì successive bipartizioni del quadrato

Per ogni formula proposizionale rappresentata con tale grafico si può quindi determinare facilmente la forma canonica disgiuntiva. Ad esempio da:

si conclude P₁ Ù Ø (P_2Ù P₃) = (P₁ Ù P₂ Ù Ø P₃)Ú (P₁ Ù Ø P₂ Ù P₃)Ú (P₁ Ù Ø P₂ Ù Ø P₃).Un'altra forma normale disgiuntiva risulta visibilmente da:

cioè la formula P₁ Ù Ø (P_2Ù P₃) = (P₁ Ù P₂ Ù Ø P₃)Ú (P₁ Ù Ø P₂).Per passare da un grafico È a una forma canonica disgiuntiva ¸ la cuiinterpretazione sia equivalente a È si può costruire un albero i cui percorsi dalla radice alle foglie sono in corrispondenza con le congiunzioni fondamentali di ¸ :indicare la radice, il nodo di profondità O, con la coppia ( vero, È ), dove a vero è associata la figura che ha per complementare il vuoto,da un nodo di profondità n già indicato (× ,É ) nasce un ramo sinistro fino al nodo da indicare (P+1,JrmP+) se la figura JThPflfJ è non vuota, nasce un ramo destro da indicare ( mP+ ,É Pfl+ ) se la figura fl+1 è non vuota,un nodo già indicato (X,J) diventa una foglia dell'albero anche se, considerati i nodi indicati (X1,...),(X2,...)..(X,...) lungo il percorso verso la radice, si ha che flx,-J,la congiunzione di tutte le lettere proposizionali lungo un percorso dalla radice alle foglie è una congiunzione fondamentale di P, che è l'unione di tali congiunzioni fondamentali Ad esempio si può vedere il procedimento applicato nel caso seguente:

Anche per formule con più di due lettere proposizionali, una proposizione P è conseguenza logica di una proposizione Q quando la relazione risultato dell'espressione insiemistica che interpreta P è sottinsieme della relazione risultato dell'espressione insiemistica che interpreta Q. Concludiamo quindi mostrando come servirsi di questa impostazione grafica per ricavare conclusioni logiche da premesse date.

Premesse:

O si iscriverà all'università, oppure sarà arruolato.

Se non s'iscriverà all'università, si sposerà.

Se si sposerà, avrà bisogno di un buono stipendio.

Nell'esercito non percepirà un buono stipendio.

Dopo aver introdotto in modo opportuno variabili proposizionali affinché la forma delle premesse risulti: P_1Ú P₂, Ø P_1Þ P₃, P_3Þ P₄, P_2Þ P₅, potremmo servirci dei seguenti grafici:

Poiché la congiunzione delle premesse è:

allora la formula proposizionale:

in forma normale disgiuntiva, è una possibile conseguenza logica, così come ogni altra formula proposizionale interpretabile da una relazione che contenga quella rappresentata graficamente.

Bibliografia

G.Lolli, Introduzione alla logica formale, il Mulino, Bologna 1991.

Association Interentreprises pour le Développement de L'Enseignement Programè (acura di), Algèbre de Boole, Dunod, Paris 1965.

G. Giaccaglini, Elettronica industriale, Lib. ed univ. Levrotto e Bella, Torino 1969.