П2.2. Операции сложения и умножения

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

Перечислим свойства сложения и умножения в рамках булевой алгебры.

1) Коммутативность: А+В=В+А; АВ=ВА.

2) Ассоциативность: А+(В+С)=(А+В)+С; А(ВС)=(АВ)С.

3) Дистрибутивность: А(В+С)=АВ+ВС; А+ВС=(А+В)(А+С).

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

4) Идемпотентность (равносильность):

А+А=А=АА.

Для обоснования идемпотентности, обратим внимание на то что 0+0=0, но также должно быть 1+1=1, так как в булевой алгебре нет чисел, больших единицы. Кроме того очевидно, что 0·0=0 и 1·1=1.

5) Операции с константами:

А+0=А, А·1=А, А·0=0 и А+1=1.

Последняя операция обосновывается тем, что 1+1=1.

6) Поглощение:

А(А+В)=А+АВ=А.

Свойство поглощения становится понятным в следующей цепочке преобразований:

А(А+В)=АА+АВ=А+АВ=А(1+В)=А.

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

 

П2.3. Операция инверсии и законы де Моргана

Инверсной (дополнением) логической переменной А является логическая переменная , равная 1, когда А=0, и нулю, когда А=1. Логическая переменная и ее инверсия связаны соотношениями склеивания:

=1 и =0.

Кроме того, применение операции инверсии ведет к следующим следствиям:

=А, =0, =1.

Важнейшее значение в технических приложениях булевой алгебры имеют законы двойственности, или законы де Моргана (А. de Morgan, 1806-71):

1) инверсия суммы равна произведению инверсий слагаемых, входящих в состав данной суммы:

= ;

2) инверсия произведения равна сумме инверсий сомножителей, входящих в состав данного произведения:

= + .

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

Пример П2.1.

, поскольку и тождественно равны нулю.

 

П2.4. Булевы функции

Функцией логических переменных Х1, Х2,... Xn (булевой функцией) называется выражение

Y=f(Х1, Х2, … Хn),

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

Y0=0, Y1=Х, Y2= , Y3=1,

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

С точки зрения общепринятой в математике терминологии следовало бы применять обозначение НЕ-ИЛИ вместо ИЛИ-НЕ и НЕ-И вместо И-НЕ.

 

Таблица П2.1

Х0 Х1 1 0 1 0 1 1 0 0 Наименование функций Алгебраические выражения функций
Y0 0 0 0 0 Константа нуль Y0=0
Y1 0 0 0 1 Отрицание суммы (функция Пирса ИЛИ-НЕ) Y1=
Y2 0 0 1 0 Запрет по Х1 Y2=
Y3 0 0 1 1 Инверсия Х1(функция НЕ) Y3=
Y4 0 1 0 0 Запрет по Х0 Y4=
Y5 0 1 0 1 Инверсия Х0 (функция НЕ) Y5=
Y6 0 1 1 0 Неэквивалентность Y6=
Y7 0 1 1 1 Отрицание произведения (функция Шеффера И-НЕ) Y7=
Y8 1 0 0 0 Логическое произведение (конъюнкция, функция И) Y8=Х1Х0
Y9 1 0 0 1 Эквивалентность Y9=
Y10 1 0 1 0 Повторение Х0 Y10=Х0
Y11 1 0 1 1 Импликация Х1 и Х0 Y11=
Y12 1 1 0 0 Повторение Х1 Y12=Х1
Y13 1 1 0 1 Импликация Х0 и Х1 Y13=Х1+
Y14 1 1 1 0 Логическое сложение (дизъюнкция, ИЛИ) Y14=
Y15 1 1 1 1 Константа единица Y15=1

 

Булевы функции заданы в табл. П.2.1 двумя способами: с помощью таблиц истинности и с помощью алгебраических выражений. В таблицах истинности (называемых также таблицами задания) каждому набору аргумента Х0 и Х1 задано значение функции Yi. В общем случае таблицы истинности полностью определяют значение любой булевой функции, поскольку в них указываются значения функции для всех 2n возможных наборов аргументов (n – количество аргументов заданной функции). Однако при n³5 таблицы истинности становятся громоздкими и употребляются редко. Алгебраические выражения позволяют получить компактную запись булевых функций с помощью операций инверсии, сложения и умножения. Переход от таблицы истинности к алгебраическому выражению может быть осуществлен путем формирования алгебраического выражения в виде суммы произведений аргументов или их инверсий, называемого дизъюнктивной нормальной формой (ДНФ) булевой функции. Для получения ДНФ необходимо для каждого единичного значения функции, заданного в таблице истинности, сформировать произведение аргументов и их инверсий по правилу: в формируемое произведение ставится сам аргумент, если его значение в таблице истинности равно единице, но ставится инверсия, если значение аргумента в таблице истинности равно нулю. ДНФ формируется в виде суммы полученных описанным образом произведений.

Пример П2.2. Записать по таблице истинности выражение функции Y9 из табл. П2.1.

Решение. Единичным значениям функции Y9 соответствуют два набора аргументов:

1) Х0=1, Х1=1;

2) Х0=0, Х1=0.

Следовательно, ДНФ функции Y9 должна иметь вид

Y9=Х1Х0+ .

Полученные ДНФ следует по возможности упростить, применяя операции склеивания и поглощения. Рекомендуем получить по таблице истинности выражение функций Y5 и Y14 (см. табл. П3.1.) и упростить их до выражений, приведенных в таблице П3.1.

 

Приложение 3. Символы и функции стандартного кода ISO-7 для ЧПУ (ГОСТ 20999–83)