Новая философская энциклопедия в четырех томах научно-редакционный совет

Этих тождеств достаточно для того, чтобы из них можно было вывести любое (верное) тождество, обе части которого суть выражения «языка» УСЕ. А добавив к ним тождества VIII, мы сможем выводить и все тождества «языка» КДО.

Выражение «языка» УСЕ называется приведенным полиномом (п. п.), если оно есть 1+1 (т. е. нуль) или имеет вид а^а]+ ... +А„ где каждый член Αι есть либо 1, либо буквенная переменная, либо произведение последних, причем ни в одном члене нет никаких повторений букв, никакие два члена не одинаковы (в том же смысле, что и выше), a s не обязательно больше 1 (т. е. знаков «+» может не быть). Всякое выражение алгебры логики можно привести к п. п. (теорема Жегалкина).

Кроме «языков» КДО и УСЕ существуют и другие «языки», обладающие тем свойством, что через операции (и константы) этих «языков» можно представить всякую функцию алгебры логики. Такие системы называются (функционально) полными. Примеры полных систем: а) конъюнкция и отрицание, б) дизъюнкция и отрицание, в) импликация и отрицание, г) импликация и 0, д) умножение, эквиваленция и 0, е) штрих Шеффера А[В, ж) медиана (Л, В, С), (определение: (А, В, C)=ABvACvBC\, отрицание и 1, и) медиана, эквиваленция и сложение.

Иногда совершают еще один важный дальнейший шаг абстракции. Отвлекаются от табличного задания операций и от того, что значениями буквенных переменных являются высказывания. Вместо этого допускаются различные интерпретации рассматриваемого «языка», состоящие из той или иной совокупности объектов (служащих значениями буквенных переменных) и системы операций

«Язык» КДО в результате такого шага абстракции превращается в «язык» т. н. булевой алгебры, «язык» УСЕ—в «язык» т. н. булева кольца (с единицей), .«язык» конъюнкции и дизъюнкции — в «язык» т. н. дистрибутивной структуры.

Важным примером булевой алгебры является алгебра классов, в которой роль элементов играют подмножества (классы) некоторого фиксированного множества (т. н. универсума) V, роль 0 играет пустое множество 0, роль 1—само Ü, роль AS, AvB и -ιΑ— теоретико-множеств. операции пересечения, объединения и дополнения соответственно. Связь между алгеброй классов, алгеброй предикатов и алгеброй высказываний, этими тремя важнейшими интерпретациями абстрактной алгебры логики как «языка» булевой алгебры, состоит в следующем: первая переходит во вторую путем замены множеств (классов) их т. н. характеристическими предикатами (т. е. множества Л—предикатом хеА, гласящим: «х принадлежит множеству А*), если при этом соответствующим образом преобразуются также операции и константы 0 и I, а вторая переходит в третью при подстановке во все предикаты на место их аргументов некоторого фиксированного их значения. Вернее, при таком переходе от алгебры классов к алгебре предикатов получается алгебра одноместных предикатов. Другим важным случаем является алгебра двуместных предикатов, называемых чаще отношениями. С ней тесно связана алгебра отношений, отличающаяся от нее только тем, что в последней, кроме трех операций булевой алгебры, имеются еще две.

Всякую булеву алгебру можно «переделать» в булево кольцо, определив операцию А+В согласно закону Χ (и отбросив операцию Ανΰ). Напр., в случае алгебры множеств роль А+В играет т. н. симметрическая разность множеств А и В (состоящая из всех тех элементов универсума, которые принадлежат одному и только одному из множеств А или ΰ). Обратно, всякое булево кольцо (с единицей) можно «переделать» в булеву алгебру. Понятия булевой алгебры и булева кольца связываются с именем Дж. Буля. Однако оформились эти понятия (не говоря уже о терминах) значительно позже, Первые работы по алгебре логики были посвящены задачам: а) выражения логических соотношений между объемами понятий (соответственно высказываниями) в виде уравнений (равенств), б) построения алгоритмов решения логических уравнений и систем уравнений с целью автоматизировать способы извлечения из данных посылок содержащейся в них (неявно) информации (того или иного рода).

В настоящее время алгебра логики развивается гл. о. под влиянием задач, встающих в области ее приложений. Она находит широкое применение в технике (особенно при решении задач, связанных с построением автоматов) и, наоборот, развивается сама под влиянием запросов техники (задач автоматизации программирования, уменьшения числа элементов в устройствах релейного действия и др.). Важную роль играют приложения в теории электрических схем, включая первоначально, начиная с работ В. И. Шестакова и К. Шеннона (30—40-е гг. 20 в.), теорию релейно-контакгных схем. Вопросы, касающиеся понятий самой алгебры логики, приводят к проникновению в алгебру логики неалгебраических методов (таких, как табличные, топологические, дескриптивные) и вследствие этого к постепенному выделению из алгебры логики самостоятельной области—теории функций алгебры логики (или иначе, теории булевых функций).

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

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

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

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

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

Сокращенный вариант статьи: Алгебра логики.— В кн.: Философская энциклопедия. Т. 1. M., I960.

