Полином жегалкина как сделать

Добавил пользователь Владимир З.
Обновлено: 19.09.2024

Полином Жегалкина — многочлен над полем Z 2 _> , то есть полином с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. Полином был предложен в 1927 году Иваном Жегалкиным в качестве удобного средства для представления функций булевой логики. В зарубежной литературе представление в виде полинома Жегалкина обычно называется алгебраической нормальной формой (АНФ).

Теорема Жегалкина — утверждение о существовании и единственности представления всякой булевой функции в виде полинома Жегалкина [1] .

Полином Жегалкина представляет собой сумму по модулю два попарно различных произведений неинвертированных переменных, где ни в одном произведении ни одна переменная не встречается больше одного раза, а также (если необходимо) константы 1 [1] . Формально полином Жегалкина можно представить в виде

или в более формализованном виде как

P = a ⊕ ⨁ 1 ⩽ i 1 … i k ⩽ n k ∈ 1 , n ¯ a i 1 , … , i k ∧ x i 1 ∧ … ∧ x i k , a , a i 1 , … , i k ∈ < 0 , 1 >. 1\leqslant i_

A⊕B=B⊕A
A ⊕ B ⊕ C = C ⊕ A ⊕ B = B ⊕ C ⊕ A =
B ⊕ A ⊕ C = C ⊕ B ⊕ A = A ⊕ C ⊕ B =

(A ⊕ B) ⊕ C = A⊕ (B ⊕ C),
(A ⊕ B) ⊕ (C ⊕ D) = A ⊕ B ⊕ C ⊕ D = B ⊕ A ⊕ C ⊕ D

Дистрибутивность конъюнкции относительно суммы по модулю два:

Сумма по модулю два относительно конъюнкции не дистрибутивна, т. е.:

A ⊕ (B*C) ≠ (A ⊕ B)*(A ⊕ C)
(A*B) ⊕ C ≠ (A ⊕ C)*(A ⊕ B)

A ⊕ A = 0
A ⊕ 0 = A
A ⊕ 1 = ⌐A
1 ⊕ 1 = 0
0 ⊕ 0 = 0
0 ⊕ 1 = 1
Вычислим, например, значение выражения
1⊕0*1⊕1*1=1⊕0⊕1=1⊕1=0.

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

H(x1,x2,…, xn)=C0 ⊕ C1 x1 ⊕C2 x2⊕ Cn xn⊕ C12 x1 x2⊕ C13 x1 x3⊕…⊕ C1…n x1…xn,

где C0, C1, …, C1…n – коэффициенты при переменных 1, x1, x2,…xn, x1x2,…, x1…xn соответственно.
Теорема. Любая функция п переменных может быть представлена полиномом Жегалкина и это представление единственно.
Доказательство. Любая функция f(x1, x2, …, xn) имеет свою таблицу истинности. Запишем сначала данную функцию в виде полинома Жегалкина с неопределенными коэффициентами. Затем по очереди подставляем всевозможные наборы переменных и находим коэффициенты. Легко видеть, что за каждую подстановку находим только один коэффициент. Так как число наборов равно числу коэффициентов (и равно 2п), отсюда следует утверждение теоремы.
Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.
Для булевых функций двух переменных полином Жегалкина имеет вид:

Определим булевы функции двух переменных через операции алгебры Жегалкина (т. е. через конъюнкцию и сумму по модулю 2).
Предварительно дадим решение простейших уравнений, вытекающих из определения суммы по модулю 2:
Если a ⊕ 1 = 1, то a = 0
Если a ⊕ 0 = 1, то a = 1
Если a ⊕ 1 = 0, то a = 1
Если a ⊕ 0 = 0, то a = 0.
Функция f0(x1,x2)= есть тождественный ноль.
Функция f1(x1,x2)= есть конъюнкция.
Для функции f2(x1,x2)= определим значения коэффициентов полинома Жегалкина:
f2(0,0) = C0=0
f2(0,1) = C0⊕ C2=0
f2(1,0) = C0⊕ C1=1
f2(1,1) = C0⊕ C1⊕ C2⊕ C12=0

Метод треугольника
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина путём построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000. 00 до 111. 11.
Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
Ячейка в каждом последующем столбце получается путём сложения по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т.д.
Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.

