- •Ф.К. Алиев, и.А. Юров
- •Введение
- •Основные способы задания двоичных функций
- •1.1. Табличный способ задания
- •1.2. Геометрический способ задания
- •1.3. Задание двоичных функций формулами
- •Основные способы задания двоичных функций (продолжение)
- •2.1. Нормальные формы двоичных функций
- •2.2. Многочлен Жегалкина и действительный многочлен двоичной функции
- •2.3. Теорема о разложении в ряд Фурье
- •Полнота и замкнутость. Критерий полноты системы. Функционально полные системы. Замкнутые классы булевых функций
- •3.1. Полнота и замкнутость. Функционально полные системы
- •3.2. Замкнутые классы булевых функций
- •3.3. Критерий полноты системы булевых функций
- •4.1. Псевдобулевы функции
- •4.2. Функции k-значной логики
- •5.1 Минимизация двоичных функции
- •5.2. Геометрическая интерпретация минимизации днф
- •6.1. Метод Квайна — Мак-Класки нахождения сокращённой днф двоичной функции
- •6.2. Метод нахождения тупиковых днф
- •6.3. Метод Петрика нахождения тупиковых днф
- •Алгебраические системы
- •7.1. Алгебраические системы. Булевы алгебры
- •7.2. Изоморфизм алгебраических систем
- •Алгебры высказываний. Предикаты и операции над ними
- •8.1. Основные логические операции и их свойства
- •8.2. Предикаты и операции над ними
- •Исчисление предикатов
- •9.1. Общее понятие о логическом исчислении
- •9.2. Формулы алгебры предикатов
- •9.3. Равносильность формул. Основные отношения равносильности
- •9.4. Использование равносильностей для упрощения формул
- •9.5. Построение исчисления предикатов
- •9.6. Выводимость и доказуемость формул
- •9.7. Семантика исчисления предикатов
- •Понятие о теории моделей
- •Элементы теории алгоритмов
- •11.1. Основные требования к алгоритмам
- •11.2. Машина Тьюринга и функции, вычислимые по Тьюрингу
- •11.3. Машины произвольного доступа и вычислимые функции
- •Частично рекурсивные функции и их вычислимость
- •Вычислимость суперпозиции
- •Вычислимость рекурсии
- •Вычислимость минимизации
- •Нумерация наборов чисел и слов
- •Нормальные алгоритмы
- •Нумерация алгоритмов
- •1. Нумерация машин Тьюринга
- •2. Нумерация мпд-программ
- •Универсальные функции
- •Алгоритмически неразрешимые проблемы
- •16.1. Алгоритмически неразрешимые проблемы
- •16.2. Примечательные алгоритмически неразрешимые проблемы
- •Характеристики сложности вычислений
- •Характеристика сложности вычислительных задач
- •18.1. Классы сложности p и np и их взаимосвязь
- •18.3. Основные np-полные задачи. Сильная np-полнота
- •Список Литературы
4.2. Функции k-значной логики
Пусть , где.
Определение 4.7. Функцией k-значной логики, или k-значной функцией, от переменных при называется произвольное отображение,k-значными функциями от 0 переменных называются функции-константы 0, 1, …, k – 1.
Обозначим через имножества всехk-значных функций и k-значных функций от переменных.
При изучении k-значных функций используются многие из терминов и обозначений, введенных при изучении булевых функций. В частности, аналогичным образом определяются равенство функций, существенные и несущественные переменные, функции от переменных, тождественно равны константам 0, 1, …,k – 1, подфункции и т.д.
Так как множество конечно, тоk-значную функцию от переменных можно задать таблицей её значений на всех наборах (или векторах) из. При этом условимся записывать их в порядке возрастания как числа в конечной системе исчисления. Непосредственно из табличного значения видно, что различныхk-значных функций равно . Притабличное заданиеk-значных функций практически еще более трудно осуществимо.
В связи с этим важным вопросом является вопрос о разработке аналитических способов k-значных функций.
Множество можно рассматривать как кольцо вычетовпо модулю, и потому можно считать определенными наоперации сложения и умножения по модулю. Будем обозначать эти операции притеми же значками, что и операции над числами. Используя эти операции и функции-константы можно построить кольцо многочленовот переменных. Каждый многочлен из этого кольца представляетk-значную функцию от переменных. При простом, когдаесть поле, многочленами представляются всеk-значные функции. При составном — это не так.
Используя операции сложения и умножения, а также элементарные функции
можно получить представление k-значной функции, сходное с совершенной дизъюнктивной нормальной формой для случая :
. (4.4)
Другими, часто используемыми операциями на являются аналоги дизъюнкции, конъюнкции и отрицания:
Для k-значных функций, как и в двоичном случае, можно ввести понятия операции, представления функций формулами над заданной системой функций, замыкания, замкнутой и полной системы функций и.т.д. Приведем примеры полных систем k-значных функций.
1. Из представления (4.4) следует, что полной является система функций .
2. Так как в разложении (4.4) операцию сложения можно заменить на дизъюнкцию (выбор максимума), то полной является также система функций .
3. Наряду с разложением (4.4) имеет место еще один аналог совершенной дизъюнктивной нормальной формы функции , гдеIa(x) = 1 как только x = a, и в остальных случаях равна 0. Отсюда следует, что полной является система функций .
4. Система функций является полной системой функций.
Доказательство. С помощью суперпозиции из функции легко получить функции. Из них получим константу, а поэтому все функции константы. Теперь нетрудно получить функции:
.
Как следует из примера 3, остается построить функцию , т.е.Для этого сначала построим функции
Теперь из них можно получить функции
и .
5. Аналогично функции Шеффера в k-значной логике является функция Вебба , которая одна образует систему, т.е. системаявляется полной.
Доказательство. Используя , приимеем. Далее получаем:
А так как
Отсюда имеем, что — полная система функций.
Утверждение 4.8. Все k-значные функции представляются многочленами над в том и только том случае, когдаk — простое число, т.е. поле (без доказательства).
Утверждение 4.9. (Критерий полноты — критерий Слупецкого). Пусть система k-значных функций K содержит все функции одной переменной, причем . Тогда для полноты системыК необходимо и достаточно, чтобы К содержала функцию, существенно зависящую по меньшей мере от двух переменных и принимающую все значений из.
Л е к ц и я 5