Задать вопрос юристу

2.2.3. Полные системы булевых функций

Определение. Система булевых функций f1,f2, …, fn называется полной, если любая булева функция может быть выражена через функции f1,f2, …, fn с помощью суперпозиций.

Пример 42.

Исходя из определения полной системы булевых функций, следует, что система {Ù, U, O} является полной, так как любая булева функция может быть представима в виде СДНФ и/либо СКНФ.

Дадим определение суперпозиции функций.

Определение. - конечная система булевых функций. Функция f называется суперпозицией ранга 1 (или элементарной суперпозицией) функций f1, f2, …, fm, если f может быть получена одним из следующих способов: переименованием некоторой переменной xj какой-нибудь функции fi, т. е. f=fi(x1, …, xj-1, y, xj+1, …, xk1), где y может совпасть с любой переменной; подстановкой некоторой функции fl (1£ l m) вместо какой-либо переменной xj любой из функций fiÎK0, т. е. f=fi(x1, …, xj-1, fl(x1, x2, …, xk1), xj+1, ..., xki).

Определение. Суперпозиции ранга 1 образуют класс функций К1. Класс функций, получающихся из функций класса Кr-1 суперпозиций ранга r-1 с помощью элементарных суперпозиций, называется классом функций Kr суперпозиций ранга r. Суперпозициями функций из К0 называются функции, входящие в какой-либо из классов Kr.

Определение. Класс (множество) К булевых функций называется функционально замкнутым, если вместе с функциями из этого класса он содержит и все их суперпозиции.

Пример 43.

1. Четыре булевы функции одной переменной (f1 = 00, f2 = 11, f3 = 01, f4 = 10) образуют замкнутый класс.

2. Булевы функции f1 = x и образуют замкнутый класс.

Теорема. Класс T0={f | f(0, 0, …, 0)=0} функций, сохраняющих константу ноль на нулевом наборе, замкнут относительно суперпозиций.

Теорема. Класс T1={ f | f(1, 1, …, 1)=1} функций, сохраняющих константу один на единичном наборе замкнут относительно суперпозиций.

<< | >>
Источник: Лекции - Дискретная математика. 2016

Еще по теме 2.2.3. Полные системы булевых функций:

  1. 1.9. Полные системы функций
  2. Булевы функции.
  3. Булевы переменные и функции
  4. 1.3.2. Булевы функции
  5. Полиномиальное разложение булевых функций
  6. Арифметическое разложение булевых функций
  7. 2.2.1. Представление булевой функции формулой логики высказываний
  8. Элементарные булевы функции. Равносильности
  9. §1.3. Реализация булевых функций формулами
  10. Разложение булевых функций в канонический полином Жегалкина