Особенности k – значной логики

Во многом k – значная логика подобна двухзначной. В ней сохраняются многие результаты, имеющие место в двузначной логике. Однако ряд результатов, верных для функций алгебры логики, т.е. при k =2, уже не переносятся на случай, когда k ³3.

Например, как показал Пост, каждый замкнутый класс в P ₂ имеет конечный базис и поэтому, число замкнутых классов в P ₂ счетно. С другой стороны для k ³ 3 в :

а) существует замкнутый класс не имеющий базиса;

б) существует замкнутый класс имеющий счетный базис;

в) имеется бесчисленные множества различных замкнутых классов.

3. ОСНОВНЫЕ ПОЛОЖЕНИЯ ТЕОРИИ АЛГОРИТМОВ

3.1. ПОНЯТИЯ АЛГОРИТМА И РЕКУРСИВНОЙ ФУНКЦИИ

3.1.1. Интуитивное понятие алгоритма

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

Например:

алгоритм умножения двух многозначительных чисел;

алгоритм извлечения квадратного корня;

алгоритм определения истинностного значения некоторого высказывания.

Характерные свойства алгоритмов:

1. Дискретность. Алгоритм описывает процесс последовательного построения величин, идущий в дискретном времени. При этом интервал времени, необходимый для вычисления, разбивается на малые отрезки – такты. В результате осуществления элементарного шага алгоритма (определенной программы преобразований) из системы величин, имеющихся в начале такта, получается система величин приходящихся на конец такта.

2. Детерминированность. Это означает, что программа преобразований в каждом такте определена однозначно.

3. Результативность. Каждый алгоритм направлен на получение определенного результата. В частности, если вычисляемая функция в некоторой точке не определена, то совокупность правил должно точно указать, что нужно считать в этом случае результатом применения алгоритма.

4. Массовость. В определенных пределах исходные величины могут варьироваться. Это значит, что алгоритм служит для решения не только какой-либо одной конкретной задачи. Он предназначен для решения целого класса задач. Процедуру решения одной конкретной задачи никогда не называют алгоритмом.

Понятие алгоритма, задаваемое его эмпирическими свойствами, не является строго математическим, поэтому оно называется интуитивным.

3.1.2. Проблема уточнения понятия алгоритма

Интуитивное понятие алгоритма допустимо при положительном решении вопроса о существовании алгоритма. Теоремы о не существовании алгоритмов не могут быть доказаны ввиду нечеткости интуитивного понятия алгоритма. В этом случае требуется его уточнение. Существуют несколько подходов уточнения понятия алгоритма. Основаниями для них являются:

теория рекурсивных функций;

машины Тьюринга;

нормальный алгоритм Маркова.

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

Пусть N – множество натуральных чисел. k -местными частичными функциями называются функции с областью определения (k – целое положительное число) и областью значений . Слово «частичная» означает, что функция определена на подмножестве .

Если , то функция называется всюду определенной.

k –местная частичная функция f: называется вычислимой, если существует алгоритм, вычисляющий f. Этот алгоритм должен удовлетворять следующим условиям:

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

Если на выход алгоритма поступает , то алгоритм никогда не заканчивается.

Заметим, что множество вычислимых функций не совпадает с множеством “практически вычислимых” функций, которые связаны с ограничениями современных вычислительных машин.

Определение вычислимой функции не является формальным. Формализацией этого понятия служит частично-рекурсивная функция.

3.1.3. Частично-рекурсивные функции

Простейшими (базисными) называются следующие числовые функции:

1) постоянная функция , где ;

2) одноместная функция следования ;

3) функция проекции .

Преобразование функций называется оператором. При построении рекурсивно частичной функции используются следующие операторы:

1. Оператор суперпозиции. k -местная функция получена с помощью суперпозиции из m -местной функции и k -местных функций , ,…, , если = .

2. Оператор примитивной рекурсии. При из k -местной функции f и (k+2)- местной функции g строится (k+1)- местная функция h по следующей схеме:

;

.

3. Оператор минимизации. Этот оператор ставит в соответствие частичной функции f: частичную функцию h: , которая определяется следующим образом:

1) область определения и ;

2) = наименьшее значение y, при котором .

Естественный путь вычисления состоит в подсчете значения последовательно для y =0,1,2,… до тех пор, пока не найдется значение y, обращающее в 0. Этот алгоритм может не остановиться, если нигде не обращается в 0.

