Teoría de la computación. Apuntes y ejercicios En este capítulo vamos a repasar escuetamente conceptos elementales que el lector ya debiese conocer, y después introduciremos elementos más relacionados con la materia. La mayor parte de las definiciones, lemas, etcétera de este capítulo no están indizados en el índice de Materias al final del apunte, puesto que son demasiado básicos. indexamos solo lo que se refiere al tema concreto de lenguajes formales, dificultad, y computabilidad. No vamos a repasar el lenguaje de la lógica de predicados de primera importancia, que usaremos de manera directa, ni nada sobre números. Inducción Estructural En muchas demostraciones del curso vamos a hacer inducción sobre estructuras definidas recursivamente. La inducción natural que se supone que el lector ya conoce, (P (0) A (P(n) ^ P (n + 1)) ^ Vn 0, P(n)), puede extenderse a estas estructuras recursivas. Fundamentalmente lo que se hace es aplicar inducción natural sobre alguna propiedad de la estructura (como su tamaño), de tal modo que pueda suponerse que la propiedad sirve para sus subestructuras. Veamos un caso. Un árbol binario es o un nodo hoja o un nodo interno del que cuelgan 2 árboles binarios. Llamemos i(A) y h(A) a la cantidad de nodos internos y nodos hojas, respectivamente, de un árbol binario A. Probemos por inducción estructural que, para todo árbol binario A, i(A) = h(A) — 1. Caso base: Si el árbol A es un nodo hoja, entonces tiene cero nodos internos y una hoja, y la proposición vale puesto que i (A) = 0 y h(A) = 1. Caso inductivo: Si el árbol A es un nodo interno del que cuelgan subárboles A1 y A2, tenemos por hipótesis inductiva que i(A1) = h(A1) — 1 y i(A2) = h(A2) — 1. Ahora bien, los nodos de A son los de A1, los de A2, y un nuevo nodo interno. De forma que i(A) = i(Ai) + i(A2) + 1 y h(A) = h(Ai) + h(A2). De acá que i(A) = h(Ai) — 1 + h(A2) — 1 + 1 = h(A1) + h(A2) — 1 = h(A) — 1 y hemos terminado