Основные понятия. Элементарные функции k-значной логики и их свойства

Функции k-значной логики.

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

Часть 2

Свойства элементарных функций.

Основные формулы функции алгебры логики

1. - нуль функция; 2. - единичная функция;

3. { ; 4. - тождественная функция;

5. 6.

7. 8.

9. 10.

11. 12.

1. 2.

3. 4. принципы de Моргана 5.

6.

Законы поглощения: Операция удаления элементарной конъюнкции:

1. Операции удаления множителя: 1.

2. 2.

3. 3.

4. - двойственная функция

Опр.1. Пусть E_k={0,1,…,k-1}. Функция называется функцией k-значной логики, если на каждом наборе , где значение функции также принадлежит множеству . Совокупность всех функций k-значной логики обозначается .

Способы задания функций k-значной логики

1. Описание (элементов k штук, т.е. 0,1,2,3,…,k-1)
2. Табличный

Переменных n штук.

Тогда в таблице переменных.

- размещения из k элементов по n.

Количество функций будет

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

Пример.

1) k=2 P₂(n) = .

2) k=3 P₃(n) = ; ,

При n=2 количество функций 19683, т.е. множество P₃(2) практически необозримо.

В P_k часто вместо табличного задания функций употребляют задание при помощи алгоритма вычислимости функций.

2. Элементарные функции в P_k

Дата добавления: 2014-12-27