Многозначная логика

Многозначная логика – раздел математической логики, изучающий математические модели логики высказываний. Эти модели отражают две основные черты последней – множественность значений истинности высказываний и возможность построения новых более сложных высказываний из заданных при помощи логических операций, которые позволяют также по значениям истинности исходных высказываний устанавливать значение истинности сложного высказывания. Примерами многозначных высказываний являются суждения с модальным исходом (<<да>>, <<нет>>, <<может быть>>) и суждения вероятностного характера, а примерами логических операций – логические связки типа <<и>>, <<или>>, <<если..., то>>. В общем случае модели М. л. представляют собой обобщения алгебры логики. Важно отметить, что в алгебре логики высказывания принимают только два значения истинности (<<да>>, <<нет>>), в связи с чем она в общем случае не может отразить всего многообразия логических построений, встречающихся на практике. При достаточно широком толковании М. л. в нее иногда включают также логические исчисления.

Исторически первыми моделями М. л. явились двузначная логика Дж. Буля (G. Boole, сер. 19 в.), называемая также алгеброй логики, трехзначная логика Я. Лукасевича (J. Lucasiewicz, 1920) и m-значная логика Э. Поста (Е. Post, 1921). Изучение этих моделей составило важный этап в создании теории М. л.

↑Основные модели многозначной логики

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

Построение моделей М. л. осуществляется по аналогии с построением двузначной логики. Так, индивидуальные высказывания логики, разбитые на классы с одним и тем же значением истинности, приводят к понятию множества E – констант модели, которые фактически отождествляют все индивидуальные высказывания, заменяя их соответствующими значениями истинности; переменные высказывания приводят к переменным величинам x₁, x₂ ..., которые в качестве значений принимают элементы из множества E; логические связки приводят к множеству M элементарных функций (операций), которые, как и их аргументы, принимают значения из E. Сложные высказывания, построенные из индивидуальных и переменных высказываний, а также логических связок, приводят к множеству формул над M. Значение истинности из E сложного высказывания является функцией от соответствующих значений истинности высказываний, входящих в данное сложное высказывание. В модели эта функция приписывается формуле, соответствующей данному сложному высказыванию; говорят также, что формула реализует эту функцию. Функции, отображающие кортежи элементов из E в E, называемые функциями m-значной логики, где m обозначает мощность множества E. Множество всех функций m-значной логики обозначают через . Множество формул приводит к множеству [M] функций, реализуемых формулами из и называемыми суперпозициями (или композициями) над M. Множество [M] называется замыканием множества M. Задание конкретной модели М. л.считается эквивалентным указанию множеств E, M, и [M], при этом говорят, что модель порождается множеством M; если M конечно, говорят, что модель является конечно порожденной. Эта модель называется формульной моделью, а также m-значной логикой.

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

Вместе с тем существует ряд задач логики и кибернетики, который связан с изучением соответствий между множествами M и [M] и при котором роль множества несколько затушевывается, сводясь к способу определения второго множества по первому. В этом случае приходят к другой модели М. л., представляющей собой алгебру, элементами которой являются функции, принимающие в качестве значений, как и их аргументы, элементы из E. В качестве операций в этих алгебрах обычно используется специальный набор операций, эквивалентный в смысле соответствий M и [M] множеству формул, построенных из функций множества M, т. е. получению сложных функций из заданных путем подстановки одних функций вместо аргументов других. Эти алгебры называются алгебрами m-значных логик. Конкретно это может быть достигнуто, например, введением следующих унарных операций: ζ, τ, Δ и бинарной операции *. В предположении, что каждая функция ƒ из с учетом фиктивных переменных зависит от переменных x₁, x₂ ..., где определяется функцией ƒ, эти операции могут быть заданы так:

если n>1 и ζ ƒ= τ ƒ= Δ ƒ=n, если n=1

и для и

Возникающие алгебры иногда называются алгебрами Поста.

↑Проблематика многозначной логики

К числу задач, характерных для формульной модели М. л., относится задача <<об описании>>, т. е. вопрос об указании для заданного множества всех формул из , реализующих функции из M₂. Частным случаем такой задачи является важный вопрос математической логики об указании всех формул, реализующих заданную константу, что, например, для исчисления высказываний эквивалентно построению всех тождественно истинных высказываний.

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

