Математическая логика и теория алгоритмов-РОСДИСТАНТ-практические задания
Задание 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.
