Лекции - Машины Тьюринга. Основы теории вычислимости. Булевы функции и пропозициональные формулы

Учебное пособие - М.: ФИЗМАТЛИТ, 2005 г. - 416 с. В пособии включены задачи и упражнения по конечнозначным логикам (втч и по алгебре логики), по теории алгоритмов, теории графов и сетей, теории кодирования, комбинаторике, минимизации булевых функций и синтезу схем и формул, реализующих булевы функции. Имеются задачи, предназначенные для первоначальной проработки и освоения методов дискретной математики, а также задачи для углубленного изучения пр...

Множества. Отображения и соответствия. Отношения. Натуральные числа. Логика высказываний. Логика предикатов. Формальные теории. Алгоритмы и вычислимость. Булевы функции. Элементы теории кодирования. Функции выбора и их логическая форма. Элементы комбинаторики. Биномиальная модель. Биномиальный ряд. Производящие. Рекуррентные последовательности. Числа Фибоначчи. Графы. Деревья. Доминирование. Внутренняя и внешняя устойчивость в графах.

Предварительные сведения. Содержание: Множества. Операции над множествами. Как доказывать равенство множеств? Отношения и функции. Мощность множества. Задачи. Индукция и комбинаторика. Содержание: Метод математической индукции. Задачи. Элементы комбинаторики. Размещения, перестановки, сочетания. Принцип включения и исключения. Задачи. Булевы функции и их представления. Содержание: Булевы функции от n переменных. Геометрическое представление. Табл...

Учебное пособие. ЮУрГУ, кафедра ЭВМ, 2009. - 64 стр. В пособии рассматриваются общие особенности теории алгоритмов, а также конкретные алгоритмические системы, такие как «Рекурсивные функции», «Машины Поста и Тьюринга», «Нормальные алгоритмы Маркова» и т. п. В соответствии с предметом дисциплины «Математическая логика и теория алгоритмов». Для студентов специальности 230101 («Вычислительные машины, комплексы, системы и сети») и направления 01040...

Таганрог, 2001 г. Введение в теорию множество, основы комбинаторики, алгебра высказываний, булевы функции, исчисление высказываний, алгебра предикатов, Основы теории алгоритмов

Множества и операции над ними. Соответствия и функции. Отношения и их свойства. Основные виды отношений. Элементы общей алгебры. Различные виды алгебраических структур. Элементы математической логики. Логические функции. Булевы алгебры. Булевы алгебры и теория множеств. Полнота и замкнутость. Язык логики предикатов. Комбинаторика. Графы: основные понятия и операции. Маршруты, цепи и циклы. Некоторые классы графов и их частей.rn

Лекции для студентов Бурятского филиала ФГОУ ВПО СибГУТИ. Раздел 1 Основы теории множеств. Раздел 2 Формулы логики. Раздел 3 Булевы функции. Раздел 4 Предикаты и бинарные отношения. Раздел 5 Отображения. Подстановки. Раздел 6 Метод математической индукции. Раздел 7 Основы теории графов. Раздел 8 Элементы теории алгоритмовrn

Все лекции по дискретной математике факультета Информационных технологий. Элементы общей алгебры. Различные виды алгебраических структур. Элементы математической логики. Логические функции. Булевы алгебры. Булевы алгебры и теория множеств. Полнота и замкнутость. Язык логики предикатов. Комбинаторика. Графы: основные понятия и операции. Маршруты, цепи и циклы. Некоторые классы графов и их частей. rn

Элементы модели алгоритма. Машина Тьюринга имеет 3 алфавита. Правила работы машины (правила обращения УУ с программой и СЗУ ). Замечания. Пример (Пусть программа машины Тьюринга имеет вид, Предъявим машине ленту, которую она воспринимает в состоянии q1).

Wegener I. The Complexity of Boolean Functions. (Wiley-Teubner series in computer science). John Wiley & Sons Ltd, and B. G. Teubner, Stuttgart, 1987. Различные аспекты теории сложности: булевы функции, схемы, формулы, программы итд. Булевы функции и схемы. Минимизация булевых функций. Разработка эффективных схем для некоторых важных функций. Асимптотики и универсальные схемы. Нижние границы сложности схем. Монотонные схемы. Связь между сложн...