КОНСТРУКТИВНАЯ ЛОГИКА- совокупность логических принципов, признаваемых представителями копструк- тмшшш (в математике) и включающих абстракцию потенциальной, но не актуальной бесконечности, что определенным образом изменяет понимание логических связок и кванторов (по сравнению с их пониманием в классической логике), сочетая это понимание с ковсмруктшвнымж яротессамш (процессами, описываемыми алгоритмам). Так, дизъюнкция высказываний «А или В» считается обоснованной, если потенциально осуществим конструктивный процесс, позволяющий выбрать верный член этой дизъюнкции; аналогично оценивается обоснованность многочленных дизъюнкций. Близко к пониманию дизъюнкции истолкование квантора существования: утверждение «существует такой х, для которого справедливо условие А* считается обоснованным, если потенциально осуществим конструктивный процесс подбора конструктивного объекта х, подтверждающего условие А. Обоснование конъюнкции «А и A» состоит в обосновании обоих (т. е. всех) конъюнктивных членов, а утверждение «Для всякого х справедливо условие А* считается обоснованным, если мы в состоянии для всякого объекта рассматриваемого вида доказать, что он удовлетворяет предъявленному требованию. Обоснование импликации «если А, то В> состоит в предъявлении конструктивного процесса, позволяющего по обоснованию утверждения А построить обоснование утверждения В. Отрицание утверждения А обосновывается предъявлением конструкции, приводящей к противоречию всякую попытку обоснования А. Конструктивное истолкование логических связок и кванторов допускает и различные другие уточнения. В частности, созданы различные аксиоматические системы конструктивной логики. Поскольку конструктивная позиция идейно близка интуиционистской, аксиоматические системы, первоначально предназначавшиеся для реконструкции интуиционистски приемлемых рассуждений (см. Имтушщшонястская логика), называются (или подразумеваются) конструктивными. (Напр., активно изучающиеся суперинтуиционистские логики в 60-е гг. и несколько позже назывались суперконструктивными.) Отличие этих логик от классической проявляется в том, что хотя конструктивно приемлемыми являются, напр., законы р —>—^р, -•"•"Т), —»-¦ р (р —> q) —> (^q—>--p), в этих системах отсутствуют практически все остальные варианты форм рассуждений «от противного» — закон снятия двойного отрицания —^р —ф, закон контрапозиции (^р—> -q) —> (q —> р), закон Клавия (^р—>р) —> р, закон Пирса ((р —> q) —> р)—>р и др. Кроме того, в конструктивной логике связки независимы, т. е. не выражаются друг через друга, нет классической взаимовыразимости кванторов всеобщности и существования. В результате оказываются, в частности, необоснованными рассуждения, приводящие к доказательству т. н. чистых теорем существования, типичным примером которых является доказательство Г. Кантора существования трансцендентных (т. е. действительных, но не алгебраических) чисел: приводится к противоречию предположение о возможности расположить все действительные числа в последовательность, в то время как алгебраические числа в последовательность можно расположить. Чистые теоремы существования (имеется в виду формулировка теоремы, проистекающая из доказательства) имеют вид -"Зх4(х), не переводимый в ЗхА(х), посколысу их доказательства не дают конкретного х, подтверждающего справедливость А, а лишь приводят к противоречию утверждение об отсутствии такого х. Однако ввиду специфики конструктивных объектов и процессов многими представителями конструктивизма (в отличие, скажем, от приверженцев интуиционизма) принимается принцип конструктивного подбора (или принцип Маркова): если имеется алгоритм, позволяющий по произвольному конструктивному объекту х осуществлять конструктивный процесс установления наличия у х свойства Ау то в случае обоснования -*-BxA(x) считается обоснованным и ЭхА(х). Взаимосвязи классических и конструктивных логических систем проявляются на пропозициональном уровне в виде т. н. теоремы Гливенко: а) отрицательные утверждения в этих системах одинаковы; б) конструктивно приемлемым является двойное отрицание любого закона классической логики высказываний и наоборот. Для справедливости теоремы Гливенко для предикатных вариантов конструктивных и классических систем необходимо добавление в качестве схемы аксиом в конструктивную систему закона -•-•Vx/4(x) V -ч Vx4(x) и/или закона Vx^-v4(x)—> -»-»Vx/I(x) (обратная импликация -»-«Vx/Kx)—Л/х-"-у4(х) принимается в конструктивной логике). Отличительной чертой систем конструктивной логики и построенных на их основе теорий являются т. н. 1) свойство дизъюнкции (или дизъюнктивное свойство) — если выводима дизъюнкция, то выводим и некоторый ее дизъюнктивный член, — и 2) экзистенциальное свойство—если выведенаформулаНх <4(х), то можно вывести и формулу ДО при некотором конкретном эффективно разыскиваемом t, т. е. из доказательства существования конструктивного объекта с требуемыми свойствами можно извлечь кон- струкциюего построения. Кроме аксиоматических систем кон-

292

КОНСТРУКТИВНОЕ НАПРАВЛЕНИЕ структивной логики, имеются различные семантические построения, отражающие конструктивные воззрения на смысл логических связок, формул и т. д. Наиболее известными являются рекурсивная реализуемость по С. К. Клини и ее варианты, а также разработанная Н. А. Шаниным мажорантная семантика арифметических формул и созданная А. А. Марковым ступенчатая система построения логических языков с одновременным определением их семантики «снизу вверх». Лит.: Марков А. А. О логике конструктивной математики. М., 1972; Навыков П. С. Конструктивная математическая логика с точки зрения классической. М, 1977; Он же. Элементы математической логики. М, 1984; Справочная книга по математической логике, т. IV: Теория доказательств и конструктивная математика. М., 1983; Марков А. А., Нагорный Н. М. Теория алгорифмов. 2-е изд. М., 1996. А. В. Чагров

