2020-04-12
206
Операции над множествами и основные логические операции, такие как отрицание, конъюнкция (умножение, пересечение), дизъюнкция (сложение, объединение) обладают свойством коммутативности относительно конъюнкции и дизъюнкции, и дистрибутивным законом конъюнкции относительно дизъюнкции.
Рассмотрим непустое множество 
– элементы этого множества. На множестве определено отношение равенства, отрицание, операции сложения и умножения. Отношение равенства будем записывать как 
, отрицание как 
, умножение как 
, или 
; сложение как 
, или 
.
Перечисленные операции подчиняются следующим законам.
Коммутативные законы: 
, 
.
Ассоциативные законы:
, 
.
Дистрибутивные законы:
, 
.
Законы идемпотентности: 
, 
.
Закон двойного отрицания: 
.
Законы де Моргана: 
, 
.
Законы поглощения: 
, 
.
Множество 
с определенными на нем операциями, подчиняющимися указанным законам, называется булевой алгеброй.
Алгебра логики и алгебра множеств – булевы алгебры.
Булева функция, или функция алгебры логики, является одним из основных объектов дискретной математики.
Булевы функции названы в честь Джорджа Буля, положившего начало применению математики в логике.
Определение 1. Булевой функцией (или функцией алгебры логики) от 
переменных называется любая функция 
, принимающая одно из двух значений 0 или 1, от переменных, каждая из которых принимает одно из двух значений 0 или 1.
Определение 2. Две булевы функции называются равными, если для любых одинаковых наборов значений переменных обе функции принимают одинаковые значения. Булевых функций одной переменной четыре, а двух переменных – шестнадцать и т. д. Число булевых функций от переменных равно 
.
Определим функции одной и двух переменных, которые называются элементарными функциями и с помощью которых можно определить функции большего количества переменных.
Составим таблицы истинности таких функций.
Таблица истинности булевой функции одной переменной:
| 
| 
| 
| 
|
| 0 1 | 0 0 | 0 1 | 1 0 | 1 1 |
Функции и называются константами – соответственно 0 и 1. Функция совпадает с переменной 
и называется тождественной 
. Функция принимает значения, противоположные значениям аргумента и называется отрицанием , обозначается 
: 
.
Таблица истинности булевой функции двух переменных:
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
|
| 0 0 1 1 | 0 1 0 1 | 0 0 0 0 | 0 0 0 1 | 0 0 1 0 | 0 0 1 1 | 0 1 0 0 | 0 1 0 1 | 0 1 1 0 | 0 1 1 1 | 1 0 0 0 | 1 0 0 1 | 1 0 1 0 | 1 0 1 1 | 1 1 0 0 | 1 1 0 1 | 1 1 1 0 | 1 1 1 1 |
| константа 0 | 
| 
|
| 
|
| 
| 
|  Стрелка Пирса
| 
| 
| 
| 
|  импликация
| | штрих Шеффера | константа 1 |
Следует отметить, что здесь к функциям двух переменных относятся и такие, которые в действительности зависят от одной переменной.
1. Функции и представляют собой константы 0 и 1.
2. Функции , , , 
существенно зависят только от одной переменной: 
, 
, 
, 
.
3. Остальные функции существенно зависят от двух переменных, и для них есть названия и обозначения:
а) функция 
называется конъюнкцией;
б) функция 
называется дизъюнкцией;
в) функция 
называется эквивалентностью;
г) функция 
называется суммой по модулю два, или суммой Жегалкина;
д) функция 
называется конверсией;
е) функция 
называется импликацией;
ж) функция 
называется штрихом Шеффера;
и) функция 
называется стрелкой Пирса;
к) функции 
и логически несовместимы с импликацией и конверсией и называются функциями запрета.
Для булевых функций справедливы равенства, аналогичные формулам, указанным для высказываний.
1. Функции: конъюнкция, дизъюнкция, сумма по модулю два, стрелка Пирса, штрих Шеффера обладают свойством коммутативности.
2. Функции: конъюнкция, дизъюнкция, сумма по модулю два обладают свойством ассоциативности и свойством дистрибутивности.
3. Закон де Моргана: 
; 
.
4. Закон двойного отрицания: 
.
5. Выражение дизъюнкции через конъюнкцию и суммы по модулю два: 
.
6. Выражение дизъюнкции через импликацию: 
.
7. Выражение отрицания через штрих Шеффера, стрелку Пирса, сумму по модулю два и эквивалентность: 
.
8. Выражение конъюнкции через штрих Шеффера:
.
9. Выражение дизъюнкции через стрелку Пирса:
.
10. Закон поглощения: 
; 
.
11. Закон склеивания: 
.
12. Для функций конъюнкции, дизъюнкции и сумме по модулю два справедливы следующие тождества:
 ;
 ;
 ;
 ;
|  ;
 ;
 ;
 ;
|  ;
 ;
 ;
 .
|
13. Для функций конъюнкции и дизъюнкции справедливы тождества: 
; 
.
Для доказательства справедливости любых из приведенных тождеств нужно составить таблицы истинности для булевых функций.
Булеву функцию любого числа переменных можно задать формулой, содержащей функции одной и двух переменных посредством подстановки одних булевых функций вместо переменных в другие булевы функции, т. е. посредством суперпозиции булевых функций.
