Полная версия

Главная arrow Информатика arrow Вычислительная техника

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Основные теоремы алгебры Буля

В этом параграфе рассматриваются основные теоремы, относящиеся к выполнению операций в различных их сочетаниях над различным числом переменных. Доказательство этих теорем производится с использованием правил выполнения основных операций ИЛИ, И, НЕ. Переменная может принимать только два значения, поэтому для доказательства можно применять метод подстановки всех возможных комбинаций значений переменных (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 справедливы при любом числе переменных

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>