Новая философская энциклопедия. Том второй Е—М

МНОГОЗНАЧНЫЕ ЛОГИКИ ции является множество M (без ограничения общности можно считать, что его элементами являются 0, 1, 2,..., п-1), называется n-значной функцией, или функцией n-значной логики. Имеются различные способы задания функций. Напр., функция f(x,..., xm) может быть задана таблицей, где в некотором порядке перечислены все n-ичные наборы длины m (из элементов 0, 1, 2,..., п — 1) и на каждом из них указано значение функции, как это делалось в двузначной логике. Число п-ичных наборов длины m равно nm и на каждом из них значение функции можно задать п способами. Поэтому число всех функций n-значной логики Ри, зависящих от аргументов х,..., хт, составляет п"™ . Случай п > 2 оказывается существенно более сложным, чем классический случай Рт Уже в Р3 число функций от двух переменных равно 19 683, в то время как в Р2 таких функций всего 16. Как и в двузначном случае, в Рп выделяются функции, которые наиболее часто употребляются в логике и кибернетике и играют там важную роль. Такие функции называются элементарными. Вот некоторые из них: константы 0,1, 2,..., п—1 — (нульместные функции); отрицание Лукасевича: ~х=(п— 1)—х — обобщение отрицания в смысле «зеркального отрицания»; отрицание Поста: —ix = х + l(mod n) — обобщение отрицания в смысле «циклического сдвига значений»; характеристическая функция числа i, i = 0,1,..., n — 1: т ( ч _ f n — 1, если х = i, JiW~ 10,еслих*1. J.(x) — обобщение некоторых свойств отрицания; минимум х и у: х л у = min (x, у) — обобщение конъюнкции; максимум х и у: х V у = max (x, у) — обобщение дизъюнкции; сумма по модулю п:х ® у = х + у (mod n) — обобщение суммы по mod 2 (значение этой функции равно остатку от деления суммы х + у на п); импликация Лукасевича: х =/п- 1,еслих <у, \ (п — 1) — х + у, если х > у. х —> у — обобщение одного из свойств классической импликации; функция Вебба: Wn(x, у) = тах(х, у) + l(mod n) — обобщение штриха Шеффера на функционально полную логику Поста Рп. Операция дизъюнкции х V у и отрицание Поста -iX, определенные на множестве М, являются исходными операциями первой n-значной логикой (п>3), названной Рп, которая была построена Постом в 1921, притом с произвольным числом выделенных значений. В свою очередь, n-значная логика Лукасевича Ln была построена в 1922—23 как обобщение L3. Изучение Ln и Рп составило важнейший этап в развитии теории многозначных логик. Кроме двух рассмотренных способов задания функций (табличного и алгоритмического (в последнем случае x v у, к примеру, задается как тах(х, у)) не менее известным способом является формула, описывающая функцию как суперпозицию исходных элементарных функций. Функция, полученная из функций f,,..., fk подстановкой и/или переименованием аргументов, называется суперпозицией f,,..., fk. Выражение, описывающее эту суперпозицию и содержащее функциональные знаки и символы аргументов, называется формулой, и тогда говорят, что формула реализует или представляет данную функцию. В этом случае имеем дело с формульной моделью многозначной логики, а сама модель зачастую отождествляется с этой логикой. Основной проблемой здесьявляется проблема интерпретации истинностных значений. Для широкого класса многозначных логик эта проблема решена А. С. Карпенко (1983) в терминах классических истинностных значений. В кибернетике такие модели рассматриваются как управляющие системы. Элементарные функции при этом являются элементами, производящими определенные операции, а формулы интерпретируются как схемы, построенные из элементов и осуществляющие переработку входной информации в выходную. Характерными для формульной модели являются: задача об указании всех формул, реализующих заданную константу; задача об эквивалентных преобразованиях; задача о сложности реализации; задача о минимизации и т. д. Однако в зависимости от того, какие цели преследуются при изучении многозначных логик, по-разному понимается, что собой представляет ее модель. Для многих специалистов, связанных с вычислительной техникой, инженеров, прикладных математиков и физиков гораздо большее значение имеет представление модели многозначной логики в виде функциональной системы, обозначаемой (Рп, С), где Рп есть множество всех функций n-значной логики (или множество всех функций счетнозначной логики PJ с заданной на нем операцией суперпозиции С, а сама функциональная система (Рп, С) зачастую отождествляется с многозначной логикой, т. е. (Рл, С) выступает в качестве модели многозначной логики. Эта модель, в отличие от рассмотренных выше алгебр истинностных значений, является алгеброй функций. Известна содержательная трактовка понятия функциональной системы ((РпУ С) выступает ее частным случаем), в основе которой лежит рассмотрение таких пар (Р, Q), в которых Р есть множество отображений, реализуемых управляющими системами из некоторого класса, a Q состоит из операции, используемой при построении новых управляющих систем из заданных. В нашем случае Q представляет собой операцию суперпозиции С. Труднейшей проблемой при изучении функциональных систем является следующая: какие функции могут быть сконструированы из данного множества функций. Проблема эта возникает и в самом пропозициональном исчислении, представленном формульной моделью, и в синтезе автоматов, и в универсальной алгебре; но именно здесь ей уделяется специальное внимание. Важнейшее свойство функциональной системы есть свойство функциональной полноты (напр., для того, чтобы можно было реализовать любую переключательную схему). Система функций 9t = {f,,—, fk,...} из Р называется функционально полной, если любая функция из Рп пред- ставима посредством суперпозиций функций из системы 9t. Т. о., указанная выше проблема приобретает здесь следующий вид: является ли некоторое множество 9t функционально полным? Напр., логика Поста Рп, как и классическая двузначная логика, является функционально полной. Отсюда их исключительно широкое применение и развитие. С понятием полноты связано понятие операции замыкания и замкнутого класса. Пусть 9t c P • Множество всех функций, которые могут быть получены из функций системы 9t с помощью операции суперпозиции, называется замыканием 91 и обозначается [9t ]. Класс функций 9t называется (функционально) замкнутым, если [9t ] = 9t, т. е. замкнутость класса функций 9I обозначает собою сохранение при суперпозиции «наследственных» свойств этих функций. В терминах замыкания можно дать другое определение полноты, эквивалентное исходному: 9t — полная система, если [ 9t ] = Р .