Dimostrazione: numero di sottoformule di una formula con n connettivi

Ciao ragazzi ho questa dimostrazione da svolgere sul numero di sottoformule di una formula con n connettivi logici:

dimostrare che una formula in cui compaiono n connettivi ha al più 2n+1 sottoformule.

Ho pensato di poterla dimostrare per induzione:

- se n=0 allora la formula ha 1 sottoformula e quindi ci siamo;

- poi non riesco più ad andare avanti. :(

Mi date una mano per favore? Come posso procedere per svolgere questa dimostrazione?

Grazie a tutti!

Procedere con il principio di induzione mi pare una buona cosa

Prima di procedere però vorrei sapere la definizione di connettivo che ti ha fornito il tuo insegnante

ciao ifrit, per connettivi intende i 5 connettivi booleani ovvero la negazione, la congiunzione, la disgiunzione, implicazione e doppia implicazione

Questo è un tentativo di dimostrazione

Sia una formula con connettivi, allora il numero di sottoformule, che indico con è 1.

Il passo base è soddisfatto.

Passo induttivo:

Supponiamo che la formula abbia connettivi. Supponiamo inoltre che il numero di sottoformule di (è l'ipotesi induttiva)


Passo conclusivo:

Cosa succede ora? Aggiungiamo un connettivo alla formula così da ottenere una nuova formula:



Per ipotesi induttiva ha connettivi a cui aggiungiamo l'ulteriore connettivo così da averne . è una sottoformula senza connettori.

allora il numero di sottoformule di è al più perché ha al più sottoformule a cui vanno aggiunte e stessa dunque:



Spero funzioni