Студопедия

КАТЕГОРИИ:

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


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




 

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

Любая булева функция может быть представлена полиномом Жегалкина, поскольку любая ДНФ или КНФ с помощью равенств (3.1.) и (3.2.) может быть преобразована в формулу алгебры Жегалкина, в которой всегда можно избавиться от скобок (если они там есть) с помощью тождества 5 (дистрибутивность относительно ) [4].

Пример3.1. Найти полином Жегалкина для булевой функции эквиваленция.

Решение. С учетом (3.1.) и (3.2.) имеем

Получили полином Жегалкина для эквиваленции

 

. (3.3.)

 

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

Линейные функции это сама операция сложения по модулю два , а также инверсия и эквиваленция (соотношения (3.1.) и (3.3.) соответственно). Примерами нелинейных булевых функций являются конъюнкция (ее полином Жегалкина ), дизъюнкция, т.к., согласно (3.2.), ее полином содержит конъюнкцию и ряд других функций.

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

 

Пример 3.2. Проверить свойство линейности для импликации.

Решение. Вычислим полином Жегалкина для импликации, используя соотношения.

Получим

.

 

Импликация – нелинейная функция, поскольку ее полином Жегалкина содержит конъюнкцию двух переменных

 

. (2.4.)

 

 


Поделиться:

Дата добавления: 2015-08-05; просмотров: 168; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.007 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты