Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Разложение булевых функций по переменным


Помощь в написании учебных работ
1500+ квалифицированных специалистов готовы вам помочь

Введем понятие степени булевой переменной x

Рассмотрим функцию вида f(x1,x2,x3)

x1 x2 x3 f

Выделим переменную x1 и рассмотрим функцию f относительно нее.

Все множество наборов <a1, a2, a3> таблицы истинности разбивается на два подмножества, в каждом из которых по четыре набора <0, a2, a3> и <1, a2, a3>.

Тогда функцию f(x1,x2,x3) можно представить в виде дизъюнкции двух функций от двух переменных и эта формула будет иметь вид:

Рассмотрим следующие формулы:

Левая часть первой формулы эквивалентна правой, поскольку для x1=0 и в соответствии с операцией конъюнкции. Аналогично можно показать справедливость второй формулы. Таким образом, поставив эти формулы в предыдущую дизъюнкцию, получим:

(*1)

Это выражение называется разложением функции f(x1,x2,x3) по переменной x1.

Теперь аналогично можно разложить функции f(0,x2,x3) и f(1,x2,x3) по переменной x2. Получим

(*2)

Подставляя эти формулы в предыдущие получим

Внесем в соответствии с дистрибутивностью операции & переменную x1 и ее инверсию в скобки, получим

Далее разложим f(x1,x2,x3) по переменной x3. Получим

(*3)

В общем виде для функции f(x1,x2,..,xn) от n переменных разложение по m переменным (m£n) имеет вид

, (*4)

где дизъюнкция берется по всем 2m наборам переменных x1,x2,..,xm.

Рассмотрим разложение (*4) при крайнем случае, когда m=n. (см. пример (*3)).

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

Проделаем все это для примера (*3).

После удаления из (*3) конъюнкций с нулевыми значениями функции f на заданных наборах, получим:



Так как в соответствии с таблицей истинности

f(0,0,0) = f(0,1,0) = f(1,1,0) = f(1,1,1)=1

то из конъюнкций уберем сомножители функций, после чего получим:

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

 

Лемма. Любая булева функция (кроме константы "0") имеет СДНФ, при том только одну.

Аналогично можно ввести конъюнктивную форму,

Построение СДНФ для функции, заданной таблицей

Данное следствие носит конструктивный характер, т.к. оно по таблице функции позволяет построить формулу, являющуюся СДНФ (если ).
СДНФ функции f содержит ровно столько конъюнкций, сколько единиц в таблице f; каждому “единичному” набору (d 1,…,d n), т.е. набору, на котором значение функции равно 1, соответствует конъюнкция всех переменных, в которой xi взято с отрицанием, если d i=0, и без отрицания, если d i=1.

Пример 5.1. Записать СДНФ для функции x1 ® x2.

x1 x2 x1 ® x2 Основная элементарная конъюнкция
0 0 1
0 1 1 x2
1 0 0  
1 1 1 x1x2

.

<== предыдущая лекция | следующая лекция ==>
Возможные исходы нелеченного | Представление логических функций булевыми формулами

Дата добавления: 2014-01-03; Просмотров: 2402; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Читайте также:
studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.