Page 19 - MATINF Nr. 4

Elemente computat , ionale de deduct , ie logic˘a 19

Definit , ia 2. Un arborele binar (T = (V (T), E(T)), cu V (T) reprezentˆand mult ,imea nodurilor
din arbore, iar E(T) reprezentˆand mult ,imea muchiilor din arbore, muchiile fiind precizate
prin perechile de noduri definite la nivelul arborelui considerat), direct ,ionat, avˆand r˘ad˘acina s , i
vˆarfurile etichetate cu simboluri din mult ,imea V ∪ L este arbore de structur˘a dac˘a etichetele
vˆarfurilor sunt definite astfel ˆıncˆat, pentru orice vˆarf n ∈ V (T) avem:

(i) dac˘a od (n) = 0 atunci ϕ (n) ∈ V ;
(ii) dac˘a od (n) = 1 atunci ϕ (n) = ¬;
(iii) dac˘a od (n) = 2 atunci ϕ (n) ∈ L \ {¬}
unde od (n) reprezint˘a num˘arul de descendent ,i direct ,i ai vˆarfului n, iar ϕ (n) este eticheta
vˆarfului n.

Observat ,ia 3. Fiecare formul˘a logic˘a din limbajul de calcul cu propozit , ii logice α poate fi
reprezentat˘a printr-un arbore de structur˘a T (α) ˆın acord cu definit , ia de mai sus. Construct , ia
arborelui de structur˘a T (α) poate fi realizat˘a recursiv utilizˆand definit , ia arborelui de structur˘a,
precum s , i observat , ia 2 (iii) astfel:
(i) dac˘a α ∈ V atunci
T (α) : r
s , i ϕ (r) = α;
(ii) dac˘a α = (¬β) atunci
r
T (α) : ↓ ,
T (β)
unde ϕ (r) = ¬ s , i T (β) este arborele de structur˘a al formulei β;
(iii) dac˘a α = (βργ) cu ρ ∈ L \ {¬} atunci

r
T (α) : .& ,
T (β) T (γ)

unde ϕ (r) = ρ s , i T (β) , T (γ) sunt arborii de structur˘a corespunz˘atori formulelor β,
respectiv, γ.
Exemplul 2. Se consider˘a o formul˘a logic˘a α s , i se construies , te arborele de structur˘a asociat T(α)
folosind abservat , ia 3. Se consider˘a formula α = ((¬ ((¬a) ∨ b)) ↔ (a ∧ (¬b))).

Deoarece α = (βργ) cu ρ =↔, β = (¬ ((¬a) ∨ b)) s , i γ = (a ∧ (¬b)) obt , inem

r
T (α) : .& ,
T (β) T (γ)

unde ϕ (r) =↔.
Deoarece β = (¬β 1 ), unde β 1 = ((¬a) ∨ b), obt , inem,

n 1
T (β) : ↓ ,
T (β 1 )

ϕ (n 1 ) = ¬.