Problemas_de_matemática_discreta

G. P. GAVRÍLOV\nA. A. SAPOZHENKO\nPROBLEMAS de MATEMÁTICA DISCRETA\nEditorial\nMIR\nMoscú Издательство\nМИР Г. П. Гаврилов, А. А. Сапоженко\nСБОРНИК ЗАДАЧ ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ\nИздательство «НАУКА»\nМосква G. P. GAVRILÓV\nA. A. SAPOZHENKO\nPROBLEMAS de MATEMÁTICA DISCRETA\nEditorial MIR\n Moscú Traducido del ruso por\nBernardo del Río Salceda, candidato\na doctor en ciencias técnicos\n\nНа испанском языке\n\n© Главная редакция Физико-математической\nлитературы издательства «Наука», 1977\n© Traducción al español. Editorial Mir. 1980\n\nImpreso en la URSS. 1980 INDICE\nIntroducción . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7\n\nCAPÍTULO I. LAS FUNCIONES DE BOOLE, SUS FORMAS DE DESIGNACIÓN\nY SUS PROPIEDADES PRINCIPALES . . . . . . . . . . . . . 11\n§ 1. Vectores de Boole y el cubo unidad n-dimensional . . . . . . . . . 11\n§ 2. Formas de expresión de las funciones de Boole. Funciones ele- . . . . .\n montales, Fórmulas. Operación de superposición . . . . . . . 21\n§ 3. Tipos especiales de fórmulas. Formas normales disyuntivas y con- . . . .\n juntivas. Polinomios . . . . . . . . . . . . . . . . . . . . . . 30\n§ 4. Minimización de las funciones de Boole . . . . . . . . . . . . . . 37\n§ 5. Variables sustanciales y ficticias . . . . . . . . . . . . . . . 43\n\nCAPÍTULO II. CLASES CERRADAS Y PLENITUD . . . . . . . . . . . . . 47\n§ 1. Operación de clausura. Clases cerradas . . . . . . . . . . . . . . 48\n§ 2. Dualidad y clase de funciones auto duales . . . . . . . . . . . 55\n§ 3. Linealidad y clase de funciones lineales . . . . . . . . . . . 58\n§ 4. Monotonía y clase de funciónes monótonas . . . . . . . . . . . 66\n§ 5. Plenitud y clases cerradas . . . . . . . . . . . . . . . . . 71\n\nCAPÍTULO III. LÓGICAS K-VALENTES . . . . . . . . . . . . . . 71\n§ 1. Representación de las funciones de las lógicas k-valentes con fór- . . . . .\n mulas de tipo especial . . . . . . . . . . . . . . . . . . . 71\n§ 2. Clases cerradas de la lógica k-valente . . . . . . . . . . . 79\n§ 3. Estudio de la plenitud de las funciones de la lógica k-valente . . 85\n\nCAPÍTULO IV. GRAFOS Y REDES . . . . . . . . . . . . . . . . . 91\n§ 1. Conceptos fundamentales de la teoría de los grafos . . . . . . 91\n§ 2. Planicidad, conexión, características numérales de los grafos . . 99\n§ 3. Grafos orientados . . . . . . . . . . . . . . . . . . . . 104\n§ 4. Arboles y redes bipolares . . . . . . . . . . . . . . . . . 109\n§ 5. Evaluacion en la teoria de los grafos y redes . . . . . . . . . . . 120\n§ 6. Realización de las funciones booleanas por medio de esquemas de contacto y fórmulas . . . . . . . . . . . . . . . . . . . . . . . 129 CAPÍTULO V. ELEMENTOS DE LA TEORÍA DE CODIFICACIÓN . . . . . . . . . . . . . . . . 138\n§ 1. Códigos con corrección de errores . . . . . . . . . . . . . . . . . . . 138\n§ 2. Códigos lineales . . . . . . . . . . . . . . . . . . . . . . . . . 142\n§ 3. Codificación alfabética . . . . . . . . . . . . . . . . . . . . . 146\n\nCAPÍTULO VI. AUTÓMATAS FINITOS . . . . . . . . . . . . . . . . . . . . . . 154\n§ 1. Funciones determinadas y de determinación acotada . . . . . . . . . 154\n§ 2. Representación de funciones determinadas con diagramas de Moo- . . . . .\n ro, conclusiones canónicas, con tablas y con esquemas. Opera- . . . . . . . .\n ciones sobre las funciones determinadas . . . . . . . . . . . . . . 164\n§ 3. Clases cerradas y plenitud en los conjuntos de funciones determi- . . .\n nadas y aceptadas-determinadas . . . . . . . . . . . . . . . . . . 180\n\nCAPÍTULO VII. ELEMENTOS DE LA TEORÍA DE LOS ALGORITMOS . . . . . . . . . . 185\n§ 1. Máquinas de Turing y operaciones a las que se someten. Funcion- . . . .\n es calculables en las máquinas de Turing . . . . . . . . . . . 185\n§ 2. Clases de funciones calculables y recursivas . . . . . . . . . . . 210\n§ 3. Calcularibilidad y complejidad de los cálculos . . . . . . . . . . . . 215\n\nCAPÍTULO VIII. ELEMENTOS DE COMBINATORIA . . . . . . . . . . . . . . . . . 215\n§ 1. Permutaciones y combinaciones. Propiedades de los coeficientes . . . . .\n binomiales . . . . . . . . . . . . . . . . . . . . . . . . . . . 215\n§ 2. Fórmula de inclusión y exclusiones . . . . . . . . . . . . . . . . . . . . . . 221\n§ 3. Evaluaciones regresivas, funciones generatrices, relaciones recurrentes . . .\n Soluciones, resultados y condiciones . . . . . . . . . . . . . . . 263\n\nBibliografía . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309\nÍndice alfabético de materias . . . . . . . . . . . . . . . . . . . . . 313 INTRODUCCIONEsta 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 título para los estudiantes de los cursos superiores y los aspirantes a doctor que se especializan en el terreno de la matemática discreta. Los profesores pueden emplear este libro al preparar las clases prácticas.\nEl 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 ho- \nra en la facultad de matemática de cómputo y cibernética de la Univesidad estatal de Moscú.\nEl libro es compuesto de ocho capítulos. Los dos primeros están dedicados a la lógica algebraica. La sección dedicada a la lógica algebraica 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 conceptos como función discreta, operación de superposición, sistema funcionalmente completo; asimilan las diferentes formas de presentación de las funciones discreta (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 sistemas de funciones.\nEl 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 transformaciones equivalentes de las formas, en las principales clases. cerradas de funciones de lógica k-valente y en los métodos de investigación de la plenitud y propiedad de cerrado de sistemas de funciones. En una serie de problemas se ilustra la diferencia que existe entre las lógicas k-valentes (k ≥ 2) y la lógica algebraica.\n\nEl capítulo cuarto 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 conceptos fundamentales, los métodos y el lenguaje de la teoría de los grafos. Todo esto se emplea muy ampliamente para describir e investigar las propiedades de las estructuras de los objetos en los más variados terrenos de la ciencia y de la técnica. En esta parte hay problemas predestinados a afirmar los conocimientos de los conceptos principales de la teoría de los grafos; problemas que ilustran la aplicación de la teoría de los grafos y las redes a la síntesis de esquemas 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 encuentren aquí problemas con la ayuda de los cuales podrán enseñar a los estudiantes a hacer rigurosas demostraciones matemáticas de afirmaciones geométricas evidentes.\n\nEl quinto capítulo está dedicado a la teoría de la codificación. Los problemas presentados traen sobre las propiedades de los códigos que corrigen errores; sobre los códigos alfabéticos; sobre los códigos con mínimo exceso.\n\nEl capítulo sexto contiene problemas que muestran diferentes tipos de automatismos discretos (automáticos). Se han incluido problemas para revelar la determinación y la determinación acotada de los automátas; para presentar automátas de diferentes 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 propiedades de las diferentes operaciones a las que se pueden someter estas aplicaciones.\n\nEl 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 calculabilidad y la complejidad de los cómputos, sobre ciertas formas concretas de definición del algoritmo (máquinas de Turing y funciones recursivas).\n\nEl 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 la existencia, el cálculo y la evaluación de diferentes objetos combinatorios. Por este motivo los autores han considerado útil incluir también problemas sobre combinatoria.\n\nActualmente todavía no existo un manual que abarque por completo los materiales teóricos del programa del curso universitario de la asignatura matemática discretas. El primer tomo de la monografía 'La matemática discreta y las cuestiones matemáticas de la