П2.1. Объекты булевой алгебры

Булева алгебра представляет в символическом виде, принятом в математике, законы и соотношения формальной логики. Булева алгебра названа по имени английского математика Джорджа Буля (G. Boole, 1815-64), разрабатывавшего вопросы математической логики.

Все операции булевой алгебры производятся над математическими объектами, которые могут принимать только два значения. В общем виде эти два значения обозначают как I (Integer – нечто целое) и 0 (ноль – отсутствии чего-либо). При логическом анализе символы I и 0 применяются в смысле утверждения истинности (ДА) или ложности (НЕТ) некоторого высказывания. Символы I и 0 называют логическими булевыми значениями, причем символ I чаще всего заменяют символом 1. В этом случае единица является не единицей счета, а обозначением одного из двух возможных значений объектов булевой алгебры.

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

 

П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, Х₂,... X_n (булевой функцией) называется выражение

Y=f(Х₁, Х₂, … Х_n),

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

Y₀=0, Y₁=Х, Y₂= , Y₃=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 двумя способами: с помощью таблиц истинности и с помощью алгебраических выражений. В таблицах истинности (называемых также таблицами задания) каждому набору аргумента Х₀ и Х₁ задано значение функции Y_i. В общем случае таблицы истинности полностью определяют значение любой булевой функции, поскольку в них указываются значения функции для всех 2ⁿ возможных наборов аргументов (n – количество аргументов заданной функции). Однако при n³ 5 таблицы истинности становятся громоздкими и употребляются редко. Алгебраические выражения позволяют получить компактную запись булевых функций с помощью операций инверсии, сложения и умножения. Переход от таблицы истинности к алгебраическому выражению может быть осуществлен путем формирования алгебраического выражения в виде суммы произведений аргументов или их инверсий, называемого дизъюнктивной нормальной формой (ДНФ) булевой функции. Для получения ДНФ необходимо для каждого единичного значения функции, заданного в таблице истинности, сформировать произведение аргументов и их инверсий по правилу: в формируемое произведение ставится сам аргумент, если его значение в таблице истинности равно единице, но ставится инверсия, если значение аргумента в таблице истинности равно нулю. ДНФ формируется в виде суммы полученных описанным образом произведений.

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

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

1) Х₀=1, Х₁=1;

2) Х₀=0, Х₁=0.

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

Y₉=Х₁Х₀+ .

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

 

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

П3.1. Символы задания параметров рабочего режима

A – угол поворота вокруг оси X (A→ α );

B – угол поворота вокруг оси Y (B→ β );

C – угол поворота вокруг оси Z (C→ Γ → γ );

D – величина коррекции (Displacement);

E – номер кадра перехода;

F – величина подачи (Feed);

G – подготовительная функция (Geometry);

H – число повторений участка программы, заголовок (Heading);

I, J, K – параметры интерполяции или шаг резьбы параллельно осям X, Y, Z соответственно;

L– обращение к подпрограмме (Linkage);

M – вспомогательная функция управления электроавтоматикой (Mode);

N – номер кадра (Number);

P, Q – третьи функции перемещений, параллельных осям X, Y соответственно;

R – формальный параметр, регистр (Register);

S – скорость шпинделя, главного движения (Spindle);

T – функция инструмента (Tool);

U, V, W – вторые функции перемещений, параллельных осям X, Y, Z соответственно;

X, Y, Z – первичные перемещения относительно осей X, Y, Z соответственно.

Если символы A, B, C, D, E, P, Q, R, U, V, W не используются в значениях, указанных выше, они становятся неопределенными и могут быть использованы для специальных значений.

 

⇐ Предыдущая123456789

Поделиться: