Alfabeto

Definizione: Un linguaggio del primo ordine è definito da un alfabeto $A$, costituito da:

• un insieme finito $VAR$ di simboli di variabile $x, y, z, ...$;
• un insieme di simboli di costante $a, b, ..., c_1,c_2,...$;
• un insieme di simboli di funzione $f, g, h, ..., f_1, f_2, ..., g_1, g_2,...,$ ognuno con associata la sua arietà (numero di argomenti);
• un insieme di simboli di predicato $A, B, ..., P, P_1, P_2, ..., Q, Q_1, Q_2,...$, ognuno con associata la sua arietà.

Osservazioni:

• Quando si costruiranno delle formule, si sceglierà l’alfabeto sulla base del mondo che si vorrà modellare: in un certo senso, i simboli che compaiono nell’alfabeto sono ciò che crea la corrispondenza tra il linguaggio formale e gli elementi del mondo considerato. Infatti, gli lfabeti sono costituiti da una parte fissa, l’insieme di simboli di variabile, e da tre parti dipendendi dal dominio: i simboli di costante, di funzione e di predicato.
• Le variabili della logica del primo ordine indicano elementi del dominio, diversamente dalle variabili proposizionali, che rappresentano formule (atomiche).
• Formalmente, un alfabeto è composto da simboli di variabile, costante, funzione e predicato. In pratica, per semplicità, spesso si parlerà di variabili, costanti, funzioni e prdicati (omettendo “simbolo di”).
• In ambito informatico, quando si utilizza la logica per formalizzare dei problemi, spesso un alfabeto viene chiamato segnatura.

Simboli logici

Un’altra parte fissa del linguaggio, usata insieme all’alfabeto (che specifica il “lessico” di base) per costruire le formule, sono i simboli logici:

Definizione: I simboli logici utilizzati da un linguaggio del primo ordine sono:

• i connettivi proposizionali: $\land, \lor, \rarr\neg;$
• i quantificatori: $\forall, \exist;$
• le parentesi: $"(", ")".$

Nella logica del primo ordine, i quantificatori agiscono sulle variabili individuali. Invece, nelle logiche di ordini superiori la quantificazione può avvenire su elementi più complessi: ad esempio, nella logica del secondo ordine, i quantificatori agiscono sui predicati (che rappresentano sostanzialmente insiemi di elementi del dominio).

Termini

Definizione: L’insieme $TERM$ dei termini (su un alfabeto $A$) è così definito: