Албанская философская и общественная мысль—алгебра логики 33 2 глава

Такие уже встречавшиеся выше словесные выражения, как «множитель члена днф», «множители совершенной кнф» и т. п., становятся еще более понятными и оправданными после совер­шения еще одного, часто употребляемого в А. л. шага абстракции. Последний состоит в отождествлении И с числом 1, а л — с числом 0. Это еще больше сближает А. л. с обычной школьной алгеброй и арифметикой. Таблица конъюнкции при этом приоб­ретает следующий вид: 0-0=0, 0-1 = 0, 1-0 = 0, 1-1 = 1, т. е. конъюнкция становится обычным умножением в области чисел 0 и 1. Вводится еще одна операция A-i-B, задаваемая таблицей: 0+0=0,0 + 1 = 1,1+0 = 1, 1 + 1=0. Она наз. сложением (точнее сложением по модулю 2; др. назв.: разделительная дизъюнкция; читается: «А плюс В», или «А не эквивалентно В», или «Либо А, либо В»),

Всякую функцию А. л. можно представить через умножение (т. е. конъюнкцию), сложение и константу 1 (теорема Жегалки-на). В частности, верны следующие тождества:

VIII. АУ В = АВ + А + В, А = А+ I IX. А-+ В = АВ + А + 1, А~В = А + В + 1. Обратные представления имеют вид

X. А + В = АВ V АВ, 1 = А V А. Тождества VIII позволяют «переводить» выражения «языка» конъ­юнкции, дизъюнкции и отрицания (КДО) на «язык» умножения, сложения и единицы (УСЕ), а тождества X — осуществлять обратный «перевод». Только «переводы» эти таковы, что «пере­ведя» по этим тождествам выражение с первого языка на второй, а то, что получится, обратно на первый, мы, как правило, получим не то выражение, из к-poro исходили, а более сложное, хотя, во всяком случае, и тождественно равное ему; пример: А V В = АВ + А +В = АВ + (,АВ~\АВ) =

= АВАВ~\ АВ \/ ~АВ(АВ V АВ). Тождеств, преобразования можно производить и на «языке» УСЕ, что даже гораздо удобнее, чем на «языке» КДО, т. к. они при этом гораздо более похожи на те, к-рые привычны для всех, знающих школьную алгебру. В основе их лежат следующие тождества: _{XJ Ав} ^ _{ВА> А + В = в + А} (законы коммутативности);

XII. (АВ) С = А (ВС), (А + В) + С = А + (В + С) (законы ассоциативности);

XIII. А (В + С) = АВ +АС (закон дистрибутивности);

XIV. АА = А, А+ (В + В) = А XV. А-1 = А.

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

Выражение «языка» УСЕ наз. приведенным полиномом (п.п.), если оно есть 1 + 1 (т. е. нуль) или имеет вид 81, + в1₂ +...+8l_s где каждый член 81; есть либо 1, либо буквенная переменная, либо произведение последних, причем ни в одном члене нет ни­каких повторений букв, никакие два члена не одинаковы (в том же смысле, что и выше), a s не обязательно больше 1 (т. е. зна­ков «+» может не быть). Примеры п. п.: 1, 1 + 1, А, В, А+В+1, ABC, A+AB + B + BCD, ABD + BCD + CD + CE + i.

Всякое выражение А. л. можно привести к п. п. (теорема Жегал-кина). Для этого достаточно элиминировать в данном выраже­нии 0 и знаки операций, отличные от «-» и «+», «переводя» их на «язык» УСЕ, а затем раскрыть скобки (по закону дистри­бутивности, с использованием также, здесь и дальше, законов коммутативности и ассоциативности) и ликвидировать повторе­ния букв в членах (по закону АА=А) и повторения членов (по законам А+В+В=А, А+А=1 + 1). Тождество 81 = S3 верно, если, и только если, 81 и S3 приводятся к одинаковым п. п.

Кроме «языков» КДО и УСЕ, существуют и др. «языки», равносильные им в том смысле, что всякое выражение первых переводимо на последние и обратно (в этом смысле КДО и УСЕ тоже равносильны между собой). В основу такого «языка» доста­точно положить любую систему операций (и констант), обладающую тем свойством, что через операции (и константы) этой системы можно представить всякую функцию А. л. Такие системы наз. (функционально) полными (см. Полнота функциональная).

Примеры полных систем: а) конъюнкция и отрицание (при­меры представлений: А\В=АВ, А^В=АВ, А~В=АВ~-АВ,

А-\-В = АВ • АВ, 0=АА, 1=АА); б) дизъюнкция и отрицание (примеры представлений — тождества, двойственные предыду­щим); в) им пликация и отрицание [примеры представлений:

АВ=А-*Тз, А\>В=~А-+В, А + В=(А-*В)->В~4^ 0=А^-А, (= =А-*А); г) импликация и 0 [примеры представлений: АВ= = (А-»(В->-0))-»-0, А\В = (А-^В)->В, А=А-+0, 1=0-+0]; д) ум­ножение, эквиваленция и 0 [примеры представлений: АуВ— =АВ~А~В, А^В = АВ~А, А=А~0, 1=0-0]; е) штрих Шеф-фера А\В [определение: А\В—АВ; примеры представлений: АВ=

=(A|B)[(A|B),AVB = (A|A)|(B|B),A-»B = (A|B)|A,Z=A1A.A + B= = ((А|В)|А)|(А|В)|В), 1 = (А|А)|А)1', ж) медиана (А,В,С), отрица­ние и 1 [определение: (А,В, С)=АВ\АС\'ВС; примеры представ­лений: АВ = (А₁В,1), АуВ = (А, В, 1), А-»В = (А, В, 1), А~В = = (А,В,1),(А,В, 1),1) 0 = 1]; и) медиана,эквиваленция и сложение [примеры представлений: 0 = А + А, 1=А~А, А = А~(А + А) АВ = (А, В, А + А), A\JB = (A, В, А~А)].

Заметим, что для медианы имеет место ряд своеобразных тождеств; например (А, А, В) = А, (А, А, В) = В, (,А~Гв7~С) = = (А, В, С) (закон самодвойственности), (А, В, С)= (В, С, А) = = (А, С, В) (законы симметричности), (А, В, С)+В= = (A-\-D, B + D, C+D) (закон дистрибутивности сложения отно­сительно медианы), «А, В, С), D, Е) =((A, D, Е), (В, D,!-.), (С, D,Е)) (закон самодистрибутивности), ((А, В, С), D, А) = = (А, В. (С. D, А)) (закон частичной ассоциативности) и др.

Можно, очевидно, строить и такие «языки», в основе к-рых лежат системы операций, не являющиеся полными (напр., конъ­юнкция и дизъюнкция, сложение и отрицание, медиана и отри­цание, медиана и сложение, импликация и конъюнкция, отри­цание и константы). Если рассматривать не только те операции, к-рые встречались выше, но вообще всевозможные операции А. л., допускающие табличное задание (т. е., по существу, все­возможные функции А. л.), то таких «языков» можно построить бесконечно много. Среди них даже найдется бесконечно много попарно неравносильных «языков» (в смысле отсутствия взаим­ной «переводимости» с одного «языка» на другой). Однако для всякого «языка», построенного на основе тех или иных операций А. л., существует такая конечная система тождеств этого «язы­ка», что всякое тождество этого «языка» выводимо по методу тождеств, преобразований из тождеств этой системы (теорема Линдона). Такая система тождеств наз. (дедуктивно) полной си­стемой тождеств (п. с. т.) данного «языка» (см. Полнота дедуктив­ная). Напр., тождества I—VI составляют п. с. т. «языка» КДО (если считать, что константы И и Л тоже входят в этот «язык»); тождества XI—XV — п. с. т. «языка» УСЕ, тождества I—IV — п. с. т. «языка» конъюнкции и дизъюнкции, тождестваХ1— XIV— п.с. т. «языка» умножения и сложения, тождества I—Vil­li, с. т. «языка» конъюнкции, дизъюнкции, отрицания, имплика­ции и эквпваленции. Впрочем, последний «язык» мало отличает­ся от «языка» КДО из-за того, что импликация и эквивален­ция могут быть в нем элиминированы (по тождествам YL1).

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

