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

Необходимо выполнить контрольную работу на тему: «Контрольная работа для заочников по математической логике и теории алгоритмов».

Раздел 1.Математическая логика.Логика высказываний. Рассуждения. Логика предикатов. Формальные (аксиоматические) системы. Неклассические логики.

Раздел 2. Теория алгоритмов.Введение в теорию алгоритмов. Введение в анализ алгоритмов. Теория сложности вычислений и сложностные классы задач. Рекурсивные алгоритмы и методы их анализа.

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

Задание 2. Формализовать следующие высказывания:

Задание 3. Проверить корректность рассуждений:

Задание 4. Выяснить, является ли формула В логическим следствием посылок.A1, A2, A3,..., Ak 

Задание 5. Найти множество истинности предиката, заданного на множестве А.

Задание 7. Прочитайте следующие формулы (запишите на естественном языке) и установите их истинность (ложность) на соответствующих множествах:

Задание 8.Запишите следующие предложения в виде формул алгебры предикатов, выделите в них субъекты и предикаты:

Используя предикаты Запишите в виде формул алгебры предикатов следующие высказывания:

Задание 9 Используя предикаты запишите в виде формул алгебры предикатов следующие предложения:

Запишите в подходящей сигнатуре определения:

Задание 10 Перед следующими предикатами поставьте соответствующие кванторы так, чтобы получились высказывания, истинные на множестве действительных чисел:

Для следующих формул (2шт) установите их истинность (ложность) на множестве А, если:

Задание 11. Проверить истинность заключения методом резолюций

Задание 12. Свести к предложениям (множествам дизъюнктов) следующие формулы;

Задание 13. Найти функцию f(x,y), полученную из функций g(x) и h(x, у, z) по схеме примитивной рекурсии.

Задание 14 1. Построить машину Тьюринга, вычисляющую числовую функцию f(x1,x2,…,xn);2. Проверить работу построенной машины над некоторыми наборами значений переменных.