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-значной логики.