Мат.логика и теория алгоритмов 26 вар.
Задание № 1. Тема: Сложность алгоритмов.
Вариант 26. Оценить временную сложность алгоритма сложения матриц
Задание № 2. Тема: Таблицы истинности формул алгебры высказываний, эквивалентные преобразования.
Доказать тождественную истинность формул двумя методами: 1 - построив таблицу истинности, 2 - с помощь эквивалентных преобразований
Задание № 3. Тема: Нормальные формы логических (булевых) функций.
Вариант с 16 по 31. Привести к КНФ и Совершенной КНФ логические функции:
Задание № 4. Тема: Метод резолюции в исчислении предикатов.
Методом резолюций доказать:
Задание № 5. Тема: Алгоритмические модели: нормальные алгоритмы Маркова (НАМ), машины Тьюринга (МТ), рекурсивные функции (РФ).
Вариант 26. Представить в виде НАМ алгоритм для выполнения операции декремент в унитарном коде.
Задание № 6. Тема: Теоретические разделы дисциплины «Математическая логика».
Вариант 26. Задача доказательства теорем. Приведение к противоречию. Метод резолюции.