Функция f(x1,x2,x3,x4)=1100101000111010. Выяснить,полна ли система функций {f, ¬x}. В случае полноты выяснить, является ли система базисом, и выразить через нее функцию xy.

задан 7 Янв '14 17:47

изменен 7 Янв '14 18:18

То, что у Вас указано в качестве f, это не функция, а двоичная последовательность. По идее, она задаёт функцию от 4 переменных, если считать, что первый бит задаёт значение f на (0,0,0,0), потом идёт значение f на (0,0,0,1), и так далее. Если именно такое соглашение имелось в виду, то я могу дать ответ.

(7 Янв '14 17:57) falcao

Да, именно так.

(7 Янв '14 18:06) redfox94
10|600 символов нужно символов осталось
0

Отрицание не принадлежит предполным классам $%T_0$%, $%T_1$% и $%M$%. Функция $%f$% несамодвойственна (в противном случае запись в виде двоичной последовательности, прочитанная слева направо и справа налево, должна приводить к противоположным картинам). Таким образом, всё сводится к вопросу о линейности функции $%f$%.

Разбивая запись на четвёрки, мы видим, что она такова: 1100 1010 0011 1010. Вторая четвёрка совпадает с последней, и результат при этом равен отрицанию последней из переменных. Это значит, что при $%x_2=1$% значение функции равно $%x_4+1$%. Для первой и третьей четвёрки, то есть при $%x_2=0$%, мы видим, что значение функции равно $%x_3$% для третьей секции и равно $%x_3+1$% для второй. Это значит, что в этом случае функция задаётся формулой $%x_1+x_3+1$%.

Теперь можно подобрать полином Жегалкина для функции $%f$%. Если её разложить по переменной $%x_2$% в виде $%u+x_2v$%, то $%u=x_1+x_3+1$%, и $%u+v=x_4+1$%. Отсюда ясно, что $%f(x_1,x_2,x_3,x_4)=1+x_1+x_3+x_2(x_1+x_3+x_4)$%. Полином Жегалкина нелинеен, откуда $%f\notin L$%, и система полна по критерию Поста.

ссылка

отвечен 7 Янв '14 19:01

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×1,476

задан
7 Янв '14 17:47

показан
2985 раз

обновлен
7 Янв '14 19:01

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru