Функционально полные базисы.

В предыдущих разделах рассматривались возможности представления переключательных функций и эквивалентных преобразований формул, записанных с помощью операций конъюнкции, дизъюнкции и отрицания. Однако такой способ аналитического представления переключательных функций не является единственным. Современные технологии позволяют строить логические схемы из элементов, выполняющих операции, отличные от конъюнкции, дизъюнкции и отрицания. Естественно сформулировать следующую задачу: с помощью каких операций можно представить любую переключательную функцию и какими свойствами должны обладать операции, допускающие такое представление.

Приведенные формулы позволяют сформулировать следующие утверждения:

1. Каждая булева функция от n переменных, отличная от константы 0, имеет единственную СДНФ.

2. Каждая булева функция от п переменных, отличная от константы 1, имеет единственную СКНФ.

Эти утверждения называются теоремой о функциональной полноте.

Прежде чем приступить к решению поставленной задачи, необходимо уточнить два вопроса:

1. каким образом должно строиться представление произвольной переключательной функции с помощью некоторого подмножества операций?

2. как следует подходить к выбору операций, включаемых в это подмножество?

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

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

· выражение f(x₁,...,x_n), где f ∈ В, есть формула над В;

если f(x₁,...,x_m) - базисная функция, а выражения F₁,...,F_m являются символами переменных либо формулами, то суперпозиция f(F₁,...,F_m) также есть формула над В.

Определение: Принцип подстановки заключается в следующем: если a = b, то в любой формуле, содержащей a, вместо а можно подставить b, и в результате будет получена эквивалентная формула.

Ответ на второй вопрос заключается в том, что в базис B целесообразно включать "простейшие" операции (функции), зависящие по возможности от меньшего числа аргументов. Такими функциями, очевидно, являются функции одной и двух переменных.

УПРАЖНЕНИЕ 8.3.1

1. Сколько нужно сделать операций склеивания, чтобы получить конъюнкцию ранга 3 из конъюнкций ранга 7?

2. Проверьте, является ли совокупность кодов {0z01, z111, 1z10} покрытием функции f(x₁, x₂, x₃, x₄) = { 1,5,7,10,14,15}?

3. Может ли ранг СкДНФ совпадать с рангом МДНФ?

УПРАЖНЕНИЕ 8.3.2

1. Постройте гиперкуб для 4 переменных, соединяя ребрами одноименные вершины двух трехмерных кубов.

2. Выделите вершины построенного гиперкуба, определяющие функцию f₁(x₁, x₂, x₃, x₄) = {0,1,5,7,8,10,12,14,15}, а затем все грани размерности 3 и 2.

УПРАЖНЕНИЕ 8.3.3

Найдите с помощью табличного метода множество минималей для следующих функций:

· f₁(x₁, x₂, x₃, x₄) из упражнения 3.2 (п.2);

· f₂(x₁, x₂, x₃, x₄, x₅) = {1,5,10,14,17,19,21,23,26,27,30,31};

· f₃(x₁, x₂, x₃, x₄, x₅) = {0,1,4,5,9,10,11,16,18,24,25,26,27}.

УПРАЖНЕНИЕ 8.3.4

Построить, используя алгоритм последовательного извлечения экстремалей, минимальные покрытия для следующих функций из упражнения 3.3:

· f₁(x₁, x₂, x₃, x₄);

· f₂(x₁, x₂, x₃, x₄, x₅);

· f₃(x₁, x₂, x₃, x₄, x₅),

· используя построенные ранее СкДНФ.

УПРАЖНЕНИЕ 8.3.5

Постройте неизбыточные покрытия, применяя способ ветвления для следущих функций:

· f₄(x₁, x₂, x₃, x₄)= { 0,1,5,7,8,10,14,15};

· f₅(x₁, x₂, x₃, x₄, x₅) =

· = {0,1,2,3,4,5,6,7,12,13,14,15,16,17,18,19,24,25,26,27,28,29,30,31};

· f₆(x₁, x₂, x₃, x₄, x₅) = {8,10,11,12,13,14,15,24,25,26,27,28,29,31},

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

УПРАЖНЕНИЕ 8.3.6

Используя карты Карно, найдите МДНФ функций:

· f₄(x₁, x₂, x₃, x₄) = { 0,1,5,7,8,10,14,15};

· f₅(x₁, x₂, x₃, x₄, x₅) = {0,1,2,3,4,5,6,7,12,13,14,15,16,17,18,19,24,25,26,27,28,29,30,31};

· f₆(x₁, x₂, x₃, x₄, x₅) = {8,10,11,12,13,14,15,24,25,26,27,28,29,31},
а затем сравните полученные результаты с результатами упражнения 8.3.5.

Дата добавления: 2015-07-07