АЛГЕБРА ЛОГИКИ 37

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

«Язык» КДО в результате такого шага абстракции превра­щается в «язык» т. н. булевой алгебры, «язык» УСЕ — в «язык» т. II. булева кольца (с единицей), «язык» конъюнкции и дизъ­юнкции — в «язык» т. н. дистрибутивной структуры. Булевой алгеброй паз. любая совокупность элементов (объектов), среди к-рых выделены два элемента, обозначенные соответственно: О и 1, и в применение к любым элементам к-рой определены опе­рации АВ, А\/В и А, удовлетворяющие тождествам I—VI (если Л в V заменить на 0, а И в VI— на 1; вместо знака «V» в «языке» булевой алгебры чаще употребляют знак «+»). Ана­логично определяются понятия булева кольца, дистрибутивной структуры, структуры (последнее связывается с тождествами 1-Ш).

Важным примером булевой алгебры является алгебра клас­сов, в к-рой роль элементов играют подмножества (классы) нек-рого фиксированного множества (т. н. универсума) U, роль 0 — пустое множество л, роль 1— само V, роль АВ, А\'В и А — теоретико-множеств. операции пересечения, объ­единения и дополнения, соответственно. Пересечением мно­жеств А и В наз. их общая часть, т. е. множество всех элементов, принадлежащих и А и В одновременно; объедине­нием множеств А и В наз. множество всех элементов, при­надлежащих А или В; дополнением множества А наз. мно­жество всех элементов универсума, не принадлежащих А, Другим примером булевой алгебры является алгебра преди­катов (определенных на нек-рой области предметов, тоже играю­щий роль универсума), в н-pofi роль 0 играет тождественно лот- ный предикат (т. е. ложный при всех значениях своих аргумен­тов), роль 1—тождественно истинный предикат, роль АВ, А\'В и А — так же, как и в случае обычной алгебры высказы­ваний, — конъюнкция, дизъюнкция и отрицание, соответствен­но. Связь между алгеброй классов, алгеброй предикатов и ал­геброй высказываний, этими тремя важнейшими интерпрета­циями абстрактной А. л. — «языка» булевой алгебры, состоит в следующем: первая переходит во вторую путем замены мно­жеств (классов! их т. н. характеристическими предикатами (т. е. множества А -- предикатом (хеА, гласящим: «х принад­лежит множеству А»), если при этом соответствующим образом преобразуются также операции и константы 0 и 1, а вторая переходит в третью при подстановке во все предикаты на место ик аргументов нек-рого фиксированного их значения. Вернее, при таком переходе от алгебры классов к алгебре предикатов получается алгебра не всех предикатов (определенных на уни­версуме), а лишь алгебра одноместных предикатов — частный случай алгебры предикатов. Другим важным частным случаем последней является алгебра двуместных предикатов, называ­емых чаще отношениями. С ней тесно связана т. н. алгебра отно­шений, отличающаяся от нее только тем, что в последней, кроме трех операций булевой алгебры, имеются еще две операции.

Всякую булеву алгебру можно «переделать» в булево коль­цо, определив операцию А+В согласно X (и отбросив операцию A\jB). Напр., в случае алгебры множеств роль А-\-В играет т. н. симметрическая разность множеств А и В (состоящая из всех тех элементов универсума, к-рые принадлежат одному и только одному из множеств А или В). Обратно, всякое булево кольцо (с единицей) можно «переделать» в булеву алгебру. Т. о., теория булевых алгебр и теория булевых колец (с едини­цей) — лишь разные варианты одной и той же, по существу, теории.

