1.1 Introduzione.
 1.2 Logica enunciativa o proposizionale.
     1.2.1 Proposizioni e connettivi logici
     1.2.2 Valore di verità
        Negazione:
        Congiunzione:
        Disgiunzione:
        Condizionale:
        Bicondizionale:
        Esempio 1: valutare VdV((~A /\ B) \/ ~B)
        Esempio 2: valutare VdV(~A ->A)
        Esempio 3: valutare VdV((A /\ B) ->A)
        Esempio 4: valutare VdV((A/\B)->(B\/A))
     1.2.3 Equivalenza logica e Tautologia.
         Verifica
         Teoremi
         Osservazione (importante)
 1.3 Logica dei predicati.
     1.3.1 Predicati, proprietà
     1.3.2 Quantificatori.
         Utilizzo di quantificatori: esempi
     1.3.3 Applicazione su domini numerici.
         Esempi.
 Esercizi riepilogativi

Gli argomenti trattati in questo capitolo rientrano nella disciplina chiamata logica matematica, o simbolica.

L'aggettivo matematica si riferisce al fatto che i problemi tipici dello studio della logica, la correttezza e la natura del ragionamento, sono affrontati attraverso l'analisi di strutture matematiche che emergono da quei problemi.

L'aggettivo simbolica si riferisce al fatto che i linguaggi entro cui si esprimono i ragionamenti e i fatti della logica, che diventano oggetto del sopraddetto studio matematico, non sono i linguaggi naturali ma linguaggi artificiali costruiti su simboli, in certa misura arbitrari.

Quello che ci interessa spiegare ed esplicitare è la sensazione intuitiva che certi legami tra le proposizioni, legami per cui una proposizione è detta conseguenza di altre, sembrano imporsi per una sorta di necessità intrinseca: questi legami non dipendono da nulla di accidentale incluso nel senso e nelle sfumature delle parole usate, da nulla la cui verifica richieda l'esplorazione di una particolare situazione e la cui verità dipenda da fatti accidentali che possono essere o non essere noti.

Questo legame intrinseco è spesso caratterizzato come legame di conseguenza logica: scopo della logica simbolica è di specificarlo in modo estrinseco come legame indipendente dal contesto e quindi valido in tutti i contesti.

Anlizziamo le seguenti frasi:

E` semplice accorgersi che i due ragionamenti hanno in comune la forma: ma il passo che ora bisogna compiere è quello di isolare ed enunciare le proprietà usate e riconoscerne la coincidenza nei diversi casi.

Quello che è in gioco in ambedue le argomentazioni è la proprietà transitiva delle relazioni usate (insieme al fatto di includere il padre fra gli antenati e il predecessore fra i minori).

Ma per indicare in modo esplicito la forma del ragionamento conviene che non usiamo ne la parola minore ne la parola antenato: che 3 è minore di 11 non può seguire dalla proprietà transitiva della relazione antenato e che Ferdinando d'Aragona era antenato di Filippo il Bello non può seguire dalla proprietà transitiva della relazione minore.

Nello stesso tempo se enuncio la proprietà transitiva della relazione antenato nel primo caso e la proprietà transitiva della relazione minore nel secondo caso sto solo duplicando il lavoro ed è un'inutile pignoleria.

Ancora, se usassi la parola antenato per descrivere una relazione che ha la proprietà transitiva e poi nel caso dei numeri facessi appello alla proprietà di antenato, correrei il rischio di inserire involontariamente altre proprietà di antenato che non sono quella transitiva e che minore non ha.

Quello a cui pensiamo è una relazione generica che abbia la proprietà transitiva e allora non possiamo che indicarla con un segno diverso da tutte le parole della lingua italiana; se usassimo una parola dotata di senso, una parola di uso comune, ci porteremmo dietro il senso e le proprietà di questa parola e dovremmo poi specificare che la usiamo con un significato diverso da quello naturale: questo creerebbe confusione.

Siamo così condotti a impostare una scrittura simbolica che potrebbe avere questo aspetto

suggerito dalle frasi

Quelli che chiamiamo ragionamenti su specifici domini di conoscenza vengono così spezzati in tre momenti distinti:

1- formalizzazione (passaggio da Carlo è padre di Filippo a Pab)

2- deduzione logica che si compie sui simboli in cui è pervenuta la formalizzazione

3- interpretazione dei simboli (passaggio da Rac a Ferdinando è antenato di Filippo)

L'esempio di sopra non è certo sufficiente e potrebbe anche essere ingannevole: non è la proprietà transitiva in sè che è una regola logica, altrimenti, dato che le proprietà possibili di relazioni sono illimitate, le regole si moltiplicherebbero con risultati poco utili.

Bisognerà fare un passo ulteriore di analisi per individuare quelle che potremmo chiamare regole logiche, che nell'esempio sono state sottaciute, e per mezzo delle quali realizzare e verificare la consequenzialità logica.

Quanto abbiamo detto non è nulla di nuovo: stiamo solo generalizzando e precisando quello che avviene, ad esempio, con ogni teoria matematica che non è altro che una rete articolata di legami logici tra proposizioni, le dimostrazioni.

Il fatto di porre al centro dello studio la consequenzialità logica, cioè la correttezza formale, può sembrare limitativo: nell'esame di un ragionamento interessa sia la correttezza formale sia la validità.

Da quanto detto in precedenza possiamo dire che un ragionamento è formalmente corretto quando la conclusione è una conseguenza delle premesse. Riteniamo quindi corretti i seguenti ragionamenti:

Il secondo di questi ragionamenti, pur essendo formalmente identico al primo, è evidentemente non valido: la conclusione è una conseguenza delle premesse ma le premesse sono false.

Possiamo quindi dire che per essere valido, un ragionamento deve avere premesse vere: l'analisi della validità di un ragionamento è quindi ricondotto all'analisi della verità delle premesse.

In precedenza avevamo suddiviso i ragionamenti su specifici domini in tre parti: formalizzazione, deduzione logico-formale, interpretazione dei simboli.

Possiamo ora affermare che il problema della validità è posto, se esiste, al livello della formalizzazione, non a quello della deduzione logico-formale e dimostreremo che in una deduzione logico-formale è fondamentale che le premesse siano coerenti, cioè non contraddittorie.

La logica enunciativa esamina le argomentazioni costituite da enunciati dichiarativi: considereremo un enunciato come una sequenza di simboli (stringa) che esprime una proposizione.

Consideriamo le seguenti stringhe:

1- La terra è piatta

2- 2+2=4

3- Sommando 2 a 2 si ottiene il valore 4

4- E` la terra piatta

5- jkl tyu =@asd

Le stringhe 1 e 4 sono enunciati ed esprimono la stessa proposizione.

Le stringhe 2 e 3 sono enunciati ed esprimono la stessa proposizione.

La stringa 5 non è un enunciato in quanto non esprime proposizioni in un linguaggio noto.

Definiamo valore di verità (VdV) di una proposizione il valore vero o falso associabile alla proposizione:

E` importante non confondere una proposizione col suo valore di verità:

In seguito indicheremo le proposizioni con lettere maiuscole.

Introduciamo ora altri cinque simboli del nostro linguaggio:

e la convenzione che le stringhe ben formate (proposizioni) del nostro linguaggio devono essere comprese tra parentesi rotonde.

Se P è una proposizione ~P è una proposizione.

Se P e Q sono proposizioni allora (P\/Q), (P/\Q), (P->Q), (P<->Q) sono proposizioni.

Considereremo ben formate solo le stringhe costruite in questo modo.

Chiameremo connettivi logici i cinque simboli introdotti:

Esempio di stringhe costruite in modo non corretto:

1- (((A /\ B) /\ C) parentesi aperta in eccesso

2- (A /\ C) /\ B) errore di parentesi

3- (A -> /\ C) due connettori consecutivi

4- (~A -> C D) manca un connettivo tra C e D

5- (A /\ B) /\ (C -> A) errore di parentesi

VdV(~P)=vero se e solo se VdV(P)=falso.

La tabella associata è quindi
 

VdV(P/\Q)=vero se e solo se VdV(P)=vero e VdV(Q)=vero.

La tabella associata è quindi
 

VdV(P\/Q)=falso se e solo se VdV(P)=falso e VdV(Q)=falso.

La tabella associata è quindi
 

VdV(P-Q)=falso se e solo se VdV(P)=vero e VdV(Q)=falso.

La tabella associata è quindi
 

VdV(P<-Q)=vero se e solo se VdV(P)=VdV(Q).

La tabella associata è quindi
 

Un metodo per calcolare il VdV di un enunciato composto da più proposizioni legate tramite connettivi logici è quello di analizzare prima le parentesi più interne e, una volta risolte, proseguire fino ad ottenere il valore di tutta la proposizione:

Esempio 1: valutare VdV((~A /\ B) \/ ~B)

Si esaminerà prima ~A, poi (~A /\ B) e ~B, ed infine la proposizione finale.
 

Esempio 2: valutare VdV(~A ->A)

Esempio 3: valutare VdV((A /\ B) -> A)
 

Esempio 4: valutare VdV((A/\B)->(B\/A))

Due enunciati P e Q sono logicamente equivalenti se e solo se VdV(P)=VdV(Q) per ogni possibile combinazione dei valori di verità delle loro parti elementari.

Un enunciato P è una tautologia se e solo se VdV(P)=vero per ogni possibile combinazione dei valori di verità delle sue parti elementari

Due enunciati P e Q sono logicamente equivalenti se e solo se (P<-Q) è una tautologia.

Le seguenti preposizioni

sono tautologie.

Detto con altre parole:

1- l'operatore /\ è commutativo

2- l'operatore \/ è commutativo

3- l'operatore <-> è commutativo

4- l'operatore /\ gode della proprietà associativa

5- l'operatore \/ gode della proprietà associativa

6- L'operatore \/ gode della proprietà distributiva rispetto all'operatore /\

7- L'operatore /\ gode della proprietà distributiva rispetto all'operatore \/

La verifica delle prime tre tautologie è immediata e viene quindi lasciata come esercizio.

Verifica 4:
 

e quindi
 

La verifica delle tautologie 5,6,7 è simile a quella verificata sopra e viene lasciata come esercizio.

La verifica fatta sopra mostra che il metodo di confrontare tutte le possibili combinazioni dei valori di verità degli enunciati elementari per ottenere il valore di verità di un enunciato composto pur essendo semplice è molto costoso: infatti per una proposizione composta da N enunciati elementari si hanno 2^N combinazioni.

Le seguenti proposizioni

sono tautologie.

Detto con altre parole:

I punti 3,4,5 implicano che due soli simboli, ad esempio negazione e congiunzione, sono sufficienti per scrivere ogni proposizione, a scapito di chiarezza e semplicità.

In effetti la seguente argomentazione, formata da due enunciati dichiarativi uniti da un connettivo di disgiunzione

Non si da il caso che la terra non è piatta e il cane non è un animale

Verifica 1:
 

Verifica 2:
 

Verifica 3:
 

e quindi
 

Verifica 4:
 

Verifica 5, nota come legge di De Morgan:
 

e quindi
 

Se T è una tautologia e A è una proposizione, (A -> T) e (~T -> A) sono tautologie.

Verifica:
 

Questo teorema può essere molto utile per determinare se una proposizione è una tautologia. Ad esempio:

è una tautologia in quanto (A->A) è una tautologia.

Verificare la seguente tutologia: (((A /\ B) -> C) <-> (A -> (B -> C)))

Verifica:
 

e quindi
 

Questo esempio merita un po` di attenzione proprio in programmazione: afferma una equivalenza logica tra

1- se A e B allora C

2- se A allora se B allora C

