Логические (Булевы) функции

Рассмотрим функции одной переменной y = f(x). Пронумеруем эти функции (их четыре) и расположим в виде таблицы:

Видно, что f₀(х) = 0, a f₃(х) = 1, т.е. эти две функции не зависят от х, f₁(х) = х, т.е. она не меняет аргумента. Функция f₂(х) действительно содержательная функция. Она принимает значения, противоположные значениям аргумента, обозначается и называется отрицанием.

Рассмотрим функции двух переменных y = f(x₁, x₂).

Число этих функций равно 2⁴ = 16. Пронумеруем и расположим их в естественном порядке.

Рассмотрим более подробно эти функции. Две из них f₀ = 0 и f₁₅ = 1 являются константами. Функции

, , ,

являются по существу функциями одной переменной.

Наиболее важные функции двух переменных имеют специальные названия и обозначения. Заметим, что эти обозначения не всегда общеприняты.

Перечислим семь важнейших функций.

1. Конъюнкция (функция И)

.

Конъюнкция (логическое умножение) переменных x₁ и х₂ равна лог. 1 в том случае, когда и x₁ и х₂ равны лог. 1 (отсюда и возникло название операции логическое И).

Конъюнкция – это фактически обычное умножение (нулей и единиц). Иногда эту функцию обозначают x₁ & x₂ или x₁ x₂.

2. Дизъюнкция (функция ИЛИ)

.

Дизъюнкция (логическое сложение) переменных x₁ и х₂ равна лог. 1, если или x₁ или х₂ равна лог. 1 (отсюда название операции логическое ИЛИ). В тех случаях, когда число переменных больше двух, их конъюнкция равна лог. 1 при равенстве лог. 1 всех переменных; дизъюнкция равняется лог. 1, если хотя бы одна из переменных имеет значение лог. 1.

3. Импликация (следование)

.

Иногда импликацию обозначают x₁ כ х₂ или x₁ → х₂ (читается “из x₁ следует х₂”).

Это очень важная функция, особенно в логике. Ее можно рассматривать следующим образом: если x₁ = 0 (т. е. x₁ “ложно”), то из этого факта можно вывести и “ложь”, и “истину” (и это будет правильно), если х₂ = 1(т.е. х₂ “истинно”), то истина выводится и из “лжи” и из “истины”, и это тоже правильно. Только вывод “из истины ложь” является неверным. Заметим, что любая теорема всегда фактически содержит эту логическую функцию.

4. Сложение по модулю 2, Исключающее ИЛИ (здесь и далее, если не оговорено противное, знаком “+” мы будем обозначать такое сложение):

.

5. Эквивалентность или подобие ~

.

Эта f₉ = 1 тогда и только тогда, когда х₁ = х₂.

6. Штрих Шеффера

.

Иногда эту функцию называют “НЕ И” (так как она равна отрицанию конъюнкции).

7. Стрелка Пирса (иногда эту функцию называют штрих Лукасевича)

.

Эта функция является отрицанием дизъюнкции, и поэтому иногда ее называют “не ИЛИ”.

Заметим, что свойства последних двух функций похожи между собой и, может быть, поэтому в литературе их часто путают (т. е. называют f₈ штрихом Шеффера, а f₁₄ – стрелкой Пирса).

Три оставшиеся функции, (f₂ , f₄ и f₁₁) особого значения в дискретной математике не имеют.

Операцию отрицания называют инверсией или дополнением. Для ее обозначения используют черту над соответствующим выражением. Операция определяется следующими постулатами:

если х = 1, то = 0, если х = 0, то = 1.

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

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

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. ;

8. ;

9. ;

10. ;

11. ;

12. ;

13. ;

14. ;

15. ;

16. ;

17. ;

18. ;

19. ;

20.

21. ;

22. ;

23.

Справедливость всех перечисленных теорем может быть до-казана непосредственной подстановкой.