Как и предвидел А. Кузнецов, все большее прикладное значение приобретает теория булевых функций как самостоятельная область, выделившаяся из алгебры логики. В результате пришли к понятию функциональной системы (Ря, С), где Ря есть множество всех функций и-значной логики (или множество всех функций счетаозначной логики Р») с заданной на нем операцией суперпозиции С. Р, обычно рассматривается как обобщение множества всех булевых функций Рг. Известна содержательная трактовка понятия функциональной системы ((Р„ С) выступает ее частным случаем), в основе которой лежит рассмотрение таких пар (Ρ, Ω), в которых Р есть множество отображений, реализуемых управляющими системами из некоторого класса, a Ω состоит из операции, используемой при построении новых управляющих систем из заданных. В свою очередь (Рг, С) есть эквивалент алгебры логики. Таким образом, от алгебры формул, изучаемой в алгебре логики, перешли к алгебре функций. И хотя именно алгебра логики, т. е. классическая логика высказываний, лежит в основе проектирования микросхем для современной цифровой электронной техники, в том числе и для компьютеров, подобные работы ведутся и на основе многозначных логик. В частности, для функционально полных (и некоторых других) многозначных систем был построен аналог совершенной днф, Еще более важное предвидение А. Кузнецова связано с выделением алгебраической логики в одно из направлений современной алгебры логики. В первую очередь имеется в виду построение алгебр, соответствующих неклассическим логикам в том смысле, в каком булева алгебра соответствует классической логике высказываний (Rasiowa, 1974). Здесь существенным является также вопрос о построении алгебраической семантики, под которой понимается класс всех моделей некоторой алгебры, соответствующей логике L, поскольку посредством алгебраической семантики решаются такие металогические проблемы, как полнота L (относительно общезначимости в классе всех моделей), разрешимость L и др. В итоге пришли к общему вопросу о том, какая логика алгебраически представима, т. е. имеет алгебраическую семантику, а какая нет. Ответ на этот вопрос дан в работе В. Блока и Д. Пигоцци (Blök, Pigozzi, 1989). Существенно, что современное развитие алгебраической

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

Хотя неформально математики все время занимались поиском алгоритмов, данное понятие было уточнено лишь в 30-х гг. 20 в. Первыми уточнениями были абстрактные определения частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами доказательств теории. В 1936 Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и подметили, что любой алгоритм в интуитивном смысле слова может быть реализован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий. Так, памятью машины Тьюринга является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, т. е. либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки, которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab{L, R, S)i, в которой присутствует лишь одна из букв L, R, S. — приказ сдвинуться на следующем такте на одну клетку влево, R—враво, S— остаться на месте. Элементарная инструкция означает следующее: если машина видит а, записать в клетку Ь, передвинуться в соответствии с командой и перейти к исполнению команды /. Такая элементарность действий машины явилась результатом проведенного Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов. Команды машины Поста предвосхитили систему команд современных вычислительных машин. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно 0. Одновременно А. Черч и X. Б, Карри создали одно из самых абстрактных

И ранее созданные теоретические понятия, и самые элементарные, и самые абстрактные из вновь появившихся уточнений алгоритма оказались эквивалентны. Этот факт, подтвержденный в дальнейшем для всех вновь появлявшихся точных определений алгоритма, послужил основой утверждения, скромно называемого в математике тезисом Черча, хотя степень его подтвержденности ныне выше, чем у любого физического «закона». Содержательное понятие алгоритма эквивалентно по объему любому из имеющихся в данный момент математических уточнений этого понятия, в частности вычислимости на машине Тьюринга.

Одним из последних появилось уточнение алгоритма, наиболее близкое к современным языкам программирования, — рекурсивные схемы Скотта. Это — совокупность определений вида

/(5c)<=if P(x) then t(x) else rÇc), где Зс— кортеж переменных, а сами определяемые функции могут входить в выражения /, г. Определение понимается следующим образом: проверяется предикат Р, если он истинен, вычисляется /, иначе г. Если в вычисляемом выражении встречаются определяемые функции, они вновь по тем же правилам заменяются на их определения. Хотя по объему определяемых функций существующие уточнения понятия алгоритма эквивалентны, они различаются по своей направленности. Эти различия можно подчеркнуть, рассматривая относительные алгоритмы, строящиеся на базе некоторых абстрактных структур данных и операций над ними. Относительные алгоритмы, получающиеся на базе различных определений алгоритма, могут определять разные классы функций при одних и тех же исходных структурах и элементарных операциях. Так, напр., машины Тьюринга приводят к одним из наиболее узких определений относительных алгоритмов, а комбинаторная логика и рекурсивные схемы—наоборот, к весьма широким.

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

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

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

