Page 18 - MATINF Nr. 4

18 D. Constantin, A.F. S , tefan

Pe mult , imea {T, F} se definesc operat , iile logice:

¬ : {T, F} → {T, F} (negat , ia logic˘a)
2
∧ : {T, F} → {T, F} (conjunct , ia logic˘a)
2
∨ : {T, F} → {T, F} (disjunct , ia logic˘a)
2
→: {T, F} → {T, F} (implicat , ia logic˘a)
2
↔: {T, F} → {T, F} (echivalent , a logic˘a)

cu urm˘atoarele tabele de definire a valorilor de adev˘ar rezultate asociate fiec˘arei conective logice
pentru toate combinat , iile valorilor de adev˘ar corespunz˘atoare pentru dou˘a propozit , ii logice ce
pot avea valorile T sau F:

∧ T F ∨ T F → T F ↔ T F
¬ T F
T T F T T T T T F T T F
F T
F F F F T F F T T F F T

Regulile de bun˘a formare pentru structurile simbolice din mult , imea FORM se formuleaz˘a
pe baza not , iunii de SGF (Secvent , ˘a Generativ˘a Formule).

Definit , ia 1. Secvent ,a de asamblaje α 1 , α 2 , . . . , α n este SGF, dac˘a pentru orice i, 1 ≤ i ≤ n,
este ˆındeplinit˘a una dintre condit ,iile:

(i) α i ∈ V,
(ii) exist˘a j, 1 ≤ j < i astfel ˆıncˆat α i = (¬α j ),
(iii) exist˘a j, k, 1 ≤ j, k < i s , i exist˘a ρ ∈ L \ {¬} astfel ˆıncˆat α i = (α j ρα k ).

Observat ,ia 1. Fie α un asamblaj. Atunci, exist˘a n ≥ 1 s , i α 1 , α 2 , . . . , α n – SGF astfel ˆıncˆat
α n = α dac˘a s , i numai dac˘a α ∈ FORM.

Exemplul 1. Pentru formula
α = ((¬ ((¬a) ∨ b)) ↔ (a ∧ (¬b))) ,

putem construi urm˘atorul SGF:

a, b, (¬a) , (¬b) , (a ∧ (¬b)) , ((¬a) ∨ b) , (¬ ((¬a) ∨ b)) ,((¬ ((¬a) ∨ b)) ↔ (a ∧ (¬b))) = α.
Observat ,ia 2. (i) Dac˘a α ∈ V atunci secvent , a α este SGF, deci V ⊂ FORM;
(ii) Dac˘a α 1 , α 2 , . . . , α n este SGF, atunci pentru orice i, 1 ≤ i ≤ n, α 1 , α 2 , . . . , α i este SGF.
Cu alte cuvinte, toate componentele unui SGF sunt formule logice;
(iii) Delimitarea rezultat˘a prin utilizarea parantezelor pentru structurile simbolice din FORM \
V permite identificarea conectivei principale corespunz˘atoare fiec˘arei formule care nu este
ˆ
propozit , ie elementar˘a. Intr-adev˘ar, orice formul˘a α ∈ FORM \ V se ˆıncadreaz˘a pe un
singur s , ablon dintre α = (¬β) sau α = (βργ) cu ρ ∈ L \ {¬}. Dac˘a α = (¬β) atunci
conectiva principal˘a a formulei α este “¬” s , i, respectiv, dac˘a α = (βργ) atunci α are
conectiva principal˘a “ρ”.

1.2 Reprezentarea arborescent˘a a formulelor logice s , i funct , ia de
adˆancime

Pentru structurile simbolice din mult , imea FORM se poate utiliza s , i o variant˘a alternativ˘a de
reprezentare s , i anume cu ajutorul arborilor de structur˘a asociat , i formulelor logice.