Контрольные по математике | Зачет по матлогике | Matematiku5
Вузы по математике Готовые работы по математике Как писать работы по математике Примеры решения задач по математике Решить задачу по математике online

Зачет по матлогике


Зачет

Математическая логика 2012

Уровень А (Формулировки без доказательства)

Высказывания: простые, сложные, примеры высказываний. Истинностное значение высказывания.

Дать определение конъюнкции и импликации

Дать определение дизъюнкции и эквиваленции.

Определение формулы алгебры высказываний.

Свойство коммутативности и дистрибутивности. Какие логические связки им удовлетворяют?

Свойство ассоциативности и идемпотентности. Какие логические связки им удовлетворяют?

Отрицание высказывания. Снятие двойного отрицания. Правила де Моргана.

Какое рассуждение называется логичным?

Равносильные формулы. Формулы поглощения и расщепления.

Тавтология и противоречие. Свойства констант.

Двойственная формула. Принцип двойственности.

Проблема разрешимости в логике высказываний. Определение КНФ. Как проверить, что формула является тавтологией с помощью КНФ?

Проблема разрешимости в логике высказываний. Определение ДНФ. Как проверить, что формула является противоречием с помощью ДНФ?

Определение аксиоматической теории (4 пункта).

Определение вывода в исчислении высказываний.

Правила подстановки и m. p.

Теорема дедукции.

Правила силлогизма и разъединения посылок.

Правила перестановки и соединения посылок.

Полнота и непротиворечивость аксиоматической теории.

Определение предиката. Предметное множество и предметные переменные.

Операции над предикатами. Связывание кванторами.

Интерпретация формулы. Равносильность формул в данной интерпретации.

Равносильность формул на множестве и в логике предикатов. Перенос квантора через отрицание.

Правила вынесения квантора за скобки.

Приведенная и нормальная формы формул

Правило резолюций

Алгоритм метода резолюций в логике высказываний

Алгоритмы.

Элементарные рекурсивные функции

Оператор .

Общая схема примитивной рекурсии для функции 1 переменной.

Общая схема примитивной рекурсии для функции 2 переменных.

Оператор минимизации для функции одной переменной.

Какая функция называется примитивно-рекурсивной.

Какая функция называется частично-рекурсивной.

Какая функция называется общерекурсивной.

Тезисы Черча, Тьюринга и Маркова

Функции информационной ленты машины Тьюринга.

Функции считывающей-записывающей головки машины Тьюринга.

Функции управляющего устройства машины Тьюринга.

Внешний алфавит и внутренние состояния машины Тьюринга.

Конфигурация на ленте машины Тьюринга.

Команда машины Тьюринга.

Программа машины Тьюринга.

Применимость и неприменимость машины Тьюринга к данному слову.

Произведение машин Тьюринга.

Итерация машины Тьюринга по паре состояний.

Разветвление машины Тьюринга.

Схемы машин Тьюринга.

Кодирование чисел и наборов чисел для машин Тьюринга. Программа вычисления 0(x).

Вычислимость по Тьюрингу.

Вычислимость элементарных рекурсивных функции. Программа для S(x).

Программа вычисления

Логическая схема Ляпунова: типы операторов, условные обозначения, принцип работы.

Пример логической схемы Ляпунова для произведения и итерации машин Тьюринга.

Нормальный алгоритм Маркова: алфавит, подстановка, правила очередности применения подстановок. Пример алгоритма Маркова.

ВС( доказать)

Свойства двойственных формул. Принцип двойственности Теорема1 исчисления высказываний Теорема 2 исчисления высказываний Доказать теорему Доказать теорему Доказать теорему Правило силлогизма Теорема 3 исчисления высказываний Правило перестановки Теорема 4 исчисления высказываний Правила с конъюнкцией Теорема 5 исчисления высказываний Правило соединения посылок Теорема 6 (а) исчисления высказываний Правило разъединения посылок Теорема 6 (б) исчисления высказываний Равносильные преобразования с кванторами: перенос квантора через отрицание, вынос квантора за скобки Доказать примитивную рекурсивность функций Доказать неразешимоесть проблемы самоприменимостимости и применимости к входному слову для машин Тьюринга Схема Ляпунова для вычисления

Наташа

Автор

Наташа — контент-маркетолог и блогер, но все это не мешает ей оставаться адекватным человеком. Верит во все цвета радуги и не верит в теорию всемирного заговора. Увлекается «нефрохиромантией» и тайно мечтает воссоздать дома Александрийскую библиотеку.

Распродажа дипломных

 Скидка 30% по промокоду Diplom2020