Сделай Сам Свою Работу на 5

Булевы многочлены и булевы функции





Для описания алгебраических свойств булевых алгебр используются формулы, которые называются булевыми многочленами и которые образованы из булевых переменных x,y,…(принимающих значения 0,1) и символов булевых операций +,×,¢ по следующим правилам:

1) все булевы переменные x,y,… и символы 0,1 – булевы многочлены;

2) если p и q – булевы многочлены, то таковыми являются выражения

.

Если p образован с помощью , то он обозначается .

Множество всех булевых многочленовот n переменных обозначим Pn .

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

Каждый булев многочлен определяет отображение Bn®B , которое называется булевой полиномиальной функцией, определяемой булевым многочленом .

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

Символическая запись: или просто .

Бинарное отношение ~ является эквивалентностью на множестве .

Классы эквивалентности , образуют фактор-множество .

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



Для булевой переменной x и aÎ{0,1}положим:

Выражение называется литерой.

Литера или конъюнкция (соответственно, дизъюнкция) литер называется конъюнктом (соответственно, дизъюнктом).

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

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

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

Теорема. Любая булева функция f:Bn®B является булевой полиномиальной функцией следующих булевых многочленов:

и

.

Следствие 1. Если булева функция f:Bn®B не равна тождественно нулю, то она является булевой полиномиальной функцией следующей совершенной дизъюнктивной нормальной формы

,

которая называется совершенной дизъюнктивной нормальной формой (сокращенно СДНФ) функции f .



Следствие 2. Если булева функция f:Bn®B не равна тождественно единице, то она является булевой полиномиальной функцией следующей совершенной конъюнктивной нормальной формы

,

которая называется совершенной конъюнктивной нормальной формой (сокращенно СКНФ) функции f .

Системы булевых функций

Операция отрицания ¢ является одной из четырех булевых функций от одной переменной, которые перечисляются в следующей таблице:

 

x

 

Операции дизъюнкция + и конъюнкция × являются примерами двух из шестнадцати булевых функций от двух переменных, которые перечисляются в следующей таблице:

x y
  × x y Å + ¯ «   ® ½

Функция - штрих Шеффера, обозначается .

Функция - стрелка Пирса, обозначается .

 

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

.

Для упрощения записи суперпозиции булевых функций скобки по возможности опускаются с учетом следующего приоритета выполнения булевых операций: ¢, × и затем все остальные операции.

 

Лемма. Булевы функции от двух переменных взаимосвязаны следующими свойствами:

1) , – законы де Моргана;

2) , – законы поглощения;



3) , – характеристическое свойство отрицания;

4) , – характеристическое свойство элемента 1;

5) , – характеристическое свойство элемента 0;

6) , – взаимосвязь конъюнкции и дизъюнкции;

7) , – взаимосвязь импликации с дизъюнкцией, конъюнкцией и отрицанием;

8) , ;

9) , , , – взаимосвязь штриха Шеффера с дизъюнкцией, конъюнкцией и отрицанием;

10) , , , – взаимосвязь стрелки Пирса с дизъюнкцией, конъюнкцией и отрицанием;

11) , , , , , – характеристическое свойство суммы Жегалкина;

12) , , , – взаимосвязь суммы Жегалкина с дизъюнкцией, конъюнкцией, отрицанием, импликацией и эквивалентностью.

 

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

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

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

Определение. Булева функция f называется линейной, если ее представление полиномом Жегалкина не содержит произведения переменных.

Множество всех линейных булевых функций обозначим символом L.

Определение. Булева функция называется самодвойственной, если .

Множество всех самодвойственных булевых функций обозначим символом S.

Определение. Булева функция называется монотонной, если для любых из следует .

Множество всех монотонных булевых функций обозначим символом M.

Пусть P0 - класс всех булевых функций , удовлетворяющих условию .

Пусть P1 - класс всех булевых функций , удовлетворяющих условию .

 

Определение. Классы булевых функций L,S,M,P0,P1 называются классами Поста.

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

Переключательные схемы

Переключатель - электромагнитное реле с контактами и индукционной катушкой, состояние которой моделируется булевой переменной x: x=1 - в катушке идет ток, и x=0 - в катушке тока нет.

Контакты реле – замыкающие или размыкающие.

Через замыкающий контакт реле ток проходит в том и только том случае, если x=1 - такой контакт моделируется булевой переменной x.

Через размыкающий контакт реле ток проходит в том и только том случае, если x=0 - такой контакт моделируется отрицанием булевой переменной x¢.

 








Не нашли, что искали? Воспользуйтесь поиском по сайту:



©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.