Аналогичное место занимает т. н. проблема полноты, состоящая в указании всех таких подмножеств M₁ заданного замкнутого, т. е. совпадающего со своим замыканием, множества M, для которых выполнено равенство [M₁] = M, т. е. имеет место свойство полноты (или свойство функциональной полноты) M₁ в M. К этой задаче примыкает задача о базисах, состоящая в указании всех полных в подмножеств , никакое собственное подмножество которых уже не полно в M (базисы называют также полными независимыми системами функций). Выделяют два подхода к решению задачи о полноте – алгоритмический и алгебраический. В первом случае ставится вопрос о существовании алгоритма, устанавливающего полноту или неполноту систем функций, описанных на некотором языке; во втором – переходят к изучению свойств решетки подалгебр данной алгебры m-значной логики и решают задачу о полноте, используя эти свойства. Важным понятием при алгебраическом подходе является понятие критериальной системы подалгебр. Система N подалгебр алгебры называется критериальной, если любое множество является полным тогда и только тогда, когда оно не является подмножеством ни одной подалгебры из N. Таково, например, множество всех собственных подалгебр алгебры M. В общем случае последняя критериальная система является избыточной. Всякая критериальная система содержит все максимальные подалгебры алгебры M (или предполные классы), и это позволяет перейти к рассмотрению более экономных критериальных систем, которые не содержат подалгебр максимальных подалгебр. Таким образом, в задачах о полноте можно ограничиться использованием критериальных систем вида , где ∑₁ – множество всех максимальных подалгебр, а множество ∑₂ состоит из некоторых таких подалгебр, которые не являются подалгебрами никакой максимальной подалгебры. В случае пустоты ∑₂ задача о полноте сводится к описанию максимальных подалгебр алгебры N.

Глобальной задачей для М. л. является описание решетки замкнутых классов данной модели М. л.

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

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

Решения всех перечисленных выше задач существенно зависят от мощности множества E и множества M, порождающего заданную модель М. л.

↑Важнейшие примеры многозначных логик

К числу наиболее важных примеров М. л. относятся конечнозначные логики (т. е. m-значные логики, для которых m конечно). Для них обычно полагают, что, а m-значную логику обозначают . Наиболее глубоко исследован случай m=2, при этом функции двузначной логики называют также булевыми функциями. Важнейшим результатом здесь является полное описание Э. Постом (E. Post[1]) решетки замкнутых классов. Множество их оказалось счетным, а каждый класс и решетки их по включению строятся эффективно. Эти классы называются классами Поста. Всякий замкнутый класс имеет конечный базис, и его мощность не превосходит 4. Из этих результатов получаются решения задач о выразимости, полноте и базисах, а также задачи о тождественных преобразованиях. Относительно полных конечных систем для <<почти всех>> функций указано поведение меры сложности простейших формул, реализующих эти функции, и построен соответствующий алгоритм синтеза формул[2]. Изучены задачи о построении оптимальных по сложности формул, реализующих функции надежно и достаточно хорошо по быстродействию, а также вопросы сложности реализации для большого числа специальных классов функций и отдельных функций.

Одним из глубоко исследованных вопросов для двузначной логики является также задача минимизации. В ней изучается специальный язык задания функций двузначной логики – язык дизъюнктивных нормальных форм (д. н. ф.). Вводится понятие сложности д. н. ф. – число букв в ней – и изучаются задачи поиска, строения и метрических свойств <<простейших>> в смысле этой меры д. н. ф., реализующих заданную функцию[3]. Задача о декомпозиции для булевых функций состоит в выяснении условий, при которых заданная функция от n переменных может быть реализована формулой, построенной из функций от меньшего числа переменных, причем все функции, подставляемые друг в друга в процессе построения формулы, не зависят от общих переменных. Такие формулы называются бесповторными. Показано, что не существует конечной системы функций такой, что каждая функция может быть реализована бесповторной формулой над этой системой, и даже что <<почти все>> функции не допускают реализации бесповторными формулами. В целом двузначные логики, в силу не которых их особенностей, являются главным объектом, на котором просматриваются общие постановки задач.

Для произвольных конечнозначных логик, которые при m>2 существенно отличаются от двузначной логики, имеются эффективные решения задач о выразимости для конечных систем. Показано, что при m≥3 существуют m-значные логики с конечным базисом и в то же время не имеющие конечной полной системы тождеств[4], тогда как в двузначной логике каждый замкнутый класс имеет конечную полную систему тождеств[5]. Для конечнозначных логик с конечным базисом имеется эффективное решение задачи о полноте. Оно достигается следующим путем. Говорят, что функция сохраняет множество если для любого набора , где , имеет место . Множество K называется правильным, если селекторная функция содержится в K при всех j, 1≤ j ≤ n, и каждая функция из K сохраняет K. Если M=[K], то в M выбирают все системы K' с такими свойствами: функции в них зависят только от x₁, x₂ ... добавление к ним всех селекторных функций делает их правильными, они не содержат в качестве подмножества . Указанная процедура выделения всех правильных множеств , является эффективной. Критериальной системой является , где (класс сохранения Kj) состоит из всех функций из M, сохраняющих Kj, 1≤ i ≤ t. Невключение произвольного конечного множества в каждый из классов U(Ki) проверяется также эффективно. Каждый предполный класс является одним из классов сохранения, а множество всех предполных классов в этом случае образует критериальную систему. Показано, что при m≥3 в имеется континуум замкнутых классов, существуют замкнутые классы с базисами заданной конечной или счетной мощности, а также такие классы, которые не имеют базисов, при этом сами семейства классов без базисов или со счетным базисом континуальны. Примерами классов без базиса или имеющих счетный базис являются и , где: при n=0, а при функция равна 0 на всех наборах, кроме (2, ..., 2) на котором равна 1; равна на всех наборах, кроме наборов вида (2, ..., 2, 1, 2,..., 2) , на которых равна 1[6].

Особый интерес представляет задача о полноте в m-значной логике . В существуют конечные полные системы, что позволяет из каждой полной системы выделить конечную полную подсистему и свести задачу к изучению полноты конечных систем. Существуют также полные системы, состоящие из одной функции, такие функции называются шефферовыми. Примером их может служить функция Вебба max (x₁, x₂) + 1 (mod m). В силу конечной порожденности в эффективно решается задача о полноте.

В явно построены все предполные классы, являющиеся классами сохранения специальных предикатов. Указание этих предикатов составляет содержание теоремы о полноте в конечнозначных логиках[7]. Говорят, что функция сохраняет предикат , если формула

тождественно равна 1 при всех значениях переменных . Класс всех функций U(R), сохраняющих предикат R, называется классом сохранения предиката R. Показано, что для каждого предполного класса N можно выбрать такой предикат R, зависящий не более чем от m+2 переменных, а при m≥3 не более чем от m переменных, что N=U(R). Эти предикаты могут быть разбиты на шесть семейств: H, S, E, L, Z, U. Семейства H, S и E состоят из всех двуместных предикатов отношения порядка на, имеющих по одному максимальному и минимальному элементу, – в первом случае; задающих подстановки на , разлагающиеся в циклы одинаковой простой длины (без инвариантных элементов), – во втором случае; и задающих нетождественные и неуниверсальные отношения эквивалентности на – в третьем случае. Семейство L не пусто при , p – простое, и состоит из всех четырехместных предикатов таких, что = 1 эквивалентно y₁+y₂=y₃+y₄ , где G – абелева группа, в которой каждый ненулевой элемент имеет порядок p. Предикат рефлексивен, если из того, что не все числа a₁, a₂, ... различны, следует, что и симметричен, если для любой подстановки s чисел 1,2 ..., h имеет место . Множество элементов таких, что для любых , называется центром симметричного предиката R. Предикат является центральным, если он рефлексивен, симметричен и имеет центр с такой, что . Семейство Z состоит из всех h-местных центральных предикатов таких, что 1 ≤ h ≤ m. Для α из полагают , где . Семейство U состоит из всех предикатов таких, что  при 3 ≤ h ≤ m и , для некоторой сюръекции равенство эквивалентно тому, что набор неразнозначен при любом ℓ=0,1, ..., k-1. Установлено, что предикаты из разных семейств задают разные предполные классы, и указаны условия, когда предикаты из одного и того же семейства задают одинаковые классы. Показано, что число предполных классов асимптотически равно, где δ(m)=1, если m четно, и δ(m)=2, если m нечетно (т. е. это число растет достаточно быстро), что указывает на малую практическую эффективность критериальных систем[8]. Рассматриваются различные модификации задачи о полноте, сводящиеся к исследованию систем с некоторыми заранее известными свойствами, например систем, содержащих множество всех одноместных функций или же множество всех подстановок. В первом случае система при m>2, а во втором m>4 при является полной тогда и только тогда, когда она содержит существенную функцию, т. е. функцию, зависящую более чем от одного переменного и принимающую все m значений [9][10]. С ними связана задача указания всех таких подмножеств T множеств и , каждое из которых вместе с любой существенной функцией образует полную систему. Показано, что подмножество всех одноместных функций, не принимающих хотя бы одного значения, является таковым, а подмножество всех одноместных функций, не принимающих хотя бы двух значений, вообще говоря, таковым уже не является. При m>4 таковыми являются те и только те подмножества T, которые 4-транзитивны при , 3-транзитивны при , p– простое, p≠2, 2-транзитивны при остальных m. Эти условия после естественного обобщения транзитивности сохраняются и для произвольных Для систем, состоящих из одной функции, критерием полноты является условие 2-транзитивности. Произвольное множество функций при m>2 является полным тогда и только тогда, когда оно m-транзитивно и степень транзитивности не может быть понижена.

От конечных полных систем путем операции отождествления можно перейти к рассмотрению более простого класса полных систем, называемого простыми базисами. Под простым базисом понимается такая конечная полная система, которая теряет свойство полноты после отождествления любой пары существенных переменных у любой функции этой системы. Существует лишь конечное число q простых базисов и [11]. Число переменных y функций из простых базисов не превосходит , и существует функция, входящая в простой базис и существенно зависящая от переменных. Указаны представления М. л. в т. е. гомоморфизмы в [12]; построены также некоторые аналоги теории минимизации для произвольных конечнозначных логик.

Первыми примерами конечнозначных логик явились трехзначная логика Лукасевича, которая порождается функциями 1-x, min(1,1-x₁+x₂), где x₁, x₂ принимают значения 0,1/2,1 и m-значная логика Поста, которая порождается функциями x₁+1 (mod m), max(x₁, x₂), где x₁, x₂ принимают значения 0,1, ..., m-1. К конечнозначным логикам примыкают алгебры многозначных функций, на которые в значительной мере переносятся проблематика и методы исследования конечнозначных логик.

Примерами других М. л. являются счетнозначные и континуумзначные логики (т. е. такие m-значные логики, для которых мощность m является соответственно счетной или континуальной). Эти модели играют важную роль в математической логике, теории моделей и в математическом анализе. Для счетнозначных логик установлена гиперконтинуальность множеств предполных (а значит и множества всех) замкнутых классов и найдено решение задачи о полноте систем, содержащих множество всех одноместных функций[13]. В отличие от конечнозначных логик при m>2, где имеется только один предполный класс, содержащий все одноместные функции, в существуют два таких предполных класса и указанная система функций является полной тогда и только тогда, когда она не содержится в этих классах. Если обобщить понятие существенной функции и считать, что таковой является всякая функция, образующая полную систему вместе с , то так же, как и в конечнозначных логиках, возникает задача описания всех тех подмножеств множества , которые содержат все множество подстановок из и вместе с любой существенной функцией образуют полную систему. Показано, что пересечение всех таких замкнутых подмножеств само обладает указанным свойством. Это пересечение, которое отлично от , эффективно описано в теоретико-множественных терминах.

В счетнозначных и континуумзначных логиках особую роль играют различные их подклассы. Таковыми являются в первом случае предельные логики, а во втором – М. л. непрерывных функций. Предельные логики представляют собой счетные замкнутые классы функций М. л. , содержащие гомоморфные прообразы всех конечнозначных логик. Существует континуум различных и даже конечно порожденных попарно неизоморфных предельных логик. Установлено, что в общем случае для предельных логик задача о полноте не эквивалентна отысканию всех предполных классов. Мощность множества предполных классов в предельных логиках может быть равной любому натуральному числу, а также быть счетной или континуальной[14]. Для М. л. непрерывных функций показана полнота всех двуместных функций и получены некоторые аналоги теоремы о полноте систем, состоящих из всех одноместных и многоместной функций. Установлено также, что всякую непрерывную функцию можно представить в виде суммы специально выбранных непрерывных одноместных функций. Показано, что для k раз дифференцируемых функций от n переменных, вообще говоря, невозможно представление их с помощью суперпозиций функций той же гладкости, но зависящих от меньшего числа переменных[15].

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

↑Рекомендуемая литература

Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б., Функции алгебры логики и классы Поста, М., 1966

Лупанов О.В., Проблемы кибернетики, 1965

Журавлев Ю.И., Проблемы кибернетики, 1962

Линдон Р.К., Кибернетичtкий сборник, 1960

Мурский В.Л., Докл. АН СССР, 1965, т. 163, №4

Янов Ю.И., Мучник А.А., Докл. АН СССР, 1959, т. 127, №1

Rоsеnbеrg J., Ьber die funktionale Vollstдndigkeit in den mehrwertigen Logiken, Praha, 1970

Зaxapовa E.Ю., Кудрявцев В.Б., Яблонский С.В., Докл. АН СССР, 1969, т. 186, №3

Яблонский С.В., Тр. Матем. ин-та АН СССР, 1958, т. 51

Саломаа А., Кибернетич. сборник, 1964

Кудрявцев В.Б., Elektronische Informationsverarbeitung und Kybernetik (EIK), 1973, Bd 9, Hft 1/2, S. 81-105

Алексеев В.Б., Дискретный анализ, 1971, №19

Мальцев А.И., Алгебра и логика, 1966, т. 5

Гаврилов Г.П., Проблемы кибернетики, 1965

Деметрович Я., Проблемы кибернетики, 1975

Витушкин А.Г., в кн.: Тр. Международного конгресса математиков, М., 1968