Математическая логика и теория алгоритмов. контрольная работа. вариант №8

Владивостокский государственный университет
экономики и сервиса
____________________________________________________
А.А. СТЕПАНОВА
Т.Ю. ПЛЕШКОВА
Е.Г. ГУСЕВ

МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ

Практикум



1. ПЕРЕЧЕНЬ ТЕМ
Тема 1. «Совершенные дизъюнктивные нормальные формы (СДНФ) и совершенные конъюнктивные нормальные формы (СКНФ) в алгебре высказываний (АВ)». Формулы АВ. Эквивалент-ность формул АВ. Понятия дизъюнктивной нормальной формы (ДНФ), конъюнктивной нормальной формы (КНФ), СДНФ, СКНФ.
Тема 2. «Логическое следствие в алгебре высказываний». По-нятия логического следствия. Связь между понятиями логического следствия, противоречивого множества формул, тождественно ложной формулы и тождественно истинной формулы.
Тема 3. «Исчисление высказываний (ИВ). Доказуемые формулы ИВ». Понятие исчисления. Язык ИВ. Определение формулы ИВ. Ак-сиомы и правила вывода ИВ. Доказуемые и выводимые формулы ИВ. Примеры доказуемых и выводимых формул ИВ. Теорема о дедукции в ИВ. Эквивалентные формулы ИВ.
Тема 4. «Логика предикатов (ЛП). Алгебраические системы. Подсистемы». Понятия сигнатуры, алгебраической системы данной сигнатуры, подсистемы, подсистемы, порожденной множеством. При-меры. Понятия терма данной сигнатуры, значение терма на кортеже в алгебраической системе. Теорема о подсистеме, порожденной множест-вом.
Тема 5. «Формулы ЛП». Понятие формулы данной сигнатуры. Определение истинности формулы ЛП на кортеже элементов в алгеб-раической системе. Примеры.
Тема 6. «Истинность формулы ЛП в алгебраической системе».
Тема 7. «Логическое следствие в ЛП. Эквивалентные формулы ЛП». Понятия логического следствия, противоречивого множества формул ЛП, тождественно истинной формулы ЛП. Связь между этими понятиями. Определение эквивалентных формул ЛП. Основные эквива-лентности в ЛП.
Тема 8. «Исчисление предикатов (ИП). Доказуемые формулы ИП». Язык ИП. Определение формулы ИП. Аксиомы и правила вывода ИП. Доказуемые и выводимые формулы ИП. Примеры доказуемых и выводимых формул ИП. Тавтологии. Связь между тавтологией и дока-зуемой формулой. Эквивалентные формулы ИП.
Тема 9. «Пренексная нормальная форма для формул ИП». По-нятия ДНФ и ПНФ для формул ИП. Теорема о существовании для лю-бой формулы ИП эквивалентной ей ПНФ.
Тема 10. «Машины Тьюринга». Определение машины Тьюринга. Понятие функций, вычислимых по Тьюрингу. Примеры таких функций.
Тема 11. «Примитивно рекурсивные функции». Понятия базис-ных функций, операторов суперпозиции, примитивной рекурсии, при-митивно рекурсивных функций. Примеры.
Тема 12. «Частично рекурсивные функции». Понятия оператора минимизации, частично рекурсивных функций. Примеры. Эквивалент-ность классов функций, вычислимых по Тьюрингу, с классом частично рекурсивных функций.