Двоичные переменные и булевы функции

Логические основы вычислительной техники

BCD-код с избытком 6 для одного из слагаемых

При сложении чисел с одинаковыми знаками неважно, к какому из слагаемых добавить 0110. Причем это равносильно добавлению 0011 к каждому слагаемому.

При суммировании чисел в коде с избытком 6 коррекция может понадобиться только в случае, когда сумма меньше 16. В остальных случаях (сумма больше 16) возникает перенос, удаляющий из тетрады 6 лишних единиц, и коррекции результата не требуется.

Результат должен быть без избытка.

Пример:

A = 169 0.0111 1100 1111

B = 378 0.0011 0111 1000

A + B = 547 0.1001 0100 0111

0110.

0.0101 0100 0111

Суммирование чисел с разными знаками производится в BCD-коде, но в сущности тоже с избытком 6.

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

Двоичные переменные могут принимать только два значения: 0 (ложь) и 1 (истина) − и обозначаются символами x₁, x₂, …, x_n. Двоичные (логические, булевы) переменные являются аргументами булевых (переключательных) функций.

Функция f, зависящая от n переменных x₁, x₂,...., x_n, называется булевой, или переключательной, если функция f и любой из ее аргументов x_i, (i = 1...n) принимают значения только из множества {0, 1}.

Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежат множеству { 0, 1 }. Множество { 0, 1 } обозначим через B.

Булеву функцию от n аргументов можно рассматривать как n -местную алгебраическую операцию на множестве B. При этом алгебра <B;Ω >, где Ω – множество всевозможных булевых функций, называется алгеброй логики (булевой алгеброй).

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

x₁ x₂... x_n-1 x_n f

0 0... 0 0 f(0,0,...,0,0)

0 0... 0 1 f(0,0,...,0,1)

0 0... 1 0 f(0,0,...,1,0)

0 0... 1 1 f(0,0,...,1,1)

..................

1 1... 0 1 f(1,1,...,0,1)

1 1... 1 0 f(1,1,...,1,0)

1 1... 1 1 f(1,1,...,1,1)

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

Таким образом, булевы функции на конечном множестве своих аргументов могут принимать значения 0 и 1 и обозначаются f(x₁,x₂, …,x_n). Булевы функции могут служить аргументами более сложных логических функций.

Способы задания булевых функций

Для задания произвольной булевой функции широко используются табличный (матричный) и аналитический способы. При табличном способе булева функция f (х₁,...,х_n) задается таблицей истинности (табл. 7), в левой части которой представлены все возможные двоичные наборы длины n, а в правой указываются значения функции на этих наборах.

Таблица 7

№ набора	х1х2х3	f
0 1 2 3 4 5 6 7	000 001 010 011 100 101 110 111	0 1 0 0 1 1 0 1

Под двоичным набором понимается совокупность значений аргументов х₁,х₂,...,x_n булевой функции f. Двоичный набор имеет длину n, если он представлен n цифрами из множества {0,1}. В табл. 7 представлены все двоичные наборы длиной 3. Иногда двоичные наборы из таблицы истинности булевой функции удобно представлять их номерами. Запишем аргументы х₁,х₂,...,x_n в порядке возрастания их индексов. Тогда любому двоичному набору можно поставить в соответствие целое десятичное число N, называемое номером набора. Например, двоичные наборы 011 и 101 имеют номера 3 и 5 соответственно. Булевы функции, зависящие от большого числа переменных, задавать таблицей истинности неудобно в силу ее громоздкости. Например, таблица истинности булевой функции 8 переменных будет содержать 2⁸ = 256 строк. Для задания функций многих переменных удобно использовать модификацию таблицы истинности. Рассмотрим способ построения такой таблицы истинности для функции n переменных. Множество из n переменных функции разбивается на два подмножества: х₁, х₂,..., х_j-1 и х_j, х_j+1,..., х_n. Переменными x₁, x₂,..., x_n отмечают строки таблицы истинности, задавая в каждой строке значение соответствующего двоичного набора длины j-1. Переменными x_j, x_j+i,..., x_n отмечают ее столбцы, задавая в каждом столбце значения соответствующего двоичного набора длиной n-j+1. Значение функции записывается в клетке на пересечении соответствующей строки и столбца (табл. 8).

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

Таблица 8

x1,x2,...xj-1	xj, xj+1,...,xn
00...0	0...1	...	11...1
00...0
00...1
...
11...1

Дата добавления: 2014-12-26