Фактически, этот метод является модификацией метода построения по таблице истинности, описанного выше. По сравнению с ним он удобнее тем, что расчёты занимают мало места и в них сложнее ошибиться, но метод треугольника требует бо́льшего количества операций. Достоинством метода является то, что при построении вспомогательной таблицы коэффициенты полинома просчитываются автоматически.

Пример преобразования таблицы истинности в полином Жегалкина для функции трёх переменных P(A,B,C) показан на рисунке.

Это - еще один способ выразить произвольную булеву функцию через бинарные операции. Мы уже знаем, что произвольную булеву функцию можно выразить через &, и ~ в виде СДНФ. Мы также знаем, что и ~ можно выразить через & и :

Применив эти формулы, мы всякую булеву функцию выразим через операции & и .

Дальше мы можем раскрыть все скобки, кроме самого последнего уровня, применяя правила дистрибутивности (в точной аналогии с тем, как это делалось в школе с раскрытием скобок и приведением подобных членов):

В результате получится формула вида:

где в скобках стоят те или иные наборы аргументов, объединенные операцией &, а сами скобки объединены операцией . После этого формулу можно сократить, убрав повторяющиеся элементы внутри скобок с помощью законов поглощения

Затем выполним дополнительное сокращение, убрав одинаковые скобки с помощью законов поглощения

В результате получится формула, которая и называется полиномом Жегалкина.

Пример составления полинома Жегалкина.

Возьмем СДНФ нашей функции, и упростим его, насколько возможно:

Теперь преобразуем инверсии:

Теперь преобразуем операцию :

Применим законы поглощения внутри скобок:

Применим законы поглощения для одинаковых скобок, учитывая, что переменные, соединенные знаками & можно менять местами:

Это - и есть полином Жегалкина. Таким образом, любую логическую функцию можно выразить в виде полинома Жегалкина: цепочки элементов, соединенных операцией . Каждый элемент - 0, 1, переменная или скобка, в которой несколько переменных,

Как известно, любую функцию, отличную от константы 0, можно представить в виде СДНФ. Если сравним таблицы истинности дизъюнкции и суммы по модулю два, видим, что они отличаются только последней строкой, т.е. на наборе 11. Так как в СДНФ на каждом наборе только одна конъюнкция равна 1, то все дизъюнкции можно заменить суммами по модулю два. Кроме того, известно, что = xÅ1. На этом и основан первый алгоритм построения многочлена Жегалкина:

1. Находим множество тех двоичных наборов, на которых функция принимает значение 1.

2. Составляем СДНФ.

3. В СДНФ каждый знак дизъюнкции меняем на знак суммы Жегалкина.

4. Упрощаем, если можно, полученное выражение, используя тождество

5. В полученной формуле каждое отрицание заменяем на x_i Å1.

7. Приводим подобные члены, используя тождество x_iÅx_i=0.

Пример 1. f (x_1, x_2, x₃) = ;

СДНФ функции = f (x_1, x_2, x₃ )= Ú Ú

Построим многочлен Жегалкина с помощью СДНФ:

выписываем СДНФ функции Ú Ú

заменяем знак дизъюнкции на знак суммы Жегалкина Å

Å Å

вынесем из 1 и 2 конъюнкции :

Ù Å = Å .

Проделаем замены = x₁Å1; = x₂Å1, получаем:

= = = .

Алгоритм перехода к полиному Жегалкина методом логических преобразований

Метод, базирующийся на преобразовании формул над множеством связок . Строят некоторую формулу над множеством связок реализующую заданную функцию, затем заменяют всюду подформулы вида на xÅ1, раскрывают скобки, пользуясь дистрибутивным законом x(yÅz) = xyÅxz, и применяют эквивалентности xx=x, x×1=x, xÅx =0, xÅ0 =x.

Пример 2. x®y = = = x (yÅ1) Å1= xy Å x Å1.

Алгоритм нахождения многочлена Жегалкина методом неопределенных коэффициентов

Составляем систему линейных уравнений относительно неизвестных коэффициентов, решением которой являются коэффициенты многочлена Жегалкина. Число уравнений – 2 n , где n – число неизвестных

Пример 3. Пусть f = xÚy. Запишем полином Жегалкина P(x,y) в общем виде P(x,y) = α₀ Å α₁х Å α₂y Å α₃xy. Придавая возможные значения, выписываем систему уравнений для коэффициентов:

Следовательно, xÚy = xÅyÅxy.

Для проверки составим таблицы истинности левой и правой части равенства.

Вывод: преобразование выполнено верно.

Линейные функции

Функция, у которой полином Жегалкина имеет вид Å g, где

a_i, gÎ, называется линейной.

Иными словами, многочлен Жегалкина называется нелинейным, если он содержит конъюнкции переменных, а если он не содержит конъюнкции переменных, то он называется линейным.

Класс линейных функций обозначается L n (L). Из определения вытекает, что |L n |= 2 n +1 .

В частности, xÅyÎ L, 0ÎL, xy L. Все функции от одной переменной линейны. Линейными функциями от двух переменных являются xÅy и x«y .

Пример 4.Функция f =1001011010010110 = x₂Å x₃Å x₄Å1 линейна.

Работу составила преподаватель Т.С. Пронина

Практическое занятие №10

1 Наименование работы: Операции над множествами.

2 Цель работы: Научиться выполнять операции над множествами.

Формирование ОК 2- 5; овладение знаниями и умениями, необходимыми для освоения ПК 1.2. (спец. 09.02.03.), ПК 1.1, 1.2, 2.4. (спец. 09.02.04.).

3 Подготовка к занятию: Повторите тему: Операции над множествами.

4 Литература:

4.2 Приложение к ПЗ №10.

5 Перечень необходимого оборудования и материалов:

5.1 Бланк для отчета.

5.2 Канцелярские принадлежности.

6 Задание на занятие:

Основная часть

6.1 Опишите множества, заданные ниже:

6.2 Заданы множества:

а) A∆B	г) (A Ç )\B
б) \A	д) (AÈB) Ç (BÈC)
в) (A\B) È C	е) (AÇC) È (AÇB) È (CÇB)

6.3 Заданы множества:

а) AÈBÈCÈD

б) AÇBÇCÇD

в) (AÇB) È (CÇD)

г) (AÈB) Ç (CÈD)

д) (A\B) È (B\A)

6.4 Заданы два множества А = , B = . Определите декартово произведение AxB.

Вариативная часть

6.5 Перечислите элементы множества ;

а) Если x 2 +4x =12, то x(x+4) = 12. Поскольку x – целое число, делящее 12, то оно может быть равно только ±1, ±2, ±3, ±4, ±6 и ±12. С другой стороны, x+4 тоже делит 12. Поэтому остается только два значения: x= -6 или x=2.

Другой способ решения заключается в отыскании корней квадратного уравнения x 2 +4x-12 =0. Он приводит к тому же ответу x= -6 или x=2.

Некоторые множества чисел столь часто используются, что имеют стандартные названия и обозначения.

- пустое множество;

N= – множество натуральных чисел;

Z= – множество целых чисел;

– множество рациональных чисел;

R= – множество вещественных чисел.

В некоторых книгах натуральные числа включают и 0.

Существует несколько способов конструирования нового множества из 2 данных. Опишем коротко эти операции на множествах. Прежде всего отметим, что в вышеприведенных примерах все элементы некоторых множеств принадлежали другим большим множествам. Например, все элементы множества С= содержатся в множестве Z= .

Говорят, что множество С является подмножеством множества Z, если каждый элемент множества С автоматически является элементом множества Z. Довольно часто при этом говорят, что множество C содержится в множестве Z. Этот факт обозначают как C Ì Z. Два множества считаются равными, если каждое из них содержится в другом.

Показать, что A=B.

Решение. Если xÎA, то x 2 – нечетное целое число. Само число x - целое и нечетное. Следовательно, xÎB, т.е. А Ì В.

В обратную сторону, пусть xÎB. Тогда x - нечетное целое число. В этом случае x 2 тоже будет нечетным целым числом, а значит, xÎА. В виду произвольности взятого элемента xÎB мы можем утверждать, что все элементы из В принадлежат А т.е. В Ì А. Итак, А=В.

Объединением двух множеств А и В называется множество

Оно состоит из тех элементов, которые принадлежат либо множеству А, либо множеству В, а возможно и обоим сразу.

Пересечением двух множеств А и В называется множество

Оно состоит из элементов, которые принадлежат как множеству А, так и множеству В.

Дополнением множества В до множества А называется А\В= . Дополнение А\В состоит из всех элементов множества А, которые не принад-лежат В.

Если мы оперируем подмножествами некоего большого множества U, мы называем U универсальным множеством для данной задачи.

Для подмножества А универсального множества U можно рассматривать дополнение А до U, т.е. U\А. Поскольку в каждой конкретной задаче универсаль-ное множество фиксировано, множество U\А обычно обозначают и называют просто дополнением множества А. Таким образом, понимая, что мы работаем с подмножествами универсального множества U, можно записать

= Û = .

Симметрической разностью двух множеств А и В называют множество

Оно состоит из всех тех и только тех элементов универсального множества, которые либо принадлежат А и не принадлежат В, либо наоборот, принадлежат В, но не А. Грубо говоря, симметрическая разность состоит из элементов, лежащих либо в А, либо в В, но не одновременно.

Найдите АÈС, ВÇС, А\С и В∆С.

Пример 4. Пусть

Убедитесь, что =

Решение. Прежде всего заметим, что универсальным множеством здесь служит U= .

Фиксируем алфавит булевых переменных .

Напомним, что

Определение 1.Элементарной конъюнкцией ранга относительно алфавита назовем форму ,

где . При конъюнкция называется совершенной.

Определение 2. Дизъюнктивной нормальной формой (ДНФ) относительно алфавита называется любая дизъюнкция элементарных конъюнкций. Совершенной дизъюнктивной нормальной формой относительно алфавита называется любая дизъюнкция различных совершенных конъюнкций (СДНФ).

Отметим все важные свойства совершенных конъюнкций:

а) произведение двух различных совершенных конъюнкций равно ;

б) в совершенной дизъюнктивной нормальной форме относительно алфавита при подстановке фиксированного набора либо все совершенные конъюнкции равны нулю, либо равна одна единственная конъюнкция.

Действительно, при произведение

(1)

c одержит для некоторого множители и , отсюда , и поэтому произведение (1) равно . Далее для любого набора уравнение влечет . – единственно возможное решение, т.к. если для некоторого имеем , то и нулю равна вся конъюнкция.

Теорема. Всякая функция алгебры логики представима совершенной дизъюнктивной нормальной формой относительно алфавита своих переменных . :

(2)

Дизъюнкция идет по всем наборам, в которых функция равна . Формула (2) следует непосредственно из свойств совершенных конъюнкций.

Вопрос. Чем является функция ?

ДНФ (дизъюнктивная нормальная форма)

Да, правильно. Так как во втором слагаемом нет переменной .

Составление СДНФ

Пример 1. Совершенные ДНФ для элементарных функций (табл. 2):

для конъюнкции: ;

для дизъюнкции: ;

для сложения по mod 2: ;

для импликации: ;

для эквиваленции: ;

для штриха Шеффера: ;

для отрицания : ;

для селекторной функции : ;

для константы : ;

константа не имеет СДНФ.

Пример 2. Написать СДНФ относительно алфавита , , для функции голосования от трех переменных, заданной таблично (см. табл. 3).

СДНФ для содержит четыре совершенные конъ-юнкции (по числу единиц функции)

.

Пример 3. Преобразовать в СДНФ формулу относительно алфавита , , .

Данная формула есть ДНФ, но имеет несовершенные конъюнкции. С помощью преобразований вида доводим конъюнкции до совершенства:
,
раскроем скобки
,
собираем подобные члены по правилу :
.
Это и есть СДНФ.

Замечание. Если функция задана формулой, то можно для функции вычислить таблицу, а затем задача сведется к примеру 2. Однако создание таблицы может оказаться очень трудоемким. Так, например, если алфавит переменных состоит из переменных, то таблица имеет строк, что неприемлемо, так как потребуется много места на доске или бумаге.

Вопрос. Сколько элементарных конъюнкций содержится в СДНФ для функции, заданной своими значениями ?

Да, правильно. Потому что функция равна 1 только на трех наборах.

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

Элементарные конъюнкции вида , , …, , (конъюнкция нулевого ранга) называются положительными элементарными конъюнкциями.

Любая сумма по различных положительных конъюнкций называется полиномом Жегалкина. Константу считаем нулевым полиномом Жегалкина. Тогда справедливо утверждение:

Теорема.Всякая функция алгебры логики представима полиномом Жегалкина единственным образом с точностью до перестановки слагаемых.

Доказательство. Если , то представима СДНФ
. (3)
В силу совокупной ортогональности совершенных конъюнкций в (3) знаки дизъюнкции можно заменить на знаки , что приведет к формуле
. (4)
Удаляя в (4) отрицания переменных по формуле , раскрывая скобки и приведя подобные члены по правилу , мы получим полином Жегалкина. Единственность представления функции полиномом следует из того, что полиномов Жегалкина под алфавитом ,…, столько же, сколько и функций от переменных, то есть . ▲

Вопрос. Чем является данная функция ?

Пример составления полинома Жегалкина

Пример 1. Пусть задана функция таблицей.

Представим ее СДНФ
.
Отсюда имеем
.
Раскрываем скобки:
.
Приводим подобные члены:
.
Получили полином Жегалкина.

Пример 2. Пусть задана функция формулой .

ДНФ функции состоит из двух ортогональных конъюнкций ( ), поэтому
.
Получили полином Жегалкина.

Пример 3. Для элементарных функций табл. 2 полиномы Жегалкина имеют вид:

а) для конъюнкции – ;

б) для дизъюнкции – ;

в) для суммы по – ;

г) для импликации – ;

д) для эквиваленции – ;

ж) для : ;

з) для , , , – без изменений.

Вопрос. Чему равен полином Жегалкина для функции ?

Теорема двойственности

Функция называется двойственной к функции .

Из определения следует, что таблица для двойственной функции может быть получена из таблицы для функции заменой всех нулей на единицы и всех единиц на нули.

Если оказывается, что , то функция называется самодвойственной. Самодвойственная функция на противоположных наборах принимает противоположные значения, т.е. для любого набора .

Отношение двойственности симметрично, .

Пример 1. Двойственные функции к элементарным функциям табл. 2:
, , ,
, , ,
, , , , .

Пример 2. Является ли функция самодвойственной?
Чтобы ответить на этот вопрос, можно составить (вычислить) таблицу и по таблице проверить значения функции на противоположных наборах, и если найдется пара противоположных наборов, на которых функция принимает одинаковые значения, то функция несамодвойственна.
Можно также перейти к двойственной функции

и вычислять одновременно значения двух функций и , и как только обнаружится, что на наборе будем иметь , значит, функция несамодвойственна. В противном случае – самодвойственная, но цена этому выводу высока – ведь вычислены таблицы двух функций. Наконец, если преобразовать и к полиномам Жегалкина, и полиномы оказались разные, то и – несамодвойственна.

Теорема двойственности. Пусть имеется формула (тождество)
,
тогда верно тождество
.

Доказательство.

. ▲

С помощью этой теоремы легко доказываются некоторые тождества. Например,

1) из формулы де Моргана и теоремы двойственности следует другая формула де Моргана, так как влечет ;

2) из формулы (формула сокращения) следует , по теореме двойственности получаем другую формулу сокращения ;

3) из формулы получаем и отсюда .

Замечание. Операция меняет приоритетность операндов, поэтому во избежание ошибок в начальной формуле надо отменить приоритетность, то есть должны быть расставлены все скобки, выделяющие бинарные операции.

Вопрос. Является ли функция , заданная таблично, самодвойственной?

Правильно, так как таблица не симметрична.

Определение СКНФ

Элементарной дизъюнкцией ранга относительно алфавита назовем форму
,
где . При дизъюнкция называется совершенной.

Любая конъюнкция элементарных дизъюнкций называется конъюнктивной нормальной формой (КНФ). Любая конъюнкция совершенных дизъюнкций называется совершенной конъюнктивной нормальной формой (СКНФ).

Теорема. Всякая функция алгебры логики представима совершенной конъюнктивной нормальной формой
.

Доказательство. Из условия теоремы запишем СДНФ для функции
,
отсюда и из теоремы двойственности имеем

, что и требовалось доказать. ▲

Вопрос. Чем является функция ?

Правильно, так как во второй скобке содержатся не все переменные.

Примеры составления СКНФ

Пример 1. Совершенные КНФ для элементарных функций табл. 1 относительно алфавита переменных , :

для конъюнкции: ;

для дизъюнкции: ;

для суммы по : ;

для импликации: ;

для эквиваленции: ;

для отрицания : ;

для селекторной функции : ;

для константы ;

для константы СКНФ не существует.

Пример 2. Написать СКНФ для функции голосования.

СКНФ для (она содержит четыре нуля и поэтому состоит из четырех совершенных дизъюнкций):

Пример 3. Преобразовать в СКНФ формулу относительно алфавита , , .

Данная формула есть ДНФ. Преобразуем ее сначала в КНФ:
.
Преобразуем дизъюнкции в совершенные:

.

Вопрос. Как выглядит СКНФ для функции, заданной таблично?

Читайте также: