Алгебраическая нормальная форма булевой функции
Перевести таблицу из 2ⁿ значений в единственную XOR-сумму мономов, определить алгебраическую степень и проверить обратное восстановление.
Ваш пример
Разбор примера
x1 ⊕ x2
- Порядок переменных закреплён маской.
- Подстановка во все наборы восстановила исходную таблицу точно.
Метод и условия расчёта
Коэффициенты получаются двоичным преобразованием Мёбиуса по подмножествам.
Сложение — XOR, умножение переменных — AND; xᵢ²=xᵢ.
Теория к методу
Алгебраическая нормальная форма записывает булеву функцию как XOR-сумму квадратсвободных мономов. Коэффициенты находятся над GF(2) по таблице значений. Подстановка во все исходные наборы проверяет и коэффициенты, и принятую нумерацию переменных.
Начните с порядка строк, потому что одна и та же последовательность значений при разных соглашениях описывает разные функции. В инструменте номер строки является двоичной маской, а x₁ соответствует младшему биту. Для двух переменных порядок наборов поэтому равен (0,0), (1,0), (0,1), (1,1), если координаты записывать как (x₁,x₂).
Пример: Таблица 0,1,1,0 в принятом порядке задаёт XOR двух переменных. Полученные коэффициенты равны 0,1,1,0, поэтому форма записывается x₁⊕x₂ и имеет степень один.
На наборе (1,1) оба линейных слагаемых дают единицу, их XOR равен нулю. Если ошибочно заменить сложение на ИЛИ, получится единица и проверка последней строки сразу обнаружит подмену.
Вопросы по теме
Это ДНФ с операцией ИЛИ?
Нет. Сумма здесь исключающая: одинаковые мономы сокращаются по модулю два.
Как читать порядок строк?
Маска 1 означает x₁=1 при остальных нулях; x₁ является младшим битом.
Логика и логические схемы: объяснения, примеры и практика
Основа объяснения
Объяснения и примеры подготовлены для erudeet. По ссылкам можно сверить определения и условия модели.