Терминологически понятия булевой алгебры и булева кольца связываются с именем Дж. Буля. Однако оформились эти поня­тая (не говоря уже о терминах) значительно позже.

В 17 в., когда проблема создания общих методов для решения возможно более широких классов задач была в центре внима­ния ученых и когда в качестве одного из таких методов (для решения математич. задач) возникла буквенная алгебра. Лейб­ниц первым предпринял попытку создания аналогичных общих методов (алгоритмов) и для решения задач логики. Однако решить эту задачу ему не удалось. Параллелизм между нек-рыми логич. и алгебраич. операциями подметили также ученики Лейбница, братья Якоб и Иоганн Бернулли (1685). К идеям Лейбница возвращались в дальнейшем Плуке (1763), Ламберт (1764—65), Кастнйон (1805) и др. Однако первую А. л. создали (в 1847) только Дж. Буль и А. де Морган. При этом А. л. у Бу­ля носила форму скорее не булевой алгебры, а булева кольца (т. е. была ближе к «языку» УСЕ, чем к «языку» КДО). А. л. в виде булевой алгебры разработали в дальнейшем Джевонс (1864), Пирс (начиная с 1867), Шредер (начиная с 1877), П. С. Порецкий (начиная с 1880). Пирсу и Шредеру принадлежит также разра­ботка начал алгебры отношений. С более общей т. зр., связыва­ющей А. л. с теорией групп, А. л. занимался также в своих первых работах Уайтхед (1898—1903). Строгое постро­ение А. л. как кольца вычетов по модулю 2 (арифметики четного и нечетного, в виде «языка» УСЕ) осуществил (в 1927— 1928) И. И. Жегалкин.

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

ния различные логич. задачи. В их числе можно указать, напр., следующую простую задачу, сохранившуюся в истории мате­матич. логики под назв. задачи Венна (1876): известно, что члены (а) правления одной страховой компании суть либо владель­цы облигаций (ft),либо владельцы акций (с), но не те и другие одновременно. Случайно оказалось, что все владельцы облигаций компании входят в состав ее правления. Что можно сказать на основании этих сведений о соотношении между владельцами акций и владельцами облигаций этой компании? — Естественно, сказать можно, что ни один, вообще, владелец акций не есть, владелец облигаций (*.с = 0). Однако, по свидетельству Венна, когда он предложил эту задачу в двух разных классах: обычных студентов-логиков и студентов, изучающих А. л., последние справились с ней значительно лучше.

В наст, время А. л. развивается гл. обр. под влиянием за­дач, встающих в области ее приложений. Из них самую важную роль играют приложения в теории электрич. схем, включая первоначально, начиная с работ В. И. Шестакова и К. Шенно­на (30—40-е гг. 20 в.), теорию релейно-коитактных схем, а позднее и схем с иными элементами: электронными лампами, сопротивлениями, полупроводниковыми, ферритовыми элемента­ми и пр. В простейших случаях здесь мы имеем дело еще с одной интерпретацией абстрактной А. л. Она связана, в част­ности, с тем, что у мн. элементов электрич. схем необходимо различать лишь два состояния, что соответствует паре значе­ний 0 и 1. Так, напр., у контакта имеются два состояния: 1) контакт замкнут, что соответствует 1, 2) контакт разомкнут, что соответствует 0; у 2-полюсной контактной схемы есть два состояния: 1) проводимость между полюсами имеется (в этом слу­чае она считается равной 1), 2) проводимость между ними отсут­ствует (и считается равной 0). АВ при этом соответствует после­довательному соединению схем, А\/В — параллельному соеди­нению. Уже здесь, в случае произвольной контактной схе­мы, возникает ряд осложнений по сравнению с положением соответствующих вещей в А. л. Для преодоления нек-рых из связанных с ними трудностей была построена (гл. обр. в рабо­тах А. Г. Лунца, 1950—52) алгебра матриц над булевой алгеб­рой, родственная алгебре отношений. Да и вопросы, касающие­ся понятий самой А. л., но встающие под влиянием запросов теории контактных схем (такие, как, напр., вопросы т. н. минимизации и вообще упрощения выражений А. л. путем тождеств, преобразований, а также вопросы различных связан­ных с этим оценок), приводят к проникновению в А. л. не-алгебраич. методов (таких, как табличные, топологические, дескриптивные) и вследствие этого к постепенному выделению из А. л. самостоят, области — теории функций А. л. (или иначе, теории булевых функций).

В случае исследования более сложных схем, чем контакт­ные, приходится часто отказываться от использования лишь обычной двузначной А. л. и рассматривать те или иные ее мно­гозначные обобщения, отличные от булевых алгебр и булевых колец (см. Многозначная логика и Трехзначнаялогика). В нек-рых работах, тоже в этой связи, намечается выход в область алге­бры предикатов (или даже предикатов от предикатов, хотя и при­нимающих лишь два значения), причем алгебры, более богатой операциями, чем обычная булева алгебра предикатов; напр., Б. А. Трахтенброт рассматривает в алгебраич. аспекте выра­жения с кванторами по переменным одноместным предикатам и с огранич. кванторами по предметным переменным.

Др. направлением совр. развития А. л. является т. н. алгебраич. логика, связанная с именем Керри и др. Она интересна, напр., тем, что выдвигает и частично решает задачу построения алгебр неклассич. логик, т. е. таких вариан­тов А. л., к-рые соответствуют тем или иным неклассич. исчис­лениям высказываний, подобно тому, как обычная классич. А. л., т. е. булева алгебра (с импликацией, к-рая в ней, одна­ко, элиминируется, т. к. представима через другие операции), соответствует классич. исчислению высказываний.

Соответствие при этом должно быть таким: любое произволь­ное тождество 'Д=а* должно быть верным в данной А. л., если, и только если, формула >д~5И доказуема (или обе формулы *l—-S8 и!В->*(доказуемы) в соответствующем ей исчислении высказы­ваний; а формула 'Л должна быть доказуема в данном исчислении высказываний, если, и только если, тождество VI =1 верно в соот­ветствующей ему А. л. Оказывается, что, напр., алгеброй мини­мальной логики является импликативная структура (или, вер­нее, теория таких структур), а алгеброй интуиционистской логики является импликативная структура с нулем. В обоих этих случаях свободная импликативная структура и, соответст­венно, свободная импликативная структура с нулем так же свя­заны с соответствующими исчислениями высказываний, как свободная булева алгебра с классич. исчислением высказы­ваний.

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

38 АЛГОРИТМ

Другая из этих тенденций связана больше с другой ветвью общей алгебры — ст. н. алгоритмич. алгеброй, к-рая появи­лась в сер. 20 в. в связи с успехами теории алгоритмов, позво­лившей уточнить ряд алгоритмич. проблем алгебры, и последо­вавшим решением (положительным или отрицательным) (Пост, Марков, Новиков, Адян и др.) нек-рых из них. Тенденция эта состоит в объединении алгоритмич. алгебры с самой теорией алгоритмов и попытках алгебраизации последней, т. е. постро­ения алгебраич. теории алгоритмов. Именно, с помощью рас­смотрения операций перехода от значений параметров алго­ритмич. проблемы к значению ответа на нее алгебраич. операции сведения произвольной алгоритмич. проблемы (весьма общего вида) к нек-рой проблеме тождества (см. Тож­дества проблемы), а также нахождения нек-рых критериев разрешимости последней (связанных с алгебраизацией понятия рекурсивной функции) удается дать общий алгебраич. кри­терий существования алгоритма для данной алгоритмич. проблемы.

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

