Консультация № 110773
24.11.2007, 12:36
0.00 руб.
0 2 1
Здравствуйте, уважаемые эксперты! Помогите пожалуйста, разобраться в решении следующих типов задач. Нужно подготовиться к контрольной работе...
№1. Доказать, что L принадлежит к (объединению классов T0, T1, S) .
№2.Как определить , когда данная функция принадлежит к классу монотонных функций? вот например если рассмотреть функцию (00000111) тут все понятно, она принадлежит потому что все единички строго под нулями (ведь так?..) А вот например если (00010111) то верно ли то что так как на наборе 011 стоит 1 а на 100 стоит 0 то функция не принадлежит..
Или же нужно определять принадлежность каким то другим способом?
Подскажите пожалуйста)
№3. Возможно Вы мне сможете подсказать какой нибудь сайт где можно скачать полезную книгу где разобраны примеры решения задач по булевой алгебре, например разложение функции по ее переменным, с этим я тоже не разобралась на 100%..
№4.Найти замыкание след систем (вообще не представляю как это делать..) {xvy, y+x} например.
Если что можете писать в асю 402120848
БОЛЬШОЕ ПРЕБОЛЬШОЕ ВСЕМ СПАСИБО !!!
С уважением, Гуля.

Обсуждение

Неизвестный
25.11.2007, 02:03
общий
это ответ
Здравствуйте, Gul4atai!

Я не специалист в этой области, потому подходите к моим ответам с некоторой долей скепсиса.

№1. Доказать, что L принадлежит к (объединению классов T0, T1, S) .

Интересно, согасно <a href="http://ru.wikipedia.org/wiki/Замкнутые_классы_булевых_функций">Википедии</a> "Ни один из классов Поста не содержится целиком в объединении четырёх остальных."
А Вам предлагают доказать обратное?

№2.Как определить , когда данная функция принадлежит к классу монотонных функций?
вот например если рассмотреть функцию (00000111) тут все понятно, она принадлежит потому что все единички строго под нулями (ведь так?..)
А вот например если (00010111) то верно ли то что так как на наборе 011 стоит 1 а на 100 стоит 0 то функция не принадлежит..
Или же нужно определять принадлежность каким то другим способом?
Подскажите пожалуйста)

Согласно сайта <a href="http://www.mathpages.com/home/kmath094.htm">Generating the Monotone Boolean Functions</a>: A given function F is NON-monotonic if and only if for some two input states I1 and I2 we have F(I1)=1 and F(I2)=0 and (I1 OR I2)=I2.
Т.е. можно определить, что функция не монотонна, если для набора 011 значение 1, а для набора 111 значение 0.
Т.о. Вам надо взять все наборы, для которых значение 1.
При замене 0 на 1 в любой позиции этих наборов, для нового набора Вы опять дожны получить 1.
Например, если у Вас 1 для наборов 010, 011, 111, а для остальных 0, то функция не монотонна.
Если Вы рассмотрите набор 010, то значение 1 должно быть для наборов 110, 011 и 111, но для 110 значение 0, т.е. функция не монотонна.

В Вашем случае для 00010111.
Значение 1 получается для наборов 011, 101, 110, 111.
Для набора 011 в это множество должен входить 111.
Для набора 101 в это множество должен входить 111.
Для набора 110 в это множество должен входить 111.
Все условия выполняются - функция монотонна.

№3. Возможно Вы мне сможете подсказать какой нибудь сайт где можно скачать полезную книгу где разобраны примеры решения задач по булевой алгебре, например разложение функции по ее переменным, с этим я тоже не разобралась на 100%..

Мне понравился сайт <a href="http://olddesign.isu.ru/~slava/do/disc/fr_bools.htm">http://olddesign.isu.ru/~slava/do/disc/fr_bools.htm</a>, где в конце страницы описывается очень наглядно как построить совершенную дизъюнктивную нормальную форму функции по таблице.
К сожалению не нашёл ничего подобного для коньюктивной нормальной формы.

№4.Найти замыкание след систем (вообще не представляю как это делать..) {xvy, y+x} например.

Это по определению класс монотонных фукнций, т.е. функций которые можно выразить только операциями И и ИЛИ.
давно
Профессор
230118
3054
15.10.2011, 19:04
общий
В Википедии нет такого утверждения. И утверждение задачи доказывается очень легко.
Пусть линейная функция не принадлежит к T0, T1. Докажем, что она самосопряженая.
f=a0+a1x1+...anxn
Так как она не принадлежит T0, то a0=1
Так как она не принадлежит T1, то a1+...an+1=0
a1+...an=1, среди коэффициентов a1...an нечетное число единиц.
f*=1+f(xi+1)=f(x)+1+a1+...an=f(x)
Форма ответа