Dimostrazione: numero di sottoformule di una formula con n connettivi

Prima di postare leggi le regole del Forum. Puoi anche leggere le ultime discussioni.

Dimostrazione: numero di sottoformule di una formula con n connettivi #51878

avt
WhiteC
Frattale
Ciao ragazzi emt 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! emt
 
 

Dimostrazione: numero di sottoformule di una formula con n connettivi #51887

avt
Ifrit
Amministratore
Procedere con il principio di induzione mi pare una buona cosa emt

Prima di procedere però vorrei sapere la definizione di connettivo che ti ha fornito il tuo insegnante emt
Ringraziano: Galois, Bellissimarosa

Dimostrazione: numero di sottoformule di una formula con n connettivi #51888

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

Dimostrazione: numero di sottoformule di una formula con n connettivi #51896

avt
Ifrit
Amministratore
Questo è un tentativo di dimostrazione emt

Sia \phi una formula con 0 connettivi, allora il numero di sottoformule, che indico con N_{\phi} è 1.

Il passo base è soddisfatto.

Passo induttivo:

Supponiamo che la formula \phi abbia k-1 connettivi. Supponiamo inoltre che il numero di sottoformule di N_{\phi}\le 2k-1 (è l'ipotesi induttiva)


Passo conclusivo:

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

\Phi=\phi\square \psi

Per ipotesi induttiva \phi ha k-1 connettivi a cui aggiungiamo l'ulteriore connettivo \square così da averne k. \psi è una sottoformula senza connettori.

allora il numero di sottoformule di \Phi è al più 2k+1 perché \phi ha al più 2k-1 sottoformule a cui vanno aggiunte \psi e \Phi stessa dunque:

N_{\Phi}\le 2k+1

Spero funzioni emt
Ringraziano: Omega, Pi Greco, Galois
  • Pagina:
  • 1
Os