Алгебраическая нормальная форма булевой функции

Перевести таблицу из 2ⁿ значений в единственную XOR-сумму мономов, определить алгебраическую степень и проверить обратное восстановление.

Ваш пример

Числа и дроби: 0.5, 0,5 или 1/3. Числа в строке разделяются пробелами, строки — переносом. Выражения не выполняются.

Разбор примера

x1 ⊕ x2

  1. Порядок переменных закреплён маской.
  2. Подстановка во все наборы восстановила исходную таблицу точно.

Метод и условия расчёта

Коэффициенты получаются двоичным преобразованием Мёбиуса по подмножествам.

Сложение — 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. По ссылкам можно сверить определения и условия модели.