Logica: Induzione

[vinid]

Ciao a tutti,

Sto studiando per un esame e sul mio libro di logica mi sono imbattuto in due esercizi che non so bene come risolvere:

1)Si definisca mediante induzione strutturale una struttura ad albero.

2)Si definisca mediante ricorsione strutturale l’insieme degli Antenati a partire
dall'insieme dei Genitori.

Qualcuno è in grado di darmi una mano? Grazie mille

[hamming_burst]

Ciao,
prima di tutto definisci un insieme di assiomi: come radice, nodo, foglia. Poi definisci una relazione che lega queste tre definizioni creando un albero di livello 1 e poi generalizzi.

Devi dimostrare tramite induzione strutturale ciò che hai definito (la relazione) costruisce veramente un albero.

[vinid]

Ok, per gli assiomi più o meno credo di aver risolto così, anche se non sono sicuro:
radice: elemento che ha solo archi uscenti
nodo: elemento che ha un solo arco entrante e almeno uno uscente
foglia: elemento con un arco entrante e senza archi uscenti

Non saprei a questo punto costruire la relazione che li collega, devo usare la definizione di albero?

Grazie mille della risposta

[hamming_burst]

Per costruire strutturalmente un albero devi utilizzare una delle sue definizioni.
Parti come base induttiva con il nodo e poi passo induttivo le varie componenti. Perciò dimostrato che le componenti di un albero sono anch'esse un albero (radice, foglia, ...) tramite la sua definizione, dimostrerai che anche la sua generalizzazione lo è.

[vinid]

Vediamo se ho capito:

Passo Base: Un singolo nodo è un albero, che viene definito radice
Passo Induttivo: Considerando diversi alberi e un nuovo nodo K, se connetto le radici degli alberi con K avrò sempre un albero con radice in K


Può essere così? Grazie Mille di nuovo

[hamming_burst]

mmm si dai...

La struttura di definizione struturale deve essere che componendo dei nodi si crei una struttura ad albero.

Passo base:
- specializzi la definizione di nodo in radice
passo induttivo:
- specializzi un nodo in foglia e costruisci una struttura radice-foglia (tramite la definizione)
- generalizzi il tutto (tramite la definizione)

direi che così informalmente potrebbe andare...

[vinid]

Grazie Mille! All'esame sono stato più preciso in questo esercizio e ho tentato di essere meno informale! Grazie Mille ancora!