Множество, характеристическое свойство которого является всюду определенным вычислимым предикатом, называется разрешимым. Множество, принадлежность элемейта которому можно установить за конечное число шагов применением некоторого алгоритма, называется перечислимым. Напр., множество тавтологий классической логики высказываний разрешимо, а множество тавтологий классической логики предикатов перечислимо. Заметим, что в случае перечислимого множества алгоритмически установить можно лишь истинность, а не ложность. В классической математике имеет место следующий критерий разрешимости: множество разрешимо, если и оно, и его дополнение перечислимы. В конструктивной этот критерий эквивалентен принципу Маркова (см. Конструктивное направление). Другая характеризация перечислимого множества—множество объектов, выводимых в некотором исчислении. Необходимо отметить, что схема вычислительного процесса на компьютере конца 20 в.—написание программы на языке высокого уровня, трансляция ее в машинный язык и исполнение компьютером—имеет теоретической, основой теорему об универсальном алгоритме. При любом точном определении алгоритмов каждый алгоритм может быть задан своим определением, которое является конструктивным объектом. Этот конструктивный объект может быть алгоритмически в содержательном смысле (и при этом достаточно просто и естественно) закодирован тем видом конструктивных объектов, которые обрабатываются данными алгоритмами. Напр., определение алгоритма может быть записано как слово в некотором алфавите, а если мы взяли определение алгоритма, в котором рассматриваются лишь натуральные числа, такое слово может быть естественно представлено как число в системе счисления, основанием которой является количество букв в алфавите. Тогда имеется универсальный алгоритм U, перерабатывающий любую пару (ψ, Р), где ф—конструктивный объект, называемый записью или программой (относительно Ü) алгоритма ф, в результат применения ψ к Р. Универсальный алгоритм не может быть всюду определен. Примером универсального алгоритма может служить транслятор с алгоритмического языка, в частности с Паскаля, вместе с операционной системой, исполняющей получившуюся программу.

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

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

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

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

Число шагов и используемая память —взаимозависимые характеристики вычислительного процесса. Часто удается убыстрить процесс, задействовав бодыяе памяти, либо уменьшить память, увеличив число шагов процесса. Но такая оптимизация ресурсов возможна лишь в ограниченных пределах, и более критическим является число шагов. Память теоретически можно неограниченно уменьшать, замедляя программу (конечно же она тем не менее растет с ростом исходных данных, но не более чем линейно). Имеются и такие случаи, когда за счет сложности описания алгоритма можно неограниченно убыстрять процесс вычисления (теорема об ускорении). Тем не менее практически и здесь быстро наступает предел ввиду неустойчивости работы сложных алгоритмов.

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

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

Прямая и обратная функции могут сильно различаться по сложности, поэтому можно строить простые коды, практически не расшифровываемые без знания ключа. Это послужило основой современной практики кодирования и электронных подписей.
Сложность описания системы—гораздо более сложный объект, чем само ее описание, Т. о., познать систему полностью может лишь система более высокого порядка. Минимум сложности описаний конструктивных объектов с данным числом элементов растет медленнее, чем любая вычислимая функция (т, о., есть громадные, но исключительно просто описываемые объекты, напр. ΙΟ¹⁰¹⁰). Сложность описания большинства объектов данной длины не намного ниже, чем длина записи этих объектов. Т. о., возникает понятие содержательного случайного объекта, не описываемого кратко никакими алгоритмическими средствами.

На основе теории сложности описания А. Н. Колмогоров, Л, А. Левин, П. Мартин-Леф и другие развили алгоритмическую теорию вероятностей. Основой данной теории явилось содержательное определение случайной последовательности по Р. Мизесу. Двоичная последовательность случайна, если из нее нельзя выбрать никакую последовательность с другой частотой нулей и единиц. Напр., последовательность 0, 1, 0, !.„ неслучайна, поскольку последовательность ее четных членов состоит из одних единиц. В классической математике такое определение пусто. А. Н, Колмогоров уточнил его, предложив рассматривать лишь алгоритмические перестановки подмножеств членов данной последовательности. Оказалось, что случайность связана со сложностью определения. Сложность фрагментов случайной последовательности пропорциональна длине их записи. Итак, содержательно случайные объекты являются приближениями к случайньщ последовательностям.

Для любой совокупности программ, имеющих ограниченную сложность, можно построить ограниченный универсальный алгоритм, исполняющий все их без ошибок, но его сложность будет неизмеримо выше, чем сложность исполняемых программ. Далее, можно построить алгоритмический процесс, расширяющий ограниченный универсальный алгоритм с тем, чтобы включить любую предъявленную программу, не входящую в данный класс, но при этом сложность универсального метода станет еще выше. Уже один шаг данного процесса диагонализации далеко выводит за рамки класса функций, считающихся реально вычислимыми. Это—алгоритмическая основа софизма, примененного в аргументе Саймона (см. Парадокс логический). Заметим, что тезис Черча содержит одно важное онтологическое предположение: о невозможности обозреть вечность. Поэтому в общей теории относительности (в частности, во вселенной Гёделя, в которой время может ходить по кругу) имеются миры, в которых, пролетая сквозь вращающуюся черную дыру, можно вычислить алгоритмически иевычислимую функцию. Класс функций, которые могут быть вычислены в таких Вселенных, называется гиперарифметическим. Он неопределим в арифметике и определим лишь в анализе.