ЛОГИКА МНОГОЗНАЧНАЯ

— область математики, изучающая свойства функций, принимающих в качестве значений, как и их аргументы, элементы из заданного множества, семейств и алгебр таких функций, в которых в качестве операций выступают операции суперпозиции и некоторые их аналоги. Иногда предмет Л. м. расширяют, включая в нее различные логич. исчисления. Ниже термин Л. м. будет пониматься без такого включения. Л. м. занимает промежуточное положение между логикой математической, алгеброй и теор. кибернетикой. Первоначально Л. м. использовали при изучении логич. исчислений (исчисления высказываний и предикатов), в которых высказываниям приписывались любое конечное (большее, чем 1) и иногда бесконечное мн-ва значений истинности. Это позволяло, помимо общих, рассматривать и спец: задачи матем. логики, связанные с оценкой меры истинности модальных высказываний, а также высказываний, в которых не указано время и место события, и т. п. Исторически первыми системами Л. м. явились двузначное исчисление Дж. Буля (середина 19 в.), позднее оформленное усилиями англ. логика Б. Рассела (1872—1971), нем. логика Д. Гильберта (1862—1943), амер. математика Э. Поста (1897—1954) и др. в двузначную логику (см. Алгебра логики), трехзначная логика Лукасевича (1920) и -значная логика Поста (1921). Одновременно Э. Пост предложил рассматривать Л. м. как алгебры и установил целый ряд существенных свойств этих алгебр. С тех пор Л. м. стала важным объектом алгебры. Позже (30-40-е гг. 20 ст.) в процессе развития кибернетики выяснилось большое прикладное значение Л. м. Было установлено, что язык Л. м. удобен при описании функционирования сложных электр. схем, и это дало новый толчок к ее развитию. Пограничное

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

В основе построения Л. м. лежит следующая концепция, обобщающая построение алгебры логики. Исходят из некоторых высказываний, истинность значений которых градуирована и образует некоторое мн-во Е. Отвлекаясь от смысла этих высказываний, интересуются прежде всего их значениями с точки зрения истинности, что позволяет все исходные высказывания разбить на группы, соответствующие одному и тому же значению истинности. Эти значения, а также переменные из алфавита , принимающие в качестве значений указанные величины, объявляются элементарными высказываниями (константами и переменными соответственно). По аналогии с логикой суждений, вводятся некоторые отношения над элементарными высказываниями, точнее, функции, которые, как и их аргументы, принимают в качестве значений константы и которые соответствуют различным логическим связкам над высказываниями. Эти функции, образующие мн-во М, наз. элементарными. Мн-во М является подмножеством мн-ва Р Е всех т. н. ф-ций значной логики, т. е. функций, зависящих от переменных из алфавита X и принимающих значения из Е (здесь через обозначена мощность Е). Затем вводят понятие формулы, которое соответствует содержательному представлению сложного высказывания, построенного из исходных высказываний. Ф-лы строят из обозначений (элементарных ф-л) вида элементарных ф-ций из М по правилам подстановки ф-ций друг в друга вместо некоторых переменных и путем подстановки переменных из X вместо переменных рассматриваемых ф-ций (операции суперпозиции). В результате получается мн-во (М) всех ф-л над М. Содержательно сложные высказывания при фиксации в них значений истинности исходных высказываний также принимают значения истинности из Е. Эти значения определяются структурой сложного высказывания и логическими связками, входящими в него. Тем самым каждое сложное высказывание определяет некоторую ф-цию логики (производную связку). Формально каждой ф-ле приписывается ф-ция из РЕ (суперпозиция над М), которая является ф-цией, естественно определяемой этой ф-лой. Говорят также, что ф-ла реализует приписанную ей ф-цию. Все суперпозиции над М образуют мн-во которое наз. замыканием мн-ва М. С содержательной точки зрения построение Л. м. завершается указанием мн-в логических связок, сложных высказываний и производных связок. По аналогии с этим и формальное задание Л. м. (точнее: -значной логики) будет эквивалентно заданию мн-в (говорят также, что Л. м. порождается мн-вом М). Эту модель, играющую важную роль в матем. логике и теор. кибернетике, наз. формульной. Своеобразие подхода теор. кибернетики к Л. м. состоит в рассмотрении Л. м. в качестве управляющей системы. Элементарные ф-лы при этом играют роль элементов, производящих определенные операции, а ф-лы интерпретируются как схемы, построенные из элементов и также осуществляющие переработку входной информации в выходную. Такого рода управляющие системы, известные в кибернетике как схемы из функциональных элементов, играют фундаментальную роль в теоретических и практических вопросах кибернетики.

Существует целый ряд общих проблем Л. м. которые интересны с позиций матем. логики, алгебры и с позиций кибернетики. К их числу относятся, например, вопрос о включении при заданных РЕ (задача о выразимости) и об указании мн-ва всех ф-л из реализующих ф-ции из при об описании). Частным случаем задачи об описании является важный вопрос матем. логики об указании всех ф-л, реализующих заданную константу, что, например, эквивалентно для исчисления высказываний построению всех тождественно истинных или соответственно тождественно ложных высказываний. Пограничным вопросом между матем. логикой и алгеброй, примыкающим к задаче об описании, является задача о тождественных преобразованиях. В ней при заданном мн-ве М требуется выделить в некотором смысле простейшее подмножество пар равных (т. е. реализующих одну и ту же ф-цию) ф-л из позволяющее путем подстановки выделенных равных ф-л друг вместо друга получить из любой ф-лы все ф-лы, равные ей. Аналогичное место занимает один из важнейших вопросов Л. м.- т. н. проблема полноты, состоящая в указании всех подмножеств заданного замкнутого, т. е. совпадающего со своим замыканием, мн-ва таких, что . К ней примыкает задача о базисах, состоящая в указании всех полных в подмножеств никакое собственное подмножество которых уже не является полным. Глобальной задачей для Л. м. является задача о строении структуры замкнутых мн-в в данной Л. м. и выяснении ее различных свойств. Характерный для теории управляющих систем вопрос о сложности этих систем, естественно, можно поставить и по отношению к ф-лам и ф-циям из Л. м. При таком подходе типичной является следующая задача о сложности реализации. На мн-ве всех элементарных ф-л некоторым способом вводят числовую меру (сложность формул), которая затем распространяется на мн-во всех ф-л, напр., путем суммирования мер всех тех элементарных ф-л, которые участвуют в построении заданой ф-лы. Требуется для заданой ф-ции указать ту ф-лу (простейшая ф-ла), которая реализует эту ф-цию и имеет наименьшую сложность, а также выяснить, как эта сложность зависит от некоторых свойств рассматриваемой ф-ции. Исследуют различные

обобщения этой задачи. Широкий круг вопросов, связанный с реализацией ф-ций ф-лами с наперед заданными свойствами, в известном смысле примыкает к уже рассмотренному вопросу о сложности реализации. Здесь в первую очередь следует назвать задачу о реализации ф-ций алгебры логики дизъюнктивными нормальными формами и связанную с этим т. н. задачу минимизации, а также обобщение этой задачи на ф-ции -значной логики при Сюда же относятся задачи о реализации ф-ций ф-лами в некотором смысле ограниченной глубины, когда цепочка подставляемых друг в друга выделенных элементарных ф-л не может превосходить некоторой константы, что при соответствующей интерпретации может быть связано с надежностью или скоростью вычисления ф-ции ф-лами; задачи о декомпозиции, т. е. о реализации ф-ций от переменных при помощи ф-л, построенных из элементарных ф-л, реализующих ф-ции, зависящие менее чем от переменных, и ряд других.

При рассмотрении ряда задач и в том числе о выразимости, о полноте, об описании структуры замкнутых классов и других, где на первый план выдвигаются соответствия типа мн-во М и его замыкание и затушевывается иная роль ф-л над М, кроме их способности порождать новые ф-ции, часто переходят к другой модели в которой мн-во (М) заменяется мн-вом термов, представляющих собой те же ф-лы, но построенные не из имен индивидуальных ф-ций, а из обобщенных (переменных) имен ф-ций с фиксированной для данного переменного имени арностью. Эти термы фактически играют роль частичных операторов над мн-вом М. Следующий шаг на этом пути, в некотором смысле упрощающий только что введенную термальную модель, приводит к рассмотрению Л. м. как алгебры. Наиболее употребительной является алгебра, введенная сов. математиком А. И. Мальцевым (1909—67), которая строится следующим образом. Сначала уточняют строение мн-ва РЕ предположением о том, что каждая ф-ция с учетом фиктивных переменных зависит от переменных где зависит от Затем определяются пять операций Первые четыре из них являются унарными и фактически действуют на мн-ве индексов переменных ф-ций следующим образом;

При этом для одноместной ф-ции полагается Операция бинарная, действует одновременно на индексы переменных рассматриваемой пары ф-ций и на саму пару, ставя ей в соответствие ф-цию

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

К числу наиболее важных примеров Л. м. можно отнести алгебры при при , среди которых наиболее детально исследован случай Важнейшим результатом здесь является полное описание Э. Постом структуры всех подалгебр. Мн-во всех подалгебр оказалось счетным, каждая подалгебра строится эффективно и эффективно же указывается включение их друг в друга. Э. Пост показал также, что во всякой подалгебре имеется конечный базис и число ф-ций в нем не превосходит четырех. Из этих результатов легко можно извлечь также решения упомянутых задач о выразимости, о полноте и о базисах. На основе результатов Э. Поста амер. логик Р. Линдон решил задачу о тождественных преобразованиях. В задаче о сложности реализации относительно полных конечных систем советский математик О. Б. Лупавов (р. 1932) для почти всех ф-ций указал поведение меры сложности «простейших» ф-л, реализующих эти ф-ции, и построил соответствующий алгоритм синтеза Значительно продвинуто решение задач о построении оптимальных по сложности ф-л, реализующих ф-ции надежно или достаточно хорошо по быстродействию. Вместе с тем следует отметить, что в указанном направлении по отношению к семействам ф-ций, составляющим малую долю от всех ф-ций, а также по отношению к индивидуальным функциям общая теория пока еще далека от своего завершения. Продвинуто вперед решение и других из упомянутых выше задач. Следует подчеркнуть особенность случая с которой связано пристальное внимание

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

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

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

Заметное место в проблематике Л. м. занимают вопросы исследования спец. замкнутых классов ф-ций Л. м., которые представляют интерес прежде всего в связи с вопросами интерпретации различных логич. исчислений. Здесь следует назвать уже упомянутые трехзначную логику Лукасевича, которую порождают ф-ции где принимают в качестве значений - значную логику Поста, которую порождают ф-ции где принимают значения , а также Л. м., соответствующие матрицам Ст. Яськовского, Л. м. М. Мак-Нотона и др. Эти исследования представляют интерес как с точки зрения накопления фактов для построения общей теории Л. так и с целью установления посредством их некоторых новых свойств интерпретируемых логических исчислений.

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

Лит.: Яблонский С. В. Функциональные построения в -значной логике. «Труды Математического института им. В. А. Стеклова АН СССР», 1958, т. 51; Журавлев Ю. И. Теоретико-множественные методы в алгебре логики. «Проблемы кибернетики», 1962, в. 8; Лупанов О. Б. Об одном подходе к синтезу управляющих систем — принципе локального кодирования. «Проблемы кибернетики», 1965, в. 14; Гаврилов Г. П. О функциональной полноте в счетнозначной логике. «Проблемы кибернетики», 1965, в. 15; Яблонский С. В., Гаврилов Г. П., Кудрявцев В. Б. Функции алгебры логики и классы Поста. М., 1966 [библиогр. с. 113—115]; Мальцев А. И. Итеративные алгебры и многообразия Поста. «Алгебра и логика», 1966. т. 5, в. 2; Rоsеnbегg I. (jber die funktionale vollstandigkeit in den mehrwertigen Logiken. «Rozpravy Ceskoslovenske Akademie ved», 1970, r. 80, N. A. В. Б. Кудрявцев.