раздел 6. 6. реализация булевых функций в различных базисах анализ комбинационных схем Функционально полные системы бф
 Скачать 1.54 Mb.
| Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей |
| 6. реализация булевых функций в различных базисах. анализ комбинационных схем 6.1. Функционально полные системы БФ Систему БФ {f1, f2, …, fn} называют полной, если любая БФ может быть выражена суперпозицией функций f1, f2,…, fn и булевых переменных. Функции, полученные применением суперпозиции, отличаются от исходных функций, и их свойства отличаются от свойств исходных функций. Среди БФ есть такие, которые обладают основными свойствами. Доказано, что число функций в полной системе не превышает четырех. 6.2. Понятие базиса Базисом называют полную систему функций алгебры логики, с помощью которых любую БФ можно представить как суперпозицию функций базиса. Минимальный базис состоит из такого набора функций, что исключение любой из них превращает этот набор в неполную систему функций. Известны и широко применяются несколько базисов, состоящих из элементарных функций. Базис, который называют основным, включает три функции – И, ИЛИ, Не.
Чтобы представить эту функцию в базисе И, Не, необходимо в исходной функции заменить операцию логического сложения на операцию логического умножения. Выполнить эти преобразования можно с использованием теоремы де Моргана:  . Рис. 6.1. Реализация БФ в базисе И, Не После такого преобразования функция реализуется только с помощью операции конъюнкции и инверсии. Схема, реализующая эту функцию, представлена на рис. 6.1 и содержит только элементы И и Не, входящие в базис.
 Таким образом, в окончательной формуле присутствуют только операции ИЛИ и Не. Схема, реализующая эту БФ, приведена на рис. 6.2.  Рис. 6.2. Реализация БФ в базисе ИЛИ, Не
 .Таким образом, в окончательной формуле присутствуют только операции И-Не. Схема, реализующая эту БФ, приведена на рис. 6.3.  Рис. 6.3. Реализация БФ в базисе И-Не
 Схема, реализующая эту БФ, приведена на рис. 6.4.  Рис. 6.4. Реализация БФ в базисе ИЛИ-Не Рассмотрим особенности базисов И-Не и ИЛИ-Не. Элемент И-Не описывается функцией  . Таблица истинности этой функции приведена в табл. 6.1.Таблица 6.1 Таблица истинности функции И-Не  Если на оба входа элемента И-Не подать одну и ту же переменную (первая и четвертая строки таблицы), то в результате получается функция:  , т. е. элемент И-Не становится инвертором (рис. 6.5, а). При последовательном соединении двух элементов И-Не, как показано на рис. 6.5 (б), схема выполняет функцию И. Таким образом, базис И-Не содержит как бы три элемента – И-Не, И, Не. Рис. 6.5. Соединение элементов базиса И-Не: а – инвертор (Не); б – элемент И Элемент ИЛИ-Не описывается функцией  . Таблица истинности этой функции приведена в табл. 6.2.Таблица 6.2 Таблица истинности функции ИЛИ-Не  Если на оба входа элемента ИЛИ-Не подать одну и ту же переменную, то получим функцию:  т. е. элемент ИЛИ-Не становится инвертором (рис. 6.6, а). При последовательном соединении двух элементов ИЛИ-Не, как показано на рис. 6.6 (б), элемент ИЛИ-Не преобразуется в элемент ИЛИ. Таким образом, базис ИЛИ-Не содержит как бы три элемента – ИЛИ-Не, ИЛИ, Не. Рис. 6.6. Соединение элементов базиса ИЛИ-Не: а – инвертор (Не); б – элемент ИЛИ Рассмотрим примеры реализации функций в различных базисах.
  Рис. 6.7. Функция D: а – карта Карно; б – схема в базисе И-Не
  Рис. 6.8. Функция K: а – карта Карно; б – схема в базисе И-Не
  Рис. 6.9. Функция F: а – карта Карно; б – схема в базисе И-Не
  Рис. 6.10. Функция Q: а – карта Карно; б – схема в базисе И-Не
  Рис. 6.11. Функция R: а – карта Карно; б – схема в базисе ИЛИ-Не
  Рис. 6.12. Функция S: а – карта Карно; б – схема в базисе ИЛИ-Не
  Рис. 6.13. Функция G: а – карта Карно; б – схема в базисе ИЛИ-Не
  Рис. 6.14. Функция W: а – карта Карно; б – схема в базисе ИЛИ-Не 6.3. Разложение булевых функций Любая БФ может быть преобразована к виду:  Например,  .В общем случае разложение может быть проведено для любого количества переменных k, где k≤n, и тогда БФ может быть представлена в виде:  где  – БФ, получаемая из исходной подстановкой в нее набора переменных, равного значению k. При этом можно получить БФ в форме, упорядоченной по отношению к некоторым переменным. Например, БФ можно представить так, что каждая конъюнкция функции будет зависеть от х1 и х2 или их инверсий даже в тех случаях, когда в конъюнкциях исходной функции они отсутствуют. Например, Теперь каждая конъюнкция функции зависит от х1 и х2. При проведении разложения по всем переменным можно получить СДНФ БФ. Разложение БФ используется в тех случаях, когда БФ должна быть представлена так, чтобы в каждой конъюнкции присутствовали необходимые переменные. 6.4. Анализ комбинационных схем Задача анализа комбинационных схем состоит в нахождении булевой функции КС. БФ при анализе может быть представлена или в аналитической форме, или в виде таблицы истинности. Анализ проводят для того, чтобы определить функциональные свойства КС или для проверки правильности функционирования КС, или же для того, чтобы определить работоспособность схемы в режимах, отличающихся от заданных при проектировании КС. Работу устройств железнодорожной автоматики необходимо анализировать и при повреждениях некоторых его элементов. При этом важно выполнение основного требования: любое повреждение не должно приводить к изменению алгоритма функционирования, которое может нарушить условия обеспечения безопасности движения поездов. При анализе КС важным является определение возможности упрощения КС. Этого можно достичь минимизацией и упрощением БФ. Отдельной задачей является выяснение поведения устройства в переходных режимах и нарушения работы именно в эти периоды. Анализ КС проводят в два этапа.
При анализе контактной схемы функция в виде ДНФ записывается непосредственно по самой схеме:
Для схемы, представленной на рис. 6.15 (а), запишем БФ в форме ДНФ:  Рис. 6.15. Контактная схема а – исходная схема; б – упрощенная схема  Доопределим эту ДНФ до СДНФ. Для этого каждую конъюнкцию ДНФ необходимо умножить на сумму  ,чтобы получить конституенты единицы, где k – номер переменной, недостающей в конъюнкции.  Нанесем СДНФ на карту Карно (рис. 6.16) и минимизируем. В результате минимизации получится более простая функция, схема которой показана на рис 6.15 (б).  Рис. 6.16. Минимизация функции f картой Карно  При анализе схемы на электронных элементах функция также может записываться непосредственно по самой схеме. Но при сложной схеме это может оказаться затруднительным. В этом случае можно предложить следующий алгоритм:
 Рис. 6.17 Комбинационная схема и функция Y а – исходная КС; б – минимизированная КС Рассмотрим схему, приведенную на рис. 6.17 (а). Выход каждого элемента обозначен своей функцией. Запишем функцию каждого элемента, выведем БФ Y и построим схему (рис. 6.17, б):  Иногда удобно закон схемы представить в виде таблицы истинности. Для этого составляют таблицу, в левой части которой записаны все возможные наборы аргументов. Затем вычисляется значение выходного сигнала схемы для каждого набора переменных и результат заносится в таблицу. При этом можно использовать следующие очевидные свойства элементов.
Например, задана КС (рис. 6.18). Составить для нее таблицу истинности. Для решения задачи обозначим выходы элементов Z, G, F, Y и составим следующую таблицу истинности (для упрощения вычислений выход каждого элемента обозначен своей функцией и занесен в таблицу):  Рис. 6.18. Комбинационная схема и таблица истинности
При решении таких задач промежуточные столбцы (Z, G, F) в таблице истинности могут быть опущены, а вычисление выходных сигналов производится прямо на схеме. Например, на рис. 6.19 рассмотрены состояния выхода схемы при ABC={010, 100, 101, 111}. Результат совпадает с предыдущим анализом.  Рис. 6.19. Значения выхода схемы при различных наборах входных переменных Пусть задана контактная схема (рис. 6.20), для которой необходимо составить таблицу истинности. При рассмотрении схемы цепи, имеющие разомкнутые контакты, будем разрывать, а замкнутые контакты соединять проводником. Слева от каждой схемы представлены наборы аргументов в последовательности х1, х2, х3, а справа над схемой показано значение функции (рис. 6.21).  Рис. 6.20. Контактная схема На наборах 0, 4, 7 все три параллельные цепи имеют разрывы, а значит, ток через цепь течь не может и значение функции равно 0. На наборах 1, 3 замкнута верхняя цепь, на наборах 2, 6 – нижняя, на наборе 5 – средняя. На этих наборах значение функции равно единице (табл. 6.3).  Рис. 6.21. Состояние контактов схемы при различных наборах аргументов Таблица 6.3 Восстановленная таблица истинности релейной схемы  На рис. 6.22, 6.23, 6.24 приведены схемы устройств. Таблицы истинности схем сведены в табл. 6.4. Полученные функции минимизированы и построены новые схемы на основе МДНФ в различных базисах.  Рис. 6.22. Преобразование схемы: а – исходная схема; б – минимизированная схема  Рис. 6.23. Преобразование схемы: а – исходная схема; б – минимизированная схема  Рис. 6.24. Преобразование схемы: а – исходная схема; б – минимизированная схема  Таблица 6.4 Таблица истинности для F1, F2, F3
При анализе некоторых схем достаточно вывести выходную функцию, чтобы найти более короткую формулу, описывающую схему. Например, на рис. 6.25 приведена схема устройства, для которого выведена выходная функция (выход элемента DD5). Элемент DD6 на этой схеме реализует ту же самую функцию, что и заданная схема.  Рис. 6.25. Анализ схемы и ее минимизация Покажем вывод выходной функции схемы:  На рис. 6.26, 6.27 приведены еще две схемы, для которых приведены значения выходных функций.  Рис. 6.26. Анализ схемы и ее минимизация  Рис. 6.27. Анализ схемы и ее минимизация  перейти в каталог файлов | Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей |
. Она записана в базисе И, ИЛИ, Не.
На основе этого элемента производятся различные цифровые устройства. Чтобы реализовать любую функцию в этом базисе, необходимо также проводятся преобразования БФ: