1.8 Свойства бинарных операций

Ассоциативной бинарной операцией называется операция, если она обладает свойством (aφb)φc = aφ(bφc). Ассоциативность позволяет записывать последовательность таких операций без скобок: aφbφc . Ср. в арифметике формулы a+b+c, abcd. Примером ассоциативных операций служат объединение и пересечение множеств. Операция деления не ассоциативна: (24:3):4 = 2, тогда как 24:(3:4) = 24: 3/4 = 32. Также не ассоциативно вычитание. Проверьте это. Поэтому для бесскобочной записи 20-5-7 принято специальное соглашение: она означает (20-5)-7, но не 20-(5-7).

Коммутативной бинарной операцией называется операция, обладающая свойством перестановочности: aφb = bφa .

Ассоциативными и коммутативными являются операции max(X,Y) и min(X,Y) на множестве чисел; поэтому можно употреблять записи max(X,Y,Z,T), min(A,B,С).

Для описанных функциональных элементов, реализующих некоммутативные операции, необходимо правильное присоединение подсхем-аргументов к входам; различный порядок присоединения реализует разные функции. Обычно считается, что входы элемента упорядочены слева направо, и у 2-местного элемента левый вход соответствует первой переменной, правый - второй. Так, для операции вычитания оба варианта присоединения показаны на рисунке 7.

Дистрибутивность бинарной операции выражает распределительный закон, подобный арифметическому соотношению (а+b)с=ас+bc.

Дистрибутивность слева бинарной операции φ относительно бинарной операции ψ- свойство, состоящее в том, что aψ(bφc) = (aφb)ψ(aφc).

Свойством дистрибутивности в арифметике обладает умножение относительно сложения, но не сложение относительно умножения ab+cac+bc

Дистрибутивность справа бинарной операции φ относительно бинарной операции ψ- свойство, состоящее в том что (aψb)φc=(aφc)ψ(bφc).

Дистрибутивность операций позволяет раскрывать скобки в формулах.

Вернемся к перечню свойств операций над множествами. Можно видеть, что свойства 1-2 выражают коммутативность, а свойства 3-4 - ассоциативность операций и , свойства 5-6 - взаимную дистрибутивность. Свойства 1-10 относятся только к операциям объединения и пересечения. Законы де Моргана 11, 12 связывают все три операции. Свойства 13-20 связаны с операциями над пустым множеством 0 и универсальным множеством U.

 

Вопросы для самоконтроля

  1. Дайте определение ассоциативной, коммутативной и дистрибутивной бинарных операций.
  2. Объясните чем отличается дистрибутивность слева и дистрибутивность справа.
    Приведите примеры.

Практические задания

Tест для самоконтроля