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

Лекция № 12

Читайте также:
  1. Лекция (1 час).
  2. Лекция (1 час).
  3. ЛЕКЦИЯ (методическая разработка)
  4. ЛЕКЦИЯ (методическая разработка)
  5. ЛЕКЦИЯ (методическая разработка)
  6. Лекция 1
  7. Лекция 1

(лек. 2 час + прак. занят 2 час + самос. 4 час)

Синтез с помощью булевых функций электронных схем (на примере сумматора)

 

 

Многочлены Жегалкина

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

Многочленом Жегалкина называется многочлен, являющийся сум­мой константы и различных одночленов, в которые каждая из перемен­ных входит не выше, чем в первой степени.

Многочлен Жегалкина константы равен самой же константе;

мно­гочлен Жегалкина булевой функции одной переменной ;

многочлен Жегалкина булевой функции двух переменных

;

многочлен Жегалкина булевой функции трех переменных

и т.д. Коэффициенты a1,...,i и свободный член а0 принимают значения 0 или 1, а число слагаемых в формуле равно 2n, где п число переменных. Знак — сумма Жегалкина или сумма по модулю два.

 

Теорема 3 (Жегалкина). Каждая булева функция f(х1, х2, . . . , хп) может быть представлена в виде многочлена Жегалкина и притом единственным образом, с точностью до порядка слагаемых.

 

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

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

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

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

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

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

6. Раскрываем скобки в полученной формуле, содержащей только функции и и константу 1.

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

 

Используя метод неопределенных коэффициентов, получаем второй алгоритм определения многочлена Жегалкина:

1. Составляем систему линейных уравнений относительно 2n неиз­вестных коэффициентов, содержащую 2n уравнений, решением которой являются коэффициенты а0, a1, . . . , а12…n многочлена Жегалкина.

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

Функция f(х1, х2, . . . , хп) называется линейной, если ее многочлен Же­галкина имеет вид , и нелинейной в противном случае.

Из определения многочлена Жегалкина следует, что для любой буле­вой функции коэффициенты при переменных х1, х2, . . . , хп и свободный член вычисляются по формулам:



а0 = f(0, 0, . . . ,0),

,

,

…………..

.

На этом основан алгоритм определения линейности (или нелинейно­сти) булевой функции.

1. По таблицам истинности булевой функции f(х1, х2, . . . , хп) и выше указанным формулам находим коэффициенты: о, а1, ... , аn).

2. Выписываем многочлен и про­веряем, задает ли он эту функцию. Для этого строим таблицу истинности многочлена Ф(х1, х2, . . . , хп) и сравниваем ее с таблицей истинности функ­ции f(х1, х2, . . . , хп).

Если таблицы истинности совпадают, то функция f(х1, х2, . . . , хп) ли­нейная и Ф(х1, x2, . . . ,xп) ее многочлен Жегалкина. В противном случае функция нелинейная.


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


Читайте в этой же книге: Полиномы Жегалкина | Минимизация булевых функций с помощью матрицы Квайна | Минимизация булевых функций с помощью карт Карно |
<== предыдущая страница | следующая страница ==>
Социально-экономические последствия инфляции.| Функционально полные базисы.

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