Esistono linguaggi di programmazione (il Pascal ad esempio) in cui non sempre le due scritture forniscono lo stesso risultato: ciò avviene quando il valore di verità di A è falso e il valore di verità di B non è calcolabile.

Riassumendo le principali equivalenze logiche:

a- Quali delle seguenti stringhe sono costruite in modo corretto?

b- Quali delle seguenti proposizioni sono tautologie?

La logica dei predicati è una estensione della logica proposizionale costruita in modo da permettere di trattare al suo interno un maggior numero di tipi di enunciati.

Indicheremo le proprietà con le lettere maiuscole dell'alfabeto:

e con lettere minuscole x,y,z,t,u,y elementi generici (variabili) appartenenti ad un insieme:

Le frasi sopra scritte non sono ancora enunciati in quanto non siamo in grado di attribuire loro un valore di verità.

In modo formale le esprimiamo con le seguenti scritture:

che chiameremo enunciati incompleti o predicati.

Indicheremo con le lettere minuscole a,b,c,d,e elementi specifici appartenenti ad un insieme:

Si ha quindi

sono proposizioni con

Sempre con le lettere maiuscole indicheremo anche le relazioni tra due elementi di un insieme:

Non esiste praticamente alcuna differenza tra il trattamento delle relazioni e quello delle proprietà: in una formula le relazioni ci appariranno seguite da due variabili:

Un modo per trasformare un predicato in una proposizione è quello di sostituire le variabili con delle costanti. Ad esempio:

Il predicato Pxy può essere trasformato in una proposizione sostituendo x con a e y con b. Diremo allora che Pab è un esemplare di Pxy, cioè una proposizione ottenuta sostituendo le variabili del predicato con costanti.

Intendiamo per quantificatore una espressione che indica quanti individui di un insieme hanno una proprietà indicata da un enunciato incompleto.

Un quantificatore premesso ad un enunciato incompleto lo rende completo e quindi diventa possibile attribuire ad esso un valore di verità.

Esistono due quantificatori: il quantificatore esistenziale e il quantificatore universale.

Il primo, es(x), indica che esiste almeno un elemento che gode della proprietà enunciata; il secondo, og(x), indica che ogni elemento gode della proprietà enunciata.

Sono quindi proposizioni:

Per esse vale quanto detto per la logica delle proposizioni.

Una stringa costruita con proprietà, variabili, quantificatori, è una proposizione se non contiene variabili libere, cioè variabili che non compaiono nel campo di alcun quantificatore:

Le seguenti proposizioni

sono tautologie.

Il precedente teorema ci indica una relazione tra i due quantificatori.

La 1 ad esempio, ci dice che per dimostrare che una affermazione universale è falsa è sufficiente verificare che esiste un caso in cui è vero il contrario.

Un errore molto comune è quello di dimostrare che una affermazione universale è vera proponendo un esempio in cui è vera: si considera erroneamente

una tautologia.

Formalizziamo i seguenti enunciati:

Indichiamo con

A = "è un cane"

B = "è un animale"

La frase può essere così riscritta:

o in modo formale

E` sufficiente ora aggiungere il quantificatore universale

La frase può essere così riscritta:

o in modo formale

E` sufficiente ora aggiungere il quantificatore universale

Svolgimento 3:

La frase può essere così riscritta:

cioè

In modo formale

Svolgimento 4:

La frase può essere così riscritta:

o in modo formale

E` sufficiente ora aggiungere il quantificatore esistenziale

Svolgimento 5:

La frase può essere così riscritta:

o in modo formale

E` sufficiente ora aggiungere il quantificatore esistenziale

Formalizziamo i seguenti enunciati:

1- "tutti i cani e i gatti sono animali con quattro zampe"

2- "alcuni numeri sono maggiori di altri numeri"

3- "tutti i cani rincorrono i gatti che li temono"

4- "i ragazzi o leggono o gioacano"

5- "solo i cani rincorrono i gatti"

Indichiamo con

