Почвоведение

Базисы могут быть избыточными (базис 1) и минимальными (базисы 4 и 5). Базис является минимальным, если удаление хотя бы одной функции превращает систему функций алгебры логики в неполную.

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

И 0,0,0,0,

И 0,1,0,0,1,1;

И 1,0,0,1.

И 0,0,1;

И 1,0;

Для функций двух аргументов монотонными являются следующие функции (см. табл. 8.9):

Класс самодвойственных функций .

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

Два набора называются противоположными, если все значения аргументов одного набора противоположны значениям аргументов другого набора. Например:

т.е. для того, чтобы получить противоположный набор, достаточно заменить в данном наборе нули единицами, а единицы - нулями.

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

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

Функции (функция Пирса) и /м(х1,х₂) (функция Шеффера) не принадлежат ни одному из указанных классов.

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

- не сохраняющую нуль,

- не сохраняющую единицу,

- не являющуюся линейной,

- не являющуюся монотонной,

- не являющуюся самодвойственной.

К базису относится система функций:

«И», «ИЛИ», «НЕ» (базис 1);

«И», «НЕ» (базис 2),

«ИЛИ», «НЕ» (базис 3),

состоящих из функции Шеффера («И-НЕ») (базис 4);

состоящих из функции Пирса «ИЛИ-НЕ» (базис 5).

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

Функционально полными будут пять систем элементарных функций, пять базисов, приведенных в таблице 8.15.

Таблица 8.15.

Функционально полные системы элементарных логических функций (базисы)

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

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

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