В законах описаны правила равенства (равносильности) функций. Функции считаются равными, если для любых комбинаций значений переменных их значения совпадают.
1) переместительный закон (закон коммутативности):
(От перестановки слагаемых сумма не меняется и от перестановки сомножителей произведение не меняется)
2) Сочетательный закон (закон ассоциативности)
(этот закон говорит о том, что операции одного приоритета можно вычислять как слева направо, так и справа налево)
3) Распределительный закон (закон дистрибутивности)
(Эти законы говорят о том, как раскрывать скобки. Первая форма этого закона аналогична закону обычной алгебры: , а вот вторая форма этого закона аналога в обычной алгебре не имеет, но эту форму можно получить из первой, заменив все сложения на умножения, а умножения на сложения.)
4) Законы двойственности, или инверсии (законы де Моргана)
(Эти законы говорят о том, что операцию логического сложения можно заменить на логическое умножение и наоборот).
Законы де Моргана справедливы для любого количества переменных.
Законы алгебры логики доказывают с помощью таблиц истинности.
Докажем один из законов:
A | B | C | A&B | |||||
Поскольку значения функций, стоящих слева и справа от знака равенства совпадают, следовательно функции равны.
Тождества
Правила поглощения и склеивания
Эти правила используют для упрощения логических функций. Доказываются эти правила с помощью законов и тождеств алгебры логики.
1)
Доказательство:
2)
Доказательство:
3) (отрицание и следующая за ним операция поглощаются)
Доказательство:
4) (отрицание и следующая за ним операция поглощаются)
Доказательство:
Задачи
1) Проверить, будет ли верным условие, записанное на С/C++:
F = (a>b) && (b>c) || (c<d) && (b<=c) при a = 5, b = 3, с = 3, d = 7.
Решение:
1) a > b à 1 2) b>c à 0 3) c < d à 1 4) b <= c à 1
5) F = 1 & 0 1&1 = 1
Ответ: для данных значений переменных условие верно.
2) При каких значениях переменной x условие, записанное на С/C++, будет верно: F =!(x > 8 || x < -3).
Решение:
Обозначим (x > 8) как A, а (x < -3) как B, тогда
= (x <=8) && (x>=-3)
Ответ: -3 <= x <= 8
3) Упростить условие: F = (x > y) && (x <= y || у > z)
Решение:
Обозначим (x > y) как A, тогда (x <= y) соответствует .
(y > z) обозначим как B.
Тогда: (использовали 4 правило поглощения)
Ответ: F = (x > y) && (y>z)
4) Решить уравнение относительно X:
Для решения уравнения необходимо выразить X через другие переменные, для этого нужно упростить выражение, содержащее X.
Когда стоит отрицание над выражением, обычно убирают отрицание, используя законы де Моргана:
Вынесем X за скобки, используя закон дистрибутивности: à
Ответ: (к сожалению не всегда ответ можно получить так просто, в более сложных случаях для решения уравнения анализируют таблицы истинности).
5) Упростить функцию:
Решение:
(использовали закон де Моргана)
(использовали правило , где вместо A используется , а вместо B - )
Ответ:
6) Упростить функцию:
Решение:
В первой скобке дают 1, а если в выражение входит хотя бы одна единица, то все это выражение равно единице.
Ответ: (знаки умножения можно опустить, что мы и будем делать дальше, чтобы сократить запись выражений)
7) Упростить функцию:
Решение:
=
(подчеркнутые выражения сокращаются, поскольку A&A = A)
(использовали правила: и )
Ответ: F = XY.
8) Упростить функцию:
Решение:
(подчеркнутые части выражения сокращаются на основе правила )
(в подчеркнутой части выражения выносим за скобки)
Ответ:
9) Упростить функцию:
Решение:
Когда над выражением стоит отрицание, можно сначала попробовать упростить выражение под отрицанием, а потом убирать отрицание:
, поэтому
аналогично
Ответ:
Переход от табличной формы функции
алгебры логики к аналитической