Вопросы к экзамену по математической логике

Вопросы к экзамену по математической логике
Понятие о функциональной полноте систем булевых функций. Операция замыкания и замкнутые классы. Теоремы о функциональной полноте систем булевых функций. Базис класса и способы его определения для заданной системы булевых функций. Примеры функционально полных систем в Р2.
Предполные классы. Теорема о замкнутости предполных классов.
Класс функций, сохраняющих нуль: признак принадлежности функции к классу, доказательство замкнутости класса, мощность класса. Привести примеры элементарных булевых функций, сохраняющих нуль.
Класс функций, сохраняющих единицу: признак принадлежности к классу, доказательство замкнутости класса, мощность класса. Привести примеры элементарных булевых функций, сохраняющих единицу.
Класс самодвойственных функций: признак принадлежности функции к классу самодвойственных, доказательство замкнутости класса, мощность класса. Лемма о несамодвойственной функции. Привести примеры самодвойственной функции и применения леммы о несамодвойственной функции.
Класс монотонных функций: признак принадлежности функции к классу, доказательство замкнутости класса, примеры элементарных булевых функций, принадлежащих к классу. Лемма о немонотонной функции. Привести примеры применения леммы о немонотонной функции.
Класс линейных функций: признак принадлежности функции к классу линейных функций, доказательство замкнутости класса линейных функций, мощность класса линейных функций, привести примеры элементарных линейных булевых функций. Способы построения полиномов по mod 2.
Лемма о нелинейной функции. Примеры применения леммы.
Машина Тьюринга как пример алгоритмической системы: алгебраическое описание МТ, понятие программы, слова, конфигурации. Применимость МТ к слову. Привести пример МТ, складывающей два унарных числа.
Машина Тьюринга как пример алгоритмической системы: алгебраическое описание МТ, понятие программы, слова, конфигурации. Применимость МТ к слову. Привести пример МТ, выполняющей перевод числа из унарной системы счисления в двоичную.
Машина Тьюринга как пример алгоритмической системы: алгебраическое описание МТ, понятие программы, слова, конфигурации. Применимость МТ к слову. Привести пример МТ, переводящей числа из унарной системы счисления в троичную.
Машина Тьюринга как пример алгоритмической системы: алгебраическое описание МТ, понятие программы, слова, конфигурации. Применимость МТ к слову. Привести пример МТ, удваивающей унарные числа.
Логика высказываний как формальная модель. Основные теоремы логического вывода. Понятие семантики в логике высказываний. Доказательство выводимости формул методом семантических таблиц Бета. Корректность и полнота метода семантических таблиц.
Формулировка исчисления высказываний. Дать определения секвенции, вывода, теоремы, правила вывода, схемы аксиом. Доказательство выводимости секвенций в исчислении высказываний. Привести пример прямого и обратного доказательства выводимости секвенции |- (U(U).
Метод резолюций в логике высказываний. Корректность и полнота метода резолюций.
Термы и формулы в логике предикатов. Интерпретация термов и формул.
Подстановка термов в формулы. Композиция подстановок. Понятие коллизии переменных.
Аксиоматические основания логики предикатов. Теорема универсальной конкретизации.
Аксиоматические основания логики предикатов. Теорема экзистенциального обобщения.
Аксиоматические основания логики предикатов. Доказать, что если free(x,t,(), то справедлива теорема: |=(((((x)) ( |=|=((((x(((x))).
Аксиоматические основания логики предикатов. Доказать, что если free(x,t,(), то справедлива теорема: |=(((x)(() ( |=((x(((x)(()).
Доказательство общезначимости формул логики предикатов методом семантических таблиц Бета. Доказать общезначимость формулы (((xU(x))((((xU(x)).
Нормальные формы в логике предикатов. Правило построения пренексной нормальной формы. Привести к пренексной нормальной форме формулу (x(yU(x,y)((x(yB(x,y).
Сколемовская нормальная форма в логике предикатов. Доказательство существования СНФ. Для формулы (x(z(y(u((y>z(y>x)&(uТеоретико-множественное представление (-формул. Эрбрановские интерпретации. Доказательство невыполнимости предложения с использованием метода семантических деревьев. Теорема Эрбрана.
Унификация и резолюция в логике предикатов. Теорема Робинсона. Используя метод резолюций, доказать, что воробей – птица, если известны факты: «птица несет яйца и имеет крылья», «рептилия откладывает яйца и имеет чешую», «воробей откладывает яйца», «питон откладывает яйца», «питон имеет чешую», «воробей имеет крылья».
Исчисление предикатов как формальная система. Связь правил вывода в исчислении предикатов с аксиоматическими основаниями логики предикатов. Прямой и обратный вывод в исчислении предикатов.

Приложенные файлы

  • doc 8958669
    Размер файла: 36 kB Загрузок: 0

Добавить комментарий