Все функции, которые можно получить из базисных с помощью трех указанных операторов называются частично-рекурсивными. Если при этом функция, полученная с помощью этих операторов, всюду определена, то она называется общерекурсивной. Если при этом функция полученная из базисных функций без механизма минимизации, всюду определена, то она называется примитивно-рекурсивной.

Можно показать, что введение фиктивных переменных, а также перестановка и отождествление переменных не выводят функцию за пределы класса частично-рекурсивных.

В частности:

Введение фиктивных переменных. Если - примитивно-рекурсивная функция и , то - примитивно-рекурсивная функция.

Перестановка переменных. Если - примитивно-рекурсивная функция и , то f есть также примитивно-рекурсивная функция.

Отождествление переменных. Если - примитивно-рекурсивная функция и = , то есть также примитивно-рекурсивная функция.

3.2. МАШИНЫ ТЬЮРИНГА

3.2.1. Понятие и формальное определение

машины Тьюринга

Понятие машины Тьюринга впервые было введено в 1936 году логиком Тьюрингом. Тьюринг рассматривал гипотетическую «машину», имеющую конечное множество S внутренних состояний и одну бесконечно длинную ленту, разделенную на ячейки. Машина за один такт может передвигать на одну ячейку вправо или влево. В каждой ячейке машина записывает символ из конечного алфавита А. Первоначально лента должна быть пустой, за исключением конечного числа ячеек, заполненных заранее. Эти заранее заполненные ячейки представляют собой программу запуска машины.

Формальное определение машины Тьюринга состоит в следующем. Машиной Тьюринга называется пятерка объектов [ ] следующего типа: А - это конечный алфавит символов, которые могут быть записаны в ячейках и являются одновременно входными и выходными, т. е. . S есть конечное множество внутренних состояний, т. е. ; v - функция из в S; - функция из в A; - функция из в множество {П, Л, ОСТАНОВ}. Интуитивный смысл данных выражений станет ясен из дальнейшего.

Машина Тьюринга работает следующим образом. Она начинает работу, находясь в начальном состоянии . После считывания первого символа она переходит в новое внутреннее состояние, определяемое функцией v, записывает в ячейке символ, являющийся значением функции , перемещает ленту направо (П), налево (Л), или остается на месте и прекращает работу (ОСТАНОВ) в зависимости от значения функции .

На рисунке схематически изображена лента машины Тьюринга и считывающе-записывающая головка.

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

3.2.2. Примеры машин Тьюринга

Пример 1. Машина Тьюринга считывает входную последовательность нулей и единиц, печатает Ч, если число единиц четное, и Н, если нечетно. Строке из нулей и единиц предшествуют и последуют пустые ячейки, обозначаемые #. Символы Ч или Н печатаются в первой пустой ячейке вслед за входной строкой. Таким образом, алфавит данной машины Тьюринга имеет вид:

