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

приводит к классической двузначной логике С2.

Характерен случай с паранепротиворечивыми логиками и их. трехзначными вариантами, которые заведомо строились с целью фальсифицировать формулы

Как мы видели, паранепротиворечивая логика J3 (см. 3.5.3) асиоматизирована как расширение С2. Поскольку в изложенном методе аксиоматизации каждая конечнозначная логика Ln есть рас­ширение С2, то все эти формулы уже содержатся в исходных ак­сиомах (или выводимы из них). Более того, если Ln не является итинностно-полной С-расширяющей логикой, то это не значит, что она может быть аксиоматизируема только в виде квази-гильбертовского исчисления. Например, в логиках Гёделя Gn (см. 5.1.7) не выразимы J-операторы, т. е. эти логики не являются ис­тинностно-полными. Тем не менее, как отмечалось, они имеют простую гильбертовскую аксиоматизацию.

Также обратим внимание на явную связь истинностно-полных логик с наличием в них нормального изоморфа С2 (см. 3.3.1.1). Это как раз и позволяет представить аксиоматизацию истинностно-полных С-расширяющих логик как расширение С2. Таким образом, наличие изоморфа является достаточным основанием для С-аксиоматизации широкого класса конечнозначных логик. При этом заметим, что при построении изоморфа нет необходимости использовать все J-операторы. Это наводит на мысль расширить метод Аншакова-Рычкова на те конечнозначные логики, в которых не выразимы все J-операторы, но наличие изоморфа гарантируется.

Итак, по заданной конечной матрице можно построить если не гильбертово, то квази-гильбертово исчисление. Возникает следую­щий естественный вопрос: можно ли по каждой конечной матрице построить конечную гильбертову аксиоматизацию? Ответ отрица­телен. В качестве предположения это было высказано в [Аншаков и Рынков 1984]. В пользу такого ответа говорят следующие ре­зультаты.

В. Раутенберг [Rautenberg 1981] доказал, что содержание лю­бой двузначной матрицы, т. е. Е(2), конечно аксиоматизируемо, и в связи с этим спрашивает, имеет ли это место для любой конечной матрицы. П. Вуйтылак [Wojtylak 1984] опровергает возможность этого, сконструировав пятизначную матрицу с двумя выделенными значениями, которая не является конечно аксиоматизируемой. За­тем В. Дзёбяк [Dziobiak 1991] находит четырехзначную матрицу с одним выделенным значением с тем же самым свойством и ставит вопрос о существовании подобной матрицы среди трехзначных.

Наконец, К. Палашиньска [Patasinska 1992; 1994], представила две 3-значные матрицы с одним выделенным значением, в которых операция присоединения следствий не является конечно-аксиома­тизируемой. Одна из них имеет следующий вид:

гдепринимает всюду значение 2, кроме случая

7. Многозначная логика как функциональ­ная система

В силу прикладного характера многозначной пропозициональной логики главным становится не изучение многозначной логики как логического исчисления (класса аксиоматизируемых тавтологий) и не изучение свойств алгебраических тождеств, что все вместе пред­ставляет сугубо теоретический интерес, а изучение функциональ­ных свойств моделей логики высказываний.

7.1. Формульная модель п-значной логики

Модели многозначной логики строятся по аналогии с двузначной логикой, как это было видно на примере с х-значной логикой Лука-севичаТак, индивидуальные высказывания логики, разбитые на классы, с одним и тем же значением истинности, приводят к поня­тию множества Vn — константы модели, которые заменяют индиви­дуальные высказывания их соответствующими значениями истин­ности; переменные высказывания приводят к переменным величи­нам х1\, х2, ..., которые в качестве значений принимают элементы из множества Vn; логические связки приводят к множеству элементарных функций (операций). Напомним, что в п-значной ло­гике Лукасевича этими функциями являются отрицание ~ и им­пликация

7.1.1. Понятие функции п-значной логики. Элементарные функции

В моделях многозначной логики понятие функции является основ­ным и наряду с булевыми функциями (функциями двузначной ло­гики) используется для описания дискретных устройств, компонен­ты которых могут находиться в некотором числе различных состояний. Произвольная функция от любого конечного

числа переменных, областью определения которых и областью зна­чения самой функции является множество Vn (без ограничения общности можно считать, что его элементами являются 0, 1, 2, ..., п-1), называется п-значной функцией или функцией п-значной логи­ки. Таким образом, если - функция от т переменных, то f отображает множествово множество Vn, где m обозначает т-ную декартову степень множества В случае имеем дело с булевыми функциями. Имеются различные способы задания функций. Например, функция может быть задана таблицей, где в некотором порядке перечислены все n-ичные на­боры длины т (из элементов 0, 1, 2, ..., п-1) и на каждом из них ука­зано значение функции, как это делалось в двузначной логике.

Число n-ичных наборов длины т равно пт и на каждом из них значение функции можно задать п способами. Поэтому число функций

n-значной логики, зависящих от аргументов составляет Множество всех функций n-значной логики обозначим посредством Случай п > 2 оказывается существенно более

сложным, чем классический случай Р2. Уже в Р3 число функций от двух переменных равно 19 683, в то время как в P2 таких функций всего 16, Естетвенно в Рп возникают трудности как в возможности эффективного использования табличного задания функций, так и в возможности просмотра всех функций от т переменных. Поэтому вместо табличного задания функций часто употребляется задание при помощи алгоритма вычислимости функций. Например, тах(х1, -..., хт) можно рассматривать как алгоритм, который для любого набора значений переменных выдает их максимум.

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

1. Константы

2. Отрицание Лукасевича: - обобщение отрицания

в смысле «зеркального отрицания».

3. Отрицание Поста: - обобщение отри-

шания в смысле «циклического сдвига значений».

отрицания,

5. Функция min(x,y) - обобщение конъюнкции. Функция

min (х, у) обозначается также или.

6. Функция ху (mod n) - второе обобщение конъюнкции.

7. Функция тах(х, у) - обобщение дизъюнкции. Функция тах(х, у) обозначается также.

8. Функция - обобщение суммы по mod 2.

9. Импликация Лукасевича:

- обобщение

одного из свойств классической импликации.

10. Функция Вебба: —обобщение стрелки Пирса [Webb 1935; 1936].

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

аналогов, каждый из которых обобщает соответствующее свойство данной булевой функции.

Заметим, что не для всех обобщений булевых функций сохра­няются соответствующие классические свойства. Например,

7.1.2. Формулы как суперпозиция элементарных функций

Кроме двух рассмотренных способов задания функций не менее известным способом является формула, которая строится из эле­ментарных функций. Пусть F — некоторое непустое множество

п-значных функций. По индукции определим понятие формулы над F.

a) Базис индукции. Каждая функция из Fназы­вается формулой над F.