ФУНКЦИЙ АЛГЕБРЫ ЛОГИКИ

Date: 2015-10-07; view: 959.

Практически все функциональные узлы ЭВМ (АЛУ - арифметико-логические устройства, УУ - устройства управления) построены на базе аппарата алгебры логики. Основу этой алгебры составляют логические функции и логические аргументы.

Логические функции выполняют преобразования над логическими аргументами.

Основными базовыми функциями алгебры логики являются функция отрицания НЕ, функция конъюнкции (логического умножения) И и дизъюнкции (функция логического сложения) ИЛИ. Названия этих функций отражают вид преобразования, которые они осуществляют (выполняют) над логическими аргументами.

Так, функция отрицания НЕ выполняют операцию инвертирования значения аргумента, т.е. осуществляет преобразование значения аргумента из 1 в 0, и наоборот из 0 в 1.

Функция конъюнкции выполняет преобразование (операцию) логического умножения аргументов.

Функция дизъюнкция выполняет преобразование (операцию) логического сложения аргументов.

Указанные выше функции называют базовыми потому, что через эти функции можно выразить любые другие логические функции. Мы уже знаем, что для двух логических аргументов можно организовать 16 разновидностей логических функций.

Одной из 16-ти логических функций от двух аргументов является функция суммирования по модулю 2. Установленная (принятая) форма записи этой функции такая:

f(X1,X2)=X1 X2, где знак означает операцию суммирования по модулю 2.

Таблица истинности функции суммирования по модулю 2 имеет вид:

Таблица N

Покажем как функция суммы по модулю 2 может быть выражена через базовые функции И, ИЛИ, НЕ. Составим по данным таблицы истинности СДНФ для этой функции, состоящей из аргументов и их отрицаний имеющихся в таблице, объединенных знаками логических операций И, ИЛИ.

Т.к. два выражения выполняют одинаковые преобразования, то они являются эквивалентными. Следовательно, можно написать:

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

Т.к. через базовые функции можно выразить любые другие логические функции, включая функции от многих аргументов, то, можно сказать, что они являются универсальными в рамках теории булевой алгебры.

Для построения функциональных узлов ЭВМ, работа которых описывается сложными логическими функциями, были разработаны электронные схемы (логические элементы), которые на уровне электрических сигналов реализуют логические функции конъюнкции, дизъюнкции, отрицания (выполняют логические операции НЕ, И, ИЛИ).

Имея логическую функцию, которая описывает работу функционального узла ЭВМ и имея указанный выше набор логических элементов, можно осуществить аппаратную реализацию (аппаратное конструирование) этого функционального узла.

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

На структурной схеме логические элементы имеют общепринятые графические обозначения. На условные графические обозначения введены государственные стандарты. Так для условных графических обозначений логических элементов имеется ГОСТ 2.743-82. - Обозначения условные графические в схемах. Элементы цифровой техники. - Введен 01.07.83.

Согласно ГОСТ 2.743-82 логические элементы НЕ, И, ИЛИ изображаются следующим образом:

Разработку структурной схемы функционального узла ЭВМ покажем на примерах.

Пример 1. Пусть необходимо разработать функциональный узел для ЭВМ выполняющий операцию арифметического суммирования, т.е. необходимо разработать арифметическое устройство ЭВМ.

Арифметическое устройство (АУ) выполняет операцию арифметического суммирования над двумя числами представленной в двоичной системе счисления. В двоичном представлении чисел, подлежащих суммированию, каждый из разрядов 1-го и 2-го слагаемого, может иметь значение равное 0 или 1 и, следовательно, является логическими переменными. (Может быть отождествлен с логической переменной). Причем эти логические переменные являются независимыми величинами, т.е. являются логическими аргументами.

Полученная в результате выполнения арифметической операции сумма также является двоичным числом, каждый разряд которого может иметь значение 0 или 1 и, следовательно, могут быть также отождествлена с логической величиной.

Значение любого из разрядов, в полученной сумме, зависит от значений соответствующих разрядам в первом и втором слагаемых.

Следовательно, значение любого разряда суммы является зависимой логической величиной.

Логические функции, которые описывают операцию арифметического суммирования над i-тым разрядом двух чисел могут быть представлены следующей таблицей истинности:

Построим по данным таблицы истинности совершенную дизъюнктивную нормальную форму этой функции сумма:

Эта СДНФ логической функции минимизации не поддается и, следовательно, является минимизированной, т.е.

Построим по данным таблицы истинности совершенную дизъюнктивную нормальную форму функции. Перенос:

П(X1X2)_СДНФ=X1*X2.

Это СДНФ минимизации не поддается и, следовательно, является минимизированной. Поэтому, можно написать:

П(X1,X2)_СДНФ=П(X1,X2)_МДНФ=X1*X2.

По МДНФ функций S(X1,X2) и П(X1,X2) разработаем структурную схему узла, который бы на аппаратном уровне мог осуществлять преобразования описываемые функцией S(X1,X2) 4МДНФ 0.

Эта схема должна содержать в своем составе два логических элемента НЕ, три логических элемента И и один логический элемент ИЛИ.

Соединив между собой логические элементы требуемым образом, т.е. в соответствии с описанием МДНФ функций, получим следующую структурную схему:

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

1. Представим заданную логическую функцию алгебраическим способом в СДНФ форме:

2. Минимизируем - СДНФ логической функции. После минимизации будем иметь ее МДНФ, которая представлена выражением:

3. По минимизированной форме логической функции разработаем структурную схему функционального узла ЭВМ.

Для разработки структурной схемы необходимо:

ü проанализировать выражение МДНФ функции, описывающее работу функционального узла, и определить количество и виды операций из которого оно составлено. В данном примере МДНФ логической функции содержит две операции отрицания (инверсии), три операции логического умножения и две операции логического сложения.

ü в соответствии с имеющимся перечнем операции в СДНФ логической функции выбрать требуемое количество и типы логических элементов НЕ, И, ИЛИ. В данном примере, для аппаратной реализации функции нам потребуется иметь в наличии: два логических элемента НЕ, три логических элемента И и два логических элемента ИЛИ.

ü начертить структурную схему функционального узла, в которой логические элементы соединены между собой в соответствии с описанием логической функции.

Пример 3. Выше было показано, как можно представить логическую функцию посредством операций И, ИЛИ, и НЕ. Системы элементов в интегральном исполнении в своем наборе реализуют различные комбинации этих операций. Наибольшее распространение получили логические элементы, реализующие комбинации: И – ИЛИ, И – НЕ, ИЛИ – НЕ, И – ИЛИ – НЕ.

Элемент И – НЕ (операция «штрих Шеффера») представляет собой элемент И с инверсным выходом. Выход элемента имеет нулевое значение только в том случае, когда сигналы на всех его входах имеют единичное значение.

Элемент ИЛИ – НЕ выполняет логическую операцию, называемую «стрелка Пирса», и представляет схему ИЛИ с инверсным выходом. Выход элемента ИЛИ – НЕ имеет нулевое значение, если хотя бы один из его входов имеет единичное значение.

Например, синтезируем комбинационную схему, на которой реализуется переключательная функция Y=Σ(2,4,5,6,10,11,12,15) с помощью логических элементов И-НЕ.

Найдем минимальную дизъюнктивную нормальную форму (МДНФ) с использованием карты Карно изображенной на рис.5:

Y

Применим теорему Де Моргана:

По данному выражению строим электрическую принципиальную схему: