Scrivi un'espressione booleana, guarda il suo albero di parsing, calcola altezza h(F) e lunghezza l(F) — e poi prova a ricostruire la formula risalendo dalle foglie alla radice.

Vai allo strumento ↓

Formazione Digitale · Sistemi · Logica

Cos'è un albero di parsing

Una formula booleana non è solo una stringa di simboli: ha una struttura ad albero che rispecchia l'ordine in cui gli operatori vengono effettivamente applicati. La radice è sempre l'operatore applicato per ultimo (quello a precedenza più bassa, fuori da ogni parentesi); le foglie sono variabili o costanti.

∧Esempio: a ∧ b

La radice ∧ ha due figli: la foglia a (a sinistra) e la foglia b (a destra).

▸Precedenza degli operatori

Operatore	Precedenza
¬	più alta
∧	↓
∨	↓
⊕	↓
→	↓
↔	più bassa

La radice dell'albero è sempre l'operatore a precedenza più bassa tra quelli non già "chiusi" da parentesi: è l'ultimo che viene applicato leggendo la formula.

⎵Le parentesi vincono sempre

Qualunque sia la precedenza, il contenuto di una coppia di parentesi viene risolto (cioè diventa un sotto-albero completo) prima di essere combinato con il resto della formula.

💬 In ¬(a∨b)∧(c→a), sia (a∨b) che (c→a) sono sotto-alberi "chiusi" dalle parentesi prima ancora di applicare ¬ e ∧.

Attenzione all'associatività. Quando lo stesso operatore si ripete senza parentesi, l'ordine con cui si raggruppa non è sempre "da sinistra". In questo strumento: ∧, ∨, ⊕, ↔ si raggruppano da sinistra (es. a∧b∧c = (a∧b)∧c), mentre → si raggruppa da destra (es. a→b→c = a→(b→c)) — è una convenzione standard in logica, ma è facile sbagliarla se non la si conosce.

Prova lo strumento interattivo ↓

Costruttore di alberi di parsing

Scrivi una formula con i simboli (¬∧∨⊕→↔) oppure con le alternative da tastiera (! & | ^ -> <->) e genera il suo albero, con altezza h(F) e lunghezza l(F) calcolate passo per passo.

🔒 Calcolo locale nel browser · Nessun dato inviato · Fino a 4 variabili

Espressione F

Alternative da tastiera:

¬ = ! / not

∧ = & / and

∨ = | / or

⊕ = ^ / xor

→ = -> / impl

↔ = <-> / iff

Esempi:

🌳

Scrivi un'espressione e clicca
Costruisci albero

🧩 Ricostruzione bottom-up

Parti dalle foglie e risali verso la radice: ad ogni passo combini i sotto-alberi già pronti con l'operatore giusto, fino a ricostruire l'intera formula F.

Modalità

🧩

Costruisci prima un albero nella sezione qui sopra,
poi torna qui per ricostruirlo.

Formazione Digitale · Sistemi · Logica

Definizioni induttive di h(F) e l(F)

Due grandezze che descrivono un albero di parsing: l'altezza (quanto è "profondo") e la lunghezza (quanti nodi contiene in totale). Entrambe si definiscono per induzione sulla struttura della formula — esattamente come l'albero stesso è costruito.

hAltezza h(F)

Caso base — F è una variabile o una costante: h(F) = 0.

F = ¬G: h(F) = h(G) + 1.

F = G∧H (oppure ∨, ⊕, →, ↔): h(F) = 1 + max(h(G), h(H)).

💬 È il numero di "livelli" da scendere dalla radice fino alla foglia più lontana.

lLunghezza l(F)

Caso base — F è una variabile o una costante: l(F) = 1.

F = ¬G: l(F) = l(G) + 1.

F = G∧H (oppure ∨, ⊕, →, ↔): l(F) = l(G) + l(H) + 1.

💬 È il numero totale di nodi disegnati nell'albero: variabili, costanti e connettivi.

Perché "induttiva"? Perché ogni regola calcola h e l di una formula a partire da h e l delle sue sotto-formule (i figli nell'albero) — esattamente il modo in cui lo strumento di ricostruzione qui sopra fa risalire i valori dalle foglie alla radice.