Часть 3. Логические элементы. Задача 1 ХYZF0001 0010 0101 1. Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? - презентация

1 Часть 3. Логические элементы

2 Задача 1 ХYZF Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F?

3 Задача 2 Три преподавателя отбирают задачи для олимпиады. По каждой из задач каждый из преподавателей высказывает свое мнение: легкая (0) задача или трудная (1). Задача включается в олимпиадное задание, если не менее двух преподавателей отметили ее как трудную, но если все три преподавателя отметили как трудную, то такая задача как слишком сложная не включается в задание. Составить схему устройства, которое на выходе будет выдавать 1, если задача включается в задание, и 0, если не включается.

4 Задача 3 В конкурсе решается вопрос о допуске к следующему туру. Работают три члена жюри P, Q, R. Положительное решение жюри принимается тогда и только тогда, когда «ЗА» выскажутся хотя бы два члена жюри, из которых обязательно один председатель жюри Q. Разработать устройство для голосования, в котором каждый член жюри нажимает кнопки «ЗА» и «Против», а результат голосования определяется по включению сигнальной лампочки. (Составить функциональную схему устройства, которое на выходе выдавало бы 1 или 0.)

5 Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) нескольких переменных, взятых с отрицанием или без отрицания, причем среди переменных могут быть одинаковые X v X X v Z X v Y v Z - правильно X v Y & Z - неправильно Элементарная дизъюнкция Элементарная конъюнкция X & X X & Z X & Y & Z - правильно X v Y & Z - неправильно

6 Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивно-нормальной формой - ДНФ Всякая конъюнкция элементарных дизъюнкций называется конъюнктивно-нормальной формой - КНФ X & X v X & Y & Z X & Y v Z v X & Z (X v Y v Y) & (X v Z) X & (Z v Y) & (X v Z)

7 Совершенной дизъюнктивно-нормальной формой – (СДНФ) называется ДНФ, в которой: - нет одинаковых элементарных конъюнкций, - все конъюнкции состоят из одного набора переменных, - каждая переменная входит в элементарную конъюнкцию только один раз (возможно с отрицанием). ДНФСДНФ X & Y & Z v X & Y & Z Y & X & Z v Y & X & Z Z & X v X & Y & Z X & Y v Z v X & Z

8 (X v Y v Z) & (X v Y v Z) (Z v Y) & (Z v Y) Совершенной конъюнктивно-нормальной формой – (СКНФ) называется КНФ, в которой^ - нет одинаковых элементарных дизъюнкций? - все дизъюнкции состоят из одного набора переменных, - каждая переменная входит в элементарную дизъюнкцию только один раз (возможно с отрицанием). КНФ СКНФ (X v Y v Y) & (X v Z) X & (Z v Y) & (X v Z) Любую функцию, кроме констант 0 и 1, можно представить в виде как СДНФ, так и СКНФ 0=X & X 1=X v X СДНФ СКНФ

9 Алгоритм получения СДНФ по таблице истинности ХYF(X,Y) Отметить строки таблицы истинности, в которых значение функции истинно. 2. Выписать для каждой строки конъюнкцию всех переменных: - если значение переменной равно 1, в конъюнкцию включать переменную; - если значение переменной равно 1, в конъюнкцию включать переменную; - если значение переменной равно 0, в конъюнкцию включать инверсию переменной; - если значение переменной равно 0, в конъюнкцию включать инверсию переменной; для 2-й строки: X & Y; для 3-й строки: X & Y. 3. Все конъюнкции связать в дизъюнкцию ( X & Y) v ( X & Y).

