Понятие базиса.
Цифровые устройства и микропроцессоры
Базис называется избыточным, если исключение одной элементарной функции не приводит к потере функциональной полноты. В противном случае базис называется минимальным. Так, базисы 1,8 — избыточные, а остальные — минимальные. С помощью ограниченного набора элементарных функций можно представить любую, сколь угодно сложную функцию алгебры логики. Такой набор элементарных функций называют базисом, или… Читать ещё >
Понятие базиса. Цифровые устройства и микропроцессоры (реферат, курсовая, диплом, контрольная)
С помощью ограниченного набора элементарных функций можно представить любую, сколь угодно сложную функцию алгебры логики. Такой набор элементарных функций называют базисом, или функционально полным набором.
Базисов может быть много (рис. 1.9):
- 1) И, ИЛИ, НЕ;
- 2) И, НЕ;
- 3) И-НЕ;
- 4) НЕ-И;
- 5) ИЛИ, НЕ;
- 6) ИЛИ-НЕ;
- 7) НЕ-ИЛИ;
- 8) «О», «1», НЕ, >п и др.
Рис. 1.9. Некоторые базисы
Мажоритарный элемент (> п) имеет нечетное число входов и вырабатывает единицу, если число единиц на входе больше чем нулей (правило голосования).
Базис называется избыточным, если исключение одной элементарной функции не приводит к потере функциональной полноты. В противном случае базис называется минимальным. Так, базисы 1,8 — избыточные, а остальные — минимальные.
Используя законы алгебры логики, можно переходить от одного базиса к другому.
Например, пусть имеется элемент ЗИ-НЕ, а необходимо реализовать следующие операции:
- 1) НЕ;
- 2) И (для двух переменных);
- 3) ИЛИ (для двух переменных).
Реализуем эти операции.
1. Операция НЕ получается на основании закона тавтологии (рис. 1.10).
Рис. 1.10. Инвертор на элементе Шеффера
2. Операция И получается на основании законов тавтологии и двойного отрицания (рис. 1.11).
Рис. 1.11. Конъюнктор на элементах Шеффера
3. Операция ИЛИ получается на основании правила двойственности a + b = a + b = ab. Тогда получаем реализацию, показанную на рис. 1.12.
Рис. 1.12. Дизъюнктор на элементах Шеффера