Тема 5. -значная логика

-значная логика

Обобщением двузначных логик являются конечнозначные логики. Необходимо обратить внимание на два обстоятельства:

1)  в -значных логиках сохраняются многие свойства и результаты, которые имели место в двузначной логике;

2)  в -значных логиках наблюдаются явления, обнаруживающие принципиальное их отличие от алгебры логики.

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

Зададим функцию в виде таблицы 1.

Таблица 1

………………

………………

, где - символ обозначающий отображение. Определим функцию от двух переменных в троичной системе исчисления (таблица 2). Т. е. . .

Таблица 2

0

0

0

0

0

1

0

1

1

0

2

0

2

2

0

3

1

0

1

0

4

1

1

1

1

5

1

2

2

1

6

2

0

2

0

7

2

1

2

1

8

2

2

2

2

Например, ; ; .

Обозначим через множество всех функций -значной логики над алфавитом , а также констант . Так как число наборов значений переменных равно , то имеем следующий результат.

Теорема. Число всех функций из множества , зависящих от переменных , равно (например, если ).

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

Рассмотрим примеры некоторых конкретных функций из множества , которые можно считать "элементарными" функциями.

НЕ нашли? Не то? Что вы ищете?

1.  (). Здесь представляет обобщение отрицания в смысле "циклического" сдвига значений (таблица 4).

2.  . Здесь или, как часто обозначают, является другим обобщением отрицания в смысле "зеркального" отображения значений (носит название отрицания Лукашевича) (таблица 4).

Пример 1. Пусть (таблица 4).

Таблица 4

0

1

2

0

2

1

2

1

1

0

2

0

0

2

1

Пример 2. Пусть (таблица 5).

Таблица 5

[P1] ~

~(~)

0

1

3

0

2

1

2

2

1

3

2

3

1

2

0

3

0

0

3

1

3.  - обобщение конъюнкции (таблица 2).

- второе обобщение конъюнкции.

4.  - обобщение дизъюнкции (таблица 2).

5.  Функция Вебба

является полной в конечнозначной логике (таблица 6).

Таблица 6

0

0

1

0

1

2

0

2

0

1

0

2

1

1

2

1

2

0

2

0

0

2

1

0

2

2

0

6)  - обобщение суммы по модулю

Примеры

1) 

2)  ;

3)  ;

4)  ~(~~).

Минимизация логических функций конечнозначных логик

При минимизации логических функций конечнозначных логик используют результаты двузначной логики – теорию ДНФ булевых функций. Введем булеву переменную равную 1 при и 0 в противном случае, Будем называть -й фазой переменной , :

.

Пример. Осуществить минимизацию трехзначной функции Вебба, заданной таблицей 1.

Таблица 1

0

0

1

0

1

2

0

2

0

1

0

2

1

1

2

1

2

0

2

0

0

2

1

0

2

2

0

Возьмем наборы, на которых значения и найдем минимальную ДНФ для 0-ой фазы функции.

Каждая конъюнкция соответствует максимальному интервалу – ребру.

1 этап – склеивание ярусов (рис. 1).

2 этап – таблица Квайна (таблица 2).

Таблица 2

максимальный

интервал

Интервалы

0 2

1 2

2 0

2 1

2 2

2-

0

0

1

1

1

-2

1

1

0

0

1

Минимальная ДНФ =.

Имеем одно покрытие которому соответствует минимальная ДНФ нулевой фазы трехзначной функции Вебба:

Аналогично получаем минимальные формы для 1-ой и 2-ой фаз функции .

1 этап – склеивание ярусов (рис. 2).

2 этап – таблица Квайна (таблица 3).

Таблица 3

максимальный

интервал

Интервалы

0 1

1 0

1 1

- 1

1

0

1

1 -

0

1

1

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

 [P1]