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

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

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

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

Пример. Логической функции 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 )

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

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

Решение: функция, соответствующая логической схеме 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.

МДНФ: 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

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

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

Пример. Найти дизъюнктивное разложение Шеннона по переменной 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 )

Дизъюнктивное разложение по двум переменным 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

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 Решение:

Полное дизъюнктивное разложение: 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). Полное дизъюнктивное разложение = СДНФ

Пример. Найти полное дизъюнктивное разложение Шеннона для логической функции 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)

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.

Пример. Найти конъюнктивное разложение Шеннона по переменной 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 ))

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

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 Решение:

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)). Полное конъюнктивное разложение: Полное конъюнктивное разложение = СКНФ

Пример. Найти полное конъюнктивное разложение Шеннона для логической функции 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))

8.3 Реализация логических функций на мультиплексорах Мультиплексоры (коммутаторы) – коммутационные элементы логических схем, обеспечивающие подключение одного из нескольких информационных входов к одному выходу дигитального устройства. Мультиплексоры объединяют логические элементы определенным образом и, управляя ими, реализуют любую логическую функцию.

Каждый n-мультиплексор имеет: * n управляющих входов, * 2 n информационных входов, * 1 выход n-MUX... 2 n информационных входов... n управляющих входов выход Обобщённая схема:

1- мультиплексор: 1-MUX 1 управляющий вход 2 информационных входа выход В зависимости от значения, поданного на управляющий вход, 1-мультиплексор коммутирует (передает) на выход одно определенное логическое значение с информационного входа.

Пример: логические элементы составляющие 1-мультиплексор. & & 1 c управляющий вход вход_1, при c = 0 вход _2, при c = 1 Схема передает на выход значение с того информационного входа, который выбран значением управляющей переменной c.

2- мультиплексор: 2-MUX Объединяя мультиплексоры в логическую схему и управляя значениями логических переменных, можно реализовать любую логическую функцию. 4 информационных входа 2 управляющих входа выход

Для реализации на мультиплексорах логическую функцию надо преобразовать с помощью дизъюнктивного разложения Шеннона. на 1- мультиплексорах применяют дизъюнктивное разложение Шеннона по одной переменной; на 2- мультиплексорах применяют дизъюнктивное разложение Шеннона по двум переменным; и т.д. Для реализации логической функции Для каждой полученной остаточной функции делают снова дизъюнктивное разложение по одной переменной, пока не получат в скобках константу или одну переменную.

Пример: реализовать на 1-мультиплексорах логическую функцию f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4 Решение:дизъюнктивное разложение Шеннона по переменной X 2 Для каждой остаточной функции делают снова дизъюнктивное разложение по одной переменной, пока не получат в скобках константу или одну переменную 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 & X 3 X 3 & X 4 ) X 2 & (X 3 & X 4 ) = X 2 & ( X 3 & (X 1 & 1 0 & X 4 ) X 3 & (X 1 & 0 1 & X 4 )) X 2 & ( X 3 & (0 & X 4 ) X 3 & (1 & X 4 )) = = X 2 & ( X 3 & (X 1 ) X 3 & (X 4 )) X 2 & ( X 3 & (0) X 3 & (X 4 ))

Полученное выражение реализуем на 1-мультиплексорах, где управляющими переменными будут переменные, по которым было сделано разложение. Схему строят в направлении справа налево, от функции к переменным. Каждое следующее разложение функции дает новое разветвление на схеме, ветвь 0 соотв. компоненту с отрицанием, 1 без отрицания. X 2 & ( X 3 & (X 1 ) X 3 & (X 4 )) X 2 & ( X 3 & (0) X 3 & (X 4 )) f (X 1, X 2, X 3, X 4 ) 1-MUX X2X2 X 2 =0 X 2 =1 1-MUX X 3 =1 X3X3 X 3 =0 X1X1 X4X4 1-MUX X 3 =1 X 3 =0 X3X3 X4X4 0

Пример: реализовать на 2-мультиплексорах логическую функцию f (X 1, X 2, X 3, X 4 ) = X 1 & X 2 & X 3 X 3 & X 4 Решение: дизъюнктивное разложение Шеннона по переменным X 2 и Х 3 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 ) X 2 & X 3 & (X 4 ) X 2 & X 3 & (0) X 2 & X 3 & (X 4 ) Полученное выражение реализуем на 2-мультиплексорах, где управляющими переменными будут переменные, по которым было сделано разложение.

f (X 1, X 2, X 3, X 4 ) 2-MUX X2X2 X 2 =0, X 3 =0 X3X3 X 2 =0, X 3 =1 X 2 =1, X 3 =0 X 2 =1, X 3 =1 X1X1 X4X4 0 X4X4

9. Исчисление предикатов Значение истинности предиката зависит от значений переменных P (x) P (x,y) и т.д. Кванторы : - квантор всеобщности (для каждого x) - квантор существования (найдется хотя бы один x) P (x,y) (x > y) P (5,3) = 1 P (3,5) = 0 P (3,y) = {y | y