Semantica per formule di un linguaggio proposizionale

p.9 della dispensa

Per stabilire la verità di una formula proposizionale, fissiamo innanzitutto il fatto che accettiamo di avere solo due possibili valori di verità: il vero e il falso

(si dice che la nostra logica proposizionale è “bivalente”)

Poi definiamo l’attribuzione del valore di verità ad una formula “per gradi”, a partire dalle formule più semplici (le atomiche, costituite dalla sola lettera proposizionale P, Q, R…) fino a quelle sempre più complesse (che contengono uno o più connettivi).

Si parte, quindi, assegnando valori di verità

alle formule atomiche. Tale assegnamento è “libero”: non ha nessun carattere di necessità.

• Se si vuole usare una terminologia matematica, questo atto di assegnamento può essere rappresentato come una funzione (cioè un’operazione) che va dall’insieme delle formule atomiche all’insieme dei valori di verità, in quanto è un’operazione che, ricevendo in entrata formule atomiche, dà in uscita il verdetto, cioè il valore di verità di ciascuna (che, appunto, è preso dall’insieme dei due valori, vero/falso).

Per rappresentare tutto ciò con una scrittura simbolica, chiamiamo:

V l’assegnamento,

L l’insieme delle formule atomiche,

2 l’insieme dei due valori “vero” e “falso”

(non storcete il naso: “2” è un simbolo come un altro, che può essere utilizzato come nome di un insieme – perché no?- specialmente se l’insieme contiene due sole cose!)

• Il “vero” e il “falso” possono essere rappresentati, ciascuno, con “V” e “F”, oppure con “T” (true) e “F”, oppure con “1” e “0”.

• Quindi, quanto appena detto a proposito dell’assegnamento dei valori di verità alle formule atomiche può essere scritto così:

V: L2

che esprime il fatto che la funzione V prende in entrata formule atomiche e dà in uscita un valore di verità

(I due punti dopo la “V” stanno a significare, appunto, che si sta per esplicitare come lavora quella funzione con quel nome)

La scritta 2:= {1,0}è la definizione dell’insieme che ha come

nome 2. Si tratta, appunto, dell’insieme che contiene i due membri “1” e “0” che vengono utilizzati per rappresentare il “vero” e il “falso”

(“:=“ è un simbolo che significa che si sta per definire il simbolo scritto alla sua sinistra)

• Una volta assegnato il valore di verità alle formule atomiche, il valore delle formule composte resta fissato automaticamente sulla base delle tavole di verità per i connettivi, che sono state date alle pp. 7 e 8.

• Quelle tavole possono anche essere espresse in maniera abbreviata come segue:

Tavola di veritàdella negazione

A ¬A

1 0

0 1

Può essere espressa come:

V(¬A) := 1-V(A)che significa che:[V(¬A )] l’assegnamento di valore di verità a ¬A [:= ] è definito con l’operazione 1-V(A), cioè togliendo a 1 il valore di verità di A

Infatti

Osservando la tabella, vediamo che:

Se V(A) è 1, (cioè, se nella colonna di sinistra c’è il valore 1),

Allora

V(¬A) è 1-1, cioè 0 (cioè, nella colonna di destra c’è valore 0).

Se V(A) è 0, (cioè, se nella colonna di sinistra c’è il valore 0),

V(¬A) è 1-0, cioè 1 (cioè, nella colonna di destra c’è valore 1).

Tavola di verità della disgiunzione

A B A B

1 1 1

1 0 1

0 1 1

0 0 0

può essere espressa come:

V(A B) := max (V(A), V(B))che significa che:

V(A B)l’assegnamento di valore di verità a AB [:= ] è definito con l’operazione che sceglie max (V(A), V(B)), cioè il maggiore tra i valori di verità attribuiti, volta per

volta, ad A e a B:

Infatti,

Osservando la tabella, vediamo che:

• alla prima riga, dove abbiamo come valore di A (cioè come V(A)) 1 e come valore di B (cioè come V(B)) ancora 1,

abbiamo come valore di A B (cioè come V(A B)) 1, che è il massimo tra 1 e 1.

• alla seconda riga, dove abbiamo come valore di A (cioè come V(A)) 1 e come valore di B (cioè come V(B)) 0,

abbiamo come valore di A B (cioè come V(A B)) 1, che è il massimo tra 1 e 0.

• alla terza riga, dove abbiamo come valore di A (cioè come V(A)) 0 e come valore di B (cioè come V(B)) 1,