Лит.: Яновская С. А., Основания математики и мате­
матическая логика, в кн.: Математика в СССР за тридцать
лет (1917 —1947), М.-Л.,1948; ее же, Математическая логи­
ка и основания математики, в кн.: Математика в СССР за со­
рок лет (1917-1957), т. 1, М., 1959; И о р ец к и й П. С,
О способах решения логических равенств и об обратном
способе математической логики, Казань, 1884; Ж е г а л-
кин И. И., Арифметизация символической логики, «Матем.
сб.», т. 35, вып. 3—4, М., 1928; Г а в р и л о в М. А., Теория
релейно-контактных схем, М.—Л., 1950; Яблонский СВ.,
О суперпозициях функций алгебры логики, «Матем. сб.»,
1'. 30 (72), вып. 2, М., 1952; Лунц А. Г., Алгебраические
методы анализа и синтеза контактных схем, «Изв. АН СССР»,
Сер. матем., 1952, т. 16, № 5; Т р а х т е н б р о т Б. А., Об
операторах, реализуемых в логических сетях, «Докл. АН
СССР», 1957, т. 112, № 6; Сборник статей по математической
логике и ее приложениям к некоторым вопросам кибернетики,
М., 1958; Войшвилло Е. К., Метод упрощения форм вы­
ражения функций истинности, «Научн. докл. высшей школы.
Философские науки», 1958, № 2; К у з и е ц о в А. В., Алго­
ритмы как операции в алгебраических системах, «Успехи матем.
наук», т. 13, вып. 3, 1958, с. 240—41; Н о в и к о в П. С,
Элементы математической логики, М., 1959; Гильберт Д.
и Аккерман В., Основы теоретической логики, пер.
с нем., М., 1947; Биркгоф Г., Теория структуры,
пер. с англ., М., 1952; Т а р с к и й А., Введение в логику
и методологию дедуктивных наук, пер. с англ., М., 1948;
К лини С. К., Введение в метаматематику, пер. с англ., М.,
1957; Джевонс В, Ст., Основы науки, пер. с англ.,
СПБ 1881; Schroder E., Vorlesungen iiber die Algeb­
ra der Logik, Bd 1—3, Lpz., 1890—1905; P о s t E., Intro-
duct,on to a general theory of elementary propositions, «Amer.
J. Math.», 1921, v. 43; В о о 1 e G., The mathematical analysis
of loigie, being an essay towards a calculus of deductive rea­
soning, Oxf.— N. Y., 1948; его ж е, An investigation of the
laws of thought, on which are founded the mathematical theo­
ries of logic and probabilities, N. Y., 1951; L у n d о n R. C.,
Identities in two-valued calculi, «Trans. Amer. Math. Soc»,
1951, v. 71; Curry H. В., Lecons de logique algebrigue,
P., 1952., А. Кузнецов. Москва.

АЛГОРИТМ (алгорифм)— одно из основных понятий логики и математики. Под А. понимают точное предписание, задающее вычислит, процесс, ведущий от начальных данных, к-рые могут варьи­ровать, к искомому результату.

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

Значение А. Само слово «А.» восходит к 9 в. (оно происходит от Algoritmi, являющегося, в свою очередь, лат. транслитерацией, произведенной, по-видимому, в 12 в., арабского имени хорезмийского

математика аль-Хорезми). В наши дни простейшие А. появляются уже в начальной школе — это А. арифметич. действий (в ср.-век. Европе А. как раз и называлась совр. школьная арифметика, т. е. десятичная позиционная система счисления и искус­ство счета в ней, поскольку трактат аль-Хорезми был одним из первых, если не самым первым, благодаря к-рому Европа познакомилась с позиционной систе­мой). Подчеркнем, что в начальной школе обучают именно А. счета. Говоря об умении человека скла­дывать числа, имеют в виду не то, что он для любых двух чисел рано или поздно сумеет найти их сумму, а то, что он владеет нек-рым единообразным приемом сложения, применимым к любым двум конкретным записям чисел, т. е., иными словами, А. сложения (примером такого А. является известный А. сложения чисел «столбиком»).

