EDB — 1YS

3.1 Logica[1YS]

[23H]↺↻

Proposizioni

[23J]↺↻

Una proposizione può dipendere da alcune variabili. Esempi:

• “la persona x di mestiere fa il panettiere”,

• “il numero x è maggiore di 9”.

Scriveremo

per dire che \(P(x)\) è il simbolo che riassume la proposizione scritta a destra.

Logica proposizionale

[ [00F]↺↻] [1YK]↺↻ [ [00H]↺↻] Dunque una formula ben formata è una “proposizione logica” in quanto assume valore di verità o di falsità, a seconda del valore dato alle sue variabili libere. Possiamo allargare la definizione aggiungendo che le proposizioni viste nella sezione precedente sono “formule atomiche”; ad esempio

sarà anch’essa una “formula ben formata”.

Per comodità, in questa Sezione, aggiungiamo al linguaggio anche le costanti \(V\) e \(F\) che sono rispettivamente sempre vere e sempre false, in ogni valutazione.  ¹ Nella costruzione delle formule ben formate vengono trattate come le variabili. Notate che non abbiamo introdotto il connettivo di uguaglianza “\(=\)”. Quando tutte le variabili possono assumere solo i valori vero/falso, l’uguaglianza \(a=b\) può essere interpretata come \(a\iff b\). In contesti più generali (come nel caso della teoria degli insiemi) invece “l’uguaglianza” necessita di una precisa definizione.

E7

[1VY]↺↻

E7

[00K]↺↻

E7

[00N]↺↻

E7

[22C]↺↻

E7

[2G8]↺↻

Logica del primo ordine

Nella logica del primo ordine si aggiungono i connettivi \(∀\), che si legge “per ogni” e \(∃\), che si legge “esiste”. Dobbiamo dunque allargare la famiglia delle formule ben formate.

In ogni parte di una formula in cui una variabile è quantificata, questa variabile può essere sostituita con ogni altra variabile.

Notate che, in molti esempi, si suppone che le variabili quantificate siano elementi di un “insieme”.

Usiamo qui il termine “insieme” in maniera informale, si veda la nota [01J]↺↻.

Dato che un elemento di un insieme potrebbe non avere un valore di verità/falsità, arricchiamo il linguaggio aggiungendo le “proposizioni logiche”.

Un esempio di proposizione logica potrebbe essere: “\(n\) è un numero pari”. Possiamo usare le proposizioni logiche come atomi nella costruzione delle formule ben formate.

E14

[00V]↺↻

E14

[00X]↺↻

E14

[00Z]↺↻

E14

[011]↺↻

E14

[016]↺↻

E14

[013]↺↻