Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Формы представления логических функций



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

3.7.1. Словесная, табличная и аналитическая формы. Любая логическая функция может быть представлена в виде словесного описания. Например, логическая функция Пирса (стрелка Пирса) словесно может быть описана так: значение функции Пирса равно 1 только тогда, когда обе входные переменные х1, и х2 равны нулю, при любых других значениях входных переменных значение функции Пирса равно 0.

Эту же функцию можно представить в табличной форме — в виде таблицы истинности или карты Карно.

Таблица 1

Таблица истинности логической функции Пирса

Номер набора x1 x2

 

Таблица истинности (табл. 1) и карта Карно содержат все четыре возможных входных набора и значения функции, соответствующие каждому из них. Карта Карно для логической функции двух переменных (рис. 1) представляет собой квадрат, разделенный на четыре ячейки, по одной на каждый входной набор. Пере­менная х1 связана со строками карты, а переменная х2 — со столбцами. Следовательно, ячейка, расположенная слева вверху, соответствует входному набору (00), а справа внизу — входному набору (11). Представление логической функции на карте Карно производится в соответствии с таблицей истинности. Если функция при входном наборе (00), то этот факт отражается на карте Карно записью в левую верхнюю ячейку единицы (рис. 1, а). Остальные ячейки остаются незаполненными. Нулями заполняют ячейки карты Карно, соответствующие входным наборам, при которых (рис. 1, б).

    x2       x2
         
x1     x1  
     

 

а б

Рис. 1. Карта Карно для логической функции двух переменных

 

Устройство, реализующее действия над двоичными числами, можно рассматривать как логический функциональный преобразователь с п входами и т выходами (рис. 2), на входы которого подаются исходные двоичные числа, а на выходе получается результат преобразования также в виде двоичного числа. Работа устройства состоит в том, что при поступлении на его вход двоичного числа Р (т.е. комбинации нулей и единиц, общее количество которых равно п)на выходе образуется выходное двоичное число Q (т.е. комбинация нулей и единиц, общее количество которых равно т). Если работа устройства полностью определяется только входным двоичным числом, то она может быть определена для всех входных чисел (всего таких двоичных чисел может быть z = 2n) следующим образом: входу Р1 соответствует выход Q1, входу Р2 — выход Q2, входу Pz — выход Qz.

Значение выходного числа определяется конкретным сочетанием значений всех п разрядов входного двоичного числа, которое называется двоичным набором. Каждому набору на входе устройства будет соответствовать 0 или 1 на определенном выходе. Для описания работы такого устройства используется математический аппарат алгебры логики, или булевой алгебры. Функция алгебрылогики — это функция, однозначно определяющая соответствие каждого двоичного набора 0 или 1. Таким образом, двоичные наборы являются наборами значений аргументов функции алгебры логики. Количество возможных различных наборов равно максимальному числу, которое может быть изображено с помощью двоичных разрядов, т.е. 2n.

Любую функцию алгебры логики, зависящую от п аргументов, можно задать в виде таблицы с 2n строками. В этих строках записывают все возможные двоичные наборы значений аргументов x1, х2, …, хп и указывают значения функции f(x1, х2, …, xn), которые она принимает при каждом наборе (т.е. 0 или 1). Такая таблица, как уже было отмечено, называется таблицей истинности.

Для полного определения функции не обязательно задавать ее значения во всех наборах, достаточно определить либо все наборы, обращающие ее в 0, либо все наборы, обращающие ее в 1.

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

3.7.2. Геометрическая (кубическая) форма. Эта форма представления логических функций особенно удобна при более чем двух переменных. В геометрическом смысле каждый двоичный набор (х1, х2, ..., х„), где хi,- — это 0 или 1, можно рассматривать как n-мерный вектор, определяющий точку n-мерного пространства. Исходя из этого все множество наборов, для которых определена функция п переменных, представляется в виде вершин n-мерного куба. Отмечая точками вершины, в которых функция имеет единичные значения, получают ее геометрическое представление. Например, функция Y= v (3, 4, 5, 6, 7) геометрически представляется, как показано на рис. 3, а.

На основе геометрических представлений строятся кубические представления логических функций, в которых используются элементы n-мерных кубов. Геометрически каждому набору (х1, х2, … хn) соответствует вершина n-мерного куба с данными координатами. Каждую вершину, на которой функция принимает единичное значение, принято называть0-кубом (нулевым кубом). Множество 0-кубов образует нулевой кубический комплекс К0. Например, для функции Y= v (3, 4, 5, 6, 7) нулевой кубический комплекс имеет вид К0 = {011, 100, 101, 110, 111} и в данном случае состоит из пяти 0-кубов, каждый из которых соответствует определенной вершине трехмерного куба (рис. 3, а).

Если два 0-куба из комплекса К0 различаются только одной координатой, то они образуют один 1-куб (единичный куб). Он представляется общими элементами 0-кубов, а на месте координаты, по которой различаются 0-кубы, указывается символ «-», обозначающий независимую координату. Например, два 0-куба 100, 101 различаются только третьей координатой и, следовательно, образуют единичный куб 10-, которому соответствует ребро трехмерного куба. Все множество единичных кубов функции об­разует единичный кубический комплекс Кх. Для функции Y= v (3, 4, 5, 6, 7) он состоит из пяти 1-кубов: К{ = {-11, 10-, 1-0, 1-1, 11-} и определяет все множество ребер, на которых функция 7прини-мает единичные значения (рис. 3, б).

Если два единичных куба из комплекса К1 имеют общую независимую координату и различаются только одной координатой, то они образуют один 2-куб (двоичный куб). Его запись состоит из общих компонент 1-кубов, а координата, принимающая различные значения в 1-кубах, обозначается в 2-кубе как независимая координата «-» (пробел). Например, два единичных куба 1-0 и 1-1 образуют один двоичный куб 1--. Для рассматриваемой функции Y комплекс имеет вид К2 = (1--) и состоит из одного двоичного куба, соответствующего грани трехмерного куба (рис. 3, в). Размерность куба определяется числом независимых координат (символов «-»).

Объединение кубических комплексов K0, К1, … Кn функции f(x1, х2, …, хn) образует кубический комплекс функции K(f)

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

 

Законы алгебры логики

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

Сочетательный закон:

;

При выполнении одинаковых логических действий можно из­менять их последовательность, для чего ставить скобки иным спо­собом.

Переместительный закон:

;

Этот закон справедлив для произвольного числа переменных. Последовательность одинаковых действий над аргументами мож­но изменять.

Распределительный закон:

;

Распределительный закон умножения по отношению к сложе­нию имеет такой же вид, как и для алгебраических умножения и сложения, а для сложения по отношению к умножению является специфичным для алгебры логики и не имеет аналога в обычной алгебре. Подобно переместительному закону, распределительный справедлив для произвольного числа аргументов. Благодаря неко­торому сходству законов обычной алгебры и алгебры логики ло­гическую функцию дизъюнкция называют логическим сложени­ем, а логическую функцию конъюнкция называют логическим умножением.

Из распределительного закона могут быть получены следу­ющие формулы:

; .

Справедливы также следующие тождества:

Связь между дизъюнкцией и конъюнкцией реализуется с по­мощью операции инверсии (отрицания) и определяется законом двойственности (правилом, или формулами, де Моргана):

;




©2015 studenchik.ru Все права принадлежат авторам размещенных материалов.