Полная версия

Главная arrow Информатика arrow Вычислительная техника

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Общие сведения о булевой функции и способах ее представления

Введем некоторые определения и положения, необходимые для рассмотрения логических основ ЭВМ.

Известно, что ЭВМ оперируют с дискретными сигналами, которые принимают только два строго определенных значения: 0 либо 1 (двоичные сигналы).

Для обработки двоичных сигналов в ЭВМ используются цифровые устройства (ЦУ), реализованные на элементах 2-х видов:

  • - логических элементах (ЛЭ), выполняющих простейшие логические операции: И, ИЛИ, НЕ, И-НЕ, ИЛИ-HE и др.;
  • - запоминающих элементах (элементах памяти - ЭП), обеспечивающих хранение двоичных сигналов (триггеры и запоминающие устройства на их основе).

Схема соединения ЛЭ и ЭП, предназначенная для преобразования (обработки) и хранения дискретной информации, называется логической (цифровой) схемой (ЛС).

В общем случае ЛС содержит М входов и N выходов. Входные и выходные дискретные сигналы обозначаются буквами латинского алфавита: A,B,C,D,...,X,Y,Z.

Комбинация входных (выходных) переменных называется набором (ко-

дом).

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

Примеры БФ:

К основным операциям булевой алгебры (алгебры логики) относятся:

  • - логическое сложение (дизъюнкция);
  • - логическое умножение (конъюнкция);
  • - отрицание (инверсия).

Эти операции составляют булев базис и выполняются соответственно ЛЭ ИЛИ, И, НЕ.

Каждая из перечисленных логических операций имеет свой приоритет: в первую очередь выполняется инверсия над отдельными аргументами, далее - операции логического умножения и сложения и в последнюю очередь - отрицание над совокупностью переменных и общее отрицание. Знание последовательности выполнения логических операций в заданной (полученной) БФ позволяет построить соответствующую ей ЛС (именно в такой же последовательности соединяют ЛЭ).

Обычно БФ задается значением F, которое равно либо 0, либо 1 при всех возможных комбинациях входных сигналов (аргументов). При этом каждую конкретную комбинацию аргументов называют набором.

Набор записывается в виде двоичного числа, цифрами которого являются значения переменных, обычно расположенные в алфавитном порядке:

А, В, С ,..., X, Y, Z.

Например, вместо А=1, В=0, С=1 записывается набор в виде двоичного числа 101.

Номер набора - это десятичное число, являющееся эквивалентом данного двоичного числа: 101 [2j -» 5[ю].

Если в БФ п аргументов (разрядов), то для них можно записать 2" наборов, которые нумеруются от 0 до 2п-1. Так, в БФ 2-х аргументов (А,В) 4 набора (22) с номерами 0,1,2,3. При 3-х аргументах (А, В, С) имеем 8 наборов (23) с номерами от 0 до 7 и т.д.

Если значения БФ (0 или 1) заданы на всех 2" наборах, то такая функция является полностью определенной.

Если для некоторых наборов переменных значения БФ неизвестны, то она называется не полностью (частично) определенной. Это имеет место, когда по условиям работы цифрового устройства некоторые наборы заведомо невозможны. В таких случаях частично определенную БФ на этих наборах (или части наборов) можно доопределить (принять ее значения равными 0 либо 1). Условия, исходя из которых доопределяется БФ, называются факультативными (действия с такой функцией будут рассмотрены далее).

Рассмотрим способы представления БФ:

1. Словесный - оговаривается правило, по которому устанавливается соответствие значений БФ возможным наборам аргументов, т.е. словесно определяется логика работы разрабатываемого устройства.

Пример: БФ 3-х аргументов F(A, В, С) принимает значение 1, если не менее чем два аргумента равны 1 (в других случаях функция равна 0).

2. Табличный - БФ представляется в виде таблицы наборов в порядке возрастания их номеров. В случае полностью определенной БФ на каждом наборе устанавливается ее значение: F=0 либо F=1.

Примечание: Если БФ не полностью определена, то на соответствующих наборах в графе F ставится буква Ф (факультатив).

3. Алгебраический - БФ представляется аналитически, т.е. в виде математической (структурной) формулы, записанной с использованием символов логических операций.

Существуют 2 формы алгебраического представления БФ:

a) 1 форма - дизъюнктивная нормальная форма (ДНФ).

Она представляет собой сумму элементарных логических произведений, в каждое из которых аргумент или его отрицание входит не более 1 раза:

Частными случаями ДНФ БФ являются: 1-я стандартная форма (СДНФ), когда каждое слагаемое содержит одинаковое число (п) аргументов:

Полная стандартная 1 форма (ПДНФ) включает все возможные наборы для п аргументов (2П наборов):

Переход от таблицы к 1-й форме называют составлением структурной формулы по 1 (данная форма представления БФ чаще всего и используется в процессе синтеза ЦУ).

b) 2-я форма - конъюнктивная нормальная форма (КНФ).

Она представляет собой произведение элементарных логических сумм, в каждое из которых аргумент или его отрицание входит не более 1 раза:

Аналогично вводятся частные случаи КНФ:

СКНФ:

ПКНФ:

Переход от таблицы ко 2-й форме называют составлением структурной формулы по 0 (при синтезе ЦУ используется редко).

4. Числовой - сокращенная форма алгебраического представления БФ. Возможны 2 варианта соответствующие 1-й и 2-й стандартным формам.

a) числовое представление БФ в форме С ДНФ:

под знаком суммы (?) записываются в возрастающем порядке номера наборов (из таблицы) на которых F=l:

Если БФ не полностью определена, то под знаком суммы дополнительно перечисляются номера наборов с факультативными условиями:

b) числовое представление БФ в форме СКНФ:

под знаком произведения (П) записываются в возрастающем порядке номера наборов (из таблицы), на которых F=0:

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

5. Картой Карно

Для нанесения БФ на карту Карно (рабочую, незаполненную) необходимо:

a) записать БФ в 1-й стандартной форме алгебраическим или числовым способом,

b) на рабочей карте отыскать соответствующие слагаемым (наборам) клетки и записать в них 1 (остальные клетки оставить пустыми или записать в них 0).

Примечание-. Если БФ нс полностью определена и доопределяется в процессе синтеза ЦУ, то в этих клетках карты записывается буква Ф (факультативное условие). Карта Карно для функции 4-х переменных F(A,B,C,D) = ABCD v ABCD v ABCDv ABCD) приведена на рис. 3.1.

Карта Карно для 4-х переменных

Рис. 3.1 Карта Карно для 4-х переменных

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>