Элементы математического аппарата ЦС

1. Элементы математического аппарата ЦС 1.1 Основы булевой алгебры. Историческая справка. Английский математик Джордж Буль (1815 – 1864) опубликовал в 1848 г. работу "Математический анализ логики", а в 1854 г. "Исследование законов мышления", в которых изложил основы алгебры логики. Лишь в 1938 году были выполнены первые исследования по приложениям булевой алгебры к потребностям релейной техники. Их авторами были в нашей стране – В.И. Шестаков (диссертация "Некоторые математические методы конструирования и упрощения двухполюсных электрических схем "), а в США – Клод Шеннон (статья "Символический анализ электрических цепей с контактными выключателями"). В 50-х годах основным источником новых задач теории логического проектирования переключательных устройств стали потребности рационального построения электронных вычислительных машин. Благодаря привлечению крупных сил математиков и специалистов электронной техники были разработаны методы, ставшие классической основой теории логического проектирования. Современное состояние теории цифровых автоматов отражено в работах Д.Хоффмана, В.Квайна, Е.Вейча, М.Карно, В.М.Глушкова и др. Алгебра Буля имеет своей целью исследование различного рода ситуаций, которые задаются высказываниями. Высказыванием называется любое утверждение, о котором можно сказать, истинно оно или ложно. При этом полагается, что каждое высказывание в данный момент времени может быть либо только истинным, либо только ложным и не может быть одновременно и тем, и другим. Значение истинности высказывания может рассматриваться как двоичная(логическая) переменная, принимающая в каждой конкретной ситуации одно из двух значений: 1 – если высказывание истинно, 0 – если высказывание ложно. Логическая функция - это функция логических переменных, которая может принимать только два значения : 0 или 1. Высказывания могут быть простыми и сложными. Простым высказыванием называется такое высказывание, значение истинности которого не зависит от значений истинности двух высказываний. Сложным высказыванием называется высказывание, значение истинности которого зависит от значений истинности составляющих его простых высказываний. Таким образом, значение истинности сложного высказывания является двоичной (булевой) функцией значений истинности простых высказываний, играющих роль аргументов. Высказывания различной сложности могут образовываться из простых высказываний с помощью определенных логических связей (операций). В булевой алгебре рассматриваются не сами словесные высказывания и взаимосвязи между ними, а двоичные логические переменные (аргументы), отображающие ложность или истинность этих высказываний, и логические операции над ними. Так как значение истинности каждого высказывания является двоичной переменной, то это дает возможность применить методы алгебры логики для исследования схем, использующих двоичные сигналы. В этом случае алгебра логики оперирует не с высказываниями, а с сигналами, которые обозначаются как двоичные переменные Xn-1 , Xn-2 , …X1 , X0. Нумерацию переменных целесообразно осуществлять в соответствии со значениями разрядов двоичного числа, образуемого этими переменными при их позиционной записи. Значения этих переменных отождествляются со значениями входных сигналов, поступающих на схему. Связи между входными и выходными сигналами в цифровых схемах аналитически описываются логическими (булевыми) функциями. Таким образом, значение булевой функции f (Xn-1 ,Xn-2 ,...,X1 ,X0) будет соответствовать значению выходного сигнала цифровой схемы, на которую по ступают входные сигналы Xn-1 ,Xn-2 ,...,X1 ,X0 . 1.2. Основные операции алгебры логики Действия над двоичными переменными производятся по правилам логических операций. Между обычной алгеброй и алгеброй логики имеются существенные различия в отношении количества и характера операций, а также законов, которыми они подчиняются. Простейшими логическими операциями являются: отрицание (инверсия, операция НЕ); логическое умножение (конъюнкция, операция И); логическое сложение (дизъюнкция, операция ИЛИ). Более сложные логические преобразования всегда можно свести к указанным простейшим операциям. 1.3 Способы представления булевых функций. - словесное представление; - табличное представление (таблицы истинности или переходов); - аналитическое представление (сднф или скнф); - графическое представление (с помощью графов). 1.4 Основные правила и законы алгебры логики. Операции с константой: X v 0=X X v1=1 X ^ 0=0 X ^ 1=X Правило тавтологии: X v X v X….v X = X X ^ X ^ X….^ X =X Закон противоречия: X ^ X̅ = 0 Закон исключённого третьего: X v X̅ =1 Закон двойного отрицания: X̿ = X Переместительный (коммутативный) закон: XvY=YvX X^Y=Y^X Сочетательный (ассоциативный) закон: (XvY)VZ=Xv(YvZ) (X^Y)^Z=X^(Y^Z) Распределительный (дистрибутивный) закон: (X^Y)VZ=(X^Z)v(Y^Z) (X^Y)VZ=(XvZ)^(YvZ) Правило де Моргана: ________ _______ X v Y = X̅ ^ Y̅ X ^ Y = X̅ v Y̅ Закон поглощения: Xv(X^Y)=X X^(XvY)=X Закон исключения (склеивания): _ (X v Y ) ^ ( X v Y ) = Y ( X ^ Y ) v(X ̅ ^ Y ) = Y 1.5 Логические элементы Логический элемент НЕ: Техническая реализация этой функции инвертор на любом транзисторе работающий в ключевом режиме. Логический элемент ИЛИ: Y= X1 + X2 = X1 v X2 Техническая реализация этой функции - два параллельно соединенных ключа: Логический элемент И: Y = X1^X2 = X1&X2 = x1·x2 Логическое И (логическое умножение, конъюнкция, схема совпадений) Техническая реализация этой функции - два последовательно соединенных ключа: 1.6 Логический базис - три набора логических элементов И,ИЛИ,НЕ; - два набора И, НЕ; - два набора ИЛИ, НЕ; - один набор И- НЕ; - один набор ИЛИ-НЕ. Логический элемент И-НЕ (штрих Шеффера). Элемент 2И-НЕ, реализующий штрих Шеффера, обозначается по стандартам ANSI В европейских стандартах принято другое обозначение: Логический элемент ИЛИ-НЕ (стрелка Пирса). Логический базис И-НЕ (доказательство). 1.7 Этапы синтеза цифровых устройств 1.Разработка алгоритма по заданной физической задаче. 2.Таблица истинности (таблица переходов). 3. Алгебраическое выражение в формах СДНФ или СКНФ. 4.Минимизация алгебраического выражения. 5.Преобразование в заданный логический базис. 6.Составление логической схемы цифрового устройства.