Математическая логика и теория алгоритмов-РОСДИСТАНТ-практические задания

Задание 1 Составив таблицы истинности, выясните, равносильны ли формулы алгебры высказываний из таблицы 1.1.

Задание 2. С помощью равносильных преобразований упростите формулу из таблицы 2.1.

Задание 3. Докажите логическое следствие двумя различными способами. Задание представлено в таблице 3.1.

Задание 4. Используя СДН-форму, найдите наиболее простую формулу алгебры высказываний от четырех переменных, принимающую значение 1 на следующих наборах переменных и только от них. Задание по вариантам представлено в таблице 4.1.

Задание 5 Для предикатов, заданных на,... , выяснить, является ли первый предикат следствием второго, а второй – следствием первого. Задание по вариантам представлено в таблице 5.1.

Задание 6. Равносильными преобразованиями приведите формулу алгебры предикатов из таблицы 6.1 к предваренной (пренексной) нормальной форме.

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

 и переводящую их в слово α. Задание по вариантам представлено в таблице 7.1.

Задание 8. Построить нормальный алгоритм, применимый ко всем словам в алфавите  и переводящий их в слово α. Задание по вариантам представлено в таблице 8.1.