Дискретно-непрерывная математика (стр. 32 )

~ есть унарная и → бинарная операции отрицания и импликации соответственно, определенные на множестве Vn сле­дующим образом:

Операции дизъюнкции и конъюнкции вводятся по опреде­лению:

Заметим, что здесь '.

Определим теперь функцию оценки v формул языка в мат­рице v есть функция оценки формул языка ватрице если она удовлетворяет следующим условиям:

1) функция v определена для каждой формулы А;

2) если А есть пропозициональная переменная, то

3) если А и В есть формулы, то

Обратим внимание, что здесь в левые части равенств входят пропозициональные связки, а в правые - символы матричных опе­раций. Для простоты, и те и другие обозначаем одинаково.

Будем говорить, что формула А является тавтологией в матри­це если для любой функции оценки v в матрице Наконец, многозначная матричная логика Лукасевича есть множество тавтологий в

Отметим, что матрицаявляется характеристической для классического пропозиционального исчисления С2 (см. раздел 1.4), а матрицаявляется характеристической для трехзначного ис-яисления (см. раздел 3.1).

5.1.2. Отношения между конечнозначными логиками

Основное отношение между конечнозначньши матричными логи-

ками Лукасевича, т. е. между классами их тавтологий, описываются риедующим условием Линденбаума [Lukasiewicz and Tarski 1930, theorem 19]:

т. т.т., когда т-есть делитель n-1.

Впервые доказательство этой теоремы было опубликовано Щ. Аккерманном [Аскегтапп 1967].

Из этой теоремы имеем очевидное следствие для случая, когда п-1 есть простое число

5.1.3. Ji-операторы

Особое место при изучении свойств конечнозначных логик Лука-севича занимают Ji-операторы, введенные Дж. Россером и А. Тюркеттом [Rosser andTurqette 1952]:

Ими доказана следующая

Теорема. Ji-операторы определимы посредством → и ~ в .

Заметим, что результат этой теоремы следует из критерия Мак-Нотона (о нем см. 5.1.5). :

На самом деле Ji - операторы являются характеристическими функциями числа и обобщают некото-

рые свойства отрицания. В дальнейшем Ji - операторы будут не раз использоваться.

5.1.4. Оператор Слупецкого для

В [Rosser and Turqette 1952] дано также обобщение резуль­тата Е. Слупецкого относительно (см. 3.1.1):

Пусть для всех Тогда система функций

{х →у, ~х, } функционально полна.

В свою очередь обобщением этого результата стала теорема Эванса—Шварца [Evans and Schwartz 1958]:

Пусть где 0 < i < I. Тогда система функций

является функционально полной т. т.т., когда (п-1, i) = 1, т. е. п-1 и i есть взаимно простые числа.

Этот результат независимо был открыт Р. Клэем [Clay 1962] как следствие теоремы:

Система функций является функционально

полной т. т.т., когда где

В разделе (7.3.3) будет дано строгое определение понятия функциональной полноты.

5.1.5. Критерий Мак-Нотона выразимости

операций в

В общем случае на вопрос о том, какие операции (функции) можно выразить в дает ответ критерий выразимости Р. Мак-Нотона, который является следствием фундаментальной теоремы Мак-Нотона о выразимости функций в континуальной логике Лукасеви­ча [McNaughton 1951] (см. ниже раздел 8.1):

Функция выразима в матрице для тогда

и только тогда, когда НОД (x1, ..., хk, п-1) есть делитель х (НОД — наибольший общий делитель).

С помощью критерия Мак-Нотона доказывается много важных теорем относительно многозначных логик Лукасевича (см. об этом [Токаж 1979]).

Следует отметить, что хотя Мак-Нотон дает необходимое и достаточное условие выразимости конечнозначной функции в само доказательство не является конструктивным; оно только ука­зывает, какие конечнозначные функции f являются выразимыми без указания метода, конструирующего-формулу, определяющую f в терминах ~ и →. Эта проблема решена в [Takagi, Nakashima and Mukaidono 1999], где представлено другое необходимое и доста­точное условие. Более того, в этой работе показывается, как выра­зить функцию в языке по ее истинностной таблице.

5.1.6. Аксиоматизация

В разделе (3.1) была рассмотрена аксиоматизация трехзначной ло­гики Лукасевича предложенная М. Вайсбергом. Однако неясно, как этот способ аксиоматизации может быть распространен на ко­нечнозначные логики Правда, ему же принадлежит аксиомати­зация для случая, когда п-1 есть простое число. Как отмечается в [Lukasiewicz and Tarski 1930], расширение этого результата на произвольное конечное п принадлежит Линденбауму. айсбергом [Wajsberg 1935] был предложен общий ме­тод аксиоматизации широкого класса конечнозначных логик, куда входят также все n-значные логики Лукасевича. Однако метод, предложенный В айсбергом, весьма громоздок и практически мало пригоден.

Две неудачные попытки аксиоматизировать были пред­приняты Дж. Россером и А. Тюркеттом [Rosser and Turquette 1945, 1950]. Наконец ими был разработан метод аксиоматизации [Rosser and Turquette 1952], который включает в себя в качестве исходного условия общезначимость законов транзитивности, перестановки и утверждения консеквента (см. выше гл. 1). Кроме этого здесь впервые было указано на обязательное наличие в аксиоматизируе­мой логике

Ji-операторов. Все эти условия выполняют, например, конечнозначные логики Лукасевича Этот метод применим так­же для произвольного числа выделенных значений и распространя­ется на предикатные многозначные логики. Однако, как и преды­дущий метод, он оказался весьма общим и громоздким в применении.

Только в начале 70-х годов XX ст. появились сразу две аксиоматиза­ции После того как было дано алгебраическое доказательство полноты для бесконечнозначной логики Лукасевича появилась возможность распространить этот метод на n-значный случай, что и было сделано Р. Григолия (см. [Григолия 1973] и [Grigolia 1977]). Аксиоматизация предложенная Григолия, основана на том, что к четырем аксиомам для бесконечнозначной логики Лукасевича добавляются характеристические аксиомы для каждого п. Выгля­дит это следующим образом: