Рис. 7.7. Реализация минимизированной системы функций логической схемой

8. ФУНКЦИОНАЛЬНО ПОЛНЫЕ СИСТЕМЫ ЭЛЕМЕНТАРНЫХ ЛОГИЧЕСКИХ ФУНКЦИЙ

Любую логическую функцию в алгебре логики можно представить в виде СДНФ и СКНФ, используя триэлемента р- ные логические функции: инверсию, конъюнкцию и дизъюнкцию. Данный набор представляет собой полный функциональный набор.

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

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

ментным базисом.

Минимальным базисом называется такой базис из f1, f2, …, fn, для которого удаление хотя бы одной из функций fi, вхо-

110

дящих в этот базис, превращает систему функций f1, f2, …, fm в неполную.

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

Функциональной полнотой обладают следующие элементные базисы:

1.И, ИЛИ, НЕ (основной базис);

2.И, НЕ;

3.ИЛИ, НЕ;

4.И-НЕ;

5.ИЛИ-НЕ;

6.1, И, .

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

Требовалось доказать, что если с помощью элементарных функций f1, f2, …, fn могли быть реализованы логические функции основного базиса (И, ИЛИ, НЕ), то в этом случае система функций f1, f2, …, fn считалась полной. Суть этого доказательства рассмотрим на примере логического базиса, состоящего из элемента И-НЕ.

1. Докажем, что с помощью элемента И-НЕ может быть реализована операция НЕ.

Дано y = a b ; пусть a=b, следовательно y = a a = a - реализована операция НЕ.

a & a

111

2. Докажем, что с помощью элемента И-НЕ может быть реализована операция И.

Дано y = a b ; рассмотрим функцию z = y = a b = a b - реализована операция И.

b

3. Докажем, что с помощью элемента И-НЕ может быть реализована операция ИЛИ.

Необходимо получить операцию ИЛИ - y = a + b .

Рассмотрим функцию z = y = a +b = a b - реализована операция ИЛИ.

b &

Следовательно, базис И-НЕ является полным.

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

1. Свойство сохранения нуля: данным свойством обл а-

дают те логические функции, для которых справедливо соотношение: f (0,0,...,0) = 0 , т.е. на нулевом наборе аргументов,

логическая функция принимает нулевые значения.

112

2. Свойство сохранения единицы: данным свойством обладают те логические функции, для которых справедливо соотношение: f (1,1,...,1) =1, т.е. на единичном наборе аргумен-

тов, логическая функция принимает единичные значения.

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

соотношение: f (x1 , x2 ,..., xn ) = f (x1 , x2 ,..., xn ), т.е. самодвойственной является функция, у которой инвертирование значений всех аргументов приводит к инвертированию значений функции.

4.Свойство монотонности: функция обладает этим свойством, если для любой последовательности наборов, в каждом из которых аргументы не убывают, значения функции также не убывают, при этом полагаем, что 0<1.

5.Свойство линейности: данным свойством обладают

те логические функции, которые могут быть представлены в следующем виде:

f (x1, x2 ,..., xn ) = a0 a1x1 a2 x2 .... an xn , где ai {0,1}.

Продолжение табл. 8.1

В табл. 8.1 приведены элементарные логические функции одного и двух аргументов: таблицы истинности, представление в виде ДНФ или КНФ, названия наиболее используемых логических функций.

Рассмотрим наличие и отсутствие перечисленных выше пяти свойств у элементарных логических функций из таблицы 8.1. Результаты исследований занесем в таблицу 8 .2. Если функция обладает исследуемым свойством, то в соответствующей ячейке поставим “x”.

114

Таблица 8.2

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

Более подробно рассмотрим, как определяется наличие или отсутствие у логических функций четвертого свойства – свойства монотонности.

Из неубывающих значений аргументов логических функций строятся неубывающие наборы, состоящие из значений аргументов. Рассмотрим значения x1, x2 в таблице 8.2. Как видно из таблицы аргумент x1 не убывает, а аргумент x2 убывает. Для того, чтобы аргумент x2 не убывал, необходимо составлять наборы значений аргументов либо из 1,3,4 строк, либо из 1,2,4 строк таблицы 8.2.

115

Выпишем эти наборы значений:

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

Для наглядности рассмотрим значения функции F5 из табл. 8.2:

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

Далее рассмотрим, как определяется наличие или отсутствие у логических функций пятого свойства – свойства линейности.

Логические функции обладают свойством линейности, если они могут быть представлены в следующем виде:

где ai {0,1}, i =0, n

116

Поскольку исследуемые нами логические функции зависят максимум от двух аргументов, то выражение (8.1) примет вид полинома Жегалкина (8.2):