↔ Таблица истинности онлайн

Полином Жегалкина онлайн

Введите логическую функцию — инструмент построит таблицу истинности и рядом со СДНФ и СКНФ выведет полином Жегалкина (алгебраическую нормальную форму, АНФ): сумму по модулю 2 конъюнкций переменных без отрицаний. Ниже показано, как получить тот же полином вручную методом треугольника (преобразованием Мёбиуса) по столбцу значений.

Введите формулу — таблица построится сразу.

Примеры: A ∧ B, A ∨ ¬B, (A → B) ∧ (B → C), закон де Моргана, A ⊕ B ⊕ C

Какие знаки можно вводить

ОперацияЗнаки вводаОписание
НЕ (отрицание)¬ ! ~ NOTменяет значение на противоположное
И (конъюнкция)∧ & * ANDистинно, когда истинны оба
ИЛИ (дизъюнкция)∨ | + ORложно, когда ложны оба
XOR (исключающее ИЛИ)⊕ ^ XORистинно, когда операнды различны
Штрих Шеффера (И-НЕ)↑ NANDложно только когда истинны оба
Стрелка Пирса (ИЛИ-НЕ)↓ NORистинно только когда ложны оба
Импликация→ ->ложно только при 1 → 0
Эквивалентность↔ ≡ <->истинно, когда операнды равны
Переменные / константыA B C D … 1 0буквы — переменные, 1 — истина, 0 — ложь

Приоритет: НЕ → И / И-НЕ → XOR → ИЛИ / ИЛИ-НЕ → импликация → эквивалентность. Меняйте порядок скобками. Регистр и пробелы не важны.

Что такое полином Жегалкина

Полином Жегалкина (алгебраическая нормальная форма, АНФ) — это запись логической функции только через сложение по модулю 2 (⊕, XOR) и конъюнкцию (∧), с возможной константой 1 и без отрицаний. В общем виде:

f = c₀ ⊕ c₁·A ⊕ c₂·B ⊕ c₃·C ⊕ c₄·(A∧B) ⊕ … ⊕ c·(A∧B∧C)

где каждый коэффициент cᵢ равен 0 или 1, а слагаемые — это конъюнкции подмножеств переменных (моном пустого множества — это константа 1). Для каждой логической функции такой полином существует и единствен. Базис {∧, ⊕, 1} функционально полон, поэтому любую функцию можно записать в этом виде.

Пример: полином Жегалкина функции большинства

Построим полином для функции голосования (мажоритарной) F = (A ∧ B) ∨ (B ∧ C) ∨ (A ∧ C) из примера выше — она истинна, когда истинны хотя бы две из трёх переменных. Переменных три, значит в таблице 2³ = 8 наборов.

№ABCA ∧ BB ∧ CA ∧ CF
00000000
10010000
20100000
30110101
41000000
51010011
61101001
71111111

Столбец значений функции сверху вниз: 0 0 0 1 0 1 1 1.

Метод треугольника (Паскаля)

Выпишем столбец значений F в первую строку. Каждая следующая строка — это суммы по модулю 2 (⊕) соседних чисел строки выше, поэтому она короче на один элемент. Коэффициенты полинома — это левый край треугольника (первый элемент каждой строки):

0 0 0 1 0 1 1 1
 0 0 1 1 1 0 0
  0 1 0 0 1 0
   1 1 0 1 1
    0 1 1 0
     1 0 1
      1 1
       0

Левый край сверху вниз: 0 0 0 1 0 1 1 0. Пронумеруем позиции 0…7 и запишем номер в двоичном виде как биты ABC — единичные биты показывают, какие переменные входят в моном (позиция 0 — константа):

ПозицияДвоично (ABC)КоэффициентМоном
30111B ∧ C
51011A ∧ C
61101A ∧ B

Остальные коэффициенты равны нулю, поэтому полином Жегалкина функции большинства:

F = (A ∧ B) ⊕ (B ∧ C) ⊕ (A ∧ C)