A = {#, 0, 1, Ч, Н}.

Внутренние состояния: ; - начальное состояние. Машина останавливается по сигналу ОСТАНОВ.

Функции могут быть представлены табличным способом в следующем виде

v:	:	:

Удобнее задавать функции , пользуясь обозначениями Тьюринга. В этом варианте машина Тьюринга задается конечным множеством пятерок [ ]. В каждой такой пятерке

- текущее состояние машины;

- символ, считываемый из ячейки;

- следующее состояние машины, ;

- символ, печатаемый в ячейке, ;

- одна из команд П, Л, ОСТАНОВ.

В этих обозначениях описанная выше машина задается так:

	#		#	Л
				Л
				Л
				Л
				Л
				Л
				Л
	#		Ч	ОСТАНОВ
	#		Н	ОСТЕНОВ

Машины Тьюринга, могут вычислять разнообразные функции от чисел, подаваемых на вход. Стандартным представлением неотрицательного числа n в машине Тьюринга является последовательность из n +1 единиц, стоящих подряд. Два таких числа отделяются нулем. Так, строка...##111011##... представляет упорядоченную пару (2,1). Строка...##111101101011# #... представляет последовательность (3, 1, 0, 1).

Пример 2. Следующая машина Тьюринга складывает два неотрицательных целых числа, поданных на вход:

# # Л

1 1 Л

1 1 Л

0 1 Л

1 1 Л

# # П

1 # П

1 # ОСТАНОВ

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

3.3. СЛОЖНОСТЬ АЛГОРИТМОВ (АНАЛИЗ АЛГОРИТМОВ)

Основные понятия

Сложность алгоритмов – это величина, характеризующая длину описания алгоритма или громоздкость его применения к исходным данным.

Изучение сложностей алгоритмов началось в 60-х годах 20 века. Этот раздел теории алгоритмов имеет важное теоретическое и практическое значение. Разрабатываемые методы оценки сложности алгоритмов позволяют находить наиболее эффективные способы вычисления функций. В терминах сложностей алгоритмов можно уточнить и исследовать многие проблемы, связанные с нахождением оптимального алгоритма для решения конкретных задач.

Класс однородных вычислительных задач называется проблемой (массовой задачей).

Индивидуальные случаи проблемы Т называются частными случаями проблемы Т.

Таким образом, Т это множество всех своих частных случаев. Например, можно говорить о проблеме умножения матриц, частным случаем которой является нахождение произведения двух конкретных матриц.

Другим примером является задачи коммивояжера. Параметры этой массовой задачи - это множество «городов» и расстояний между каждый парой городов и из . Решение – это упорядоченный набор заданных городов, который минимизирует величину

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

С каждым частным случаем I проблемы Т (I Î Т) связывается размер | I |. Эта функция не единственна. Ее выбор определяется теоретическими и практическими соображениями, связанными с точками зрения на эту проблему.

Например, для пары квадратных матриц , размер­ности которых - , разумной мерой их умножения может служить величина . Однако, если изучается объем памяти, необходимый для алгоритма умножение матриц, то мера .

В задаче о коммивояжере | I | можно определить как количество данных городов m.

Пусть Т – проблема и А – алгоритм, решающий ее. При решении частного случая I Î Т алгоритм А выполняет некоторую последовательность вычислений .

При этом важны следующие характеристики:

длина _, которая характеризует время вычисления,

глубина _, то есть число уровней параллельных шагов, на которые может быть разложено,

объем памяти, требуемый для вычисления _,

число арифметических операций при алгебраических вычислениях или число обращений к памяти.

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

После выбора меры вычисления , функция сложности вычисления определяется несколькими способами. Главные из них – сложность в наихудшем случае и сложность поведения в среднем.

Сложность в наихудшем случае

.

Сложность поведения в среднем

,

где: и – вероятность появления I среди других случаев размера n.

3.3.2. Классификация задач по степени сложности

Сложность задачи – это сложность наилучшего алгоритма известного для ее решения.

Для оценки сложности важно следующее определение. Функция ¦ (n) есть , если существует константа С, такая, что .

Основной вопрос теории сложности – насколько успешно или с какой стоимостью может быть решена заданная проблема Т? Решение вопроса заключается в рассмотрении всех возможных алгоритмов проблем Т и попытке формулировки утверждения о вычислительной сложности внутренне присущей Т. Любой алгоритм А для Т дает верхнюю оценку величины F_A сложности Т. Однако математический интерес представляет знание нижней оценки. В этом случае она дает руководство в поиске хороших алгоритмов, указывая заведомо ложные попытки.

Быстрыми являются линейные алгоритмы, которые обла­дают сложностью порядка n и называются алгоритмами порядка , где n – размерность входных данных.

К линейным алгоритмам относится алгоритм нахождения суммы двух десятичных чисел. Его сложность – .

Существуют алгоритмы быстрее линейных. Например, алгоритм двоичного поиска в линейном упорядоченном массиве. Его сложность – , где: n – длина массива.

Полиномиальным алгоритмом (алгоритм класса Р) называется алгоритм, у которого временная сложность равна , где k – целое число >0. алгоритмы для временной сложности которых не существует такой оценки называются экспоненциальными (алгоритмы класса Е).

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

Задача называется «хорошей», если для нее существует полипомиальный алгоритм.

Примеры алгоритмов класса Р:

Задача Прима – Краскала. Дана плоская страна и в ней n – городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. Эта задача решается с помощью жадного алгоритма сложности .

Кратчайший путь на графе, состоящем из n вершин и m ребер. Сложность – .

Быстрое преобразование Фурье - , обычное преобразование Фурье – .

Умножение чисел. Алгоритм Шенхаге–Штрассена - . Школьный метод умножения .

Умножение матриц размерности (n ´ n). Алгоритм Штрассена . Обычный алгоритм О (n ³).

Примеры алгоритмов класса Е:

К экспоненциальным задачам относятся задачи, в которых требуется построить множество всех подмножеств данного множества, все полные подграфы некоторого графа или все поддеревья некоторого графа.

3.3.3. Недетерминированные алгоритмы и классы NP

алгоритмов

Недетерминированным называется алгоритм, который мо­жет находится одновременно во многих состояниях. Он не является ни вероятностным, ни случайным. Недетерминированный алгоритм исследует все альтернативные варианты одновременно. Если в одном из них обнаружен неправильный выбор, этот вариант прекращает выполняться. Если в каком-либо вари­анте найдено решение, то это решение фиксируется, а все остальные варианты прекращают свою работу.

Класс NP алгоритмов – это все задачи, которые можно решить недетерминированными алгоритмами, работающими в течении полиномиального времени.

К этому классу относятся задачи:

1) Задачи о выполнимости - существует ли для данной буле­вой формулы, заданной в КНФ, такое распределение истинност­ных значений, в которых она принимает истинное значение?

2) Задача коммивояжера.

3) Решение систем уравнений с целыми переменными.

4) Составление расписаний, учитывающих определенные условия.

5) Размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров.

6) Оптимальная загрузка емкости (рюкзак, поезд, корабль, самолет) при наименьшей стоимости.

7) Оптимизация раскроя (бумаги, картона, стального проката), маршрутов, инвестиций, станочного парка.

8) Задача распознавание простого числа. Самый лучший в настоящее время алгоритм имеет сложность порядка , где L (n) – количество цифр в числе n.

Хотя в данных задачах не содержатся экспоненциальных вычислений, тем не менее для них до сих пор не разработаны эффективные (то есть полиномиальные) алгоритмы.

ЗАКЛЮЧЕНИЕ

Данное пособие восполняет имеющиеся пробелы в учебной литературе по математической логике и теории алгоритмов.

Издание рекомендуется для работы студентов при самостоятельном изучении теоретического материала, на практических занятиях в качестве справочного пособия, а также при выполнении типовых расчетов и подготовки к зачетам и экзаменам, предусмотренных учебными планами по указанной дисциплине.

Пособие поможет более глубокому и полному усвоению студентами ученого материала по математической логике и теории алгоритмов и будет способствовать эффективной организации учебного процесса по этой дисциплине.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Яблонский С.В. Введение в дискретную математику: учеб. пособие для вузов /С.В.Яблонский.-3-е изд. - М.: Высш. шк. 2002. - 384 с.

Судоплатов С.В. Элементы дискретной математики: учебник / С.В.Судоплатов, Е.В. Овчинникова. - М.: ИНФРА-М, Новосибирск, Изд-во НГТУ, 2002. - 280 с.

Новиков Ф.А. Дискретная математика для программистов: учебник /Ф.А. Новиков. - СПб.: Питер, 2002.- 304с.

Шелупанов А.А. Математическая логика и теория алгоритмов: учеб. пособие /А.А. Шелупанов, В.М.Зюльков. - Томск: STT, 2001. - 176 с.

Столл Р. Множества, логика, аксиоматические теории /Р. Стол. - М.: Просвещение, 1968.- 231с.

Криницкий Н.А. Алгоритмы вокруг нас /Н.А. Криницкий. – Изд. 2-е. - М.: Наука, 1984. – 224с.

Биркгоф Г. Современная прикладная алгебра /Г. Биркгоф, Т. Барти. - М.: Мир, 1976. - 400с.

Карпов Ю.Г. Теория автоматов: учебник для вузов /Ю.Г. Карпов. - СПб.: Питер, 2003.- 208с.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ 3

1. КРАТКИЕ СВЕДЕНИЯ О МНОЖЕСТВАХ, ОТНОШЕНИЯХ

И АЛГЕБРАИЧЕСКИХ СИСТЕМАХ 5

1.1. Элементы теории множеств 5

1.1.1. Основные понятия 5

1.1.2. Операции над множествами 7

1.1.3. Алгебраические свойства операций над множествами 9

1.2. Отношения 10

1.2.1. Понятие отношения 10

1.2.2. Операции над отношениями 13

1.2.3. Свойства отношений на множестве 14

1.2.4. Отношения эквивалентности, толерантности и порядка 15

1.3. Понятие алгебраической системы 16

1.3.1. Понятие отображения 16

1.3.2. Алгебраическая операция 17

1.3.3. Общие сведения об алгебраических системах 19

1.4. Реляционная алгебра 20

1.4.1. Алгебра отношений 20

1.4.2. Реляционная алгебра 22