7. Элементы логических схем (логические элементы) Электрическую схему, обрабатывающую двоичные коды называют дигитальной схемой. Составляющими частями. - презентация

1 7. Элементы логических схем (логические элементы) Электрическую схему, обрабатывающую двоичные коды называют дигитальной схемой. Составляющими частями каждой дигитальной схемы являются логические элементы, которые выполняют простейшие логические действия с логическими константами 0 и 1. Логическая схема получается соединением логических элементов. Каждое дигитальное устройство состоит из логических схем и обрабатывает последовательности из нулей и единиц.

2 Логические функции = математические модели логических схем. Логические схемы = физические модели логических функций. 7.1 Обозначения логических элементов 1. Инвертор или НЕ-элемент (NOT) X X входвыход

3 2. Конъюнкция или И-элемент (AND) X1X1 X2X2 X 1 & X 2 & 3. Дизъюнкция или ИЛИ-элемент (OR) вход выход X1X1 X2X2 вход 1 X 1 X 2 выход

4 X1X1 X2X2 (X 1 & X 2 ) & 5. Инверсия дизъюнкции или ИЛИ-НЕ-элемент (NOR) вход выход X1X1 X2X2 вход 1 (X 1 X 2 ) выход 4. Инверсия конъюнкции или И-НЕ-элемент (NAND)

5 Пример. Логической функции 3-х переменных f (X 1, X 2, X 3 ) = (X 1 & ( X 2 X 3 )) соответствует логическая схема: X3X3 X2X2 1 X1X1 & f (X 1, X 2, X 3 )

6 7.2 Минимизация логических схем Алгоритм: 1. шаг: найти логическую функцию, соответствующую данной схеме 2. шаг: найти МДНФ или МКНФ этой функции 3. шаг: найти схему, соответсвующую минимальной форме

7 Пример. Дана логическая схема, реализующая логическую функцию f на ИЛИ-НЕ элементах. Является ли данная схема минимальной? Найти МДНФ функции и соответствующую ей схему. X3X3 X2X2 1 X1X1 1 f (X 1, X 2, X 3, X 4 ) X1X1 X4X4 X2X2 X2X2 X3X3 X4X4 1 1

8 Решение: функция, соответствующая логической схеме f (X 1, X 2, X 3, Х 4 ) = = ( (X 1 X 2 X 3 X 4 ) ( X 2 X 3 X 4 ) ( X 1 X 2 )) Найдем МДНФ: f (X 1, X 2, X 3, Х 4 ) = ( (X 1 X 2 X 3 X 4 ) ( X 2 X 3 X 4 ) ( X 1 X 2 )) = (X 1 X 2 X 3 X 4 ) & ( X 2 X 3 X 4 ) & ( X 1 X 2 ) = ( X 2 X 3 X 4 ) & ( X 1 X 2 ) 7.b)11.а ) Карта Карно: X3 X4X1 X2X3 X4X1 X МДНФ: X 2 X 1 & X 4 X 1 & X 3.

9 МДНФ: X 2 X 1 & X 4 X 1 & X 3. Соответствующая логическая схема: X4X4 X1X1 & 1 f (X 1, X 2, X 3, X 4 ) X1X1 X3X3 & X2X2

10 8. Разложение логических функций в ряд Шеннона Разложение Шеннона дизъюнктивное конъюнктивное частичноеполноечастичноеполное Частичное разложение = разложение по одной или нескольким переменным X i. Полное разложение = разложение по всем переменным X i.

11 8.1 Дизъюнктивное разложение Шеннона Дизъюнктивное разложение по одной переменной X i : f (X 1,...,X i,..., X n ) = X i & f (X 1,..., X i-1,0, X i+1,..., X n ) X i & f (X 1,..., X i-1,1, X i+1,..., X n ), где f (X 1,...,0,..., X n ) - остаточная функция для X i = 0 и f (X 1,...,1,..., X n ) - остаточная функция для X i = 1. Пример. Найти дизъюнктивное разложение Шеннона по переменной X 2 для логической функции f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4