Проверка: на наборе 111 все три монома равны 1, а 1 ⊕ 1 ⊕ 1 = 1 — совпадает со значением F. На наборах с двумя единицами ровно один моном даёт 1, на остальных все нули. Введите свою формулу в поле выше — полином Жегалкина построится автоматически рядом со СДНФ и СКНФ.

Зачем нужен полином Жегалкина

По полиному сразу видно важные свойства функции. Функция линейна, если в её полиноме нет ни одной конъюнкции из двух и более переменных (только отдельные переменные и константа) — это критерий из теоремы Поста о функциональной полноте. Функция сохраняет ноль, если свободный член c₀ = 0, и сохраняет единицу, если сумма всех коэффициентов по модулю 2 равна 1. Полином Жегалкина используют в теории булевых функций, криптографии (алгебраическая степень функции) и при проверке принадлежности функции классам Поста.

Теория и пояснения

Полином Жегалкина — это канонический способ записать логическую функцию через две операции: сложение по модулю 2 (исключающее ИЛИ, ⊕) и конъюнкцию (И, ∧), при этом отрицания не используются, а роль «единицы» играет константа 1. Такое представление называют также алгебраической нормальной формой (АНФ). В отличие от СДНФ и СКНФ, где слагаемые соединяются знаками ИЛИ и И, здесь все мономы (конъюнкции переменных без отрицаний) складываются по модулю 2. Для любой функции полином Жегалкина существует и определён однозначно с точностью до порядка слагаемых. Коэффициенты полинома вычисляют по таблице истинности преобразованием Мёбиуса: это удобно оформить «методом треугольника» (треугольником Паскаля по модулю 2). В первую строку выписывают столбец значений функции, каждую следующую строку получают как поразрядное сложение по модулю 2 соседних элементов предыдущей строки, а коэффициенты читают по левому краю треугольника — первому элементу каждой строки. Позицию коэффициента записывают в двоичном виде: единичные разряды указывают, какие переменные входят в соответствующий моном (нулевая позиция отвечает за свободный член — константу 1). Полином Жегалкина позволяет мгновенно проверить линейность функции (нет конъюнкций из двух и более переменных), определить сохранение нуля и единицы и найти алгебраическую степень — старший порядок монома. Инструмент строит полином Жегалкина автоматически: введите формулу, и рядом с таблицей истинности, СДНФ и СКНФ появится готовая АНФ.

Частые вопросы

Как построить полином Жегалкина онлайн?

Введите логическую функцию в поле ввода — калькулятор построит таблицу истинности и рядом со СДНФ и СКНФ выведет полином Жегалкина (АНФ). Всё считается прямо в браузере, формула никуда не отправляется.

Что такое полином Жегалкина?

Это запись функции только через сложение по модулю 2 (⊕) и конъюнкцию (∧) с константой 1 и без отрицаний: f = c₀ ⊕ c₁A ⊕ … ⊕ (A ∧ B ∧ C). Такую форму называют алгебраической нормальной формой (АНФ). Для каждой функции она единственна.

Как найти полином методом треугольника?

Выпишите столбец значений функции из таблицы истинности в верхнюю строку. Каждую следующую строку получайте как сложение по модулю 2 (⊕) соседних чисел строки выше — она станет короче на один элемент. Коэффициенты полинома — это левый край треугольника; позицию коэффициента переведите в двоичный вид, и единичные разряды покажут переменные монома.

Чем полином Жегалкина отличается от СДНФ?

В СДНФ минтермы (полные конъюнкции с отрицаниями) соединяются знаком ИЛИ, а в полиноме Жегалкина мономы без отрицаний складываются по модулю 2 (⊕). Полином часто короче и позволяет проверить линейность функции — свойство, которое по СДНФ не видно.

Как по полиному определить, что функция линейна?

Функция линейна, если её полином Жегалкина не содержит ни одной конъюнкции из двух и более переменных — только отдельные переменные и, возможно, константу 1. Это один из критериев функциональной полноты по теореме Поста.