Элементы вычислительной техники. Марков Б.Г. - 7 стр.

                                                                                  7
   Теорема Моргана
    x1 ⋅ x 2 = x1 + x 2                 x1 + x 2 = x1 ⋅ x 2 .
   Операции с 0 и 1:
     x⋅0 = 0                               x+0= x
     x ⋅1 = x                              x + 1 = 1.
   Дистрибутивный          закон   x1+x2⋅       x3=(x1+x2)⋅     (x1+x3)    требует
пояснения. Раскроем скобки в правой части равенства:
(x1+x2)⋅ (x1+x3) = x1⋅ x1+x1⋅ x3+x1⋅ x2+x2⋅ x3 = x1+x1⋅ x3+x1⋅ x2+x2⋅ x3 =
x1(1+x3+x2)+x2⋅ x3=x1+x2⋅ x3.                                                     .
Равенство левой и правой частей доказано. Аналогично можно
доказать правила склеивания:
   x1⋅ (x1+x2) = x1⋅ x1+x1⋅ x2 = x1+x1⋅ x2 = x1⋅ (1+x2) = x1.
   Теорема      Моргана      основана      на    так    называемом        принципе
двойственности. Если функцию и аргументы поменять на их
отрицания, знак логического сложения заменить на знак логического
умножения,      знак      логического   умножения         заменить        на   знак
логического сложения, то равенство в уравнении, определяющем
функцию, не нарушится.
   Если     y = x1 + x 2 ,   то,   согласно        принципу     двойственности,

y = x1 ⋅ x 2 , если же y = x1 ⋅ x 2 , то        y = x1 + x 2 . Это и доказывает
теоремы Моргана.


   Вопросы для самопроверки
   1.1. Чему равно число наборов аргументов при числе аргументов
равном 2, 3, n?
   1.2. Каково общее количество булевых функций двух аргументов,
трех аргументов, n аргументов?
   1.3. Чему равна логическая сумма двух единиц?
   1.4. Запишите таблицу истинности для функции ИЛИ-НЕ.
   1.5. Запишите таблицу истинности для функции И-НЕ.
   1.6. Докажите, что а1+а2⋅ а3 = (а1+а2) ⋅ (а1+а3).