Page 22 - MATINF Nr. 6

22 D. Constantin

* Q = {∀, ∃} este mult¸imea cuantificatorilor; simbolul ∀ este cuantificatorul universal,
respectiv simbolul ∃ este cuantificatorul existent¸ial.

Simbolurile non-logice sunt elementele mult¸imii CS ∪ FS ∪ PS unde:

* CS este mult¸imea constantelor.
* FS este mult¸imea simbolurilor functoriale. Fiecare functor f ∈ FS este caracterizat de
un num˘ar natural r (f) ≥ 1 numit aritatea functorului f. (un functor are interpretarea
semantic˘a de funct , ie s , i atunci aritatea reprezint˘a num˘arul de argumente acceptat de
funct , ia respectiv˘a).
* PS este mult¸imea simbolurilor predicat¸ionale. Fiecare predicat π ∈ PS este caracterizat
de un num˘ar natural r (π) ≥ 0 numit aritatea predicatului π.
Presupunˆand c˘a mult¸imile V, L, S, Q, CS, FS, PS sunt dou˘a cˆate dou˘a disjuncte se poate
stabili vocabularul limbajului prin V = V ∪ L ∪ S ∪ Q ∪ CS ∪ FS ∪ PS. Expresiile generate
∗
pe baza vocabularului stabilit pentru limbajul extins sunt elemente ale mult¸imii A = V s , i se
numesc asamblaje.
ˆ
Intr-un limbaj extins identific˘am mult¸imi de structuri simbolice de interes precum mult¸imea
termenilor TERM ¸si mult¸imea de atomi ATOM.

Definit , ia 3. Secvent¸a de asamblaje t 1 , ..., t n este o secvent¸˘a generativ˘a termeni (SGT), dac˘a
pentru orice i, 1 ≤ i ≤ n, t i ˆındepline¸ste una dintre urm˘atoarele condit¸iile:

ι) t i ∈ V ∪ CS

ιι) exist˘a f ∈ FS ¸si exist˘a indicii j 1 , ..., j r(f) cu 1 ≤ j p < i , p = 1, ..., r (f) astfel ˆıncˆat

t i = ft j 1 t j 2 ... t j r(f)
Definit , ia 4. Se numes , te termen orice asamblaj t cu proprietatea c˘a exist˘a n = 1 ¸si t 1 , ..., t n −
SGT, astfel ˆıncˆat t n = t. Mult¸imea termenilor este notat˘a TERM.

Exemplu pentru definirea termenilor ˆın limbajul aritmeticii

Simbolurile non-logice ale limbajului standard al aritmeticii sunt: CS = {0} , FS = {+, ∗, S},
¦ ◦ © € ◦ Š
PS = <, = , unde r (+) = r (∗) = r (<) = r = = 2, r (S) = 1. Simbolul S desemneaz˘a
∆
ˆ
functorul succesor; pentru orice num˘ar natural n, SS...S 0 = n (Observat¸ie: In acest limbaj
| {z }
n
structurile simbolice din mult¸imea TERM sunt reprezent˘ari ale expresiilor aritmetice ˆın scriere
prefixat˘a).
Fie asamblajul t = ∗ + ∗SySSzSSx + xSS0, unde x, y, z ∈ V.

Secvent¸a de asamblaje: t 1 = 0, t 2 = x, t 3 = y, t 4 = z, t 5 = Sx = St 2 , t 6 = Sy = St 3 ,
t 7 = Sz = St 4 , t 8 = SSz = St 7 , t 9 = SSx = St 5 , t 10 = ∗SySSz = ∗t 6 t 8 , t 11 = +∗SySSzSSx =
+t 10 t 9 , t 12 = S0, t 13 = SS0 = St 12 , t 14 = +xSS0 = +t 2 t 13 , t 15 = ∗ + ∗SySSzSSx + xSS0 =
∗t 11 t 14 = t este SGT, deci t ∈ TERM.

Definit , ia 5. Mult¸imea expresiilor de tip atomi notat˘a prin ATOM este definit˘a prin:

ATOM = {π | π ∈ PS, r (π) = 0} ∪

∪ πt 1 ...t r(π) | π ∈ PS, r (π) ≥ 1, t 1 , ..., t r(π) ∈ TERM .