Отрицание - функция у = f(х), принимающая значения 1, когда х = 0, и значение 0, когда х = 1; она обозначается у = x̅ (читается «не х»).

Дизъюнкция — функция у = f(x₁, x₂), принимающая значение 0 тогда и только тогда, когда оба аргумента имеют значение 0; она обозначается у = x₁ ∨ x₂ (читается «у = x₁ или x₂»).

Конъюнкция—функция у = f(x₁, x₂), принимающая значение 1 тогда и только тогда, когда оба аргумента имеют значение 1; она обозначается у = x₁ ∧ x₂ («у = x₁ и x₂»).

Таблицы для этих функций имеют вид:

3. Логические операции и формулы.Булевы функции можно рассматривать как логические операции над величинами, принимающими два значения - 0 и 1. Отрицание - это одноместная операция, а дизъюнкция и конъюнкция — двухместные операции. При этом выражения x̅ , x₁ ∨ x₂, x₁ ∧ x₂ являются логическими формулами.

Более сложные формулы получаются замещением входящих в них переменных другими логическими формулами, которые обычно заключаются в скобки. Например, положив x₁ = a̅ и x₂ = b ∧ c из x₁ ∨ x₂,имеем ( a̅ ) ∨ (b ∧ c).

- 63 -

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

x₁ = a̅ = 0̅ =1, x₂ = b ∧ с = 1 ∧ 0 = 0 и x₁ ∨ x₂ = a̅ ∨ (b ∨ c) = 1 ∨ 0 = 1. Аналогично получаем значения функции и при других комбинациях значений аргументов.

Две функции (как и определяющие их формулы) считаются равносильными,если при любых значениях аргументов эти функции (формулы) принимают одинаковые значения. Равносильные функции соединяются знаком равенства, например: (х ∧ у) ∨ z̅ = (

) ∧ z или ((х ∨ x̅ ) ∧ у) ∨ (у ∨ х) == х ∨ у. Равносильность функций проверяется по таблицам основных операций, причем необходимо сравнить их значения для всех комбинаций значений переменных.

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

На основе определения основных операций нетрудно убедиться в справедливости следующих тождеств (свойств) булевой алгебры:

коммутативность

х ∨ 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.

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

(законы де Моргана), х ∨ (х ∧ у) = х ∧ (х ∨ у) = х (законы поглощения) х ∨ х = х ∧ х = х (законы идемпотентности), а также тождества x ∨ (x̅ ∧ y) = x ∨ y; (x ∧ y) ∨ (x ∧ z) ∨ (x ∧ z̅ ); = (x ∧ z) ∨ (y ∧ z̅ ); x̅ = x; 1̅ = 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, откуда сравнением с

= 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̅ доказано. Аналогично доказывается и второй закон.

Упрощение записи формул.Операции дизъюнкции и конъюнкции удовлетворяют законам коммутативности и ассоциативности. Поэтому если переменные или формулы связаны только посредством одной из этих операций, то их можно выполнять в лгсбом порядке, а формулы записывать без скобок. Например:

((х₁ ∨ x₂) ∨ (х₃ ∨ x₄) ∨ х₅ = х₁ ∨ x₂ ∨ х₃ ∨ x₄ ∨ х₅,

а также (х₁ ∧ x₂) ∧ (x₃ ∧ (х₄ ∧ x₅) = х₁ ∧ x₂ ∧ x₃ ∧ х₄ ∧ x₅.

Если считать, что операция конъюнкции должна предшествовать операции дизъюнкции (конъюнкция связывает сильнее дизъюнкции), то можно опустить скобки, в которые заключены формулы со знаком конъюнкции. При наличии скобок в первую очередь должны выполняться операции внутри скобок, независимо от их старшинства. Обычно опускают также скобки, в которые заключены формулы со знаком отрицания.

Еще одно упрощение связано с символикой. Знак конъюнкции в формулах можно опустить и вместо х ∧ у писать ху. Операцию конъюнкции часто называют логическим умножением, а операцию дизъюнкции - логическим сложением.

С учетом приведенных условий запись существенно упрощается. Например, формуле (x ∧ (y ∧ z̅ )) ∨ (( x̅ ̅∨̅ ̅y̅ ) ∧ z) соответствует запись xyz̅ ∨ x̅ ̅∨̅ ̅y̅ z.

7. Переключательные схемы. В качестве одной из интерпретаций булевых функций рассмотрим электрическую схему, состоящую из источника напряжения (батареи), лампочки и одного или двух ключей (х₁ и x₂). Ключи управляются кнопками с двумя состояниями: кнопка нажата (1) и кнопка отпущена (0). Если в исходном состоянии ключ разомкнут, то при нажатии кнопки он замыкается.

- 65 -

Ключ может быть сконструирован и так, что в исходном состоянии он замкнут, тогда нажатие кнопки означает его размыкание, т. е. приводит к противоположному результату. Поэтому нормально замкнутые ключи обозначим через x̅₁ и x̅₂.

При соответствующих состояниях кнопок лампочка принимает одно из двух состояний: горит (1) и не горит (0). Состояния кнопок отождествляются со значениями булевых переменных х₁ и x₂, а состояние лампочки — со значением функций этих переменных.

Рис. 22. Переключательные схемы, соответствующие операциям отрицания (а), дизъюнкции (б) и конъюнкции (в)

Операции отрицания соответствует схема с одним нормально замкнутым ключом (рис. 22, а). Если кнопка нажата (х = 1), ключ разомкнут и лампочка не горит, т. е. f(х) = 0; при отпущенной кнопке (х = 0) ключ замкнут и лампочка горит, т. е. f(x) = 1. Операциям дизъюнкции и конъюнкции соответствуют схемы с двумя нормально разомкнутыми ключами (рис. 22, б, в). Легко убедиться, что в схеме рис. 22, б лампочка горит при нажатии хотя бы одной из кнопок, а в схеме рис. 22, в - только при нажатии обеих кнопок одновременно.