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

МНОГОЗНАЧНАЯ ЛОГИКА раздел математической
логики, изучающий математические модели логики высказываний. Эти
модели отражают две осн. черты последней - множественность значений истинности
высказываний и возможность построения новых, более сложных высказываний
из заданных при помощи логич. операций, к-рые позволяют также по значениям
истинности исходных высказываний устанавливать значение истинности сложного
высказывания. Примерами многозначных высказываний являются суждения с модальным
исходом ("да", "нет", "может быть") и суждения вероятностного характера,
а примерами логич. операций - логич. связки типа "и", "или", "если...,
то". В общем случае модели М. л. представляют собой обобщения алгебры
логики. Важно отметить, что в алгебре логики высказывания принимают
только два значения истинности ("да", "нет"), в связи с чем она в общем
случае не может отразить всего многообразия логич. построений, встречающихся
на практике. При достаточно широком толковании М. л. в неё иногда включают
также логич. исчисления.

Исторически первыми моделями М. л. явились
двузначная логика Дж. Буля (называемая также алгеброй логики), трёхзначная
логика Я. Лукасевича (1920) и пг-значная логика Э. Поста (1921).
Изучение этих моделей составило важный этап в создании теории М. л. М.
л. обладает определённой спецификой, состоящей в рассмотрении задач и подходов,
возникающих при исследовании М. л. с позиций матем. логики, теоретич. кибернетики
и
алгебры.
Так,
с позиций теоретич. кибернетики, модели М. л. рассматриваются как языки,
описывающие функционирование сложных управляющих систем, компоненты к-рых
могут находиться в нек-ром числе различных состояний; а с точки зрения
алгебры, модели М. л. представляют собой алгебраич. системы, имеющие наряду
с прикладным и чисто теоретич. интерес.

Построение моделей М. л. осуществляется
по аналогии с построением двузначной логики. Так, индивид, высказывания
логики, разбитые на классы с одним и тем же значением истинности, приводят
к понятию множества Е - констант модели, к-рые фактически отождествляют
все индивидуальные высказывания, заменяя их соответствующими значениями
истинности; переменные высказывания - к переменным величинам xi, х..., к-рые в качестве значений принимают элементы из множества Я; логич.
связки - к множеству М элементарных функций (операций), к-рые, как
и их аргументы, принимают значения из Е. Сложные высказывания, построенные
из индивидуальных и переменных высказываний, а также логич. связок, приводят
к множеству <М> формул над М. Значение истинности из Е
сложного
высказывания является функцией от соответствующих значений истинности высказываний,
входящих в данное сложное высказывание. В модели эта функция приписывается
формуле, соответствующей данному сложному высказыванию; говорят также,
что формула реализует эту функцию. Множество формул <М>
приводит
к множеству [М] функций, реализуемых формулами из <М>
и
называемых суперпозициями над М. Множество [М] наз. замыканием множества
М.
Задание
конкретной модели М. л. считается эквивалентным указанию множеств
Е,
М, <М> и [Л/]; при этом говорят, что модель порождается множеством
М.
Эта модель наз. формульной моделью, а также m-значной логикой, где
т обозначает мощность множества Е.

Своеобразие подхода матем. кибернетики
к М. л. состоит в рассмотрении моделей М. л. как управляющих систем. Элементарные
функции при этом являются элементами, производящими определённые операции,
а формулы интерпретируются как схемы, построенные из элементов и также
осуществляющие переработку входной информации в выходную. Такого рода управляющие
системы, известные в кибернетике как схемы из функциональных элементов,
широко используются в теоретич. и практич. вопросах кибернетики. Вместе
с тем существует ряд задач логики и кибернетики, к-рый связан с изучением
соответствий между множествами М и [М] и при к-ром роль множества
<М>
несколько
затушёвывается, сводясь к способу определения второго множества по первому.
В этом случае приходят к другой модели М. л., к-рая представляет собой
алгебру, элементами к-рой являются функции, принимающие в качестве значений,
как и их аргументы, элементы из Е. В качестве операций в этих алгебрах
обычно используется спец. набор операций, эквивалентный в смысле соответствий
М
и [М] множеству формул, построенных из функций множества
М,
т. е. получению сложных функций из заданных путём подстановки одних
функций вместо аргументов других.

К числу задач, характерных для формульной
модели М. л., относится задача "об описании", т. е. вопрос об указании
для заданного множества М [Mi]
всех формул из <Mi>, реализующих функции из Мслучаем такой задачи является важный вопрос матем. логики об указании всех
формул, реализующих заданную константу, что, напр., для исчисления высказываний
эквивалентно построению всех тождественно истинных высказываний. Пограничным
вопросом между матем. логикой и алгеброй, примыкающим к задаче об описании,
является задача о тождественных преобразованиях. В ней при заданном множестве
М
требуется
выделить в нек-ром смысле простейшее подмножество пар равных (т. е. реализующих
одну и ту же функцию) формул из <М>, позволяющее путём подстановки
выделенных равных формул одной вместо другой получить из любой формулы
все формулы, равные ей. Аналогичное место занимает один из важнейших вопросов
для М. л.- т. н. проблема полноты, состоящая в указании всех таких подмножеств
Mi
заданного замкнутого, т. е. совпадающего со своим замыканием, множества
М, для к-рых выполнено равенство [Mi] = М, т. е. имеет место
свойство полноты Mi в М. Глобальной задачей для М. л. является описание
структуры замкнутых классов данной модели М. л.

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

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

К числу наиболее важных примеров М. л.
относятся конечнозначные логики (т. е. ги-значные логики, для к-рых т
конечно).
Среди них наиболее глубоко исследован случай т = 2. Важнейшим результатом
здесь является полное описание структуры замкнутых классов и получение
для них важной информации по задаче о сложности реализации. Установлено,
что при m > 2 у конечнознач-ных логик возникает ряд особенностей, существенно
отличающих их от двузначного случая. Таковы, напр., континуальность множества
замкнутых классов (при m = 2 их счётное число), особенности решения задачи
о сложности реализации и ряд других. Общим результатом для конечнозначных
логик является эффективное решение задачи о полноте для замкнутых классов,
содержащих все функции со значениями в Е. Решение остальных проблем
для конечнозначных логик продвинуто в различной степени. Особая значимость
конечнозначных логик связана ещё и с тем, что они позволяют описывать работу
самых различных реальных вычислит, устройств и автоматов.

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

Лит.: Яблонский С. В., Гаври-л о
в Г. П., Кудрявцев В. Б., Функции алгебры логики и классы Поста, М., 1966;
Яблонский С. В., Функциональные построения в fe-значной логике, "Тр. Матем.
ин-та АН СССР", 1958, т. 51, с. 5-142.

В. Б. Кудрявцев.