Logica: Metodo Breve by Daniele Mundici

autore:Daniele Mundici [Mundici, Daniele]
La lingua: ita
Format: epub
Tags: Mathematics, Logic, Language Arts & Disciplines, Linguistics, Semantics, History & Philosophy, General, Discrete Mathematics
ISBN: 9788847018846
Google: tyiMqIGL1XIC
editore: Springer Science & Business Media
pubblicato: 2011-05-01T17:37:33+00:00

13 Significato delle clausole

già abbiamo fatto nella Definizione 12.7 e nel Lemma 12.9, per ogni termine t scriviamo t(x1, … , xn) per dire che le variabili in t appartengono all’insieme

{x1, … , xn}. Lo stesso significato hanno L(x1, … , xn) oppure C(x1, … , xn), quando L è un letterale e C è una clausola. Scriveremo x come abbreviazione della n-pla (x1, … , xn). Non useremo il connettivo di implicazione e il quantificatore esistenziale fino al Capitolo 16.

Definizione 13.2. Siano dati un termine t = t(x1, … , xn), un modello M =

(M,∗ ) e una n-pla m = (m1, … , mn) ∈ Mn. Per induzione sul numero di simboli di funzione occorrenti in t, definiamo l’elemento tM[m] di M come segue:

aM[m] = a∗, per ogni simbolo di constante a

(13.1)

(m evidentemente non ha alcun ruolo);

xM

i [m] = mi ;

(13.2)

e per ogni simbolo di funzione k-aria f e k-pla (t1, … , tk) di termini, (f (t1, … , tk))M[m] = f∗(tM

1 [m], … , tM

k [m]).

(13.3)

Data una p-pla di termini r = (r1(x1, … , xn), … , rp(x1, … , xn)) si definisce analogamente rM[m] = (rM

1 [m], … , rM

p [m]).

Dunque per dare significato a un termine t = t(x1, … , xn) in un modello M abbiamo dovuto accompagnare M con una n-pla di elementi m1, … , mn del suo universo. Per come abbiamo definito t(x1, … , xn), non è detto che ogni variabile xi occorra in t. In realtà basta accompagnare M con tanti elementi quante sono le variabili che occorrono effettivamente in t. In particolare quando t è ground, possiamo accompagnare M con la 0-pla vuota ∅, che naturalmente non scriveremo. In questo caso la definizione (13.3) prende la forma semplificata

(f (t1, … , tk))M = f∗(tM

1 , … , tM

k ).

(13.4)

Per ogni p-pla s = (s1, … , sp) di termini ground useremo la notazione sM = (sM

1 , … , sM

p ).

(13.5)

Esempio 13.3. Sia τ = {c, s, f, g}, e sia M il modello di tipo τ il cui universo è l’insieme N = {0, 1, 2, …} dei numeri naturali, e in cui c∗, s∗, f ∗, g∗ sono rispettivamente lo zero, il successore, la somma e il prodotto. Sia t il termine dato da f (g(c, s(x)), f (x, y)). Allora tM[(3, 7)] = (0 · (3 + 1)) + (3 + 7) = 10.

Esercizio 13.4. Fermo restando lo stesso termine t(x, y) dell’esempio precedente, costruisci un modello Q = (Q, ) di tipo τ avente per universo i numeri razionali e in cui c , s , f , g sono definiti in modo che tQ[(1, 0)] = −1.

13.2 La semantica di Tarski per le clausole: M |= S

75

Vi è una relazione degna di nota tra la sostituzione (un’operazione puramente sintattica che trasforma espressioni in espressioni) e l’operazione g → gM (che trasforma il termine ground g in un elemento dell’universo del modello M):

Lemma 13.5. Sia t = (t1(x1, … , xn), … , tp(x1, … , xn)), e g = (g1, … , gn),

ove ogni gi è un termine ground.

scaricare

Disconoscimento:
Questo sito non memorizza alcun file sul suo server. Abbiamo solo indice e link                                                  contenuto fornito da altri siti. Contatta i fornitori di contenuti per rimuovere eventuali contenuti di copyright e inviaci un'email. Cancelleremo immediatamente i collegamenti o il contenuto pertinenti.