Основные теоремы алгебры Буля
В этом параграфе рассматриваются основные теоремы, относящиеся к выполнению операций в различных их сочетаниях над различным числом переменных. Доказательство этих теорем производится с использованием правил выполнения основных операций ИЛИ, И, НЕ. Переменная может принимать только два значения, поэтому для доказательства можно применять метод подстановки всех возможных комбинаций значений переменных (0 и 1).
Теоремы для одной переменной
Эти теоремы охватывают все случаи операций над переменной X и константами 0 и 1:
Произведём доказательство некоторых теорем.
Теорема 2. При X =0 X vl = 0vl = l. Если же Х=1,то Xv1 = 1v1 = 1,h тем самым мы доказываем, что X v 1 = 1.
Теорема 8. При X = 0, X = 1 и поэтому ХлХ=0л1 = 0. Если же, X = 1, то X = 0 и X а X =1л0 = 0. Тем самым мы доказываем, что X л X = 0.
Теоремы для двух и более переменных
Теоремы даются в двух вариантах: а) для логического сложения;
- б) для логического умножения.
- 10. Переместительный закон, имеющий такой же смысл, как и в обычной
алгебре
Теорема справедлива при любом числе переменных. Она показывает, что результат операции ИЛИ и И не зависит от порядка написания переменных, то есть не зависит от того, какие входные сигналы к каким клеммам подводятся.
11. Сочетательный закон, аналогичный закону обычной алгебры
12. Распределительный закон
Теорема 12,а означает, что в алгебре Буля, так же как и в обычной алгебре, можно раскрывать скобки и выносить общие сомножители за скобки. Доказательство этой теоремы можно привести подстановкой всех значений переменных.
Для доказательства теоремы 12,6 воспользуемся принципом двойственности. Для этого в теореме 12,а X, Y, Z заменим их отрицаниями, знак «V» заменим на знак «•» и наоборот. Равенство при этой замене сохраняется и, следовательно, теперь имеем
Введём новые обозначения: Х = А, Y = B, Z = C. Тогда
Значение функции не зависит от её обозначения и последнее выражение соответствует теореме 12,6.
13. Закон поглощения
Доказательство теоремы 13а. На основании теоремы 12,а общий множитель X можно вынести за скобки. Тогда получим ХуХлУ = Ха(КК). Согласно теореме 2 (1 v Y) = 1 . Следовательно, X v X aY - X л (1 v У) = X л 1 = X , что и является доказательством теоремы 13,а.
Теорема 13,6 доказывается с использованием принципа двойственности.
Докажем теорему 14,а. На основании теоремы 12,а раскроем скобки (X vY)aY = X aYv X л7 . Так как Y aY = О И XaKvO=XaT, то (X v Y) a Y = X a Y .
15. Закон склеивания
Докажем указанные теоремы: XaYvXaY = Ya(XvX). Так как X л X = О и Y а 1 = Y , то X aYv X aY = Y. Соответственно,
(Xvr)A(Xvr) = XAXvXAFvXArvrAy = OvyA(XvXvr) = FA(lvK) = r, что и требовалось доказать.
16. Теоремы де Моргана
Доказательство теоремы 16,а. Пусть задана функция F -XvY . В соответствии с принципом двойственности получим F = X a Y . С другой стороны, взяв отрицание от левой и правой частей исходной функции F, получим выражение F = х v У. Сравнивая выражения для F, приходим к выводу, что X v Y = X л Y
Аналогично доказывается теорема 16,6.
Теоремы 16,а и 16,6 справедливы при любом числе переменных
В алгебре логики операции выполняются только над логическими высказываниями. Высказывания могут быть простыми и сложными. Простые высказывания называют логическими переменными, а сложные - логическими функциями этих переменных. Высказывания оценивают только по их истинности или ложности. В алгебре логики имеются основные законы для одной и для двух переменных.
