- •Проектирование электронных устройств
- •Чернигов чгту 2012
- •Оглавление
- •2.4 Пример выполнения работы № 3 46
- •Введение
- •1Ргр №2. Реализация булевых функций на логических элементах
- •1.1Цель работы
- •Табличный способ представления
- •1.2Теоретические сведения
- •1.3Способы представления булевых функций
- •Матричный способ представления
- •Логические функции двух переменных
- •1.5Алгебра Буля
- •1.6Законы алгебры логики
- •1.7Переход от табличной формы представления логической функции к аналитической
- •1.8Импликанты и имплициенты булевых функций
- •1.9Сокращенные, минимальные и тупиковые формы
- •Метод карт Карно (диаграммы Вейча)
- •Минимизация функции трех переменных
- •Минимизация функции четырех переменных
- •Минимизация функции пяти переменных
- •Минимизация систем булевых функций по картам Карно
- •1.10Алгебра Жегалкина
- •Определение алгебры Жегалкина
- •Преобразование функций в алгебре Жегалкина
- •Переход от булевой алгебры к алгебре Жегалкина
- •1.11Задания, выполняемые в расчетно-графической работе
- •1.12Пример выполнения работы № 2
- •Выполнение задания 1
- •Выполнение задания 2
- •Выполнение задания 3
- •Цель работы.
- •2.3Запоминающие элементы триггеров
- •Запоминающие элементы триггеров, управляемые уровнем тактирующего сигнала
- •Запоминающие элементы триггеров, управляемые перепадом тактирующего сигнала - зэзэ триггеров, собранные по ms схеме
- •- Зэзэ по схеме трёх триггеров
- •Задания, выполняемые в расчетно-графической работе
- •2.4Пример выполнения работы № 3
- •Пример построения dv-триггеров по ms схеме на элементах и-не
- •Пример реализации т-триггера по ms схеме на элементах или-не
- •Пример реализации jk-триггера по схеме трех триггеров на и-не
- •Цель работы.
- •3.3Абстрактный синтез автомата
- •Минимизация числа состояний автомата
- •Кодирование состояний автомата
- •Получение функций возбуждения блока памяти и функций выхода
- •Задания выполняемые в расчетно-графической работе
- •3.4Пример выполнения работы № 4
- •3.5Выводы
- •3.6Содержание отчета
- •Цель работы.
- •4Рекомендованная литература
1.8Импликанты и имплициенты булевых функций
Определение: булевая функция G (x1, … , xn) называется импликантой логической функции F (x1, … , xn), если для любого набора переменных, на котором G (x1, … , xn) = 1, справедливо и F (x1, … , xn) = 1.
Определение: булевая функция H (x1, … , xn) называется имплициентой логической функции F (x1, … , xn), если для любого набора переменных, на котором H (x1, … , xn) = 0, справедливо и F (x1, … , xn) = 0.
Таблица 1.9 – Импликанты функции 3 – х переменных
х1 х2 х3 |
F |
G1 |
G2 |
G3 |
G4 |
G5 |
G6 |
G7 |
0 0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 0 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 1 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 1 1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 0 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 0 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 1 0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 1 1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Функция F имеет семь импликант:
СДНФ: F = х1 х2 х3 х1 х2 х3 х1 х2 х3 = G7,
G1 = х1 х2 х3,
G2 = х1 х2 х3 ,
G3 = х1 х2 х3 х1 х2 х3 = х1 х2,
G4 = х1 х2 х3 ,
G5 = х1 х2 х3 х1 х2 х3 = х2 х3,
G6 = х1 х2 х3 х1 х2 х3 .
Определение: импликанта G булевой функции F, являющаяся элементарной конъюнкцией, называется простой импликантой, если никакая часть импликанты G не является импликантой функции F.
В нашем примере простые импликанты G3 = х1 х2 и G5 = х2 х3.
Определение: дизъюнкция любого числа импликант булевой функции F также является импликантой этой функции.
Все выше сказанное касается и имплициент, если мы рассматриваем логическую функцию исходя из СКНФ.
1.9Сокращенные, минимальные и тупиковые формы
Определение: Любая булевая функция F эквивалентна дизъюнкции своих простых импликант. Такая форма булевой функции называется сокращенной дизъюнктивной нормальной формой.
В нашем случае сокращенная ДНФ: F = G3 G5 = х1 х2 х2 х3.
Определение: сокращенная ДНФ булевой функции называется тупиковой ДНФ, если в ней отсутствуют лишние простые импликанты.
Примечание: булевая функция может иметь несколько тупиковых ДНФ.
Определение: тупиковая ДНФ булевой функции, содержащая минимальное число аргументов, называется минимальной ДНФ.
Примечание: минимальных ДНФ у логической функции также может быть несколько.
Аналогично определяются сокращенные, тупиковые и минимальные конъюнктивные нормальные формы.