10 Алгоритм получения СКНФ по таблице истинности ХYF(X,Y) Отметить строки таблицы истинности, в которых значение функции ложно. 2. Выписать для каждой строки дизъюнкцию всех переменных: - если значение переменной равно 0, в дизъюнкцию включать переменную; - если значение переменной равно 0, в дизъюнкцию включать переменную; - если значение переменной равно 1, в дизъюнкцию включать инверсию переменной; - если значение переменной равно 1, в дизъюнкцию включать инверсию переменной; для 1-й строки: X v Y; для 4-й строки: X v Y. 3. Все дизъюнкции связать в конъюнкцию ( X v Y) & ( X v Y). СКНФ и СДНФ эквивалентны рекомендация

11 ПримерХYZF Дан фрагмент таблицы истинности выражения F: Какое выражение соответствует F? Предложите схему устройства а) для блока проверки трех сигналов на совпадение (на выходе блока должна возникать единица, когда все входные сигналы совпадают); б) для блока проверки трех сигналов на несовпадение. F=X & Y & Z v X & Y & Z F=X v Y v Z назад

12 Функциональные схемы и структурные формулы Логическое устройство – цепочка из логических элементов, в которой выходы одних элементов являются входами других. Функциональная схема – схема соединения логических элементов, реализующая логическую функцию Структурная формула - форма описания функции, реализуемой логическим устройством Логический элемент – это преобразователь, который получая сигналы об истинности отдельных высказываний, обрабатывает их и выдает значение логического отрицания, логической суммы или логического произведения этих высказываний

13 Инвертор (НЕ) Физическая модель Схема Обозначение Таблица истинности Реле с нормально замкнутыми контактами X F(X) В F X X Логические элементы

14 Конъюнктор (И) Физическая модель Схема Обозначение Таблица истинности Последователь- ное соединение переключателей X Y F(X) X X & Y +5 В F Y &

15 Дизъюнктор (ИЛИ) Физическая модель Схема Обозначение Таблица истинности Параллельное соединение переключателей X Y F(X) X X V Y Y 1 +5 В F

16 Логический элемент Обозначение Обозначение И-НЕИЛИ-НЕ X Y & X & Y X Y 1 X V Y

17 Задача 1 Определить структурную формулу по заданной функциональной схеме X Y 1 F(X,Y) F(X,Y) = X V Y Задача 2 Построить функциональную схему, соответствующую структурной формуле F(X,Y) = X & Y Задача 3 Определить структурную формулу по заданной функциональной схеме X Y & F(X,Y) = X & Y X Y 1 F(X,Y) & F(X,Y) = X & Y

18 Задача 4 Построить функциональную схему, соответствующую структурной формуле F(X,Y) = ( X V Y ) & X XYX X V Y F(X,Y) Таблица истинности, построенная по формуле Таблица истинности, построенная по функциональной схемеXY Выход 1 Выход 2 Выход 3 Выход Проверка: X Y 1 & F(X,Y) = ( X V Y ) & X

19 Задача 6 F(P,Q,R) = P & Q & R V ( P V Q V R) & Q Задача 7 Построить функциональную схему, соответствующую структурной формуле P Q 1 F & & R 1 Построить функциональную схему, соответствующую структурной формуле Y(A,B) = A & (A V B ) A B F & 1

20 Задача 8 Задача 9 Построить функциональную схему, соответствующую структурной формуле F(X,Y,Z) = (X V Y ) & ( X V Z) & (Y V Z ) X Y F 1 Z & 1 1 Определить структурную формулу по заданной функциональной схеме X Y F 1 F(X,Y) = (X V Y )

21 Задача 10 F(X,Y,Z) = (X V Y ) & ( Y & Z) Определить структурную формулу по заданной функциональной схеме X Y F 1 Z & & Отбор по конкурсу Отбор по конкурсу Задачи к олимпиаде Задачи к олимпиаде Несовпадение сигналов Несовпадение сигналов

22 Задача 2 Составить структурную формулу и функциональную схему: а) для блока проверки трех сигналов на совпадение (на выходе блока должна возникать единица, когда все входные сигналы совпадают); б) для блока проверки трех сигналов на несовпадение. F=X & Y & Z v X & Y & Z назад X Y F Z 1 & & X Y F Z & 1 1

23 Задача 3 Три преподавателя отбирают задачи для олимпиады. По каждой из задач каждый из преподавателей высказывает свое мнение: легкая (0) задача или трудная (1). Задача включается в олимпиадное задание, если не менее двух преподавателей отметили ее как трудную, но если все три преподавателя отметили как трудную, то такая задача как слишком сложная не включается в задание. Составить структурную формулу и функциональную схему устройства, которое на выходе будет выдавать 1, если задача включается в задание, и 0, если не включается. PQRF F=P & Q & R v P & Q & R v P & Q & R P Q F & R 1 & & назад

24 Задача 3 В конкурсе решается вопрос о допуске к следующему туру. Работают три члена жюри P, Q, R. Положительное решение жюри принимается тогда и только тогда, когда «ЗА» выскажутся хотя бы два члена жюри, из которых обязательно один председатель жюри Q. Разработать устройство для голосования, в котором каждый член жюри нажимает кнопки «ЗА» и «Против», а результат голосования определяется по включению сигнальной лампочки. (Составить функциональную схему устройства, которое на выходе выдавало бы 1 или 0.) PQRF P Q F & R 1 & & F=P & Q & R v P & Q & R v P & Q & R

25 Логические устройства ЭВМ Сумматор – основной узел арифметико-логического устройства - служит для суммирования многозначных двоичных чисел посредством поразрядного сложения 1 XnXn YnYn SnSn XiXi YiYi SiSi X2X2 Y2Y2 S2S2 X1X1 Y1Y1 S1S1 P1P1 P1P1 P i-1 PiPi P n =110000

26 XY S P Одноразрядный полусумматор – одноразрядный двоичный сумматор на два входа и два выхода ХYРS P(X,Y)=X & Y S(X,Y)=X & Y v X & Y S(X,Y)=(X & Y) & (X v Y) Условное обозначение Структурные формулы Правило сложения двоичных чисел Преобразованная формула S(X,Y)=(X v Y) & (X v Y) Функциональная схема X & P & 1 Y & S Таблица истинности ВходыВыходыХY СДНФ СКНФ

27 Одноразрядный двоичный сумматор на три входа и два выхода ХYРQS Условное обозначение Структурные формулы Правило сложения двоичных чисел XY S Q P Q(X,Y,P)=X & Y & P v X & Y & P v X & Y & P v X & Y & P Q(X,Y,P)=X & Y & P v X & Y & P v X & Y & P v X & Y & P Преобразованные формулы Q(X,Y,P)=Y & P v X & P v X & Y S(X,Y,P)=X & Y & P v X & Y & P v X & Y & P v X & Y & P S(X,Y,P)=X & Y & P v X & Y & P v X & Y & P v X & Y & P S(X,Y,P)=(Q v P·Y·X) & (P v Y v X)

28 Преобразование формул Q(X,Y,Р)=¬X & Y & P v X & ¬Y & P v X & Y & ¬ P v X & Y & P = =¬X & Y & P v X & ¬Y & P v X & Y & ¬ P v X & Y & P v X & Y & P v X & Y & P = =(¬X & Y & P v X & Y & P) v (X & ¬Y & P v X & Y & P) v (X & Y & ¬ P v X & Y & P) = = Y & P (¬X v X) v X & P (¬Y v Y) v X & Y & (¬ P v P) = Y & P v X & P v X & Y & Q(X,Y)= (¬X & ¬Y & P) v (¬X & Y & ¬P ) v (X & ¬Y & ¬P) v (X & Y & P) = = ¬ ¬((¬X & ¬Y & P) v (¬X & Y & ¬P) v (X & ¬Y & ¬P) v (X & Y & P))= = = ¬((X v Y v ¬P) & (X v ¬Y v P) & (¬X & Y v P) & (¬X & ¬Y v ¬P)) = = ¬((X v Y v ¬P) & (X v ¬Y v P) & (¬X & Y v P) & (¬X & ¬Y v ¬P)) == = ¬((X v (Y v ¬P) & (¬Y v P)) & (¬X v (Y v P) & (¬Y v ¬P))) = = ¬((X v (Y v ¬P) & (¬Y v P)) & (¬X v (Y v P) & (¬Y v ¬P))) = = ¬ ((X v (Y ·¬Y v ¬P ·¬Y v Y ·P v ¬P · P)) & (¬X v (Y · ¬Y v Y · ¬P v P · ¬Y v P · ¬P))) = = ¬ ((X v (¬P ·¬Y v Y ·P)) & (¬X v (Y · ¬P v P · ¬Y )) )= = ¬ (X v ¬P ·¬Y v Y ·P) & (¬X v Y · ¬P v P · ¬Y ) = = = ¬ (X·¬X v X·Y·¬P v X·P·¬Y v ¬P·¬Y·¬X v ¬P·¬Y·Y·¬P v ¬P·¬Y·P·¬Y v Y·P·¬X v Y·P·Y·¬P v Y·P·P ·¬Y) = = ¬ (X·Y·¬P v X·P·¬Y v ¬P·¬Y·¬X v Y·P·¬X) = ¬ ((X·Y·¬P v X·P·¬Y v Y·P·¬X) v (¬P·¬Y·¬X)) = = = ¬ (X·Y·¬P v X·P·¬Y v Y·P·¬X) & ¬ (¬P·¬Y·¬X) = = ¬ (X·Y·¬P v ·¬Y v Y·P·¬X) & (P v Y v X) = = ¬ (X·Y·¬P v X·P·¬Y v Y·P·¬X v X ·¬X ·(YvP) v Y·¬Y·(XvP) v P·¬P ·(YvX)) & (P v Y v X) = = ¬ ((X·Y·¬P v P·¬P ·(YvX)) v (X·P·¬Y v Y·¬Y·(XvP)) v (Y·P·¬X v X ·¬X ·(YvP)) & (P v Y v X) = = ¬ ((¬P ·(X·P vY ·P v X·Y)) (¬Y ·(X·P vY ·P v X·Y)) v (¬X·(X·P v Y·P v X·Y)) & (P v Y v X) = = ¬ ((X·P vY ·P v X·Y) · (¬P v ¬Y v ¬X)) & (P v Y v X) = = (¬ (X·P vY ·P v X·Y) v (P·Y·X)) & (P v Y v X) = = (¬Q v P·Y·X) & (P v Y v X)

29 Одноразрядный сумматор на три входа Функциональная схема Q(X,Y,P)=Y & P v X & P v X & Y S(X,Y,P)=(Q v P·Y·X) & (P v Y v X) X & 1 & & & 1 Y P 1 & Q S

30 Триггер - устройство, которое может запоминать сигналы 0 и 1, демонстрировать их, а при необходимости забывать. Используется как запоминающая ячейка вычислительных устройств. RS-триггер (защелка, выключатель) – Режим работы Входы Выходы SRQ¬QВлияние на выход Q Запрещенное состояние 0011Не используется Установка 0110Для установки Q в 1 Сброс 1001Для установки Q в 0 Хранение 1100Зависит от предыдущего состояния установки R QS Q T Условное обозначение Функциональная схема R - reset & & S - set Q Q Установка 1 Прямой выход Инверсный выход Таблица истинности

31 T-триггер (переключатель, тумблер) Условное обозначение Q0Q0 Q0Q0 Q1Q1 Q2Q2 Q3Q3 Q4Q4 Q1Q1 Q2Q2 Q3Q3 Q4Q4 TQ Q Счетчик Для запоминания и демонстрации n разрядного двоичного числа необходимо n параллельно соединенных тригеров, совокупность которых называется n -разрядным регистром Тригер запоминает один разряд двоичного числа Для запоминания 1 байта требуется 8 тригеров