Уважаемые дамы и господа !! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши, выберите команду "Save target as ..." ("Сохранить объект как ...") и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.
ЧАСТЬ I
ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ
Глава 1. Алгебра логики
§ 1. Функции алгебры логики
§ 2. Формулы. Реализация функций формулами
§ 3. Эквивалентность формул. Свойства элементарных
функций. Принцип двойственности
§ 4 Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
§ 5. Полнота и замкнутость
§ 6. Важнейшие замкнутые классы, теорема о полноте
§ 7. Представление о результатах Поста
Глава 2. k-значная логика
§ 1. Функции k-значной логики. Формулы и реализация функций формулами
§ 2. Примеры полных систем
§ 3. Распознавание полноты. Теорема о полноте
§ 4. Некоторые свойства существенных функций. Критерий полноты
§ 5. Особенности k-значных логик
Глава 3. Ограниченно-детерминированные (автоматные)
функции с операциями
§ 1. Детерминированные функции
§ 2. Задание детерминированных функций при помощи деревьев. Вес дерева
§ 3. Ограниченно-детерминированные функции и способы их задания
§ 4. Операции над о.-д. функциями
§ 5. Примеры полных систем
§ 6. О соотношении операций
Глава 4. Вычислимые функции
§ 1. Машины Тьюринга
§ 2. Один метод построения машип Тьюринга
§ 3. Машинные коды и их преобразования
§ 4. Вычислимые функции
§ 5. Операции С и Пр
§ 6. Вычислимые функции и операции С и Пр
§ 7. Формула Клини. Частичная рекурсивность вычислимых функций. Примеры полных систем
ЧАСТЬ II КОМБИНАТОРНЫЙ АНАЛИЗ
§ 1. Комбинаторные объекты и комбинаторные числа
§ 2. Простейшие свойства комбинаторных объектов и чисел
§ 3. Методы изучения комбинаторных объектов и чисел
§ 4. Оценки а асимптотики для комбинаторных чисел
ЧАСТЬ III ГРАФЫ И СЕТИ
Глава 1. Графы
§ 1. Реализация в евклидовом пространстве. Изоморфизм
§ 2. Оценка числа трафов
Глава 2. Сети
§ 1. Сети и их свойства
§ 2. Оценка числа сетей
§ 3. Двухполюсные сети из двухобъектных наборов
§ 4. Пи-сети
ЧАСТЬ IV
ТЕОРИЯ КОДИРОВАНИЯ
§ 1. Критерий однозначности декодирования
§ 2. Алгоритм распознавания однозначности декодирования
§ 3. Об одном свойстве взаимно однозначных кодов
§ 4. Коды с минимальной избыточностью
§ 5. Самокорректирующиеся коды
ЧАСТЬ V
НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
Глава 1. Дизъюнктивные нормальные формы
§ 1. Понятие д. н. ф. Проблема минимизации булевых Функций
§ 2. Упрощение д. н. ф. и тупиковые д. н. ф. (относительно упрощения)
§ 3. Постановка задачи в геометрической форме
§ 4. Сокращенная д. и. ф
§ 5. Тупиковость на основе геометрических представлений. Методы построения тупиковых д. н. ф.
§ 6. Некоторые однозначно получаемые д. н. ф.
§ 7. Понятие локального алгоритма
Глава 2. Синтез схем из функциональных элементов
§ 1. Понятие схемы из функциональных элементов
§ 2. Проблема синтеза схем из Ф. Э.
§ 3. Элементарные методы синтеза
§ 4. Нижняя оценка для L(n)
§ 5. Оптимальный по порядку метод синтеза схем из
Ф. Э. (метод Шеннона)
§ 6. Асимптотически наилучший метод синтеза схем из Ф. Э. (метод Лупанова)
§ 7. Синтез сумматора
§ 8. Синтез схем из Ф. Э,, реализующих симметрические функции
Краткая аннотация книги
Книга является введением в дискретную математику - раздел прикладной математики, бурно развивающийся в последние годы и являющийся базой для математической кибернетики. Она написана на основе курса лекций, читавшегося автором в течение ряда лет на факультете вычислительной математики и кибернетики Московского государственного университета. Предназначается студентам факультетов прикладной математики, аспирантам, а также инженерам и специалистам, работающим в области прикладной математики.
Дискретная математика - часть математики, которая зародилась в глубокой древпости. Как говорит само заглавие, главной ее спецификой является дискретность, т. е. антипод непрерывности. В широком смысле дискретная математика включает в себя и такие сложившиеся разделы математики, как теория чисел, алгебра, математическая логика и ряд разделов, которые наиболее интенсивно стали развиваться в середине этого века в связи с внедрением ЭВМ. Научно-технический прогресс поставил проблему изучения сложных управляющих систем. В узком смысле дискретная математика ограничивается только этими новыми разделами. Именно так это понимается и в данной книге. К упомянутым новым разделам мы относим: теорию функциональных систем; теорию графов и сетей; теорию кодирования; комбинаторный анализ; целочисленное программирование и т. п.
Дискретная математика сегодня является не только фундаментом математической кибернетики, но и важным звеном математического образования. Книга содержит материал, соответствующий двум типам программ курса "Дискретная математика": стандартной программе для факультетов прикладной математики и кибернетики большинства университетов и программе соответствующего курса, читаемого в МГУ. Эти программы не ставят целью дать большое количество материала фактического и имеющего спрос в данное время. Чрезмерная детализация и привязывание программы к специальным фактам опасны тем, что лет через 10-15 (а это как раз время активной деятельности обучаемых сейчас студентов) появятся новые факты, а старые частично утратят свою значимость. Ввиду этого главная задача курса - это обучение методам и мышлению, характерным для дискретной математики. Материал, вошедший в эту книгу, знакомит читателя с узловыми задачами из нескольких разделов дискретной математики и ее приложений. Он подобран таким образом, чтобы сократить число необходимых понятий до минимума и, с другой стороны, дать небольшое количество (10-15) серьезных теорем с непохожими доказательствами, а также познакомить с применениями понятия алгоритма, владение которым особенно важно для специалистов в области прикладной математики. Содержание книги охватывает почти все основные разделы дискретной математики. При ее написании автору пришлось усовершенствовать целый ряд доказательств, в ряде случаев дать новые доказательства, которые публикуются здесь впервые.
Изложение многих вопросов из перечисленных разделов не всегда ведется па абстрактной основе: здесь широко используется геометрический язык и содержательные интерпретации. Это позволяет сочетать в построениях наглядность и известную строгость. Надо иметь в виду, что в математических статьях существуют две крайности: пренебрежение строгостью изложения и доведение строгости до абсурда. Обе указашше тенденции одинаково опасны. Строгость изложения должна соответствовать рассматриваемой задаче (и уровню аудитории), подобно тому как в приближенных вычислениях число значащих цифр получаемых результатов должно соответствовать точности исходных данных. Слишком "большой" запас строгости в этом смысле подобен вычислениям со значительным числом дополнительных разрядов.
Данная кттига рассчитана на студентов, аспирантов и научных сотрудников.
Второе издание книги отличается от первого наличием дополнительной части по комбинаторному анализу, некоторой переработкой остальных частей и устранением всех вамеченных погрешностей. В этой работе автору помогли замечания многих математиков, которым автор весьма призпателен. Особую благодарность автор выражает редакторам первого и второго изданий Б, П. Липатову и В. М. Храпченко, проделавшим большую работу по улучшению изложения материала.
Вы можете использовать скачанные с веб-сайта книги и другие материалы только для личного ознакомления. Авторское право авторов книг и любых электронных приложений к ним (в том числе фото, видео, рукописи, архивы и прочее) не подлежит патентованию и подобным "искусственным" дополнительным мерам защиты авторского права - не патентуют рукописи, фотографии, видеоматериалы, формулы, графики, сводные таблицы, тексты монографий, черновики и оригинальные издания вне зависимости от того, находятся ли они в частных или государственных архивах любой страны. Вне зависимости от того, есть ли у книги или рукописи и автора какие-либо коды или нет, подписаны они или нет, известен автор или нет, является он(а) гражданином Украины или иностранцем - запрещено явным образом присваивать чужое авторское право и ставить чужие ФИО в чужих работах и трудах (в случае неуказанного, неустановленного или сомнительного авторства наиболее предпочтительно использовать анонимность - это корректно, этично и непротивозаконно, так как в этом случае истинные владельцы будут поданы в розыск и объективно установленны в своих правах независимой комиссией).
Сегодня электронный вариант публикации приравнен к печатной бумажной форме распространения информации (требования аналогичны). Наиболее предпочтительными являются международные форматы публикаций PDF и DJVU (они лучше всего защищены от сторонних модификаций - изменения в них могут внести только профессионалы), допускаются и другие общепринятые и широко распространенные форматы электронного представления авторской или смежной информации. Помните, что один человек сам по себе ничего не делает и не решает - у любого автора любого издания есть коллеги, единомышленники, соратники, кураторы, преподаватели, наставники, идейные, политические и научные руководители и вдохновители, предшественники и приемники, завистники и плагиаторы, желающие незаконно "упасть на хвост и поехать", "присоседиться к работе" и "присоединиться". Чем серьезнее ученый и чем более масштабные объективные и фундаментальные работы он(а) реально ведет, тем большее количество мошенников и аферистов желает незаконно "находиться" и "быть рядом" с таким человеком, его деньгами, премиями, подарками и другими объективными поощрениями. Поэтому все подобные аферисты и мошенники, как и их голословные заявления, подлежат строгой проверке на практике как гласными, так и негласными методами государственного, общественного и политического независимого контроля (в том числе судебного и силового).
Вам разрешается использовать электронные публикации и иные материалы только для личного ознакомления. Никаких дополнительных прав и свобод (в том числе авторских и коммерческих прав, в том числе права на коммерческое распространение) получение и обладание электронной и иной публикации и материалов Вам не предоставляет. Вам не дает никаких прав, в т.ч. авторских и смежных прав, личное знакомство с автором и правообладателем, совместное проживание, учеба или работа, семейный и иной статус, совместное хобби и увлечения, посещение одних и тех же мероприятий, встречи, конфликты и даже отсутствие таковых. Вы не имеете право продавать электронные публикации и иные авторские материалы, отчуждать их от владельца и извлекать материальную выгоду от владения электронной и иной формой представления авторской информации. Отчуждение авторского научного и творческого права запрещено вне зависимости от срока давности издания, способа и места его хранения, разрекламированности, известности или неизвестности и даже анонимности автора и соавтора, гражданства, здоровья, болезни и любого другого объективного статуса реального правообладателя. Запрещены фото- и видеомонтажи, врезки и изъятия, компиляция из сторонних источников и другие формы заведомого мошенничества. Запрещено иностранцам без признанной в Украине и документально подтвержденной профессии, без легитимных виз и специальных персонифицированных межгосударственных соглашений занимать рабочие места граждан Украины на территории Украины и во всех предприятиях, которые являются собственностью Украины и ее граждан вне зависимости от места регистарции и дислокации этих предприятий. Запрещено работать без рабочих виз на территории Украины гражданам и подданым стран, с которыми у Украины установлен визовый режим.
Авторское право (особенно научное и творческое) никогда не патентуется, не отчуждается ни при каких обстоятельствах, не продается и не покупается и является неотъемлимым от его создателя при любых обстоятельствах - патентуются только уникальные инженерные и программные разработки, авторские алгоритмы, изобретения и подобные материалы, содержащие более 60% объективно признанных независимой государственной экспертной комиссией авторских инноваций. Незаконным является присвоение себе чужих архивов, черновиков, заметок, аудио, фото и видеоматериалов (даже если вы не знаете их автора или же непосредственно знакомы с создателем и правообладателем, это ничего не решает). Научное и творческое авторское право не отчуждается от автора и создателя и никогда не делегируется третьим лицам (особенно без профессии и неконтрафактных документов) - оно является наиболее строгим авторским правом, неотделимым от своего создателя, и не подлежит передаче, купле и продаже ни при каких обстоятельствах. Оно только может быть передано в возмездное или безвозмездное пользование БЕЗ ПРАВА НА ОТЧУЖДЕНИЕ. Главной особенностью научного и творческого авторского права является его обязательная частичная передача в безвозмездное пользование широким слоям заинтересованного населения - на этом сайте все научные книги бесплаты и свободны для скачивания без паролей, кодов и ограничений (я как владелец этого сайта и интернет-хостинг-провайдеры не несем ответственность за деятельность третьих лиц, возможные сбои и технические нарушения интернет-связи при пользовании сайтами по вине третьих лиц). Никаких искусственных препятствий, ограничений скорости, других "негативов" и препятствий мы не устанавливаем.
Государство Украина имеет достаточную базу для обеспечения научных работ и научных исследований по всем законным направлениям научной деятельности. C 2010 г. в Украине любая наука и научные исследования являются объектами строгой государственной монополии и требуют наличия не только документально признанной в Украине профессии, но и высшего государственного образования, официально признанного в Украине.