yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->1. 7. Свойства булевых функций

Математическая логика

1. 7. Свойства булевых функций

Определение 1.1В. Пусть дана некоторая булева формула А. Формула А* называется двойственной формуле А, если она получается из формулы А путем замены операций конъюнкции на дизъюнкцию, дизъюнкции на конъюнкцию, 1 на 0, 0 на 1 всюду, где они входят.

Припер. A=xyv¬x¬y; A*=(xvy)( ¬xv¬y).

Теорема. Если А(х1...,хn) и А*(х1...,хn) - две взаимно двойственные формулы то

¬A(x1  .....¬xn) A*(¬x,,... ¬xn)

Определение 148- Функция называется самодвойственной, если она двойственна самой себе, т. е. А(х12,...,х„)= ¬A(¬x1, ¬x2 ....... ¬xn ), или ¬A(x1,x2,...,xn)=A(¬x1, ¬x2 ,..., ¬xn).

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

1.8. Функционально замкнутые классы булевых функций

Определение      1.20.      Класс      функций      называется      функционально

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

а1х1 а2х2 ...аiхi...an x nу/ Подставим вместо x1 линейный полином  . Получим  линейный  полином: . Следовательно, класс линейных функций функционально замкнут.

Рассмотрим  еще одно деление булевых функций на дна класса: класс гонных и класс немонотонных функций. Для этого определим отношение порядка для наборов булевых переменных. Рассмотрим два набора: А=() и B=(). Если для всех i (i=l,2,…,n) , существует хотя бы одно такое i, при котором aj<j, то набор А меньше набора В. Это обозначается: А. Если для всех i, ai<i, но существует такое j, что аi>i, то наборы А и В несравнимы. Например: работы (010101) и (010010) несравнимы, а набор (0000101) меньше набора (0100101).

Определение 1.21. Булева функция i называется монотонной, если для любых двух наборов А и В из ее области определения, таких что, А<В, f(A}<f(B). Если хотя бы для одной пары наборов, таких, что А<В, f(A)>f(B), тс. функция немонотонна.

Пример. Среди булевых функций одной и двух переменных функции конъюнкции, дизъюнкция, константы 0 и 1 монотонны, функции отрицание, импликации,  эквивалентность,     штрих     Шеффера,     стрелка     Пирса немонотонны.

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

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

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

1.8. Функциональная полнота систем  булевых функций.

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

Теорема 1.9 (Поста). Для того, чтобы система функций была полна, необходимо и достаточно, чтобы она содержали хотя бы одну немонотонную, хотя бы одну нелинейную, хотя бы одну несамодвойтенную, хотя бы одну, не сохраняющую моль, к хотя бы одну, не сохраняющую единицу функцию.

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

Системы функций {v, , ¬} и  {,¬} являются функционально полными.

 

11