Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Обобщенные полиномы Чебышева-Лагерра
  2. Производящая функция и полиномы Лежандра

Полиномом (многочленом) Жегалкина от ппеременных называется функция

P = a0 + a1x1 +a2x2 + ...anxn +an +1x1x2 +...+an+C2nxn-1xn + ...+a2n-1 x1x2..xn

Всего здесь 2пслагаемых. Напомним, что + сейчас означает сложение по модулю 2, коэффициенты a0, a1,..., a2n-1 являются константами (равными нулю или единице).

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

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

Доказательство этой теоремы показывает, как по таблице истинности построить полином Жегалкина.

 

Имеется 2-й способ нахождения для функций, заданных в виде ДНФ. Этот способ основан на том, что х+1 = . Если функция задана в виде ДНФ, то сначала убираем дизъюнкцию, используя при этом правило де Моргана, а все отрицания заменяем прибавлением единицы. После этого раскрываем скобки по обычным правилам, при этом учитываем, что четное число одинаковых слагаемых равно нулю (так как х + х = 0), а нечетное число одинаковых слагаемых равно одному такому слагаемому.

Пример.

( xy + 1) ((x + 1)(y + 1) + 1) ((y + 1)z + 1) + 1 = (xy + 1)(xy + x + y)(yz + z + 1) + 1 = (x + y)(yz + z + 1) + 1= xyz + yz + xz +yz + x + y + 1 = xyz + xz + x +y + 1.

Последнее выражение и есть полином Жегалкина данной функции.

 

Функция f (x1,x2,,xn) называется линейной, если ее содержит только первые степени слагаемых. Более точно функция называется линейной, если ее можно представить в виде

f(x1, x2,…, xn) = a0 + a1 x1 + a2 x2 +…+ an xn.

Класс линейных функций часто обозначают через L.(Заметим, что число линейных функций п переменных равно 2п+1).

Класс линейных функций часто обозначают через L.(Заметим, что число линейных функций п переменных равно 2п+1).

Замечание. Если пі2 то линейная функция в таблице истинности может содержать только четное число единиц.Действительно, если f(x1,x2,, xn) = x1+ x2+…+xn, то легко видеть что такая функция в таблице истинности содержит одинаковое число нулей и единиц а именно 2п/2 единиц и нулей, т. е. число это четно при пі2. Столько же нулей и единиц имеет функция.Добавлениежефиктивнойпеременной приводитк увеличению числа единиц (и нулей) в два раза. Разумеется, нелинейная функция может иметь в таблице истинности как четное, так и нечетное число единиц.

 

 

Теорема Поста

Получение совершенной дизъюнктивной и конъюнктивной нормальных форм


Дата добавления: 2015-07-07; просмотров: 126 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
Функционально полные базисы.| Минимизация булевых функций с помощью матрицы Квайна

mybiblioteka.su - 2015-2021 год. (0.016 сек.)