КОНСТРУКТИВНОЕ НАПРАВЛЕНИЕ(в математике и логике) — одно из направлений в основаниях математики, в рамках которого исследования ограничиваются конструктивными процессами и конструктивными объектами. Конструктивное направление имеет точки соприкосновения с интуиционистской математикой (см. Интуиционизм). Конструктивисты сходятся с интуиционистами в трактовке предложений о существовании и в понимании дизъюнкции и в силу этого признают правильной данную Браузром критику закона исключенного третьего. Вместе с тем конструктивисты считают неприемлемыми методологические основы интуиционизма. В основу своей теории действительных чисел интуиционисты кладут идею свободно становящейся последовательности, которую они считают интуитивно ясной, но которая для многих других математиков совсем не ясна. Эта идея, во всяком случае, несовместима с основным требованием конструктивного направления, состоящим в том, что лишь конструктивные объекты допускаются в качестве объектов исследования. Один из простейших (но достаточный для развития конструктивной математики) типов конструктивных объектов образуют слова (ряд букв) в некотором фиксированном алфавите. Естественным образом здесь применяется абстракция отождествления. При рассмотрении слов в данном алфавите возникает потребность в абстракции и другого типа — в абстракции потенциальной осуществимости. Она состоит в отвлечении от практических границ наших возможностей в пространстве, времени и материале при построении слов. Напр., мы отвлекаемся от практической невозможности написать на данной доске данным мелом сколь угодно длинные слова и начинаем рассуждать так, как если бы это было возможно. Мы утверждаем, в частности, что к любому слову в данном алфавите можно приписать справа любое другое слово в этом алфавите. Рассматривая натуральные числа как слова в однобуквенном алфавите, мы утверждаем, что любые два натуральных числа можно сложить. Это, однако, вовсе не означает, что мы начинаем рассматривать «натуральный ряд» как некоторый бесконечный объект. Такое рассмотрение было бы связано с абстракцией актуальной бесконечности, выходящей за рамки конструктивного направления и характерной для классической математики и логики. Здесь мы имеем водораздел, отделяющий конструктивное направление от классического. Характерное различие между этими двумя направлениями связано с предложениями о существовании. Конструктивисты и классики по-разному понимают самый термин «существование» в связи с объектами математики и логики. В классической математике и логике доказываются многочисленные чистые теоремы существования, состоящие в утверждениях о существовании объектов с такими-то свойствами при полном игнорировании способов построения таких объектов. Конструктивисты отвергают такого рода предложения. Конструктивное понимание параметрических предложений о существовании (содержащих параметры, могущие принимать разные значения) предполагает их трактовку как предложений о возможности существования алгоритмов, перерабатывающих любое допустимое значение параметров в объект, существование которого утверждается. Напр., конструктивный смысл теоремы Евклида: «для всякого натурального числа существует простое число у, большее х» (где х играет роль параметра) усматривается в том, что имеется алгоритм, который даст возможность, исходя из произвольного натурального числа jc, получить простое число у, большее — алгоритм, перерабатывающий любое натуральное число х в простое число у, большее х. Конструктивному пониманию существования соответствует конструктивное понимание дизъюнкций — предложений вида «Рили 0>. Такое предложение тогда считается установленным, когда хотя бы одно из предложений установлено как верное. Это понимание дизъюнкции не дает основания считать верным исключенного третьего закон. Т. о., конструктивное направление требует своей конструктивной логики, в некоторых важных аспектах отличной от классической. Оформление и развитие конструктивного направления имело место на основе осуществленного в 30-х гг. 20 в. уточнения понятия алгоритма. Слова в рассматриваемом алфавите, записи (программы) алгоритмов — все это потенциально осуществимые конструктивные объекты. Сам процесс применения алгоритма к данному слову рассматривается как потенциально осуществимый процесс. Для того, чтобы удостовериться в применимости алгоритма А к слову Р, не обязательно, чтобы процесс применения А к Р был выполнен перед нашими глазами от начала до конца. Здесь возможно применить рассуждение от противного: алгоритм А применим к слову Р, если предположение о неограниченной продолжаемости процесса применения А к Р опровергается приведением к нелепости. Данный способ рассуждения назвали принципом Маркова. Использование точного понятия алгоритма дало возможность развивать конструктивную математику и конструктивную математическую логику как науки. Н. А. Шанин построил алгоритм конструктивной расшифровки, выделяющий из любой математической формулы явное построение конструктивного объекта и условие, которое необходимо доказать для корректности данного построения. Он заметил, что для обоснования уже сделанного построения можно, в предположении принципа Маркова, использовать классическую логику. Т о., при конструктивном понимании формула содержит две задачи: задачу на построение и задачу на доказательство. Если первая из них практически с неизбежностью требует перехода к неклассической логике, то вторая зачастую может быть решена традиционными средствами. Это разделение двух типов задач явилось важным методологическим следствием, достичь которого помог принцип Маркова, поскольку без него такого простого алгоритма расшифровки и простой характе- ризации задач на доказательство достичь не удается. Вместе с тем Б. А. Кушнер выяснил, что из чисто математических результатов от принципа Маркова зависит лишь теорема Г. С. Цейтина о непрерывности конструктивных функ-