Математический аппарат инженера - страница 29
Отрицание - функция у = f(х), принимающая значения 1, когда х = 0, и значение 0, когда х = 1; она обозначается у = x̅ (читается «не х»).
Дизъюнкция — функция у = f(x>1, x>2), принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0; она обозначается у = x>1 ∨ x>2 (читается «у = x>1 или x>2»).
Конъюнкция—функция у = f(x>1, x>2), принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1; она обозначается у = x>1 ∧ x>2 («у = x>1 и x>2»).
Таблицы для этих функций имеют вид:
3. Логические операции и формулы.Булевы функции можно рассматривать как логические операции над величинами, принимающими два значения - 0 и 1. Отрицание - это одноместная операция, а дизъюнкция и конъюнкция — двухместные операции. При этом выражения x̅ , x>1 ∨ x>2, x>1 ∧ x>2 являются логическими формулами.
Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив x>1 = a̅ и x>2 = b ∧ c из x>1 ∨ x>2,имеем ( a̅ ) ∨ (b ∧ c).
- 63 -
Каждая формула определяет некоторую булеву функцию. Ее значение при различных значениях переменных определяется на основании таблиц функций, приведенных в (2). Так, при а = 0, b = 1 и с = 0 имеем:
x>1 = a̅ = 0̅ =1, x>2 = b ∧ с = 1 ∧ 0 = 0 и x>1 ∨ x>2 = a̅ ∨ (b ∨ c) = 1 ∨ 0 = 1. Аналогично получаем значения функции и при других комбинациях значений аргументов.
Две функции (как и определяющие их формулы) считаются равносильными,если при любых значениях аргументов эти функции (формулы) принимают одинаковые значения. Равносильные функции соединяются знаком равенства, например: (х ∧ у) ∨ z̅ = (
Множество всех булевых функций вместе с операциями отрицания, конъюнкции и дизъюнкции образует булеву алгебру.
На основе определения основных операций нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры:
коммутативность
х ∨ y = y ∨ х, х ∧ y = y ∧ х;
ассоциативность
х ∨ ( y ∨ z) = (х ∨ y) ∨ z, х ∧ ( y ∧ z) = (х ∧ y) ∧ z;
дистрибутивность
х ∧ ( y ∨ z) = (х ∧ y) ∧ (х ∨ z), х ∨ ( y ∧ z) = (х ∧ y) ∧ (х ∨ z);
свойство констант
х ∨ 0 = x, х ∧ 1 = x;
свойство отрицания
х ∨ x̅ = 1, х ∧ x̅ = 0.
Приведенные свойства позволяют получить ряд других важных законов и тождеств уже без обращения к таблицам соответствия:
0̅ = 1; x ∨ 1 =1; x ∧ 0 = 0 и т. д.
- 64 -
Так, законы идемпотентности доказываются следующими преобразованиями:
х ∨ х = (х ∨ х) ∧ 1 = (х ∨ х) ∧ (х ∨ x̅ ) = х ∨ (х ∧ (х ∨ х)) = х ∨ 0 = х;
х ∧ х = (х ∧ х) ∨ 0 = (х ∧ х) ∨ (х ∧ x̅ ) = х ∧ (х ∨ x̅ ) = х ∧ 1 = х.
Используя полученные соотношения, имеем:
х ∨ 1 = x ∨ ( x ∨ x̅ ) = (х ∨ х) ∨ x̅ = х ∨ x̅ = 1; x ∧ 0 = x ∧ ( x ∧ x̅ ) = x ∧ x̅ = 0.
Доказательство законов поглощения имеет вид:
x ∨ (x ∧ y) = (x ∧ 1) ∨ (x ∧ y) = x ∧ (1 ∧ y) = x ∧ 1 = x;
x ∧ (x ∨ y) = (x ∨ 0) ∧ (x ∨ y) = x ∨ (y ∧ 0) = x ∨ 0 = x.
Соотношение
из х ∨ x̅ = 1 по закону коммутативности следует x̅ ∨ x = 1, откуда сравнением с
Интересно доказательство закона де Моргана. На основании свойств отрицания равенство функций x̅ ̅∨̅ ̅y̅ и x̅ ∧ y̅ должно означать, что
(х ∨ у) ∨ ( x̅ ∧ y̅ ) = 1 и (х ∨ у) ∨ ( x̅ ∧ y̅ ) = 0.
Действительно,
(х ∨ у) ∨ ( x̅ ∧ y̅ ) = ((х ∨ у) ∨ x̅ ) ∧ ((х ∨ у) ∨ y̅ ) = (( x ∧ x̅ ) ∨ y ) ∧ (x ∨ (y ∨ y̅ )) =
= (1 ∨ y) ∧ (x ∨ 1) = 1 ∧ 1 = 1, а также
(х ∨ у) ∧ ( x̅ ∧ y̅ ) = (х ∧ ∨ ( x̅ ∧ y̅ ) = (у ∧ ( x̅ ∧ y̅ ) = ((x ∧ x̅ ) ∧ y̅ ) ∨ ((y ∧ y̅ ) ∧ x̅ ) =
= (0 ∧ y̅ ) ∨ ( x̅ ∧ 0) = 0 ∨ 0 = 0.
Следовательно, соотношение x̅ ̅∨̅ ̅y̅ = x̅ ∧ y̅ доказано. Аналогично доказывается и второй закон.
Упрощение записи формул.Операции дизъюнкции и конъюнкции удовлетворяют законам коммутативности и ассоциативности. Поэтому если переменные или формулы связаны только посредством одной из этих операций, то их можно выполнять в лгсбом порядке, а формулы записывать без скобок. Например: