Документ взят из кэша поисковой машины. Адрес оригинального документа : http://www.intsys.msu.ru/study/TDF/TDFprog.pdf Дата изменения: Sat Sep 7 20:16:42 2013 Дата индексирования: Thu Feb 27 21:09:50 2014 Кодировка: Windows-1251

Программа курса "Теория дискретных функций"
Курс является введением в дискретную математику - раздел прикладной математики, являющийся основой для математической кибернетики и информатики. В него включены сведения из алгебры логики, теории многозначных логик,а также теории конечных и клеточных автоматов. Эти сведения предоставляют базис для решения широкого круга задач, связанных с компьютерной обработкой данных и созданием интеллектуальных систем. 1. Функции и множества. Равенство функций. n-местные функции. Функции алгебры логики, их задание таблицами. Число n-местных функций алгебры логики. Существенные и несущественные переменные. Операция добавления либо удаления несущественной переменной. Симметрические функции алгебры логики. Элементарные функции алгебры логики. 2. Формулы алгебры логики. Слова в конечных алфавитах. Сигнатура. Определение формулы в сигнатуре . Значение формулы на наборе значений пе~ ременных x. Существенные и несущественные переменные формулы. Функция, ~ ~ определяемая формулой относительно переменных x. Функция, получаемая ~ суперпозициями над множеством функций F . Определение суперпозиций, не использующее понятия формулы (без доказательства эквивалентности). Операции суперпозиции: подстановка переменных, подстановка функции, добавление либо удаление несущественных переменных. 3. Эквивалентные формулы. Основные тождества для элементарных функций алгебры логики. Двойственность и самодвойственность. Принцип двойственности. 4. Представление функций алгебры логики посредством совершенных дизъюнктивных нормальных форм. Выразимость функций алгебры логики суперпозициями через дизъюнкцию, конъюнкцию и отрицание. Совершенная конъюнктивная нормальная форма. 5. Полные системы функций алгебры логики. Примеры. Теорема Жегалкина. 6. Замыкание множества функций алгебры логики. Примеры. Простейшие свойства замыкания. Замкнутые классы. Примеры. 7. Классы T0 и T1 , их замкнутость. 8. Класс S , его замкнутость. Лемма о несамодвойственной функции. 9. Класс M , его замкнутость. Лемма о немонотонной функции. 10. Класс L. Лемма о нелинейной функции. 11. Различие классов T0 , T1 , L, S, M . Теорема о полноте систем функций алгебры логики. 12. Предполные классы. Предполнота классов T0 , T1 , L, S, M . Отсутствие в P2 других предполных классов. 13. Теорема о выделении из полной системы функций алгебры логики полной подсистемы, имеющей не более 4 функций. 1


14. Полнота относительно замкнутого класса. Базис в замкнутом классе. Примеры. Теоремы Поста (без доказательства) о мощности множества замкнутых классов в P2 и о базисах этих классов. 15. Функции k -значной логики. Задание их таблицами, элементарные функции. Формулы k -значной логики. Суперпозиции. 16. Простейшие тождества для функций в Pk . Аналог совершенной дизъюнктивной нормальной формы для Pk . 17. Полные системы в Pk . Примеры. Система {max(x1 , x2 ), x}. Функция Вебба. ? 18. Замыкание и замкнутые классы в Pk . Примеры. 19. Алгоритм распознавания полноты в Pk . Последовательность Кузнецова для множества F функций k -значной логики. Стабилизация этой последовательности на множестве [F ]x1 x2 . 20. Существование конечной полной подсистемы в полной системе функций k значной логики. 21. Селекторные функции. Сохранение множества K , включающего селекторные функции. Описание класса S как класса сохранения некоторого множества K . Замкнутость класса U (K ) всех функций, сохраняющих K . 22. Неполнота системы F , содержащейся в U (K ), если Vk K . / 23. Существование для неполной системы F такого множества K , что Vk K и / F U (K ). 24. Теорема Кузнецова о полноте в Pk . 25. Существенная функция в Pk . Лемма С.В.Яблонского о трех наборах. 26. Лемма о подмножестве G1 Ч . . . Ч Gn , на котором функция принимает l значений. 27. Квадрат в (Ek )n . Лемма о квадрате. 28. Теорема Слупецкого. Замечание С.В.Яблонского о возможности сужения множества одноместных функций. Теорема Мартина. 29. Теорема Янова. 30. Теорема Мучника. 31. Представление функций в Pk полиномами. 32. Абстрактный конечный автомат. Способы задания. Доопределение функций переходов и выходов автомата на множестве входных слов. Функции , . Про?? стейшие свойства функций , , , . ?? 33. Инициальный конечный автомат. Функции, реализуемые конечными инициальными автоматами. Система канонических уравнений.

2


34. Преобразование конечным инициальным автоматом бесконечной входной последовательности. Периодические последовательности в конечном алфавите. Теорема о преобразовании конечным инициальным автоматом периодической последовательности. 35. Неотличимость состояний конечного автомата. Автоматы приведенного вида. Неотличимость автоматов. Изоморфизм автоматов. Теорема о существовании единственного с точностью до изоморфизма конечного автомата приведенного вида, неотличимого от заданного конечного автомата. 36. Теорема Мура о длине слова, достаточной для различения двух отличимых состояний одного конечного автомата. 37. Теорема Мура о длине слова, достаточной для различения отличимых состояний двух различных конечных автоматов. 38. Множества слов, представимые в конечном автомате. События в конечном алфавите. Операции над событиями. Регулярные события. 39. Лемма о решении уравнения X = X C D. 40. Лемма о регулярности событий, удовлетворяющих системе уравнений с регулярными коэффициентами. 41. Лемма о регулярности представимых событий. 42. Обобщенные источники в конечном алфавите. Событие, определяемое обобщенным источником. Лемма о существовании обобщенного источника, определяющего заданное регулярное событие. 43. Лемма о представимости события, определяемого обобщенным источником. Теорема Клини. Регулярность пересечения, дополнения и разности регулярных событий. Существование нерегулярных событий. Пример нерегулярного события. 44. Представление о схемах из конечных автоматов. Класс Pавт . Зависимость заданного выхода автоматной функции от заданного входа с задержкой. Сигнатура. Элемент схемы. Индуктивное определение схемы и реализуемой ею автоматной функции. Автоматная функция, получаемая из заданных автоматных функций операциями композиции. Замыкание и полнота множеств функций в Pавт . 45. Пример полной системы функций в Pавт . 46. Однородные структуры. Окрестность ячейки. Состояние однородной структуры. Конфигурации. Локальная и глобальная функции переходов. Поведение однородной структуры. Пример: двумерная однородная структура, локальная функция переходов которой имеет вид x0 + x1 + . . . xh-1 ( mod 2). 47. Теорема Мура о взаимно стираемых конфигурациях.

Список литературы
1. Яблонский С.В. Введение в дискретную математику. Москва, "Высшая школа". 2001г. 3


2. Сб. "Дискретная математика и математические вопросы кибернетики". Москва, "Наука", 1974г. 3. Кудрявцев В.Б., Алешин С.В., Подколзин А.С. Введение в теорию автоматов. Москва, "Наука", 1985г. 4. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. Москва, "Наука", 1977г.

4