Page 21 - MATINF Nr. 4

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

Exemplul 3. Prin traversarea r-s-d a arborelui de structur˘a al formulei,

α = ((¬ ((¬a) ∨ b)) ↔ (a ∧ (¬b))) ,

rezult˘a secvent , a de vˆarfuri:

r, n 1 , n 2 , n 3 , n 4 , n 5 , n 6 , n 7 , n 8 , n 9 ,

secvent , a etichetelor corespunz˘atoare lor fiind

↔ ¬ ∨ ¬ab ∧ a¬b,

deci reprezentarea α prefix . Prin traversarea s-d-r a arborelui de structur˘a rezult˘a secvent , a de
vˆarfuri
n 4 , n 3 , n 5 , n 2 , n 1 , n 7 , n 9 , n 8 , n 6 , r,

secvent , a etichetelor corespunz˘atoare lor fiind

a¬b ∨ ¬ab¬∧ ↔,

deci reprezentarea α postfix .

Complexitatea structural˘a a formulelor logice se poate exprima prin intermediul valorilor
funct , iei adˆancime.

Definit , ia 3. Funct ,ia adˆancime ~: FORM−→ N este definit˘a prin: α ∈ FORM,


 0, dac˘a α ∈ V,
~ (α) = 1 + ~ (β) , dac˘a α = (¬β) ,
1 + max {~ (β) , ~ (γ)} , dac˘a α = (βργ) , ρ ∈ L \ {¬} .


Exemplul 4. Se va aplica definit , ia dat˘a pentru formula logic˘a:

α = ((¬ ((¬a) ∨ b)) ↔ (a ∧ (¬b))) .

Se obt , ine:
~ (α) = 1 + max {~ (β) , ~ (γ)} ,

unde β = (¬ ((¬a) ∨ b)) , γ = (a ∧ (¬b))

~ (β) = 1 + ~ (((¬a) ∨ b)) = 2 + max {~ ((¬a)) , ~ (b)} =
= 2 + max {1 + ~ (a) , 0} = 2 + max {1, 0} = 3

~ (γ) = 1 + max {~ (a) , ~ ((¬b))} = 1 + max {0, 1 + ~ (b)} = 2

Rezult˘a ~ (α) = 1 + max {~ (β) , ~ (γ)} = 1 + max {3, 2} = 4.

Observat ,ia 4. Pentru orice α ∈ FORM, valoarea ~ (α) exprim˘a ˆın˘alt , imea arborelui de structur˘a
T(α) corespunz˘ator formulei α.