occorrenza

occorrenza

occorrenza termine che, riferito a un simbolo s, ne indica la presenza all’interno di una formula F di un linguaggio formale. Vi sono 1, 2, 3, ..., n occorrenze del simbolo s nella formula F se s compare in essa 1, 2, 3, ..., n volte. Per esempio, nella formula x + 2 = 3y + 1, il simbolo + ha due occorrenze mentre la variabile y ha una sola occorrenza. Nei linguaggi logici che contengono quantificatori, come per esempio il linguaggio dei predicati, o comunque operatori, quali il lambda-calcolo, è importante distinguere le occorrenze libere dalle occorrenze vincolate (o legate) di una stessa variabile. Una occorrenza libera si ha quando la variabile non rientra nel campo di azione di alcun operatore o quantificatore; altrimenti, si ha una occorrenza vincolata. Per esempio, nell’espressione del linguaggio dei predicati (x = y) ⇒ ∀x(x + 1 = y + 1) la variabile x ha tre occorrenze, di cui la prima è libera mentre le altre due sono vincolate in quanto la variabile compare nel campo d’azione del quantificatore ∀; la variabile y ha invece due occorrenze, entrambe libere.