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

Презентация:



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

4. Минимизация логических функций. Карты Карно. Задача минимизации логической функции заключается в том, чтобы найти наиболее компактное её представление.
Базовые логические элементы Иванова ЮлияАмериканец Клод Шеннон раскрыл связи между двоичным способом хранения информации, алгеброй логики и электрическими.
Презентация к уроку по информатике и икт по теме: Базовые логические элементы (презентация)
Элементы математической логики. Высказывание Объект изучения – высказывание. Высказывание – предложение (сообщение) об объективно существующей действительности,
8.3 Реализация логических функций на мультиплексорах Мультиплексоры (коммутаторы) – коммутационные элементы логических схем, обеспечивающие подключение.
СДНФ и СКНФ Формы булевых функций. Дополнительные операции Импликация Эквивалентность Сложение по модулю 2 Стрелка Пирса (ИЛИ-НЕ) Штрих Шеффера (И-НЕ)
Логика в информатике Решение уравнений. Логические основы ПЭВМ.
1 Совершенная дизъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма Логические основы ЭВМ 10 класс Белоусова Елена Ивановна, учитель.
7.2. Логические элементы. Малые интегральные схемы. Логические элементы. Малые интегральные схемы. Схемы цифровых устройств делятся по степени сложности.
Базовые логические элементы. Чтобы сконструировать устройство, мы должны знать: каким образом следует реализовать логические значения 0 и 1 в виде электрических.
Часть 3. Логические элементы. Элементарной конъюнкцией (дизъюнкцией) называется конъюнкция (дизъюнкция) нескольких переменных, взятых с отрицанием или.
ФОРМЫ ПРЕДСТАВЛЕНИЯ ВЫСКАЗЫВАНИЙ Элементарной дизъюнкцией называется выражение вида: Элементарной конъюнкцией называется выражение вида: Где A i - либо.
Нормальные формы ХНУРЭ, кафедра ПО ЭВМ, Тел , Лекция 6 Н.В. Белоус Факультет компьютерных наук Кафедра ПО ЭВМ,
Элементы математической логики.
ЛОГИЧЕСКИЕ ОСНОВЫ ЭВМ 1) АЛГЕБРА ЛОГИКИ 2) СИНТЕЗ ЛОГИЧЕСКИХ СХЕМ.
Логические функции. Логической (булевой) функцией называют функцию F(x 1,x 2,...,x n ), аргументы которой x 1,x 2,...,x n (независимые переменные) и сама.
Логические элементы Подготовил ученик 8 « А » класса Егоров Владимир.
Логические основы устройства компьютера. В вычислительной технике для построения более сложных логических устройств используются три основных логических.
3. Нормальные формы логических функций Нормальной формой логической функции является такая формула, которая считается наиболее наглядной и удобной в использовании,
Транксрипт:

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))