A = "è un cane" B = "è un animale"

C = "è un gatto" D = "ha quattro zampe"

Qui bisogna fare attenzione all'uso che viene fatto della 'e': in questa frase si intende dire che se qualcosa è un cane oppure un gatto esso è un animale, non che se qualcosa è un gatto e contemporaneamente un cane esso è un animale. La frase può essere così riscritta:

o in modo formale

E` sufficiente ora aggiungere il quantificatore esistenziale

Indichiamo con

A = "è un numero" B = "è maggiore di"

le due proprietà espresse nella proposizione.

La frase può essere così riscritta:

o in modo piu' preciso

In modo formale:

Indichiamo con

A = "è un cane" B = "è un gatto"

P = "teme " R = "rincorre "

La frase diventa

cioè

Svolgimento 4:

Indichiamo con

R = "è un ragazzo" L = "legge" B = "gioca"

Se consideriamo mutuamente esclusivi il fatto di leggere o giocare, la frase diventa:

Indichiamo con

G = "è un gatto" C = "è un cane" R = " rincorre "

La frase diventa

cioè

Vogliamo ora semplificare il modo di scrivere delle proposizioni nel caso che gli insiemi di variazione delle variabili siano insiemi numerici:

Con la simbologia descritta ora la 1 diventa:

da cui:

Significa:

cioè

La 2 diventa:

si scrive come

oppure

Determinare il valore di verità delle seguenti proposizioni e, se possibile, l'insieme dei valori per cui risultano vere:

1- In N: es(x) ((x < 12) /\ ( x 4))

2- In Z: es(x) ((x^2 + 5*x + 6 = 0) \/ (x = 5))

3- In R: og(x)(x * x > 0)

4- In Q: es(x)(es(y) ((x + y = 1) /\ (x - y = 0)))

5- In N: es(x)(og(y) ( x - y = 0))

6- In N: og(y)(es(x) ( x - y = 0))

dove N,Z,Q,R rappresentano rispettivamente gli insiemi dei numeri naturali, relativi, razionali e reali.

Ci chiediamo se in N esiste un valore minore di 12 e maggiore di 4:

VdV(In N: es(x) ((x < 12) /\ ( x 4)))= vero

per x in T = (5,6,7,8,9,10,11)

Ci chiediamo se in Z esiste un valore uguale a 5 oppure valori che per cui

x^2 + 5*x + 6 = 0 :

VdV(In Z: es(x) ((x^2 + 5*x + 6 = 0) \/ (x = 5))) = vero

per x in T = (-2,-3,5)

Ci chiediamo se per ogni numero reale x, x*x > 0 :

VdV( In R: og(x)(x * x > 0)) = falso

poichè per x = 0 abbiamo (0 = 0)

Ci chiediamo se esiste una coppia di valori x,y appartenenti a Q tali che

x + y = 1 e x - y = 0 :

VdV( In Q: es(x)(es(y) ((x + y = 1) /\ (x - y = 0)))) = vero

per x=0.5 e y= 0.5

E` inportante rendersi conto della differenza di quanto affermano le proposizioni 5 e 6:

la 5 afferma che, esiste almeno un x tale che, per tutte le possibili scelte di y, x - y = 0.

La 6 afferma che, comunque si scelga y, esiste un valore di x tale che

x - y = 0.

5) Poichè

es(x)(og(y) ( x - y = 0)) e es(x)(~(es(y) (x - y < 0))

sono logicamente equivalenti e la seconda è falsa in quanto è sufficiente sceglire un valore di y diverso da x si ha:

VdV(es(x)(og(y) ( x - y = 0)))= falso

6) VdV(og(y)(es(x) ( x - y = 0)))= vero

in quanto è sufficiente, comunque si scelga y, scelgliere x=y.

a- Indicare quali delle seguenti stringhe sono proposizioni:

b- Formalizzare le seguenti proposizioni:

c- Individuare tra le seguenti proposizioni quelle vere indicando per quali valori delle variabili sono verificate.