Demostrar que la longitud de una fórmula con exactamente \( m \) conectivos binarios es \( 4m+n+1. \)
Hola, quisiera preguntar como resolver este problema. Sabemos que los conectivos binarios son \( \wedge, \vee, \rightarrow{}, \longleftrightarrow \).
En mi cuaderno tengo la siguiente idea (no sé si está bueno).
Por inducción sobre el largo de la palabra. Denotemos por \( \ell(\varphi) \) el número de elementos de la palabra.
Caso base
\( \ell(\varphi)=1 \), pero las únicas fórmulas de longitud 1 son las variables proposicionales. ¿Qué pasa si tiene longitud mayor?
Mi hipótesis de inducción es que funcione para algo menor que algo. Todas las palabras de longitud menor o igual que \( n \) satisfacen la conclusión. Supongamos que \( \ell(\varphi)\ge n+1. \) Entonces, \( \varphi=\~A \) o \( \varphi=(A\star B) \) en \( \star \in \{\wedge, \vee, \rightarrow, \longleftrightarrow\} \).