Понятие базиса

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

Базисов может быть много:

1. И, ИЛИ, НЕ 2. И, НЕ

3. И – НЕ 4. НЕ – И

5. ИЛИ, НЕ 6. ИЛИ – НЕ

7. НЕ – ИЛИ 8. “0”, ”1”, НЕ, n и другие.

Рисунок 1.15 – Некоторые базисы

Мажоритарный элемент ( n) имеет нечетное число входов и вырабатывает 1, если число единиц на входе больше чем нулей (правило голосования).

Базис называется избыточным, если исключение одной элементарной функции не приводит к потере функциональной полноты. В противном случае базис называется минимальным. Так, базисы 1, 8 – избыточные, а остальные – минимальные.

Используя законы алгебры логики, можно переходить от одного базиса к другому.

Например, пусть имеется элемент 3И-НЕ, а необходимо реализовать следующие операции:

1. НЕ

2. И (для 2-x переменных)

3. ИЛИ (для 2-x переменных)

Реализуем эти операции.

1. Операция НЕ получается на основании закона тавтологии (рис.1.16)

Рисунок 1.16 – Инвертор на элементе Шеффера

2. Операция И получается на основании законов тавтологии и двойного отрицания (рис. 1.17)

Рисунок 1.17 – Конъюнктор на элементах Шеффера

3. Операция ИЛИ получается на основании правила двойственности . Тогда получаем следующую реализацию (рис. 1.18):

Рисунок 1.18 –Дизъюнктор на элементах Шеффера