А. встречаются в науке на каждом шагу, умение решать задачу «в общем виде» всегда означает, по су­ществу, владение нек-рым А. Понятие задачи «в общем виде» уточняется при помощи понятия массовой проблемы. Под термином «проблема» можно понимать задачу нахождения объекта, обладающего теми или иными свойствами; этот объект наз. решением проб­лемы (в частности, для проблемы нахождения ответа на какой-то вопрос решением является ответ «да» или «нет» на поставл. вопрос). Проблема неразреши­ма, если она не имеет решения, т. е. не существует объекта, обладающего нужными свойствами. Ясно по­этому,что неразрешимость проблемы не дает основапий для агностич. выводов; напротив, установление нераз­решимости конкретной проблемы есть важный позна-ват. акт. Массовая проблема задается серией отдель­ных, «единичных» проблем и состоит в требовании найти общий метод (т.е. А.) их решения. Неразре­шимость массовой проблемы означает невозможность найти соответств. А. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благо­даря тому, что одновременно дает общий метод для ре­шения целого класса проблем; в то же время постанов­ка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему — проблему нахождения А. для решения всех проблем этого класса; здесь проявляется связь таких катего­рий диалектики, как единичное, особенное и все­общее. Ролью массовых проблем и определяется зна­чение А.

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

Содержат, явления, к-рые легли в основу образования понятия «А.», издавна занимали важное место в науке. Мно­гие задачи, возникавшие в математике и логике, заключи­лись в поисках тех или иных конструктивных методов. Поиски таких методов, особенно усилившиеся в связи с созданием удобной математич. и логич. символики, а также осмысление принципиального отсутствия этих методов в ряде случаев — все это было мощным фактором развития науч. знания. Осо­знание невозможности решить любую задачу прямым вычисле­нием привело к созданию в 19 в. теоретико-множеств. кон­цепции. Лишь после периода бурного развития этой кон­цепции (в рамках к-рой вопрос о конструктивных методах в совр. их понимании вообще не возникает) оказалось воз­можным в последние десятилетия вновь вернуться к вопросам конструктивности, но уже на новом уровне, обогащенном вы­кристаллизовавшимся понятием «А.» (еще одна иллюстрация к положению Ленина о спиралеобразном характере развития познания). И хотя понятие «А.» не является столь далеко идущей абстракцией, как, скажем, понятие «множество», нельзя считать

АЛГОРИТМ 39

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

Примеры А. Подобно понятиям «множество», «соответствие», «натуральное число», «отношение» и т. п., понятие «А.» является первичным логико-математич. понятием (одной из категорий логики и математики). Оно не допускает формального опреде­ления через более простые понятия, а (как и др. математич. категории) абстрагируется непосредственно из опыта. Понятие «А.» может быть усвоено лишь на примерах.

П р и м е р 1. Возможными начальными данными являются ко­нечные непустые комбинации, составленные из палочек (I), т. е. объекты I, II, 111 и т. д. А. состоит из след. правил (выпол­нять к-рые надлежит начиная с правила 1°):

1°. Подчеркни снизу крайнюю слева палочку и перейди к вы­полнению правила 2°.

2°. Надчеркни сверху крайнюю справа палочку и перейди к выполнению правила 3°.

3°. Рассмотри подчеркнутую палочку и, если она не надчерк­нута, перейди к выполнению правила 4°.

4°. Рассмотри палочку непосредственно следующую за под­черкнутой; если она не надчеркнута, перейди к выполнению Правили 5", если же она надчеркнута, перейди к выполнению правила 7°.

5³. Перенеси нижнюю черточку с подчеркнутой палочки на непосредственно за ней следующую и перейди к выполнению правила 6°.

6°. Перенеси верхнюю черточку с надчеркнутой палочки на Непосредственно ей предшествующую и перейди к выполнению правила 7°.

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: