Построение полинома жегалкина по таблице истинности
Рассмотрим алгоритмы построения полинома Жегалкина булевой функции, заданной различными способами, а именно: совершенной ДНФ, произвольной ДНФ, формулой и таблицей истинности.
Алгоритм построения полинома Жегалкина по СовДНФ (основан на доказательстве теоремы о существовании полинома Жегалкина).
Начало. Задана совершенная ДНФ функции f(x1, …, xn).
Шаг 1. Заменяем каждый символ дизъюнкции на символ дизюнкции с исключением.
Шаг 2. Заменяем каждую переменную с инверсией x равносильной формулой x 1.
Шаг 3. Раскрываем скобки.
Шаг 4. Вычеркиваем из формулы пары одинаковых слагаемых.
Конец. Получен полином Жегалкина функции f(x1, …, xn).
Пример. Найдем полином Жегалкина мажоритарной булевой функции по ее совершенной ДНФ.
Алгоритм построения полинома Жегалкина по ДНФ (основан на равносильности K1 K2= K1 K2 K1K2).
Начало. Задана произвольная ДНФ функции f(x1, …, xn).
Шаг 1. Разбиваем ДНФ на пары конъюнкций, предпочтительно ортогональных (если число конъюнкций нечетно, одна из них остается без пары).
Шаг 2. Заменяем дизъюнкцию каждой пары конъюнкций K1 K2 формулой K1 K2 K1K2 или формулой K1 K2, если K1 и K2 ортогональны.
Шаг 3. В полученной формуле находим очередную дизъюнкцию A1 A2и заменяем ее формулой A1 A2 A1A2. Повторяем шаг 3 до тех пор, пока это возможно.
Шаг 4. Заменяем каждую переменную с инверсией x равносильной формулой x 1.
Шаг 5. Раскрываем скобки.
Шаг 6. Вычеркиваем из формулы пары одинаковых слагаемых.
Конец. Получен полином Жегалкина функции f(x1, …, xn).
Пример. Найдем полином Жегалкина мажоритарной функции по ДНФ.
Отметим, что полиномы мажоритарной функции, полученные в двух последних примерах, совпадают с точностью до порядка конъюнкций, и это естественно (по теореме о единственности полинома Жегалкина).
Способ 1 основан на предварительном преобразовании формулы в ДНФ (любым известным нам способом). Затем ДНФ преобразуется в полином Жегалкина по только что изученному алгоритму.
Примеры. Получим полиномы Жегалкина двух элементарных булевых функций: импликации и эквивалентности, представив их предварительно кратчайшими ДНФ.
Аналогично можно получить полиномы Жегалкина всех элементарных булевых функций (оставим читателю их вывод).
Константы 0 и 1, тождественная функция, а также конъюнкция ab и дизъюнкция с исключением ab уже являются полиномами Жегалкина. Полином Жегалкина инверсии a =1a.
Заметим, что некоторые из приведенных полиномов могут быть получены гораздо проще, в частности,
Способ 2. Если булева функций задана произвольной формулой, то ее полином Жегалкина можно получить подстановкой в формулу вместо элементарных булевых функций их полиномов.
Пример. Найдем полином Жегалкина мажоритарной функции, заданной формулой:
[ подставим в формулу полином Жегалкина штриха Шеффера 1 ab при a=(xy) z, b=x y ]
[ подставим полиномы Жегалкина обратной импликации 1 b ab при a=xy, b=z и импликации 1 a ab при a=x, b= y ]
[ подставим полином Жегалкина эквивалентности 1 x y, раскроем скобки, и вычеркнем появившиеся при этом пары одинаковых слагаемых ]
[заменим инверсию ее полиномом Жегалкина, раскроем скобки и вычеркнем пары одинаковых слагаемых ]
Полином, естественно, совпадает с полученными ранее по совершенной и произвольной ДНФ.
Способ 3. Если булева функций задана произвольной формулой, то ее полином Жегалкина можно получить, используя специальное разложение функции.
Определение. Разложением Дэвио называется следующее разложение булевой функции f(x1, …, xn по переменной xi:
Разложение Дэвио непосредственно следует из разложения Шеннона, если учесть, что слагаемые в последнем ортогональны, и что x i=xi 1.
Пример. Найдем разложение Дэвио по переменной x мажоритарной булевой функции, заданной формулой.
Для получения полинома Жегалкина необходимо продолжить разложение подформул, не являющихся дизъюнкцией с исключением элементарных конъюнкций, пока не получится формула над . Если в такой формуле заменить инверсии x на x 1, раскрыть скобки и вычеркнуть пары одинаковых слагаемых, то получится полином Жегалкина.
Пример. Продолжив предыдущий пример, получим полином Жегалкина мажоритарной функции. Для этого разложим подформулы (y z) / y и y z по переменной y:
Полином Жегалкина, естественно, совпадает с полученными ранее.
Алгоритм построения полинома Жегалкина по таблице истинности (основан на методе неопределенных коэффициентов).
Продемонстрируем идею метода на примере произвольной булевой функции двух аргументов f(x,y). Представим ее полиномом Жегалкина в форме с коэффициентами
Подставив в данное равенство наборы значений аргументов, получим систему из четырех линейных уравнений с четырьмя неизвестными коэффициентами: c0, c1 c2, c3.
Заметим, что наборы подставлены в равенство в естественном порядке, и система имеет треугольный вид: в первом уравнении обратились в ноль все слагаемые, следующие за c0, во втором – следующие за c1 и так далее. Значит, коэффициент c0 можно получить из первого уравнения и подставить его в остальные. Тогда c1 можно получить из второго уравнения, и так далее.
В общем случае для функции n аргументов получается система треугольного вида из 2 n линейных уравнений с 2 n неизвестными – коэффициентами полинома Жегалкина.
Пример. Найдем полином Жегалкина мажоритарной булевой функции, заданной таблицей истинности, последовательно вычисляя коэффициенты полинома и подставляя их в остальные уравнения.
Из первого уравнения следует, что c0=0. Из второго и третьего уравнений следует, что c1=0 и c2=0, значит, c1z и c2y тождественно равны нулю. Из четвертого уравнения получаем c3=1, значит, надо вычислять значения конъюнкции c3yz в остальных уравнениях. Аналогично получаем c4=0, c5=1, c6=1 и c7=0. Найден вектор коэффициентов полинома Жегалкина мажоритарной функции π=00010110, и сам полином P=yz xz xy, который, естественно, совпадает с полученными ранее. •
Читайте также: Gs u210b нет сигнала
Полином (многочлен) Жегалкина представляет собой полином, коэффициентами которого являются числа $0$ или $1$, причем в качестве операций умножения и сложения выступают соответственно конъюнкция и сумма по модулю $2$. Например, для булевой функции $fleft(x_1, x_2, x_3
ight)$ от трех переменных $x_1, x_2, x_3$ полином Жегалкина будет иметь следующий вид:
$$fleft(x_1, x_2, x_3
ight)=a_0igoplus a_1x_1igoplus a_2x_2igoplus a_3x_3igoplus a_x_1x_2igoplus a_x_1x_3igoplus a_x_2x_3igoplus a_x_1x_2x_3.$$
Коэффициенты $a_0, a_1, dots , a_in left ight>$, то есть могут принимать значения либо $0$, либо $1$ в зависимости от того, какое значение принимает булева функция $fleft(x_1, x_2, x_3
ight)$ на том или ином наборе значений переменных.
С помощью полинома Жегалкина можно представить любую булеву функцию, причем единственных образом. Поэтому можно сказать, что полином Жегалкина является еще одним способом представления булевых функций в алгебре операций $igoplus $ — суммы по модулю $2$, $cdot $ — конъюнкции и константы $1$.
Операция $igoplus $ имеет и другие названия: сумма Жегалкина, неравнозначность, исключающее ИЛИ-НЕ. Иногда, для удобства ее обозначения используют привычную запись сложения $+$, но не стоит путать с дизъюнкцией и, тем более, с обычной арифметической операцией сложения. Таблица истинности данной операции имеет вид:
$$egin <|c|c|>
hline
x & y & xigoplus y \
hline
0 & 0 & 0 \
hline
0 & 1 & 1 \
hline
1 & 0 & 1 \
hline
1 & 1 & 0 \
hline
end $$
Сумма $xigoplus y$ принимает истинное значение тогда и только тогда, когда истинно одно и только одно составляющее высказывание. Если сравнить таблицы истинности основных логических операций, то можно заметить, что $xigoplus y=overline$. То есть операция сумма Жегалкина $igoplus $ есть отрицание эквиваленции.
Для двух введенных операций $igoplus , cdot $ (суммы по модулю 2 и конъюнкции) выполняются все логические законы:
- Коммутативность: $xigoplus y=yigoplus x$;
- Ассоциативность: $left(xigoplus y
ight)igoplus z=xigoplus left(yigoplus z
ight)$, то есть результат $xigoplus yigoplus z$ не зависит от расстановки скобок; - Дистрибутивность: $xleft(yigoplus z
ight)=xyigoplus xz$; - $xigoplus x=0$;
- $0igoplus x=x$;
- $overline =xigoplus 1$.
Для построения полинома Жегалкина можно использовать различные методы:
- Метод неопределенных коэффициентов;
- Метод треугольника Паскаля;
- Преобразование ДНФ;
- Преобразование СДНФ.
Метод неопределенных коэффициентов
Найдем полином Жегалкина для функции $fleft(x_1, x_2, x_3
ight)=left(x_1x_2vee x_3
ight) o _2$, используя метод неопределенных коэффициентов. Для этого сначала необходимо построить таблицу истинности данной булевой функции $fleft(x_1, x_2, x_3
ight)$.
$egin <|c|c|>
hline
x_1 & x_2 & x_3 & x_1x_2 & x_1x_2vee x_3 & fleft(x_1, x_2, x_3
ight)=left(x_1x_2vee x_3
ight) o _2 \
0 & 0 & 0 & 0 & 0 & 1 \
hline
0 & 0 & 1 & 0 & 1 & 1 \
hline
0 & 1 & 0 & 0 & 0 & 1 \
hline
0 & 1 & 1 & 0 & 1 & 0 \
hline
1 & 0 & 0 & 0 & 0 & 1 \
hline
1 & 0 & 1 & 0 & 1 & 1 \
hline
1 & 1 & 0 & 1 & 1 & 0 \
hline
1 & 1 & 1 & 1 & 1 & 0 \
hline
end $
Общий вид полинома Жегалкина для функции $fleft(x_1, x_2, x_3
ight)$ трех переменных $x_1, x_2, x_3$:
$$fleft(x_1, x_2, x_3
ight)=a_0igoplus a_1x_1igoplus a_2x_2igoplus a_3x_3igoplus a_x_1x_2igoplus a_x_1x_3igoplus a_x_2x_3igoplus a_x_1x_2x_3.$$
Последовательно подставляем наборы значений переменных и находим коэффициенты $a_0, a_1, dots , a_$.
$fleft(0, 0, 0
ight)=a_0=1;$
$fleft(0, 0, 1
ight)=a_0igoplus a_3=1Rightarrow 1igoplus a_3=1Rightarrow a_3=0;$
$fleft(0, 1, 0
ight)=a_0igoplus a_2=1Rightarrow 1igoplus a_2=1Rightarrow a_2=0;$
$fleft(0, 1, 1
ight)=a_0igoplus a_2igoplus a_3igoplus a_=0Rightarrow 1igoplus 0igoplus 0igoplus a_=0Rightarrow 1igoplus a_=0Rightarrow a_=1;$
$fleft(1, 0, 0
ight)=a_0igoplus a_1=1Rightarrow 1igoplus a_1=1Rightarrow a_1=0.$
$fleft(1, 0, 1
ight)=a_0igoplus a_1igoplus a_3igoplus a_=1Rightarrow 1igoplus 0igoplus 0igoplus a_=1Rightarrow 1igoplus a_=1Rightarrow a_=0;$
$fleft(1, 1, 0
ight)=a_0igoplus a_1igoplus a_2igoplus a_=0Rightarrow 1igoplus 0igoplus 0igoplus a_=0Rightarrow 1igoplus a_=0Rightarrow a_=1;$
$fleft(1, 1, 1
ight)=a_0igoplus a_1igoplus a_2igoplus a_3igoplus a_igoplus a_igoplus a_igoplus a_=0Rightarrow 1igoplus 0igoplus 0igoplus 0igoplus 1igoplus 0igoplus 1igoplus a_=0Rightarrow 1igoplus a_=0Rightarrow a_=1;$
Подставляя найденные коэффициенты, получаем полином Жегалкина:
$$fleft(x_1, x_2, x_3
ight)=1igoplus x_1x_2igoplus x_2x_3igoplus x_1x_2x_3.$$
Метод треугольника Паскаля
Построим полином Жегалкина для функции из предыдущего метода, используя треугольник Паскаля.
Поясним, как заполняется треугольник Паскаля. Верхняя строка треугольника задает вектор значений булевой функции $f=left(11101100
ight)$. В каждой строке, начиная со второй, любой элемент такого треугольника вычисляется как сумма по модулю $2$ двух соседних элементов предыдущей строки. Так, элементы второй строки: $1igoplus 1=0, 1igoplus 1=0, 1igoplus 0=1, 0igoplus 1=1, 1igoplus 1=0, 1igoplus 0=1, 0igoplus 0=0$. Аналогично вычисляются элементы других строк.
Левой стороне треугольника Паскаля соответствуют наборы значений переменных исходной функции $fleft(x_1, x_2, x_3
ight)$. Соединяя знаком конъюнкции переменные, значения которых в наборе равны $1$, мы получим слагаемое в полиноме Жегалкина. Набору $left(000
ight)$ соответствует $1$, набору $left(001
ight)$ соответствует $x_3$, и т.д.
Поскольку единицам левой стороны треугольника соответствуют слагаемые $1, x_2x_3, x_1x_2, x_1x_2x_3$, то полином Жегалкина:
$$fleft(x_1, x_2, x_3
ight)=1igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3.$$
Преобразование ДНФ
Используя основные законы алгебры логики, приведем сначала данную функцию к ДНФ.
Далее в полученной ДНФ необходимо «избавиться» от дизъюнкции, используя законы де Моргана:
Заменяем каждое отрицание $overline =1igoplus x$ и применяем написанные выше логические законы, получаем:
$overline_1_3>x>_2>=1igoplus
ight)left(1igoplus x_3
ight)
ight)x_2=1igoplus left(1igoplus 1igoplus x_3igoplus x_1igoplus x_1x_3
ight)x_2=1igoplus left(x_3igoplus x_1igoplus x_1x_3
ight)x_2=1igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3$ — полином Жегалкина.
Преобразование СДНФ
$egin <|c|c|>
hline
x_1 & x_2 & x_3 & fleft(x_1, x_2, x_3
ight) \
hline
0 & 0 & 0 & 1 \
hline
0 & 0 & 1 & 1 \
hline
0 & 1 & 0 & 1 \
hline
0 & 1 & 1 & 0 \
hline
1 & 0 & 0 & 1 \
hline
1 & 0 & 1 & 1 \
hline
1 & 1 & 0 & 0 \
hline
1 & 1 & 1 & 0 \
hline
end $
Для построения СДНФ по таблице истинности выбираем наборы, на которых функция $f$ принимает значение, равное 1. Если значение переменной в этом наборе равно 0, то она берется с отрицанием, если значение переменной равно 1, то переменная берется без отрицание. Соединив знаком конъюнкции переменные соответствующего набора, получим элементарную конъюнкцию. Тогда дизъюнкция всех таких элементарных конъюнкций есть СДНФ.
Читайте также: Почему на айфоне не выключается звук камеры
Чтобы построить полином Жегалкина через СДНФ, необходимо исключить операции дизъюнкции и отрицания, затем раскрыть скобки.
$fleft(x_1, x_2, x_3
ight)=_1_2_3igoplus _1_2x_3igoplus _1x_2_3igoplus x_1_2_3igoplus x_1_2x_3=left(1igoplus x_1
ight)left(1igoplus x_2
ight)left(1igoplus x_3
ight)igoplus left(1igoplus x_1
ight)left(1igoplus x_2
ight)x_3igoplus left(1igoplus x_1
ight)x_2left(1igoplus x_3
ight)igoplus x_1left(1igoplus x_2
ight)left(1igoplus x_3
ight)igoplus x_1left(1igoplus x_2
ight)x_3=1igoplus x_3igoplus x_2igoplus x_2x_3igoplus x_1igoplus x_1x_3igoplus x_1x_2igoplus x_1x_2x_3igoplus x_3igoplus x_2x_3igoplus x_1x_3igoplus x_1x_2x_3igoplus x_2igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3igoplus x_1igoplus x_1x_3igoplus x_1x_2igoplus x_1x_2x_3igoplus x_1x_3igoplus x_1x_2x_3=1igoplus x_2x_3igoplus x_1x_2igoplus x_1x_2x_3$ — полином Жегалкина.
Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.
Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина
введите функцию или её вектор
Построено таблиц, форм: 4798
Как пользоваться калькулятором
- Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
- Укажите действия, которые необходимо выполнить с помощью переключателей
- Укажите, требуется ли вывод решения переключателем «С решением»
- Нажмите на кнопку «Построить»
Видеоинструкция к калькулятору
Используемые символы
В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.
Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.
Для смены порядка выполнения операций используются круглые скобки ().
Обозначения логических операций
- И (AND): & • ∧ *
- ИЛИ (OR): ∨ +
- НЕ (NOT): ¬ !
- Исключающее ИЛИ (XOR): ⊕ ^
- Импликация: -> → =>
- Эквивалентность: =
Что умеет калькулятор
- Строить таблицу истинности по функции
- Строить таблицу истинности по двоичному вектору
- Строить совершенную конъюнктивную нормальную форму (СКНФ)
- Строить совершенную дизъюнктивную нормальную форму (СДНФ)
- Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
- Определять принадлежность функции к каждому из пяти классов Поста
- Строить карту Карно
- Минимизировать ДНФ и КНФ
- Искать фиктивные переменные
Что такое булева функция
Булева функция f(x1, x2, . xn) — это любая функция от n переменных x1, x2, . xn, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.
Что такое таблица истинности?
Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2 n строк, где n — число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.
Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.
Логические операции
Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).
Таблица истинности логических операций
| a | b | a ∧ b | a ∨ b | ¬a | ¬b | a → b | a = b | a ⊕ b |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
Как задать логическую функцию
Есть множество способов задать булеву функцию:
- таблица истинности
- характеристические множества
- вектор значений
- матрица Грея
- формулы
Рассмотрим некоторые из них:
Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).
Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c
Способы представления булевой функции
С помощью формул можно получать огромное количество разнообразных функций, причём с помощью разных формул можно получить одну и ту же функцию. Иногда бывает весьма полезно узнать, как построить ту или иную функцию, используя лишь небольшой набор заданных операций или используя как можно меньше произвольных операций. Рассмотрим основные способы задания булевых функций:
- Совершенная дизъюнктивная нормальная форма (СДНФ)
- Совершенная конъюнктивная нормальная форма (СКНФ)
- Алгебраическая нормальная форма (АНФ, полином Жегалкина)
Совершенная дизъюнктивная нормальная форма (ДНФ)
Простая конъюнкция — это конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция простых конъюнкций.
Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ относительно некоторого заданного конечного набора переменных, в каждую конъюнкцию которой входят все переменные данного набора.
Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.
Совершенная конъюнктивная нормальная форма (КНФ)
Простая дизъюнкция — это дизъюнкция одной или нескольких переменных, или их отрицаний, причём каждая переменная входит в неё не более одного раза.
Конъюнктивная нормальная форма (КНФ) — это конъюнкция простых дизъюнкций.
Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ относительно некоторого заданного конечного набора переменных, в каждую дизъюнкцию которой входят все переменные данного набора.
Читайте также: Разрешить разблокировку загрузчика ос что это
Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.
Алгебраическая нормальная форма (АНФ, полином Жегалкина)
Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.
Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1
Алгоритм построения СДНФ для булевой функции
- Построить таблицу истинности для функции
- Найти все наборы аргументов, на которых функция принимает значение 1
- Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые конъюнкции с помощью дизъюнкции
Алгоритм построения СКНФ для булевой функции
- Построить таблицу истинности для функции
- Найти все наборы аргументов, на которых функция принимает значение 0
- Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые дизъюнкции с помощью конъюнкции
Алгоритм построения полинома Жегалкина булевой функции
Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.
- Построить таблицу истинности для функции
- Добавить новый столбец к таблице истинности и записать в 1, 3, 5. ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6. прибавить по модулю два значения из соответственно 1, 3, 5. строк.
- Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10. строк, а к 3, 4, 7, 8, 11, 12. строкам аналогично предыдущему пункту прибавить переписанные значения.
- Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
- Выписать булевы наборы, на которых значение последнего столбца равно единице
- Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.
Примеры построения различных представлений логических функций
Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬a b∨ ¬b c∨ca
1. Построим таблицу истинности для функции
| a | b | c | ¬a | ¬a ∧b | ¬b | ¬b ∧c | ¬a ∧b∨ ¬b ∧c | c∧a | ¬a ∧b∨ ¬b ∧c∨c∧a |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Построение совершенной дизъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает истинное значение: < 0, 0, 1 > < 0, 1, 0 > < 0, 1, 1 >
В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:
Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:
Построение совершенной конъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает ложное значение: < 0, 0, 0 >
В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:
Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:
Построение полинома Жегалкина:
Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:
| a | b | c | F | 1 | |
| 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 0 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 1 | 1 | 0 | 0 | → | 0 |
| 1 | 1 | 1 | 1 | ⊕ 0 | 1 |
Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:
| a | b | c | F | 1 | 2 | |
| 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | 1 | → | 1 |
| 1 | 1 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:
| a | b | c | F | 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | → | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | ⊕ 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
Окончательно получим такую таблицу:
| a | b | c | F | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):
Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc
А Вы знаете, что мы пишем программы на C, C++, C#, Pascal и Python?
Так что если Вам нужно написать программу на C/C++, C#, Pascal или Python — мы с радостью поможем с этим!
В том числе мы занимаемся репетиторством по информатике и программированию, а также готовим к ОГЭ и ЕГЭ!
Почему именно мы?
- Более 1800 выполненных заказов;
- Более 170 отзывов;
- Качественное решение
- Короткие сроки и привлекательные цены
- Различные акции и скидки
Как с нами связаться?
- группа Вконтакте: vk.com/programforyou
- наша почта: order@programforyou.ru
Programforyou — позвольте нам писать код для вас и вы получите качественное решение в короткие сроки по привлекательной цене!
Нет связанных сообщений
Построение полинома Жегалкина по таблице истинности — шаг за шагом руководство с примерами
Полином Жегалкина – это математический инструмент, который используется для представления логических функций в виде многочлена. Он был разработан российским математиком и инженером, Нильсом Жегалкиным, в 1927 году. Полином Жегалкина может быть полезен при анализе и проектировании электронных цепей, а также в других областях, где требуется работа с логическими функциями.
Построение полинома Жегалкина по таблице истинности может быть достаточно простым процессом. Для начала необходимо составить таблицу истинности, в которой будут указаны все возможные значения аргументов и соответствующие им значения функции. Затем следует использовать эти данные для определения коэффициентов полинома Жегалкина.
Для построения полинома Жегалкина сначала необходимо определить порядок переменных. Затем каждая переменная представляется вектором значений, принимаемых этой переменной в таблице истинности. Далее следует записать значения функции, соответствующие каждой комбинации значений переменных. На основе этих данных можно определить коэффициенты полинома Жегалкина. Таким образом, по таблице истинности можно легко построить полином Жегалкина для любой логической функции.
Раздел 1: Определение и основные понятия
Для построения полинома Жегалкина по таблице истинности необходимо понимать некоторые основные понятия.
- Таблица истинности — таблица, которая отображает все возможные комбинации значений переменных и результаты логических выражений.
- Переменные — символы, которые могут принимать два значения: истина (1) или ложь (0).
- Логическое выражение — выражение, состоящее из логических операторов и переменных, которое возвращает значение истина или ложь в зависимости от значений переменных.
- Минтермы и макстермы — конъюнкции (произведения) и дизъюнкции (суммы) переменных соответственно, которые соответствуют определенному значению функции в таблице истинности.
- Полином Жегалкина — линейная комбинация макстермов, представляющая логическую функцию.
Теперь, когда мы разобрались с основными понятиями, можно перейти к построению полинома Жегалкина по таблице истинности.
Раздел 2: Построение таблицы истинности
Таблица истинности представляет собой таблицу, в которой входные переменные принимают все возможные комбинации значений (0 и 1), а на выходе указывается значение функции, которое получается при данных значениях переменных.
Для построения таблицы истинности нужно создать n столбцов для переменных и один дополнительный столбец для значения функции. Всего будет 2^n строк, так как количество комбинаций значений переменных равно 2^n.
| Переменная 1 | Переменная 2 | … | Переменная n | Значение функции |
|---|---|---|---|---|
| 0 | 0 | … | 0 | 0 |
| 0 | 0 | … | 1 | 1 |
| 0 | 1 | … | 0 | 1 |
| 0 | 1 | … | 1 | 0 |
| 1 | 0 | … | 0 | 1 |
| 1 | 0 | … | 1 | 0 |
| 1 | 1 | … | 0 | 1 |
| 1 | 1 | … | 1 | 1 |
После построения таблицы истинности можно переходить к построению полинома Жегалкина.
Раздел 3: Составление полинома Жегалкина
Для составления полинома Жегалкина по таблице истинности необходимо следующие шаги:
- Создать таблицу истинности, где каждая строка соответствует комбинации значений переменных, а последний столбец содержит значения функции.
- Определить, какие строки соответствуют истинным значениям функции. Для этого обратите внимание на последний столбец таблицы истинности.
- Определить, какие переменные являются значимыми для достижения истинных значений функции. Для этого рассмотрите только строки, в которых функция принимает значение 1.
- Найти минимальный полином Жегалкина, используя выявленные значимые переменные и их отрицания. Для этого можно использовать метод Квайна или метод Карно.
- Записать полученный полином Жегалкина в виде суммы произведений переменных и их отрицаний, где каждое произведение соответствует одному значимому слагаемому.
Полученный полином Жегалкина представляет собой компактную формулу, которая эквивалентна исходной логической функции. Он может быть полезен для решения задач по оптимизации логических схем, а также для анализа и синтеза цифровых систем.
Применение полинома Жегалкина позволяет упростить логические уравнения, снизить их сложность и повысить эффективность работы системы в целом.
| Переменные | Функция |
|---|---|
| 0 | 1 |
| 1 | 0 |
Раздел 4: Пример построения полинома Жегалкина
Для наглядности рассмотрим конкретный пример построения полинома Жегалкина по таблице истинности.
Допустим, у нас есть следующая таблица истинности:
| a | b | c | f |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |
Для построения полинома Жегалкина по данной таблице истинности необходимо найти все импликанты, то есть наборы переменных, для которых функция принимает значение истины (1).
В нашем примере, импликантами являются следующие наборы переменных:
Далее необходимо составить полином Жегалкина, где каждому импликанту сопоставляется переменная или их комбинация. В данном примере, полином Жегалкина будет выглядеть следующим образом:
f = a©b©c ⊕ ©a©b©c ⊕ ©a©b©c ⊕ ©a©b©c ⊕ a©b©c ⊕ a©b©c ⊕ a©b©c ⊕ ©a©b©c
Таким образом, мы получили полином Жегалкина по таблице истинности нашей функции.
Построение таблицы истинности. СДНФ. СКНФ. Полином Жегалкина.
Онлайн калькулятор позволяет быстро строить таблицу истинности для произвольной булевой функции или её вектора, рассчитывать совершенную дизъюнктивную и совершенную конъюнктивную нормальные формы, находить представление функции в виде полинома Жегалкина, строить карту Карно и классифицировать функцию по классам Поста.
Калькулятор таблицы истинности, СКНФ, СДНФ, полинома Жегалкина
введите функцию или её вектор
Скрыть клавиатуру
Показать настройки
Опускать знак конъюнкции
Таблица истинности
Полином Жегалкина
Классификация Поста
Минимизация, карта Карно
Фиктивные переменные
С решением
Построено таблиц, форм:
Как пользоваться калькулятором
- Введите в поле логическую функцию (например, x1 ∨ x2) или её вектор (например, 10110101)
- Укажите действия, которые необходимо выполнить с помощью переключателей
- Укажите, требуется ли вывод решения переключателем «С решением»
- Нажмите на кнопку «Построить»
Видеоинструкция к калькулятору
Используемые символы
В качестве переменных используются буквы латинского и русского алфавитов (большие и маленькие), а также цифры, написанные после буквы (индекс переменной). Таким образом, именами переменных будут: a , x , a1 , B , X , X1 , Y1 , A123 и так далее.
Для записи логических операций можно использовать как обычные символы клавиатуры ( * , + , ! , ^ , -> , = ), так и символы, устоявшиеся в литературе ( ∧ , ∨ , ¬ , ⊕ , → , ≡ ). Если на вашей клавиатуре отсутствует нужный символ операции, то используйте клавиатуру калькулятора (если она не видна, нажмите «Показать клавиатуру»), в которой доступны как все логические операции, так и набор наиболее часто используемых переменных.
Для смены порядка выполнения операций используются круглые скобки ().
Обозначения логических операций
- И (AND): & • ∧ *
- ИЛИ (OR): ∨ +
- НЕ (NOT): ¬ !
- Исключающее ИЛИ (XOR): ⊕ ^
- Импликация: -> → =>
- Эквивалентность: = ~ ≡
- Штрих Шеффера: ↑ |
- Стрелка Пирса: ↓
Что умеет калькулятор
- Строить таблицу истинности по функции
- Строить таблицу истинности по двоичному вектору
- Строить совершенную конъюнктивную нормальную форму (СКНФ)
- Строить совершенную дизъюнктивную нормальную форму (СДНФ)
- Строить полином Жегалкина (методами Паскаля, треугольника, неопределённых коэффициентов)
- Определять принадлежность функции к каждому из пяти классов Поста
- Строить карту Карно
- Минимизировать ДНФ и КНФ
- Искать фиктивные переменные
Что такое булева функция
Булева функция f(x1, x2, . xn) — это любая функция от n переменных x1, x2, . xn, в которой её аргументы принимают одно из двух значений: либо 0, либо 1, и сама функция принимает значения 0 или 1. То есть это правило, по которому произвольному набору нулей и единиц ставится в соответствие значение 0 или 1. Подробнее про булевы функции можно посмотреть на Википедии.
Что такое таблица истинности?
Таблица истинности — это таблица, описывающая логическую функцию, а именно отражающую все значения функции при всех возможных значениях её аргументов. Таблица состоит из n+1 столбцов и 2 n строк, где n — число используемых переменных. В первых n столбцах записываются всевозможные значения аргументов (переменных) функции, а в n+1-ом столбце записываются значения функции, которые она принимает на данном наборе аргументов.
Довольно часто встречается вариант таблицы, в которой число столбцов равно n + число используемых логических операций. В такой таблице также первые n столбцов заполнены наборами аргументов, а оставшиеся столбцы заполняются значениями подфункций, входящих в запись функции, что позволяет упростить расчёт конечного значения функции за счёт уже промежуточных вычислений.
Логические операции
Логическая операция — операция над высказываниями, позволяющая составлять новые высказывания путём соединения более простых. В качестве основных операций обычно называют конъюнкцию (∧ или &), дизъюнкцию (∨ или |), импликацию (→), отрицание (¬), эквивалентность (=), исключающее ИЛИ (⊕).
Таблица истинности логических операций
| a | b | a ∧ b | a ∨ b | ¬a | ¬b | a → b | a = b | a ⊕ b |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 |
Как задать логическую функцию
Есть множество способов задать булеву функцию:
- таблица истинности
- характеристические множества
- вектор значений
- матрица Грея
- формулы
Рассмотрим некоторые из них:
Чтобы задать функцию через вектор значений необходимо записать вектор из 2 n нулей и единиц, где n — число аргументов, от которых зависит функция. Например, функцию двух аргументов можно задать так: 0001 (операция И), 0111 (операция ИЛИ).
Чтобы задать функцию в виде формулы, необходимо записать математическое выражение, состоящее из аргументов функции и логических операций. Например, можно задать такую функцию: a∧b ∨ b∧c ∨ a∧c
Способы представления булевой функции
С помощью формул можно получать огромное количество разнообразных функций, причём с помощью разных формул можно получить одну и ту же функцию. Иногда бывает весьма полезно узнать, как построить ту или иную функцию, используя лишь небольшой набор заданных операций или используя как можно меньше произвольных операций. Рассмотрим основные способы задания булевых функций:
- Совершенная дизъюнктивная нормальная форма (СДНФ)
- Совершенная конъюнктивная нормальная форма (СКНФ)
- Алгебраическая нормальная форма (АНФ, полином Жегалкина)
Совершенная дизъюнктивная нормальная форма (ДНФ)
Простая конъюнкция — это конъюнкция некоторого конечного набора переменных, или их отрицаний, причём каждая переменная встречается не более одного раза.
Дизъюнктивная нормальная форма (ДНФ) — это дизъюнкция простых конъюнкций.
Совершенная дизъюнктивная нормальная форма (СДНФ) — ДНФ относительно некоторого заданного конечного набора переменных, в каждую конъюнкцию которой входят все переменные данного набора.
Например, ДНФ является функция ¬a bc ∨ ¬a ¬b c ∨ ac, но не является СДНФ, так как в последней конъюнкции отсутствует переменная b.
Совершенная конъюнктивная нормальная форма (КНФ)
Простая дизъюнкция — это дизъюнкция одной или нескольких переменных, или их отрицаний, причём каждая переменная входит в неё не более одного раза.
Конъюнктивная нормальная форма (КНФ) — это конъюнкция простых дизъюнкций.
Совершенная конъюнктивная нормальная форма (СКНФ) — КНФ относительно некоторого заданного конечного набора переменных, в каждую дизъюнкцию которой входят все переменные данного набора.
Например, КНФ является функция (a ∨ b) ∧ (a ∨ b ∨ c), но не является СДНФ, так как в первой дизъюнкции отсутствует переменная с.
Алгебраическая нормальная форма (АНФ, полином Жегалкина)
Алгебраическая нормальная форма, полином Жегалкина — это форма представления логической функции в виде полинома с коэффициентами вида 0 и 1, в котором в качестве произведения используется операция конъюнкции, а в качестве сложения — исключающее ИЛИ.
Примеры полиномов Жегалкина: 1, a, a⊕b, ab⊕a⊕b⊕1
Алгоритм построения СДНФ для булевой функции
- Построить таблицу истинности для функции
- Найти все наборы аргументов, на которых функция принимает значение 1
- Выписать простые конъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 0, то она входит в конъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые конъюнкции с помощью дизъюнкции
Алгоритм построения СКНФ для булевой функции
- Построить таблицу истинности для функции
- Найти все наборы аргументов, на которых функция принимает значение 0
- Выписать простые дизъюнкции для каждого из наборов по следующему правилу: если в наборе переменная принимает значение 1, то она входит в дизъюнкцию с отрицанием, а иначе без отрицания
- Объединить все простые дизъюнкции с помощью конъюнкции
Алгоритм построения полинома Жегалкина булевой функции
Есть несколько методов построения полинома Жегалкина, в данной статье рассмотрим наиболее удобный и простой из всех.
- Построить таблицу истинности для функции
- Добавить новый столбец к таблице истинности и записать в 1, 3, 5. ячейки значения из тех же строк предыдущего столбца таблицы истинности, а к значениям в строках 2, 4, 6. прибавить по модулю два значения из соответственно 1, 3, 5. строк.
- Добавить новый столбец к таблице истинности и переписать в новый столбец значения 1, 2, 5, 6, 9, 10. строк, а к 3, 4, 7, 8, 11, 12. строкам аналогично предыдущему пункту прибавить переписанные значения.
- Повторить действия каждый раз увеличивая в два раза количество переносимых и складываемых элементов до тех пор, пока длина не станет равна числу строк таблицы.
- Выписать булевы наборы, на которых значение последнего столбца равно единице
- Записать вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора записать единицу) и объединить их с помощью операции исключающего ИЛИ.
Примеры построения различных представлений логических функций
Построим совершенные дизъюнктивную и дизъюнктивную нормальные формы, а также полином Жегалкина для функции трёх переменных F = ¬a b∨ ¬b c∨ca
1. Построим таблицу истинности для функции
| a | b | c | ¬a | ¬a ∧b | ¬b | ¬b ∧c | ¬a ∧b∨ ¬b ∧c | c∧a | ¬a ∧b∨ ¬b ∧c∨c∧a |
| 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 |
Построение совершенной дизъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает истинное значение: < 0, 0, 1 > < 0, 1, 0 > < 0, 1, 1 > < 1, 0, 1 >
В соответствие найденным наборам поставим элементарные конъюнкции по всем переменным, причём если переменная в наборе принимает значение 0, то она будет записана с отрицанием:
Объединим конъюнкции с помощью дизъюнкции и получим совершенную дизъюнктивную нормальную форму:
K1 ∨ K2 ∨ K3 ∨ K4 ∨ K5 = ¬a ¬b c ∨ ¬a b ¬c ∨ ¬a bc ∨ a ¬b c ∨ abc
Построение совершенной конъюнктивной нормальной формы:
Найдём наборы, на которых функция принимает ложное значение: < 0, 0, 0 > < 1, 0, 0 >
В соответствие найденным наборам поставим элементарные дизъюнкции по всем переменным, причём если переменная в наборе принимает значение 1, то она будет записана с отрицанием:
Объединим дизъюнкции с помощью конъюнкции и получим совершенную конъюнктивную нормальную форму:
D1 ∧ D2 ∧ D3 = (a∨b∨c) ∧ ( ¬a ∨b∨c) ∧ ( ¬a ∨ ¬b ∨c)
Построение полинома Жегалкина:
Добавим новый столбец к таблице истинности и запишем в 1, 3, 5 и 7 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 2, 4, 6 и 8 сложим по модулю два со значениями из соответственно 1, 3, 5 и 7 строк:
| a | b | c | F | 1 | |
| 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 0 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 1 | 1 | 0 | 0 | → | 0 |
| 1 | 1 | 1 | 1 | ⊕ 0 | 1 |
Добавим новый столбец к таблице истинности и запишем в 1 и 2, 5 и 6 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 3 и 4, 7 и 8 сложим по модулю два со значениями из соответственно 1 и 2, 5 и 6 строк:
| a | b | c | F | 1 | 2 | |
| 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | ⊕ 0 | 1 |
| 0 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | → | 0 |
| 1 | 0 | 1 | 1 | 1 | → | 1 |
| 1 | 1 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
Добавим новый столбец к таблице истинности и запишем в 1 2, 3 и 4 строки значения из тех же строк предыдущего столбца таблицы истинности, а значения в строках 5, 6, 7 и 8 сложим по модулю два со значениями из соответственно 1, 2, 3 и 4 строк:
| a | b | c | F | 1 | 2 | 3 | |
| 0 | 0 | 0 | 0 | 0 | 0 | → | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | → | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | → | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | ⊕ 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | ⊕ 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | ⊕ 1 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | ⊕ 1 | 1 |
Окончательно получим такую таблицу:
| a | b | c | F | 1 | 2 | 3 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 | 0 | 1 |
Выпишем наборы, на которых получившийся вектор принимает единичное значение и запишем вместо единиц в наборах имена переменных, соответствующие набору (для нулевого набора следует записать единицу):
Объединяя полученные конъюнкции с помощью операции исключающего или, получим полином Жегалкина: c⊕b⊕bc⊕ab⊕abc
Programforyou — это сообщество, в котором Вы можете подтянуть свои знания по программированию, узнать, как эффективно решать те или иные задачи, а также воспользоваться нашими онлайн сервисами.
Copyright © 2017 — 2023 Programforyou — помощь с программированием | programforyou.ru
Построение полинома Жегалкина по таблице истинности — подробное руководство с пошаговыми инструкциями и примерами
Полином Жегалкина является одним из основных инструментов в теории булевых функций. Он представляет собой многочлен, состоящий из логических операций И, ИЛИ и НЕ, которые применяются к переменным заданной булевой функции. Построение полинома Жегалкина по таблице истинности позволяет компактно описать булеву функцию и выполнять с ней различные операции.
Для построения полинома Жегалкина необходимо знать таблицу истинности функции. Таблица истинности состоит из набора значений переменных и результатов функции для каждого набора. Учитывая эту таблицу, можно построить полином Жегалкина, используя следующий алгоритм:
- Выбрать каждую комбинацию значений переменных из таблицы истинности и записать их в виде чисел в двоичной системе счисления.
- Подставить каждую комбинацию значений переменных в функцию и записать соответствующее значение функции (0 или 1).
- Воспользоваться этими значениями для записи полинома Жегалкина.
Построение полинома Жегалкина позволяет упростить анализ и работы с булевыми функциями. Он может быть использован для оптимизации работы логических схем, программирования, а также для анализа электронных сигналов и построения автоматических систем.
Определение полинома Жегалкина
Данный полином представляет собой сумму произведений литералов и их отрицаний. Литералами могут быть переменные или их отрицания. Каждое произведение, входящее в полином, называется мономом.
Полином Жегалкина имеет некоторые особенности. Во-первых, он может быть представлен несколькими эквивалентными формами из-за коммутативности операций конъюнкции и дизъюнкции. Во-вторых, полином Жегалкина может быть представлен в нормализованной форме и сокращенной форме.
Нормализованная форма полинома Жегалкина представляет собой сумму всех возможных мономов, где каждый моном присутствует только один раз. Сокращенная форма полинома Жегалкина возникает после упрощения полинома для минимизации его размера.
Построение полинома Жегалкина по таблице истинности заключается в поиске произведений переменных и их отрицаний, которые присутствуют во всех строках таблицы истинности, где значение функции равно 1. Эти произведения и составляют полином Жегалкина.
Назначение полинома Жегалкина
Назначение полинома Жегалкина заключается в исследовании и анализе логических выражений, а также в их преобразовании и оптимизации. С помощью полинома Жегалкина можно упростить сложные логические функции, а также выполнять операции с ними, такие как сравнение, комбинирование и др.
Полином Жегалкина также широко применяется в различных областях, связанных с теорией информации, автоматизацией процессов и проектированием электронных систем. Он является одним из основных инструментов в алгоритмах синтеза и оптимизации цифровых схем и логических устройств.
Использование в цифровой логике
Использование полинома Жегалкина позволяет удобно описывать логические функции и выполнять операции над ними с помощью алгебры логики. С помощью полинома можно легко определить функциональное поведение цифровых схем, таких как комбинационные логические схемы или автоматы.
Одним из основных преимуществ использования полинома Жегалкина является его компактное представление. Полином можно существенно сократить и упростить, используя правила алгебры логики, такие как законы Де Моргана или законы ассоциативности и дистрибутивности.
Использование полинома Жегалкина также позволяет легко выполнять анализ и оптимизацию цифровых схем. Можно проводить алгебраические преобразования и упрощения полинома, чтобы получить эквивалентное представление функции с меньшим числом переменных или сократить количество логических элементов в схеме.
Применение в синтезе комбинационных схем
Построение полинома Жегалкина по таблице истинности позволяет компактно описывать логические функции и сокращать количество используемых элементов в схеме. Это позволяет экономить ресурсы и упрощает процесс разработки цифровых устройств.
Применение полиномов Жегалкина в синтезе комбинационных схем также позволяет проводить оптимизацию схемы и улучшить ее производительность. Путем преобразования полинома и использования логических законов, можно упростить структуру схемы и уменьшить задержки сигналов.
Кроме того, полиномы Жегалкина позволяют установить эквивалентность различных логических функций и провести анализ их взаимосвязи. Это может быть полезно при оптимизации схемы или при поиске ошибок в проектировании.
Применение полиномов Жегалкина в синтезе комбинационных схем является эффективным инструментом для разработки и оптимизации цифровых устройств. Они позволяют сократить ресурсы и улучшить производительность схемы, а также провести анализ и оптимизацию логических функций.
Построение полинома Жегалкина по таблице истинности
Для построения полинома Жегалкина по таблице истинности необходимо выполнить следующие шаги:
- Записать значения функции в виде таблицы истинности, где каждой комбинации значений аргументов соответствует единственное значение функции.
- Выбрать переменные, которые принимают значение 1 при некоторой комбинации значений аргументов, и записать соответствующие им члены полинома.
- Суммировать все записанные члены полинома для получения итогового полинома Жегалкина.
Например, рассмотрим таблицу истинности функции F(A, B, C):
| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
При анализе данной таблицы истинности видно, что функция F равна 1 при комбинациях значений аргументов (0, 0, 0), (0, 1, 0), (1, 0, 1) и (1, 1, 0). Соответственно, мы можем записать полином Жегалкина в следующем виде:
F = A’BC + AB’C + AC’
Таким образом, мы получили полином Жегалкина, представляющий данную функцию F. Этот полином можно использовать для анализа и оптимизации данной булевой функции.
Шаг 1: Расчет множества Мак-Класки
Для построения полинома Жегалкина необходимо сначала вычислить множество Мак-Класки.
Множество Мак-Класки представляет собой набор всех столбцов таблицы истинности, для которых функция принимает значение «1».
Для этого нужно пройтись по каждой строке таблицы истинности и проверить значение функции в соответствующем столбце. Если значение равно «1», то соответствующий столбец добавляется в множество Мак-Класки. Если значение равно «0», то столбец не добавляется.
Результатом шага будет множество Мак-Класки, которое будет использоваться на следующем шаге построения полинома Жегалкина.
-
Таблица истинности:
| A | B | C | Функция |
|---|---|---|---|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Шаг 2: Расчет элементов полинома
После составления таблицы истинности, необходимо расcчитать элементы полинома Жегалкина. Каждый элемент полинома представляет собой произведение соответствующих переменных, которые принимают значение 1 в соответствующих строках таблицы истинности.
Расчет проводится следующим образом:
- Для каждого набора переменных, где значение функции равно 1, записываем произведение переменных. Если переменная равна 0, то она не включается в произведение.
- Суммируем все полученные произведения и записываем их в виде суммы.
- Пусть дана функция F(a, b, c) = a’bc + ab’c’.
- Составляем таблицу истинности:
| a | b | c | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |
- Расчитываем элементы полинома:
- Для F = 1, соответствующая строка таблицы истинности: a = 1, b = 0, c = 1. Произведение переменных: a’b’c = 1 * 0 * 1 = 0.
- Для F = 1, соответствующая строка таблицы истинности: a = 1, b = 1, c = 1. Произведение переменных: abc = 1 * 1 * 1 = 1.
- Складываем произведения: 0 + 1 = 1.
- Получаем полином Жегалкина для функции F(a, b, c) = a’bc + ab’c’: F(a, b, c) = 1.
Таким образом, произведение переменных, где значение функции равно 1, позволяет построить полином Жегалкина.
Присваивание коэффициентов
Каждая переменная принимает два значения: 0 или 1. Коэффициенты для переменных соответствуют булевому значению: если переменная принимает значение 0, то ей присваивается коэффициент 0, если переменная принимает значение 1, то коэффициент равен 1.
Например, если в таблице истинности есть три переменные A, B, C, то всего будет 2 3 = 8 комбинаций значений переменных. Присвоим коэффициенты переменным следующим образом:
- Для A=0 коэффициент равен 0
- Для A=1 коэффициент равен 1
- Для B=0 коэффициент равен 0
- Для B=1 коэффициент равен 1
- Для C=0 коэффициент равен 0
- Для C=1 коэффициент равен 1
Таким образом, получим значения коэффициентов для каждой комбинации значений переменных. Например, комбинация A=1, B=0, C=1 будет иметь коэффициенты: 1, 0, 1 соответственно.
Присваивание коэффициентов является первым шагом в построении полинома Жегалкина и позволяет связать значения переменных с их булевыми коэффициентами.
Расчет канонической формы
Для построения полинома Жегалкина по таблице истинности необходимо выполнить некоторые шаги:
- Составить список дизъюнкций, где каждая дизъюнкция соответствует одной строке таблицы истинности, в которой значение функции равно 1.
- Разложить каждую дизъюнкцию на конъюнкции, где каждая конъюнкция соответствует переменным функции, принимающим значение 1 в данной строке таблицы истинности.
- Выразить каждую конъюнкцию в виде произведения переменных и их отрицаний.
- Привести произведения переменных и их отрицаний к канонической форме полинома Жегалкина, используя законы алгебры логики и свойства отрицания.
Например, для таблицы истинности:
| X | Y | Z | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
Каноническая форма полинома Жегалкина будет выглядеть следующим образом:
F = Y’Z + XY’Z’ + XYZ’
Таким образом, проведя вышеописанные шаги, мы можем построить полином Жегалкина по таблице истинности.
Sally-Face.ru — это отличный ресурс для тех, кто ищет свежие вопросы и ответы на самые разные темы. На сайте собрана огромная база знаний, которая поможет вам быстро и легко найти ответы на интересующие вас вопросы.
Одной из главных особенностей сайта является его актуальность. Администрация регулярно обновляет базу данных, добавляя новые вопросы и ответы на самые разные темы. Благодаря этому вы всегда можете быть уверены в том, что найдете на сайте самую актуальную информацию.
Кроме того, на сайте Sally-Face.ru вы можете найти ответы на вопросы, которые вам не удалось найти на других ресурсах. На сайте собраны ответы на самые разные вопросы, начиная от технических и заканчивая медицинскими.
Если вы обнаружили неточность или ошибку в ответе на сайте, вы всегда можете сообщить об этом администрации. Для этого на сайте есть специальная форма обратной связи, которую можно заполнить, чтобы сообщить об ошибке.
В целом, сайт Sally-Face.ru является одним из лучших ресурсов для тех, кто ищет свежие и актуальные ответы на самые разные вопросы. Благодаря его удобному интерфейсу и огромной базе данных вы можете быстро и легко найти ответы на все свои вопросы.