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

Раздел математической логики, изучающий математич. модели логики высказываний. Эти модели отражают две основные черты последней — множественность значений истинности высказываний и возможность построения новых более сложных высказываний из заданных при помощи логич. операций, к-рые позволяют также по значениям истинности исходных высказываний устанавливать значение истинности сложного высказывания. Примерами многозначных высказываний являются суждения с модальным исходом ("да", "нет", "может быть") и суждения вероятностного характера, а примерами логич. операций — логич. связки типа "и", "пли", "если..., то". В общем случае модели М. л. представляют собой обобщения алгебры логики. Важно отметить, что в алгебре логики высказывания принимают только два значения истинности ("да", "нет"), в связи с чем она в общем случае не может отразить всего многообразия логпч. построений, встречающихся на практике. При достаточно широком толковании М. л. в нее иногда включают также логические исчисления. Исторически первыми моделями М. л. явились двузначная логика Дж. Буля (G. Boole, сер. 19 в.), называемая также алгеброй логики, трехзначная логика Я. Лукасевича (J. tucasiewicz, 1920) и m-значная логика Э. Поста (Е. Post, 1921). Изучение этих моделей составило важный этап в создании теории М. л. Основные модели многозначной логики. М. л. обладает определенной спецификой, состоящей в рассмотрении задач и подходов, возникающих при исследовании М. л. с позиций математич. логики, математич. кибернетики и алгебры. Так, с позиций математич. кибернетики модели М. л. рассматриваются как языки, описывающие функционирование сложных управляющих систем, компоненты к-рых могут находиться в нек-ром числе различных состояний, а с точки зрения алгебры модели М. л. представляют алгебраические системы, имеющие наряду с прикладным и теоретич. интерес. Построение моделей М. л. осуществляется по, аналогии с построением двузначной логики. Так, индивидуальные высказывания логики, разбитые на классы с одним и тем же значением истинности, приводят к понятию множества Е- констант модели, к-рые фактически отождествляют все индивидуальные высказывания, заменяя их соответствующими значениями истинности; переменные высказывания приводят к переменным величинам х 1 , х 2, ..., которые в качестве значений принимают элементы из множества Е;. логич. связки приводят к множеству Мэлементарных функций (операций), к-рые, как и их аргументы, принимают значения из Е. Сложные высказывания, построенные из индивидуальных и переменных высказываний, а также логич. связок, приводят к множеству формул над М. Значение истинности из Есложного высказывания является функцией от соответствующих значений истинности высказываний, входящих в данное сложное высказывание. В модели эта функция приписывается формуле, соответствующей данному сложному высказыванию; говорят также, что формула реализует эту функцию. Функции, отображающие кортежи элементов из Ев Е, наз. функциями т- значной логики, где тобозначает мощность множества Е. Множество всех функций m-значной логики обозначают через Р т . Множество формул приводит к множеству [М]функций, реализуемых формулами из и наз. суперпозиция м и (или композициями) над М. Множество [М]наз. замыканием множества М. Задание конкретной модели М. л.считается эквивалентным указанию множеств Е, М,<M> и [М], при этом говорят, что модель порождается множеством М;если Мконечно, говорят, что модель является конечно порожденной. Эта модель наз. формульной моделью, а также т- значной логикой. Своеобразие подхода математич. кибернетики к М. л. состоит в рассмотрении моделей М. л. как управляющих систем. Элементарные функции при этом являются элементами, производящими определенные операции, а формулы интерпретируются как схемы, построенные из элементов и также осуществляющие переработку входной информации в выходную. Такого рода управляющие системы, известные в кибернетике как схемы из функциональных элементов (без ветвления), широко используются в теоретич. и практич. вопросах кибернетики. Вместе с тем существует ряд задач логики н кибернетики, к-рый связан с изучением соответствий между множествами Ми [М]и при к-ром роль множества <М> несколько затушевывается, сводясь к способу определения второго множества по первому. В этом случае приходят к другой модели М. л., представляющей собой алгебру, элементами к-рой являются функции, принимающие в качестве значений, как и их аргументы, элементы из Е. В качестве операций в этих алгебрах обычно используется специальный набор операций, эквивалентный в смысле соответствий Ми [М]множеству формул, построенных из функций множества М, т. е. получению сложных функций из заданных путем подстановки одних функций вместо аргументов других. Эти алгебры наз. алгебрами m-значных логик. Конкретно это может быть достигнуто, напр., введением следующих унарных операций: и бинарной операции . В предположении, что каждая функция f из PE с учетом фиктивных переменных зависит от переменных х 1 , х 2, ... , х п, где попределяется функцией f, эти операции могут быть заданы так: если если n=1; и для Возникающие алгебры иногда наз. алгебрами Поста. Проблематика многозначной логики. К числу задач, характерных для формульной модели М. л., относится задача "об описании", т. е. вопрос об указании для заданного множества всех формул из реализующих функции из . Частным случаем такой задачи является важный вопрос математич. логики об указании всех формул, реализующих заданную константу, что, напр., для исчисления высказываний эквивалентно построению всех тождественно истинных высказываний. Пограничным вопросом между математич. логикой и алгеброй, примыкающим к задаче об описании, является задача о тождественных преобразованиях. В ней при заданном множестве Мтребуется выделить в нек-ром смысле простейшее подмножество пар равных, т. е. реализующих одну и ту же функцию, формул из (тождеств), позволяющее путем подстановки выделенных равных формул одной вместо другой получить из любой формулы все формулы, равные ей (полную систему тождеств). Аналогичное место занимает т. н. проблема полноты, состоящая в указании всех таких подмножеств заданного замкнутого, т. е. совпадающего со своим замыканием, множества М, для к-рых выполнено равенство т. е. имеет место свойство полноты (или свойство функциональной полноты) M1 в М. К этой задаче примыкает задача о базисах, состоящая в указании всех полных в Мподмножеств М 1 никакое собственное подмножество к-рых уже не полно в М(базисы называют также полными независимым и системами функций). Выделяют два подхода к решению задачи о полноте — алгоритмический и алгебраический. В первом случае ставится вопрос о существовании алгоритма, устанавливающего полноту или неполноту систем функций, описанных на нек-ром языке; во втором — переходят к изучению свойств решетки подалгебр данной алгебры m-значной логики и решают задачу о полноте, используя эти свойства. Важным понятием при алгебраич. подходе является понятие критериальной системы подалгебр. Система Nподалгебр алгебры наз. критериальной, если любое множество является полным тогда и только тогда, когда оно не является подмножеством ни одной подалгебры из N. Таково, напр., множество всех собственных подалгебр алгебры М. В общем случае последняя критериальная система является избыточной. Всякая критериальная система содержит все максимальные подалгебры алгебры М(или предполные класс ы), и это позволяет перейти к рассмотрению более экономных критериальных систем, к-рые не содержат подалгебр максимальных подалгебр. Таким образом, в задачах о полноте можно ограничиться использованием критериальных систем вида где — множество всех максимальных подалгебр, а множество состоит из нек-рых таких подалгебр, к-рые не являются подалгебрами никакой максимальной подалгебры. В случае пустоты е 2 задача о полноте сводится к описанию максимальных подалгебр алгебры N. Глобальной задачей для М. л. является описание решетки замкнутых классов данной модели М. л. Характерный для теории управляющих систем вопрос о сложности этих систем естественно возникает и по отношению к формулам и функциям из М. л. Типичной при таком подходе является следующая задача о сложности реализации. На множестве всех элементарных формул нек-рым способом вводится числовая мера (сложность формул), к-рая затем распространяется на множество всех формул, напр, путем суммирования мер всех тех элементарных формул, к-рые участвуют в построении заданной формулы. Требуется для заданной функции указать ту формулу (простейшую), к-рая реализует эту функцию и имеет наименьшую сложность, а также выяснить, как эта сложность зависит от нек-рых свойств рассматриваемой функции. Исследуются различные обобщения этой задачи. Широкий круг вопросов связан с реализацией функций формулами с наперед заданными свойствами. Сюда относятся задача о реализации функций алгебры логики дизъюнктивными нормальными формами и связанная с этим задача минимизации; а также задача о реализации функций формулами в нек-ром смысле ограниченной глубины (т. е. такими формулами, в к-рых цепочка подставляемых друг в друга формул имеет ограниченную длину, такое ограничение связано с надежностью и скоростью вычислений), задача о декомпозиций, т. е. о реализации функций от переменных при помощи формул, построенных из элементарных формул, реализующих функции от меньшего числа переменных, и ряд других. Решения всех перечисленных выше задач существенно зависят от мощности множества Еи множества М, порождающего заданную модель М. л. Важнейшие примеры многозначных логик. К числу наиболее важных примеров М. л. относятся конечно-значные логики (т. е. m-значные логики, для к-рых тконечно). Для них обычно полагают, что Е=Е , а m-значную логику MF обозначают М т . Наиболее глубоко исследован случай т=2, при этом функции двузначной логики наз. также булевыми функциями. Важнейшим результатом здесь является полное описание Э. Постом (Е. Post, см. [1]) решетки замкнутых классов. Множество их оказалось счетным, а каждый класс и решетки их по включению строятся эффективно. Эти классы наз. классами Поста. Всякий замкнутый класс имеет конечный базис, и его мощность не превосходит 4. Из этих результатов получаются решения задач о выразимости, полноте и базисах, а также задачи о тождественных преобразованиях. Относительно полных конечных систем для "почти всех" функций указано поведение меры сложности простейших формул, реализующих эти функции, и построен соответствующий алгоритм синтеза формул (см. [2]). Изучены задачи о построении оптимальных по сложности формул, реализующих функции надежно и достаточно хорошо по быстродействию, а также вопросы сложности реализации для большого числа специальных классов функций и отдельных функций. Одним из глубоко исследованных вопросов для двузначной логики является также задача минимизации. В ней изучается специальный язык задания функций двузначной логики — язык дизъюнктивных нормальных форм (д. н. ф.). Вводится понятие сложности д. н. ф.- число букв в ней — и изучаются задачи поиска, строения и метрич. свойств "простейших" в смысле этой меры д. н. ф., реализующих заданную функцию (см. [3]). Задача о декомпозиции для булевых функций состоит в выяснении условий, при к-рых заданная функция от ппеременных может быть реализована формулой, построенной из функций от меньшего числа переменных, причем все функции, подставляемые друг в друга в процессе построения формулы, не зависят от общих переменных. Такие формулы наз. бесповторными. Показано, что не существует конечной системы функций такой, что каждая функция может быть реализована бесповторной формулой над этой системой, и даже что "почти все" функции не допускают реализации бесповторными формулами. В целом двузначные логики, в силу нек-рых их особенностей, являются главным объектом, на к-ром просматриваются общие постановки задач. Для произвольных конечнозначных логик, к-рые при m>2 существенно отличаются от двузначной логики, имеются эффективные решения задач о выразимости для конечных систем. Показано, что при существуют m-значные логики с конечным базисом и в то же время не имеющие конечной полной системы тождеств (см. [4]), тогда как в двузначной логике каждый замкнутый класс имеет конечную полную систему тождеств (см. [5]). Для конечнозначных логик с конечным базисом имеется эффективное решение задачи о полноте. Оно достигается следующим путем. Говорят, что функция f(x1,... , х п). сохраняет множество К= , если для любого набора gi1 gi2,..., gik , где , имеет место . Множество Кназ. правильным, если селекторная функция содержится в Кпри всех и каждая функция из Ксохраняет К. Если М=[К], то в М выбирают все системы с такими свойствами: функции в них зависят только от добавление к ним всех селекторных функций делает их правильными, они не содержат в качестве подмножества К. Указанная процедура выделения всех правильных множеств , является эффективной. Критериальной системой является , где (класс сохранения К i )состоит из всех функций из М, сохраняющих . Невключение произвольного конечного множества в каждый из классов проверяется также эффективно. Каждый пред-полный класс является одним из классов сохранения, а множество всех предполных классов в этом случае образует критериальную систему. Показано, что при в имеется континуум замкнутых классов, существуют замкнутые классы с базисами заданной конечной или счетной мощности, а также такие классы, к-рые не имеют базисов, при этом сами семейства классов без базисов или со счетным базисом континуальны. Примерами классов без базиса или имеющих счетный базис являются и , где: при n=0, а при n>0 функция fn( х 1 ,... , х п )равна 0 на всех наборах, кроме (2, ... , 2), на к-ром равна 1; gn(x1 , ..., х п ). равна 0 на всех наборах, кроме наборов вида (2, ... , 2,1, 2, ... , 2), на к-рых равна 1 (см. [6]). Особый интерес представляет задача о полноте в т- значной логике Р т. В Р т существуют конечные полные системы, что позволяет из каждой полной системы выделить конечную полную подсистему и свести задачу к изучению полноты конечных систем. Существуют также полные системы, состоящие из одной функции, такие функции наз. шефферовыми. Примером их может служить функция Вебба mах (x1, х 2)+l (mod m). В силу конечной порожденности в Р т эффективно решается задача о полноте. В Р т явно построены все предполные классы, являющиеся классами сохранения специальных предикатов. Указание этих предикатов составляет содержание теоремы о полноте в конечнозначных логиках (см. [7]). Говорят, что функция f , если формула тождественно равна 1 при всех значениях переменных . Класс U(R)всех функций, сохраняющих предикат R, наз. классом сохранения предиката R. Показано, что для каждого предполного класса Nможно выбрать такой предикат R, зависящий не более чем от m+2 переменных, а при не более чем от тпеременных, что N= U(R). Эти предикаты могут быть разбиты на шесть семейств: Н. S, Е, L, Z, U. Семейства Н, S и Есостоят из всех двуместных предикатов отношения порядка на Е т, имеющих по одному максимальному и минимальному элементу,- в первом случае; задающих подстановки на Е т, разлагающиеся в циклы одинаковой простой длины (без инвариантных элементов),- во втором случае; и задающих нетождественные и неуниверсальные отношения эквивалентности на Е т- в третьем случае. Семейство Lне пусто при m=р h, р- простое, и состоит из всех четырехместных предикатов RG(y1 , у2, у 3 , y4 )таких, что RG (y1 , у2, у 3 , y4)=1 эквивалентно y1+ у2 = у 3 + y4., где G- абелева группа, в к-рой каждый ненулевой элемент имеет порядок р. Предикат R(y1 ,... у h ), рефлексивен, если из того, что не все числа а 1 , а2, ... , ah различны, следует, что R(a1 , a2, ..., ah)=1, и симметричен, если для любой подстановки s чисел 1, 2, ... , hимеет место R(y1 ,... у h )= R(ys(1) , ... , ys(h)). Множество элементов таких-то R(a1, ... , ah-1 , c)=1 для любых а 1 , ..., ah_1 , наз. центром симметричного предиката R. Предикат R(y1 ,... у h ) является центральным, если он рефлексивен, симметричен и имеет центр с такой, что . Семейство 2состоит из всех h- местных центральных предикатов таких, что 1=<h=<m. Для аиз полагают Семейство Uсостоит из всех предикатов R(y1,... , yh )таких, что при , для нек-рой сюръекции равенство R(a1, ... , ah) = l эквивалентно тому, что набор неразнозначен при любом l=0, 1, ... , k-1. Установлено, что предикаты из разных семейств задают разные предполные классы, и указаны условия, когда предикаты из одного и того же семейства задают одинаковые классы. Показано, что число предполных классов асимптотически равно , где , если тчетно, и , если тнечетно (т. е. это число растет достаточно быстро), что указывает на малую практич. эффективность критериальных систем (см. [8]). Рассматриваются различные модификации задачи о полноте, сводящиеся к исследованию систем с нек-рыми заранее известными свойствами, напр, систем, содержащих множество всех одноместных функций или же множество Sm всех подстановок. В первом случае система при m>2, а во втором при m>4 является полной тогда и только тогда, когда она содержит существенную функцию, т.