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

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

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

Пример. Рассмотрим функцию k-значной логики при k = 3 и n = 2, значение функции определяется максимальным аргументом.

Таблица 1.14
		f
0	0	0
0	1	1
0	2	2
1	0	1
1	1	1
1	2	2
2	0	2
2	1	2
2	2	2

1.10. Контрольные вопросы к главе 1

1. Дайте определение булевой функции.

2. Определите табличное задание булевой функции.

3. Сколько всего булевых функций от n переменных?

4. Какие функции называются элементарными?

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

6. Дайте определение существенных и фиктивных переменных.

7. Какие булевы функции являются равными?

8. Дайте определение булевой формулы.

9. Какие формулы называются эквивалентными?

10. Сформулируйте основные тождества алгебры логики.

11. Какие функции называются двойственными?

12. Приведите основные способы получения двойственных функций.

13. Сформулируйте теорему о двойственной функции.

14. Дайте определение полной системы булевых функций.

15. Приведите примеры полных систем булевых функций.

16. Сформулируйте теорему о полных системах.

17. Дайте определение замыкания.

18. Сформулируйте основные свойства замыканий.

19. Какие замкнутые классы вы знаете?

20. Определите замкнутые классы , и их свойства.

21. Определите замкнутый класс самодвойственных функций и его свойства.

22. Сформулируйте лемму о несамодвойственной функции.

23. Определите замкнутый класс монотонных функций и его свойства.

24. Сформулируйте лемму о немонотонной функции.

25. Дайте определение полинома Жегалкина.

26. Сформулируйте теорему о единственности полинома Жегалкина.

27. Какие функции называются линейными?

28. Сформулируйте лемму о нелинейной функции.

29. Сформулируйте теорему о необходимых и достаточных условиях полноты систем булевых функций.

30. Сформулируйте теорему о числе функций полных систем.

31. Дайте определение функции k-значной логики.

Глава 2. Минимизация днф

2.1. Введение

Известно, что функция булевой алгебры (алгебры логики) может быть представлена множеством формул, даже если для их построения используются только элементарные функции. Среди формул особый интерес представляют дизъюнктивные нормальные формы, построенные без применения скобок на подмножестве элементарных функций: {, , }. Интерес к этим формулам объясняется, с одной стороны, простотой их вида, а с другой – возможностью для разработчика аппаратуры задавать в виде ДНФ поведение проектируемых устройств.

Функция , где = {0, 1}, называется функцией алгебры логики или булевой функцией.

Для отдельной функции в общем случае можно построить несколько ДНФ, отличающихся числом символов, образующих формулу. Под символом будем понимать переменную и ее знак инверсии. Переменную вместе со знаком инверсии часто называют буквой или литерой.

Введенная ранее совершенная дизъюнктивная нормальная форма, как правило, не является компактной формулой по сравнению с другими ДНФ, представляющими эту же функцию.

Например, мажоритарная функция, значения которой определяются значениями большинства ее аргументов, представляется следующей совершенной ДНФ:

   .

В то же время она может быть представлена в виде ДНФ:

  .

Вторая формула содержит 6 символов переменных, а первая – 12.

При решении различных задач проектирования дискретных систем важно получать для булевых функций по возможности более компактные их представления в виде ДНФ. Теория ДНФ позволяет это делать.

Для выяснения главной проблемы теории ДНФ введем ряд определений.

Определение. Элементарной конъюнкцией называется логическое произведение K = r переменных, в котором все различны. Число r называется рангом конъюнкции. При r = 0 конъюнкция полагается равной единице.

Определение. Дизъюнктивной нормальной формой называется дизъюнкция D = … элементарных конъюнкций , в которой все различны, j = 1,…, n. Число l называется длиной ДНФ. Для l = 0 ДНФ называется пустой и полагается равной 0.

Определение. Минимальной ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число символов переменных по сравнению со всеми другими ДНФ, реализующими эту функцию.

Определение. Кратчайшей ДНФ функции f( ,…, ) называется ДНФ, реализующая f и содержащая наименьшее число элементарных конъюнкций по сравнению со всеми другими ДНФ, реализующими эту функцию.

Главной проблемой теории ДНФ является проблема построения минимальных и кратчайших ДНФ для булевых функций.

Существует тривиальный алгоритм построения минимальной (кратчайшей) ДНФ для произвольной булевой функции.

Все ДНФ, составленные из символов переменных ,…, , ,…, , упорядочиваются по числу символов переменных (числу конъюнкций), и для каждой ДНФ проверяется соотношение D = f( ,…, ).

Первая по порядку ДНФ, для которой это соотношение выполняется, есть минимальная (кратчайшая) ДНФ для функции f( ,…, ).

Этот алгоритм не применим на практике, так как уже для небольших значений n требует перебора огромного числа ДНФ.

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

Доказательство. Число различных элементарных конъюнкций, составленных из n переменных, равно . Действительно, каждая из n переменных либо не входит в конъюнкцию, либо входит в нее с отрицанием, либо входит в нее без отрицания. Это значит, что всевозможных конъюнкций . В конкретную ДНФ каждая из конъюнкций либо входит, либо нет. Это значит, что число различных ДНФ функций, зависящих от n переменных, равно числу подмножеств множества из элементов: . Ч.Т.Д.

Из теоремы 2.1 следует, что число различных ДНФ от n переменных существенно больше числа ( ) функций от n переменных.