15. Основные зависимости между булевыми функциями.
Аргументы |
Функция |
Название функции |
||||
Х1 |
0 |
0 |
1 |
1 |
||
Х2 |
0 |
1 |
0 |
1 |
||
|
0 |
0 |
0 |
0 |
у1=0 |
Константа 0 |
|
0 |
0 |
0 |
1 |
у2=х1*х2 |
Конъюнкция, операция И |
|
0 |
0 |
1 |
0 |
|
Отрицание импликации (совпадение с запретом) |
|
0 |
0 |
1 |
1 |
у4=х1 |
Тождественность (тавтология) х1 |
|
0 |
1 |
0 |
0 |
у5=х2←х1=х2→х1=х1*х2 |
Отрицание обратной импликации |
|
0 |
1 |
0 |
1 |
у6=х2 |
Тождественность (тавтология) х2 |
|
0 |
1 |
1 |
0 |
|
Исключающее ИЛИ (сумма по модулю 2) |
|
0 |
1 |
1 |
1 |
у8=х1 v х2 |
Дизъюнкция, операция ИЛИ |
|
1 |
0 |
0 |
0 |
|
Стрелка Пирса (операция ИЛИ–НЕ) |
|
1 |
0 |
0 |
1 |
у10=х1~х2=х1х2 v х1х2 |
Равнозначность, эквивалентность |
|
1 |
0 |
1 |
0 |
у11=х2 |
Отрицание (инверсия) х2 |
|
1 |
0 |
1 |
1 |
у12=х2→х1=х1 v х2 |
Импликация от х1 к х2 |
|
1 |
1 |
0 |
0 |
у13=х1 |
Отрицание (инверсия) х1 |
|
1 |
1 |
0 |
1 |
у14=х1→х2=х1 v х2 |
Обратная импликация |
|
1 |
1 |
1 |
0 |
|
Штрих Шеффера |
|
1 |
1 |
1 |
1 |
у13=1 |
Константа 1 |
у3=х1←х2=х1→х2=х1*х2
у7=х1
х2=х1х2
v х1х2
у9=х1↓х2=х1
v х2
у15=х1/х2=х1х2
16. Основные законы булевой алгебры.
Законы булевой алгебры:
Переместительный:
х1*х2=х2*х1
х1 v х2=х2 v х1
Сочетательный:
х1*(х2*х3)=(х1*х2)*х3=х1*х2*х3
х1 v (х2 v х3)=(х1 v х2) v х3=х1 v х2 v х3
Распределительный:
х1*(х2 v х3)=х1*х2 v х1*х3
х1 v (х2*х3)=(х1 v х2)*(х1 v х3)
Закон инверсии (закон Де Моргана):
х
1*х2=х1
v х2
х 1 v х2=х1*v х2
Закон повторения (тавталогии):
х*х=х
х v х=х
Закон двойной инверсии:
х =х
Закон множества:
х*0=0 х v 0=х
х*1=х х v 1=1
Закон дополнительности:
х *х=0
х v х=1
Закон поглощения:
х1 v х1*х2=х1
х1*(х1 v х2)=х1
Закон склеивания:
( х1 v х2)*(х1 v х2)=х1
х 1*х2 v х1*х2=х1