1.1. Demuestre por inducción en fórmulas que S[α] = 3I[α] + 1 para toda
fórmula α, siendo S la cantidad de śımbolos e I la de paréntesis izquierdos.
Demostración:
Teniendo en cuenta que S es la cantidad de Śımbolos e I la cantidad de
paréntesis izquierdos.
• Paso Inicial:
Si p es letra, entonces S[p] = 3I[p] + 1, pues I[p] = 0, por lo que S[p] =
1 = (3(0) + 1)
• Paso Inductivo:
1. Si S[α] = 3I[α] + 1 entonces S[¬(α)] = 3I[¬(α)] + 1
Veamos que
S[¬(α)] = 3 + S[α]
S[¬(α)] = 3 + (3I[α] + 1)
S[¬(α)] = 3 + (1 + I[α] + 1)
S[¬(α)] = 3I[¬(α)] + 1
Se debe a que I[¬(α)] = 1 + I[α]