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

Матричные операции определяются так:

Отрицание Поста называется циклическим отрицанием.

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

Самое главное свойство многозначных логик Поста Рn заключа­ется в том, что они функционально полны, т. е. любая функция п-значной логики в них определимы. С функционально полными ло­гиками мы уже встречались: это n-значные логики Лукасевича с различными обобщениями функтора Слупецкого Т(x) (см. раздел 3.3.5). Как частный случай, имеем: В разделе 7.3.1 мы при-

ведем доказательство функциональной полноты Рn .

5.2.1.1. Трехзначная логика Поста Р3

Рассмотрим конкретный пример n-значной логики Поста, а именно Рз, где истинностные значения для удобства обозначим, как в трех­значной логике Лукасевичаи пусть выделенным значением будет 1. Тогда имеет истинностную таблицу точно такую же, как в но существенное отличие заключается в операции отри­цания:

Заметим, что в отличие от и G3 в Р3 (как и во всех Рn) есть операция (в данном случае циклическое отрицание которая на множестве классических истинностных значений {0, 1} принимает отличное от них значение, например, Поэтому можно указать формулу, которая является тавтологией в Р3, но не является тавтологией классической логики С2:

Отметим также, что не всякая тавтология С2 с исходными связ­ками отрицания и дизъюнкции является тавтологией Р3, например в Рз, как и в не имеет места закон исключенного третьего но зато имеет место закон исключенного четвертого:

И вообще, в Рn имеет место закон исключенного (n+1)-го.

5.2.2. Алгебры Поста

Алгебра есть алгебра Поста

порядка п, если есть п-значная алгебра

Лукасевича и есть п-2 элемента, удовлетворяющие сле-

дующему условию:

Или, по другому, алгебра

, есть алгебра Поста порядка п, еслиесть симметрическая алгебра Гейтинга и выполняются условия (LI) — (L6) и (Р).

По алгебрам Поста существует огромная литература. Это вы­звано еще и тем, что в силу их функциональной полноты они явля­ются наилучшими кандидатами на применение в компьютерных науках; по крайней мере, они могут реализовать любую переклю­чательную схему (выполнение одного из условий для практическо­го использования многозначной логики в [Lee and Ajabnoor 1978]).

Первая система аксиом для алгебры, соответствующей п-значной логике Поста, принадлежит П. Розенблуму [Rosenbloom 1942]. Она была упрощена Г. Эпштейном [Epstein I960] и Т. Трачыком [Traczyk 1962]. В первой работе было показано, что алгебра Поста есть дистрибутивная решетка с псевдодополнением и к тому же обладает симметричностью, т. е. была определена операция ~. В [Traczyk 1963] для алгебр Поста была доказана теорема типа стоуновского представления, а в [Traczyk 1964] впервые алгебры Поста были заданы как эквациональный класс, т. е. заданы тождествами. Здесь определение алгебры Поста дано в сигнатуре

где есть ограниченная дистрибутивная решетка с и операторы Di- определяются следующим образом:

Первым, кто обнаружил, что алгебры Поста суть также алгеб­ры Рейтинга, был Г. Руссо [Rousseau 1969; 1970J. Здесь определе­ние алгебры Поста дано в сигнатуре

где есть алгебра Рейтинга и для лю-

бых х, у выполняются следующие равенства:

Заметим, что класс всех алгебр Поста любого порядка яв-

ляется эквационально определимым, поскольку класс всех алгебр Рейтинга является эквационально определимым (см. 4.4.2).

В [Rasiowa 1974] доказывается эквивалентность опре­делений алгебр Поста, данная Т. Трачыком и Г. Руссо. Отсюда сле­дует еще одно определение данное Е. Расёвой. Здесь же развита теория алгебр Поста.

5.2.3. Аксиоматизация логик Рn

уссо позволил ему дать аксиоматизацию n-значного пропозиционального исчисления Поста Рn на основе интуицио­нистской импликации и других связок. Эти идеи были развиты Е. Расёвой [Rasiowa 1974], где подробно рассматривается взаимоотношение между алгебрами Поста порядка п и n-значной пропозициональной логикой Поста Рn. Аксиоматизация Рn дается в сигнатуре: где есть в точности пропозициональные связки логики Гёделя Qn; - пропозициональные константы; - одноместные связки, определяемые следующим обра­зом:

Связка эквивалентности вводится по определению:

Тогда аксиоматизация Рn выглядит следующим образом:

(Р0) аксиомы пропозиционального интуиционистского исчис­ления

Int и

Правила вывода:

Первопорядковые исчисления, основанные на этих пропози­циональных исчислениях, изучались Е. Расёвой.

Имеется ряд работ, где логики Рn строятся в виде секвенциональных исчислений тенценовского типа.

Заметим, что n-значные логики Поста Рn к тому же являются исторически первыми матричными логиками с произвольным, кроме 0, числом (конечным) выделенных значений. Аксиоматиза­ция таких логик впервые появилась в [Bole andBorowik 1992].

Как и для любой многозначной логики возникает сложная про­блема интерпретации истинностных значений, степень истинности которых пронумерована натуральными числами. Этот вопрос мы рассмотрим разделе 10.6.

5.3. Другие конечнозначные логики

Обобщения трехзначной логики Бочвара В3 на n-значный случай, притом совершенно разные, т. е. с разными классами тавтологий, имеются у Н. Решера [Rescher 1969] со связками и в [Бочвар и Финн 1972] со связками Рассмотрим определение последних, поскольку логика Вn именно с этими связками была аксиоматизирована в [Григолия и Финн 1979] и построена ее алгебра с доказательством теоремы представления.

Логическая матрица определяется следующим образом:

Ji есть операторы Россера-Тюркетта,

Заметим, что алгебры для Вп являются не многообразием, а только квазимногообразием [Мальцев 1970]. Теорема пред­ставления для этих алгебр доказана в виде подпрямого произве­дения определенного вида