Новая философская энциклопедия. Том первый. А - Д. - Коллектив авторов (е книги txt) 📗

74

АЛГЕБРА ЛОГИКИ ниями буквенных переменных) и системы операций над объектами этого множества, удовлетворяющих тождествам из полной системы тождеств этого «языка». «Язык» КДО в результате такого шага абстракции превращается в «язык» т. н. булевой алгебры, «язык» УСЕ - в «язык» т. н. дистрибутивной структуры. Важным примером булевой алгебры является алгебра классов, в которой роль элементов играют подмножества (классы) некоторого фиксированного множества (т. н. универсума) ?/, роль О играет пустое множество 0, роль 1 - само U, роль AB, AvB и -Л ~ теоретико-множеств. операции пересечения, объединения и дополнения соответственно. Связь между алгеброй классов, алгеброй предикатов и алгеброй высказываний, этими тремя важнейшими интерпретациями абстрактной алгебры логики как «языка» булевой алгебры, состоит в следующем: первая переходит во вторую путем замены множеств (классов) их т. н. характеристическими предикатами (т. е. множества А - предикатом хеА, гласящим: «х принадлежит множеству А»), если при этом соответствующим образом преобразуются также операции и константы 0 и 1, а вторая переходит в третью при подстановке во все предикаты на место их аргументов некоторого фиксированного их значения. Вернее, при таком переходе от алгебры классов к алгебре предикатов получается алгебра одноместных предикатов. Другим важным случаем является алгебра двуместных предикатов, называемых чаще отношениями. С ней тесно связана алгебра отношений, отличающаяся от нее только тем, что в последней, кроме трех операций булевой алгебры, имеются еще две. Всякую булеву алгебру можно «переделать» в булево кольцо, определив операцию А+Всогласно закону X (и отбросив операцию AvB). Напр., в случае алгебры множеств роль А+В играет т. н. симметрическая разность множеств А и В (состоящая из всех тех элементов универсума, которые принадлежат одному и только одному из множеств А или В). Обратно, всякое булево кольцо (с единицей) можно «переделать» в булеву алгебру. Понятия булевой алгебры и булева кольца связываются с именем Дж. Буля. Однако оформились эти понятия (не говоря уже о терминах) значительно позже. Первые работы по алгебре логики были посвящены задачам: а) выражения логических соотношений между объемами понятий (соответственно высказываниями) в виде уравнений (равенств), б) построения алгоритмов решения логических уравнений и систем уравнений с целью автоматизировать способы извлечения из данных посылок содержащейся в них (неявно) информации (того или иного рода). В настоящее время алгебра логики развивается гл. о. под влиянием задач, встающих в области ее приложений. Она находит широкое применение в технике (особенно при решении задач, связанных с построением автоматов) и, наоборот, развивается сама под влиянием запросов техники (задач автоматизации программирования, уменьшения числа элементов в устройствах релейного действия и др.). Важную роль играют приложения в теории электрических схем, включая первоначально, начиная с работ В. И. Шестакова и К. Шеннона (30~40-е гг. 20 в.), теорию релейно-контактных схем. Вопросы, касающиеся понятий самой алгебры логики, приводят к проникновению в алгебру логики неалгебраических методов (таких, как табличные, топологические, дескриптивные) и вследствие этого к постепенному вьшелению из алгебры логики самостоятельной области - теории функций алгебры логики (или иначе, теории булевых функций). В случае более сложных схем, чем контактные, приходится часто отказываться от использования лишь обычной алгебры логики и рассматривать те или иные ее многозначные обобщения, отличные от булевых алгебр и булевых колец (см. Многозначные логики). Другим направлением современного развития алгебры логики является алгебраическая логика. Она интересна тем, что выдвигает и частично решает задачу построения алгебр неклассических логик, т.е. таких вариантов алгебры логики, которые соответствуют неклассическим исчислениям высказываний. Некоторые тенденции возможного дальнейшего развития алгебры логики как совокупности алгебраических методов логики намечаются в связи с бурным развитием ряда областей как современной алгебры, так и математической логики. Одна из них связана с мощным ростом теоретико-множественной алгебры, позволяя всякую операцию рассматривать как алгебраическую операцию. Такое рассмотрение дает возможность охватить алгебраическими методами значительную часть современной математической логики (см. Логика символическая). Другая - связана с успехами теории алгоритмов, позволившей уточнить ряд алгоритмических проблем алгебры, и последовавшим решением некоторых из них. Тенденция эта состоит в объединении алгоритмической алгебры с самой теорией алгоритмов м попытках алгебраизации последней, т.е. построения алгебраической теории алгоритмов. Эта постепенная алгебраизация все большего числа сторон математической логики будет, по-видимому, содействовать наилучшему вьшелению и ее чисто логических сторон, для того чтобы изучать последние уже иными методами. А В. Кузнецов Сокращенный вариант статьи: Алгебра логики. — В кн.: Философская энциклопедия. Т. 1. М., 1960. Как и предвидел А. Кузнецов, все большее прикладное значение приобретает теория булевых функций как самостоятельная область, выделившаяся из алгебры логики. В результате пришли к понятию функциональной системы (Рп, Q, где Рп есть множество всех функций л-значной логики (или множество всех функций счетнозначной логики PJ с заданной на нем операцией суперпозиции С. Рп обычно рассматривается как обобщение множества всех булевых функций Рт Известна содержательная трактовка понятия функциональной системы ((Рп, Q выступает ее частным случаем), в основе которой лежит рассмотрение таких пар (Р, П), в которых Р есть множество отображений, реализуемых управляющими системами из некоторого класса, a ? состоит из операции, используемой при построении новых управляющих систем из заданных. В свою очередь (Pv С) есть эквивалент алгебры логики. Таким образом, от алгебры формул, изучаемой в алгебре логики, перешли к алгебре функций. И хотя именно алгебра логики, т.е. классическая логика высказываний, лежит в основе проектирования микросхем для современной цифровой электронной техники, в том числе и для компьютеров, подобные работы ведутся и на основе многозначных логик. В частности, для функционально полных (и некоторых других) многозначных систем был построен аналог совершенной днф. Еще более важное предвидение А. Кузнецова связано с выделением алгебраической логики в одно из направлений современной алгебры логики. В первую очередь имеется в виду построение алгебр, соответствующих неклассическим логикам в том смысле, в каком булева алгебра соответствует классической логике высказываний (Rasiowa, 1974). Здесь существенным является также вопрос о построении алгебраической семантики, под которой понимается класс всех моделей некоторой алгебры, соответствующей логике L, поскольку посредством алгебраической семантики решаются такие металогические проблемы, как полнота L (относительно общезначимости в классе всех моделей), разрешимость L и др. В итоге пришли к общему вопросу о том, какая логика алгебраически представима, т.е. имеет алгебраическую семантику, а какая нет. Ответ на этот вопрос дан в работе В. Блока и Д. Пигоцци (Blok, Pigozzi, 1989). Существенно, что современное развитие алгебраической

75

АЛГОРИТМ логики представляет собой систематическое применение методов и, главное, аппарата универсальной алгебры к символической логике. Именно на это как на тенденцию возможного дальнейшего развития алгебры логики указывал А. Кузнецов, говоря о возможности «охватить алгебраическими методами значительную часть современной математической логики». Сегодня речь уже идет об алгебраическом охвате всей символической логики, и результаты здесь весьма значительны. К примеры, если Alg(L) обозначает класс алгебр, который соотносится с некоторой логикой L (если L есть классич. логика высказываний, то Alg(L) есть класс булевых алгебр), можно формулировать теоремы, утверждающие, что L имеет определенное логическое свойство тогда и только тогда (т. т. т.), когда Alg(L) имеет определенное алгебраическое свойство. Это позволяет дать алгебраическую характеризацию таких логических свойств, как полнота, наличие теоремы дедукции, компактность, разрешимость, интерполяционность Крейга, истинность формул в модели и т. д. Так, первые два свойства принимают следующий вид: L допускает строго полную гильбер- товскую аксиоматизацию (Г,_ А т. т. т., когда Г ^ А) т. т. т., когда Alg(L) есть финитно аксиоматизируемое квази-мно- гообразие; L допускает теорему дедукции (см. Дедукции теорема) т. т. т., когда Alg(L) имеет эквационально определимые главные конгруэнции. Вообще, алгебраическая логика является хорошим инструментом не только для выяснения взаимоотношения между различными логическими системами, но и для уточнения статуса логики. Лит.: Жегалкин Я. И. Арифметизация символической логики. - «Матем. сб.», т. 35. Вып. 3-4. М., 1928; Яновская С. А. основания математики и математическая логика. - В кн.: Математика в СССР за тридцать лет (1917-1947). М.-Л., 1948; Онаже. Математическая логика и основания математики. - В кн.: Математика в СССР за сорок лет (1917-1957), т. 1. М., 1959; Сб. статей по математической логике и ее приложениям к некоторым вопросам кибернетики. М., 1958; Войшвилго Е. К. Метод упрощения форм выражения функций истинности. - «Философские науки», 1958, № 2; Кузнецов А. В. Алгоритмы как операции в алгебраических системах. - «Успехи математических наук», 1958, т. 13, в. 3; Новиков П. С. Элементы математической логики. М., 1973; Биркгоф Г. Теория решеток. М., 1952; Владимиров Д. А. Булевы алгебры. 1969; Гиндикин С. Г. Алгебра логики в задачах. М., 1972; Кудрявцев В. Б. О функциональных системах. М., 1981; Яблонский С. В., Гаврилов Г. #., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М., 1966; Фридлендер Б. #., Ревякин А. М. Булева алгебра и ее применение в задачах электроники: учебное пособие. М., 1993; Algebraic logic and the methodology of applying it.—CSU Publications, 1995; Anderka H., Nemeti L, Sain L Algebraic Logic— Handbook of philosophical logic (2 ed.), forthcoming; Blok W. /., Pigozzi D. Algebraizable logics (monograph).—Memoirs of the American Mathematical Society, 1989, № 396; Font J. M., Jansana R. A general algebraic semantics for sentential logics. В., 1996; Handbook of Boolean algebras, Ed. J. D. Monk with the coop. R. Bennet, v. I—Ш. Amst., 1989; Nemeti I, Anderka H. General algebraic logic: a perspective on «What is logic».- What is logical system? Oxf., 1994; N. Y, 1995; Rasiowa H. An algebraic approach to non-classical logics. Warsz., 1974. А. С. Карпенко АЛГОРИТМ, алгоритм (от лат. algorithmi, algorismus, no имени арабского ученого 9 в. ал-Хорезми) — точное предписание, задающее потенциально осуществимый (см. Абстракция потенциальной осуществимости) вычислительный процесс (процесс исполнения алгоритма), ведущий от исходныхданных, которые могут варьировать, к конечному результату. Овладение общим методом решения точно поставленной задачи по сути дела означает знание алгоритма. Так, умение складывать два числа означает владение алгоритмом сложения чисел (напр., сложением столбиком, которому учат в школе). Необходимо различать алгоритм и алгоритмическое предписание, имеющее внешнюю форму алгоритма, но включающее не до конца определенные шаги. Так, для перевода текста с одного естественного языка на другой нельзя дать алгоритм, поскольку придется апеллировать к таким неточным понятиям, как смысл и контекст. При попытке же применения точного алгоритма получается то, что в более откровенной форме выдают машинные переводчики и в более мягкой, но от этого не менее вредной — профессиональные переводчики в тот момент, когда выходят за рамки полностью освоенных ими понятий и действий. Поскольку процесс исполнения потенциально осуществим, в теоретическом определении алгоритма отвлекаются от реальных ограничений на ресурсы и следят лишь за тем, чтобы в любой момент вычисления требуемая информация и другие ресурсы были конечными. При создании практических алгоритмов проблемы сложности выходят на первый план. Хотя неформально математики все время занимались поиском алгоритмов, данное понятие было уточнено лишь в 30-х гг. 20 в. Первыми уточнениями были абстрактные определении частично-рекурсивных и представимых функций в формальной теории чисел, появившиеся в связи с задачами доказательств теории. В 1936 Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и подметили, что любой алгоритм в интуитивном смысле слова может быть реализрован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий. Так, памятью машины Тьюринга является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, т.е. либо пуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки, которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке. Это действие имеет вид совокупности элементарных инструкций формы ab(L, R, S)i, в которой присутствует лишь одна из букв Z, R, S. Z, — приказ сдвинуться на следующем такте на одну клетку влево, R — вправо, S — остаться на месте. Элементарная инструкция означает следующее: если машина видит а, записать в клетку 6, передвинуться в соответствии с командой и перейти к исполнению команды /. Такая элементарность действий машины явилась результатом проведенного Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов. Команды машины Поста предвосхитили систему команд современных вычислительных машин. В машине имеются регистры, содержащие натуральные числа, элементарные операции увеличения и уменьшения числа на 1 и условный переход, если число в регистре равно 0. Одновременно А, Чёрч и X. Б. Карри создали одно из самых абстрактных