Problemas_de_matemática_discreta

G. P. GAVRÍLOV A. A. SAPOZHENKO PROBLEMAS de MATEMÁTICA DISCRETA Editorial MIR Moscú ИЗДАТЕЛЬСТВО МИР Г. П. Гаврилов, А. А. Сапоженко СБОРНИК ЗАДАЧ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ Издательство «НАУКА» Москва G.P.GAVRÍLOV A.ASAPOZHENKO PROBLEMAS de MATEMÁTICA DISCRETA Editorial MIR Moscú Traducido del ruso por Bernardo del Río Salceda, candidato a doctor en ciencias técnicas На испанском языке © Главная редакция физико-математической литературы издательства «Наука», 1977 © Traducción al español. Editorial Mir. 1980 Impreso en la URSS. 1980 INDICE Introducción ......................................................... 7 CAPITULO I. LAS FUNCIONES DE BOOLE, SUS FORMAS DE DESIGNACION [Y]SUS PROPIEDADES PRINCIPALES .................................. 11 § 1. Vectores de Boole y el cubo unidad n-dimensional .............. 11 § 2. Formas de expresión de las funciones de Boole. Funciones ele- mentales. Fórmulas. Operación de superposición ..... 21 § 3. Tipos especiales de fórmulas. Formas normales disyuntivas y con- juntivas. Polinomios .......................................... 30 § 4. Minimización de las funciones de Boole ..................... 37 § 5. Variables sustanciales y ficticias .......................... 43 CAPITULO II, CLASES CERRADAS Y PLENITUD .......................... 47 § 1. Operación de clausura. Clases cerradas ........................ 48 § 2. Dualidad y clase de funciones autoduales ...................... 52 § 3. Linealidad y clase de funciones lineales ....................... 55 § 4. Clases de funciones que conservan las constantes ............. 58 § 5. Monotonía y clase de funciones monótonas ................. 61 § 6. Plenitud y clases cerradas ................................. 66 CAPITULO III. LOGICAS k-VALENTES ................................ 71 § 1. Representación de las funciones de las lógicas k-valentes con fór- mulas de tipo especial ....................................... 71 § 2. Clases cerradas de la lógica k-valenta ..................... 79 § 3. Estudio de la plenitud de las funciones de la lógica k-valente ..... 85 CAPITULO IV. GRAFOS Y REDES .................................. 91 § 1. Conceptos fundamentales de la teoría de los grafos ......... 91 § 2. Planicidad, conexión, características numerales de los grafos ... 99 § 3. Grafos orientados .......................................... 104 § 4. Arboles y redes bipolares .................................. 112 § 5. Evaluaciones en la teoría de los grafos y redes ............... 120 § 6. Realización de las funciones booleanas por medio de esquemas de contacto y de fórmulas ...................................... 129 CAPITULO V. ELEMENTOS DE LA TEORIA DE CODIFICACION .......... 138 § 1. Códigos con corrección de errores .............................. 138 § 2. Códigos lineales ............................................... 142 § 3. Codificación alfabética ........................................ 146 CAPITULO VI. AUTOMATAS FINITOS ...................................... 154 § 1. Funciones determinadas y de determinación acotada ............... 154 § 2. Representación de funciones determinadas con diagramas de Moo- re, con funciones canónicas, con tablas y con esquemas. Opera- ciones sobre las funciones determinadas ................. 164 § 3. Clases cerradas y plenitud en los conjuntos de funciones determi- nadas y acotadas-determinadas .......................... 180 CAPITULO VII. ELEMENTOS DE LA TEORIA DE LOS ALGORITMOS ............ 185 § 1. Máquinas de Turing y operaciones a las que se someten. Funcio- nes calculables en las máquinas de Turing ............... 185 § 2. Clases de funciones calculables y recursivas .................... 203 § 3. Calculabilidad y complejidad de los cálculos .................... 210 CAPITULO VIII. ELEMENTOS DE COMBINATORIA ........................... 215 § 1. Permutaciones y combinaciones. Propiedades de los coeficientes binominales ............................................ 215 § 2. Fórmula de inclusiones y exclusiones ............................ 224 § 3. Sucesiones regresivas, funciones generatrices, relaciones recurrentes ....................................................... 225 § 4. Evaluaciones asintóticas y desigualdades ....................... 234 Soluciones, resultados «soluciones» ............................... 265 Bibliografía ....................................................... 279 Indice alfabético de materias ..................................... 309 INTRODUCCION Esta colección de problemas que se propone al lector se proyectó como un manual de ejercicios para la asignatura de matemática discreta destinado fundamentalmente para los estudiantes de los primeros cursos de las universidades. También puede ser útil para los estudiantes de los cursos superiores y los aspirantes a doctor que se especializan en el terreno de la matemática discreta. Los profeso- res pueden emplear este libro al preparar las clases prácticas. El libro se basa en el curso de matemática discreta que se dio durante una serie de años en la facultad mecánico-matemática y aho- ra en la facultad de matemática de cómputo y cibernética de la Uni- versidad estatal de Moscú. El libro se compone de ocho capítulos. Los dos primeros están dedicados a la lógica algebraica. La sección dedicada a la lógica alge- braica es fundamental en el estudio de la matemática discreta. En la facultad de matemática de cómputo y cibernética de la Universidad de Moscú esta sección ocupa una cuarta parte del tiempo dedicado a las conferencias y ejercicios prácticos. A base de este material los estudiantes adquieren los primeros conocimientos sobre tales con- ceptos como función discreta, operación de superposición, sistema funcionalmente completo; asimilan las diferentes formas de presen- tación de las funciones discretas (en forma de tablas, representación con polinomios y formas normales, representación geométrica con el empleo del cubo unidad n-dimensional); estudian los procedimientos de investigación de la plenitud y propiedad de cerrado de los siste- mas de funciones. El tercer capítulo está dedicado a las lógicas k-valentes. Los problemas aquí presentados persiguen el fin de iniciar al lector en la descomposición canónica de las funciones k-valentes con trans- formaciones equivalentes de las fórmulas, en las principales clases cerradas de funciones de lógica k-valente y en los métodos de invest- tigación de la plenitud y propiedad de cerrado de sistemas de fun- ciones. En una serie de problemas se ilustra la diferencia que existe entre las lógicas k-valentes (k ⩾ 2) y la lógica algebraica. El capítulo cuatro contiene problemas de la teoría de los grafos (orientados y no orientados), de la teoría de las redes y de esquemas. El objetivo de esta sección es dar a conocer al estudiante los concep- tos fundamentales, los metodos y el lenguaje de la teoría de los gra- fos. Todo esto se emplea muy ampliamente para describir e investiga- car las propiedades de las estructuras de los objetos en los más va- riados terrenos de la ciencia y de la técnica. En esta parte hay pro- blemas predestinados a afirmar los conocimientos de los conceptos principales de la teoría de los grafos; problemas que ilustran la apli- cación de la teoría de los grafos y las redes a la síntesis de es quemas que realizan funciones booleanas; problemas de cálculo de objetos con una estructura geométrica dada, etc. Los autores esperan que los profesores también encontrarán aquí problemas con la ayuda de los cuales podrán enseñar a los estudiantes a hacer rigurosas de- mostraciones matemáticas de afirmaciones geométricas evidentes. El quinto capítulo está dedicado a la teoría de la codificación. Los problemas presentados tratan sobre las propiedades de los códi- gos que corrijen errores; sobre los códigos alfabéticos; sobre los có- digos con mínimo exceso. El capítulo sexto contiene problemas que muestran diferentes modos de descripción de l os sistemas matemáticos discretos (autómatas). Se han incluido problemas para revelar la determinación y la determi- nación acotada de los autómatas; para presentar autómatas de dife- rentes maneras: por medio de diagramas, de ecuaciones canónicas, de esquemas; para investigar la plenitud funcional y la cerrabilidad de los sistemas de aplicaciones automáticas; para estudiar las pro- piedades de las diferentes operaciones a las que se pueden someter dichas aplicaciones. El séptimo capítulo, dedicado a los elementos de la teoría de los algoritmos, tiene como fin dar nociones sobre la eficacia de la cal- culabilidad y la complejidad de los cómputos, sobre ciertas formas concretas de definición del algoritmo (máquinas de Turing y funcio- nes recursivas). El capítulo ocho tiene un carácter auxiliar y está dedicado a la combinatoria. Esta parte sale de los límites del curso universitario de la matemática discreta. No obstante, el que estudia la matemá- tica discreta frecuentemente choca con cuestiones sobre su existen- cia, el cálculo y la evaluación de diferentes objetos combinatorios. Por este motivo los autores han considerado útil incluir también proble- mas sobre Combinatoria. Actualmente todavía no existe un manual que abarque por com- pleto los materiales teóricos del programa del curso universita- rio de la asignatura «matemática discreta. El primer tomo de la mono- grafía «La matemática discreta y las cuestiones matemáticas de la 8