матлогика_методичка. Методические указания к выполнению практических работ Омск Издательство Омгту 2009

• Название: Методические указания к выполнению практических работ Омск Издательство Омгту 2009
• Анкор: матлогика_методичка.doc
• Дата: 04.05.2017
• Размер: 0.58 Mb.
• Имя файла: матлогика_методичка.doc
• Тип: Методические указания; #7036
• страница: 13 из 14

4.3. Задания

Определить степень равносильности формул P и Q при условии, что X и Yпринимают значения степеней истинности из множества {0,1; 0,5}.
Варианты индивидуальных заданий

№	P	Q	№	P	Q
1	X  Y	X Y	11	X  Y	X  Y
2	X  Y	X  Y	12	X  Y	X  Y
3	X Y	X  Y	13	X  Y	X Y
4	X  Y	X  Y	14	X Y	X  Y
5	X  Y	X  Y	15	X  Y	X  Y
6	X  Y	X  Y	16	X  Y	X  Y
7	X  Y	Y  X	17	Y  X	X  Y
8	Y  X	X  Y	18	X  Y	Y  X
9	Y  X	Y X	19	Y X	Y  X
10	Y  X	Y  X	20	Y  X	Y  X

Тема 5. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ

5.1. Понятие алгоритма

Для устранения нечеткости интуитивного понятия алгоритма были предложены точные математические модели алгоритма, например такие, как машина Тьюринга, система рекурсивных функций, нормальные алгоритмы Маркова. С помощью этих моделей алгоритма доказана алгоритмическая неразрешимость ряда важных задач математики и вычислительной техники.

Алгоритмическая неразрешимость некоторой задачи означает, что не существует общего алгоритма, решающего любую задачу рассматриваемого класса, но для отдельных подклассов алгоритмически неразрешимой задачи может существовать алгоритм.

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

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