abbiamo come valore di A B (cioè come V(A B)) 1, che è il massimo tra 0 e 1.

• alla quarta riga, dove abbiamo come valore di A (cioè come V(A)) 0 e come valore di B (cioè come V(B)) ancora 0,

abbiamo come valore di A B (cioè come V(A B)) 0, che è il massimo tra 0 e 0.

Tavola di verità della congiunzione

A B A B

1 1 1

1 0 0

0 1 0

0 0 0

può essere espressa come

V(A B) := min (V(A), V(B))che significa che:

V(A B)l’assegnamento di valore di verità a A B [:= ] è definito con l’operazione che sceglie min(V(A), V(B)), cioè il minimo tra i valori di verità attribuiti, volta per

volta, ad A e a B:

Infatti

Osservando la tabella, vediamo che:

• alla prima riga, dove abbiamo come valore di A (cioè come V(A)) 1 e come valore di B (cioè come V(B)) ancora 1,

abbiamo come valore di A B (cioè come V(A B)) 1, che è il minimo tra 1 e 1.

• alla seconda riga, dove abbiamo come valore di A (cioè come V(A)) 1 e come valore di B (cioè come V(B)) 0,

abbiamo come valore di A B (cioè come V(A B)) 0, che è il minimo tra 1 e 0.

• alla terza riga, dove abbiamo come valore di A (cioè come V(A)) 0 e come valore di B (cioè come V(B)) 1,

abbiamo come valore di A B (cioè come V(A B)) 0, che è il minimo tra 0 e 1.

• alla quarta riga, dove abbiamo come valore di A (cioè come V(A)) 0 e come valore di B (cioè come V(B)) ancora 0,

abbiamo come valore di A B (cioè come V(A B)) 0, che è il minimo tra 0 e 0.

Tavola di verità dell’implicazione

A B A B

1 1 1

1 0 0

0 1 1

0 0 1

può essere espressa come

V(A B) := max (1-V(A), V(B))che significa che:

V(A B)l’assegnamento di valore di verità a A B [:= ] è definito con l’operazione che sceglie max (1-V(A), V(B))cioè il massimo tra :

(1-V(A)), ossia ciò che si ottiene sottraendo da 1 il valore di verità di A e

V(B) il valore di verità di B.

Infatti

Osservando la tabella, vediamo che:

• alla prima riga, dove abbiamo come valore di A (cioè come V(A)) 1 e come valore di B (cioè come V(B)) ancora 1,

• abbiamo come valore di A B (cioè come V(A B)) 1, che è il massimo tra:

1-V(A) [cioè 1-1] , che è 0

e V(B) che è 1.

• alla seconda riga, dove abbiamo come valore di A (cioè come V(A)) 1 e come valore di B (cioè come V(B)) 0,

• abbiamo come valore di A B (cioè come V(A B)) 0, che è il massimo tra:

1-V(A) [cioè 1-1] , che è 0 e V(B) che è 0.

• alla terza riga, dove abbiamo come valore di A (cioè come V(A)) 0 e come valore di B (cioè come V(B)) 1,

• abbiamo come valore di A B (cioè come V(A B)) 1, che è il massimo tra:

1-V(A) [cioè 1-0] , che è 1

e V(B) che è 1.

alla quarta riga, dove abbiamo come valore di A (cioè come V(A)) 0 e come valore di B (cioè come V(B)) ancora 0,

• abbiamo come valore di A B (cioè come V(A B)) 1, che è il massimo tra:

1-V(A) [cioè 1-0] , che è 1

e V(B) che è 0.

Tavola di verità della biimplicazione

A B A B

1 1 1

1 0 0

0 1 0

0 0 1

Per cui si capisce subito che:

• V (A B)=1 se e solo se V(A)=V(B).

• Infatti, il valore di verità di è 1 solo alla prima e ultima riga, dove, rispettivamente, A e B hanno entrambi valore 1 e valore 0.

Ultime definizioni

• A questo punto, si possono introdurre le seguenti definizioni relative ad una formula A:

• 1) è una TAUTOLOGIA (o VERITA’ LOGICA) se risulta VERA secondo OGNI ASSEGNAMENTO di verità;

• 2) è una CONTRADDIZIONE (o è REFUTABILE) se risulta FALSA secondo OGNI ASSEGNAMENTO di verità;

• 3) è SODDISFACIBILE se e solo se è vera per almeno un assegnamento.