Новая философская энциклопедия В 4 томах. Том 1 (1184478), страница 47
Текст из файла (страница 47)
Логика символическая).Другая - связана с успехами теории алгоритмов, позволившей уточнить ряд алгоритмических проблем алгебры, и последовавшим решением некоторых из них. Тенденция эта состоит в объединенииалгоритмической алгебры с самой теорией алгоритмов м попыткахалгебраизации последней, т.е. построения алгебраической теорииалгоритмов.Эта постепенная алгебраизация все большего числа сторон математической логики будет, по-видимому, содействовать наилучшемувыделению и ее чисто логических сторон, для того чтобы изучатьпоследние уже иными методами.А.
В. КузнецовСокращенный вариант статьи: Алгебра логики. —В кн.: Философская энциклопедия. Т. 1. М., 1960.Как и предвидел А. Кузнецов, все большее прикладноезначение приобретает теория булевых функций как самостоятельная область, выделившаяся из алгебры логики. Врезультате пришли к понятию функциональной системы(Рп, С), где Рп есть множество всех функций л-значной логики (или множество всех функций счетнозначной логикиPJ с заданной на нем операцией суперпозиции С. Рп обычно рассматривается как обобщение множества всех булевыхфункций Р2. Известна содержательная трактовка понятияфункциональной системы ((Pa,Q выступает ее частным случаем), в основе которой лежит рассмотрение таких пар (Р,Ω), в которых Ρ есть множество отображений, реализуемыхуправляющими системами из некоторого класса, а Ω состоитиз операции, используемой при построении новых управляющих систем из заданных.
В свою очередь (Р2, Q есть эквивалент алгебры логики. Таким образом, от алгебры формул,изучаемой в алгебре логики, перешли к алгебре функций. Ихотя именно алгебра логики, т.е. классическая логика высказываний, лежит в основе проектирования микросхем для современной цифровой электронной техники, в том числе и длякомпьютеров, подобные работы ведутся и на основе многозначных логик. В частности, для функционально полных(и некоторых других) многозначных систем был построенаналог совершенной днф.Еще более важное предвидение А. Кузнецова связанос выделением алгебраической логики в одно из направлений современной алгебры логики.
В первую очередьимеется в виду построение алгебр, соответствующихнеклассическим логикам в том смысле, в каком булева алгебра соответствует классической логике высказываний(Rasiowa, 1974). Здесь существенным является такжевопрос о построении алгебраической семантики, подкоторой понимается класс всех моделей некоторой алгебры, соответствующей логике L, поскольку посредством алгебраической семантики решаются такие металогические проблемы, как полнота L (относительнообщезначимости в классе всех моделей), разрешимостьL и др.
В итоге пришли к общему вопросу о том, какаялогика алгебраически представима, т.е. имеет алгебраическую семантику, а какая нет. Ответ на этот вопросдан в работе В. Блока и Д. Пигоцци (Blok, Pigozzi, 1989).Существенно, что современное развитие алгебраической75АЛГОРИТМлогики представляет собой систематическое применениеметодов и, главное, аппарата универсальной алгебры ксимволической логике. Именно на это как на тенденцию возможного дальнейшего развития алгебры логики указывалА. Кузнецов, говоря о возможности «охватить алгебраическими методами значительную часть современной математической логики». Сегодня речь уже идет об алгебраическом охвате всей символической логики, и результаты здесьвесьма значительны.
К примеры, если AJg(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 andthe methodology of applying it.—CSLI Publications, 1995; AnderkaH., Nemeti I., Sain I. Algebraic Logic— Handbook of philosophicallogic (2 ed.), forthcoming; Blok W. J., Pigozzi D. Algebraizable logics(monograph).—Memoirs of the American Mathematical Society,1989, № 396; Font J. M., Jansana R. A general algebraic semanticsfor 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 islogic»,— What is logical system? Oxf., 1994; N. Y, 1995; Rasiowa H.An algebraic approach to non-classical logics. Warsz., 1974.А. С. КарпенкоАЛГОРИТМ, алгоритм (от лат.
algorithmi, algorismus, noимени арабского ученого 9 в. ал-Хорезми) — точное предписание, задающее потенциально осуществимый (см. Абстракция потенциальной осуществимости) вычислительный процесс (процесс исполнения алгоритма), ведущий от76исходныхданных, которые могут варьировать, к конечномурезультату. Овладение общим методом решения точно поставленной задачи по сути дела означает знание алгоритма.Так, умение складывать два числа означает владение алгоритмом сложения чисел (напр., сложением столбиком,которому учат в школе). Необходимо различать алгоритми алгоритмическое предписание, имеющее внешнюю форму алгоритма, но включающее не до конца определенныешаги. Так, для перевода текста с одного естественного языка на другой нельзя дать алгоритм, поскольку придетсяапеллировать к таким неточным понятиям, как смысл иконтекст.
При попытке же применения точного алгоритма получается то, что в более откровенной форме выдаютмашинные переводчики и в более мягкой, но от этого неменее вредной — профессиональные переводчики в тотмомент, когда выходят за рамки полностью освоенных имипонятий и действий.Поскольку процесс исполнения потенциально осуществим, в теоретическом определении алгоритма отвлекаются от реальных ограничений на ресурсы и следят лишь затем, чтобы в любой момент вычисления требуемая информация и другие ресурсы были конечными. При созданиипрактических алгоритмов проблемы сложности выходятна первый план.Хотя неформально математики все время занимались поиском алгоритмов, данное понятие было уточнено лишь в30-х гг.
20 в. Первыми уточнениями были абстрактные определении частично-рекурсивных и представимых функций вформальной теории чисел, появившиеся в связи с задачамидоказательств теории. В 1936 Э. Пост и А. Тьюринг независимо друг от друга предложили понятия абстрактных вычислительных машин и подметили, что любой алгоритм винтуитивном смысле слова может быть реализрован на данных машинах, несмотря на кажущуюся примитивность ихэлементарных действий. Так, памятью машины Тьюрингаявляется потенциально бесконечная лента, в каждой клеткекоторой записан символ из заранее заданного конечного алфавита.
Более того, достаточно рассматривать ленту, каждаяклетка которой содержит один бит информации, т.е. либопуста, либо содержит символ |. Процессор машины Тьюринга состоит из головки, которая в любой момент обозревает одну клетку, и программы, состоящей из конечногочисла команд, обычно нумеруемых натуральными числами.Каждая команда представляет собой условное действие,зависящее от символа, записанного в клетке. Это действиеимеет вид совокупности элементарных инструкций формыab(L, R, S)i, в которой присутствует лишь одна из букв L, R,S. L — приказ сдвинуться на следующем такте на одну клетку влево, R — вправо, S — остаться на месте.
Элементарнаяинструкция означает следующее: если машина видит а, записать в клетку Ъ, передвинуться в соответствии с командойи перейти к исполнению команды /. Такая элементарностьдействий машины явилась результатом проведенного Тьюрингом методологического анализа элементарных действийчеловека по исполнению алгоритмов.Команды машины Поста предвосхитили систему командсовременных вычислительных машин. В машине имеютсярегистры, содержащие натуральные числа, элементарныеоперации увеличения и уменьшения числа на 1 и условныйпереход, если число в регистре равно 0.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
