Спирина, М.С. Дискретная математика

0 + 0 = 0 , 0 +1 = 1 , 1 + 0 = 1 , 1 + 1 = (1) 0. Эти наблюдения дают основания для выдвижения еще одной гипотезы: возможно применение суммы по модулю два в двоич­ ном сумматоре для системы контроля и исправления ошибок. Действительно, если из-за неисправности в схеме один из ар­ гументов функции М2 исказится, то одновременно и значение функции изменится на противоположное, что сразу можно будет обнаружить на выходе. Поэтому операция сложения по модулю два имеет особое зна­ чение для организации работы компьютера: в схемах контроля и исправления ошибок используется это ее специфическое свойство. Теперь поясним, откуда берется название «сумма по модулю два». Обозначим остаток от деления целого числа М на число N как М mod N. Рассмотрим множество {0, 1}, причем не абстракт­ ных булевых символов, а обычных чисел (в математике его обо­ значают Z2). Произведем на этом множестве операцию (а + b ) mod2. Имеем: (0 + 0)mod2 = 0, (1 + 0)mod2 = (0 + l)m od2 = 1mod2 = 1, (1 + l)m od2 = 2mod2 = 0. Видим, что операция (a + b ) mod2 на множестве Z2 совпадает с нашей строгой дизъюнкцией на мно­ жестве В. Поэтому эти множества изоморфны: (Z2, mod 2) - (В, ®). Геометрическая интерпретация суммы по модулю два с раз­ личным числом переменных может быть представлена на плоско­ сти для функции F(xlf х2) = х1® х2 (рис. 4.16, о) и в трехмерном пространстве для функции F(xu х2, х3) = х { Ф х2 © х3(рис. 4.16, б). Закрашенные точки символизируют 1, выколотые или отсутству­ ющие точки обозначают 0. Отрицание функции х х ® х2 © х3 изоб­ ражено на рис. 4.1, б. При любом обходе такого куба по его ребрам нельзя попасть из одного единичного значения в другое непосредственно, так как между этими значениями расположен хотя бы один нуль. За счет Рис. 4.16. Геометрическая интерпретация суммы по модулю два: а — на плоскости; б — в пространстве 191