Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Цифровые устройства по способу функционирования делятся на:
-комбинационные устройства;
-последовательностные устройства (конечные автоматы).
Комбинационные устройства (комбинационные логические схемы) не содержат элементов памяти и их выходные сигналы Fi определяются совокупностью входных сигналов (a, b, …, z) на данном временном интервале.
Fi=fi(a, b, …, z)
Конечные автоматы содержат элементы памяти и обратные связи, поэтому их выходные сигналы Fij+1 в j+1 интервале времени зависят, как от совокупности входных сигналов a, b, …, z действующих на j+1 интервале, так и от их совокупности aj, bj, …,zj на предшествующих временных интервалах .
Fi=fi(aj+1, bj+1, …, zj+1, aj, bj, …,zj )
Цифровые устройства выполняют операции над простыми и сложными высказываниями, принимающих только два значения «истина» и «ложь» или «да» и «нет». В соответствии с булевой алгеброй логики (двоичной алгеброй логики), получившей свое название по имени математика Джорджа Буля (1815-1864 гг.), указанные два значения принято обозначать «1» - логическая единица и «0» - логический ноль.
Каждая двоичная цифра «0» или «1» содержат один бит двоичной информации. Последовательность из восьми бит называется байтом. Четыре бита составляют полубайт.
Часто используемые единицы измерения:
1Кбайт=1024 байт; 1Мбайт=1024 Кбайт=1048576 байт;
1Гбайт=1024 Мбайт1 млрд. байт.
Булева переменная – это переменная, принимающая значения из множества (0,1).
Булева функция – это произвольная функция, которая, как и ее аргументы, принимает значения из множества (0,1).
Множество всех булевых функций называется булевой алгеброй логики.
Логические элементы – это электронные устройства, реализующие простейшие двоичные операции (функции) над входными сигналами согласно правилам алгебры логики.
Наиболее распространено представление «0» и «1» различными уровнями потенциала, так называемая «потенциальная логика».
Различают: положительную логику, в которой логическому «0» соответствует низкий уровень потенциала, а логической «1» - высокий уровень потенциала. В отрицательной логике – наоборот.
Все рассуждения и выкладки будем рассматривать для положительной логики.
F= a+b =
Электромеханическим аналогом является следующая схема:
Здесь a и b нормально открытые контакты реле. Ток в нагрузке будет протекать тогда, когда хотя бы один контакт замкнут.
Часто логическая функция задается таблицей истинности, в которой записываются все возможные наборы значений аргументов (входных сигналов) и соответствующие им значения логической функции (выходных сигналов).
Элементы, реализующие функцию логического сложения, называются логическими элементами ИЛИ (дизъюнкторами). Графическое изображение содержит «1».
F=a∙b=
Электромеханический аналог имеет вид:
Здесь a и b нормально открытые контакты реле.
Таблица истинности:
Элементы, реализующие функцию логического умножения, называются логическими элементами И (конъюнкторами). Графическое обозначение в поле прямоугольника содержит знак «&».
3. Логическое отрицание (инверсия; функция НЕ; англ. «NOT») обозначается штрихом или чертой над обозначением аргумента. Вводится следующим образом:
F=ā F=
Моделью ячейки, реализующей функцию НЕ, может служить нормально закрытый контакт реле, включенный последовательно с нагрузкой.
Таблица истинности:
Логические элементы, реализующие функцию НЕ, называются инверторами.
В графическом обозначении окружность на входе (выходе) логического элемента обозначает инверсию входного (выходного) сигнала.
F2=a – логический повторитель.
Логическое выражение – это равенство, в левой части которого записано имя функции, а в правой части дано выражение, содержащее двоичные переменные, соединенные знаками логического умножения, сложения и инверсии.
Используются две формы записи:
Любая логическая функция может быть представлена в ДНФ или КНФ. При этом может существовать несколько равносильных ДНФ и КНФ.
ДНФ и КНФ форма представления логического выражения, в котором логическая функция может быть записана единственным образом – это:
СДНФ – совершенная ДНФ
СКНФ – совершенная КНФ
Логическое выражение в СДНФ представляет собой логическую сумму минтермов.
Минтерм – это простая конъюнкция, включающая все независимые переменные данной логической функции.
Простая конъюнкция – это логическое проведение, в котором каждая переменная входит один раз в прямом или инверсном виде. Она не должна содержать сумм и отрицаний нескольких переменных.
СКНФ представляет логическое произведение макстермов.
Макстерм – это простая конъюнкция, включающая все независимые переменные данной логической функции.
Простая дизъюнкция – это логическая сумма, в которой каждая переменная входит один раз в прямом либо инверсном виде. Простая дизъюнкция не должна содержать произведений двух и более переменных, либо отрицания суммы нескольких переменных.
Пример 1: логические выражения
Второе выражение – простая конъюнкция, 1,3 – нет.
Пример 2: даны логические выражения
Алгебра логики и ее законы применяются для математического исследования цифровых устройств, их синтеза и структурной минимизации.
а+0=а а·0=0
а+1=1 а·1=а
0· a·b·…·z=0
1+a+b+…+z=1
a+a=a или a+a+a+….+a=a
a·a=a или a·a·a·…·a=a
a+b=b+a a·b=b·a
(a+b)+c=a+(b+c)=a+b+c
a·b·c=a·(b·c)=a·b·c
a·(b+c)=ab+ac
a+b·c=(a+b)(a+c)
доказательство: (a+b)(a+c)=aa+ab+ac+bc=a+cb+ac+bc=a(1+b+c)+bc=a+bc
т.к. 1+b+с=1
т.е. инверсия дизъюнкции есть конъюнкция инверсий, а инверсия конъюнкции – это дизъюнкция инверсии.
Другая запись правила де Моргана:
Законы отрицания справедливы для любого количества аргументов:
a+ab=a a(1+b)=a
В, более общем, виде: a+ab+ac+…+az=a.
Также имеет место другая редакция:
a(a+b)=a aa+ab=a+ab=a(1+b)=a
В более общем виде: a(a+b)(a+c)….(a+z)=a
Следствие из данных выражений:
Другая редакция имеет вид:
а) Для ДНФ выражений.
Если ДНФ содержит конъюнкцию, которая входит составной частью в другие конъюнкции этого выражения, то последние являются в нем избыточными и могут быть удалены из выражения без изменения значения.
б) Для КНФ выражений
Если КНФ содержит дизъюнкцию, которая входит составной частью в другие дизъюнкции этого выражения, то последние являются в нем избыточными и могут быть удалены из выражения без изменения ее значения.
Основными функциями булевой алгебры логики являются логические функции двух переменных F=f(a,b).
Для двух переменных – число возможных комбинаций значений 22 =4, а количество элементарных двоичных функций - 24 =16
|
Fi |
Название функции |
Значение функции |
Символ. обознач. |
Структурная формула |
|
|
F0 |
Нулевая функция |
F0= 0 при любых значениях а и b |
0 |
F0= |
|
|
F1 |
Инверсия а (функция НЕ) |
F1={ |
1 при а=0 0 при а=1 |
F1= |
|
|
F2 |
Инверсия b (функция НЕ) |
F2={ |
при b=0 0 при b=1 |
F2= |
|
|
F3 |
Дизъюнкция (функция ИЛИ) |
F3={ |
0 при а=b=0 1 в ост. случаях |
a+b |
F3=a+b |
|
F4 |
Конъюнкция (функция И) |
F4={ |
1 при а=b=1 0 в ост. случаях |
ab |
F4=ab |
|
F5 |
Повторение а (функция ДА) |
F5={ |
1 при а=1 0 при а=0 |
a |
F5=a |
|
F6 |
Повторение b (функция ДА) |
F6={ |
1 при b=1 0 при b=0 |
b |
F6=b |
|
F7 |
Запрет а |
F7={ |
0 при а=1 в при а=0 |
ba |
F7= |
|
F8 |
Запрет b |
F8={ |
0 при b=1 а при b=0 |
ab |
F8= |
|
F9 |
Штрих Шеффера (функция И-НЕ) |
F9={ |
0 при а=b=1 1 в ост. случаях |
a/b |
F9= |
|
F10 |
Стрелка Пирса (функция ИЛИ-НЕ) |
F10={ |
1 при а=b=0 0 в ост. случаях |
ab |
F10= |
|
F11 |
Импликация а |
F11={ |
0 при а=0; b=1 1 в ост. случаях |
ba |
F11= |
|
F12 |
Импликация b |
F12={ |
0 при а=1; b=0 1 в ост. случаях |
ab |
F12= |
|
F13 |
Неэквивалентность (исключающее ИЛИ) |
F13= |
1 при аb |
ab |
F13= |
|
F14 |
Равнозначность (эквивалентность) |
F14={ |
1 при а=b 0 при аb |
a~b |
F14= |
|
F15 |
Единичная функция |
F15= |
1 при любых а и b |
1 |
F15= |