12 Пример. Найти дизъюнктивное разложение Шеннона по переменной X 2 для логической функции f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4 Решение: f (X 1, X 2, X 3, X 4 ) = X 2 & f (X 1, 0, X 3, X 4 ) X 2 & f (X 1, 1, X 3, X 4 ) = = X 2 & (X 1 & 1 & X 3 X 3 & X 4 ) X 2 & (X 1 & 0 & X 3 X 3 & X 4 ) = = X 2 & (X 1 & X 3 X 3 & X 4 ) X 2 & (X 3 & X 4 )

13 Дизъюнктивное разложение по двум переменным X i и X k : f (X 1,...,X i, X k..., X n ) = X i & X k & f (X 1,...,0, 0,..., X n ) X i & X k & f (X 1,..., 0, 1,..., X n ) X i & X k & f (X 1,..., 1, 0,..., X n ) X i & X k & f (X 1,..., 1, 1,..., X n ) Пример. Найти дизъюнктивное разложение Шеннона по переменным X 2 и X 3 для логической функции f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4

14 f (X 1, X 2, X 3, X 4 )= X 2 & X 3 & f (X 1, 0, 0, X 4 ) X 2 & X 3 & f (X 1, 0, 1, X 4 ) X 2 & X 3 & f (X 1, 1, 0, X 4 ) X 2 & X 3 & f (X 1, 1, 1, X 4 ) = = X 2 & X 3 & (X 1 & 1 & 1 0 & X 4 ) X 2 & X 3 & (X 1 & 1 & 0 1 & X 4 ) X 2 & X 3 & (X 1 & 0 & 1 0 & X 4 ) X 2 & X 3 & (X 1 & 0 & 0 1 & X 4 ) = = X 2 & X 3 & (X 1 ) X 2 & X 3 & (X 4 ) X 2 & X 3 & (0) X 2 & X 3 & (X 4 ) Пример. Найти дизъюнктивное разложение Шеннона по переменным X 2 и X 3 для логической функции f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4 Решение:

15 Полное дизъюнктивное разложение: f (X 1, X 2,..., X n-1, X n ) = X 1 & X 2 &...& X n-1 & X n & f (0,0,... 0,0) X 1 & X 2 &...& X n-1 & X n & f (0,0,... 0,1) X 1 & X 2 &...& X n-1 & X n & f (0,0,... 1,0)... X 1 & X 2 &...& X n-1 & X n & f (1,1,... 1,0) X 1 & X 2 &...& X n-1 & X n & f (1,1,... 1,1). Полное дизъюнктивное разложение = СДНФ

16 Пример. Найти полное дизъюнктивное разложение Шеннона для логической функции f (X 1, X 2, X 3 ) = (X 1 & X 2 X 2 & X 3 ) Решение: f (X 1, X 2, X 3, X 4 )= X 1 & X 2 & X 3 & f (0, 0, 0 ) X 1 & X 2 & X 3 & f (0, 0, 1) X 1 &X 2 & X 3 & f (0, 1, 0) X 1 &X 2 & X 3 & f (0, 1, 1) X 1 & X 2 & X 3 & f (1, 0, 0) X 1 & X 2 & X 3 & f (1, 0, 1) X 1 & X 2 & X 3 & f (1, 1, 0) X 1 &X 2 & X 3 & f (1, 1, 1) = = X 1 & X 2 & X 3 & (1 ) X 1 & X 2 & X 3 & (1) X 1 &X 2 & X 3 & (1) X 1 &X 2 & X 3 & (0) X 1 & X 2 & X 3 & (0) X 1 & X 2 & X 3 & (0) X 1 & X 2 & X 3 & (1) X 1 &X 2 & X 3 &(0)

17 8.2 Конъюнктивное разложение Шеннона f (X 1,...,X i,..., X n ) = (X i f (X 1,...,0,..., X n )) & & ( X i f (X 1,...,1,..., X n )), Конъюнктивное разложение по одной переменной X i : где f (X 1,...,0,..., X n ) - остаточная функция для X i = 0 и f (X 1,...,1,..., X n ) - остаточная функция для X i = 1.

18 Пример. Найти конъюнктивное разложение Шеннона по переменной X 2 для логической функции f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4 Решение: f (X 1, X 2, X 3, X 4 ) = (X 2 f (X 1, 0, X 3, X 4 )) & ( X 2 f (X 1, 1, X 3, X 4 )) = = (X 2 (X 1 & 1 & X 3 X 3 & X 4 )) & ( X 2 (X 1 & 0 & X 3 X 3 & X 4 )) = = (X 2 (X 1 & X 3 X 3 & X 4 )) & ( X 2 (X 3 & X 4 ))

19 f (X 1,...,X i, X k..., X n ) = (X i X k f (X 1,...,0, 0,..., X n )) & & (X i X k f (X 1,..., 0, 1,..., X n ))& & ( X i X k f (X 1,..., 1, 0,..., X n )) & & ( X i X k f (X 1,..., 1, 1,..., X n )) Конъюнктивное разложение по двум переменным X i и X k : Пример. Найти конъюнктивное разложение Шеннона по переменным X 2 и X 3 для логической функции f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4

20 f (X 1, X 2, X 3, X 4 )= (X 2 X 3 f (X 1, 0, 0, X 4 )) & (X 2 X 3 f (X 1, 0, 1, X 4 )) & & ( X 2 X 3 f (X 1, 1, 0, X 4 )) & ( X 2 X 3 f (X 1, 1, 1, X 4 )) = = (X 2 X 3 (X 1 & 1 & 1 0 & X 4 )) & (X 2 X 3 (X 1 & 1 & 0 1 & X 4 )) & & ( X 2 X 3 (X 1 & 0 & 1 0 & X 4 )) & ( X 2 X 3 (X 1 & 0 & 0 1 & X 4 )) = = (X 2 X 3 (X 1 )) & (X 2 X 3 (X 4 )) & ( X 2 X 3 (0)) & ( X 2 X 3 (X 4 )) Пример. Найти конъюнктивное разложение Шеннона по переменным X 2 и X 3 для логической функции f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4 Решение:

21 f (X 1, X 2,..., X n-1, X n ) = (X 1 X 2... X n-1 X n f (0,0,... 0,0)) & & (X 1 X 2... X n-1 X n f (0,0,... 0,1)) & & (X 1 X 2... X n-1 X n f (0,0,... 1,0)) &... & ( X 1 X 2... X n-1 X n f (1,1,... 1,0)) & & ( X 1 X 2... X n-1 X n f (1,1,... 1,1)). Полное конъюнктивное разложение: Полное конъюнктивное разложение = СКНФ

22 Пример. Найти полное конъюнктивное разложение Шеннона для логической функции f (X 1, X 2, X 3 ) = (X 1 & X 2 X 2 & X 3 ) Решение: f (X 1, X 2, X 3, X 4 )= (X 1 X 2 X 3 f (0, 0, 0 )) & (X 1 X 2 X 3 f (0, 0, 1)) & & (X 1 X 2 X 3 f (0, 1, 0)) & (X 1 X 2 X 3 f (0, 1, 1)) & & ( X 1 X 2 X 3 f (1, 0, 0)) & ( X 1 X 2 X 3 f (1, 0, 1)) & & ( X 1 X 2 X 3 f (1, 1, 0)) & ( X 1 X 2 X 3 f (1, 1, 1)) = = (X 1 X 2 X 3 (1 )) & (X 1 X 2 X 3 (1)) & (X 1 X 2 X 3 (1)) & & (X 1 X 2 X 3 (0)) & ( X 1 X 2 X 3 (0)) & ( X 1 X 2 X 3 (0)) & & ( X 1 X 2 X 3 (1)) & ( X 1 X 2 X 3 (0))